Алгоритм симплекс-методу та його реалізація за допомогою симплекс-таблиць

 

Алгоритм симплекс-методу застосовується для КЗЛП:

,

,

,

де і .

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

Алгоритм симплекс-методу складається з таких процедур:

1. Розкладаються вектори за базисом .

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

.

Розклад базисних векторів також відомий.

Для вектора : і .

Розклад інших небазисних векторів знаходиться за формулою:

, — базисна матриця.

Позначимо через номер ітерації. На першій ітерації .

2. Для кожного обчислюємо оцінку

.

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

Якщо є хоча б одна від’ємна оцінка , тоді переходимо на 3-й крок.

3. З’ясовуємо, чи існує хоча б одна оцінка , для якої всі .

Якщо така оцінка існує, тоді цільова функція КЗЛП необмежена зверху на допустимій множині. Кінець алгоритму.

Якщо ж таких оцінок немає (тобто для будь-яких є хоча б одна координата ), тоді переходимо на 4-й крок.

4. Вибираємо одну з . Нехай це буде і підраховуємо відношення для усіх , таких що .

Знаходимо мінімальне з цих відношень (нехай це буде -те відношення):

.

5. Переходимо до нового базисного розв’язку, базис якого отримується заміною вектора на .

Координати усіх векторів у новому базисі підраховуємо за формулами:

,

. . Повертаємося на 2-й крок алгоритму.

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

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

.

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

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

При проведенні розрахунків вручну, пов’язаних з розв’язуванням ЗЛП симплекс-методом, зручно усі обчислення на кожній ітерації записувати у симплекс-таблиці (табл. 1.5):

Таблиця 1.5.

								↓
	№	Базис					…		…
		…		…
							…		…
							…		…
	…	…	…	…	…	…	…	…	…	…
←							…		…
	…	…	…	…	…	…	…	…	…	…
							…		…
							…		…

 

- значення цільової функції при даному опорному розв’язку, тобто

.

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

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

,

,

,

.

Переходимо до канонічної ЗЛП:

,

,

,

.

Базисним розв’язком цієї задачі є, наприклад, вектор .

Очевидно, що ранг матриці

дорівнює 2.

Даний базисний розв’язок невироджений, бо він має 2 додатні координати.

.

Розкладаємо небазисні вектори за базисом:

,

.

При цьому з базисного розв’язку

.

Далі заповнюємо таблицю 1.6.

Таблиця 1.6.

№

Базис

– 4

– 15

– 12

– 2

←

– 4

2/3

7/3

– 4/3

1/3

– 1

2/7

3/7

– 4/7

1/7

– 3/7

– 12

1/3

2/3

1/3

– 1/3

– 20/3

– 7/3

10/3

8/3

 

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

Підраховуємо відношення:

.

. Отже, з базису виводимо вектор , а вводимо .

Заповнюємо симплекс-таблицю, що відповідає новому базисному розв’язку, при цьому координати усіх векторів у новому базисі обчислюємо за правилами, описаними у пункті 1.4.1:

Таблиця 1.7.

№	Базис			– 4	– 15	– 12	– 2
		– 15	2/7	3/7			– 4/7	1/7	– 3/7
		– 12	1/7	– 2/7			5/7	– 3/7	2/7
			– 6

 

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

 

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

,

,

,

.

Переходимо до канонічної ЗЛП:

,

,

,

.

Базисний розв’язок .

. Враховуючи зауваження 1, заповнюємо таблицю 1.8.

Таблиця 1.8.

↓

№

Базис

←

– 1

1/5

– 1/5

1/5

1/5

– 8

– 1

– 2

 

Базисному розв’язку відповідає нульове значення цільової функції. Оскільки не виконуються умови теорем 1.4.3 та 1.4.4, переходимо до наступного базисного розв’язку у таблиці 1.9.

Таблиця 1.9.

↓

№

Базис

2/5

– 1/5

1/5

1/5

←

18/5

11/5

9/5

–1/5

18/11

9/11

–1/11

5/11

16/5

– 13/5

– 2/5

8/5

 

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

Таблиця 1.10.

№	Базис
			8/11			4/11	2/11	1/11
			18/11			9/11	-1/11	5/11
			82/11			19/11	15/11	13/11

 

За даними таблиці 1.10 видно, що виконується критерій оптимальності (всі ). Оптимальним базисним розв’язком є вектор , якому відповідає максимальне значення цільової функції .

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

Приклад 1.11. Для виробництва трьох видів продукції А, В, С використовується три види ресурсів, запаси яких відповідно дорівнюють 60, 36 та 80 умовних одиниць. Норми витрат ресурсів на одиницю продукції наведено у таблиці 1.11.

 

Таблиця 1.11.

Продукти   Ресурси	А	В	С
І
ІІ
ІІІ

 

Ціна одиниці продукції виду А – 10 грн., виду В – 5 грн. та виду С – 12 грн. Знайти оптимальний план виробництва продукції.

Побудуємо модель задачі. Змінні , означають кількість продукції відповідно виду А, В та С. Цільову функцію – виручку від реалізації продукції – запишемо так:

.

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

,

,

,

а також невід’ємністю змінних

.

Розглянемо КЗЛП:

,

,

,

,

.

Економічний зміст додаткових невід’ємних змінних - залишки відповідно першого, другого та третього виду ресурсів.

Початковий базисний розв’язок задачі - , якому відповідає базис

.

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

Таблиця 1.12.

№	Базис
				-10	-5	-12

 

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

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

Так, означає, що при виробництві одиниці продукції виду А буде забезпечено збільшення виручки на 10 грн. Якщо включити до плану по одному виробу виду В і С, тоді загальна виручка збільшиться відповідно на 5 грн. або 12 грн. Тому з економічної точки зору доцільно включити до плану виробництво саме продукту виду С.

Те ж саме необхідно зробити і згідно з правилами симплекс-методу. Введення до базису вектора говорить про те, що необхідно розпочати виробництво продукції виду С. Яку ж максимальну кількість цього продукту можна виробляти з урахування запасів ресурсів та норм їх витрат? Для відповіді на це питання знаходимо відношення

= 60, = 18, =40,

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

В результаті виробництва 18 одиниць продукту С запас другого ресурсу буде повністю використаний, тому змінна і стає небазисною. Згідно алгоритму симплекс-методу вектор виводимо з базису та переходимо до нового базисного плану (табл. 1.13).

Таблиця 1.13.

№	Базис
								-1
				-4

 

Наступний базисний план - , якому відповідає значення цільової функції .

З економічної точки зору новий план означає, що виробництво продукту виду С у кількості 18 одиниць забезпечить виручку 216 грн. Залишок першого ресурсу – 42 умовні одиниці, третього – 44, а другий ресурс використовується повністю.

Якщо у таблиці 1.12 елементи стовпчика означали запаси ресурсів, а елементи стовпчиків , , - нормативи витрат ресурсів, тоді у таблиці 1.12 економічний зміст цих стовпчиків став більш складним. Наприклад, число у стовпчику означає на скільки треба зменшити виробництво продукту С, якщо запланувати виробництво одиниці продукції виду . Числа та 4 у першому та третьому рядках стовпчика показують відповідно, скільки треба ресурсів першого та третього виду для включення до плану одиниці продукції виду . Число –4 у четвертому рядку стовпчика показує на скільки буде збільшена виручка підприємства, якщо запланувати виробництво одиниці продукції . Таким чином числа та 4 треба розглядати як нові нормативи витрат першого та третього ресурсів на виробництво одиниці продукції . Аналогічний економічний зміст у елементів стовпчика .

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

З економічної інтерпретації елементів таблиці 1.13 випливає, що знайдений план не є оптимальним. Якщо розпочати ще виробництво і продукту виду , тоді виручка буде збільшена на величину 4 , де - об’єм виробництва цього продукту, який визначається як

.

На величину випуску продукту найбільшою мірою вплинув запас третього виду ресурсу. Таким чином вводимо до базису вектор , а виводимо вектор та переходимо до нового базисного плану (табл. 1.14).

Таблиця 1.14

№	Базис
			25,5
			12,5

 

Новий базисний план ,якому відповідає значення цільової функції .

З економічної точки зору новий план означає, що виробництво продукту А складає 11 одиниць, продукту С – 12,5 одиниць, а продукт В не виробляється. В результаті такого плану другий та третій ресурси витрачаються повністю, а залишок першого ресурсу складає 25,5 умовних одиниць. У порівнянні з попереднім планом виручка зросла на 44 грн. і складає 260 грн.

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