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

(проверка на оптимальность, улучшение Т-плана)

Содержание метода:

1. Каждому поставщику поставим в соответствие действиетельное число – потенциал строки u_i. Каждому потребителю – потенциал столбцаv_j . Числаu_i иv_j рассчитывают по формуле:

u_i +v_j= с_ij

Где с_ij– удельная стоимость ввыделеннойклетке с адресом (i,j) построенной Т-таблицы. Причем один из потенциалов можно задать произвольно. Как правилоu₁=0.

2. Найдем оценку ∆ _ijдля каждой невыделенной клетки по формуле:

∆ _ij= с_ij – (u_i +v_j),

где u_{i ,}v_j – найденные потенциалы, с_ij– удельная стоимость перевозок вневыделеннойклетке (i,j).

Если оценка каждой невыделенной клетки не отрицательная, т.е. ∆ _ij0, то найденный Т-план является оптимальным. В противном случае построенный план перевозок не гарантирует минимальных затрат на перевозку груза и необходимо перейти к улучшенному Т-плану.

3). Для построения нового Т-плана, отвечающему меньшим суммарным затратам на перевозку груза, выполним следующие действия:

• Определим какой из невыделенных клеток соответствует наименьшая оценка. Предположим это клетка с адресом (l,k). Отметим ее знаком + . Клетка (l,k) – первая выделенная клетка нового Т-плана.

• Двигаясь от клетки (l,k) по тому же столбцу отмечаем знаком (-) выделенную клетку, затем отмечаем знаком (+) выделенную клетку, стоящую в той же строке, что и предыдущая. В столбце, в котором находится последняя отмеченная клетка, отметим выделенную клетку знаком (-) и так далее до получения замкнутого контура.

• Сравним величину поставок (х_{i j}) в каждой выделенной клетке со знаком (-).Пусть -величина наименьшей поставки. Исключим соответствующую ей клетку из числа базисных. В клетке (l,k), отмеченной знаком + , положимx_l,k=. Во всех остальных базисных клетках со знаком (+) увеличим величину поставок на , со знаком (-) - уменьшим на . Получили улучшенный Т-план.

4). Необходимо проверить на оптимальность новый Т-план перевозок груза. Для этого вернемся к пункту 1) схемы метода и далее выполним последовательно его шаги.

Замечание 6: замкнутый контур, полученный при построении улучшенного Т-плана, содержит четное число вершин, причем число клеток со знаком (+) совпадает с числом клеток со знаком (-).

Найдем оптимальный план перевозок для задачи (*). Для этого необходимо взять любой первоначальный Т-план из двух построенных выше. К примеру возьмем Т-план, построенный по методу наименьшей стоимости. Рассмотрим таблицу перевозок, полученную при этом (Табл.15).

1). Рассчитаем потенциалы строк и столбцов, используя удельные стоимости перевозок в выделенных клетках по формуле: u_i +v_j= с_ij.

Пусть u₁=0, тогдаv₁= с₁₁-u₁=3-0=3;v₂= с₁₂-u₁=5-0=5.

Так как v₁=3, тоu₂= с₂₁-v ₁=1-3=-2.

Известно значение v₂= 5, значитu₃= с₃₂-v ₂=8-5=3.

В свою очередь, зная значение потенциала 3-й строки, можно найти потенциал 3-го и 4-го столбцов: v₃= с₃₃-u₃=12-3=9 иv₄= с₃₄-u₃=7-3=4.

Заметим, что найденные потенциалы строк и столбцов удобно вносить в соответствующую данному шагу Т-таблицу (Табл.16)

2). Используя найденные потенциалы строк и столбцов оценим каждую из невыделенных клеток по формуле: ∆ _ij= с_ij – (u_i +v_j).

₁₃= с₁₃–(u₁ +v₃)=7-(9+0)= -2<0;₁₄= с₁₄–(u₁ +v₄)=11-(4+0)= 7>0;

₂₂= с₂₂ – (u₂ +v₂)=4-(5-2)= 1>0;₂₃= с₂₃ – (u₂ +v₃)=6-(9-2)= -1<0;

₂₄= с₂₄ – (u₂ +v₄)=2-(4-2)=0;₃₁= с₃₁ – (u₃ +v₁)=5-(3+3)= -1<0.

Так как не все значения ∆ _ij 0, то можно сделать вывод, построенный Т-план не является оптимальным.

3). Построение нового Т-плана начнем с клетки (1;3), так как оценка этой клетки наименьшая. Отметим клетку (1;3) знаком + и выделим ее. Начнем движение от этой клетки по 3-у столбцу до выделенной клеткии (3;3), которую отметим знаком (-). Далее продолжим движение по 2 –й строке до выделенной клетки (3;2), отметим ее знаком (+). Последняя вершина замкнутого контура – клетка (1;2), ее отметим знаком (-). Получили контур, состоящий из четного числа вершин и содержащий равное число положительных и отрицательных вершин (Табл.16).

Сравним величины поставок в отрицательных вершинах контура. Минимальный объем поставки, равный =80, соответствует двум отрицательным вершинам контура: (1;2) и (3;3). Удалим из числа выделенных клетку (3;3), так как ей соответствует наибольшая удельная стоимость. В остальных вершинах контура объемы перевозок распределятся следующим образом: х₁₃==80, х₃₂=40+=40+80=120, х₁₂=80-=80+80=0. Получили новый Т-план. Внесем полученные изменения в таблицу 17. Убедимся в правильности расчетов:

А) 1 строка: 100=20+0+80; 2 строка: 130=130; 3 строка: 170=120+50; 1 столбец: 150=20+130; 2 столбец: 120=0+120;

3 столбец: 80=80; 4 столбец: 50=50.

Б) Каждый новый Т-план должен гарантировать уменьшение затрат на перевозку груза. Предыдущий план перевозок требовал 2220 ден.ед. Новый Т-план:

L=3*20+5*0+7*80+1*130+8*120+7*50=1850

Таким образом, транспортные затраты уменьшились.

В) Полезно проверить сохранилось ли число выделенных клеток таблицы. В нашем случае их число не изменилось.

Выполнение пунктов проверки А),Б),В) показало, что новый Т-план построен верно. Проверим его на оптимальность. Для этого:

• рассчитаем потенциалы строк и столбцов, внесем полученные величины в таблицу 17;

• вычислим оценки невыделенных клеток таблицы

₁₄=7>0; ₂₂= 1>0; ₂₃=1>0;₂₄=0;₃₁= -1<0; ₃₃=1>0.

Поскольку среди вычисленных оценок есть отрицательная, то можно утверждать, что построенный Т-план не является оптимальным. Построение улучшенного Т-плана начнем с клетки (3;1), так как ей соответствует наименьшее значение ∆ _ij.

Таблица 16 Таблица 17

L=2220 =80		а	б	с	д	ui		L=1850 =20		а	б	с	д	ui
		150	120	80	50					150	120	80	50
А	100	3	5	7	11	0		А	100	3	5	7	11	0
		20	-80	+						-20	+0	80
В	130	1	4	6	2	-2		В	130	1	4	6	2	-2
		130								130
С	170	5	8	12	7	3		С	170	5	8	12	7	3
			+40	-80	50					+	-120		50
vi		3	5	9	4			vi		3	5	7	4

4) Построим замкнутый контур, начиная с клетки (3;1). Отобразим его в таблице 17. Наименьшая величина поставки в отрицательных вершинах контура равная 20 соответствует клетке (1;1). Исключим ее из числа выделенных. При этом х₁₂=0+=20, х₃₂=120-=100 и х₃₁==20. Внесем изменения в таблицу 18 (замечание: правильность построения Т-плана примем как факт, проверку упустим для краткости), в ней же отобразим значения потенциалов строк и столбцов.

Рассчитаем оценки невыделенных клеток: ₁₁=1>0;₁₄=7>0;₂₂=0;₂₃=0;₂₄=-1<0;₃₃=2>0. Полученный Т-план оптимальным не является.

Таблица 18 Таблица 19

L=1340 =50		а	б	с	д	ui		L=1990		а	б	с	д	ui
		150	120	80	50					150	120	80	50
А	100	3	5	7	11	0		А	100	3	5	7	11	0
			20	80							20	80
В	130	1	4	6	2	-1		В	130	1	4	6	2	-1
		-130			+					80			50
С	170	5	8	12	7	3		С	170	5	8	12	7	3
		+20	100		-50					70	100
vi		2	5	7	4			vi		2	5	7	3

5) Построение нового Т-плана начнем с клетки (2;4), так как ей соответствует наименьшая оценка. Построенный контур отразим в таблице 18. Сравним объемы поставок в отрицательных вершинах контура. Наименьшая величина поставки =50 находится в клетке (3;4). Это означает, что данную клетку необходимо исключить из числа выделенных, а в остальных вершинах контура объемы поставок распределятся следующим образом: х₂₄==50, х₃₁=20+=70 и х₂₁=130-=80. Отобразим изменения в таблице 19 (замечание: правильность построения Т-плана примем как факт, проверку упустим для краткости).

Потенциалы строк и столбцов внесем в таблицу 19. Вычислим оценки невыделенных клеток таблицы: ₁₁=1>0;₁₄=7>0;₂₂=0;₂₃=0;₃₂=2>0;₃₄=1>0. Согласно требованиям данного метода можно утверждать, что данный Т-план является оптимальным.

Сделаем выводы:

1. Оптимальный план заключается в перевозке груза в пункт а со складов В и С в объеме 80 и 70 усл.ед соответственно; в пункт б со складов А и С в объеме 20 и 100 усл.ед.; 80 усл.ед в пункт с со склада А и 50 усл.ед. в пункт д со склада В.

2. Транспортные издержки при этом будут равны L=5*20+7*80+1*80+2*50+5*70+8*100=1990 ден.ед.