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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

– Именно так!

– Ха-ха-ха! Значит, и мы что-то смыслим! Ну а теперь осталось только завезти третьему скупщику – Скряге Тому, кстати мы его ещё и надуем при расчёте. Вот так, как я изобразил в таблице 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,1) – 80 долларов. Их надо добавить. А 150 долларов – провоз тонны на маршруте (1,3) – наоборот, долой, как и 60 с маршрута (2,1). Ну и 90 придётся прибавить за лишнюю тонну на маршруте (2,3). Итого, транспортные расходы изменятся на

долларов.

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

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

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

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

– Ещё бы!

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

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

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

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

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

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

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

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

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

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

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

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

Пусть имеется m поставщиков (складов) и n потребителей, a_i – емкость i-го склада, а b_j – потребность j-го потребителя. Пусть x_ij – перевозка от i-го поставщика к j-му потребителю. Допустимы только такие планы перевозок, для которых ^**

n ∑  xij = ai     ( i = 1, 2, ..., m),  j=1	(1)
m ∑  xij = bj     ( j = 1, 2, ..., n),  i=1

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

m  n  z =  ∑  ∑  cij xij  i=1  j=1

(2)

минимальна.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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