Транспортная задача. Предположим, что заданы величины a1, a2, , an, и b1, b2, , bm, которые определяют максимальные производительности пунктов производства и минимальные

Предположим, что заданы величины a 1, a 2,…, an, и b 1, b 2,…, bm, которые определяют максимальные производительности пунктов производства и минимальные потребности пунктов потребления соответственно.

Обозначим:

c ij – стоимость перевозок единицы продукции из пункта производства A i в пункт потребления B j;

x ij – количество продукции, направляемое из пункта производства Ai в пункт потребления Bj. Совокупность чисел { x ij} образует план перевозок.

Требуется определить такой план перевозок, который минимизирует транспортные расходы.

Математически в транспортной задаче требуется найти план перевозок { xij }, который минимизирует транспортные расходы (2.1.1 – 2.1.4)

при ограничениях

,

,

x _ij ≥ 0.

Отсюда следует, что транспортная задача является задачей линейного программирования.

Решение матричных игр симплекс – методом

Для определения значения игры v и оптимальных стратегий игрока I p 1, p 2,…, pn необходимо решить задачу линейного программирования:

найти переменные v, p 1, p 2,…, pn, которые максимизируют выигрыш v игрока I

max v

при ограничениях

для всех j = 1, 2,…, m

p 1 + p 2 +…+ pn = 1

p i ≥ 0, v - не имеет ограничения на знак.

Для определения значения игры v и оптимальных стратегий игрока I q 1, q 2,…, qm необходимо решить задачу линейного программирования:

найти переменные v, pi, которые максимизируют выигрыш v игрока I

max v

при ограничениях

для всех j = 1, 2,…, m

p 1 + p 2 +…+ pn = 1

p i ≥ 0, v - не имеет ограничения на знак.

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

Поиск по сайту: