5 крок: користуючись Теоремою 1 *, перевірити базисне рішення на оптимальність:
Þякщо всі коефіцієнти цільової функції при небазисних змінних позитивні, а при базіснихравни нулю. то критерій оптимальності виконаний. Далі перейти до 6-му кроці алгоритму.
Þякщо в цільової функції знайдеться хоча б один негативний коефіцієнт сj перед небазисной змінної xj. тонайденное базисне рішення не є оптимальним. В цьому випадку, користуючись теоремою 3 *, досліджують можливість переходу до нового базисного рішення. Якщо отримали, що такий перехід можливий, то необхідно здійснити зміну однієї базисної змінної за схемою 1 *.
-Нехай в цільової функції при небазисной змінної xj коефіцієнт сj <0. Тогда для всех положительных коэффициентов aik . стоящих в столбце “xj ” симлекс-таблицы, вычисляют разрешающий коэффициент по формуле:
- Серед всіх дозвільних коефіцієнтів знаходять мінімальний. Нехай rp = min (ri). Тоді в p-му рядку таблиці проводять заміну вихідної базисної змінної на змінну xj.
- Після зміни однієї базисної змінної необхідно шляхом еквівалентних перетворень привести симплекс-таблицю до наступного вигляду:
-Тепер змінна xj буде базисної. Отримали нове базисне рішення. Його необхідно перевірити на оптимальність по теоремі 1 *. Якщо знайдене базисне рішення є оптимальним, то перейти до 6 кроці алгоритму. В іншому випадку необхідно провести зміну однієї базисної змінної за схемою 1 *.
6 крок: сформулювати висновки за результатами рішення З.Л.П.
Проілюструємо використання симплекс-таблиці для вирішення З.Л.П. наступного виду:
2 крок алгоритму: зведемо систему обмежень до системи лінійних рівнянь шляхом додавання додаткових змінних х4 і х5:
3 крок алгоритму: в даному випадку, після введення додаткових змінних, в кожній з двох рівнянь системи вже присутня виділена змінна (х4 - в першому рівнянні і х5 - у другому).
4 крок алгоритму: заповнимо симплекс-таблицю (табл.1):
Базисне рішення має вигляд: (х1, х2, х3, х4, х5) = (0,0,0,2,1). Знайдене базисне рішення не є оптимальним, тому що не всі коефіцієнти цільової функції невід'ємні. Отже, необхідно здійснити зміну однієї базисної змінної. Для цього виберемо одну з змінних, при якій в цільової функції варто негативний коефіцієнт (наприклад, змінну х1) і зробимо для цієї змінної розрахунок дозволяють коефіцієнтів (Табл. 1).
Оскільки найменший з дозвільних коефіцієнтів стоїть на другому рядку таблиці, то необхідно замінити базисну змінну х5 на змінну х1. Так як тепер х1 є базисної змінної, то необхідно шляхом еквівалентних перетворень отримати А11 = 0, з1 = 0 і а21 = 1.
В даному випадку, щоб отримати:
а21 = 1. необхідно розділити другий рядок таблиці на дозволяючий коефіцієнт;
А11 = 0. необхідно відняти з елементів першого рядка відповідні елементи другого;
з1 = 0. необхідно скласти другу і третю рядок таблиці.
Після зазначених перетворень отримаємо таблицю 2 (стор.28).
Отримали нове базисне рішення (х1, х2, х3, х4, х5) = (1,0,0,1,0). Виділене базисне рішення не доставляє максимуму цільової функції (не є оптимальним), так як не всі коефіцієнти цільової функції є невід'ємними числами.
Так перед змінної х2 в цільової функції варто коефіцієнт с2 = -2. Отже, необхідно провести зміну однієї базисної змінної. Але, оскільки в стовпці «х2» (Табл. 2) присутній тільки один позитивний коефіцієнт А12 = 2, що стоїть в першій стоці таблиці, то немає необхідності в розрахунку дозволяють коефіцієнтів. Можна відразу зробити висновок, що базисну змінну х4 необхідно замінити напеременную х2. Так як тепер х2 є базисної змінної, то необхідно шляхом еквівалентних перетворень отримати А12 = 1, с2 = 0 і а22 = 0.
В даному випадку, щоб отримати:
з1 = 0. необхідно скласти другу і третю рядок таблиці;
А12 = 1. необхідно розділити другий рядок таблиці на 2;
а22 = 0. необхідно додати до елементів другого рядка відповідні елементи першої, отримані після множення на 2;
Внесемо всі перетворення в таблицю 3.
По таблиці 3 складемо нове базисне рішення, прирівнюючи базисні змінні до вільних членам, небазисних - до нуля: (х1, х2, х3, х4, х5) = (3/2, 1/2, 0,0,0). Дане базисне рішення є оптимальним (по теоремі 1 *), так як всі коефіцієнти цільової функції є невід'ємні числа. Отже, знайдений базис буде доставляти максимальне значення цільової функції: f (x) = х1 + х2 - х3. Таким чином, max (f (x)) = 2 + 5х3 + х4 = 2. Поставлена З.Л.П вирішена.
Завдання для самостійного рішення
Завдання 1. Вирішити графічним методом задачу лінійного програмування. Знайти максимум і мінімум функції F (x) при заданих обмеженнях.
Завдання 2. Підприємство виробляє продукцію 2-х видів Р1 і Р2 з сировини 3-х видів а1, а2, а3. Запаси сировини рівні відповідно b1, b2, b3. Витрата i-го виду сировини (аi) на одиницю j-го виду продукції (Рj) дорівнює аij.
Знайти план виробництва, що забезпечує підприємству максимум доходу (значення всіх параметрів наведені в таблиці 1-9).
Вирішити задачу графічним способом.
Таблиця 1. Таблиця 2. Таблиця 3.
Потрібно знайти план завантаження верстатів, при якому випуск продукції буде максимальним (в грошовому вираженні).
4. Ромахін М.І. Елементи лінійної алгебри і лінійного программірованія.-М.: Вища школа, 1963.
5. Карасьов А.І. Кремер Н.Ш. Савельєва Т.І. Математичні методи і моделі в плануванні. -М.: Економіка, 1987.
6. Канторович Л.В. Жменька А.Б. Оптимальні рішення в економіке.-М.: Наука, 1972.