Тема 1.Двоїстий та модифікований симплекс-метод. Блочні задачі лп

1. Пряма та двоїста задачі лінійного проґрамування.

2. Зв’язок між розв’язками прямої та двоїстої задач.

3. Отримання оптимального розв’язку двоїстої задачі за допомогою симплекс-методу.

4. Економічна інтерпретація задач лінійного проґрамування.

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

6. Модифікований симплекс-метод.

7. Блочні задачі лінійного проґрамування. Метод Данціґа-Вулфа.

1. Пряма та двоїста задачі лінійного проґрамування

Для прямої задачі ЛП справедливі наступні співвідношення:

, .

Двоїста відносно прямої задача ЛП в канонічній формі має вигляд:

, .

Відповідно в матричній формі пряма задача зображається як

, а двоїста – , або .

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

Змінні прямої задачі

x1	x2	…	xj	…	xn
c1	c2	…	cj	…	cn
a11	a12	…	a1j	…	a1n	b1	y1
a21	a22	…	a2j	…	a2n	b2	y2
…	…	…	…	…	…	…	…
am1	am2	…	amj	…	amn	bm	ym

Змінні

двоїстої

задачі

Приклад.

Q= 5x₁+12x₂ +4x₃ Max,

x₁+ 2x₂+ х₃ < =10

2x₁ - x₂ + 3х₃ = 8

x₁ >=0, x₂ >=0, x₃ >=0.

Приводимо задачу до канонічної форми:

Q= 5x₁+12x₂ +4x₃ +0x₄ Max,

x₁+ 2x₂+ х₃ + х₄ =10  y₁

2x₁ - x₂ + 3х₃ +0x₄ = 8  y₂

x₁ >=0, x₂ >=0, x₃ >=0, x₄ >=0

Умова двоїстої задачі:

G= 10y₁+ 8y₂  Min,

y₁+ 2y₂ > = 5

2y₁- y₂ > = 12

y₁+ 3y₂ > = 4

y₁+ 0y₂ > = 0,

y₁, y₂ >< 0.

Двоїста задача до двоїстої буде первісною прямою задачею, тобто, якщо A — пряма задача, D{A} — двоїста до A, то A=D{D{A}}. Покажемо, що це насправді так.

Тепер переходимо до двоїстої задачі:



2. Зв’язок між розв’язками прямої та двоїстої задач

Зв’язок між розв’язками прямої та двоїстої задач встановлюється за допомогою двох теорем двоїстості. Для їх доведення використаємо наступну лему.

Лема.

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

Доведення.

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

Нехай для деяких припустимих . Припустимо, що — не оптимальний розв’язок. У такому випадку для оптимального розв’язку справедливе співвідношення , що суперечить вже доведеному вище твердженню. Припустимо, що — не оптимальний розв’язок. У такому випадку для оптимального розв’язку справедливе співвідношення , що також суперечить вже доведеному вище твердженню 

1-а теорема двоїстості.

Якщо одна з пари двоїстих задач має розв’язок, то й інша має розв’язок, і оптимальні значення функцій мети рівні між собою — . Якщо функція мети для однієї з задач не обмежена , двоїста до неї задача взагалі не має припустимих розв’язків.

Доведення.

Запишемо задачу ЛП в перетвореному вигляді:

,

, , де .

На останній ітерації — в останній симплекс-таблиці розв’язок є оптимальним, , тобто . Введемо позначення . Тоді , , і об’єднуючи ці обидва вирази , отримаємо .

Таким чином — припустимий розв’язок двоїстої задачі. Доведемо, що — оптимальний розв’язок двоїстої задачі: . Таким чином значення функції мети для двоїстої задачі для її припустимого розв’язку дорівнює значенню функції мети прямої задачі для її припустимого розв’язку . Згідно до леми це означає, що є оптимальним розв’язком двоїстої задачі.

Доведемо другу частину теореми.

Нехай відомо, що функція мети прямої задачі не обмежена згори на множині припустимих розв’язків. Припустимо, що двоїста задача при цьому має припустимі розв’язки і — один з них. У такому випадку внаслідок необмеженості функції мети прямої задачі знайдеться такий її розв’язок, для якого , що суперечить лемі 

Примітка.

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

Q= 2x₁-x₂  Max,

x₁- x₂ =1  y₁

-x₁+x₂ =1  y₂

x₁ >=0, x₂ >=0 Область припустимих розв’язків .

Умова двоїстої задачі:

G= y₁+ y₂  Min,

y₁ - y₂ > = 5

2y₁- y₂ > = 2

-y₁+ y₂ > = -1 Область припустимих розв’язків .

Теорема 2.

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

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

,

.

Ця теорема дає можливість за оптимальним розв’язком однієї з задач знайти оптимальний розв’язок двоїстої до неї.

Доведення.

Нехай для кожного , для якого , маємо . Тоді . Справді, ті складові, для яких , фактично рівні нулю, оскільки для них . Залишаються до розгляду лише ті складові, для яких , що доводить справедливість рівності. Після перегрупування суми отримаємо . Оскільки - припустимий розв’язок прямої задачі, то суми в дужках рівні відповідним значенням , тобто і згідно до леми ці розв’язки є оптимальними.

1. Нехай тепер навпаки, відомо, що , — оптимальні розв’язки прямої та двоїстої задач. Тоді за першою теоремою двоїстості . Оскільки — припустимий розв’язок задачі, то . Підставляючи ці вирази в рівність та перегруповуючи складові в лівій частині, отримаємо: . Якщо хоча б для одного j, для якого , було б , то попереднє співвідношення не виконувалося б. Тобто дійсно, для кожного j, для якого б виконувалося попередня строга нерівність, отримуємо , що й потрібно було довести 