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

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

при обмеженнях :

І серед векторів:

немає  одиничних.

Тоді, задачу (1) — (3) приводимо до еквівалентної задачі наступним чином:

де — достатньо велике число, значення якого, практично, не задається, а змінні називаються штучними. Тоді задачу (4) — (6) називають розширеною задачею по відношенню до задачі (1) — (3).

Вектори, що відповідають коефіцієнтам при штучних змінних, а саме:

metod_shtychnoho_bazusy101

називаються штучними векторами.

Тепер розширена задача матиме опорний план:

Маючи початковий опорний план, за допомогою симплекс методу ми отримуємо розв’язок розширеної задачі (4) — (6).

Теорема: якщо в оптимальному розв’язку розширеної задачі (4) — (6), штучні змінні , то пан буде служити оптимальним розв’язком задачі лінійного програмування (1) — (3).

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

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

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

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

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

Якщо в стовпці  стоїть значення 0, то дана задача є виродженою і її розв’язок містить принаймі один чи декілька штучних векторів.

Знаходження розв’язок задачі лінійного програмування методом штучного базису – приклад:

Знайти розв’язок задачі лінійного програмування методом штучного базису:

Записавши дану задачу у канонічній формі бачимо, що серед векторів системи обмежень є тільки два одиничних ( та ):

metod_shtychnoho_bazusy25

Тому в ліву частину третього рівняння системи введемо додаткову невід’ємну змінну і розглянемо розширену задачу, що полягає в максимізації функції:

при обмеженнях:

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

Метод штучного базису приклад

Початковий опорний плану розширеної задачі лінійного програмування

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

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

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

Метод штучного базису приклад

Рішення задачі лінійного програмування методом штучного базису – Ітерація №1

Як видно з таблиці, для початкової задачі опорним є план . Перевіримо його на оптимальність. Для цього розглянемо елементи четвертого рядка. У цьому рядку в стовпчику, який відповідає вектору міститься від’ємне число. Отже, даний опорний план не є оптимальним і може бути поліпшений завдяки введенню в базис вектора  та виключенню з нього вектора . Складаємо наступну симплекс таблицю:

Метод штучного базису приклад

Рішення задачі лінійного програмування методом штучного базису – Ітерація №2

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

Блок-схема алгоритму знаходження розв’язок задачі лінійного програмування методом штучного базису

Метод штучного базису блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*