Короткі теоретичні відомості

Відведений час: 4 год.

Метод штучного базису

Мета: формувати уміння розв’язувати ЗЛП симплексним методом, зокрема методом штучного базису.

Завдання для практичного заняття:

1. Пригадайте основні теоретичні питання теми.

2. Орієнтовні запитання та завдання:

- у якому випадку застосовується метод штучного базису;

- формулюйте умову несумісності системи обмежень;

- з якими знаками («+» чи «-») штучні змінні вводяться у цільову функцію;

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

3. Виконайте індивідуальне завдання.

У попередній практичній розглядався випадок, коли у системі обмежень немає необхідної кількості одиничних незалежних векторів. У такому разі застосовується метод штучного базису. Цей метод полягає у тому, що у ті рівняння системи обмежень, де не вистачає базису вводять додаткові додатні змінні, які називаються штучними. Паралельно з введенням штучних змінних у систему обмежень, ними доповнюють цільову функцію. Штучні змінні мають коефіцієнт + М (для задачі на min) або – М (для задачі на max), де М — досить велике додатне число.

Розглянемо задачу лінійного програмування:

(2.20)

(2.21)

(2.22)

Задача подана в канонічному вигляді і система обмежень (2.21) не містить необхідної кількості лінійно незалежних одиничних векторів. Тоді вводимо до кожного рівняння в системі обмежень задачі додаткову змінну . Отримаємо:

(2.23)

У результаті додавання змінних у рівняння системи (2.21) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (2.23) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві.

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

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

.

Припускається, що величина М є досить великим числом.

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

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му – ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком. Штучний базис, виключений із базису в результаті деякої ітерації, надалі не має сенсу вводити в один з подальших базисів, і, отже, перетворення стовпців цього вектора зайве.

Ітераційний процес за (m+2)-им рядком ведуть доти, доки:

1) всі штучні вектори не будуть виключені з базису, тоді відшукання опорного плану початкової задачі продовжується за (m+1)-им рядком;

2) не всі штучні вектори виключені, але (m+2)-й рядок не містить більше від’ємних елементів у стовпцях, тоді, якщо елемент, що стоїть в (m+2)-ому рядку стовпця «План» від’ємний, то початкова задача не має розв’язку; якщо ж він дорівнює нулю, то знайдений опорний план початкової задачі є виродженим і базис містить принаймні один із векторів штучного базису.

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

Теорема. Якщо в оптимальному плані розширеної задачі штучні змінні , то план є оптимальним планом початкової задачі.

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

Дата добавления: 2017-02-01