Оптимальное распределение ресурсов

Таблица 1

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

Таким образом, все запасы распределены и все потребности удовлетворены. Получен первый допустимый план при следующих значениях неизвестных:

х₁₁=120;   х₁₂=40;   х₂₂=10;   х₂₃=130;   х₃₃=60;   х₃₄=110.  

Значения остальных  неизвестных равны нулю. Значение целевой функции при этом равно:

Z₁=7·120+8·40+5·10+9·130+3·60+6·110=3220 ден.ед.

Для проверки правильности распределения ресурсов и удовлетворения потребностей необходимо суммировать объем перевозок, как по строкам, так и по столбцам. После этого план проверяется на оптимальность.

Условимся называть клетки матрицы, соответствующие положительным компонентам плана, занятыми (базисными), а остальные – свободными (небазисными). Число занятых клеток в опорном плане должно быть m + n-1. В случае, когда их оказывается меньше, одну из свободных клеток условно считают занятой и проставляют в ней перевозки х_ij=0. При этом надо следить за тем, чтобы условно занятая клетка не образовывала с другими занятыми клетками замкнутых контуров.

В нашей задаче число  занятых клеток равно 6=(3+4-1).

 

Проверка допустимого  решения на оптимальность

Для поверки плана  на оптимальность:

1. для занятых клеток рассчитывают потенциалы клеток U_i и V_j, которые определяются по формуле: U_i+V_j=C_ij и записывается в специальный столбец и строку.

Первый опорный план:

Задав одной из неизвестных U_i или V_j произвольное значение, например U₁=0, находим все U_i и V_j. Так, U₁+V₁=C₁₁, откуда V₁=C₁₁-U₁, то есть V₁=7-0=7.

2. для свободных клеток рассчитывают величину: l_ij=C_ij - (U_i+V_j), которая указывает экономию или перерасход по сравнению с предыдущим планом при перемещении единицы груза в данную точку.

Сырье	Vj    Ui	Предприятия				Запасы
		1	2	3	4
		7	8	12	15
1	0	7   120	8  - 40	1   X13	2 + Х14	160
2	-3	4   Х21	5   10 +	9  - 130	8   X24	140
3	-9	9   Х31	2   Х32	3 + 60	6 - 110	170
Потребность		120	50	190	110	470

Таблица 2

Если при решении  задач на минимум все величины l_ij будут положительными или равными нулю, то план оптимален, если же имеются отрицательные величины, то план не оптимален, и его надо улучшать (Таблица 2).

Рассчитаем l_ij:

l₁₃=C₁₃-(U₁+V₃)=1-(0+12)=-11;

l₁₄=C₁₄-(U₁+V₄)=2-(0+15)=-13;

l₂₁=C₂₁-(U₂+V₁)=4-(-3+7)=0;

l₂₄=C₂₄-(U₂+V₄)=8-(-3+15)=-4;

l₃₁=C₃₁-(U₃+V₁)=9-(-9+7)=11;

l₃₂=C₃₂-(U₃+V₂)=2-(-9+8)=3.

Так как среди значений l_ij  есть отрицательные, то первый опорный план не оптимален.

Поиск решения  более близкого к оптимальному

Для улучшения плана  среди отрицательных значений l_ij берут клетку с наибольшим по абсолютной величине значением и строят из нее замкнутый контур. В данном примере можно взять клетку а₁₄, в которой значение  l₁₄=-13. Одна вершина контура должна лежать в этой свободной клетке, остальные – только в занятых. Контур, построенный из клетки а₁₄ (таблица 2) ,обозначен пунктиром. В вершине свободной клетки ставится знак “+”, в остальных клетках – знаки “+” и “-“ чередуются.

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

В исходной задаче: отрицательные  вершины контура расположены в клетках а_12, a₂₃ и а₃₄. В клетке а₁₂ объем перевозок равен 40 т, в а₂₃– 130т, в a₃₄ –110. Следовательно, меньший объем перевозок в клетках с отрицательными вершинами равен 40. Этот объем вычитаем из клеток а_12, a₂₃ и а₃₄, прибавляем к клеткам а₁₄,a₂₂ и а₃₃ и записываем в новую таблицу (Таблица 3):    

 

 

 

 

 

 

 

Сырье	Предприятия				Запасы
	1	2	3	4
1	7 120	8 X12	1 X13	2 40	160
2	4 X21	5 50	9 90	8 X24	140
3	9 X31	2 X32	3 100	6 70	170
Потребность	120	50	190	110	470

Таблица 3

Второй опорный план.                     

В таблице 3 вновь проверяем объем ограничений по строкам и столбцам. Суммарные издержки на перевозку при таком плане равны:

Z₂=7·120+2·40+5·50+9·90+3·100+6·70=2700 ден.ед. или на 520 меньше, чем в первом плане.

Отрицательное значение l_ij свободных клеток показывает экономию на перевозке единицы груза при перемещении его из занятой клетки в свободную. В нашей задаче значение a₁₄ свободной клетки l₁₄ = –13. Таким расчетом проверяется правильность проведенных расчетов в каждом варианте.

Составленный план опять  принимается за исходный, и вся вычислительная процедура повторяется снова:

Рассчитываем потенциалы для занятых клеток:

U₁=0;

V₁=C₁₁-U₁=7-0=7;

V₄=C₁₄-U₁=2-0=2;

U₃=C₃₄-V₄=6-2=4;

V₃=C₃₃-U₃=3-4=-1;

U₂=C₂₃-V₃=9+1=10;

V₂=C₂₂-U₂=5-10=-5.

 

 

 

Сырье	Vj    Ui	Предприятия				Запасы
		1	2	3	4
		7	-5	-1	2
1	0	7 - 120	8   X12	1   X13	2  + 40	160
2	10	4 + Х21	5   50	9 90 -	8   X24	140
3	4	9   Х31	2   Х32	3 + 100	6 - 70	170
Потребность		120	50	190	110	470

Таблица 4

Затем проверяем план на оптимальность путем определения l_ij для свободных клеток (Таблица 4):

          l₁₂=C₁₂-(U₁+V₂ )=8-(0-5)=13;

          l₁₃=C₁₃-(U₁+V₃ )=1-(0-1)=2;

          l₂₁=C₂₁-(U₂+V₁)=4-(10+7)=-13;

          l₂₄=C₂₄-(U₂+V₄)=8-(10+2)=-4;

          l₃₁=C₃₁-(U₃+V₁)=9-(4+7)=-2;

          l₃₂=C₃₂-(U₃+V₂)=2-(4-5)=3.

Так как среди значений l_ij  есть отрицательные, то второй опорный план не оптимален.

Для улучшения плана среди отрицательных значений l_ij берем клетку с наибольшим по абсолютной величине значением и строим из нее замкнутый контур. Возьмем клетку а₂₁, в которой значения l₂₁ =-13. Контур, построенный из клетки а₂₁ (таблица 4), обозначим пунктиром. В вершине свободной клетки поставим знак “+”, в остальных клетках – знаки “+” и ”- ” чередуются.

В исходной задаче: отрицательные  вершины контура расположены в клетках а₁₁ и а₂₃ и a₃₄. В клетке а₁₁ объем перевозок равен 120 т, в а₂₃– 90т, в a₃₄-70т. Следовательно, меньший объем перевозок в клетках с отрицательными вершинами равен 70. Этот объем вычитаем из клеток а₁₁, a₂₃,  a₃₄ и прибавляем к клеткам а₁₄,a₂₁,a_33, затем записываем в новую таблицу (Таблица 5):

Сырье	Предприятия				Запасы
	1	2	3	4
1	7 50	8 X12	1 X13	2 110	160
2	4 70	5 50	9 20	8 X24	140
3	9 X31	2 X32	3 170	6 X34	170
Потребность	120	50	190	110	470

Таблица 5

Третий  опорный план.                     

В таблице 5 вновь проверяем  объем ограничений по строкам  и столбцам. Суммарные издержки на перевозку при таком плане равны:

Z₃=7·50+2·110+4·70+5·50+9·20+3·170=1790 или на 1430 меньше, чем в первом плане.

Составленный план опять принимаем  за исходный, и всю вычислительную процедуру повторяем  снова:

 Рассчитываем потенциалы для занятых клеток: 

U₁=0;

V₁=C₁₁-U₁=7-0=7;

V₄=C₁₄-U₁=2-0=2;

U₂=C₂₁-V₁=4-7=-3;

V₂=C₂₂-U₂=5+3=8;

V₃=C₂₃-U₂=9+3=12;

U₃=C₃₃-V₃=3-12=-9.

 

 

 

 

 

 

Сырье	Vj    Ui	Предприятия				Запасы
		1	2	3	4
		7	8	12	2
1	0	7 - 50	8   X12	1  + X13	2   110	160
2	-3	4 + 70	5   50	9 - 20	8   X24	140
3	-9	9   Х31	2   Х32	3   170	6   X34	170
Потребность		120	50	190	110	470

Таблица 6

Затем проверяем план на оптимальность путем определения l_ij для свободных клеток (Таблица 6):

l₁₂=C₁₂-(U₁+V₂ )=8-(0+8)=0;

l₁₃=C₁₃-(U₁+V₃ )=1-(0+12)=-11;

l₂₄=C₂₄-(U₂+V₄)=8-(-3+2)=9;

l₃₁=C₃₁-(U₃+V₁)=9-(-9+7)=11;

l₃₂=C₃₂-(U₃+V₂)=2-(-9+8)=3;

l₃₄=C₃₄-(U₃+V₄)=6-(-9+2)=13.

Так как среди значений l_ij  есть отрицательные, то третий опорный план не оптимален.

Для улучшения плана  среди отрицательных значений l_ij берем клетку с наибольшим по абсолютной величине значением и строим из нее замкнутый контур. Возьмем клетку а₁₃, в которой значения l₁₃ = -11. Контур, построенный из клетки а₁₃ в таблице 6, обозначим пунктиром. В вершине свободной клетки поставим знак “+”, в остальных клетках – знаки “+” и "-” чередуются.