має жодного негативного елементу, то завдання не можна вирішити. br/>
7. Проблеми виродження, зациклення
Як правило, всі базисні змінні відмінні від нуля (тобто в симплекс-таблиці всі вільні члени). Однак, немає ніяких обмежень до того, щоб одна або декілька базисних змінних звернулися в нуль. p> Базисне рішення (базис) є невиродженим, якщо воно містить рівно m відмінних від нуля компонент. В іншому випадку - виродженим.
Якщо початковий план завдання невирождени, то ніяких складнощів при вирішенні не виникає, при правильному виборі дозволяє елемента. Якщо хоча б одна базисна змінна в НДБР прийняла нульове значення, то за правилами симплекс-методу саме вона повинна буде увійти в базис на наступному кроці, так як min bi/aij * = 0. При цьому значення цільової функції не зміниться. br/>
Лекція 6.
Двоїстість в лінійному програмуванні
Запитання:
1. Поняття двоїстості, тіньової ціни, двоїстої оцінки.
2. Правила побудови двоїстої задачі.
. Основні теореми двоїстості та їх економічний зміст.
1. Поняття двоїстості, тіньової ціни, двоїстої завдання
Двоїстість є одним з фундаментальних понять в лінійному програмуванні, що призводить до важливого результату теоретичного та практичного характеру. Розглянемо поняття подвійності на прикладі задачі оптимального використання ресурсів. p> На виробництво n видів продукції підприємство витрачає m видів ресурсів, наявних в обмежених кількостях b = (b1, b2, ..., bm). На виробництво одиниці j-го виду продукції потрібно aij одиниць i-го виду ресурсу. Прибуток від реалізації одиниці продукції Сj, j =. Необхідно визначити такий план виробництва х = (х1, х2, ..., хn), при якому прибуток підприємства була б максимальною. Математична модель задачі виглядає наступним чином. br/>
С1х1 + ... + Сnxn = F (x) m ax, xj 0, j =.
У випадку завдання вирішується симплекс-методом. Що обмежує виробництво? Задамося питанням, яка з точки зору підприємства цінність наявних у його розпорядженні ресурсів? При вирішенні цього питання будемо мати на увазі, що ресурси, які підприємство не може повністю використовувати, мають для нього дуже низьку цінність, в тому сенсі, що підприємство не згідно нести навіть невеликі витрати на збільшення запасів цих ресурсів. Дороге обладнання, не використовується у технологічному процесі, складає для підприємства нульову цінність. p> Найбільшу цінність, очевидно, будуть мати ті ресурси, які найбільшою мірою обмежують випуск продукції, а, отже, і прибуток підприємства та на збільшення запасів яких підприємство згідно затратити значні кошти.
Можна вважати, що кожен вид ресурсу має деякою В«тіньовоїВ» ціною, визначальною цінність даного ресурсу для підприємства з точки зору прибутку від реалізації своєї продукції і яка від наявної кількості цього ресурсу і потреби в ньому.
Крім того, якщо зараз використовується один технологічний процес, що вимагає великих витрат деякого ресурсу, запаси якого обмежені, значить В«тіньоваВ» ціна велика, то завтра цей процес може бути змінений таким чином, що дозволить більш економно використовувати всі запаси ресурсів, отже зміняться В«тіньовіВ» ціни. Але як би не вдосконалився технологічний процес зовсім без ресурсів не обійтися. Таким чином, можна припустити, що існують оптимальні тіньові ціни, відповідні оптимальному розподілу ресурсів.
В економічній літературі В«тіньовіВ» ціни часто називають об'єктивно-зумовленими або оптимальними оцінками, двоїстими або обліковими, неявними оцінками.
Щоб визначити оптимальні В«тіньовіВ» ціни ресурсів необхідно скласти і вирішити завдання оптимізації. Маємо ті ж вихідні дані, що і для задачі оптимального використання ресурсів. Тільки тепер необхідно знайти такі В«тіньовіВ» ціни ресурсів y = (y1, y2, ..., ym), при яких вартість всіх ресурсів була б мінімальна, yi - В«тіньоваВ» ціна одиниці i-го ресурсу, yi 0. p> В«ТіньовіВ» ціни y = (y 1 , y 2 , ..., y m ) повинні бути такими, щоб В«тіньоваВ» ціна всіх ресурсів, витрачених на виробництво одиниці продукції кожного виду, була б не менше одержуваного від її реалізації доходу. Іншими словами, вартість витрачених ресурсів не може бути менше вартості остаточного продукту (оскільки існують неминучі витрати):
.
Оптимальними В«тіньовимиВ» цінами природно вважати такі, які мінімізують загальну вартість ресурсів.
.
Запишемо обидва завдання в матричному вигляді:
Пряме завдання Двоїста задача
Ах АТy C
F = CTx Z =
x 0 y 0
