Пусть имеются гп источников и п пунктов завершения однородного ресурса. В качестве целочисленного ресурса могут выступать, например, работы, заявки или задачи.
Обозначим через щ (г = 1,2,...,т) запасы ресурса на г-м пункте отправления и bj (j = 1,2,..., гг) количество требуемого ресурса на j-м пункте назначения. Обозначим через Cij (i = 1, 2,..., m;j = 1, 2,..., n) стоимость доставки единицы
ресурса из г-го пункта отправления в j-й пункт назначения, а через Xij количество единиц ресурса, перевозимого из г-го пункта отправления в j-й пункт назначения. Тогда постановка задачи заключается в определении минимального значения функции:
условие выполняется, то модель задачи называется закрытой, если нет, то модель является открытой. Далее будем полагать, что имеем закрытую модель.
Известны следующие особенности рассмотренной модели:
• коэффициенты при неизвестных равны единице,
• каждое неизвестное входит лишь в два уравнения системы,
• исследуемые данные можно считать целочисленными (условие целочисленности).
Данные особенности позволяют воспользоваться специальным методом решения транспортной задачи, содержащим два этапа: получение опорного плана и получение оптимального решения.
Рассмотрим пример. Имеются 3 пункта отправления (г = = 1,2, 3) и 4 пункта назначения (потребления) Bj (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.