Правила побудови двоїстих задач - студопедія

Кожній задачі лінійного програмування, яку назвемо вихідної. можна поставити з відповідність деяку іншу задачу лінійного програмування, яка називається двоїстої до неї. Разом узяті, ці завдання утворюють пару взаємно-двоїстих задач і будь-яку з них можна розглядати як вихідну. Вирішуючи одну з цих завдань, можна отримати рішення та іншої задачі.







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

Сформулюємо правила побудови двоїстих задач:

1. Якщо цільова функція f вихідної завдання максимізує, то цільова функція z двоїстої - мінімізується і навпаки.

2. Кількість обмежень (m) вихідної задачі дорівнює кількості змінних двоїстої, а кількість змінних (n) вихідної дорівнює кількості обмежень двоїстої. Змінні двоїстої задачі позначимо через yi (i = 1, m).







3. Оскільки змінні вихідної задачі пов'язані з обмеженнями двоїстої, кожноїзмінної xj> = 0 відповідає в двоїстої завданню обмеження виду «<=» (z→max) или «>= »(Z → min), і навпаки.

4. Кожній змінної xj. не обмеженої по знаку, відповідає обмеження виду «=» двоїстої задачі, і навпаки.

5. Вільні члени обмежень вихідної задачі bi (I = 1, m) в двоїстої є коефіцієнтами при змінних yi (I = 1, m) в цільової функції, а коефіцієнти cj (j = 1, n) при змінних xj (j = 1 , n) в цільової функції вихідної задачі є вільними членами обмежень двоїстої.

6. Матриця A коефіцієнтів при невідомих в обмеженнях вихідної задачі в двоїстої транспонується (A т).

Розглянемо в загальному вигляді одну з приватних завдань лінійного програмування, яку будемо вважати вихідною:

Подвійна до цього завдання буде мати вигляд:

Якщо застосувати правила побудови двоїстих задач, то отримаємо вихідну задачу.

У таблиці 5 наведені приватні види вихідних задач лінійного програмування в матричному вигляді і відповідні їм подвійні завдання. Через Y = (y1. Y2, ..., ym) позначена матриця-рядок невідомих двоїстої задачі. Матриця-рядок Y множиться зліва на матрицю-стовпець B (в цільової функції) і матрицю A (в обмеженнях) виходячи з правил множення двох матриць, а також правил побудови двоїстих задач (зокрема, в двоїстої завданню матриця коефіцієнтів при невідомих в обмеженнях повинна бути транспонованою).







Схожі статті