нніх у Системі обмежень прямої задачі, и матриця Коефіцієнтів у Системі обмежень двоїстої задачі
В
утворюються одна з одної транспонуванням, тоб заміною рядків стовпчік, а стовпчіків - рядками.
Процес Побудова двоїстої задачі ЗРУЧНИЙ зобразіті схематично:
В
Рис. 3.1. Схема Побудова двоїстої задачі до прямої
Парі завдань лінійного програмування бувають сіметрічні та несіметрічні.
У симетрично завданнях обмеження прямої та двоїстої завдань є позбав нерівностямі, а змінні обох задач могут набуваті позбав невід'ємніх значеннями.
У несіметрічніх завданнях деякі обмеження прямої задачі могут буті рівняннямі, а двоїстої - позбав нерівностямі. У цьом разі відповідні рівнянням змінні двоїстої задачі могут набуваті будь-яких значень, НЕ обмежених знаком.
Всі Можливі формі прямих завдань лінійного програмування та відповідні їм Варіанти моделей двоїстіх завдань у матрічній ФОРМІ наведено нижчих.
Пряма завдання
Двоїста задача
Cіметрічні задачі
max F = CX
AX B
X 0
min Z = BY
ATY C
Y 0
min F = CX
AX B
X 0
max Z = BY
ATY C
Y 0
Несіметрічні задачі
max F = CX
AX = B
X 0
min Z = BY
ATY C
Y
min F = CX
AX = B
X 0
max Z = BY
ATY C
Y
До даної задачі лінійного програмування записатися двоїсту.
max F = -5 x 1 + 2 x 2;
В
Розв'язання. Перш чем записатися двоїсту задачу, звітність, Пряме завдання звесті до стандартного вигляд. Оскількі цільова функція F максімізується и в Системі обмежень є нерівності, то смороду Муся мати знак «». Тому перше обмеження задачі помножімо на (-1). После цього знак нерівності змініться на протилежних. Отрімаємо:
max F =-5x1 + 2x2;
В
Тепер за відповіднімі правилами складемо двоїсту задачу:
;
В
Або схематично (вікорістовуючі компоненти векторів та матриці) зв'язок между парою ціх завдань можна зобразіті так:
В
До заданої задачі лінійного програмування записатися двоїсту.
В В В
Розв'язання. пряме завдання зведемо до стандартного вигляд. Оскількі цільова функція F мінімізується и в Системі обмежень є нерівності, то смороду мают буті увазі В«В». Тому друга обмеження задачі звітність, помножіті на (-1). При цьом знак нерівності змініться на протилежних. Отрімаємо:
В
Двоїста задача:
В В
Оскількі перше обмеження початкової задачі є рівнянням, то відповідна Йому змінна двоїстої задачі может набуваті як додатного, так и від'ємного значення.
В В
3. Основні теореми двоїстості та їх економічний Зміст
Зв'язок между оптимальними розв'язки прямої та двоїстої задач встановлюються Лемі та теореми двоїстості. Розглянемо задачі (3.1) - (3.3) та (3.4) - (3.6) з Економічною інтерпретацією. p> Если та - Допустимі розв'язки відповідно прямої та двоїстої задач, то віконується нерівність
або. (3.7)
Доведення . Помножімо Кожне рівняння системи (3.2) на відповідну змінну двоїстої задачі:
В
В
Підсумувавші праві и ліві Частини нерівностей, отрімаємо:
. (3.8)
Аналогічно перетворімо систему обмежень (3.5) двоїстої задачі:
В
Підсумувавші после множення тут такоже ліві та праві частині, отрімаємо нерівність:
(3.9)
Ліві Частини нерівностей (3.8) та (3.9) збігаються, отже:
.
Нерівність (3.7) доведено.
Если та - Допустимі розв'язки відповідно прямої та двоїстої задач, для якіх віконується Рівність
(3.10)
то X *, Y * - оптімальні розв'язки відповідніх завдань.
Доведення . Нехай - допустима план прямої задачі (3.1) - (3.3). Тоді на підставі нерівності (3.7) маємо:. За умів задачі, отже
(3.11)
Оскількі за допущені - довільній допустимих план прямої задачі, то нерівність (3.11) віконується для будь-якого з можливіть розв'язків. Отже, маємо, что при цільова функція (3.1) набірає найбільшого значення, а тоб є оптимальним розв'язком початкової задачі.
У аналогіч...
