Сформулюйте умови оптимальності розв’язку задачі симплекс методом
Симплексний метод уможливлює направлений перебір опорних планів, тобто перехід від одного плану до іншого, який є хоча б не гіршим від попереднього за значенням функціонала. Для того, щоб план задачі лінійного програмування був оптимальним, необхідно і достатньо, щоб його оцінки 
були невід’ємними для задачі на максимум та недодатними для задачі на мінімум.
Умови оптимальності планів задач лінійного програмування є наслідками двох теорем.
Теорема 1. Якщо для деякого вектора 
виконується умова 
, то план 
не є оптимальним і можна відшукати такий план Х, для якого виконуватиметься нерівність 
.
Теорема 2. Якщо для деякого вектора виконується умова 
, то план не є оптимальним і можна побудувати такий план Х, для якого виконуватиметься нерівність 
.
Сформулюйте необхідну і достатню умови існування розв’язку транспортної задачі
Оптимальним планом транспортної задачі називають матрицю 
, яка задовольняє умови задачі, і для якої цільова функція набирає найменшого значення.
Теорема(умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі
за обмежень:
є її збалансованість: 
У чому сутність теорії двоїстості у лінійному програмуванні
Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею.
Пряма задача:
max F = c1x1 + c2x2 + … + cnxn
|
|
|
за умов: 
Необхідно визначити, яку кількість продукції кожного j-го виду 
необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів — 
; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції — 
, а також 
— ціни реалізації одиниці j-ої продукції.
Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу 
поставимо у відповідність його оцінку 
. Умовно вважатимемо, що 
— ціна одиниці і-го ресурсу.
На виготовлення одиниці j-го виду продукції витрачається згідно з моделлю m видів ресурсів у кількості відповідно 
. Оскільки ціна одиниці і-го виду ресурсу дорівнює 
, то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб: 
.
Продавати ресурси доцільно лише за умови, що виручка, отримана від продажу ресурсів, перевищує суму, яку можна було б отримати від реалізації продукції, виготовленої з тих самих обсягів ресурсів, тобто: 
.
Зрозуміло, що покупці ресурсів прагнуть здійснити операцію якнайдешевше, отже, необхідно визначити мінімальні ціни одиниць кожного виду ресурсів, за яких їх продаж є доцільнішим, ніж виготовлення продукції. Загальну вартість ресурсів можна виразити формулою:
|
|
|
.
Отже, в результаті маємо двоїсту задачу:
за умов: 
Тобто необхідно визначити, які мінімальні ціни можна встановити для одиниці кожного і-го виду ресурсу 
, щоб продаж ресурсів був доцільнішим, ніж виробництво продукції.
Задача 2 є двоїстою або спряженою до задачі 1, яку називають прямою (основною, початковою). Поняття двоїстості є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів.
Дата добавления: 2018-02-18; просмотров: 1275; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!