4. Перехід до нового опорного плану виконується заміною базису, тобто виключенням з базису деякої змінної і введення замість неї нової з числа вільних змінних задачію.

Змінна, що вводиться в базис, відповідає тій оцінці Δj=Zj-Cj, що не задавольняє умову оптимальності. Якщо таких оцінок декілька, серед них вибирають найбільшу за абсолютною величиною і відповідну їй змінну вводять в новий базис. Стовбчик в якому знаходиться нова змінна базису називається напрямним.

Для визначення змінної, яка підлягає виключенню з базиса, знаходять оцінки θ = , де b_і – елементи стовбчика План симплексної таблиці, a_ik – додатні елементи напрямного стовбчика. Серед усіх обчислених оцінок θ вибирають найменшу, змінну, що знаходиться у одному рядку із min θ в стовбчику Базис виключають з базису. Відповідний рядок (із min θ) симплексної таблиці називаєтся напрямним. Перетином напрямного рядка і напрямного стовбчика є число a_рk , яке називають розв’язувальним елементом. За допомогою розв’язувального елемента і метода Жордана –Гаусса розраховують нову сиплексну таблицю.

Далі ітераційний процес повторюють доти, поки не буде знайдено оптимальний план ЗЛП, або визначено, що такого не існує.

Розв’язуючи ЗЛП симплексним методом можна отримати такі результати:

1). У оцінковому рядку оцінка Δj=Zj-Cj=0 відповідає вільній (небазисній) змінній, тоді ЗЛП має альтернативний оптимальний план. Отримати його можна, втбравши розв’язувальний елемент у зазначеному стовбчику таблиці і виконати ще один крок сисплекс-методу.

2). При переході від одного опорного плану до іншого в напрямному стовбчику відсутні додатні елементи, тобто неможливо визначити розв’язувальний елемент, це означає, що цільова фукція ЗЛП необмежена і оптимальних планів не існує.

3). У стовбчику θ симплексної таблиці містяться два або декілька однакових найменших значення θ_і (не можливо визначити напрямний рядок), тоді новий опорний план буде виродженим (одна або декілька базисних змінних будуть мати нульове значення).

Вироджені плани можуть привести до циклічності алгоритму, тобто до багаторазового повторення процесу обчислення, що унеможливлює отримання оптимального плану. У такому випадку, для визначення напрямного рядка застосовують метод Креко [].

Сутність методу Креко – елементи рядків що містять однакові найменші значення θ_і ділять на елементи напрямного стовбчика, результати ділення заносять у рядки додаткової таблиці. За напрямний обирається той рядок у якому раніше зустрінеться найменша частка при перегляді таблиці зліва направо по стовбцях.

Наприклад, таблиця що містьть два однакових найменших значення θ_і = 2, має вигляд:

Припустимо, що напрямним стовбчиком буде стовбчик x ₇ , тоді розв’язувальним елементом може бути 2, 4, так як min θ_і =2. застосувавши метод Креко отримуємо допоміжну таблицю:

Послідовно порівнюючи зліва направо отримані частки по стовбцях бачимо, що перші два стовбчика мають однакове значення часток. Третій стовбчик містить найменшу частку 1,5 у першому рядку, відповідно цей рядок і буде напрямним.

Продемонструємо застосування алгебраїчного симплекс-методу на прикладі.

Приклад 3.3. Продукція чотирьох видів А, В, С і D проходить послідовну обробку на двох видах виробничого обладнання. Норми часу на обробку одиниці продукції кожного виду та ціна одиниці продукції наведені в таблиці3.2.

Таблиця 3.2

Витрати на виробництво одиниці продукції кожного виду визначають як величини, прямо пропорційні до часу роботи виробничого обладнання. Вартість однієї години роботи обладнання становить 10 грошових одиниць для обладнання 1 і 15 грошових одиниць — для обладнання 2. Термін роботи обладнання обмежений і для обладнання 1 становить 900 годин, а для верстата 2 — 760 годин.

Визначити оптимальний план виробництва продукції всіх чотирьох видів, з метою отримання максимального загального прибутку від реалізації готової продукції.

Розв’язок.

Побудова економіко-математичної моделі.

Позначимо х_j — план виробництва продукції j-го виду, де j може набувати значень від 1 до 4.

Обмеженнями задачі буде ресурс часу використання обладнання для виробництва продукції:

(год.);

(год.).

Критерієм оптимальності є загальний прибуток від реалізації готової продукції, який розраховується як різниця між ціною та собівартістю виготовлення продукції кожного виду. Відповідно, цільова фукція задачі матиме вигляд:

або .

Отже, математична модель цієї задачі має такий вигляд:

→ max

за умов:

Розв’яжемо задачу симплекс-методом, попередньо записавши систему обмежень задачі в канонічному вигляді.

Для цього перейдемо від обмежень-нерівностей до рівнянь, додавши до лівої частини обмежень додаткові змінні х₅ та х_6, економічний зміст яких можна інтерпритувати як частину ресурсів не задіяну у виробництві проукції:

У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:

Канонічну систему обмежень задачі запишемо у векторній формі:

де

Оскільки вектори та одиничні та лінійно незалежні, то саме з них складається початковий базис у даній системі векторів. Змінні задачі х₅ та х₆, що відповідають одиничним базисним векторам, називаються базисними, решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних:

Оскільки додатні коефіцієнти х₅ та х₆ відповідають лінійно незалежним векторам, то за означенням -є опорним планом задачі і для цього початкового плану цільова функція має вигляд:

Складемо симплексну таблицю для першого опорного плану задачі.

Елементи останнього рядка симплекс-таблиці є оцінками _j, за допомогою яких опорний план перевіряють на оптимальність. Їх визначають так:

;

;

;

;

;

.

У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану: .

Після обчислення всіх оцінок опорний план перевіряють на оптимальність.

Якщо всі (для задачі на max) або (для задачі на min), то визначений опорний план є оптимальним. Якщо ж в оцінковому рядку є хоча б одна оцінка, що не задовольняє умову оптимальності (від’ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.

У цій задачі в оцінковому рядку дві оцінки та від’ємні, тобто не задовольняють умову оптимальності, і тому перший визначений опорний план є неоптимальним. За алгоритмом симплекс-методу необхідно від нього перейти до іншого опорного плану задачі.

Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних.

Для введення до нового базису вибираємо змінну х₂, оскільки їй відповідає найбільша за абсолютною величиною оцінка з-поміж тих, які не задовольняють умову оптимальності (|–10|>|–8|).

Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х₂» знаходимо відношення і вибираємо найменше значення. Згідно з даними симплексної таблиці маємо, що , і тому з базису виключаємо змінну х₅, а число а₁₂ =3 — розв’язувальний елемент. Будуємо другу симплексну таблицю, елементи якої розраховують за методом Жордана—Гаусса.

Друга симплексна таблиця має такий вигляд:

У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «С_баз», а решту елементів нової таблиці розраховують за правилами:

1. Кожний елемент розв’язувального (напрямного) рядка необхідно поділити на розв’язувальний елемент і отримані числа записати у відповідний рядок нової симплексної таблиці.

2. Розв’язувальний стовпчик у новій таблиці записують як одиничний з одиницею замість розв’язувального елемента.

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

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

Усі інші елементи наступної симплексної таблиці розраховують за правилом прямокутника.

Щоб визначити будь-який елемент нової таблиці за цим правилом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами:

— розв’язувальний елемент;

[N] — число, що стоїть на місці елемента нової симплексної таблиці, який ми маємо розрахувати;

[Y] та [Z] — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.

Необхідний елемент нової симплекс-таблиці визначають за такою формулою:

.

Наприклад, визначимо елемент , який розміщується в новій таблиці в другому рядку стовпчика «х₄». Тоді . Це значення записуємо в стовпчик «х₄» у другому рядку другої симплексної таблиці.

Аналогічно розраховують усі елементи нової симплексної таблиці, у тому числі й елементи стовпчика «План» та оцінкового рядка.

Після заповнення нового оцінкового рядка перевіряємо виконання умови оптимальності для другого опорного плану. Цей план також неоптимальний, оскільки . Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:

В оцінковому рядку третьої симплексної таблиці немає від’ємних чисел, тобто всі і задовольняють умову оптимальності. Це означає, що знайдено оптимальний план задачі:

або Х^* = (96; 236; 0; 0; 0; 0);

.

Отже, оптимальний план виробництва продукції передбачає випуск 96 одиниць продукції типу А та 236 одиниць продукції типу В. Випуск продукції виду С і Д за оптимальним планом не передбачається (економічно не вигідний). Максимальний прибуток за даних умов складає 3128 гр.од. При цьому час роботи верстатів використовується повністю (х₅ = х₆ = 0).