>
min , а симплекс-множники оптимального розв'язання прямої задачі є значеннями змінних в оптимальному рішенні двоїстої задачі. Доказ: Запишемо пряму задачу
Ах, x 0, b, F = CTx.
Запишемо задачу в стандартному вигляді Ах + хР = b, де хР = (х1, ..., хn + m) - додаткові, що врівноважують змінні, Т-симплекс-множники оптимального рішення. Відомо, що пряме завдання можна залагодити, отже, можна визначити значення симплекс-множників оптимального рішення. Отримаємо оптимальне вираз цільової функції, тобто
+
(-СТ +) x + = F + bT. (*) br/>
Так як це оптимальний вид цільової функції, то всі коефіцієнти
ненегативні.
або.
Т.ч., якщо y =, то обмеження двоїстої завдання виконуються.
Так як (*) - оптимальний вид цільової функції, то коефіцієнти перед базисними змінними дорівнюють нулю, а вільні змінні самі дорівнюють нулю Fmin =-bT або Fmax = bT. Якщо y =, то це і є цільова функція двоїстої задачі, тобто Z = Fmax = Zmin. Що і потрібно було довести. p align="justify"> Теорема 4. Якщо двоїста задача має кінцеве оптимальне рішення Z = Z min , то пряма задача має кінцеве оптимальне рішення F = F max . При цьому Z min = F max , а значення симплекс-множників оптимального рішення двоїстої завдання є значеннями змінних в оптимальному рішенні прямої задачі з протилежними знаками (якщо обидва завдання вирішуються прямим симплекс-методом).
Доказ: У матричної формі двоїста задача має вигляд.
АТy C, y 0, С 0, Z =
1) Запишемо в стандартному вигляді ATy - yS = C, де yS = (ym +1, ..., ym + n) T 0 - додаткові, що врівноважують змінні, - симплекс-множники оптимального рішення двоїстої завдання. Для двоїстої завдання мають те ж значення, тобто
+
(bT + = Z +. (**)
Так як це оптимальний вид цільової функції Z, то всі коефіцієнти ненегативні.
або.
Таким чином, якщо, то обмеження прямої задачі задовольняються, значить це рішення.
) Оскільки (**) - оптимальне рішення для цільової функції, то коефіцієнти перед базисними змінними дорівнюють нулю, а вільні змінні самі дорівнюють нулю. Отже, min = -, а це є цільова функція прямої задачі, якщо. Що і потрібно було довести. p> Економічний зміст теорем полягає в наступному: якщо завдання оптимізації плану, максимизирующего випуск продукції, розв'язна, те можна залагодити і завдання визначення оцінок ресурсів. План виробництва і оцінки ресурсів є оптимальними тоді і тільки тоді, коли ціна виробленої продукції і сумарна оцінка ресурсів збігаються. Оцінки виступають як інструмент балансування витрат і результатів. Так як FZ, Z - F = - витрати виробництва, які рівні нулю коли F * = Z *. p> Двоїсті оцінки володіють тим властивістю, що вони гарантують рентабельність оптимального плану, тобто рівність загальної оцінки продукції і ресурсів, і обумовлюють збитковість всякого іншого плану, відмінного від оптимального.
Крім того, якщо yi> 0, то при оптимальній виробничій програмі цей ресурс використовується повністю; якщо yi = 0, то ресурс використовується не повністю.
Лекція 7, 8
Елементи теорії ігор та прийняття рішень
Запитання:
1. Основні поняття. p align="justify">. Теореми теорії ігор. p align="justify">. Способи вирішення завдань теорії ігор. p align="justify">. Методи прийняття рішень: в умовах визначеності; в умовах ризику; в умовах невизначеності. br/>
1. Основні поняття теорії ігор
Теорія ігор належить до найбільш молодим математичних дисциплін, її виникнення відноситься до кінця II-ї Світової війни.
Теорія ігор являє собою математичну дисципліну, предметом дослідження якої є методи прийняття рішень в конфліктних ситуаціях.
Ситуація називається конфліктною, якщо в ній стикаються інтереси декількох осіб, які переслідують протилежні цілі.
Кожна з конфліктуючих сторін може проводити ряд заходів для досягнення своїх цілей, причому успіх однієї зі сторін означає невдачу іншого. За наявності вільної конкуренції в ролі борються сторін торгові фірми, промислові підприємства і т.п. Однак, конфліктні ситуації зустрічаються і в багатьох інших областях. До конфліктних ситуацій відносяться майже всі ситуації, що виникають при плануванні військових операцій, виборі системи зброї, охороні об'єктів від нападу, переслідуванні та перехопленні мети. Щоб зробити можливим ма...
