Метод потенціалів.

Одні із знайдених початкових планів кращі (ближчі до оптимального), інші – менш ефективні. Найзручнішим для перевірки є критерій оптимальності, названий методом потенціалів, який ґрунтується на такій теоремі:

Щоб опорний план був оптимальним, необхідно і достатньо, щоб виконувались умови:

– для базисних клітинок ;

– для вільних клітинок ,

де – потенціали і відповідно (, ).

Розглянемо застосування цього методу на прикладі11. Потенціали для постачальників – , для споживачів – .

aі	bj	45	60	80	65
		v1	v2	v3	v4
65	u1	2	3	65 2	4
80	u2	2	60 4	6	20 5
105	u3	45 1	5	15 4	45 5

Обчислимо кількість базисних невідомих , маємо 6 заповнених клітинок, тому опорний план не вироджений. Запишемо рівняння для заповнених (базисних) клітинок

Нехай , тоді з системи рівнянь можемо знайти інші потенціали , , , , , .

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

0–1<2 виконано

0+2<3 виконано

0+3<4 виконано

2–1<2 виконано

2+2<6 виконано

2+2<5 виконано

Всі умови виконуються, план оптимальний.

Обчислимо вартість перевезення

Приклад 12.

aі	bj	230	420	650	400
300		5	1	2	3
200		6	3	7	1
500		4	5	3	2
700		2	4	6	8

Розв’язання.

Заповнимо таблицю методом мінімальної вартості (див. приклад 11).

aі	bj	230	420	650	400
300		5	300 1	2	3
200		6	3	7	200 1
500		4	5	300 3	200 2
700		230 2	120 4	350 6	8

Перевіримо цей план на оптимальність за допомогою методу потенціалів. Запишемо рівняння для заповнених клітинок

, ,,

, ,.

Нехай , обчислимо інші потенціалиu₂=–1, u₃=0, u₄=3, v₁=–1, v₂=1, v₃=3, v₄=2.

Результати занесемо в таблицю:

aі	bj	230	420	650	400
		v1= –1	v2=1	v3=3	v4=2
300	u1=0	5	300 1	2	3
200	u2= –1	6	3	7	200 1
500	u3=0	4	5	300 3	200 2
700	u4=3	230 2	120 4	350 6	8

Перевіримо виконання нерівностей:

або

Умова оптимальності не виконується, потрібно поліпшити опорний план. Поліпшити план можна за допомогою циклу перерахунку.

Цикл перерахунку

Цикл транспортної таблиці – це замкнена ламана, що задовольняє умовам:

1. ламана починається і закінчується у вільній клітинці, в якій не виконана умова оптимальності,¹

2. ланки ламаної повертають² тільки під прямим кутом,

3. поворот може бути тільки у базисній клітинці

Приклади циклів

Перерахунок по циклу:

1. вільній клітині циклу присвоюють знак “+”;

2. при повороті знаки чергуються;

3. серед клітин зі знаком “–” обирають найменше значення поставки ;

4. з поставок в клітинах зі знаком “–” віднімають , а до поставок в клітинах зі знаком “+” додають.

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

Намалюємо цикл перерахунку для приклада 12.

aі	bj	230	420	650	400
300		5	300 – 1	+ 2	3
200		6	3	7	200 1
500		4	5	300 3	200 2
700		230 2	120 + 4	350 – 6	8

З клітинок зі знаком мінус віднімаємо найменше число , а в клітинки зі знаком плюс його додаємо:

aі	bj	230	420	650	400
300		5	1	300 2	3
200		6	3	7	200 1
500		4	5	300 3	200 2
700		230 2	420 4	50 6	8

Отриманий план перевіряємо на оптимальність за методом потенціалів.

aі	bj		230	420	650	400
300			5	1	300 2	3
200			6	3	7	200 1
500			4	5	300 3	200 2
700			230 2	420 4	50 6	8

Звідки для знайдемо,,,,,,.

Умови оптимальності виконані, план оптимальний.

Обчислимо вартість перевезення.

Відповідь: ,.

1 Якщо таких клітинок декілька, обирають з найбільшою різницею .

2 Напрямок ланок неважливий.

54