День 4. Оптимальное планирование транспортных перевозок (Куда везти бетон?)

- Водитель Задвижкин! Ваш МАЗ простаивал?
- Нет, я возил бетон фиктивному потребителю.

(Разговор в диспетчерской)

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

Все данные задачи изобразим в виде следующей таблицы^*.

^* (Этот раздел могут смело читать противники алгебры и геометрии, если они все-таки способны переносить таблицы. Читателям, которых и таблицы не устраивают, мы рекомендуем закрыть эту книжку и попросить в библиотеке "что-нибудь для души".)

В правом верхнем углу клеток, расположенных в центре таблицы, проставлены тарифы, то есть стоимости перевозок одного кубометра бетона от каждого завода поставщика к каждому потребителю. Например, тариф от второго завода к третьему объекту (маршрут 2-3) составляет 6 руб., а от первого к четвертому (маршрут 1-4) - 1 руб. Суммарная суточная мощность равна суммарной потребности в бетоне - 430 м³. Вопрос в том, как прикрепить потребителей к поставщикам, чтобы транспортные расходы были минимальны.

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

Глядя на таблицу, кое-что можно сказать без расчетов. Например, что маршрут 1-4 - самый выгодный, тариф на нем равен 1 руб., а маршрут 2-3 - самый невыгодный (6 руб. за кубометр). Но как лучше всего распределить перевозки? На этот вопрос ученые научились отвечать лишь в сороковых годах, то есть в пределах жизни большинства наших читателей. Это тем более поразительно, что, как мы сейчас увидим, способ решения транспортной задачи весьма прост. И если читатель решил освоить на пробу один из методов кибернетики, мы рекомендуем ему именно этот.

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