- •И. В. Добрынина, р. Р. Яфаева
- •Введение
- •Лабораторная работа № 1. Задачи линейного и целочисленного линейного программирования Технология компьютерной реализации
- •Задача линейного программирования
- •Пример задачи линейного программирования
- •Задача целочисленного линейного программирования
- •Пример задачи целочисленного линейного программирования
- •Задачи для самостоятельного решения
- •Лабораторная работа № 2. Задачи транспортного типа
- •Примеры задач транспортного типа
- •Задачи для самостоятельного решения
- •Лабораторная работа № 3. Модели нелинейной оптимизации
- •Технология компьютерной реализации
- •Пример задачи нелинейной оптимизации
- •Задачи для самостоятельного решения
- •Лабораторная работа №4. Метод кусочно-линейной аппроксимации
- •Пример задачи, решаемой методом кусочно-линейной аппроксимации
- •Задачи для самостоятельного решения
- •Лабораторная работа № 5. Игровые модели
- •Пример задачи по теории игр, решаемой симплексным методом
- •Задачи для самостоятельного решения
- •Лабораторная работа № 6. Динамическое программирование
- •Задачи для самостоятельного решения
- •Литература
Пример задачи, решаемой методом кусочно-линейной аппроксимации
Задача. Найти минимум функции при ограничениях:
Решить данную задачу методом кусочно-линейной аппроксимации.
Решение.
Данная задача является задачей ВП. При условии неотрицательности переменных неравенство показывает, чтоможет изменяться лишь от 0 до 2, а– от 0 до 4.
Отрезок [0;2] разобьем точками , а отрезок [0;4] точкамиПоложим:.
Удобно сначала вычислить необходимые значения этих функций (т. к. имеем лишь одно ограничение, т. е. m=1, будем писать 1 и 2 вместо 11 и 12).
x1 |
x10 |
x11 |
x12 |
|
x2 |
x20 |
x21 |
x22 |
x23 |
x24 |
x1 |
0 |
1 |
2 |
|
x2 |
0 |
1 |
2 |
3 |
4 |
0 |
1 |
4 |
|
0 |
1 |
2 |
3 |
4 | ||
f1 |
2 |
0 |
2 |
|
f2 |
4 |
1 |
0 |
1 |
4 |
По формулам имеем:
Таким образом, приближенная задача для данной задачи ВП имеет вид: найти минимум функции при ограничениях:
Решая данную задачу линейного программирования, как описано ранее, получим:
Таким образом, оптимальное решение приближенной задачи (1;2), и .
Задачи для самостоятельного решения
1. Найти максимум функции при ограничениях
2. Найти минимум функции при ограничениях
3. Найти максимум функции при ограничениях
Лабораторная работа № 5. Игровые модели
Пусть антагонистическая игра двух участников задана платежной матрицей ||aij||, с положительными элементами (условия положительности всегда можно добиться, прибавив ко всем элементам матрицы одно и тоже положительное число) и не имеет седловую точку. Тогда ее решение может быть найдено с помощью ЗЛП. Так, для 1-го игрока достаточно найти min f=x1+x2+…+xm при системе ограничений ,xi ≥0, для , а затем вектор оптимальных смешанных стратегий (p1 ,p2 ,…,pm), где . Для второго игрока необходимо найти max f= x1+x2+…+xn при системе ограничений ,xi ≥0, для а затем вектор оптимальных смешанных стратегий (p1 ,p2 ,…,pn), где .
Пример задачи по теории игр, решаемой симплексным методом
Задача. Первый и второй игроки одновременно и независимо друг от друга показывают один, два или три пальца. Выигрыш или проигрыш (в денежных единицах) равен общему количеству показанных пальцев. Если это количество четное, то выигрывает первый игрок, а второй ему платит. Если же оно нечетное, то выигрывает второй игрок, а первый ему платит. Найти оптимальные стратегии каждого игрока.
Экономико-математическая модель
У каждого игрока имеется по три стратегии: показать один, два или три пальца. В соответствии с этим платежная матрица будет выглядеть следующим образом:
Выберем минимальные значения в каждой строке, а затем из них найдем максимальное. Это даст нам нижнюю цену игры. Она равна -3. Выберем максимальные значения в каждом столбце, а затем из них найдем минимальное. Получим верхнюю цену игры. Она равна 4. Так как нижняя цена игры не совпадает с верхней, то решение будем искать в смешанных стратегиях. Прибавляя ко всем элементам матрицы число, равное 5, перейдем к матрицы модифицированной игры:
,
которой соответствует задача линейного программирования для 1 игрока:
min f(x1, x2, x3) =x1+x2+x3
и задача линейного программирования для 2 игрока:
max f(x1, x2, x3) =x1+x2+x3
Решение.
Воспользовавшись симплексным методом, получим решения обеих задач, как описано ранее. Результаты приведены на рисунке.
Таким образом, оптимальная смешанная стратегия 1-го игрока совпадает с оптимальной смешанной стратегией 2-го игрока и равна (0,25;0,5;0,25).