Спосіб подвійних позначок

Цей спосіб, крім значень , використовує ще й позначення таблиці, яке виконують у такій послідовності: спочатку позначають клітину з мінімальним значенням у кожному рядку таблиці, а потім у кожній колонці.

Результатом такого позначення є три підмножини клітин: з подвійною позначкою, однією та без позначок.

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

Базисний план за цим способом для наведеного прикладу такий:

І			20	vv
ІІ	v	40	vv

Етап II. Знаходження оптимального розв’язку.

3.4.4. Аналіз плану на оптимальність

Для проведення аналізу знайденого плану на оптимальність треба знайти значення потенціалів та . З цією метою складають систему рівнянь потенціалів для всіх :

.

Однак слід зауважити, що до складання системи рівнянь потенціалів треба перевірити знайдений план на виродження і якщо виявиться виродження, треба ввести фіктивні базисні змінні.

Для знаходження значень змінних хоча б одного допустимого розв’язку системи необхідно одну із змінних чи взяти будь-якою константою, найпростіше – нульовою, у такому разі система матиме один розв’язок.

Значення потенціалів та означають наскільки доцільно закріплювати ресурси саме за цією точкою. За знайденими значеннями потенціалів та обчислюють значення для змінних . Для цього складають рівняння потенціалів (для ),а потім за допомогою безпосередньої підстановки в ці рівняння значень та знаходять значення . Потім виконують аналіз на оптимальність .

Розглянемо приклад, коли перший базисний розв’язок знайдено діагональним способом. Складемо рівняння потенціалів для :

Система не вироджена. Тому для знаходження одного з її розв’язків один з потенціалів зрівнюємо з константою, наприклад, . Тоді матимемо такий розв’язок системи:

.

Підставимо знайдені значення та у рівняння потенціалів для змінних та визначимо , потім порівняємо їх з відповідними значеннями :

Проаналізувавши величини та і зробимо висновок, що для умова оптимальності не виконується.