Линейное программирование (стр. 5 из 8)
Для оптимальной стратегии S*A все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:
(2.3.1)Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:
x1 = p1/v, x2 = p2/v , ..., pm/v (2.3.2)
Тогда система (2.3.1) примет вид:
(2.3.3)Цель игрока А — максимизировать свой гарантированный выигрыш, т.е. цену игры v.
Разделив на v ≠ 0 равенство p1 + p2 + ...+ pm = 1 , получаем, что переменные x1 (i = 1, 2, ..., m) удовлетворяют условию: x1 + x2 + ...+ xm = 1/v. Максимизация цены игры v эквивалентна минимизации величины1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных xi ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (2.3.3) и при этом линейная функция
Z = x1 + x2 + ...+ xm, (2.3.4)
обращалась в минимум. Это задача линейного программирования. Решая задачу (2.3.3)—( 2.3.4), получаем оптимальное решение p*1 + p*2 + ...+ p*m и оптимальную стратегию SA .
Для определения оптимальной стратегии S*B = (q*1 + q*2 + ...+ q*n) следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти
. Переменные q1 , q2 , ..., qn удовлетворяют неравенствам: 
(2.3.5)которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял, игрок А.
Если обозначить
yj = qj/v, j = 1, 2, ..., n, (2.3.6)
то получим систему неравенств:
(2.3.7)Переменные yj (1, 2, ..., n) удовлетворяют условию
.Игра свелась к следующей задаче
Определить значения переменных yj ≥ 0, j = 1, 2, ..., n, которые удовлетворяют системе неравенств (2.3.7) и максимизируют линейную функцию
Z' = y1 + y2 + ...+ yn, (2.3.8)
Решение задачи линейного программирования (2.3.6), (2.3.7) определяет оптимальную стратегию S*B = (q*1 + q*2 + ...+ q*n) . При этом цена игры
v = 1 / max, Z' = 1 / min Z (2.3.9)
Составив расширенные матрицы для задач (2.3.3), (2.3.4) и (2.3.7), (2.3.8), убеждаемся, что одна матрица получилась из другой транспонированием:
Таким образом, задачи линейного программирования (2.3.3), (2.3.4) и (2.3.7), (2.3.8) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности.
3. Практическая часть
Постановка задачи: Для производства трёх видов продукции используется три вида сырья. Нормы затрат каждого из видов сырья на единицу продукции данного вида, запасы сырья, а также прибыль с единицы продукции приведены в таблице:
| Продукция/сырьё | А | В | С | Запасы сырья, ед. |
| I | 4 | 2 | 0 | ≤19 |
| II | 0 | 1 | 1 | = 8 |
| III | 1 | 2 | 0 | ≤24 |
| Прибыль, ден. ед. | 3 | 7 | 2 | ≥max |
Определить план выпуска продукции для получения максимальной прибыли, чтобы сырьё IIвида было израсходовано полностью. Оценить каждый из видов сырья, используемых для производства продукции.
Вид таблицы по заданию поставленной задачи:
| Вид сырья | Нормы затрат сырья (кг) на единицу продукции | ||
| А | В | С | |
| IIIIII | 401 | 212 | 010 |
| Цена единицы продукции (руб.) | 3 | 7 | 2 |
Решениепоставленной задачи:
Предположим, что производится x1изделийА, 
изделийВи
изделийС.Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции3.1.Построим математическую модель задачи:
тогда функция цели:
Z-0 = 3X1 + 7X2 + 2X3 – совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать.
Подсчитаем затраты сырья:
Сырье 1-го типа: 4 х1 + 2 х2 + 0 х3 , по условию затраты не превосходят 19,
Сырье 2-го типа: 0 х1 + 1 х2 + 1 х3, по условию затраты не превосходят 8,
Сырье 3-го типа: 1x1 + 2x2 + 0x3, по условию затраты не превосходят 24.
при следующих условиях:
| 4 | X1 | + | 2 | X2 | + | 0 | X3 | + | X4 | ≤ | 19 |
| 0 | X1 | + | 1 | X2 | + | 1 | X3 | + | X5 | = | 8 |
| 1 | X1 | + | 2 | X2 | + | 0 | X3 | + | X6 | ≤ | 24 |
X1, X2, X3 ≥ 0.
4X1+2X2+X4 ≤ 19
X2 + X3 +X5 = 8
X1+ 2X2+X6 ≤24
3.2 Выбираем метод решения и приводим задачу к каноническому виду:
Пришли к задаче линейного программирования:
припишем каждому из видов сырья, используемых для производства продукции.Тогда общая оценка сырья, используемого на производство продукции, составит:
Получили математическую модель. Необходимо максимизировать функцию цели ↓
Z-0 (x1, x2, x3) = 3X1 + 7X2 + 2X3 → max
Введем дополнительные переменные X4, X5, X6.
| Z-0= | 3 | X1 | + | 7 | X2 | + | 2 | X3 | -(max) |
| при системе ограничений: |
Преобразуем первое ограничение:
| 4 | X1 | + | 2 | X2 | + | 0 | X3 | + | X4 | = | 19 |
| 0 | X1 | + | 1 | X2 | + | 1 | X3 | + | X5 | = | 8 |
| 1 | X1 | + | 2 | X2 | + | 0 | X3 | + | X6 | = | 24 |
Получили задачу:
4X1+2X2+X4 = 19
X2 + X3 +X5 = 8
X1+2X2 +X6 =24
3.3 Решаем задачу путем сведения к задаче линейного программирования:
Xi≥0 ; 0-Z= -3X1- -7X2- -2X3
Приведем задачу к канонической форме.
Задача линейного программирования записана в канонической форме, если она формулируется следующим образом.
Требуется найти вектор
, доставляющий максимум линейной форме 
при условиях
где
Решим задачу симплекс-методом
Строим начальную симплекс-таблицу:
| Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | Свободные члены |
| X4 | 4 | 2 | 0 | 1 | 0 | 0 | 19 |
| X5 | 0 | 1 | 1 | 0 | 1 | 0 | 8 |
| X6 | 1 | 2 | 0 | 0 | 0 | 1 | 24 |
| 0-Z | -3 | -7 | -2 | 0 | 0 | 0 | 0 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-7). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.
Пересчитаем таблицу:
| Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | Свободные члены |
| X4 | 4 | -2 | -2 | 1 | 0 | 0 | 3 |
| X2 | 0 | 1 | 1 | 0 | 1 | 0 | 8 |
| X6 | 1 | -2 | -2 | 0 | 0 | 1 | 8 |
| 0-Z | -3 | 7 | 5 | 0 | 0 | 0 | 56 |
Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-3). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца.
Тогда каноническую форму задачи ЛП можно представить в следующем матричном виде эквивалентном первоначальному: