Постановка задачи. Имеются т пунктов отправления Ah Аъ Ат в которых сосредоточены запасы каких-то однородных грузов в количестве аи а2,ат единиц соответственно, и п пунктов назначения Въ Въ ...,Вп, готовых принять b\, b2,...,b единиц этих грузов соответственно.

Известны стоимости cik перевозки единицы груза от каждого пункта отправления At к каждому пункту назначения Bk (i = 1, 2,т\ к = 1, 2,

Представленные данные удобно записать в виде таблицы

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

Перейдем к описанию поставленной задачи, пользуясь математическими символами и формулами.

Обозначим через xik 0 (неизвестное нам) количество единиц груза, которое требуется перевезти от пункта отправления At к пункту назначения Вк (/ = 1,2,т\ к = 1,2,п). Это можно записать в виде матрицы

хп хп ... х1п

*21 *22 Х2п Хт1 Хт2 Хтп

Рассмотрение задачи начнем со случая, когда сумма всех запасов равна сумме всех заявок

Между заданными числами ah Ък и cik и введенными неизвестными xik существуют естественные связи:

суммарное количество груза, направляемого из каждого пункта отправления во все пункты назначения, должно совпадать с запасом груза в этом пункте (т условий)

ХП + Х\2 + - Х\п = а\> Х21 + Х22 + ** Х2п = а2>

Хт\ + Хт2 + Хтп = °т >

суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно совпадать с заявкой на груз, поданной этим пунктом (л условий)

*11 + Х21 + - * 1 = *!

х12 + х22 + хда2 = Z>2,

Х1 + *2 + - *- = *V

Ввиду того что стоимость перевозки xik единиц груза по маршруту AfBk пропорциональна их числу

CikXik>

суммарная стоимость всех перевозок вычисляется по формуле

т п /=1 к=\

Она должна быть минимальной

w -> min.

К решению транспортной задачи (как, впрочем, и к решению многих других задач) нужно подходить, прежде немного подумав - не всегда очевидное, явно бросающееся в глаза решение будет наилучшим. Вот только один пример ([9], с. 55-56).

Пример 1. Менеджер по транспорту должен организовать наиболее Дешевую доставку продукта с трех фабрик на три склада. Каждая фабри-

ка может отправлять продукт на любой из складов и каждый из складов может принимать продукт с любой фабрики. Стоимость перевозки по маршруту пропорциональна произведению перевозимого количества на стоимость одного килограмма груза. Количество продукта, который должен вывозиться каждый день с каждой фабрики А, В и С на каждый склад X, Y и Z известно:

300 кг с фабрики А, 600 кг с фабрики В и 500 кг с фабрики С (итого 1400 кг),

600 кг на склад X, 300 кг на склад У и 500 кг на склад Z(htoto 1400 кг).

Как видно, спрос и предложение совпадают. Стоимость перевозки килограмма груза по каждому из девяти маршрутов приведена в таблице (туда же внесены и данные, приведенные выше).

Таблица

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

Тем самым, решение, опирающееся на здравый смысл, выглядит так:

и общая стоимость перевозки равна

300 1 + 300 6 + 500 6 = 5100.