- •Раздел 1. Модели линейного программирования и его приложения Тема 1. Математическое моделирование экономических систем
- •1.1. Описание процесса математического моделирования.
- •1.2. Примеры построения математических моделей простейших экономических задач
- •1. Задача об использовании ресурсов (планирование производства, задача оптимального использования удобрений и т.Д.).
- •2. Оптимальное смешивание (составление рациона питания, смесей, задача о диете и т.Д.).
- •3. Задача об использовании мощностей (задача о загрузке оборудования)
- •4. Задача о раскрое материалов
- •Рекомендованная литература: [ 3, 8, 11, 12] Тема 2. Линейные векторные пространства
- •Понятие n-мерного пространства
- •Задача о закреплении самолетов за воздушными линиями.
- •Контрольные вопросы
- •Линейная зависимость векторов
- •2.3. Базис n-мерного векторного пространства
- •2.4. Система единичных векторов n-мерного векторного пространства
- •2.5. Решение системы линейных уравнений методом Жордана – Гаусса
- •Контрольные вопросы
- •Для приведения неравенства к равенству необходимо к его левой части прибавить неотрицательную величину . (2)
- •Пусть удовлетворяет уравнению (3) и неравенству (2), т.Е.
- •3.2. Выпуклые множества
- •3.3. Геометрическая интерпретация задачи линейного программирования
- •3.4. Свойства решений задачи линейного программирования
- •Контрольные вопросы
- •Примеры задач, решаемых графическим методом.
- •4.2. Графический метод решения злп с n переменными
- •Контрольные вопросы
- •5.2. Алгоритм симплекс-метода
- •5.3. Пример отыскания максимума линейной функции
- •5.4. Пример отыскания минимума линейной функции
- •Решение. Введем дополнительные неотрицательные переменные y5, y6 со знаком “-”, т.К. Неравенства имеют вид ””:
- •Симплексные таблицы
- •В общем случае достаточно воспользоваться правилом:
- •5.6. Метод искусственного базиса
- •Контрольные вопросы
- •Предположим, что некоторая организация решила закупить ресурсы s1, s2,…, Sm предприятия и необходимо установить оптимальные цены на эти ресурсы y1,y2,…,ym.
- •Аналогично стоимость всех затраченных ресурсов, идущих на изготовление единицы j-ой продукции, не может быть меньше стоимости окончательного продукта, т.Е.
- •6.2. Взаимно двойственные задачи линейного программирования и их свойства
- •6.3. Первая теорема двойственности
- •6.4. Вторая теорема двойственности
- •Рассмотренная теорема является следствием следующей теоремы.
- •6.5. Объективно обусловленные оценки и их смысл
- •Контрольные вопросы
- •7.2. Нахождение опорного плана
- •Пример 1. Исходные данные приведены в таблице 1.
- •7.3. Метод последовательного улучшения плана перевозок, цикл пересчета
- •7.4. Решение транспортной задачи методом потенциалов
- •Приложения транспортной задачи к решению некоторых экономических задач
- •Контрольные вопросы
- •Понятие цикла. Рекомендованная литература: [ 3, 5, 6, 7, 8, 11]
- •Тема 8. Элементы теории матричных игр
- •8.1. Предмет теории игр, основные понятия
- •8.2. Платежная матрица. Нижняя и верхняя цена игры
- •8.3. Решение игры в смешанных стратегиях
- •Решая эту систему, получим оптимальную стратегию:
- •8.4. Геометрическая интерпретация игры 2 х 2
- •8.5. Приведение матричной игры к задаче линейного программирования
- •Составив расширенные матрицы для задач, убеждаемся, что одна матрица получилась из другой транспонированием:
- •Контрольные вопросы
- •Графический метод решения игры mx2. Рекомендованная литература: [ 1, 2, 4, 9, 12] раздел 2. Модели нелинейного программирования
- •Тема 9. Нелинейное программирование
- •9.1. Общая задача нелинейного программирования
- •9.2. Метод множителей Лагранжа
- •9.3. Обобщёние метода множителей Лагранжа
- •9.4. Теорема Куна-Таккера
- •9.5. Модели выпуклого программирования
- •9.6. Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации
- •Контрольные вопросы
- •Задачі про мінімізацію розходу горючого літаком за набором висоти та швидкості. Рекомендованная литература: [ 3, 6, 7, 8, 11] Бібліографічний список
Контрольные вопросы
Предмет теории игр на основе понятия матричных игр.
Решение игр с седловой точкой. Принцип минимакса.
Решение игр размером 2х2 в смешанных стратегиях.
Геометрическая интерпретация игры 2х2.
Графический метод решения игры 2xn.
Графический метод решения игры mx2. Рекомендованная литература: [ 1, 2, 4, 9, 12] раздел 2. Модели нелинейного программирования
Тема 9. Нелинейное программирование
Розглянуті питання з теми:
9.1. Общая задача нелинейного программирования
9.2. Метод множителей Лагранжа
9.3. Обобщёние метода множителей Лагранжа
9.4. Теорема Куна-Таккера
9.5. Модели выпуклого программирования
9.6. Приближенное решение задач выпуклого программирования методом кусочно-линейной аппроксимации
9.1. Общая задача нелинейного программирования
Во многих экономических моделях зависимости между постоянными и переменными факторами лишь в первом приближении можно считать линейными, более детальное рассмотрение позволяет обнаружить их нелинейность. Как правило, такие показатели, как прибыль, себестоимость, капитальные затраты на производство и др., в действительности зависящие от объема производства, расхода ресурсов и т.п., не линейны.
Общая оптимизационная задача формулируется следующим образом: найти вектор X=(x1,x2, ... , xn), удовлетворяющий системе ограничений, представляемых в виде совокупности равенств и/или неравенств вида
i(x1, x2, ... , xn) bi , i=1,2,...,k, (1)
i(x1, x2, ... , xn) = bi , i=k+1,k+2,...,m
и доставляющий экстремальное значение целевой функции
Z=f(x1, x2, ... , xn); (2)
При этом на некоторые переменные x1, x2, ... , xn могут накладываться условия неотрицательности и целочисленности.
В случае если одна из функций i и/или f будет нелинейной, то полученную модель считают задачей нелинейного программирования (ЗНП). Класс ЗНП шире класса ЗЛП. Основные результаты получены при рассмотрении задач, в которых ограничения имеют линейный вид, а целевая функция нелинейная. Рассмотрим частные случаи, когда целевая функция сепарабельная (ее можно представить в виде суммы функций, каждая из которых зависит от одной переменной) или квадратичная.
С помощью большинства вычислительных методов можно найти точку локального оптимума, но нельзя установить, является ли она точкой глобального (абсолютного) оптимума или нет. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума.
Можно выделить класс нелинейных задач, которые относятся к классическим методам оптимизации. Рассмотрение ЗНП начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (1) содержит только уравнения, отсутствуют условия неотрицательности и целочисленности переменных, а функции i(x1, x2, ... , xn) и f(x1, x2, ... , xn) непрерывны и имеют частные производные не ниже второго порядка. Т.е. задачу оптимизации можно сформулировать так: найти переменные x1, x2, ... , xn, удовлетворяющие системе уравнений
i(x1, x2, ... , xn) = bi , i=1,2,...,m, (3)
и обращающие в максимум (минимум) целевую функцию
Z=f(x1, x2, ... , xn). (4)
Примером типичной и простой ЗНП является следующая: данное предприятие для производства какого-то продукта расходует два средства в количестве х1 и х2 . Это факторы производства, например, машины и труд, а величины х1 и х2 – затраты факторов производства. Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства Z=f(x1, x2). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (x1 и x2) и от цен этих факторов (с1 и с2). Совокупные издержки выражаются формулой b=c1x1+c2x2. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z.
Математическая модель этой задачи: найти переменные x1, x2, удовлетворяющие условиям b=c1x1+c2x2, х10, х20, при которых функция Z=f(x1, x2) достигает максимума. Как правило, функция Z может иметь произвольный нелинейный вид.
Максимум и минимум функции объединяется понятием экстремум, который может быть локальным или глобальным.
Используя классические методы оптимизации, следует четко представлять себе различие между локальным экстремумом функции, глобальным экстремумом и условным экстремумом.
Будем полагать, что функция Z=f(x1, x2, ... , xn)= f(Х) дважды дифференцируема в точке Х*=(x*1, x*2, ... , x*n) и в некоторой ее окрестности. Если для всех точек Х этой окрестности f(Х*) f(Х) или f(Х*) f(Х), то говорят, что функция f(Х) имеет локальный экстремум в Х* (соответственно максимум или минимум).
Точка Х*, в которой все частные производные функции f(Х) равны 0, называется стационарной точкой.
Необходимое условие экстремума: если в точке Х* функция f(Х) имеет экстремум, то частные производные функции в этой точке равны нулю:
Как правило, в практических задачах необходимо определить наибольшее и наименьшее значение функции (глобальный экстремум) в некоторой области.
Функция Z=f(Х) имеет в точке Х* заданной области D глобальный максимум (наибольшее значение) или глобальный минимум (наименьшее значение), если неравенство f(Х*) f(Х) или f(Х*) f(Х) соответственно выполняется для любой точки
Х D.
Если область D замкнута и ограничена, то дифференцируемая функция Z=f(Х) достигает в этой области своих наибольшего и наименьшего значений в стационарной точке или в граничной точке области (теорема Вейерштрасса).
Следовательно, чтобы найти наибольшее (наименьшее) значение функции Z=f(Х) в области D, нужно:
найти все стационарные точки внутри области D и вычислить значения функции в них;
исследовать функцию на экстремум на границе области D;
сравнить значения функции, полученные в п.1 и 2: наибольшее (наименьшее) из этих чисел и будет наибольшим (наименьшим) значением функции в этой области.
Граница области D аналитически может быть задана системой уравнений (условий) относительно переменных x1, x2, ... , xn. Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума.
Пусть необходимо найти экстремум функции Z=f(x1, x2, ... , xn) при условии, что переменных x1, x2, ... , xn удовлетворяют уравнениям
i(x1, x2, ... , xn) = 0 , i=1,2,...,m, m<n. (*)
Предполагается, что функции f и i имеют непрерывные частные производные по всем переменным. Уравнения (*) называют уравнениями связи.
Функция
Z=f(Х)
имеет в точке
,
удовлетворяющей уравнениям связи (*),
условный
максимум (минимум),
если неравенство f(
)
f(Х) (f(
)
f(Х)) имеет место
для всех точек Х, координаты которых
удовлетворяют уравнениям связи.
Легко заметить, что задача определения условного экстремума совпадает с ЗНП (3), (4).
Один из способов определения условного экстремума применяется в том случае, если из уравнений связи m переменных можно явно выразить через оставшиеся n-m переменных:
xi=I(xm+1, …,xn), i=1,2,…,m.
Подставив полученные выражения для xi в функцию Z, получим
Z= f(1(xm+1, …,xn),…, m(xm+1, …,xn), xm+1, …,xn), или Z=F(xm+1, …,xn).
Задача сведена к нахождению локального (глобального) экстремума для функции
n-m
переменных. Если в точке
функция
Z=F(xm+1,
…,xn)
имеет экстремум, то в точке
=(1
,…,m
,
функция
Z=f(x1,
x2,
... , xn)
имеет условный экстремум ( сформулированный
ранее).
Если число переменных n=2, нелинейные задачи можно решить графически. Ограничения должны быть записаны в виде неравенств i(x1, x2, ... , xn) bi , i=1,2,...,m, а целевая функция иметь вид Z=f(x1, x2).
Как и в случае геометрического решения ЗЛП, сначала необходимо построить область допустимых решение (ОДР) – множество точек плоскости, удовлетворяющих неравенствам i(x1, x2, ... , xn) bi. Но в отличии от ЗЛП здесь ОДР не обязательно будет выпуклой и может быть разрывной. Экстремум функции может достигаться и внутри области, и на границе.
После построения ОДР следует записать уравнения линий уровня целевой функции- множество точек плоскости, в которых целевая функция постоянна: f(x1, x2)=C, и определить направление возрастания (убывания) целевой функции, построив, например, линии уровня для разных значений С. Затем, перемещая линию уровня в нужном направлении в ОДР, найти точки области, в которых целевая функция принимает оптимальное значение.
Пример1. Найти минимальное и максимальное значения сепарабельной функции Z=(x1-4)2+(x2-6)2 при ограничениях:
x10,
x20.
Решение. ОДР представляет собой многоугольник ABCE (рис. 1). Если положить Z=Q (Q>0),то линии уровня целевой функции - это уравнение окружности (x1-4)2+(x2-6)2=Q. С уменьшением (увеличением) Q (квадрата радиуса) значения функции Z соответственно уменьшаются (увеличиваются).
Функция Z имеет два локальных максимума: в вершине A(1;0) функция
Рис.1 Z(A)=45, в вершине E(6;0) функция Z(e)=40.
Так как Z(А)>Z(E), то вершина A является точкой глобального максимума.
Решение. Минимальное значение функция принимает в точке M(4;1) (рис.2): Z(M)=0. Функция Z имеет два локальных максимума: в вершине E(6;0) функция Z(E)=5, в вершине С(0;4) функция Z(C)=25, причем глобальный максимум достигается в вершине С.
Рис. 2
x10,
x20.
Решение. В этом случае (рис.3) область допустимых решений не является выпуклой и состоит из двух отдельных частей. Минимальное значение функции Z=17 достигается в точках A(1;4) и L(4;1). Функция Z
Рис.3. имеет два локальных максимума: в точке D(2/3; 6) функция Z(D)=328/9 и в точке M(7; 4/7) функция Z(M)=2417/49. Точка M является точкой глобального максимума.
