Міністерство освіти і науки України
Дніпропетровський Національний Університет
Факультет електроніки, телекомунікацій та комп'ютерних систем
Кафедра АСОІ
Розрахункова задача № 4
«Дослідження операцій»
м. Дніпропетровськ
2007р.
Завдання
Записати задачу двоїсту до даної, вирішити одну з пари завдань і відшукати оптимальне рішення другої
Пряма задача має вигляд:
Загальна постановка двоїстої задачі
Двоїста задача - це допоміжна задача лінійного програмування, вона формулюється з прямої задачі.
Ідея методу заснована на зв'язку між рішеннями прямої і двоїстої задачі.
Двоїста задача формується безпосередньо з умов прямої задачі за такими правилами:
Якщо пряме завдання є завданням максимізації, то двоїста буде завданням мінімізації;
Коефіцієнти цільової функції прямої задачі С1, С2, ...., Сn стають вільними членами обмежень двоїстої задачі;
Вільні члени обмежень прямої задачі b1, b2, ...., Bn стають коефіцієнтами цільової функції двоїстої задачі;
Матрицю обмежень двоїстої задачі отримують транспонування матриці обмежень прямої задачі;
Якщо пряме завдання є завданням максимізації, то у всіх неравенствах двоїстої завдання стоятимуть знаки ≥, і знаки ≤, якщо пряма задача є задачею мінімізації.
Число обмежень прямої задачі дорівнює числу змінних двоїстої задачі.
Пряма задача в канонічній формі
Двоїста до неї завдання буде мати вигляд
Двоїста задача вирішується симплекс-методом до досягнення оптимального рішення.
Рішення прямої задачі
Всі обмеження прямої задачі - це рівності з невід'ємними правими частинами, коли всі змінні невід'ємні.
Наведемо пряму задачу до стандартного вигляду:
Підставимо значення в цільову функцію:
Таким чином, пряме завдання в стандартній формі має такий вигляд:
Будуємо симплекс таблицю:
Ітерація № 1
Базис | | | | | | | Рішення | Оцінений |
| | | 0 | 0 | | 0 | | |
| 5 | -2 | 1 | 0 | 0 | 0 | 4 |