2.4. Двоїстий та модифікований симплекс-метод. Блочні задачі лп Пряма та двоїста задачі лінійного проґрамування

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

, .

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

, .

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

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

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

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

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

Змінні

двоїстої

задачі

Приклад 6).

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.

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

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

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-те обмеження двоїстої задачі перетворюється при в строгу нерівність, , то та є оптимальними розв’язками прямої та двоїстої задач.

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

,

.

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