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

Введем показатель 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)

N_j M_i		U_i
		-4
		-3
		-4
V_j	-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.

N_j M_i		U_i

		-3
		-4
V_j	-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)