- •Тема 1. Математическая модель задачи линейного программирования (злп)
- •1. Предмет математического программирования
- •2. Математическая модель мп
- •3. Основные типы задач мп:
- •4. Многокритериальная оптимизация
- •5. Основные понятия теории оптимизации
- •6. Постановка злп. Различные формы записи ее математической модели
- •Тема 2. Графический метод решения злп. Закономерности и общие свойства решения злп
- •1. Геометрическая интерпретация решения злп
- •2. Алгоритм решения злп графическим методом
- •3. Возможные случаи области допустимых решений при решении злп графическим методом:
- •4. Основные свойства решений злп:
- •5. Классификация решений злп
- •6. Решение злп с точки зрения линейной алгебры
- •Тема 3. Симплексный метод решения задач линейного программирования
- •1. Суть симплексного метода
- •2. Критерий оптимальности решения злп
- •3. Алгоритм основного симплекс-метода:
- •4. Алгоритм двойственного симплекс-метода:
- •5. Алгоритм смешанного симплекс-метода:
- •6. Особые случаи симплекс-метода:
- •Тема 4. Модифицированный симплекс-метод решения злп. Устойчивость оптимального решения злп
- •1. Обращенный базис и симплекс-множители
- •2. Модифицированный симплекс-метод
- •3. Устойчивость оптимального решения злп:
- •Тема 5. Двойственность в линейном программировании
- •1. Понятие двойственности и теневой цены
- •2. Правила построения двойственной злп
- •3. Основные теоремы двойственности и их экономическое содержание
- •Тема 6. Элементы теории матричных игр
- •1. Основные понятия
- •2. Теоремы теории игр для парных матричных игр с нулевой суммой
- •3. Способы решения задач ти:
- •Тема 7. Матричные статистические игры
- •1. Понятие статистической игры
- •2. Критерии выбора оптимальной стратегии при решении статистической игры
- •3. Кооперативные игры
- •Тема 8. Транспортная задача (тз)
- •1. Постановка тз
- •2. Математическая модель тз
- •3. Решение тз методом потенциалов
- •4. Проверка плана на оптимальность
- •5. Цикл пересчета
- •6. Метод дифференциальных рент
- •7. Дополнительные ограничения тз
- •Тема 9. Дискретное программирование
- •1. Задача целочисленного линейного программирования
- •2. Метод Гомори
- •3. Метод ветвей и границ
- •Тема 10. Элементы нелинейного программирования
- •1. Постановка задачи нелинейного программирования
- •2. Метод множителей Лагранжа
- •3. Задача выпуклого программирования
- •4. Задача квадратического программирования
- •Тема 11. Метод динамического программирования
- •1. Общая постановка задачи динамического программирования
- •2. Принцип оптимальности. Функциональные уравнения Беллмана
- •3. Задача оптимального распределения инвестиций
- •4. Задача о замене оборудования
- •Тема 12. Программирование на сетях
- •1. Основные понятия теории графов
- •2. Экстремальное дерево графа
- •3. Матричные способы задания графов. Упорядочение элементов орграфа
- •4. Потоки на сетях. Постановка задачи о максимальном потоке
- •5. Разрез на сети. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке
- •Тема 13. Планирование на сетях
- •1. Понятие сетевого графика
- •2. Основные параметры сг
- •3. Связь временных параметров сг
- •4. Алгоритм расчета параметров сг:
2. Теоремы теории игр для парных матричных игр с нулевой суммой
Теорема 6.1. (Основная теорема ТИ) Всякая конечная игра имеет цену, и у каждого игрока существует, по крайней мере, одна оптимальная стратегия.
Теорема 6.2. В матричной игре нижняя цена игры не превосходит верхней цены игры, то есть , а для цены игры с справедливо: a £ с £ b.
Определение 6.4. Смешанной стратегией первого (второго) игрока называется вектор , где и , ( , где и ).
Теорема 6.3. Игра с седловой точкой имеет оптимальное решение в чистых стратегиях.
Теорема 6.4. (Теорема Неймана) Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях, если чистую стратегию считать частным случаем смешанной, когда одна вероятностная компонента равна 1, а остальные – нулю.
Теорема 6.5. Для того чтобы смешанные стратегии и были оптимальными для игроков А и В в игре с платежной матрицей и выигрышем с, необходимо и достаточно выполнение неравенств:
– сложение по столбцу,
– сложение по строке.
То есть первый игрок, придерживаясь своей оптимальной стратегии , не может выиграть меньше с, второй игрок, придерживаясь своей оптимальной стратегии , не позволит первому выиграть больше с.
Данная теорема дает ответ на вопрос о существовании решения игры и определяет путь решения.
Теорема 6.6. (Об активных стратегиях) Если игроки придерживаются своих активных стратегий, то выполняется следующая система уравнений:
– сложение по столбцу активной стратегии,
– сложение по строке активной стратегии.
Теорема 6.7. Оптимальные смешанные стратегии и соответственно игроков А и В в матричной игре с платежной матрицей с ценой с будут оптимальными и в матричной игре с платежной матрицей с ценой игры , где b>0.
3. Способы решения задач ти:
1) Простейшими из матричных игр являются игры , и . Использование теоремы 6.6 для таких игр составляет первый способ решения.
Пример 1. Найти решение игры, заданной матрицей:
.
Решение:
Найдем нижнюю и верхнюю цену игры:
,
.
Следовательно, . Так как , то игра не является игрой с седловой точкой и решение следует искать в смешанных стратегиях.
2) Пусть и – оптимальные смешанные стратегии первого и второго игроков соответственно. Тогда по теореме 6.6 получим системы:
и
Решим первую систему. Вычитая из первого второе уравнение системы, получим или . Подставив это соотношение в третье уравнение, будем иметь , откуда . Следовательно, . Цену игры можно найти, если подставить полученные значения и в одно из первых уравнений системы. Так, согласно первому уравнению .
Аналогично получаем решение второй системы:
Ответ: , , с=22/3.
2) Графический способ решения матричных игр , и .
Пример 2. Найти решение игры, заданной матрицей:
.
Решение:
1) Найдем нижнюю и верхнюю цену игры:
,
.
Следовательно, .
2) Изобразим стратегии игроков на плоскости pОq (рис. 6.1). Горизонтальной выбирается та ось, которая соответствует игроку с двумя стратегиями. На горизонтальной оси Оp выбирается отрезок . Из точек 0 и 1 восстановим перпендикуляры и на них отложим выигрыши первого игрока при использовании вторым игроком своих возможных стратегий. Соединим соответствующие точки на перпендикулярах прямыми: . Точки этих прямых будут соответствовать средним выигрышам первого игрока при использовании некоторой смешанной стратегии.
Рис. 6.1
Нижняя ломаная соответствует среднему гарантированному выигрышу. Вершина ломаной - максимальный гарантированный выигрыш. Следовательно, цена игры и оптимальные стратегии определяются и .
3) Составим уравнения этих прямых и определим цену игры с и смешанные стратегии:
и
Ответ: , , с=7/4.
Замечание 6.1. При решении игры, заданной матрицей , минимально удаленная от оси q точка верхней ломанной (ограничивающей максимальные средние выигрыши первого игрока) соответствует минимально возможному проигрышу второго игрока для оптимальных смешанных стратегий обоих игроков.
3) Вышеуказанные способы решения задач ТИ имеют ограничение на использование. Способ сведения задачи ТИ к ЗЛП по теореме 6.5 лишен этого недостатка.
Задача. Предприятие может выпускать два вида продукции , получая при этом прибыль, зависящую от спроса, который может быть в одном из четырех состояний . Дана матрица , элементы которой характеризуют прибыль, которую получит предприятие при выпуске i-й продукции при j-м состоянии спроса. Определить оптимальные пропорции в выпускаемой продукции с помощью линейного программирования, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределенным.
Решение задачи:
Упростим платежную матрицу, отбросив стратегии заведомо невыгодные или дублирующие. Так, вторая стратегия (второй столбец) является явно невыгодной по сравнению с первой (элементы второго столбца больше элементов первого столбца), так как цель игрока В – уменьшить выигрыш игрока А. Поэтому второй столбец можно отбросить. Получим матрицу .
Замечание 6.2. Если в платежной матрице элементы k-той строки не меньше соответствующих элементов s-той, s-тая строка вычеркивается.
Замечание 6.3. Если элементы l-того столбца не превосходят соответствующих элементов r-того столбца, то r-тый столбец вычеркивается.
Найдем нижнюю и верхнюю цену игры:
,
.
Следовательно, .
Согласно теореме 6.5 о цене игры и . Пусть для определенности с>0. Разделим каждое неравенство на с:
и .
Обозначив (6.1) и (6.2) и приняв во внимание, что первый игрок стремится по возможности увеличить цену игры, тогда как второй – уменьшить ее величину, и так как и , то
.
В результате получим пару взаимно двойственных задач:
и .
Решив одну из этих задач, получим решение другой. Решать удобнее ту задачу, в которой число столбцов больше числа строк. При этом необходимо выполнить обратный переход:
, , . (6.3)
Вернемся к решению поставленной задачи. По матрице игры составим пару двойственных задач линейного программирования:
и
Решим вторую задачу основным симплекс-методом, предварительно преобразовав математическую модель задачи к канонической форме с предпочтительными переменными:
|
|
|
|
|
|
|
|
0 |
* |
7 |
2 |
9 |
1 |
0 |
1 |
|
2 |
9 |
0 |
0 |
1 |
1 |
|
|
-1* |
-1 |
-1 |
0 |
0 |
0 |
|
1 |
|
1 |
2/7 |
9/7 |
1/7 |
0 |
1/7 |
* |
0 |
59/7 |
-18/7 |
-2/7 |
1 |
5/7 |
|
|
0 |
-5/7* |
2/7 |
1/7 |
0 |
-1/7 |
|
2 |
|
1 |
0 |
|
|
|
49/413 |
|
0 |
1 |
-18/59 |
-2/59 |
7/59 |
5/59 |
|
|
0 |
0 |
28/413 |
49/413 |
5/59 |
-84/413 |
Получили оптимальный план решения второй задачи: , . Тогда, используя соответствие между переменными исходной и двойственной задач, выпишем оптимальное решение первой задачи: , .
По формуле 6.3 получим цену игры .
Используя формулы 6.1 и 6.2, получим оптимальные смешанные стратегии игроков:
и .
Ответ: , , .
Таким образом, в ответе указаны оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом состоянии спроса.
Педагогический комментарий. Данное лекционное занятие закладывает основы для формирования следующих профессиональных умений студентов-экономистов: умение выявлять проблемы экономического характера при анализе конкретных ситуаций, предлагать способы их решения и оценивать ожидаемые результаты; умение разрабатывать и обосновывать варианты эффективных производственно-технологических решений; умение ставить цель и формулировать задачи, связанные с профессиональной деятельностью, умение использовать для их решения методы изученных дисциплин; умение логически мыслить; умение совершенствовать составление оперативно-производственного плана с использованием инструментария математического программирования; умение эффективно управлять экономическими процессами и регулировать использование комплекса имеющихся ресурсов; умение вырабатывать компромиссные рекомендации при конфликтных ситуациях принятия решения.