х1 + ... +0 хm + = F (x) +
Отриманий вираз представляє оптимальне вираз цільової функції. При цьому оптимальність таблиці також визначаться коефіцієнтами цільової функції. Зауважимо, що Сj не впливають на обмеження завдання. Якщо змінити Сj, то зміняться умови оптимальності:
якщо для Сj коефіцієнта цільової функції виявляться невід'ємними, то знайдене рішення збережеться, тобто якщо,, то рішення не зміниться
хб = хб, F (x) = -.
якщо хоча б один коефіцієнт виявиться менше нуля, то слід перейти до іншого базисного рішенням, тобто продовжити вирішення звичайним симплекс-методом.
Приклад.
4. Включення додаткових змінних
Кожна змінна ЗЛП, якщо вона не є врівноважує або штучної, визначає план виробництва деякої продукції, обсяг споживання тощо Припустимо, надійшла пропозиція випускати новий вид продукції або використовувати нову технологію. Чи варто міняти вже налагоджене виробництво? Чи буде збільшення прибутку (скорочення витрат) вагомим? p> Нехай обсяг нового виду продукції хn +1, технологічні коефіцієнти відомі
Р = (1 (n +1), 2 (n +1), ..., m (n +1)) T, передбачуваний прибуток від реалізації одиниці продукції Сn +1. Всі інші умови залишаються колишніми. Щоб врахувати ці зміни, не вирішуючи завдання з самого початку, необхідно додаткові дані записати в оптимальну таблицю. Нова В«вихіднаВ» матриця коефіцієнтів A = AP, щоб привести її до вигляду оптимальної таблиці, необхідно помножити її на В-1. Таким чином, в оптимальній таблиці додається ще один стовпець Р * = В-1Р. При цьому вільні члени не змінюються. Залишилось записати коефіцієнт цільової функції, це можна зробити за допомогою симплекс - множників. Помножимо коефіцієнти Р на відповідні симплекс - множники і додамо до коефіцієнту цільової функції в стандартному вигляді:
Cn +1 + = Cn +1 *.
Якщо Cn +1 *, то хn +1 залишиться вільною (тобто рівною нулю), так як збережеться ознака оптимальності. Отже, план змінювати не варто. p> Якщо Cn +1 * <0, то слід поліпшити рішення, а саме хn +1 ввести в базисні змінні. Отже, план зміниться. При цьому рішення продовжується звичайним симплекс-методом. p> Приклад.
5. Включення додаткових обмежень
Економічна ситуація, в якій доводиться вирішувати виробничі та планові завдання, змінюється. Може виявитися так, що деякий ресурс, який вважався раніше необмеженим, виявиться лімітований. Наприклад, введення веерного розподілу електроенергії т.п. Іншими словами, необхідно перевірити. Чи задовольняє розрахований план новим обмеженням, і як його змінити, якщо обмеження порушуються. p> Отже, нехай - нове додаткове обмеження до вже вирішеною завданню. Тобто х * вже знайдено. p> Якщо знайдене х * = (х1, х2, ..., хn) задовольняє поставленому додатковому обмеженню, то план ніяк не зміниться (обмеження не обмежує дане виробництво).
Якщо х * = (х1, х2, ..., хn) не задовольняє новому обмеженню, то необхідно змінити план, тобто продовжити вирішення.
Щоб продовжити вирішення. Необхідно врахувати нове обмеження, записавши його в канонічному вигляді, відповідному оптимальної таблиці: додаткове обмеження повинне містити одну змінну з коефіцієнтом 1, і щоб в інших рівняннях і вираженні цільової функції вона була відсутня, крім того, це рівняння не повинно містити базисних змінних оптимальної таблиці. Щоб виключити базисні змінні оптимальної таблиці, використовують оптимальний канонічний вигляд. При цьому рішення триває двоїстим симплекс-методом. p> Приклад.
6. Двоїстий симплекс-метод
Для вирішення завдання двоїстим симплекс-методом вона повинна мати неприпустимий канонічний вигляд. І ознака оптимальності повинен виконуватися. p> Загальна ідея: починаючи з неприпустимого базисного рішення при виконанні ознаки оптимальності, послідовно перейти до допустимого базисного рішенням, зберігши ознака оптимальності.
Правила.
. Неприпустимий канонічний вигляд обмежень і оптимальний вид (Сj) цільової функції записують у вихідну таблицю.
. Серед негативних вільних членів вибирають, відповідний рядок позначають * і називають роздільної.
. Серед всіх відносин коефіцієнтів цільової функції до негативних елементів роздільної рядка вибирають, відповідний стовпець позначають, виконують звичайні симплекс-перетворення і називають дозволяючими .
Зауваження: 1. Звичайний симплекс-метод при збереженні допустимості рішення переходить послідовно до оптимального рішення. А двоїстий симплекс-метод при збереженні оптимальності переходить послідовно від неприпустимого рішення до допустимого. p align="justify">. Правила двоїстого симплекс-методу відрізняються від правил звичайного вибором дозволяють стовпчика і рядка. p align="justify">. Якщо у роздільній рядку (для двоїстого методу) не...
