Двоїстість у задачах лінійного програмування: правила побудови двоїстих задач та їх основні класи


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

(4.1)

за умов

(4.2)

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

 



 

 


2. Якщо цільова функція початкової задачі досліджується на максимум, то двоїстої – на мінімум, і навпаки.

3. Щоб записати цільову функцію двоїстої задачі, потрібно праві частини основних обмежень початкової задачі перемножити на двоїсті змінні, що відповідають кожному з цих обмежень і додати. Отже, коефіцієнтами при невідомих в цільовій функції двоїстої задачі є праві частини основних обмежень прямої задачі. Вільний член цільової функції прямої задачі переноситься без змін в цільову функцію двоїстої:

4. Обмеження двоїстої задачі формуємо таким чином: коефіцієнти при невідомій кожного основного обмеження системи (4.2) множимо на відповідні двоїсті змінні і додаємо. В результаті отримуємо ліві частини обмежень двоїстої задачі:

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

5. Враховуючи, що в основних обмеженнях початкової задачі знак нерівності « », то в обмеженнях двоїстої задачі знак нерівності буде « ».

6. Матриця

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

В результаті отримаємо двоїсту задачу:

Двоїсті пари задач лінійного програмування бувають симетричні та несиметричні.

У симетричних задачах обмеження прямої та двоїстої задач є нерівностями, а змінні обох задач можуть набувати лише невід’ємних значень.

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

 



Дата добавления: 2016-07-22; просмотров: 3636;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.007 сек.