46. Транспортная задача.

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.^[1][2] Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

47. Матричная игра, как пример двойственности задач л.П.

1. Двойственные задачи линейного программирования

Каждой задаче линейного программирования можно поставить в соответствие задачу, называемую двойственной к исходной.

Предположим, что в производстве используется m различных видов ресурсов, объем которых ограничен величинами b₁, b₂,.., b_m. И производится n различных видов продукции, величина выпуска которых определяется переменными х₁, х₂,…, х_n. Известны нормы затрат каждого ресурса на единицу каждого вида продукции, образующие матрицу

.

Известна также стоимостная оценка (цена) единицы продукции каждого вида с₁, с₂,…, с_n.

Задача сводится к следующему: найти такие значения переменных х₁, х₂,…, х_n, при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигает максимума.

В математической форме задача записывается следующим образом: максимизировать

L = c₁x₁+c₂x₂+…+c_nx_n (1.1)

при условиях (1.2)

³0 (j=1, 2,.., n).

На базе тех же исходных данных может быть поставлена еще одна задача, в которой переменными величинами являются оценки у₁,у₂,…,у_m, приписываемые каждому виду ресурсов. Они должны быть такими, чтобы общая оценка всего имеющегося количества ресурсов была минимальной, но при условии, что суммарная оценка ресурсов, расходуемых на единицу любого вида продукции, будет не меньше, чем цена за эту единицу.

Математическая задача записывается следующим образом: минимизировать

`L = b₁y₁+b₂y₂+…+b_my_m (1.3)

при условиях (1.4)

Задачи (1.1) – (1.2) и (1.3) – (1.4) образуют пару взаимодвойственных задач, и любая из них может рассматриваться как исходная.

Сосредотачивая внимание на экономическом содержании и размерности постоянных переменных величин рассматриваемых задач, можно записать следующие соотношения:

для прямой (исходной) задачи

максимизируемая функция

ограничивающие условия

_;

для двойственной задачи

минимизируемая функция

ограничивающие условия

_.

 

 

Эти задачи обладают следующими свойствами:

1.    В одной задаче ищется максимум целевой функции, в другой – минимум.

2.    Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи, и наоборот.

3.    В каждой задаче система ограничений задается в виде неравенств, причем в задаче, в которой ищется максимум целевой функции, все неравенства вида «£», а в задаче, в которой находится минимум целевой функции, все неравенства вида «³».

4.    Коэффициенты при переменных системах ограничений записываются матрицами

,

транспонированными относительно друг друга.

5.    Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6.    Условия неотрицательности переменных сохраняются в обоих задачах.

Пример. Исходная задача

L = 10x₁+6x₂-4x₃®min

Приводим все неравенства системы ограничений исходной задачи к одному знаку:

L = 10x₁+6x₂-4x₃®min

Двойственная задача

`L = 2y₁+3y₂®max

при условиях

Связь между решениями исходной и двойственной задач Теорема двойственности

Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план и значение целевых функций задач равны между собой, то есть L_max = `L_min.

Если же целевая функция одной из пары двойственных задач неограниченна, то другая задача вообще не имеет решения.

Схема решения матричной игры с помощью симплексного метода

1.      Составляют пару двойственных задач линейного программирования, эквивалентных данной матричной игре.

2.      Определяют оптимальные планы пары двойственных задач, используя симплексный метод.

3.      Используя соотношение между планами пары двойственных задач и оптимальными стратегиями и ценой игры, находят решение матричной игры.

Пример. Решить игру, заданную матрицей , сведя ее к задаче линейного программирования.

Решение. Прежде всего проверяют, не имеет ли данная матрица седловую точку. Находим

.

Поскольку , то решением игры будут смешанные оптимальные стратегии, а цена игры заключена в пределах .

Нахождение оптимальных смешанных стратегий и аналогично решению двойственной пары задач линейного программирования.

Задача первого игрока.

Найти max при условиях

.

Задача второго игрока.

Найти min при условиях

.

Поскольку элементы матрицы А положительны, цена игры >0. Заменой переменных приходим к следующим задачам.

Задача первого игрока.

при условиях

.

 

Задача второго игрока

при условиях

.

здесь , , .

Решая одну из пары двойственных задач, получим решение другой. Решим задачу второго игрока.

б.	св.							б.	св.
	1	1	2	3	1	0			¾	0	7/4	5/2	1	-1/4
	3	1	2	0	0	1			¼	1	¼	½	0	¼
F	0	-1	-1	-1	0	0		F	¼	0	-3/4	-1/3	0	1/4

 

б.	св.
	3/7	0	1	10/7	4/7	-1/7
	1/7	1	0	¼	-1/7	2/7
F	4/7	0	0	4/7	3/7	1/7

 

В последней таблице получили оптимальное решение:

; ;

, отсюда .

Решение первой задачи находим в F-строке в столбцах, соответствующих дополнительным переменным:

; .

Чтобы перейти к компонентам оптимальных стратегий, умножим полученные значения переменных и на .

Ответ:

, , , , ,

; , .