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

Пусть имеются т источников и п пунктов завершения однородного ресурса. В качестве целочисленного ресурса могут выступать, например, работы, заявки или задачи.

Обозначим через щ (і = l,2,...,m) запасы ресурса на г-м пункте отправления и bj (j = 1,2,..., гг) количество требуемого ресурса на j-м пункте назначения.

ресурса из г-го пункта отправления в j-й пункт назначения, а через Xij количество единиц ресурса, перевозимого из г-го пункта отправления в j-ii пункт назначения. Тогда постановка задачи заключается в определении минимального значения функции:

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

Известны следующие особенности рассмотренной модели:

• коэффициенты при неизвестных равны единице,

• каждое неизвестное входит лишь в два уравнения системы,

• исследуемые данные можно считать целочисленными (условие целочисленности).

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

Рассмотрим пример. Имеются 3 пункта отправления Аг- (г = = 1,2, 3) и 4 пункта назначения (потребления) Вj (j = 1,... ,4). В табл. 2.14 указаны величины сц (г = 1,2,3; j = 1,..., 4), а также имеющиеся запасы и потребности (ёмкости).

1-й этап. Получение опорного решения методом минимального элемента.

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

F = Ы60 + 4 • 120 + 8 • 20 + 2 * 50 + 3 * 30 + 6 • 90 = 1530.

Таблица 2.14

Таблица 2.15

3. Для перехода к новому плану рассматривают все свободные клетки, для которых а.ц > 0 и из них выбирают клетку с максимальным значением ощ.

3.1.Каждой из клеток, связанных с данной циклом присваивают определённый знак, причём свободной клетке — знак (+), а всем остальным поочередно знаки (—) и (+) по циклу.

3.2.В данную свободную клетку переносят меньшее из чисел Xij, стоящих в минусовых клетках. Одновременно это число необходимо прибавить к соответствующим числам, находящимся в плюсовых клетках и вычесть из чисел, находящихся в минусовых клетках. Клетка, которая раньше была свободной, становится занятой, а минусовая клетка с минимальным числом становится свободной (пустой).

Таким образом, получаем новый опорный план, который следует проверить на оптимальность (переход к этапу 2).

В нашем случае необходимо заполнить клетку (1,4), так как суі4 > 0. Соответствующая разметка клеток, образующих цикл, показана в табл. 2.15. В результате перемещения ресурса в количестве 90 единиц, получаем новое решение (табл. 2.16).

Таблица 2.16

поскольку полученное решение не является оптимальным, производим перемещение ресурса в количестве 20 единиц по новому циклу с заполнением клетки (2,2), так как с*22 > 0 (табл. 2.17).

Таблица 2.17

F = 50 + 2 * 110 + 5 * 20 + 4 * 120 + 2 * 30 + 3 • 140 = 1330.

Можно легко проверить, что данный вариант является оптимальным.