Двоетапний метод штучного базису.

Нехай маємо КЗЛП:

, , де .

(1.5.1)

 

Розглянемо допоміжну КЗЛП:

 

, , , … , .

(1.5.2)

 

або у матричному вигляді

,

,

,

де — одинична матриця розміру .

Цільову функцію цієї задачі можна розглядати як міру недопустимості при перевірці виконання обмежень задачі. Коли , тоді . Тому оптимальний базисний розв’язок цієї задачі буде допустимим для задачі (1.5.1).

Нехай, як і раніше, — допустима множина початкової КЗЛП (1.5.1), а — допустима множина допоміжної КЗЛП (1.5.2) і нехай .

Розв’язуємо задачу (1.5.2) симплекс-методом з початковим базисним розв’язком та з одиничним базисом (за умовою всі ).

Оскільки , то можливі два випадки:

а) . Це можливо тоді і тільки тоді, якщо всі .

Отже, оптимальний базисний розв’язок допоміжної КЗЛП має вигляд:

.

Оскільки — базисний розв’язок, то серед , не більше відмінних від нуля.

Отже, вектор і буде допустимим базисним розв’язком задачі (1.5.1).

б) . Це можливо лише у тому випадку, коли хоча б одна з компонент оптимального базисного розв’язку додатна (відмінна від нуля).

Доведемо, що у цьому випадку початкова задача (1.5.1) не має жодного розв’язку (допустима множина порожня).

Доведемо це від супротивного. Нехай допустимий (не обов’язково базисний) розв’язок початкової КЗЛП (1.5.1), .

Тоді — допустимий розв’язок допоміжної КЗЛП (1.5.2) ().

Але при цьому , що суперечить тому, що .

Приклад 1.12. Розв’язати ЗЛП:

, , , .

(1.5.3)

 

Побудуємо допоміжну ЗЛП:

, , , .

(1.5.4)

 

Приймемо за початковий базисний розв’язок з базисом . Розв’яжемо задачу (1.5.4) (табл. 1.15):

Таблиця 1.15.

↓

№

Базис

– 1

– 1

←

– 1

– 1

– ½

3/2

½

– 1

– 1

– 28

– 3

– 1

– 2

– 1/2

3/2

1/2

←

– 1

5/2

–5/2

-1

-1

–2/5

2/5

– 10

– 5/2

5/2

3/10

1/2

-1

–2/5

2/5

 

Отже, оптимальний розв’язок задачі (1.5.4) є . Серед базисних векторів немає штучних. Таким чином, вектор є початковим базисним розв’язком задачі (1.5.3). Його базис складають вектори .

Для побудови початкової симплекс-таблиці задачі (1.5.3) скористаємося останньою частиною таблиці (1.15), але замінимо елементи стовпчика та числа над стовпчиками відповідно до даних цільової функції задачі (1.5.3) (табл. 1.16).

Таблиця 1.16.

№	Базис				– 2
		– 2				–1

 

Оскільки всі оцінки невід’ємні, то початковий базисний розв’язок виявляється і оптимальним для ЗЛП (1.5.3):

.

Цей метод носить назву двоетапного методу штучного базису. Він дозволяє знайти оптимальний розв’язок початкової задачі у два етапи. На першому етапі розв’язується допоміжна КЗЛП (1.5.2) з одиничним базисом. Якщо до базису, який відповідає оптимальному розв’язку допоміжної задачі, не входять штучні вектори, тоді цей базисний розв’язок приймається за початковий для задачі (1.5.1). На другому етапі розв’язуємо симплекс-методом задачу (1.5.1). Якщо до оптимального базису задачі (1.5.2) входять штучні вектори, тоді задача (1.5.1) буде нерозв’язуваною.

Існує інший метод, який дозволяє одночасно з пошуком початкового базисного розв’язку знайти її оптимум. Це – М-метод.

2. М-метод розв’язування КЗЛП.

Нехай маємо КЗЛП (1.5.1) з .

Як і у двоетапному методі штучного базису, який розглядався вище, в систему обмежень вводимо штучні змінні для отримання повного одиничного базису. Але при цьому цільова функція будується інакше. Допоміжна М-задача має вигляд:

, , ,

(1.5.5)

де — достатньо велике число.

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

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

.

У симплекс-таблиці вводяться два рядка для запису та . Розв’язування М-задачі ведеться по рядку оцінок до тих пір, поки існують , а потім по рядку згідно з правилами симплекс-методу.

Розв’язуючи КЗЛП (1.5.5), можна отримати три варіанта відповіді:

а) у оптимальному розв’язку М-задачі всі .

В цьому випадку оптимальним розв’язком початкової задачі (1.5.1) є вектор .

Дійсно, нехай — довільний допустимий розв’язок задачі (1.5.1). Тоді — допустимий розв’язок задачі (1.5.5).

Оскільки — оптимальний розв’язок задачі (1.5.5), то маємо

де .

Нерівність і доводить оптимальність .

б) у оптимальному розв’язку М-задачі хоча б одна із штучних координат .

В цьому випадку можна довести, що початкова задача не має жодного допустимого розв’язку ().

в) при достатньо великих цільова функція задачі (1.5.5) необмежена на допустимій множині: . Тоді і початкова задача нерозв’язувана, тобто .

Зауважимо, що у М-методі, константі не обов’язково придавати якесь конкретне значення. Достатньо вимагати, щоб у процесі розв’язування при порівнянні з будь-яким конкретним числом, було більше.

Для розв’язування М-задачі з використанням ЕОМ можна брати за будь-яке число таке, що .

Приклад 1.13.

,

,

,

.

Побудуємо М-задачу:

,

,

,

.

.

Початковий базис М-задачі складається з штучних одиничних векторів (при штучній змінній ) та (при штучній змінній ). Початковий базисний розв’язок .

Розв’язування М-задачі наведено у таблиці 1.17.

Таблиця 1.17

№	Базис
					-1	-3
				-1	-2	-1
			-15	-3

Зручно записувати оцінку у такому вигляді .

Оцінка . Значить , а .

, , .

, , .

, , .

, , .

, , .

Оцінки записуємо у рядок з номером „3” симплекс-таблиці, а - у рядок з номером „4”. Так як у рядку з оцінками існує одна від’ємна оцінка , тоді вводимо до базису вектор , а виведемо з базису вектор та переходимо до наступного базисного розв’язку (табл. 1.18).

 

Таблиця 1.18.

№	Базис

 

Вибираємо , змінюємо базис і переходимо до нового базисного розв’язку (табл.1.19).

Таблиця 1.19.

№	Базис
					-1

 

Оскільки всі , тоді переходимо до оцінок у рядку з номером „3”. Вводимо до базису вектор , виводимо та знаходимо новий базисний розв’язок (табл. 1.20).

Таблиця 1.20.

№	Базис

 

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

Зауваження. Якщо в КЗЛП є одиничні вектори, але їх не вистачає для формування базису, тоді в задачу вводиться стільки штучних змінних, скільки не вистачає одиничних векторів. Причому вибір обмежень, в які вводяться штучні змінні, визначається структурою одиничних векторів, яких не вистачає. (В усіх базисних одиничних векторах одиниці мають стояти на різних місцях.)