- •Раздел 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] Бібліографічний список
Решая эту систему, получим оптимальную стратегию:
р*1
=
,
р*2
=
.
(3)
Подставляя
значения р*1
и р*2
в одно из уравнений (*), получим:
v
=
.
(4)
Применяя
теорему об активных стратегиях при
отыскании S*B
- оптимальной
стратегии игрока B,
получаем, что при любой чистой стратегии
игрока А (А1
или А2)
средний проигрыш игрока В равен цене
игры v,
т.е.
Тогда оптимальная стратегия S*B (q*1,q*2):
q*1=
,
q*2
=
.
(5)
Пример 4. Найти решение игры, заданной матрицей из примера 1.
Решение. Имеем =-1, =1; матрица не имеет седловой точки.
Находим оптимальные стратегии и цену игры: р*1=р*2= q*1=q*2=1/2, v =0.
Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2, при этом средний выигрыш равен 0.
8.4. Геометрическая интерпретация игры 2 х 2
Р
ешение
игры 22
допускает наглядную геометрическую
интерпретацию.
П
усть
игра задана платежной матрицей Р=(aij),
i,j=1,2.
На оси абсцисс отложим единичный отрезок
А1А2.
Левый конец отрезка - точка А1
(x=0)
соответствует стратегии A1,
правый стратегии A2.
Все промежуточные точки х этого отрезка
соответствуют некоторым смешанным
стратегиям SA
1-го игрока, где р1=1-x,
р2=x.
На концах выбранного отрезка проведем
прямые, перпендикулярные оси абсцисс,
на них будем откладывать выигрыши при
соответствующих чистых стратегиях А1
и А2.
Если игрок B
применяет стратегию B1,
то выигрыш при использовании чистых
стратегий A1
и A2
составляет соответственно a11
и a21.
Отложим эти точки на прямых и соединим
полученные точки прямой B1B1.
Средний выигрыш 1,
соответствующий смешанной стратегии
SA,
определяется по формуле математического
ожидания
и равен ординате точки M1,
лежащей на прямой B1B1
(рис. 1).
Таким образом, если игрок А применяет смешанную стратегию, то его выигрышу соответствует некоторая точка М, лежащая на этой прямой.
А
налогично
можно построить отрезок B2B2,
соответствующий стратегии B2
игрока B
(рис. 2). При этом средний выигрыш
- ордината точки M2.
В соответствии с принципом минимакса оптимальная стратегия S*A такова, что минимальный выигрыш игрока А (при наихудшем поведении игрока В) обращается в максимум. Ординаты точек, лежащих на ломаной B1KB2 (рис. 3), показывают минимальный выигрыш игрока А при использовании им любой смешанной стратегии (на участке В1К – против стратегии В1, на участке КВ2 - против стратегии В2). Т.о., ломаная B1KB2 является нижней границей выигрыша, получаемого игроком A. Оптимальную стратегию S*A=(р*1,р*2) определяет точка K с координатами (x,y), в которой минимальный выигрыш достигает максимума, ее ордината равна цене игры: y= v, абсцисса х= р*1.
Чтобы
найти координаты точки К, найдем уравнения
прямых В1В1
и В2В2,
на пересечении которых она лежит. Прямая
В1В1
проходит через точки (0,а11)
и (1,а12),
подставив эти точки поочередно в общий
вид уравнения прямой y=kx+b,
получим ее уравнение y=k1x+b1.
Аналогично, прямая В2В2
проходит через точки (0,а21)
и (1,а22),
получим ее уравнение y=k2x+b2.
Решив систему
получим координаты точки К х и y.
Тогда, р*1=х
, р*2=1-х
и
v =y.
Используя геометрическую интерпретацию, можно найти решение игр 2n. Каждой из n стратегий игрока B соответствует прямая. Построив эти прямые, находят нижнюю границу выигрыша. Точка K, лежащая на нижней границе, для которой величина выигрыша наибольшая, определяет цену игры и ее решение. При этом определяются активные стратегии игрока B (соответствующие им прямые пересекаются в точке K); из геометрических соображений можно найти значения qj , соответствующие активным стратегиям игрока B.
Аналогично может быть решена игра m2, только в этом случае строят верхнюю границу выигрыша и на ней определяют минимум.
Следует отметить, что геометрические построения имеет смысл использовать для определения активных стратегий игроков. Затем решение игры можно получить с помощью формул (3) – (5), или соответствующие значения SA, SB и v находят из геометрических соображений. Формулы (3) – (5) можно использовать, так как из соответствующей матрицы исключаются все стратегии, кроме активных, и она содержит две строки и два столбца.
Пример 4. Предприятие может выпускать два вида продукции А1 и А2, получая при этом прибыль, зависящую от спроса, который может быть в одном из 4-х состояний В1, В2, В3, в4. Дана матрица
A
=
,
элементы которой aij
характеризуют прибыль, которую получит
предприятие при выпуске i-ой
продукции с j-м состоянием спроса .
Определить
оптимальные пропорции в выпускаемой
продукции, гарантирующие среднюю
величину прибыли при любом состоянии
спроса, считая его неопределенным.
Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платежной матрицей А.
Определяем верхнюю и нижнюю цены игры и проверяем, имеет ли игра седловую точку.
Нижняя
цена игры
.
Верхняя
ценя игры
.
Седловая точка отсутствует. Решение
игры S*A
= (р1*,р2*),
S*B
= (q1*,
q2*,
q3*,
q4*)
и
следует искать в смешанных стратегиях.
Откладываем
на оси абсцисс (рис.4) единичный отрезок
А1А2
. На левой
вертикальной оси откладываем отрезки
а11=2,
а12=4,
а13=1.5,
а14=3,
соответствующие стратегиям В1,
В2,
В3,
В4.
На правой вертикальной оси откладываем
отрезки а21=4,
а22=3,
а23=2,
а24=1,
соответствующие тем же стратегиям В1,
В2,
В3,
В4.
Ломаная B3KB4
соответствует нижней границе выигрыша.
Активные стратегии игрока B
– третья и четвертая, тогда q1*=0,
q2*=0.
Следовательно платежную матрицу можно
упростить: A
=
.
Ломаная B3KB4 является нижней границей выигрыша, получаемого игроком A. Оптимальную стратегию S*A=(р*1,р*2) определяют точка K с координатами (x,y). Ее ордината y равна цене игры: y= v, абсцисса х= р*1.
Чтобы
найти координаты точки К, найдем уравнения
прямых В3В3
и В4В4,
на пересечении которых она лежит. Прямая
В3В3
проходит через точки (0;1) и (1;2), подставив
эти точки поочередно в общий вид уравнения
прямой y=kx+b,
получим ее уравнение y=0.5x+1.5.
Аналогично, прямая В4В4
проходит через точки (0;3) и (1;1), получим
ее уравнение y=-2x+3.
Решив систему
получим координаты точки К х=0.6 и y=1.8.
Тогда, р*2=х=0.6
, р*1=1-х=0.4
и v
=y=1.8.
Следовательно, S*A = (0,4; 0,6), т.е. игрок A применяет стратегию A1 c вероятностью 0,4, а стратегию A2 – с вероятностью 0,6. При этом его выигрыш в среднем составит v=1,8 ед.
Оптимальные
стратегии игрока В найдем с помощью
формул (3)-(5). Запишем систему уравнений
Т.к.
цена игры нами уже найдена v=1,8,
то систему можно упростить:
Решив систему, получаем оптимальную
стратегию спроса В S*B
= (0, 0, 0.8,0.2)
С экономической точки зрения можно сделать вывод, что предприятие должно выпустить 40% продукции А1 и 60% продукции А2. А оптимальный спрос в 80% находится в состоянии В3 и в 20% - в состоянии В4.
П
ример
5.
Найти решение игры, заданной матрицей
A
=
.
Решение. Матрица имеет размерность 24. На рис. 5 построены прямые, соответствующие стратегиям игрока A. Жирной линией на рис. 5 изображена верхняя граница выигрыша игрока A.
Найдя верхнюю и нижнюю цену игры, определяем, что игра без седловой точки.
Точка
K
определяет цену игры. Активными
стратегиями для игрока A
являются первая и четвертая. Следовательно,
платежную матрицу можно упростить: A
=
.
Стратегию S*B
= (q1,
q2
) и цену игры v
находим геометрическим способом, найдя
уравнения прямых А1А1
и А4А4
( см. пример 4) и определив координаты
точки К. Получаем S*B
=(3/8; 5/8); v=27/8.
Стратегию S*A=(р*1,р*2,
р*3,
р*4)=
(р*1,
0, 0, р*4)
найдем по формулам (3)-(5) : S*A
=(7/8;0; 0; 1/8).
