Лекции Хуторецкий

Следовательно, за конечное число шагов мы построим поток y = (yij | (i, j) E) такой, что в графе G(y) = (V(y), E(y)) нет контуров и C(x) ≥ C(y) + A, где

N

A = rsCs .

s 1

Выберем произвольную вершину a V(y). Пусть W(a) V(y) ― множество всех вершин графа G(y), лежащих на путях, ведущих в вершину a, D(a) E(y) ― множество всех дуг,

входящих в эти пути. Поскольку yij = 0 для всех (i, j) E(y), условие (53) для i W(a) принима-

ет вид:

yki –	yij ≥ bi.
(k ,i ) E ( y )	(i, j ) E ( y )

Если i W(a) и (k, i) E(y), то k W(a) и (k, i) D(a). Если во второй сумме предыдущего нера-

венства заменить E(y) на D(a), то левая часть неравенства возрастет. Поэтому

yki –	yij ≥ bi.	(57)
(k ,i ) D (a )	(i, j ) D(a)

Если (i, j) D(a) и j a, то yij входит с противоположными знаками в неравенства (57)

для вершин i и j. Заметим, что a W(a), так как в графе G(y) контуров. Поэтому yia для i W(a)

входит только в неравенство (57) для вершины i (с коэффициентом –1). Суммируя неравен-

ства (57) для i W(a), получим:

– yia ≥	bi	≥ bi , или	yia	≤ | bi | = B.
(i,a ) D (a )	i W ( a )	i I	(i,a ) D (a )	i I

Следовательно, yij ≤ B для любой дуги (i, j) E(y), где B ― суммарная мощность всех источ-

ников.

Выше мы доказали, что C(x) ≥ C(y) + A. Пусть c0 = min{cij | (i, j) E(y)}. Понятно, что

C(y) ≥ c0 yij .

(i, j ) E ( y )

Если c0 ≥ 0, то C(y) ≥ 0 и C(x) ≥ A. Если же c0 < 0, то C(y) ≥ c0BN, где N ― число вершин в графе G(y).

Таким образом, C(x) ≥ min{A, c0BN} для любого потока x в графе G. #

Определение. Если (56) выполняется как равенство, то ТЗСП называют замкнутой или

сбалансированной.

Следствие 3.4.(1)

Предположим, что ТЗСП разрешима.

(а) Если задача замкнута, то все ограничения (53) в любом допустимом решении выпол-

няются как равенства.

(1) Доказательство оставляем читателю.

51

(б) Если задача не замкнута и все cij положительны, то в оптимальном решении ограниче-

ния (53) выполняются как равенства для i I+ I0 (нет избыточных перевозок) и как строгие неравенства ― для некоторых i I– (излишки в источниках).

Следствие 3.5. Матрица ТЗСП вполне унимодулярна.

Доказательство. Переменная xij имеет коэффициент –1 в ограничении (53) с номером i,

коэффициент 1 ― в ограничении (53) с номером j и в ограничении xij ≤ rij. Пусть A ― матри-

ца задачи. При фиксированном i сложим строки матрицы A, соответствующие ограничениям xij ≤ rij и результат прибавим к строке ограничения (53) с номером i. Выполнив эту операцию для каждого i, получим матрицу A1. В этой матрице столбец, соответствующий переменной xij имеет единицы в строке ограничения (53) с номером j и в строке ограничения xij ≤ rij. Под-

множества, указанные в условии (в) теоремы 3.3, сформируем следующим образом: в одно из них включим строки матрицы A1, соответствующие ограничениям (53), в другое ― осталь-

ные строки. Из теоремы 3.3 следует, что матрица A1 абсолютно унимодулярна. Но каждый минор матрицы A1 равен соответствующему минору матрицы A, которая, следовательно, то-

же абсолютно унимодулярна. #

Существует модификация метода потенциалов для замкнутой ТЗСП(1). Следствия 3.1 и 3.4 гарантируют целочисленность оптимального решения ТЗСП с целыми значениями bi и rij,

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

3.4.2. Несбалансированные и несовместные задачи

Рассмотрим ТЗСП с транспортной сетью G = (V, E).

Если задача разрешима и сумма интенсивностей вершин отрицательна (суммарное на-

личие товара больше суммарной потребности), то задачу можно сбалансировать следующим образом.

(1) Ввести в транспортную сеть G вершину с номером 0 и дуги (i, 0) для i I– с неограни-

ченными пропускными способностями (разрешить поставки в вершину 0 из любого источ-

ника).

(2) Положить затраты ci0 равными нулю или ущербу от невостребованности единицы то-

вара в источнике i.

(3) Положить b0 = – i V bi (тогда вершина 0 становится стоком).

Если условие (56) не выполняется (сумма интенсивностей вершин положительна), то ТЗСП несовместна. Задача может быть несовместной и тогда, когда условие (56) выполнено

(1) Конюховский П. Математические методы исследования операций в экономике. Спб.: Питер, 2000 (раздел 3.2.2).

52

(если пути от источников к некоторым стокам имеют недостаточные пропускные способно-

сти). В таком случае потребности нельзя полностью удовлетворить, но можно попытаться целесообразно распределить наличный товар.

Если задача несовместна, то для каждой пары (i, j) E такой, что i I– и j I+, введем в

сеть фиктивную дугу (i, j). Кроме того, если (56) не выполняется, то введем фиктивный ис-

точник, присвоим ему номер 0, и соединим его со всеми стоками фиктивными дугами. По-

ложим

b0 = – i V bi .

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

шими или равными ущербу от недопоставки единицы товара в сток j, а пропускные способ-

ности всех фиктивных дуг будем считать неограниченными.

Преобразованная таким образом задача замкнута и совместна по теореме 3.5. Если она разрешима, то в оптимальном решении разумно распределена та часть товара, которая транспортируется по дугам исходной транспортной сети, а по фиктивным дугам «распро-

страняются» неизбежные недопоставки товара.

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

ТСЗП ― это задача минимизации функции (55) при ограничениях (53), (54). Сопоста-

вим ограничениям (53) двойственные переменные pi, i V, а ограничениям xij ≤ rij ― двойст-

венные переменные dij, (i, j) E. Пусть p = (pi | i V), d = (dij | (i, j) E).
Двойственная задача имеет вид
h(p, d) = pibi +	dij rij → max при условиях	(58)
i V	(i, j ) E
pj – pi + dij ≤ cij для всех (i, j) E,		(59)
pi ≥ 0 для всех i V, dij ≤ 0 для всех (i, j) E.		(60)

Технологический способ, соответствующий переменной xij, при единичной интенсив-

ности «перевозит» единицу товара от поставщика i потребителю j с затратами (измеренными в теневых ценах) pj – pi + dij = pj – pi – |dij|, так как dij ≤ 0.

Пусть x* = ( x11* , …, xmn* )T ― решение задачи (35) – (38), (p*, d*) ― решение двойствен-

ной задачи, p* = ( pi* | i V), d* = ( dij* | (i, j) E). Будем интерпретировать pi* как стоимость единицы товара в пункте i, а | dij* | ― как плату за использование ограниченной пропускной способности дуги (i, j). Двойственное ограничение перепишем в виде p*j ≤ pi* + cij + | dij* |.

53

Оно требует, чтобы цена товара в пункте j была не больше, чем сумма цены товара в пункте i, стоимости перевозки и платы за использование дуги (i, j).

Если xij* > 0 (эффективная перевозка), то p*j = pi* + cij + | dij* | по второй теореме двойст-

венности: разница между ценами товара в пунктах j и i равна сумме транспортных затрат и платы за использование дуги (i, j). По первой теореме двойственности

					m	n
h(p*, d*) = p*i bi +	d ij*rij	= p*i bi	– p*i	| bi | – | d ij* | rij	= сij x*ij = f(x*).
i V	(i, j ) E	i I	i I	(i, j ) E	i 1	j 1

Это значит, что при оптимальном плане перевозок суммарная стоимость удовлетворения по-

требностей складывается из стоимости запасов в источниках, минимальных транспортных затрат и платежей за использование пропускных способностей (если все денежные величи-

ны, кроме транспортных затрат, рассчитаны в теневых ценах).

Уменьшение потребности стока i, то есть bi для i I+, снижает минимальные транспорт-

ные затраты на ε pi* . Уменьшение bi для i I– эквивалентно увеличению |bi|, запаса товара в источнике i, и тоже снижает транспортные затраты на ε pi* . Увеличение на ε пропускной спо-

собности дуги (i, j) уменьшает минимальные транспортные затраты на ε| dij* |. Во всех случаях мы, конечно, предполагаем, что при изменении параметра задачи на ε двойственные оценки сохраняются.

3.5. Модель производства с запасами

Цель этого раздела ― продемонстрировать различия между матричной и сетевой по-

становками транспортной задачи на примере ситуации, которая не связана с реальными пе-

ревозками.

Представим себе фирму, которая производит однородную продукцию и имеет контрак-

ты с потребителями на T единичных периодов. В соответствии с этими контрактами фирма должна поставить Dt единиц продукции в течение периода t 1,T , а при задержке поставки единицы продукции на единичный период фирма платит штраф p. Продукцию, произведен-

ную в периоде t, но не поставленную потребителям в том же периоде, можно хранить на складе фирмы с затратами s (на хранение единицы продукции в течение единичного перио-

да). Все поставки должны быть выполнены к моменту T. По плану развития фирмы ее мощ-

ность к началу периода t будет равна Vt. Удельная себестоимость производства в период t

прогнозируется в размере at. Нужно определить план производства, обеспечивающий выпол-

нение всех поставок к моменту T с минимальными суммарными затратами.

Пусть xij ― объем продукции, произведенной в периоде i в счет поставок периода j. За-

траты cij, связанные с производством единицы продукции в периоде i и поставкой этой еди-

54

ницы продукции потребителю в периоде j, включают: себестоимость производства; затраты на хранение, если i < j; штраф за несвоевременную поставку, если i > j. Следовательно,

ai s( j i), если i j,

cij = ai , если i j,

ai p(i j), если i j.

Математическая модель:

T	T
cij xij → min при условиях
i 1	j 1

T

xij ≤ Vi, i 1,T j 1

(выпуск продукции в периоде i не превосходит мощность предприятия),

T

xij ≥ Dj, j 1,T i 1

(к моменту T все поставки выполняются),

xij ≥ 0 для всех i, j.

Это транспортная задача в матричной постановке. Каждый единичный период является и «поставщиком», и «потребителем» продукции, возможны «поставки» между любыми дву-

мя периодами.

Потоки продукции, фигурирующие в постановке задачи, можно представить графом

G = (V, E), см. рисунок.

Блок производства

Блок хранения

Блок потребления

1

1

1

s

zi–1

p

ui

yi

–Vi

xi

0

i

i

i

Di

ai

0

s zi

p

ui+1

i + 1

i + 1

i + 1

T

T

T

55

Множество V состоит из трех подмножеств, в каждом из которых вершинам присвоены номера от 1 до T. Назовем эти подмножества блоками: производства, хранения и потребле-

ния.

Продукция, выпущенная в периоде i, «перемещается» из вершины i блока производства

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

ввершине i < T блока хранения может «перейти» либо в вершину i + 1 этого же блока с удельными затратами s, либо в вершину i блока потребления с нулевыми затратами. Из вер-

шины i блока потребления продукция может «вернуться во времени» в вершину того же бло-

ка с номером i – 1 (если i > 1) с удельными затратами p.

Вершина с номером i имеет интенсивность – Vi в блоке производства (источник), ин-

тенсивность 0 в блоке хранения (нейтральная вершина) и Di ― в блоке потребления (сток).

На рисунке интенсивности указаны возле вершин. Возле дуг, инцидентных вершинам с но-

мером i, указаны стоимости перемещения единицы потока (под дугой или слева от нее) и пе-

ременные потока (над дугой или справа от нее).

Смысл переменных: xi ― объем производства в периоде i; yi ― количество продукции,

передаваемой потребителям в периоде i в счет поставок этого и предшествующих единичных периодов; zi ― запас на складе в конце периода i; ui ― количество продукции, произведен-

ной не ранее периода i и передаваемой потребителям в счет поставок единичных периодов,

предшествующих периоду i.

Построенному взвешенному графу соответствует следующая транспортная задача в се-

тевой постановке:

T	T	T
ai xi	+ s zi	+ p ui → min при условиях:
i 1	i 1	i 1

–Vi ≥ –xi для всех i

(условие (53) для вершин блока производства, эквивалентное условию xi ≤ Vi, выпуск про-

дукции не больше мощности);

xi + zi–1 – yi – zi ≥ 0 для всех i

(условие (53) для вершин блока хранения, баланс запасов, производства и потребления про-

дукции в конце периода i, z0 ― запас продукции в начале планового периода); yi + ui+1 – ui ≥ Di для всех i

(условие (53) для вершин блока потребления, все поставки должны быть выполнены за пла-

новый период);

xi ≥ 0, yi ≥ 0, ui ≥ 0 для всех i.

56

Понятно, что построенные выше ТЗМП и ТЗСП эквивалентны. ТЗМП проще в записи и в решении, но требует некоторых размышлений при формализации и дополнительных расче-

тов при подготовке информации. ТЗСП подробней описывает материальные потоки и удобна для формализации.

Литература

Ашманов А.С. Линейное программирование. М.: Наука, 1982 (§§ 1 – 4 главы 7).

Волков И.К., Загоруйко Е.А. Исследование операций. М.: Изд-во МГТУ им. Н.Э. Бау-

мана, 2000 (глава 5 и приложение 1).

Гимади Э.Х., Глебов Н.И. Математические модели и методы принятия решений. Ново-

сибирск: НГУ, 2008 (раздел 4.2).

Горшков А.Ф., Евтеев Б.В., Коршунов В.А. и др. Компьютерное моделирование ме-

неджмента. М.: Экзамен, 2004 (разделы 2.4.2, 2.4.3).

Конюховский П. Математические методы исследования операций в экономике. Спб.:

Питер, 2000 (глава 3).

Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984 (разделы 2.10 – 2.12,

2.14).

Хуторецкий А.Б. Модели исследования операций. Новосибирск: Издательство СО РАН, 2006 (стр. 124 – 125, 190 – 192).

4. Элементы теории игр

4.1. Основные понятия

Теория игр анализирует принятие решений в ситуациях субъективной (игровой) неоп-

ределенности, когда на результат решения, принятого ЛПР, влияют решения других ЛПР,

преследующих собственные цели. Теоретико-игровой подход широко применяется в эконо-

мической теории, например, для анализа рынков с несовершенной конкуренцией и взаимо-

действий экономических агентов при неполной информации.

В условиях игровой неопределенности ЛПР, выбирая целесообразное решение, вынуж-

ден использовать какие-то предположения о решениях других ЛПР ― ожидания. Поэтому принятое в неоклассической экономической теории предположение рациональности эконо-

мических субъектов дополняют предположением рациональности ожиданий: каждый участ-

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

57

Определения и обозначения.

Взаимодействие ЛПР является игрой, если результат каждого ЛПР зависит не только от его решения, но и от решений других ЛПР.

Участников игры называют игроками.

Решение, которое игрок может принять (и реализовать) называется его стратегией.

Статическая игра ― это игра, в которой каждый игрок выбирает стратегию, не имея информации о стратегиях, выбранных другими игроками.

Предположение 13. Число игроков конечно.

Определения и обозначения.

I ― множество всех игроков.

Множество всех стратегий игрока i I обозначим Xi.

Положим X = X1 X2 … Xm, где m ― число игроков.

Элемент x X является набором стратегий, по одной для каждого игрока, и называется

исходом игры.

Предположение 14. Предпочтения игрока i на множестве исходов игры описаны функ-

цией выигрыша (функцией полезности) ui: X → R.

Определения.

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

Статическая игра с полной информацией в нормальной форме ― это набор

G = (I, (Xi | i I), (ui | i I)).

Игра называется конечной, если все множества Xi конечны.

В дальнейшем мы будем рассматривать только статические игры с полной информаци-

ей в нормальной форме.

Подходы и результаты теории игр позволяют по описанию игры выделить из множест-

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

4.2. Равновесие в доминирующих стратегиях

Определения и обозначения. Пусть m ― число игроков, тогда I = 1, m .

Для i I положим X–i = X1 … Xi–1 Xi+1 … Xm.

58

x–i = (x1, …, xi–1, xi+1, …, xm) X–i для исхода x = (x1, …, xm) X и игрока i I ― набор стратегий всех игроков, кроме игрока i.

Вектор x = (x1, …, xm) X будем, если удобно, записывать в виде x = (xi, x–i).

Стратегия xi игрока i сильно (слабо) доминирует его стратегию yi, если для всех x–i X–i

справедливо неравенство ui(xi, x–i) > (≥) ui(yi, x–i).

Стратегия xi игрока i называется сильно (слабо) доминирующей, если она сильно (слабо) доминирует любую другую его стратегию: ui(xi, x–i) > (≥) ui(yi, x–i) для всех yi Xi \ {xi} и x–i X–i.

Слабо доминирующую стратегию будем также называть просто доминирующей.

Следствие 4.1.(1)

(а) Если стратегия xi Xi сильно доминирует стратегию yi Xi, то xi слабо доминирует yi.

(б) Сильно доминирующая стратегия является и слабо доминирующей.

(в) Если у игрока i есть сильно доминирующая стратегия xi, то у него нет доминирующих стратегий, отличных от xi.

Для игрока i при произвольном наборе стратегий других игроков сильно доминирую-

щая стратегия полезней, чем любая другая стратегия. Естественно предположить, что рацио-

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

Доминирующие стратегии игрока i при произвольных стратегиях других игроков оди-

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

но сужает множество исходов, подлежащих анализу.

Определение. Исход игры является равновесием в доминирующих стратегиях, если стратегия каждого игрока в этом исходе является его доминирующей стратегией.

Следствие 4.2.(2) Пусть I = 1, m , X i* ― множество всех доминирующих стратегий иг-

рока i, X * ― множество всех равновесий в доминирующих стратегиях. Тогда

X * = X1* … X m* .

(1)Доказательство оставляем читателю.

(2)Эквивалентно определению равновесия в доминирующих стратегиях.

59

Таким образом, если все игроки имеют доминирующие стратегии и, действуя рацио-

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

Следствие 4.3.(1) Равновесие в доминирующих стратегиях определено однозначно то-

гда и только тогда, когда каждый игрок имеет сильно доминирующую стратегию.

Определения и обозначения.

Точечно-множественное отображение f : A → B сопоставляет каждому элементу a

множества A некоторое (возможно, пустое) подмножество f(a) множества B.

Функция f, определенная на множестве A и принимающая значения из B, ― это точеч-

но-множественное отображение f : A → B такое, что f(b) содержит ровно один элемент для любого b B.

Argmax{f(x) | x X} ― множество всех точек максимума функции f(x) на множестве X.

Точечно-множественное отображение отклика Ri(x–i) игрока i сопоставляет каждому набору x–i X–i стратегий других игроков множество стратегий игрока i, каждая из которых является его наилучшим ответом на выбор x–i других игроков:

Ri(x–i) = Argmax{ui(xi, x–i) | xi Xi} для x–i X–i.

Если отображение отклика игрока i является функцией, то стратегия игрока i однознач-

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

Следствие 4.4.(2)

(а) Стратегия xi является сильно доминирующей стратегией игрока i, если и только если

Ri(x–i) = {xi} для всех x–i X–i.

(б) Стратегия xi является слабо доминирующей стратегией игрока i, если и только если xi Ri(x–i) для всех x–i X–i.

Следствие 4.4 показывает, что отображение отклика можно использовать для выявле-

ния доминирующих и сильно доминирующих стратегий. В частности, игрок имеет сильно доминирующую стратегию тогда и только тогда, когда его функция отклика является кон-

стантой.

(1)Для доказательства нужно объединить утверждение (в) следствия 4.1 и следствие 4.2.

(2)Доказательство оставляем читателю.

60