Метод потенциалов нахождения оптимального решения.

Введем показатель U₁ для каждой строки и V₁ для каждого столбца. Эти показатели называются потенциалами поставщиков и потребителей. Потенциалы подбираются так, чтобы для заполненной клетки(I,j) выполнялось равенство:

d_ij= U_i+V_j +С_ij ; (2:4) d_ij – оценка ij клетки;

с_ij – транспортные расходы;

Оценки заполненных клеток равны нулю (d_ij=0). Значение одного из U_i можно задавать произвольно (например, U₁=0), тогда для заполненных клеток d_ij=U_i+V_j+C_ij=0;

Рассмотрим нахождение потенциалов для плана поставок(таблица 2.1)

 

Nj Mi					Ui
					-4
					-3
					-4
Vj				-3

 

 

Начинать можно с любой строки или любого столбца. Начнем с первого столбца и назначим значение потенциала поставщика равное 0: V₁ =0. Зная это, найдем оценку первой клетки (d₁₁).

 

d₁₁= U₁+V₁+C₁₁=0; d₂₁=U₂+V₁+C₂₁=0;

U₁+0+4=0; U₂+0+3=0;

U₁=-4 U₂= -3;

 

По формуле (2.4) определим остальные потенциалы:

 

d₂₂= U₂+V₂+C₂₂=0; d₂₃=U₂+V₃+C₂₃=0;

-3+V₂+1=0; -3+V₃+2=0;

V₂=2; V₃=1;

 

d₃₃=U₃+V₃+C₃₃=0; d₃₄=U₃+V₄+C₃₄=0;

V₃+1+3=0; -4+V₄+7=0;

U₃=-4; V₄=-3;

 

 

Используя формулу (2.4) определяем оценки свободных клеток:

d₁₂=U₁+V₂+C₁₂= -4+2+7=5;

d₁₃=U₁+V₃+C₁₃= -4+1+2=4;

d₁₄=U₁+V₄+C₁₄= -4+3-3= - 4;

d₂₄=U₂+V₄+C₂₄= -3-3+4=-2;

d₃₁=U₃+V₁+C₃₁= -4+0+5=1;

d₃₂=U₃+V₂+C₃₂= -4+2+6=4;

 

В итоге получаем следующую матрицу:

 

 

Нули - заполненные клетки, вычисленные оценки – не заполненные клетки.

 

Так как матрица оценок содержит отрицательные числа, то план поставок не оптимален. Проведем оптимизацию. Выберем клетку с наименьшей оценкой (клетка (1.4)). Задача: построить цикл пересчета. Выходя из клетки(1.4) и двигаясь только по заполненным клеткам, нужно вернуться в стартовую клетку (1.4), при этом направление отдельных отрезков контура могут быть только горизонтальными и вертикальными (при этом запрещается делать два последовательных шага в одной строке или в одном столбце). Например, цикл (1,4)-(1,1)-(2,1)-(2,3)-(3,3)-(3,4)-(1,4).

 

 

(1.1) (1.4)

− +

 

− +

 

 

 

(2.1)

 

 

(3.3) (3.4)

 

 

В стартовой клетке (1.4) запишем знак “+”. Двигаемся по циклу чередуя знаки. Среди поставок в клетками со знаком “−” ((1,1),(2,3),(3,4)) найдем минимальную:

min(30, 30, 130)=30;

После этого в клетках со знаком “−” уменьшаем поставки на минимум, то есть на 30, а в клетках со знаком “+” – увеличим на этот же минимум. Если обнаружится одна клетка с нулевой поставкой, то она становится пустой. У нас таких клеток две: (1,1) и (1,2). Пустой объявим только одну из них с наибольшим тарифом (1,1). В клетке (2,2) будет сделана нулевая поставка и она остается отмеченной. Это делается для выполнения соотношения m+n-1.

 

Nj Mi					Ui
					-3
					-4
Vj				-3

 

 

Для нового плана поставок нужно проверить его оптимальность, находим оценки строк и столбцов. Вычислим оценки пустых клеток и простроим матрицу:

 

 

В матрице есть отрицательный показатель, значит, план является не оптимальным, однако, суммарные затраты по этому плану составят F=3*30+3*70+1*120+2*0+3*150+7*100=1570, что меньше предыдущих затрат (1690). Далее составляется новый цикл пересчета и оптимизируется план поставок уже по изученной схеме, до тех пор пока в таблице не перестанут присутствовать отрицательные элементы. План поставок с соответствующей матрицей с не отрицательными элементами будет являться оптимальным.

Самостоятельно:

Продолжая оптимизировать план (таблица 2.2), строим для него цикл пересчета: (2,4) – (3,4) – (3,3) –(2,3)–(2,4)
(2,3) (2,4)

+

−

min(0,100)=0. Клетки (2,3) становится пустой, а клетка (2,4) –

0 отмеченной(нулевая поставка). Новый план поставок представлен

−

+

в таблице 2,3.

 

 

(3,3) (3,4)

 

Nj Mi					Ui
					-3
					-6
Vj				-3

 

Для нового плана находим оценки строк и столбцов и матрицу оценок клеток

По матрице видим, что план (таблица 2.3) не оптимален, т,к. оценка клетки (3,1)

меньше 0.

Строим для нее цикл пересчета : (3,1) – (2,1) –(2,4) – (3,4) – (3,1)

 

(2,1) (2,4)

+

−

min(70,100)=70. В клетках с “+” поставки увеличиваются на 70, а в

70 0 клетках с “−” уменьшаются. Клетка (2,3) становится пустой.

−

+

 

 

(3,1) (3,4)

 

Новый план поставок:

Nj Mi					Ui
					-1
					-2
					-5
Vj				-2

 

Находим оценки строк и столбцов. Получаем матрицу оценок клеток

Матрица оценок клеток не содержит отрицательных чисел. Получен оптималь-

ный план поставок.

Суммарные затраты на перевозку груза равны:

 

F=3*30+1*120+4*70+5*70+3*150+7*30 =1500

Против 1690 (таблица 2.1) для первоначального плана перевозок.