Материал: УП - Методы оптимальных решений

Так как игрок А стремится получить max от игры (υ = max), то функция будет минимизироваться, т. е. оптимальная стратегия игрока А определится из задачи линейного программирования вида: найти min при ограничениях (13).

Оптимальная смешанная стратегия игрока В определяется решением задачи: найти max φ(y) = = y₁ + y₂ + … + у_n при ограничениях (14).

Получим двойственную задачу линейного программирования, решив ее графически (для случая двух переменных) или симплексным методом, определим

.

Пример 23. Два сельскохозяйственных предприятия А и В выделяют денежные средства на строительство 3-х объектов. С учетом особенностей вкладов и местных условий прибыль предприятия А в зависимости от объ­_{ема финансирования выражается элементами матрицы .}

Будем предполагать, что убыток предприятия В при этом равен прибыли предприятия А. Требуется найти оптимальные стратегии предприятий А и В.

Решение.

1) Доминирующих строк и столбцов у матрицы нет, поэтому упростить ее нельзя. Обозначим чистые стратегии предприятия:

А: А₁, А₂, А₃;

В: В₁, В₂, В₃.

Предположим, что предприятие А располагает общей суммой тыс. руб., отпускаемой на строительство трех объектов, а предприятие В имеет тыс. руб. на строительство тех же объектов.

2) Проверим игру на наличие седловой точки:

	В1	В2	В3	аi	. Седловой точки нет,
А1 А2 А3	50 25 10	15 40 30	20 30 60	15 25 10
	50	40	60

поэтому решение игры определим в смешанных стратегиях. Цена игры а ≤ υ ≤ β => 25 ≤ υ ≤ 40.

3) Составим задачу линейного программирования:

_{а) найти для игрока А: min f = при ограничениях}

1

1

1, x_i ≥ 0.

_{б) найти для игрока В: max φ= y1 + y2 +y3 при ограничениях}

1

1

1, y_i ≥ 0.

Проще решить задачу для игрока В (двойственная задача): найти max φ = y₁ + y₂ + y₃ + 0y₄ + 0y₅ + 0y₆. Сведем ее к каноническому виду при ограничениях

Строим симплекс-таблицу и решаем ее. Последняя итерация представлена в табл. 28.

Таблица 28

Оптимальный план У^* = (0,0133; 0,0094; 0,0098; 0; 0;), max φ(у^*) = 0,0325.

Найдем решение прямой задачи:

СП БП

Y₁ Y₂ Y₃ Y₄ Y₅ Y₆

↕ ↕ ↕ ↕ ↕ ↕

Х₄ Х₅ Х₆ Х₁ X₂ Х₃

БП СП

_Х^*_{= (0,0102; 0,0180; 0,0043; 0; 0; 0), f(х}^*_{) = 0,0325,}

_{цена игры.}

_{Найдем верно}

_верно.

Итак, оптимальными смешанными стратегиями предприятий А и В являются стратегии р^* = (0,314; 0,554; 0,132) и g^* = (0,409; 0,289; 0,302). Это означает, что из общей суммы а тыс. руб., выделяемых предприятием А на строительство 3-х объектов, на долю 1-го объекта должно выделяться 31,4 %, 2-го – 55,4 %, 3-го – 13,2 % этой суммы. Аналогично распределяются средства b тыс. руб., предприятием В: так на долю 1-го объекта расходуется 40,9 %, 2-го – 28,9 %, 3-го – 30,2 % общей суммы. Такое распределение денежных средств предприятиями А и В по трем строящимся объектам позволит им получить max прибыль 30,77 тыс. руб.

Пример 24. Найти решение игры, заданной матрицей.

_А= .

Решение.

Попробуем упростить матрицу:

1) Элементы 1-го столбца не больше элементов 2 столбца (т. е. 1 столбец доминирует над 2-м);

2) Элементы 3-го столбца не больше элементов 4-го и 5-го столбцов (т. е. 3-й столбец доминирует над 4-м и 5-м столбцом)

1 Стр доминирует над 3 стр

3) Проверим игру на наличие седловой точки.

4) Составим задачу линейного программирования

а) для игрока А: min f_(х) = x₁ + x₂ при ограничениях

б) для игрока В: max φ_(y) = У₁ + У₂ при ограничениях

5) Решим графически прямую задачу (рис. 15):

г) оптимальное решение получим в точке В.

Решим систему

Тогда

min f = .

Точка В₁ – оптимальное решение – 9у₁ = = max φ = υ = ден. ед. – цена игры,

Следовательно, игрок А применяет стратегию А₁ с вероятностью , а стратегию А₂ с вероятностью , его выигрыш при этом в среднем составит ден. ед.