Складання двоїстої задачі, якщо пряма представлена зі змішаною системою обмежень

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

1. Всі обмеження-нерівності прямої задачі повинні мати той самий знак. При цьому характер нерівностей - обмежень і тип цільової функції погоджуються в такий спосіб:

а) б)

обмеження нерівності ≤ обмеження нерівності ≥.

2. Кожному обмеженню вихідної задачі ставиться у відповідність двоїста змінна. При цьому така змінна буде невід’ємною, якщо відповідає обмеженню - нерівності, і така змінна може мати будь-який знак, якщо відповідає обмеженню рівності.

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

а) матриця коефіцієнтів при невідомих транспонується;

б) праві частини обмежень однієї із задач є коефіцієнтами при невідомих цільовий функції іншої задачі. При цьому, якщо пряма задача мала opt max, то двоїста повинна бути орієнтована убік opt min.

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

Відмітимо, що для пари взаємо-двоїстих задач справедлива теорема про минимакс (або основна теорема теорії подвійності, або 1-а теорема теорії подвійності).

Дата добавления: 2014-12-07