Пример задачи, решаемой методом кусочно-линейной аппроксимации
Задача. Найдите минимум функции при ограничениях:
Решите данную задачу методом кусочно-линейной аппроксимации.
Решение.
Данная задача является задачей ВП. При условии неотрицательности переменных неравенство показывает, что может изменяться лишь от 0 до 2, а – от 0 до 4.
Отрезок [0;2] разобьем точками , а отрезок [0;4] точками Положим: .
Удобно сначала вычислить необходимые значения этих функций (т. к. имеем лишь одно ограничение, т. е. m=1, будем писать j 1 и j 2 вместо j 11 иj 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. Предприятие располагает двумя способами производства данного вида продукции. В течение рассматриваемого периода времени необходимый объем продукции равен 100= Х1+ Х2, где Х1и Х2 – объемы производства по соответствующему технологическому способу. Затраты производства S при каждом способе зависят от объемов нелинейно:
, .
Необходимо так распределить объем производства между технологическими способами, чтобы минимизировать общие затраты производства.
|
|
2. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (6,10), (10,50), (60,80). Нижняя граница доходности портфеля задана равной 20.
3. Найдите минимум функции при ограничениях
Решите данную задачу методом кусочно-линейной аппроксимации.
4. Найдите максимум функции при ограничениях
Решите данную задачу двумя методами.
Лабораторная работа №4. Игровые модели
Пусть антагонистическая игра двух участников задана платежной матрицей || aij ||, с положительными элементами (условия положительности всегда можно добиться, прибавив ко всем элементам матрицы одно и тоже положительное число) и не имеет седловую точку. Тогда ее решение может быть найдено с помощью ЗЛП. Так, для 1-го игрока достаточно найти min f = x 1 + x 2 +…+ xm при системе ограничений , x i ≥0, для , а затем вектор оптимальных смешанных стратегий (p 1 , p 2 ,…, pm), где .Для второго игрока необходимо найти max f = x 1 + x 2 +…+ xn при системе ограничений , x i ≥0, для а затем вектор оптимальных смешанных стратегий (p 1 , p 2 ,…, 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).
Дата добавления: 2019-02-22; просмотров: 1058; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!