Двоїсті задачі в симетричній формі

Пряма задача

(2.8)

, , (2.9)

. (2.10)

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

(2.11)

, , (2.12)

. (2.13)

Правило 1 (побудови взаємно-двоїстих задач у симетричній формі)

1. Кількість змінних однієї задачі дорівнює кількості нерівностей в обмеженнях іншої.

2. Коефіцієнти цільової функції однієї задачі дорівнюють правим частинам системи обмежень іншої.

3. Одна задача повинна бути на знаходження найбільшого (з нерівностями типу “≤“), а інша – найменшого (з нерівностями типу “≥“) значення цільової функції.

4. Матриця системи обмежень одної задачі повинна бути транспонованою матрицею системи обмежень іншої.

5. Всі змінні в обох задачах повинні бути невід’ємні.

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

· в усіх нерівностях системи обмежень вільні члени містяться у правій частині нерівності, члени з невідомими – в лівій;

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

Якщо побудувати двоїсту задачу до двоїстої, то отримаємо вихідну задачу. Тобто, будь - яку з цих задач можна вважати прямою, а тоді інша буде двоїстою до неї. Задачі (2.8) – (2.10) і (2.11) – (2.13) називають взаємно-двоїстими задачами в симетричній формі.

Приклад 1. Побудувати двоїсту задачу до задачі

(a)

(b)

(c)

Розв’язання. Спочатку надамо задачі стандартної форми запису (2.8) –(2.10). Для цього достатньо помножити обидві частини другої нерівності в системі обмежень (b) на (-1)

(d)

Шукану двоїсту задачу побудуємо як двоїсту до задачі (a), (d), (c). Обмеження прямої задачі (d) складаються з трьох нерівностей, отже, згідно з п.1 (правила 1), двоїста задача матиме три змінні Згідно з п. 2 коефіцієнти цільової функції двоїстої задачі дорівнюють вільним членам обмежень (d), а згідно з п. 3 – знаходиться найменше значення цільової функції

. (e)

Згідно з п. 4 коефіцієнти при невідомих в лівих частинах обмежень двоїстої задачі отримуються транспонуванням матриці коефіцієнтів при змінних в обмеженнях (d). Наприклад, в обмеження прямої задачі (d) змінна x ₁ входить з такими коефіцієнтами (1; -2; 19), отже, ці числа використовуємо як коефіцієнти лівої частини першої нерівності двоїстої задачі

(f)

Знак нерівності – “≥“ встановлюється згідно з п. 3, а згідно з п. 2 вільні члени в нерівностях дорівнюють коефіцієнтам цільової функції прямої задачі. Згідно з п. 5 записуємо умову невід’ємності невідомих

(g)

Задачі (a), (d), (c) та (e), (f), (g) є взаємно - двоїстими. Якщо за вихідну взяти задачу (e), (f), (g) та побудувати двоїсту до неї, то отримаємо задачу (a), (d), (c).