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

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

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

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).

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

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

D₂₄= с₂₄ – (u₂ + v₄)=2-(4-2)=0; D₃₁= с₃₁ – (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;

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

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

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

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

L=2220 a=80	а	б	с	д	ui		L=1850 a=20	а	б	с	д	ui
А						0	А						0
	-80	+		-20	+0
В						-2	В						-2
С						3	С						3
	+40	-80		+	-120
vi	3	5	9	4		vi	3	5	7	4

 

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

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

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

L=1340 a=50	а	б	с	д	ui		L=1990	а	б	с	д	ui
А						0	А						0
В						-1	В						-1
-130			+
С						3	С						3
+20			-50
vi	2	5	7	4		vi	2	5	7	3

 

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

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

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

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

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