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

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

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

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

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)

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

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

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

АХ≤В;

Z →max.

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

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

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

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

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

AY ≥trC;

F →min.

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

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

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

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

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

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