9.2.1.2 Задача на мінімум

Нехай – оптимальний розв’язок, значить відповідний вектор відносних оцінок небазисних змінних

.

Нехай коефіцієнт ЦФ при небазисній змінній прийняв значення

тоді її нова відносна оцінка буде такою:

Розв’язок залишиться оптимальним, якщо або . Отже, для небазисної змінної діапазон стійкості в якому може змінюватися її коефіцієнт ЦФ:

– відносний діапазон: ,

– абсолютний діапазон: ,

де - відносна оцінка змінної в оптимальному розв’язку

50. Постоптимальный анализ. Изменение коэффициентов матрицы ограничений (вывод соответствующих соотношений) Аналіз зміни коефіцієнтів матриці обмежень

Коефіцієнти , як правило, відомі з більшою достовірністю, ніж компоненти вектора ЦФ або вектора обмежень , оскільки зазвичай вони задаються особливостями технологічного процесу і не залежать так сильно від ринкових змін, як ціни або об'єми ресурсів.

Розглядатимемо зміни коефіцієнтів, відповідних тільки небазисним змінним, оскільки зміна значень коефіцієнтів при базисних змінних приводить до зміни базисної матриці , і проаналізувати це дуже складно.

Нехай – оптимальний розв’язок, – відповідний вектор відносних оцінок небазисних змінних, – цінності ресурсів, – небазисна змінна

Спочатку розглянемо випадок, коли змінюється тільки одна компонента одного з небазисних векторів, а потім – випадок одночасної зміни усіх компонент небазисного вектора.

51. Условия, при которых неэффективный вид деятельности становится эффективным

52. Двойственный симплекс-метод

8.6 Двоїстий симплекс-метод

На кроці 1 симплекс-метода в процесі обчислення компонентів вектора

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

.

Таким чином, на будь-якій ітерації вектор оцінок виступає як міра зміни ЦФ щодо вектора обмежень . Якщо ми визначимо двоїсті змінні з рівняння для кожної ітерації симплекс - метода, то для поточних розв’язків задач (ПЗ і ДЗ) основна нерівність теорії двоїстості буде завжди виконуватись як рівність, але двоїсті змінні будуть недопустимими впродовж усіх ітерацій симплекс - метода до тих пір, поки не буде досягнутий оптимальний розв’язок.

Нехай задана ЗЛП в канонічній формі (пряма задача).

,	(1)
,	(2)
.	(3)

Якщо вектор двоїстих змінних позначити через , то задача, двоїста до задачі (1)-(3), має вигляд :

Критерій оптимальності задачі (1)-(3) такий:

,

де - вектор відносних оцінок небазисних змінних, - вектор оцінок обмежень.

Як і раніше по аналогії з вектором введемо вектор :

.

Тоді вектор відносних оцінок змінних: визначається так:

.

З урахуванням цього критерій (умову) оптимальності задачі (1)-(3) можна записати так:

,

.

(4)

Умова оптимальності (4) розв’язку ПЗ є ні що інше, як умова допустимості вектора двоїстих змінних :

.

Таким чином, можна вважати, що в симплекс - методі ми, підтримуючи допустимість прямого розв’язку, прагнемо до допустимості двоїстого. Такий алгоритм називається прямим. Так само можна почати з допустимого двоїстого розв’язку і прагнути до допустимості прямого. Такий алгоритм називатимемо двоїстим симплекс - методом.

Нехай – деякий базисний розв’язок задачі (1) -(3), тоді відповідна пряма перетворена задача має вигляд:

	(5)
	(6)

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

Тобто передбачається, що для БР виконується умова оптимальності

,

але не виконується умова допустимості, тобто

.

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