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

(М-метод, метод великих штрафів)

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

Ключеві слова: базис, одинична матриця, розширена М-задача, штучні змінні.

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

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

Ідея методу:

1. Будуємо розширену М-задачу

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

{X₁, X₂, … , X_n, S₁, S₂, … , S_m}

«природні» «штучні»

змінні змінні

2. в водимо ці всі змінні в цільову функцію з великим додатним коефіцієнтом М

1. вирішуємо отриману М-задачу симплексом-методом. При рішенні використовуємо «штучний» базис для одержання вихідного опорного рішення, а потім виводимо з базису «штучні» змінні якомога швидше.

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

Теорема:

1. Якщо в оптимальному рішенні М-задачі всі «штучні» змінні дорівнюють нулю, тобто S_i=0, i= то відповідне рішення є оптимальним рішення вихідної задачі.

2. Якщо мається оптимальне рішення М-задачі, у якому хоч одна зі штучних змінних відмінна від нуля, то система обмежень вихідної задачі несумісна в області припустимих рішень.

3. Якщо М-задача виявилася нерозв'язною (Z), то початкова задача також нерозв'язна або через несумісність системи обмежень в ОДР, або через необмеженість функції Z (Z_max).

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

Приклад. Знайти мінімум функції при умовах

.

Рішення. Приведемо умову задачі до канонічної форми: знайти максимум функції при умовах

.

Серед змінних задачі тільки дві ( ) мають одиничні стовпці і будуть входити до базису. Тому додамо до умови задачі штучну невідємну змінну та розглянемо розширену М-задачу:

Розширена задача вже має систему з трьох одиничних векторів , , та має опорний план Х=(0; 0; 0; 24; 22; 0; 10).

Складаємо симплекс-таблицю (таблиця 6) та знаходимо оптимальне рішення розширеної М-задачі.

Таблиця 6

Сбаз		Хбаз		0	2			-3	6		1		0			0	-М
				аіо	х1			х2	х3		х4		х5			х6
1 0 -М	х4 х5		24 22 10			2 1 1	1 2 -1			-2 4 2		1 0 0		0 1 0	0 0 -1			0 0 1		- 22/4 10/2
			24-10М			-М	4-М			-8-2М		0		0	М			0
1 0 6	х4 х5 х3		34 2 5			3 -1 1/2	0 4 -1/2			0 0 1		1 0 0		0 1 0	-1 2 -1/2			1 -2 1/2
			64			4	0			0		0		0	-4			4+М
1 0 6	х4 х6 х3		35 1 11/2			5/2 -1/2 1/4	2 2 1/2			0 0 1		1 0 0		½ ½ 1/4	0 1 0			0 -1 0
			68			2	8			0		0		2	0			М

За три ітерації отримано оптимальне рішення М-задачі:

М_опт=(0, 0, 11/2, 35, 0, 1, 0), .

Оскільки штучна змінна в рішенні цієї задачі дорівнює нулю ( = 0), то рішення вихідної задачі теж існує і його можна отримати з рішення розширеної М-задачі:

Х_опт=(0, 0, 11/2, 35, 0, 1),

значення цільової функції початкової задачі протилежне значенню цільової функції розширеної М-задачі, так як умова початкової задачі предполагає мінімізацію цільової функціі.