Двоїста задача лінійного програмування

Кожній задачі лінійного програмування певним чином можна поставити у відповідність деяку іншу задачу, яка називається двоїстою задачею лінійного програмування. Запишемо пряму (вихідну) задачу лінійного програмування, яка полягає у визначенні максимуму цільової функції:

120

при обмеженнях:

216

39

Означення: Двоїстою задачею лінійного програмування по віднршенню до вихідної задачі (1) — (3) називається задача, яка полягає у визначенні мінімального значення цільової функції

47

при обмеженнях

511

69

Двоїста задача будується на основі наступних правил.

1. Цільова функція вихідної задачі (1) — (3) задається на максимум, а цільова функція двоїстої задачі (4) — (6) задається на мінімум.

2. Матриця

79

яка складається з коефіцієнтів при невідомих вихідної задачі переходить у 85.

3. Число невідомих двоїстої задачі (4) — (6) дорівнює числу рівнянь системи обмежень (2). Число рівнянь в системі обмежень двоїстої задачі (5) дорівнює числу невідомих вихідної задачі (1) — (3).

4. Коефіцієнти при невідомих цільової функції двоїстої задачі дорівнюють стовпчику вільних членів вихідної задачі. Вільні члени системи обмежень (5) двоїстої задачі дорівнюють коефіцієнтам цільової фуекції прямої задачі.

5. Якщо деяка змінна 96 може приймати тільки додатні значення, то j-та нерівність в системі обмежень двоїстої задачі задається у вигляді нерівності. Якщо деяка змінна 96 може приймати як додатні так і від'ємні значення, тоді рівності в системі обмежень двоїстої задачі задаються у вигляді рівностей.

Зауваження: пара двоїстих задач може бути симетричною або не симетричною. Симетричною називається в тому випадку, якщо обмеження в системі (2) прямої задачі і обмеженння в системі (5) двоїстої задачі задаються у вигляді нерівностей. В протилежному випадку не симетричною.

Приклад: для задачі, яка полягає у максимізації функції 106 при обмеженнях

1111

125

сформувати двоїсту задачу.

Відповідь:

135

145

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар