Розв’язання. 1 Перевірка збалансованості задачі:

1 Перевірка збалансованості задачі:

Задача є незбалансованою, тобто до неї необхідно додати фіктивного виробника а₄=800-600=200 з нульовою вартістю перевезень.

Методом північно-західного кута можна побудувати початковий опорний план. В комірці х₁₁ одночасно вичерпуються можливості постачальника та споживача, тому в комірку х₂₁ розміщується базисний нуль і «викреслюється» перший стовпчик.

Х1
	bj ai

2 Після заповнення таблиці перевіряється кількість базисних комірок. m+n‑1=4+4‑1=7, тобто план є базисним.

За таких обсягів перевезень загальна вартість складає: F(X₁) = 100*1 +
+0*2 + 100*3 +100*4+200*7+100*12+200*0=3400 грошових одиниць.

3 За базисними комірками визначаються потенціали рядків і стовпчиків.

u₁+ v₁=1

u₂+ v₁=2

u₂+ v₂=3

u₂+ v₃=4

u₃+ v₃=7

u₃+ v₄=12

u₄+ v₄=0

Для визначення 8 невідомих із 7 рівнянь один з потенціалів покладається рівним 0. Нехай u₁=0, тоді:

u₁ =0 v₁=1

u₂ =1 v₂=2

u₃ =4 v₃=3

u₄ =-8 v₄=8

4 Отриманий план перевіряється на оптимальність, визначаються оцінки вільних комірок, наприклад:

S₁₂ = u₁+ v₂-c_ij=0+2-2=0.

Значення оцінок записуються в лівому нижньому кутку вільних комірок. Від’ємні значення можна не вказувати, достатньо вказати знак «-».

Х1		v1 =1	v2 =2	v3 =3	v4 =8
	bj ai
u1 =0		1
u2 =1
u3 =4
u4 =-8

Найбільшу оцінку має комірка (1;4), тому для неї необхідно побудувати цикл.

Починаючи з вільної комірки, в циклі проставляються по черзі знаки «+» та «-». Серед комірок, що мають знак «-», обирається значення, на яке відбудеться переміщення обсягів перевезень.

До комірок, що мають знак «+», додаються 100 одиниць продукції, а від комірок, що мають знак «-», вони віднімаються. Якщо декілька комірок мають можливість звільнитись, то звільняється лише одна з зайнятих комірок (та, що має найбільшу вартість перевезень продукції). Таким чином, здійснюється перехід до нового опорного плану.

Х2		v1 =1	v2 =2	v3 =3	v4 =1
	bj ai
u1 =0		0
u2 =1
u3 =4
u4 =-1

Обчислюються потенціали та визначаються оцінки вільних комірок, на основі чого робиться висновок, що Х₂ не є оптимальним планом, бо має позитивні оцінки вільних комірок. Будується цикл для комірки (3;2):

Х3		v1 =1	v2 =0	v3 =3	v4 =1
	bj ai
u1 =0		0
u2 =1
u3 =4
u4 =-1

Х₃ не є оптимальним планом, бо має позитивні оцінки вільних комірок. Будується цикл для комірки (3;1):

Х4		v1 =1	v2 =0	v3 =3	v4 =1
	bj ai
u1 =0		1
u2 =1
u3 =4
u4 =-1

Для комірки (4;3) будується цикл:

У результаті такого циклу відбувається переміщення базисного нуля.

Х5		v1 =-3	v2 =-2	v3 =1	v4 =1
	bj ai
u1 =0			- 2 - -
u2 =3		- 2 -		- 4 - 200
u3 =6
u4 =-1		-	-

Оскільки всі оцінки вільних комірок є від’ємними, то розв’язок є оптимальним:

min F(X)=F(X₅)= F(X₄)=2300

при .