Производственной процесс и его элементы

Алгоритм «mincost maxflow» можно запускать и сразу — без нахождения опорного плана. Но в этом случае процесс решения будет несколько более долгим. Выполнение алгоритма «mincost maxflow» происходит не более чем за операций. (  — количество рёбер,  — количество вершин.) При случайно подобраных данных обычно требуется гораздо меньше — порядка операций.

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 Табл. 1  

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

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

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

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

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

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

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

 

 Табл. 2  

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

 

 Табл. 3  

– Именно так!

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

 

 Табл. 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 (ёмкости и потребности нам уже не нужны).