2. Двоїсті злп та їх властивості. Теореми двоїстості. Двоїстий симплекс-метод.

Двоїсті ЗЛП та їх властивості

Нехай маємо задачу лінійного програмування:

(1)

(2)

(3)

Поряд з цією задачею розглянемо спряжену або двоїсту до неї задачу, яка полягає у відшукані:

Теорема 1: Якщо є допустимим розв’язком задачі (1)-(3), а є допустимим розв’язком задачі (4)-(5), то має місце нерівність:

Теорема 2: Якщо є допустимим розв’язком задачі (1)-(3), а є допустимим розв’язком задачі (4)-(5) і , то тоді є оптимальним розв’язком для задачі (1)-(3), а є оптимальним розв’язком для задачі (4)-(5).

Теорема 3: Якщо цільова функція для задачі (1)-(3) необмежена зверху на множині допустимих розв’язків цієї задачі (що визначається обмеженнями (2)-(3)), то множина допустимих розв’язків задачі (4)-(5) є порожньою множиною(система (5) несумісна). Навпаки, якщо задачі (4)-(5) необмежена знизу на множині допустимих розв’язків цієї задачі ((4)-(5)), то множина допустимих розв’язків задачі (1)-(3) є порожньою множиною (система (2)-(3) несумісна).

Теореми двоїстості.

Перша теорема двоїстості в лінійному програмуванні

Теорема: Якщо одна з двоїстих задач (1)-(3) та (4)-(5) лінійного програмування має оптимальний розв’язок, то й друга задача має оптимальний розв’язок і оптимальні значення цільових функцій цих задач рівні між собою.

Доведення.

Припустимо, що (1)-(3) має оптимальний розв’язок, вона має базисний оптимальний розв’язок, який можна отримати симплекс-методом.

Позначимо його , причому всі є лінійно незалежними.

(7)

Розглянемо далі систему рівнянь:

(8)

Як відомо , в силу лінійної незалежності векторів детермінант системи (8) відмінний від нуля, тоді ця система має єдиний розв’язок, який позначимо через .

Тобто виконується рівність (8), де замість ставимо .

Переконаємось , що задовольняє і обмеженостей системи (5).

Для цього розглянемо добуток

Отже => задовольняє m+1 нерівностей системи (5).

Згідно з (8)

Тому що задовольняє (2).

Отже, . Згідно з теоремою (2) це є оптимальним розв’язком задачі (4)-(5).

Навпаки, коли задача(4)-(5) має оптимальний розв’язок, то й задача (1)-(3) теж має оптимальний розв’язок.

(4)-(5) еквівалентно:

(9)

(10)

(11)

Оскільки задача (4)-(5) має оптимальний розв’язок, то (9)-(11) теж має оптимальний розв’язок . Тому має оптимальний розв’язок задача при обмеженнях (10)-(11).

За доведеним вище тоді має оптимальний розв’язок і двоїста до задачі при (10)-(11) задача, яка полягає в наступному.

Ця задача має такий вигляд:

.

Тоді має оптимальний розв’язок і задача відшукання:

.

Тобто має оптимальний розв’язок задача (1)-(3), що й потрібно було довести.

А вище доводилося, що оптимальні значення рівні між собою.

Теорему доведено.

Друга теорема двоїстості в лінійному програмуванні

Теорема: Для того, щоб допустимий розв’язок задачі (1)-(3) та допустимий розв’язок задачі (4)-(5) були оптимальними розв’язками цієї пари двоїстих задач л.п. необхідно і досить, щоб виконувалися такі рівності:

(12)

Або

, (12)

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

Майже базисний допустимий розв’язок задачі лінійного програмування

Нехай маємо задачу (1)-(3) лінійного програмування.

Означення. Вектор , який задовольняє обмеженням (2) називається псевдо планом задачі (1)-(3), якщо вектори умов, які відповідають його ненульовим координатам утворюють лінійно незалежну систему.

Двоїстий симплекс метод та його властивості

Нехай маємо деякий псевдо план зад (1)-(3). Припустимо х⁰. Побудуємо відповідну йому таблицю що

Баз.	С баз.	Х баз	Cm+1	Cs	Сn
			Am+1	As	An
A1	C1	X1^0	Xm+1	Xs,1	Xn,1
Ar	Cr	Xr^0	Xm+1,r	Xs,r	Xn,r
Am	Cm	Xm^0	Xm+1,m	Xn,m	Xn,m
		Z^0

і будемо вважати що всі , а ті які відповідають базисним векторам = 0.

Теорема1. Якщо елементи x_m+1,r, …, x_s,r , …, x_n 0 то задача немає допустимого розв’язку. Тобто нема вектора х=(х₁,…,х_m) 0.

Припустимо, що , і коефіцієнт у рядку усі > 0. То за доведеною вище теоремою задача (1)-(3) допустимих розв’язків немає. Тоді рядок, який відповідає елементу є розв’язуючим рядком.

Припустимо, що серед чисел . Будемо вибирати такий розв’язуючий елемент у цьому рядку, щоб після кроку симплекс методу з цим розв’язуючим елементом всі . З цією метою в ролі розв’язуючого елемента брати такий який < 0. В ролі розв’язуючого елемента можна вибрати , лише тоді коли буде найбільшим серед відношень .

З цієї нерівності слідує що у випадку коли всі псевдоплани задачі (1)(3) не вироджені (всі базисні координати ) в результаті цього методу будемо переходити до нових базисів (нових псевдопланів) і оскільки кількість таких базисів не перевищує числа комбінацій то метод буде скінчений. Це означає що у випадку невиродженості ми або знайдемо оптимальний розв’язок (1)(3), або виявимо що система обмежень (2)(3) є несумісною.

Білет 14