Транспортная задача. Частный случай ЗЛП или частный случай задачи оптимизации сетей

 

Частный случай ЗЛП или частный случай задачи оптимизации сетей. Применяется при решении плановых задач выбора маршрутов перевозок. В общем виде формулируется следующим образом. Пусть рассмотрено m различных поставщиков (пунктов отправления) P_i, располагающих некоторой однородной продукций соответственно в количествах a_i i=1,m и рассматривается отправление этой продукции в n пунктов потребления Q_j, потребности которых равны b_j cсоответственно. Известны тарифы перевозок этой продукции из пункта P_i в пункт Q_j (затраты на перевозку единицы груза) C_ij. Требуется составить такой план перевозок чтобы общая стоимость затрат была минимальной. К этой задаче возможно дополнение об ограничениях по пропускным способностям, о существовании промежуточных пунктов перезагрузки, источников и стоков груза. Математическая модель этой задачи имеет вид:

X_ij – количество едениц груза из i в j пункт.

ƒ= →min

x_ij≥0; Чаще всего ∑a_i=∑b_j

Учитывая, что эта задача является частным случаем ЗЛП, рассматриваются специальные способы решения этих задач.

Транспортная таблица задачи имеет вид:

Qj Pi	Q1	Q2	…	Qn	Запасы
P1	X11 c11	X12 c12	…	X1n c1n	a1
P2	X21 c21	X22 c22	…	X2n c2n	a2
…	…	…	…	…	…
Pm	Xm1 cm1	Xm2 cm2	…	Xmn cmn	am
Потребность	b1	b2	…	bn

 

Транспортная задача имеет решение т.к ∑a_i=∑b_j (закрытая модель).

Если ∑a_i < ∑b_j, то вводят фиктивный пункт производства и не все пункты в оптимальном решении будут удовлетворены в потребности.

Если ∑a_i>∑b_j, то не все запасы будут вывезены из пунктов производства, в решении вводят фиктивный пункт потребления. Заметим, что объем продукции в фиктивном пункте равен разности │∑a_i -∑b_j│.

Циклом в транспортной таблице называют замкнутую ломаную линию, удовлетворяющую следующим условиям:

1. Все вершины ломаной находятся в клетках транспортной таблицы.

2. Ребра расположены по строкам или столбцам, но не диагоналям.

3. К каждой вершине подходят 2 ребра: одно - по строке, другое - по столбцу транспортной таблицы.

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

Теорема:

Допустимое решение транспортной задачи является опорным, т.и.т.т.к. набор заполненных клеток ацикличен, т.е в него входит m+n-1 клетка.

Определение. Потенциалом опорного решения α транспортной задачи называют числа U_i i=1,m; V_j j=1,n такие что U_i+V_j=C_ij – тариф заполненной клетки.

Теорема:

Достаточное условие оптимальности опорного решения. Если для всех незаполненных клеток (i,j) U_i+V_j=C_ij, где U_i и V_j - потенциалы опорного решения α, тогда это опорное решение является оптимальным.