> Ці завдання називають парою двоїстих завдань. Пара двоїстих завдань може бути економічно інтерпретована наступним чином. p> Пряме завдання: Скільки і якої продукції xj необхідно виробляти, щоб при заданих вартостях Cj і розмірах ресурсів bi максимізувати випуск продукції у вартісному вираженні?
Двоїста задача: Яка повинна бути ціна кожного ресурсу yi, щоб при заданих кількостях bi і вартостях Cj мінімізувати витрати?
2. Правила побудови двоїстої завдання
Виходячи з загального вигляду прямої та двоїстої задач можна встановити зв'язок між цими завданнями, що дозволяє для будь ЗЛП будувати двоїсту їй завдання.
Властивості двоїстих завдань (правила).
1. Число невідомих двоїстої задачі дорівнює числу обмежень прямої задачі. Число обмежень двоїстої задачі дорівнює числу невідомих прямої задачі.
2. Матриця коефіцієнтів двоїстої задачі є транспонованою матрицею коефіцієнтів прямої задачі.
. Коефіцієнти цільової функції двоїстої задачі є вільними членами обмежень прямої задачі.
. Вільні члени обмежень двоїстої задачі є коефіцієнтами цільової функції прямої задачі.
5.Якщо обмеження прямої задачі записані зі знаком менше або дорівнює (), то обмеження двоїстої завдання записуються зі знаком більше або дорівнює (). p>. Якщо обмеження прямої задачі задано у вигляді рівняння, то відповідне невідоме двоїстої завдання не обмежена знаком. p>. Якщо будь невідоме прямої задачі не обмежена знаком, то відповідне обмеження двоїстої завдання буде поставлено як рівності.
. Якщо цільова функція прямої задачі сформульована на максимум, то цільова функція двоїстої задачі буде сформульована на мінімум.
Існує багато різних комбінацій обмежень і цільової функції для запису вихідної задачі. Для спрощення завдання побудови двоїстої задачі запишемо пряму задачу в деякому стандартному вигляді прямої задачі. Цей вид припускає, що:
1) всі обмеження мають знак;
2) цільова функція сформульована на максимум;
) всі невідомі ненегативні.
Щоб записати пряму задачу в стандартному вигляді, необхідно:
1) нерівність зі знаком помножити на (-1);
) рівність замінити на дві нерівності протилежних знаків, одне з яких слід помножити на (-1);
) формулювання цільової функції змінюють заміною знаків коефіцієнтів на протилежні;
) якщо змінне xj не обмежена знаком, його можна представити у вигляді різниці двох невід'ємних змінних.
Приклад. Скласти двоїсту задачу до вихідної.
.
Рішення. 1) Стандартний вигляд прямої задачі.
В В В В
) Двоїста задача:
В
Завдання можна записати у вигляді, відповідному вихідної прямій задачі, якщо замінити: а) - не обмежена знаком,
б) два останні обмеження відповідають рівності.
.
3. Основні теореми двоїстості та їх економічний зміст
Теорема 1. Двоїста задача до двоїстої є пряме завдання.
Доказ: Нехай маємо пару двоїстих завдань у матричному вигляді.
Ах АТy C
F = CTx Z =
x 0 y 0
Побудуємо до двоїстої завданню двоїсту:
) запишемо у стандартному вигляді-АТy-C
Z = -
2)-Ах Ах
F = - CTx F = CTx
Що і потрібно було довести.
Теорема 2. Значення функції F, відповідає будь-якій допустимого рішення прямої задачі, що не більше значення функції Z, відповідного будь-якого допустимого рішення двоїстої завдання.
Доказ: Нехай X і Y відповідно довільні допустимі рішення прямої і двоїстої задач. Отже,
1) Ах і Y YТ, YTAX YTb = bTY = Z.
) ATY C і X 0 XТ, XTATY XTC = CTX = F.
) вираз XTATY - скалярна величина (число) вона дорівнює своєї
транспозиції, тобто XTATY = YTAX. Отже, маємо,
F XTATY = YTAX Z F Z. Що і потрібно було довести. p> Наслідки: 1) якщо в прямій задачі допустима область і не порожня, а цільова функція не обмежена зверху, те в двоїстої завдання допустима область порожня;
) якщо в двоїстої завданню допустима область не порожня, а цільова функція не обмежена знизу, то у прямої задачі допустима область порожня. p> Теорема 3. Якщо пряма задача має кінцеве оптимальне рішення F = F max , то двоїста задача має кінцеве оптимальне рішення Z = Z min . При цьому F max = Z
