 |
Взаємно двоїсті задачі
|
|
|
|
РОЗДІЛ 2
ДВОЇСТІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Взаємно двоїсті задачі
Двоїстість у математичному програмуванні є фундаментальним поняттям, на якому ґрунтується ряд підходів до розв’язування задач оптимізації. Наскільки важлива двоїстість свідчить той факт, що за її відкриття та застосування в оптимальному плануванні в 1975 р. Л.В.Канторович (колишній СРСР) та Т.Купманс (США) були відзначені Нобелівською премією.
Задачі лінійного програмування мають ОДР завжди у вигляді опуклої фігури. Тому ці задачі є окремим випадком задач опуклого програмування.
Кожна задача опуклого програмування, включаючи також задачі лінійного програмування, має свій аналог, який називають двоїстою або спряженою задачею.
Таким чином, практично завжди існує двоїста пара задач, одна з якої є прямою (або основною), а інша – двоїстою (або спряженою). За пряму або двоїсту задачу можна вважати будь-яку з цієї пари. Причому розв’язок однієї задачі з цієї пари дає розв’язок іншої за допомогою теорем двоїстості або останньої симплексної таблиці.
Для складання математичної моделі двоїстої задачі потрібно, щоб пряма задача мала таку структуру:
– знаки обмежень повинні мати одну спрямованість;
– якщо цільова функція прямує до мінімуму, то нерівності повинні бути типу „ 
”, якщо до максимуму, то „ 
”.
Таким чином, при складанні моделі двоїстої задачі пряма задача повин-
на мати модель так званої стандартної форми.
Тому, якщо система обмежень прямої задачі має мішані знаки нерівностей, то треба помножити на (-1) деякі нерівності, щоб одержати одну спрямованість знаків нерівностей, причому вони повинні бути узгоджені з напрямком цільової функції згідно із структурою стандартної форми.
|
|
|
Наприклад, у моделі прямої задачі
треба друге обмеження помножити на (-1).
Двоїста пара задач лінійного програмування буває двох типів:
– обмеження математичної моделі як прямої, так і двоїстої задач зображуються у вигляді нерівностей, причому змінні таких задач не повинні бути від’ємними; таку двоїсту пару задач називають симетричною (прикладом такої пари є задача на суміш);
– математична модель прямої задачі має деякі обмеження у вигляді рівнянь, а двоїста задача має всі обмеження у вигляді нерівностей, причому деякі змінні двоїстої задачі можливі і від’ємні; таку двоїсту пару задач називають несиметричною (прикладом такої пари є транспортна задача).
|
|
|
ВЛАСТИВОСТІ ОСНОВНОЇ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. ГЕОМЕТРИЧНЕ ТЛУМАЧЕННЯ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
ДВОЇСТІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Додавання взаємно перпендикулярних гармонічних коливань
Додавання взаємно перпендикулярних коливань
ДОСЛІДЖЕННЯ ВЗАЄМНОЇ ІНДУКТИВНОСТІ КРУГЛИХ І ПРЯМОКУТНИХ ПЛОСКИХ КОТУШОК
Економетрика як наука, об’єкт, предмет, мета та задачі. Основні характеристики економічної системи як об’єкта моделювання
ЕКОНОМІЧНА І ГЕОМЕТРИЧНА ІНТЕРПРЕТАЦІЇ ЗАДАЧІ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ
Економічна і математична постановка цілочислової задачі лінійного програмування
Завдання 2. Основні позиційні та метричні задачі.
