Правила побудови двоїстої задачі
Коефіцієнти цільової функції прямої задачі (вектор) та вектор правої частини обмежень прямої задачі в двоїстій задачі міняються місцями. Загалом можна зробити ще такий висновок, що існує тісний взаємозв'язок між функціональними обмеженнями і змінними взаємодвоїстих задач: У симетричних задачах обмеження прямої та двоїстої задач є нерівностями, а змінні обох задач можуть набувати лише невід'ємних… Читати ще >
Правила побудови двоїстої задачі (реферат, курсова, диплом, контрольна)
Порівнюючи між собою задачі (1.7) та (1.8) можна записати такі правила побудови двоїстої задачі:
- 1. Цільові функції пари двоїстих задач мають різні напрями оптимізації.
- 2. Коефіцієнти цільової функції прямої задачі (вектор) та вектор правої частини обмежень прямої задачі в двоїстій задачі міняються місцями.
- 3. Матриця умов двоїстої задачі отримується шляхом транспонування матриці умов прямої задачі.
- 4. Кожному функціональному обмеженню прямої задачі відповідає прямої задачі відповідає змінна двоїстої задачі.
Загалом можна зробити ще такий висновок, що існує тісний взаємозв'язок між функціональними обмеженнями і змінними взаємодвоїстих задач:
- · Двоїста задача має стільки змінних, скільки є функціональних обмежень у прямій задачі;
- · Двоїста задача має стільки функціональних обмежень, скільки є змінних у прямій задачі;
- · Якщо деяке функціональне обмеження прямої задачі виконується як строга рівність то на відповідну змінну двоїстої задачі не накладається умова невід'ємності
;
· Якщо на деяку змінну прямої задачі не накладена умова невід'ємності, то відповідне функціональне обмеження двоїстої задачі виконується як строга рівність.
.
Двоїсті пари задач лінійного програмування бувають симетричні та несиметричні.
У симетричних задачах обмеження прямої та двоїстої задач є нерівностями, а змінні обох задач можуть набувати лише невід'ємних значень.
У несиметричних задачах обмеження прямої задачі можуть бути записані як рівняння, а двоїстої — лише як нерівності. У цьому разі відповідні змінні двоїстої задачі набувають будь-якого значення, не обмеженого знаком.
Різні можливі форми прямих задач лінійного програмування та відповідні їм варіанти моделей двоїстих задач наведено далі.
Пряма задача. | Двоїста задача. |
Симетричні. | |
Несиметричні.
Розглянемо властивості пари двоїстих задач:
- 1. Двоїста задача до двоїстої задачі завжди дасть пряму;
- 2. Основна нерівність теорії двоїстості.
Лема 1.1 (основна нерівність теорії двоїстості). Якщо
Та.
— допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність:
. (1.9).
Доведення. Помножимо кожне рівняння системи (1.2) на відповідну змінну двоїстої задачі:
. (1.10).
Аналогічно перетворимо систему обмежень (1.5) двоїстої задачі:
(1.11).
Ліві частини нерівностей (1.10) та (1.11) збігаються, отже:
.
Нерівність (1.9) доведено.