М. И. Рейтман
Транспортная задача



Джо принимает план Бэйта

– Всё хорошо, план операции мне нравится, Бэйт, – говорил Джо, расхаживая по номеру дешёвой гостиницы и запивая каждую затяжку сигарой добрым глотком виски. Старина Бэйт сидел в кресле у жалкого камина, привычно ощущая подмышкой рукоятку пистолета.

– Ещё бы! – процедил Бэйт сквозь искусственные зубы. – Недаром за мной уже пятнадцать лет гоняется полиция всех штатов. Вряд ли я вошёл бы в такую цену, если бы только и мог орудовать кастетом. Новинки науки – вот мой конёк. Вспомни, Джо, это я впервые ввёл вертолёты при ограблении банков. А как я...

– Постой! – прервал Джо расхваставшегося коллегу. – Я ценю тебя, потому и работаю с тобой. И эта твоя новая идея – обчистить за одну ночь три склада с мануфактурой – тоже великолепна. Но шофёры...

– Это железные парни! – воскликнул Бэйт. – Можешь на них положиться! Таких не сцапает ни один фараон!

– Я доверяю этим парням, Бэйт. Но цена! 10 долларов за тонно-милю на грузовиках – да за такую цену я готов таскать вручную! Мы разоримся, даже если всё выгорит.

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

– Но не забывай, Джо, чем парни рискуют... И кроме того, кроме того... я позаботился о том, чтобы заплатить им поменьше. Нет, нет, не надуть – с такими не выйдет. Дело совсем в другом: я применю научный метод.

Джо посмотрел на Бэйта с уважением (как-никак тот когда-то кончил колледж), но всё-таки возразил:

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

– Хорошо, Джо, – серьезно кивнул Бэйт, понимая, что должен напрячь все свои педагогические способности, иначе дело не пойдёт, и он сядет на мель.

– Сколько скупщиков краденого берут мануфактуру?

– Четыре. Первые два по шестьдесят тонн, а два других – по сорок.

– А сколько на складах, помнишь?

– Ты что, смеёшься, Бэйт? Я помню эти числа даже во сне: 75, 75 и 50.

– Правильно, Джо! Давай я запишу всё это в таблице.

Бэйт сорвал висевший на стене календарь и на обороте изобразил таблицу 1.

Склады Скупщики Ёмкости
складов
1 2 3 4
1
      80
 
      120
 
      150
 
      50
 
75
2
60
 
70
 
90
 
120
 
75
3
120
 
50
 
110
 
100
 
50
Потребности
скупщиков
60 60 40 40  
 Табл. 1 

– А в правом верхнем углу каждой клетки здесь... – начал Бэйт, но Джо перебил его.

– Ох! Лучше б я не знал этих чисел! Конечно, я узнаю их! Столько эти внуки дьявола просят за перевозку одной тонны груза по каждому маршруту. Например, 100 долларов за тонну с третьего склада к четвёртому скупщику, там 10 миль. Нет, лучше я потащу сам!

– Парни рискуют, Джо, – возразил Бэйт. – Давай будем называть эти стоимости тарифами. Итак, как же мы будем возить? По каким маршрутам?

– Ясное дело, где подешевле, – пробормотал Джо, чуя подвох.

– Правильно! Давай занимать перевозками те маршруты, где тарифы поменьше. Здесь дешевле всего везти товар от первого склада к четвёртому скупщику – всего пятьдесят долларов. Назовём этот путь маршрутом (1,4). Его мы наверняка будем использовать!

– Ещё бы! И провезти по нему надо как можно больше!

– Правильно! Но больше 40 тонн не провезёшь – четвёртый скупщик не примет, он тоже рискует. Поставим на этот маршрут 40 тонн, а на маршрут (3,2) – там тоже 50 долларов – 50 тонн: больше на третьем складе не нашаришь! Получится таблица 2. Я тут заодно подправил ёмкости и потребности. И в дальнейшем будем ставить перевозки на те маршруты, где поменьше тариф.

Склады Скупщики Ёмкости
складов
1 2 3 4
1
      80
 
      120
 
      150
 
      50
40
75 35
2
60
 
70
 
90
 
120
 
75
3
120
 
50
50
110
 
100
 
50
Потребности
скупщиков
60 60 10 40 40  
 Табл. 2 

– Ты хочешь сказать, что дальше нужно поставить 60 на маршрут (2,1) – там 60 долларов, 10 на (2,2), в общем... – и Джо нарисовал таблицу 3.

Склады Скупщики Ёмкости
складов
1 2 3 4
1
      80
 
      120
 
      150
 
      50
40
75 35
2
60
60
70
10
90
 
120
 
75 15 5
3
120
 
50
50
110
 
100
 
50
Потребности
скупщиков
60 60 10 40 40  
 Табл. 3 

– Именно так!

– Ха-ха-ха! Значит, и мы что-то смыслим! Ну а теперь осталось только завезти третьему скупщику – Скряге Тому, кстати мы его ещё и надуем при расчёте. Вот так, как я изобразил в таблице 4.

Склады Скупщики Ёмкости
складов
1 2 3 4
1
      80
 
      120
 
      150
35
      50
40
75 35
2
60
60
70
10
90
 5
120
 
75 15 5
3
120
 
50
50
110
 
100
 
50
Потребности
скупщиков
60 60 10 40 40  
 Табл. 4 

– Ну и всё в порядке! – довольно потёр Джо жирные руки. – Нам это обойдётся в 35×150 + 40×50 + 60×60 + 10×70 + 5×90 + 50×50 = 14500 долларов. Не так ли, старина Бэйт? И это называется научный метод? Ставлю доллар против пяти центов, что любой полицейский сообразит, как найти этот план перевозок за 14 500 – ох-ох – 14 500 долларов. Правда, нам приходится здесь использовать маршрут (1,3) – 150 долларов за тонну, – вдруг помрачнел Джо, вглядевшись в таблицу.

– Ага, Джо, – настал черед торжествовать Бэйту. – Выходит наука всё-таки нужна? Мы рассуждали вполне здраво, а всё-таки нарвались на использование самого дорогого маршрута. Давай теперь пытаться улучшить план перевозок. Поставим тонну груза на маршрут (1,1).

– Не выйдет, – возразил Джо. – Нарушится баланс в первом столбце, если я что-то смыслю в этом деле.

– Смыслишь, смыслишь, – успокоил Бэйт. – Но баланс можно восстановить, сняв одну тонну с маршрута (2,1), не так ли?

– Постой, тогда и во второй троке не будет баланса – на тонну меньше. Хотя, хотя... если добавить ещё тонну на (2,3) и снять с (1,3), кажется, всё будет о'кэй.

– Давай представим это в новой таблице 5 (ёмкости и потребности нам уже не нужны).

 Склады  Скупщики
1 2 3 4
1
+80
 
120
 
150
35
50
40
2
60
60
70
10
+90
 5
120
 
3
120
 
50
50
110
 
100
 
 Табл. 5 

– Там, где я добавлял тонну, стоит знак плюс, а где убирал – минус. А набор клеток, в которых мы произвели изменения, давай назовём циклом *. Итак, что же это нам даст? Провоз одной тонны по маршруту (1,1) – 80 долларов. Их надо добавить. А 150 долларов – провоз тонны на маршруте (1,3) – наоборот, долой, как и 60 с маршрута (2,1). Ну и 90 придётся прибавить за лишнюю тонну на маршруте (2,3). Итого, транспортные расходы изменятся на

80 + 90 – 150 – 60 = –40

долларов.

– Здорово! 40 долларов можно сберечь! – восхитился Джо. – Но это мы поставили на маршрут (1,4) только тонну. Давай поставим 100 тонн и сбережём 4000, или нет, поставим 400 тонн и тогда ещё нам будут доплачивать!

В глазах Джо загорелся огонек алчности, но тут же потух:

– Нет, здесь что-то не так.

– Ясное дело, не так, – согласился Бэйт. – Ведь сколько мы добавим на маршрут (1,1), столько же придётся снять с (1,3) и (2,1). А оттуда самое большее можно снять 35 тонн. Ведь не хочешь же ты везти мануфактуру обратно на склад!

– Ещё бы!

– Значит, самое большее удастся провезти по маршруту (1,1) 35 тонн; это позволит сэкономить 40 × 35 = 1400 долларов, и новый план перевозок будет таким, как в таблице 6. В клетках, которые не вошли в цикл, всё осталось по-старому.

 Склады  Скупщики
1 2 3 4
1
      80
35
      120
 
      150
 
      50
40
2
60
25
70
10
90
40
120
 
3
120
 
50
50
110
 
100
 
 Табл. 6 

– 1400 долларов – кругленькая сумма! Давай проверять другие пустые клетки. Может набредём на маршрут, который тоже стоит использовать. Вот, например, начнём с клетки (1,2). Для неё расходы изменятся на

120 + 60 – 70 – 80 = 30 > 0.

Тысяча чертей! Маршрут (1,2) использовать не стоит. А, может быть, воспользоваться...

– Не трудись, Джо. Я уже проверял: больше из этого плана не выжмет ни доллара сам Данциг.

– Данциг, Данциг... это не тот ли, который обчистил «Бэнк оф...»?

– Нет, Джо, он не из наших. Это тот малый, который придумал этот метод. Правда, ещё до него какие-то красные...

... Инспектор Клифф сидел у себя в кабинете на Авеню-стрит, снова и снова всматриваясь в вещественные улики: три мастерски взломанных замка и пепел от тщательно сожжённого календаря в гостинице, где совещались грабители. И больше ничего. И всё-таки... это напоминает почерк Бэйта, за которым он, Клифф, охотится уже столько лет! К примеру календарь. Зачем он? Может, на нём делались выкладки? Возможно. Но где же искать Бэйта?

– Сержант! Усиленные наряды во все бары города! – крикнул он, осознавая в то же время полную безнадёжность своего приказа: в барах Бэйта не будет. На столе инспектора зазвонил телефон. Клифф снял трубку, послушал и закричал:

– Сержант, отставить! Оцепить научную библиотеку штата! Мне – машину и набор наручников!

Немного теории

Что же позволило сэкономить на транспортных расходах 1400 долларов? Проследим за действиями ловких гангстеров. Сначала Бэйт нашёл допустимый план перевозок. Метод, которым он при этом воспользовался называется методом минимального элемента и понятно почему: в нём перевозки всё время ставятся на маршруты с минимальными тарифами, а если будут два маршрута с одинаковым тарифом, то предпочтение, естественно, нужно отдать тому из них, для которого возможная перевозка больше.

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

Пусть имеется m поставщиков (складов) и n потребителей, ai – емкость i-го склада, а bj – потребность j-го потребителя. Пусть xij – перевозка от i-го поставщика к j-му потребителю. Допустимы только такие планы перевозок, для которых **
 n
 xij = ai     ( i = 1, 2, ..., m),
 j=1
(1)
 m
 xij = bj     ( j = 1, 2, ..., n),
 i=1

то есть из каждого склада вывозится всё, что там есть, и каждому потребителю привозится всё, что ему требуется. Кроме того, заданы тарифы cij , то есть стоимости перевозки единицы груза от i-го поставщика к j-му потребителю. В задаче требуется отыскать такой допустимый план перевозок, для которого сумма стоимостей перевозок
 m n
 z =     cij xij
 i=1 j=1
(2)

минимальна.

Сформулированная задача – это частный случай задачи линейного программирования, так как «целевая функция» (2), выражающая транспортные расходы, и ограничения (1) линейны.

Сущность распределительного метода состоит в том, что для каждой свободной клетки находится цикл, в который входят, кроме неё, только заполненные клетки. С помощью этого цикла определяют, на сколько изменятся транспортные расходы, если ввести в свободную клетку единицу груза. Эта величина kij называется индексом свободной клетки (ij). Если kij < 0, то в клетку вносится максимально возможная перевозка (она равна минимальной перевозке в «отрицательных» клетках цикла), а если kij ≥ 0, то маршрут (ij) использовать не стоит и проверяется следующая клетка. Процесс заканчивается, когда выясняется, что для всех свободных клеток kij ≥ 0.

Оптимальный план следует искать среди планов, в которых заполненные клетки не образуют циклов. Обычно в транспортной задаче число заполненных клеток в точности равно m + n – 1, и цикл можно построить единственным образом (например, в рассмотренной задаче число заполненных клеток равно 3 + 4 – 1 = 6). Если включить в цикл свободные клетки со знаком «+», то после изменения плана в нём может оказаться больше m + n – 1 заполненных клеток и план будет содержать циклы. Убедиться в этом можно, попытавшись в таблице 5 построить цикл (1,1) → (1,4) → (2,4) → (2,1).

Если число заполненных клеток меньше m + n – 1 (такая задача называется вырожденной), то для того, чтобы построить цикл, к заполненным клеткам нужно добавить пустые так, чтобы они с уже заполненными не образовывали циклов. Например, пусть таблицей 7 задан вырожденный план перевозок (в нём не хватает 1 заполненной клетки).

 Поставщики  Потребители
1 2 3
1
      3
20
      2
30
      3
 
2
3
 
3
 0
4
40
3
5
 
6
50
2
 
 Табл. 7 

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

Расходы по первому плану перевозок составят

z1 = 25×3 + 30×2 + 40×4 + 50×6 = 595.

Найдём индексы свободных клеток:
k13 = 3 + 3 – 2 – 4 = 0,
k21 = 3 + 2 – 3 – 3 = –1.

По маршруту (2,1) возить выгодно, но сколько можно по нему провезти? min(25,0) = 0. Стало быть, на маршрут (2,1) можно поставить лишь перевозку 0, получится таблица 8.

 Поставщики  Потребители
1 2 3
1
      3
20
      2
30
      3
 
2
3
 0
3
 
4
40
3
5
 
6
50
2
 
 Табл. 8 

Расходы по этому новому плану останутся прежними: z2 = 595. Но, тем не менее, операция перенесения нуля не бессмысленна: теперь изменятся индексы. Действительно, теперь

k13 = 3 + 3 – 3 – 4 = –1 < 0.

То есть теперь оказывается выгодным маршрут (1,3). Его использование с перевозкой 25 тонн приведёт к транспортным расходам в сумме z3 = 595 – 25 = 570.

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

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

Транспортная задача имеет ряд разновидностей и самые неожиданные приложения. Одно из таких приложений мы сейчас рассмотрим.

Задача о назначениях

Два немолодых джентльмена чинно сидели в научной библиотеке штата.

– ... Уверен, ищейки сюда не сунутся. Итак, в банке 4 входа. Каждый из парней согласен занять любой, но они им кажутся по-разному опасными: у одного входа дежурит полицейская машина, другой выходит на людную улицу, в третьем слишком узкая дверь. Их требования в долларах сведены в таблицу 9.

Парни Входы
1 2 3 4
1. Билл
      125
 
      130
 
      220
 
      90
+
2. Джек
120
+
120
 
230
 
100
 
3. Джим
200
 
80
+
180
 
150
 
4. Боб
160
 
90
 
150
+
120
 
 Табл. 9 

– Да, аппетиты у парней – дай бог! Но, знаешь, Бэйт, всё просто. Ставим Билла на вход № 4, Джека – на № 1, Джима – на № 2, Боба – на № 3, как я пометил крестиками. Кажется лучше не придумаешь.

– Да, здесь-то всё ясно. На каждый вход ставим парня, который за него меньше всего требует. Но, Джо, когда ребята узнали, что нами интересуется инспектор Клифф, они запросили больше! Вот в таблице 10 их новые требования.

Парни Входы
1 2 3 4
1. Билл       250       280       290       320
2. Джек 430 420 420 400
3. Джим 370 370 320 330
4. Боб 280 350 340 200
 Табл. 10 

– Это не честные гангстеры, а вымогатели! – взмолился Джо. – Я уже разорён. И главное, как их теперь распределить? Ну, Боба – на вход № 4, а как остальных?

– Давай применим научный метод, – предложил Бэйт. – Поскольку каждый вход и каждый парень в одном экземпляре, то назначить их – это то же самое, что решить транспортную задачу с исходными данными, как в таблице 11. Здесь парни – это поставщики, а входы – потребители. Давай теперь её решать, как обычную транспортную задачу, то есть сначала найдем допустимый план перевозок и добавим три нуля, чтобы ликвидировать вырожденность (см. табл. 12).

Парни Входы Ёмкости
1 2 3 4
1. Билл       250       280       290       320 1
2. Джек 430 420 420 400 1
3. Джим 370 370 320 330 1
4. Боб 280 350 340 200 1
Потребности 1 1 1 1  
 Табл. 11 

Парни Входы
1 2 3 4
1. Билл
250
1
280
 
290
 
320
 
2. Джек
430
0
420
1
420
0
400
0
3. Джим
370
 
370
 
320
1
330
 
4. Боб
280
 
350
 
340
 
200
1
 Табл. 12 

– А не придётся ли нам дробить парней? Уж лучше предоставить это полицейским пулям.

– Нет, результаты всегда будут целыми. Теперь давай подсчитаем индексы:

k12 = 280 + 430 – 420 – 250 =40 > 0; 
k13 = 290 + 430 – 250 – 420 =50 > 0; 
k14 = 320 + 430 – 250 – 400 =100 > 0; 
k31 = 370 + 420 – 420 – 320 =40 > 0; 
k32 = 370 + 420 – 420 – 320 =50 > 0; 
k34 = 330 + 420 – 320 – 400 =30 > 0; 
k41 = 280 + 400 – 430 – 200 =50 > 0; 
k42 = 350 + 400 – 420 – 200 =130 > 0; 
k43 = 340 + 400 – 420 – 200 =120 > 0. 

– Нам повезло, Джо, план оптимален! Ты видишь, все индексы больше нуля, улучшить план невозможно. Кажется, мы предусмотрели всё.

– Нет, не всё, – раздался негромкий голос.

Рядом стояли инспектор Клифф и трое полицейских, из-за их спин выглядывал Скряга Том.



ПРИМЕЧАНИЯ
*

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

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

**

Мы рассматриваем так называемую «закрытую» модель транспортной задачи, для которой ai = ∑bj , то есть сумма ёмкостей (складов) равна сумме потребностей. назад к тексту



Hosted by uCoz