Теорія ймовірностей і матстатистику - двоїста задача лінійного программиро-вання

Не знайшли те, що шукали?

Якщо вам потрібен індивідуальний підбір або робота на замовлення - скористайтеся цією формою.

Наступне питання "

Теорія ігор-мат.дісціпліна, що досліджує ситуації, до к.прінятіе рішень залежить від неск.участніков.Інтер

Двоїста задача лінійного программиро-вання. Основні теореми подвійності. Еконо-мічного сенс двоїстих оцінок. Перша теорема подвійності (Основна).

Якщо одна з двоїстих задач має оптимальне рішення, то і інша його має, той причому екстремальні значення їх цільових функцій збігаються. оптимальний рі-ня пари двоїстих задач. Якщо ж цільова однієї з двоїстих задач не обмежена, то двоїста задача рішення не має, тому що область допустимих рішень порожня.
Основна теорема подвійності дає правило знахо-дження оптимального рішення двоїстої завдання про оптимальному вирішенню вихідної задачі. Для знаходжу-дення оптимального рішення двоїстої завдання необхідно знайти оптимальне рішення вихідної задачі симплекс-методом. Оптимальне значення двоїстої змінної дорівнює відповідній оцінці останньої симплекс-таблиці плюс коеффіці-ент цільової функції вихідної задачі.
Друга теорема подвійності (Про рівновагу). Теорема вірна для симетричних двоїстих задач. Для інших завдань можна застосовувати тільки для обмежень у вигляді нерівностей і для невід'ємних змінних. Розглянемо стандартну ЗЛП.
Подвійна до неї має вигляд:
Теорема. Щоб допустимі рішення вихідної і двоїстої стандартних завдань були оптимальними необхідно і достатньо, щоб име-ли місце наступні співвідношення:
Економічний сенс двоїстих оцінок. Рас-дивимося завдання. Підприємство має m-видів ресурсів в кількості одиниць. з яких виробляються n-видів продукції. витрата i-го ресурсу на виробництво одиниці j-ої продукції. Скласти план випуску продукції, що забезпечує максимальну вартість продукції. Позначимо за кількість продукції j-го виду. Тоді модель задачі така: Знайти змінні. задовольняють системі ограниче-ний
при яких функція
Оцінимо ресурси необхідні для виготовлення про-дукції. Позначимо за - оцінку одиниці першого ресурсу. Тоді оцінка ресурсів, що йдуть на виготовлен-ня одиниці j-ої продукції дорівнює. Вона повинна бути не менше вартості одиниці продукції. Отримуємо систему обмежень двоїстої задачі.
Сумарна оцінка всіх ресурсів така:
Нехай знайдені два оптимальних рішення взаємно двоїстих задач: і
З теореми про рівновагу слід, що якщо яка-небудь змінна двоїстої задачі рівна «0», то відповід-ветствующее обмеження вихідної задачі виконуємо-ється як суворе нерівність. Припустимо, що. тоді Це означає, що 1-ої ресурс в оптимальній плані використовується не повністю. Він є в надлишку на підприємстві, тобто не є дефіцитним. З цієї ж теореми слід, що якщо яка-небудь змінна двоїстої задачі не дорівнює «0», то відповідне їй обмеження вихідної задачі виконується як суворе рівність. Нехай. тоді. тобто 2-й ресурс в оптимальному плані використовується повністю, цей ресурс дефіцитний для підприємства. Таким обра-зом, двоїсті оцінки показують, які ресурси є дефіцитними для підприємства, а які ні. Вони виявляють за рахунок збільшення якими операційними системами можна поліпшити план.
Розглянемо цільову функцію двоїстої задачі. Нехай 2-й ресурс є дефіцитним, тому що 2-й ресурс є в кількості. збільшимо це кількість на єдині-цу. отримаємо:
Тобто цільова функція збільшується на. тоді збільшується на. таким чином ненульові оцінки показують на скільки збільшиться прибуток підпри-ємства, якщо обсяг дефіцитного ресурсу збільшити на одиницю.

Схожі питання

знайдено схожих сторінок: 10