7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача

Задача, модель которой содержит только линейные функции искомых переменных, называется задачей линейного программирования (ЛП).

В общем случае модель задачи лп имеет вид

(4.1)

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

(4.2)

(4.3)

где L – критерий (целевая функция), называемый также линейной формой;

n - количество переменных;

C_i – параметры (коэффициенты) критерия, не все C_i =0;

(4.2) - функциональные условия (ограничения);

– параметры условий (могут быть любыми действительными числами, но одновременно все не могут равняться нулю при i=const). Во многих случаях они имеют смысл удельных величин (расхода или затрат на единицу переменной, содержания в единице переменной и т. п.).

b_i – параметры (свободные члены), отражающие возможности по ресурсам, допустимые или требуемые значения показателей и т.п. (могут быть любыми действительными числами).

На часть или все переменные накладывается условие неотрицательности (4.3).

Задача состоит в определении таких значений переменных, удовлетворяющих условиям (4.2) и (4.3), которые доставляют в зависимости от контекста максимум или минимум линейной форме.

Сбалансированная транспортная задача

Транспортная задача - это модель ситуации, в которой требуется найти оптимальный план перевозки некоторого груза из конечного числа пунктов поставки (отправления) с заданными объемами производства в конечное число пунктов потребления (назначения) с требуемыми объемами потребностей при известных затратах на перевозку единицы груза между каждой парой пунктов поставки и потребления. Предполагается, что удельные затраты не зависят от количества перевозимого груза. Здесь под оптимальным понимается план, минимизирующий суммарные затраты на перевозки.

В качестве примера рассмотрим задачу с двумя пунктами отправления и тремя пунктами назначения, схема которой показана на рис.4.1. Здесь а₁ и а₂ – количество груза, которым располагают пункты отправления, b₁, b₂, b₃ – потребности в грузе пунктов назначения.

Задача является сбалансированной, если суммарная потребность равна суммарной возможности. В нашем примере это значит, что

Рис. 4.1.

Если ввести обозначения:

x_ij - количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения;

С_ij – затраты на перевозку единицы груза из i-го пункта отправления в j-й пункт назначения,

то исходные данные вместе с переменными можно представить в одной таблице (табл. 4.3):

Таблица 4.3

Пункты	B1	B2	B3	Количество груза
A1	С11 Х11	С12 Х12	С13 Х13	a1
A2	С21 Х21	С22 Х22	С23 Х23	a2
Потребность в грузе	b1	b2	b3

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

L=C₁₁x₁₁ + C₁₂x₁₂ + C₂₃x₂₃→min.

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

B₁: x₁₁+x₂₁=b₁;

B₂: x₁₂+x₂₂=b₂;

B₃: x₁₃+x₂₃=b₃.

Поскольку задача сбалансированная, весь груз из пунктов отправления должен быть вывезен. Это требование отражается в модели двумя равенствами:

А₁: х₁₁+х₁₂+х₁₃=а₁;

А₂: х₂₁+х₂₂+х₂₃=а₂.

Наконец, физический смысл переменных накладывает на них ограничение неотрицательности

x_ij0.

В результате мы получили модель транспортной задачи, содержащей только линейные функции. Очевидно, что характер модели не изменится при увеличении числа пунктов.

Игра двух лиц с нулевой суммой как задача линейного программирования

Рассмотрим платежную матрицу игры двух лиц, не имеющую седловых точек,

	B1	B2	…	Bn
A1	U11	U12	…	U1n
A2	U21	U22	…	U2n
…	…	…	…	…
Am	Um1	Um2	…	Umn

где платежи U_ij имеют смысл выигрышей игрока A.

Как известно, такая игра имеет решение в области смешанных стратегий. Пусть X=(x₁,x₂,…,x_m) – распределение вероятностей на стратегиях игрока A. Тогда согласно принципу гарантированного результата этот игрок будет выбирать такое поведение (распределение X ^*), которое максимизирует наименьший ожидаемый выигрыш

.

Обозначим через  минимальный ожидаемый выигрыш

.

Отсюда очевидно, что  не больше каждого ожидаемого выигрыша, и так как цель – максимальный выигрыш, то приходим к следующей эквивалентной задаче

L=→max

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

,

х_i0.

Это обычная линейная задача, оптимальное значение критерия которой L^*=^* есть цена игры. Ее решение определяет оптимальное поведение игрока А.

Для игрока B линейная модель строится аналогично, но тот же критерий минимизируется, так как  уже имеет смысл максимального проигрыша, а ограничения на вероятности y_j соответствуют строкам платежной матрицы и записываются как неравенства “меньше или равно”.