Решение транспортной задачи с промежуточными пунктами

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

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

Пример 5. Задача об оптовых складах.

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

На рисунке, расположенном ниже, представлена схема размещения складов, на ко­торой указаны:

- номера складов (цифры 1-8 в кружках);

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

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

- возможность перевозки товара со склада i на склад j (направленная дуга от кружка с номером i к кружку с номером j);

- затраты, связанные с перевозкой единицы товара со склада i на склад j (величина над соответствующей направленной дугой, выраженная в условных денежных единицах).

 

На данном рисунке видно, что суммарный избыток товара, имеющийся на складах системы с номерами 1 и 4, равен суммарному недостатку товара, имеющемуся на складах с номерами 3, 6 и 8 этой же системы. Перераспределение товара может проис­ходить через склады с номерами 2, 4, 5, 6 и 7, которые в рассматри­ваемой задаче и являются промежуточными пунктами.

Источ­ником является лишь склад с номером 1, на котором имеется избыток товара и с которого товар можно только вывозить. Стоками же являются склады с номерами 3 и 8, на которых есть недостаток товара. На эти склады товары можно только за­возить.

Заметим также, что между складами с номерами 4 и 5 возможны перевозки в обоих направлениях, но в общем слу­чае .

Таким образом, на рисунке фактически представлена сеть рассматриваемой транспортной задачи с промежуточными пунктами. Формаль­ное описание этой сети удобно представить в виде следующей таблицы:

 

											+10
	-1
		-1		-1							-3
							-1
			-1		-1
								-1			-1
						-1			-1
										-1	-8

 

 

Номер склада

Объемы перевозок

Избыток / недостаток

 

В приведенной таблице каждому узлу сети (складу) соответствует одна строка и каждой направленной дуге сети соответствует одна переменная модели , представляющая собой количество товара (в единицах его измерения), которое должно быть отправлено с i-го склада на j-ый склад. Каждой переменной модели соответствует один столбец, в котором стоит 1 в i-ой строке, -1 в j-jой строке и в последней строке. Обратите внимание на то, что в приведенной таблице на пересечении i-ой строки и последнего столбца находится число, равное избытку (если оно неотрицательное) или недостатку (если оно отрицательное) товара на i-ом складе (в единицах измерения товара).

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

 

Ст. Ист.

Запасы:

Заявки:

 

На первом этапе в исходной таблице нужно выделить строку для каждого источника и указать его «мощность» (избыток то­вара на складе). В данном примере источником является только склад с номером 1, мощность которого = 10. В транспортной таблице этому складу будет соответствовать первый пункт производства с объ­емом поставок, равным 10.

На втором этапе в исходной таблице нужно выделить столбец для каждого стока и указать его мощность (недостаток това­ра на складе). В данном примере стоками являются третий и восьмой склады. Поэтому и , что в транспортной таблице соответствует значениям спроса для пунктов потребления 3 и 8.

На третьем этапе нужно сделать следующее.

1. В транспортной таблице выделить строку и столбец для каждого промежуточного пункта. В данном случае промежуточными пунктами являются склады с номерами 2, 4, 5, 6 и 7, которые в транспортной таблице фигурируют как пункты производства и пункты потребления.

2. Для каждого k-го промежуточного пункта определить величину чистого запаса товара , равного объему из­бытка со знаком плюс либо объему недостатка со знаком ми­нус. В данном случае:

.

3. Определить суммарный объем избытка на всех складах системы, используя последний столбец исходной таблицы. Суммарный объем избытка представляет собой общий объем перевозок (в единицах измерения товара). В данном случае:

4. Считать, что маршрут транспортировки всего суммар­ного объема избытка товара может проходить через любой промежуточный пункт. Это означает, что любой склад с но­мером k, рассматриваемый как промежуточный пункт, может принять весь суммарный объем избытка товара. Таким образом, в данном случае

В транспортной таблице эти значения фигурируют как спрос.

5. Для каждого k-того промежуточного пункта определить мощность его источника , то есть объем товара, который может быть вывезен со склада с номером k. Так как на складе с номером k величина чистого запаса товара равна , а максимально возможный объем поставок определяется величиной , то:

В данном примере:

В транспортной таблице эти значения фигурируют как поставки.

На четвертом этапе необходимо для каждого k-го промежуточного пункта ввести переменную при . В данном случае k Î {2, 4, 5, 6, 7}. Интерпретировать переменную можно как объем товара, который оседает на складе с номером k.

При построении транспортной таблицы ранее нами была введе­на величина , имеющ ая смысл динамического запаса или буфера в каждом промежуточном пункте. Для каждого k-го промежуточного пункта величина входит как в , так и в . Поэто­му сумма заявок равна сумме запасов.

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

В этом случае значение разности ( - ) представляет собой объем товара (в единицах его из­мерения), перевезенного через k-ый промежуточный пункт, так как - максимально возможный объем поставок товара на склад с номером k, a — объем товара, осевшего на этом складе. В нашей транспортной таблице заполнены лишь те клетки, которые содер­жат переменные , соответствующие направленным дугам сети, а также переменные , соответствующие промежуточ­ным пунктам. Именно в этом и заключается отличие нашей транспортной таблицы от классических транспортных таблиц, которые мы рассматривали ранее.

Следует отметить, что в исходной таблице заданы восемь ограни­чений и десять переменных, а в транспортной таблице заданы уже тринадцать ограничений (по строкам и столбцам) и пятнадцать переменных. Увеличение размерно­сти на пять единиц объясняется наличием пяти промежуточных пунктов.

Осталось доказать эквивалентность (в смысле отыскания оптимальных решений) исходной транспортной задачи с промежуточными пунктами, представленной в исходной таблице, и соответству­ющей ей классической транспортной задаче.

Нетрудно убедиться в том, что в транспортной таблице строка, соот­ветствующая первому складу (исток), и столбцы, соответ­ствующие третьему и восьмому складам (стоки), задают те же ограничения, что и соответствующие строки в исходной таблице. Обратимся теперь к k-му складу, являющемуся промежуточ­ным пунктом, т.е. k Î {2, 4, 5, б, 7}. Пусть K - множество номеров складов, на которые товар может быть доставлен с k-го склада, а N - множество номеров складов, с которых товар может быть доставлен на k-ый склад. Тогда ограничение для k-го склада, заданное в исходной таблице, имеет следующий вид:

,

где - величина, чистого запаса товара, введенная на третьем этапе построения рассматриваемой транспортной таблицы.

Так как соответ­ствующие ограничения, задаваемые в транспортной таблице (по строке и по столбцу), могут быть представлены следующим образом:

то, вычитая последние равенства друг из друга, получаем искомое ограничение:

На этом дока­зательство того, что рассматриваемая транспортная задача с промежуточными пунктами эквивалентна классической транспортной задаче, можно считать завершенным.

 

Теория игр

Эта относительно молодая ветвь математики была создана в 1930е годы Джоном фон Нейманом и Оскаром Моргеншетрном. Фон Нейман был замечательным математиком, и практически в одиночку создал теорию информации и теорию игр. Его исследования во многом поспособствовали развитию вычислительной техники и появлению компьютера. Позже, в 1950-е годы большую роль в развитие теории игр внес американский математик, лауреат Нобелевской премии по экономике, Джон Нэш. История жизни Джона Нэша настолько необычна, что легла в основу фильма «Игры разума» 2001 года. В школе Нэш не любил математику, поскольку ее преподавали посредственно. Но в 14 лет к нему в руки попала книга «Творцы математики» Эрика Белла, после прочтения которой он смог доказать малую теорему Ферма. Чуть позже Нэш наткнулся на труды фон Неймана и Моргенштерна, и в 21 год он написал диссертацию по теории игр. Именно за эту работу он получил в 1994 году Нобелевскую премию по экономике.

Теория игр (game theory) изучает, каким образом выстраивают свое поведение агенты в так называемых «играх» - ситуациях, когда результат принятия решений зависит не только от поведения данного агента, но и от поведения других участников игры.
Индивид, принимая решения, может догадываться о том, как будут вести себя другие участники игры. Индивид будет принимать решение исходя из рациональной догадки о поведении других. Говорят, что в этом случае индивид следует определённой игровой стратегии.

Игровая стратегия – это линия поведения участника в зависимости от предположений об ответных действиях других участников. Доминирующая игровая стратегия – это стратегия, при которой участник получает максимальный выигрыш при любых действиях других сторон.
Что такое игровая стратегия и доминирующая игровая стратегия лучше всего показать на конкретном примере – простейшей игре под названием «дилемма заключенного», анализ которой и положил начало теории игр.

Дилемма заключенного - это игра между двумя участниками с двумя возможными исходами и одновременными ходами.

Суть игры заключается в следующем. Представьте, что вы с напарником совершили преступление, например, ограбили банк. Полиция поймала вас обоих и теперь проводит допрос каждого из них в разных камерах. Полиция предлагает вам сделку: вы даете показания на своего напарника, и тогда выходите на свободу. Такую же сделку предлагают вашему напарнику.
Каждый из преступников имеет выбор: давать показания на напарника или молчать. Если вы оба даете показания друг на друга, то каждый получает по 2 года тюрьмы. Если вы оба молчите, то в полной мере вашу вину будет трудно доказать, и каждый получит только по 1 году. Но если вы даете показания на вашего подельника, а он нет, то вы выходите на свободу, а ваш подельник получает 5 лет тюрьмы.
Таким образом, приговор, который получит каждый преступник, зависит не только от его показаний, но и от показаний другого преступника.

То есть у Вас есть 4 варианта действий:

1. Вы даете показания, а напарник молчит. Тогда вы выходите на свободу, а напарник садится на 5 лет.

2. Вы даете показания, и ваш напарник дает показания. Вы оба получаете по 2 года.

3. Вы молчите, и напарник молчит. Вы выходите на свободу через 1 год в виду недостаточности улик для более серьезного обвинения.

4. Вы молчите, а напарник дает показания. В этом случае вы садитесь на 5 лет, а напарник выходит на свободу.

Какой вариант выберете Вы в данной ситуации?

Джон Нэш задал этот простой вопрос, и, проанализировав такую игру, пришел к выводам, которые совершили переворот во взглядах экономистов на то, как принимают решения люди при взаимодействиях друг с другом.

Ниже приведена матрица результатов для преступников в зависимости от их действий:

	заключенный А
признаться	не признаться
Заключенный В	признаться	(2; 2)	(5; 0)
не признаться	(0; 5)	(1; 1)

В каждой клеточке сначала идет срок наказания для преступника А, потом срок наказания для преступника В.
Рассмотрим ход рассуждений каждого преступника:

Преступник А: я не знаю, как поведет себя преступник В. Если он не даст показания, то мне лучше их дать, потому что тогда я выйду на свободу. Если он будет молчать, то мне опять же лучше дать показания, потому что тогда я получу 2 года наказания, а не 5. Поэтому мне лучше дать показания вне зависимости от того, как поведет себя мой подельник.
Аналогичным образом рассуждает преступник В.
Таким образом, доминирующей игровой стратегией для каждого из них становится дача показаний. В этом случае игровое равновесие устанавливается, когда они оба признаются и получат по 2 года наказания. Данное равновесие достигается потому, что стратегия «дать показания» каждого участника является оптимальной при заданной стратегии другого участника. Достигнутое равновесие является равновесием по Нэшу.
Равновесие Нэша – равновесие, когда каждый участник игры выбирает стратегию, которая является для него оптимальной при условии, что остальные участники игры придерживаются определенной стратегии.

Нетрудно увидеть, что Нэш-равновесие не является наиболее оптимальным для участников. Если бы они оба выбрали стратегию «не признаться», то получили бы только по 1 году. В этом случае говорят, что равновесие не является Парето-оптимальным¹. Если бы преступники смогли договориться заранее, то, возможно, они смогли бы достичь Парето-оптимального равновесия. Но даже в случае договоренности каждый из них имеет стимулы отступить от договоренностей и признаться, чтобы избежать наказания полностью. В этом случае эгоистические интересы каждого из участников и недоверие к напарнику заставляют преступников выбрать вариант «признаться». Согласованное поведение участников будет нерациональным с индивидуальной точки зрения каждого из участников.

Выводы Джона Нэша стали революционными. Адам Смит считал, что когда каждый член группы действует эгоистично, преследуя свои собственные интересы, это ведет к эффективному равновесному состоянию этой группы. Этот принцип был назван «невидимая рука рынка». Джон Нэш показал, что когда каждый член группы действует только в своих интересах, это не приводит к достижению максимальных интересов всей группы.
Эта идея часто иллюстрируется с помощью так называемого «парадокса блондинки». Допустим, компания холостяков отправляются вечером в бар, где за соседним столиком сидит компания молодых девушек, из которых одна является блондинкой. Каким образом компании молодых людей стоит начать знакомиться с девушками?
Если каждый из них попытается познакомиться сначала с блондинкой, то она не достанется никому. В этом случае остальные девушки (брюнетки) оттолкнут молодых людей, поскольку никто не хочет быть девушкой второго сорта. Компания молодых людей останется без девушек. Но вот если блондинку никто не заметит, то каждый из молодых людей найдет себе не менее достойную девушку.
На этом простом примере показывается, что преследование эгоистичных интересов может не всегда отвечать интересам группы. Если Адам Смит считал, что каждый индивид должен преследовать только свои личные интересы, то Джон Нэш ответил, что не только свои, но и интересы группы.

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

На рынках многих благ существует так называемая дуополия – ситуация, когда рынок контролируется двумя крупными игроками. Например, на рынке прохладительных напитков можно обнаружить два гиганта: Coca-Cola company и Pepsi-Cola, на рынке самолетостроения есть два гиганта - Airbus и Boeing. Решение одного их игроков, например, о проведении рекламной кампании, отражается не только на его положении, но и на положении другого участника. В этой ситуации конкурирующие стороны начинают соперничать, неимоверно раздувая собственные рекламные бюджеты. Им можно было бы снизить объемы рекламы и увеличить получаемую прибыль, но для этого им нужно сначала договориться.

На простейшем примере игры «дилемма заключенного» показывается, что устойчивое равновесие в игре (так называемое равновесие по Нэшу) не обязательно обеспечивает наилучший для участников результат (так называемый Парето-оптимум). Дилемма заключенного является примером одномоментной игры, в которой участники принимают решения одновременно. Также существуют последовательные игры, в которых участники принимают решения один после другого. Примеры с обоими видами игр рассматриваются нами в главе «Олигополия».

⇐ Предыдущая12345678910Следующая ⇒

Поделиться: