5.3. Алгоритм методу штучного базису

1. Складаємо розширену задачу.

2. Знаходимо початковий опорний план розширеної задачі.

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

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

5.4. Приклад

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

Зведемо задачу до канонічної форми:

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

де

Кількість обмежень . Оскільки серед векторів не має двох одиничних векторів, то складаємо розширену задачу і вводимо штучні змінні .

де ─ деяке досить велике додатне число, конкретне значення якого не задається.

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

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

Після обмеженого числа ітерацій всі штучні змінні повинні бути виведені з базису.

Побудуємо симплекс-табл. 4.

Таблиця 4

i	Базис
1		─М	27	1	─1	4		─1	0	1	0
2		─М	24	2	3	─1	4	0	─1	0	1
m+1			0	1	3	4	2	0	0	0	0
m+2			─51	─3	-2	─3	─9	1	1	0	0

Обчислимо і :

У рядок записуємо 0, оскільки немає чисел без , а в рядок записуємо ─ 51. Аналогічно обчислюємо і заносимо їх у таблицю:

Оскільки в рядку серед величин є від’ємні, то початковий опорний план розширеної задачі не є оптимальним. Треба перейти до наступного опорного плану. Обчислення виконуємо за допомогою симплекс-методу, однак розв’язуваний стовпець обираємо серед елементів рядка. Розв’язуваний стовпець відповідає найбільшому за абсолютною величиною від’ємному елементу рядка – це 9. Вектор, який вводиться, – . Знаходимо величину Розв’язуваний рядок – перший. Розв’язуваний елемент дорівнює 5.

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

Використовуючи жорданові виключення перерахуємо елементи (табл.5).

Таблиця 5

i	Базис
1		─2					1		0		0
2		─М					0		─1		1
m+1							0		0		0
m+2							0		0		0
1		─2			0		1
2		─М			1		0
m+1					0		0		0

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

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

У базис вводимо вектор , а з базису виводимо вектор і перераховуємо елементи таблиці. В результаті отримуємо табл. 6.

Таблиця 6

i	Базис
1		─2	5	0			1
2		─1	2	1			0
m+1			─12	0			0	0

У табл. 6 всі . Опорний план 0, 0, 5, 0, 0) є оптимальним планом задачі і . Оскільки початкова задача була на мінімум цільової функції, то .