Розв’язування двоїстої задачі
Використовуючи перші дві теореми та при відомому розв’язку однієї із задач двоїстої пари, можна знайти розв’язок другої задачі з цієї пари. Таким чином, теореми двоїстості дають змогу на основі розв’язку однієї задачі лінійного програмування знайти розв’язок двоїстої до неї задачі.. Така необхідність виникає тоді, коли є деякі труднощі у розв’язуванні однієї з двоїстої пари задач. Крім того, обсяг обчислень при використанні симплекс-методу залежить від кількості обмежень, тому доцільно розв’язувати одну із задач двоїстої пари з меншою кількістю обмежень. Якщо задача має п обмежень, то практично доведено, що для знаходження розв’язку такої задачі буде потрібно зробити приблизно Згідно з теоремою 2 можна виконати аналіз на дефіцитність тих або інших ресурсів, які задані в задачі. Справді, якщо повністю використовується і -й ресурс, то відповідне обмеження стає строгим рівнянням, тобто У цьому разі згідно з теоремою 2 відповідні змінні двоїстої задачі Тому змінні За допомогою теореми 3 можна проаналізувати вплив розміру початкових і- х ресурсів на значення Якщо відомий розв’язок однієї із задач двоїстої пари, то розв’язок другої задачі з цієї пари можна знайти без її розв’язування симплекс-методом. При цьому можливі такі випадки. Першій випадок. Оптимальний розв’язок однієї задачі з двоїстої пари наведено у вигляді симплекс-таблиці. Згідно з теоремою 1 використовується така відповідність
причому: якщо якщо Це означає, що кількість змінних Відповідність змінних симплекс-таблиці така:
Така форма зручна для аналізу добутих розв’язків, коли відома оптимальна симплекс-таблиця. Другий випадок. Відомі тільки значення змінних та цільова функція однієї із задач двоїстої пари. При цьому використовують теорему 2: відомі змінні підставляють в обмеження розв’язаної задачі та за знаком „=” чи „ Розглянемо приклад. Необхідно знайти оптимальний розв’язок наступної задачі лінійного програмування: а потім згідно з теоремами двоїстості знайти оптимальний розв’язок двоїстої їй задачі Розглянемо два випадки. Перший випадок. Відомий оптимальний розв’язок прямої задачі у вигляді симплекс-таблиці:
Згідно з цією симплекс-таблицею маємо
тобто Другий випадок. Проаналізуємо значення підставимо значення Згідно зі значеннями Унаслідок такого аналізу розв’язок двоїстої задачі такий:
Читайте также: А) Метод Гаусса розв’язування систем лінійних рівнянь Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|