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

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

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

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

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

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

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

aі	bj
v1	v2	v3	v4
	u1	^2	^3	65^2	^4
	u2	^2	60^4	^6	20^5
	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
	^5	^1	^2	^3
	^6	^3	^7	^1
	^4	^5	^3	^2
	^2	^4	^6	^8

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

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

aі	bj
	^5	300^1	^2	^3
	^6	^3	^7	200^1
	^4	^5	300^3	200^2
	230^2	120^4	350^6	^8

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

, , ,

, , .

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

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

aі	bj
v 1= –1	v 2=1	v 3=3	v 4=2
	u 1=0	^5	300^1	^2	^3
	u 2= –1	^6	^3	^7	200^1
	u 3=0	^4	^5	300^3	200^2
	u 4=3	230^2	120^4	350^6	^8

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

або

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

Дата добавления: 2014-12-25