Величина перерахунку

₀= min {з всіх мінусових кліток}

5. Внаслідок перерозподілу (₀ отриманий новий опорний план, який знову перевіряємо на оптимальність.

Приклад. Транспортна компанія займається перевезенням зерна спеціальними зерновозами від трьох елеваторів до чотирьох млинів. У таблиці 5 показані можливості відвантаження зерна (пропозиції) елеваторам (в зерновозах) і потреби (попит) млинів (також в зерновозах), а також вартість перевезення зерна одним зерновозом від елеваторів до млинів. Вартість перевезень приведена в сотнях грош.од.

Таблиця 5

		Млини				Пропозиції
		1	2	3	4
Елеватори	1	10	2	20	11	15
	2	12	7	9	20	25
	3	4	14	16	18	10
Попит		5	15	15	15

Потрібно визначити структуру перевезень між елеваторами і млинами з мінімальною вартістю.

Розв’язання. Зазначимо, що дана задача є закритою (сумарна пропозиція рівна сумарному попиту), тому можна приступати до розв’язання.

Початковий опорний розв’язок знайдемо методом північно-західного кута

Таблиця 6

	1	2	3	4	Проп..
1	5 10	10 2	20	11	25
2	12	5 7	15 9	5 20	25
3	4	14	16	10 18	10
попит	5	15	15	15	60=60

Тепер скористаємося методом потенціалів, для перевірки оптимальності отриманого опорного розв’язку.

Визначимо потенціали стовпців (споживачів) і рядків (постачальників). Маємо 6 рівнянь, відповідних шести базисним змінним, з 7 невідомими (потенціалами).

Базисні змінні	Рівняння відносно потенціалів
Х11 Х12 Х22 Х23 Х24 Х34	u1+v1=10 u1+v2=2 u2+v2=7 u2+v3=9 u2+v4=20 u3+v4=18

Поклавши значення u₁=0, послідовно обчислюється значення інших потенціалів: u₂=5, u₃=3, v₁=10, v₂=2, v₃=4, v₄=15.

Далі використовуючи обчислені значення потенціалів, для кожної небазисної змінної (вільної клітки) обчислимо величини u_i+ v_j- c_ij

Небазисні змінні	Значення ui+ vj- cij
Х13 Х14 Х21 Х31 Х32 Х33	u1+v3-с13 = 0+4-20=-16 u1+v4-с14 = 0+15-11= 4 u2+v1-с24 = 5+10-12=3 u3+v1-с31 = 3+10-4=9 u3+v2-с32 = 3+2-14 =-9 u3+v3-с33 = 3+4-16 =-9

Описані обчислення звичайно виконуються безпосередньо в транспортній таблиці (таблиця 7). Обчислення в транспортній таблиці починаються з привласнення потенціалу u₁ нульового значення: u₁=0. Затем обчислюють v-потенціали для всіх стовпців, що мають базисні змінні в першому рядку. Далі на основі рівняння для потенціалів, відповідному змінній х₂₂, обчислюється величина потенціалу u₂. Знаючи значення потенціалу u₂, обчислюємо потенціали v₃ і v₄, що дозволяє знайти потенціал u₃. Оскільки всі потенціали визначені, далі обчислюються величини u_i+ v_j - c_ij для кожної небазисної змінної і записуються в лівому нижньому кутку клітинок транспортної таблиці

Таблиця 7

	v1=10	v2=2	v3=4	v4=15	Предл.
u1=0	5 10	10 2	-16 20	4 11	25
u2=5	3 12	5 7	15 9	5 20	25
u3=3	9 4	-9 14	-9 16	10 18	10
попит	5	15	15	15	60=60

Оскільки серед оцінок небазисних змінних є позитивні, то даний опорний план не оптимальний. Тому треба перейти до нового опорного розв’язку.

Змінною, що вводиться в базис буде х₃₁, оскільки вона має найбільшу позитивну оцінку. Для того щоб знайти змінну, що виключається з базису спочатку побудуємо замкнений цикл, який починається і закінчується з клітки, відповідної змінної, що вводиться в базис.

Цикл складається з послідовності горизонтальних і вертикальних відрізків (але не діагональних), що з'єднують осередки, відповідні поточним базисним змінним, і осередок, відповідний змінній, що вводиться. Для будь-якої змінної, що вводиться в базис можна побудувати тільки один замкнений цикл. У таблиці 8 показаний цикл для змінної х₃₁.

Таблиця 8

	v1=10	v2=2	v3=4	v4=15	Проп..
u1=0	5 10	10 2	-16 20	4 11	25
u2=5	3 12	5 7	15 9	5 20	25
u3=3	9 4	-9 14	-9 16	10 18	10
попит	5	15	15	15	60=60

Тепер знайдемо величину перерахунку вантажу:

=min {5, 5, 10}=5.

І перерозподіливши вантаж по побудованому циклу (в осередки зі знаком «плюс» додамо величину , з осередків зі знаком «мінус» - віднімемо) отримаємо новий опорний план, нова вартість якого буде менше на величину

(u₃+v₁-с₃₁)*5=9*5=45.

Маючи новий базисний розв’язок, потрібно повторити обчислення потенціалів, як показано в таблиці 9.

Таблиця 9

	v1=1	v2=2	v3=4	v4=15	Проп..
u1=0	-9 10	15 2	-16 20	4 11	25
u2=5	-6 12	0 7	15 9	10 20	25
u3=3	5 4	-9 14	-9 16	5 18	10
попит	5	15	15	15	60=60

Новою змінною, що вводиться в базис буде х₁₄. Замкнений цикл, відповідний цій змінній, дозволяє знайти її значення і змінну х₂₄, що виключається з базису.

Новий розв’язок (таблиця 10) є оптимальним, оскільки значення величин u_i+ v_j- c_ij для всіх небазисних змінних негативні.

Таблиця 10

	v1=-3	v2=2	v3=4	v4=11	Проп..
u1=0	-13 10	5 2	-16 20	10 11	25
u2=5	-10 12	10 7	15 9	-4 20	25
u3=7	5 4	-5 14	-5 16	5 18	10
попит	5	15	15	15	60=60

Отриманий розв’язок, в термінах початкової задачі перевезення зерна від елеваторів до млинів, має наступне значення.

Від элеватора	До млина	Кількість зерновозів
1 1 2 2 3 3	2 4 2 3 1 4	5 10 10 15 5 5
Мінімальна вартість всіх перевезень рівна 435 грош. од.