Математическая модель классической транспортной задачи

Задача закрепления потребителей за поставщиками получила название классической транспортной задачи.

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

Условия задачи можно представить в математической форме. Каждый поставщик должен дать потребителям столько продукции, сколько у него есть, т.е.

_n

S_i = ∑ x_ij,

^{j= 1}

Каждый потребитель должен получить столько, сколько ему потребуется, т.е.

_m

D_j = ∑ x_ij,

^{j= 1}

Необходимо найти такой вариант плана перевозок, чтобы транспортная работа была минимальной, т.е.

_{m n}

∑ ^. ∑ a_ij ^. x_ij=min,

^{i= 1 j= 1}

где: m- число поставщиков;

n- число потребителей;

х_ij- объем перевозок между пунктами i и j;

S_i- ограничения по предложению (количество продукции у поставщика);

D_j- ограничения по спросу (количество продукции, которое должен получить потребитель);

a_ij- расстояние от пункта i до пункта j.

Запись и решение транспортной задачи выполняется методом потенциалов в таблично - матричной форме. Совокупность всех элементов матрицы х_ij называется планом перевозок или распределением поставок.

2.1. Решение транспортной задачи методом потенциалов (МОДИ)\

Рис. 2. Последовательность решений задачи методом потенциалов (схема выполнения расчета).

Задача 2.1.

Из пяти грузообразующих пунктов А1, А2, А3, А4, А5. Необходимо перевести однородный груз шести потребителям В1, В2, В3, В4, В5, В6. Количество груза в пункте А1=300 т, в пункте А2=500 т, в пункте А3=400 т, в пункте А4=800 т, в пункте А5=1000 т. Спрос потребителей на данный груз составляет: В1=200 т, В2=350 т, В3=650 т, В4=600 т, В5=900 т, В6=300 т. Расстояния между грузообразующими и грузопоглащающими пунктами приведены в таблице 2.1.

Таблица 2.1.

Дата добавления: 2015-07-20