http://npc-news.ru/

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

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

Обозначим через щ (г = 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.


Комментарии закрыты.