Якщо серед векторів системи обмежень є рівно одиничних, то розв’язок задачі лінійного програмування можна отримати за допомогою симплекс методу. Однак, не завжди дана умова виконується. Відмітимо, що саме в такому випадку використовується метод штучного базису. Отже, нехай потрібно знайти максимальне значення цільової функції:
при обмеженнях :
І серед векторів:
немає одиничних.
Тоді, задачу (1) — (3) приводимо до еквівалентної задачі наступним чином:
де — достатньо велике число, значення якого, практично, не задається, а змінні називаються штучними. Тоді задачу (4) — (6) називають розширеною задачею по відношенню до задачі (1) — (3).
Вектори, що відповідають коефіцієнтам при штучних змінних, а саме:
називаються штучними векторами.
Тепер розширена задача матиме опорний план:
Маючи початковий опорний план, за допомогою симплекс методу ми отримуємо розв’язок розширеної задачі (4) — (6).
Теорема: якщо в оптимальному розв’язку розширеної задачі (4) — (6), штучні змінні , то пан буде служити оптимальним розв’язком задачі лінійного програмування (1) — (3).
Характерною ознакою симплекс таблиць застосованих до методу штучного базису є наявніст -го та -го рядків. Де -й рядок містить доданок без коефіцієнта , а -й — містить коефіцієнти при .
Початок розвя’зку в симплекс таблиці здійснюється по -му рядку (аналогічно, як і у симплекс методі по -му). І ітераційний процес продовжується до тих пір, поки:
- Усі штучні вектори не будуть виключені із базису.
- Елементи -го рядка не міститимуть від’ємних значень, і не всі штучні вектори виключені з базису.
В першому випадку знайдено деякий опорний план розширеної задачі, а знаходження оптимального плану ведеться за симплекс методом по -му рядку.
В другому випадку, якщо в стовпці знаходиться від’ємне значення, то задача лінійного програмування немає розв’язку.
Якщо в стовпці стоїть значення 0, то дана задача є виродженою і її розв’язок містить принаймі один чи декілька штучних векторів.
Знаходження розв’язок задачі лінійного програмування методом штучного базису – приклад:
Знайти розв’язок задачі лінійного програмування методом штучного базису:
Записавши дану задачу у канонічній формі бачимо, що серед векторів системи обмежень є тільки два одиничних ( та ):
Тому в ліву частину третього рівняння системи введемо додаткову невід’ємну змінну і розглянемо розширену задачу, що полягає в максимізації функції:
при обмеженнях:
Розширена задача має опорний план , що визначається системою трьох одиничних векторів: . Cклавши початкову симплекс таблицю, перевіримо даний опорний план на оптимальність. Відмітимо, що значення та в методі штучного базису, бчислюються аналогічно симплекс методу і складаються з двох доданків, один з яких містить , а інший – ні. Відмітимо, що, як уже зазначалося вище, для зручності число, що перебуває при записується в п’ятий рядок таблиці, а який не містить , в четвертий.
Початковий опорний плану розширеної задачі лінійного програмування
Далі, виходячи з того, що в п’ятому рядку таблиці міститься два від’ємних значення, можна зробити висновок, що опорний план розширеної задачі не є оптимальним, тому здійснюємо перехід до нового. Для цього, серед усіх від’ємних значень останнього рядка, вибираємо те, яке по абсолютній величині приймає максимальне значення: . В нашому випадку, таким буде значення, що міститься в сьомому стовпці, тобто вектор потрібно ввести в базис.
Щоб визначити вектор, що виключається з базису, знаходимо . Отже, вектор виключаємо з базису. Відмітимо, що даний вектор не треба вводити ні до одного з наступних базисів, тому надалі, стовпчик даного вектора не заповнюється.
На наступному кроці, переходимо до побудови наступної симплекс таблиці (містить лише чотири рядки, оскільки штучний вектор з базису виключений) та визначення всіх її коефіцієнтів згідно нового базису:
Рішення задачі лінійного програмування методом штучного базису – Ітерація №1
Як видно з таблиці, для початкової задачі опорним є план . Перевіримо його на оптимальність. Для цього розглянемо елементи четвертого рядка. У цьому рядку в стовпчику, який відповідає вектору міститься від’ємне число. Отже, даний опорний план не є оптимальним і може бути поліпшений завдяки введенню в базис вектора та виключенню з нього вектора . Складаємо наступну симплекс таблицю:
Рішення задачі лінійного програмування методом штучного базису – Ітерація №2
Переглянувши значення елементів четвертого оцінкового рядка, бачимо, що серед них немає від’ємних, тобто отриманий на другій ітерації план початкової задачі є оптимальним, значення цільової функції для якого дорівнює .