Классическая транспортная задача. Метод потенциалов.

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Однородный продукт, сосредоточенный в m пунктах отправления в количествах a₁…a_m единиц соответственно, необходимо доставить в каждый из n пунктов назначения в количествах b₁…b_n. Стоимость перевозки единицы из i-го пункта направления в j-й пункт назначения равна c_ij и известна для всех комбинаций (i, j). Пусть x_ij – количество продукта, перевозимого по маршруту (i, j). Задача заключается в определении таких величин x_ij для всех маршрутов (i, j), при которых суммарная стоимость перевозок была бы минимальной.

Математическая модель транспортной задачи имеет следующий вид:

найти наименьшее значение линейной функции          -> min  (1)при ограничениях             (2)

,      (3)   (4)   

Для совместимости уравнений (2) и (3) необходимо, чтобы      (5) Такая модель называется закрытой. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Теорема 1. Любая транспортная задача, для которой выполняется условие (5), имеет решение.

Теорема 2. Система ограничений (2) и (3) содержит m+n-1 линейно независимых уравнений.

Следствие 1. Существует опорное решение транспортной задачи, содержащее не более чем m+n-1 положительных перевозок x_ij.

Теорема 3. Если предположить, что все a_i и b_j - неотрицательные целые числа, то любой опорный план состоит из целочисленных перевозок x_ij.

	b1		bj		bn
аi	c11 x11	…	c1j x1j	…	c1n x1n
.	.	…	.	…	.
ai	ci1 xi1		cij xij		cin xin
.	.	…	.	…	.
am	cm1 xm1	…	cmj xmj	…	cmn xmn

Все транспортные задачи записываются в виде табл.1 Клетки таблицы, в которых находятся отличные от нуля перевозки, называются занятыми, остальные – свободными. Занятые клетки соответствуют базисным неизвестным, и для невырожденного опорного решения их количество равно m+n-1.

Циклом называется набор клеток (i₁, j₁) (i₁, j₂) (i₂, j₂)… (i_k, j_k) (i_l, j_k), в котором две и только две соседние клетки расположены в одном столбце или в одной строке таблицы. Графически цикл представляет собой замкнутую ломанную линию.

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

Метод потенциалов.

Потенциалами опорного решения x = (x_ij) называют числа u_i и v_j (i= , j= ) такие, что u_i+ v_j=с_ij для всех занятых клеток. Так как количество занятых клеток m+n-1, то для определения потенциалов надо решить систему m+n-1 линейных уравнений с m+n неизвестными. Эта система всегда совместна, причем одно из неизвестных можно положить равным любому числу и тогда все остальные неизвестные определяются однозначно.

Потенциалы u_i и v_j (i= , j= ) можно интерпретировать как двойственные переменные транспортной задачи. Составить двойственную задачу линейного программирования к прямой задаче (1) – (5). С этой целью ограничения (2), (3) представим в матричной форме AX = B, где матрица А состоит из нулей и единиц и имеет размерность (m+n) x mn. Матрицу А, вектор В и вектор-строку Y двойственных переменных для наглядности можно определить формулами:       

X – вектор-столбец

X^Т = (x₁₁, x₁₂,…, x_1n, x₂₁, x₂₂,…, x_2n,…, x_m1, x_m2,…, x_mn).

Тогда двойственная задача будет иметь вид: g(Y) = (Y, B) – max; при ограничениях YA£C. В нематричном представлении ограничения двойственной задачи записываются очень просто

u_i + v_j £ c_ij (i= , j= )

Теорема 4. Пусть u_i и v_j (i= , j= ) – потенциалы опорного решения x = (x_ij) транспортной задачи. Если для всех свободных клеток (i, j) оценки s_ij= c_ij – (ui + v_j) > 0, то х – оптимальное решение задачи.

Решение транспортной задачи методом потенциалов проводится по следующей схеме:

1) находим начальное опорное решение х¹ = (х¹_ij) методами северо-западного угла (диагональный) или наименьшего элемента;

2) вычисляем потенциалы u_i и v_j (i= , j= ) опорного решения х¹. Если для всех свободных клеток (i, j) s_ij= c_ij – (ui + v_j) > 0, то х – оптимальное решение и задача решена. В противном случае выбираем клетку (k, l), соответствующую наименьшему значению s_ij;

3) в таблице строим цикл, одна вершина которого находится в клетке (k, l), а все остальные вершины – в занятых клетках. Далее, вершину в клетке (k, l), метим знаком "+", остальные – знаками "-" и "+" так, чтобы они от вершины к вершине чередовались. Обозначим через q наименьшее из чисел х¹_ij, стоящих в клетках, помеченных знаком "-"; пусть q = х_rs (если такое число находится в нескольких клетках, то выберем ту из них, которой соответствует наибольшее значение с_ij). После этого заполняем таблицу согласно следующему правилу:

а) клетки, не являющиеся вершинами цикла, остаются без изменения;

б) если клетка (i, j) помечена знаком "+", то в нее записывают число х¹_ij + q;

в) клетка (r, s) становится свободной, ее не заполняют, а в остальные клетки (i, j), помеченные знаком "-", записывают число х¹_ij - q.

В результате получаем ациклический набор из m+n-1 занятых (базисных) клеток таблицы, который определяет опорное решение х² такое, что f(х²)£f(х¹).

Принимая х² за исходное опорное решение, повторяем п.2 и п.3 до тех пор, пока не будет найдено оптимальное решение задачи.