Тема лекції: Двоїста задача лінійного програмування

Мета: ознайомити студентів з методами розв’язання двоїстих задач лінійного програмування, показати взаємозв’язок прямої та двоїстої задач.

План лекції

1. Математичні моделі двоїстих задач.

2. Основні теореми теорії двоістості.

3. Взаємозв’язок розв’язків прямої та двоїстої задач.

 

Література:

1. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

2. Іванюта І.Д. Практикум з математичного програмування: Навчальний посібник/ І.Д. Іванюта, В.І. Рибалка, І.А. Рудоміра – Дусятська. – К.: «Слово», 2008. – 296 с.

3. Кучма М.І. Математичне програмування: приклади і задачі: Навчальний посібник/ М.І. Кучма. - Львів: «Новий Світ - 2000», 2006. – 344 с.

4. А. Черемис, Р. Юринець, О. Мищишин. Методи оптимізації в економіці. Навчальний посібник. – К.: Центр навчальної літератури, 2006. – 152 с.

Математичні моделі двоїстих задач.

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

Початкова задача називається прямою задачею ЛП. Ці дві задачі тісно пов’язані між собою і утворюють єдину пару двоїстих задач.

Якщо пряма задача ЛП має вигляд:

Z=∑c_ix_i →max (1)

за умов

∑a_ijx_j ≤b_i, (i=1,2…..m) (2)

 

x_j ≥0 (j=1,2…..n) (3)

то двоїста задача записується так:

F=∑b_iy_i →min (1*)

за умов

∑a_ijy_i≥ c_j, (j=1,2…..n) (2*)

 

y_i≥0 (i=1,2…..m) (3*)

В матричному вигляді їх можна представити таким чином:

Пряма задача

, x_j ≥0 (j=1,2…..n)

де А – матриця системи обмежень задачі розміром m x n;

В – вектор стовпець;

С – вектор строка;

АХ≤В;

Z →max.

 

Двоїста задача

tr = , y_i ≥0 (i=1,2…..m)

де trA – транспонована матриця А;

trС – транспонований вектор С;

trB - транспонований вектор В;

AY ≥trC;

F →min.

У несиметричних парах двоїстих задач обмеження прямої задачі можуть бути записані як рівняння (у канонічному вигляді), а двоїстої – лише як нерівності. Якщо у цільовій функції двоїстої задачі вимагається знайти мінімум, то система обмежень матиме знак «≥», якщо максимум, то знак «≥».

Моделі несиметричних пар цих задач можна зобразити у вигляді:

Пряма задача	Двоїста задача
Z=∑cixi →max/min за умов ∑aijxj =bi, (i=1,2…..m)   xj ≥0 (j=1,2…..n)	F=∑biyi →min/max за умов ∑aijyi≥/≤ cj, (j=1,2…..n)   yi є(-∞,∞) (i=1,2…..m)

Математична модель прямої задачі мішаної пари двоїстих задач містить обмеження, записані як рівняння, так і нерівності, причому знаків різних, за виглядом. Для складання двоїстої задачі необхідно привести всі нерівності системи обмежень прямої задачі до одного вигляду: якщо пряма задача на максимум, то всі нерівності обмежень приводимо до вигляду «≤», якщо на мінімум до вигляду «≥». Нерівності, для яких дані вимоги не виконуються, домножимо на (-1).

2. Основні теореми двоїстості.

Розглянемо пару даоїстих задач, утворену канонічною задачею ЛП і двоїстої до неї:

Пряма:

Z=∑c_ix_i →max/min

за умов

∑a_ijx_j =b_i, (i=1,2…..m)

 

x_j ≥0 (j=1,2…..n)

Двоїста:

F=∑b_iy_i →min/max

за умов

∑a_ijy_i≥/≤ c_j, (j=1,2…..n)

 

y_i є(-∞,∞) (i=1,2…..m)

Між прямою і двоїстою задачами ЛП існує тісний взаємозв’язок, який видно з наведених далі лем та теорем.

Лема 1. Якщо Х – деякий план прямої задачі, Y – довільний план двоїстої задачі, то значення цільової функції прямої задачі при плані Х не перевищує значення цільової функції двоїстої задачі при плані Y, тобто

Z(X)≤F(Y)

Лема 2. Якщо Z(X*)=F(Y*), та X* - оптимальний план прямої задачі, то Y* - оптимальний план двоїстої задачі.

Теорема 1. (перша теорема двоїстості). Якщо одна із пар двоїстих задач має оптимальний план, то і друга задача має оптимальний план і значення цільової функції при їх оптимальних планах рівні між собою, тобто Z(X*)=F(Y*).

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

Теорема 2. (друга теорема двоїстості). Для того щоб плани Х* і Y* відповідно до задач (1) – (3) і (1*) – (3*) були оптимальними планами цих задач, необхідно і достатньо, щоб для кожного j (j=1,2…..n) виконувалась рівність:

(a_1j(y₁)* + a_2j(y₂)* + ……. + a_mj(y_m)* - c_j)(x_j)* = 0

Економічну інтерпретацію двоїстої задачі розглянемо на прикладі задачі про оптимальне використання ресурсів, математична модель якої має вигляд:

Z=∑c_ix_i →max

за умов

∑a_ijx_j =b_i, (i=1,2…..m)

 

x_j ≥0 (j=1,2…..n)

Двоїста задача до неї буде така:

F=∑b_iy_i →min

за умов

∑a_ijy_i≥ c_j, (j=1,2…..n)

y_i ≥0 i=1,2…..m

Приклад. Підприємство виготовляє три види продукції А,В,С.

 

Дані задачі приведені у таблиці:

Види сировини	Норми витрат сировини (кг)	Запаси сировини
А	В	С
S1
S2
S3
Ціна від реалізації 1-ї одиниці продукції

Знайти такий план випуску продукції, щоб прибуток від їх реалізації був максимальним.