Транспортная задача

13

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

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

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

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

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

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

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

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

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

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

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

— Сколько скупшков крадено берут мануфактуру?

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

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

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

14

Табл. 1.

— Правильно, Джо! Давай я зашишу все это в таблице.
Бейт сорвал внесший на стене календарь и на обороте изобразил таблицу 1.
— А в правом верхнем углу каждой клетки здесь… — начал Бейт, но Джо перебил его.
— Ох! Лучше б я не знал этих чисел! Конечно, я узнал их! Столько эти внутри дьявола просят за перевозку одной тонны груза по каждой маршруту. Например, 100 доларов за тонну с третьero склада к четвертом скупшнику, там 10 млль. Нет, лучше я поташу сам!
— Парни рискуют, Джо, — возразил Бейт. — Давай будем называть эти стоимость тарифами. Итак, как же мы будем возить? По каким маршрутам?
— Ясно дело, где подешевле, — пробормотал Джо, чуя подох.
— Правильно! Давай занимать перевозками те маршруты, где тарифы поменше. Здесь делевле все

Табл. 2.

— Во взти товар от первого склада к четвертом скупшнику — всего пятьдесят доларов. Наозем этот путь маршрутом (1, 4). Его мы наверняка будем использовать!
— Еще бы! И провезти по нему надо как можно больше!
— Правильно! Но больше 40 тонн не проверешь — четвертый скупшик не примет, он тоже рискует. Поставим на этот маршрут 40 тонн, а на маршрут (3, 2) — там тоже 50 доларов — 50 тонн: больше на третьем складе не нашаршь! Получится таблица 2. Я тут заодно подправил емкость и потребности. И в дальнейшем будем ставить перевозки на те маршруты, где поменше тариф.
— Ты хочешь сказаить, что дальше нужно поставить 60 на маршрут(2,1)— там 60 доларов, 10 на (2, 2), в обшем… — и Джо нарисовал таблицу 3.
— Именно так!
— Ха-xa-xa! Значит, и мы что-то смыслим! Ну а теперь осталось только завести третьему скупшнику — Скряге Tomу, кстати мы его еще и надуем при расчете. Вот так, как изобразил в таблице 4.
— Ну и все в порядке! — довольно потер Джо жирные руки. — Нам это обойдется в
$$35 \times 150 + 40 \times 50 + 60 \times 60 + 10 \times 70 + 5 \times 90 + 50 \times 50 = 14500$$
доларов. Не так ли, старина Бейт? И это называется научный метод? Ставлю долар против пяты центов, что любой полицейский сообщит,

15

как найти этот план перевозок за 14 500 — ох-ох — 14 500 долларов. Правда, нам приходится здесь использовать маршрут (1, 3) — 150 долларов за тонну, — вдруг помрачnel Джо, вглядевшись в таблицу.

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

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

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

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

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

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

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

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

Табл. 4.

транспортные расходы изменятся на 80+90—150—60=—40 долларов.

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

В главах Джо загорелся огонек алчности, но тут же потux:
— Нет, здесь что-то не так.
— Ясное дело, не так, — согласно Бейт. — Ведь сколько мы добавим на маршрут (1, 1), столь же придется с (1, 3) и (2, 1). А оттуда самое большее можно снять 35 тонн. Ведь не хочешь же ты взети ману-фактуру обратно на склад!
— Еще бы!
— Значит, самое большее удastoreти по маршруту (1,1) 35 тонн; это позволяет сэкономить 40×35=1400 долларов, и новый план перевозок будет таким, как в таблице 6.

Табл. 5.

16

Табл. 6.

В клетках, которые не вошли в цикл, все осталось по-старому.

— 1400 доларов — кругленская сумма! Давай проверять другие пустьые клетки. Можно набредем на маршрут, который тоже стоит использовать. Вот, например, начнем с клетки (1, 2). Для нее расходы изменятся на 120+60—70—80=30 > 0.

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

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

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

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

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

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

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

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

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

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

Пусть имеется $m$ поставшихков (складов) и $n$ потребителей, $a_i$ — емкость $i$-го склада, а $b_j$ — потребность $j$-го потребителя. Пусть $x_{ij}$ — перевозка от $i$-го поставщика к $j$-му потребителю. Допустимы только такие планы перевозок, для которых $*$

$$\sum_{j=1}^{n} x_{ij} = a_i \quad (i=1, 2, \dots, m),$$

$$\sum_{i=1}^{m} x_{ij} = b_j \quad (j=1, 2, \dots, n),$$

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

*) Мы рассматриваем так называемую «закрытую» модель трансортиной задачи, для которой $\sum a_i = \sum b_j$, то есть сумма емкости (складов) равна сумме потребностей.

18

Табл. 9.

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

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

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

Табл. 10.

Табл. 11.

роения циклов. Если число складов или число потребителей не слишком велико (до 3—4), то применимо динамическое программирование.

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

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

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

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

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

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

— Это не честные гангстеры, а вымогатели! — взмолился Джо. — Я уже разорен. И главное, как их