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

Проверить тип модели транспортной задачи и в случае открытой модели свести ее к закрытой, когда Σа_i =Σb_j

Случай открытой модели Σа_i ¹Σb_j легко сводится к закрытой модели путем введения фиктивного потребителя B_n+1 c потребностью b_n+1=Σa_i-Σb_j, либо - фиктивного поставщика А_m+1 c запасом a_m+1=Σb_j-Σa_i; при этом тарифы фиктивных участников принимаются равными 0.

Решение ТЗ разбивается на 2 этапа:

1. Определение начального допустимого базисного решения(1 опорного плана – первоначальное распределение поставок

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

Способы составления 1-таблицы (опорного плана).

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

ПН ПО	B1	В2	В3	В4	Запасы ai
A1	1 x11	2 x12	x13	3 x14
A2	1 x21	6 x22	x23	2 x24
A3	6 x31	3 x32	x33	x34
Заявки bj

I. Способ северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью вывозиться груз из А_i, либо полностью удовлетворяется потребность B_j. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы a_i и не удовлетворяются потребности b_j. В заключение проверяют, что найденные компоненты плана X_ij удовлетворяют горизонтальным и вертикальным уравнениям и что выполняется условие невырожденности плана.

ПН ПО	B1	В2	В3	В4	Запасы ai
A1	1	2		3
A2	1	6		2
A3	6	3
Заявки bj

Начинаем заполнение ТТ с левого верхнего («северо-западного») угла. Поставщик B₁ подал заявку на 20 ед.. Удовлетворим ее из запасов A₁(60-20). У него остается – 40. Отдадим их В₂. Но он заказал 110. Отдадим 110-40=70 из запасов A₂ и т.д. Сумма перевозок по строке должна быть = запасу соответствующего пункта отправления, а сумма перевозок по столбцу = заявке соответствующего ПН. Является ли данный план опорным, т.е. число свободных клеток д.б.=(m-1)(n-1) – 2x3=6.

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

x_ij=min(a_i, b_j). Если a_i<b_j, то запасы поставщикаA_i исчерпаны, а потребность B_j стала b’_j= b_j- a_i, поэтому не принимая более во внимание i строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. Для случая a_i>b_jиз рассмотрения исключаем j столбец, а запасы A_i - a’_I= a_i- b_j. Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности - удовлетворены.

ПН ПО	B1	В2	В3	В4	Запасы ai
A1	1	2		3
A2	1	6		2
A3	6	3
Заявки bj

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

Определение: потенциалами решения называются числа u_j®a_i, v_j®b_j, удовлетворяющие условию v_j+u_i=C_ij (*) для всех заполненных клеток (i,j).

Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n неизвестными, имеющую бесчисленное множество решений; для ее определенности одному неизвестному придают любое число (обычно u₁=0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности. Если известны потенциалы решения X₀ транспортной задачи и для всех незаполненных клеток выполняются условия v_j + u_i £ C_ij, то X₀ является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличились.

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

1) одна клетка пустая, все остальные занятые;

2) любые две соседние клетки находятся в одной строке или в одном столбце;

3) никакие 3 соседние клетки не могут быть в одной строке или в одном столбце.

Пустой клетке присваивают знак «+», остальным - поочередно знаки «-» и «+».

Для перераспределения плана перевозок с помощью цикла перерасчета сначала находят незаполненную клетку (r, s), в которой v_j + u_i >C_rs, и строят соответствующий цикл; затем в минусовых клетках находят число =min{X_ij}. Далее составляют новую таблицу по следующему правилу:

1) в плюсовые клетки добавляем ;

2) из минусовых клеток отнимаем ;

3) все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающее новое решение X, такое, что f(X₁) £ f(X₀); f(X₁)=f(X₀) - *max C¢_rs; оно снова проверяется на оптимальность через конечное число шагов обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Теорема

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

Правило 1.

Для свободной клетки следует построить цикл пересчета. В вершинах этого цикла расставить последовательно чередующиеся знаки, начиная со знака«+» в свободной клетке.

Правило 2

Коэффициентам затрат в таблице поставок в каждой строке и столбце нужно прибавить такие числа (потенциалы), чтобы коэффициенты затрат в заполненных клетках стали =0, полученные при этом коэффициенты затрат свободных клеток = оценкам этих клеток.