3. Алгоритм симплексного методу

Алгоритмом називають точний опис послідовності виконання дій під час розв’язування задачі. Розрахунки на основі алгоритму виконують послідовно, крок за кроком. Схематично розрахунки симплексним методом складаються з наступних етапів:

1. Математичне формулювання умов задачі у вигляді систем нерівностей і рівнянь, а також логічна і формально математична перевірка несуперечливості умов і обмежень задачі.

2. Розв’язування задачі симплексним методом. При цьому можна виділити такі стадії:

а) зведення задачі до канонічної форми (системи рівнянь) і знаходження початкового варіанту допустимого плану;

б) перевірка знайденого варіанту плану на оптимальність (якщо знайдений варіант виявиться оптимальним, то розв’язок одержано, в іншому випадку план треба поліпшити);

в) послідовне поліпшення плану до одержання оптимального.

3. Одержаний план піддається глибокому економічному аналізу. До нього можуть бути внесені додаткові корективи в разі зміни умов виробництва.

На основі цього плану визначають економічну ефективність окремих технологічних процесів виробництва окремих видів продукції, ресурсів і т.д.

Вивчення алгоритму симплексного методу і ознайомлення із застосуванням цього методу в економіці почнемо із постановки і розв’язування невеликої конкретної задачі. Спочатку розглянемо програму вирахувань для задач, умови яких виражаються нерівностями типу “<=”. При цьому паралельно з вирахувальною процедурою буде даватися економічне пояснення процесу розв’язування, а також його проміжний і кінцевий результати.

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

Задача. Припустимо, що господарство займається вирощуванням наступних сільськогосподарських культур: озимої пшениці, гречки і картоплі, маючи такі ресурси: ріллі – 400 га, праці – 1800 людино-днів, механізованих ресурсів – 800 машино-змін. Виходячи із потреб площа посіву гречки не повинна перевищувати 50 га, а картоплі – 20 га. Мета виробництва – одержання максимального обсягу товарної продукції ( у вартісному виразі). Треба знайти оптимальну комбінацію посівних площ цих культур. У математичному формулюванні умов задачі використаємо нормативи затрат і виходу продукції для даного господарства, які наведені в табл.1.

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

Таблиця 1 – Нормативи затрат і виходу продукції

Культури	Затрати на 1 га посіву		Вартість товарної продукції з 1 га, грн.
	праці, людино-днів	Механізованих ресурсів, машино-змін
Озима пшениця	1	0,5	800
Гречка	2	1,0	950
Картопля	10	5,0	1200

Як же в цих умовах відшукати варіант, що забезпечує екстремальне (в даному разі максимальне) значення цільової функції?

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

У нашому прикладі невідомими величинами є посівні площі озимої пшениці, гречки та картоплі. Позначимо їх через х₁, х₂, х₃ і назвемо змінними задачі. Критерій оптимальності відповідно до вимог лінійного програмування має бути також сформульований математично. У даному випадку вартість товарної продукції визначається як сума добутків вартості товарної продукції з 1 га на посівну площу:

800х₁ + 950х₂ + 1200х₃.

Критерій оптимальності (цільову функцію, або функціонал задачі) позначимо через Z. У нашій задачі знаходимо максимум цільової функції, що записується так:

Z_max = 800х₁ + 950х₂ + 1200х₃

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

1. Загальна площа зернових (озимої пшениці і гречки) і картоплі не повинна перевищувати площу ріллі, тобто 400 га:

х₁+х₂+ х₃<= 400

2. Загальні витрати праці (в людино-днях) не повинні бути більшими від наявних ресурсів:

х₁+2 х₂+10 х₃<= 1800

3. Загальний обсяг механізованих ресурсів (в машино-змінах) не повинен перевищувати можливих ресурсів тракторного парку:

0,5 х₁+ х₂+5 х₃<= 800

4. Площа посіву гречки не повинна перевищувати 50 га:

х₂<= 50

5. Площа посіву картоплі не повинна перевищувати 20 га:

х₃<= 20

6. Площі не можуть бути від’ємними величинами:

х₁ >= 0; х₂ >= 0; х₃ >= 0

Отже умови задачі виражаються у вигляді такої системи нерівностей:

х₁+х₂+ х₃<= 400

х₁+2 х₂+10 х₃<= 1800

0,5 х₁+ х₂+5 х₃<= 800

х₂ <= 50

х₃ <= 20

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

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

х₁+х₂+ х₃ + х₄ = 400

х₁+2 х₂+10 х₃ + х₅ = 1800

0,5 х₁+ х₂+5 х₃ + х₆ = 800

х₂ + х₇ = 50

х₃ + х₈ = 20

Економічний зміст цих перетворень наступний. При розв’язанні задачі зовсім не обов’язково, щоби наявні виробничі ресурси були повністю використані. Більше того, може бути так, що математичний розрахунок на повне використання можливостей взагалі не реальний. В зв’язку з цим вводяться додаткові змінні, які виражають можливе недовикористання виробничих ресурсів. В нашій задачі х₄ означає розмір недовикористання ріллі, х₅ – людино-днів на кінно-ручних роботах, х₆ – машино-змін на механізованих роботах, х₇ – недовиконання плану посіву гречки, а х₈ – недовиконання плану посадки картоплі. Якщо ж в оптимальному плані який-небудь вид ресурсів буде використаний повністю, то відповідна змінна перетвориться в нуль. Введемо додаткові змінні і в рівняння цільової функції. Після цього вона прийме наступний вид:

8 00х₁ + 950х₂ + 1200х₃ + 0х₄ + 0х₅ + 0х₆ + 0х₇ + 0х₈ max

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

Таким чином, умови нашої задачі сформульовані в виді системи лінійних рівнянь, яка містить п’ять рівнянь з вісьмома змінними. Система, в якій n > m, тобто кількість змінних більша кількості рівнянь, має багато допустимих розв’язків.

Щоби почати пошук оптимального розв’язку, необхідно отримати будь-який розв’язок, який би задовільняв умові задачі. Такий розв’язок системи, де всі змінні невід’єні, називають допустимим. В більшості випадків при розв’язуванні задач лінійного програмування симплексним методом в якості початкового розв’язку вибирається такий, в якому додаткові змінні мають величину, рівну наявності ресурсів, а всі основні змінні прирівнюються до нуля. Такий розв’язок називають опорним (базисним) розв’язком, або опорним планом. Опорний варіант плану обов’язково знаходиться в числі базисних розв’язків. Слід зауважити, що, хоч задача лінійного програмування має незліченну кількість допустимих розв’язків, кількість базисних розв’язків обмежена. Це дає можливість вибирати оптимальний варіант з порівняно невеликої кількості розв’язків. Базисні розв’язки геометрично відповідають тільки вершинам опуклого многогранника. Схему пошуку оптимального плану будують так: спочатку визначають певний опорний план (як правило, він не є оптимальним); знайдений план перевіряють на оптимальність. Якщо опорний план виявився неоптимальним, обчислюють інший, кращий, який знову перевіряють на оптимальність, і т.д. до одержання оптимального варіанту. Симплексним методом передбачено таку схему розрахунків, коли на кожному етапі план поліпшується. Тому симплекс-метод називають також методом послідовного поліпшення плану.

Щоби приступити до розв’язування задачі, спочатку складаємо симплексну таблицю першого допустимого розв’язку (табл.2). Перша симплексна таблиця – це форма вираження першого опорного плану, коли основні змінні дорівнюють нулю, ресурси не використовуються і Z = 0. Тому, заповнюючи першу симплексну таблицю, додаткові змінні вважають базисними (х₄, х₅, х₆, х₇, х₈). Кожний рядок таблиці відповідає відповідному рівнянню системи в канонічній формі (у формі рівняння), хоч стовпчики розміщуються в іншій послідовності, чим досягається певних технічних зручностей у розрахунках.

Заповнення першої симплексної таблиці здійснюють так:

1. У перший стовпчик записують порядкові номера рівнянь (обмежень).

2. У другому стовпчику перелічують базисні змінні.

3. У третьому стовпчику записують оцінки базисних змінних, вказані у цільовій функції.

4. У четвертому стовпчику вказують вільні члени рівнянь (обсяги ресурсів).

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

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

У симплексних таблицях формальною ознакою оптимальності є зміст оцінного (індексного) рядка.

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

Таблиця 2 – Перша симплексна таблиця

i	Базисні змінні	Сj	Вільні члени	800	950	1200	0	0	0	0	0
				Х1	Х2	Х3	Х4	Х5	Х6	Х7	Х8
1	Х4	0	400	1	1	1	1	0	0	0	0
2	Х5	0	1800	1	2	10	0	1	0	0	0
3	Х6	0	800	0,5	1	5	0	0	1	0	0
4	Х7	0	50	0	1	0 1	0	0	0	1	0
5	Х8	0	20	0	0		0	0	0	0	1
m + 1			0	-800	-950	-1200	0	0	0	0	0

Наведений розв’язок в табл.2 (перша симплексна таблиця), є допустимим і одночасно базисним, чи опорним планом. Це найбільш простий розв’язок системи рівнянь відносно базисних додаткових змінних х₄, х₅, х₆, х₇, х₈, який без яких-небудь обчислень дозволяє отримати перший опорний план задачі.

Знайдений варіант плану хоч і є формально допустимий ( усі Х_j >= 0), але економічно неприйнятний, оскільки площі зернових (озимої пшениці, гречки) і картоплі дорівнюють нулю, продукція не виробляється, і тому цільова функція токож дорівнює нулю. Рівність додаткових змінних і вільних членів рівнянь показує, що наявні ресурси не використовуються. Даний розв’язок економічно інтерпретувати можна так: є виробничі ресурси, відомі способи їх використання і нормативи затрат, але виробництва немає, значить, і результат його рівний нулю.

Оскільки одержаний опорний план не є оптимальним, то його треба поліпшити.

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

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

Щоб визначити, яку з базисних змінних вивести, треба знайти мінімальне симплексне відношення, яке обчислюють діленням елементів стовпчика вільних членів (b_i) на відповідні коефіцієнти розв’язувального стовпчика. При цьому враховують тільки невід’ємні відношення. Рядок з найменшим симплексним відношенням вказує на змінну, яку слід вивести з базису. Цей рядок називають розв’язувальним.

Розрахуємо за першою симплексною таблицею відношення b_i/a_ij і знайдемо з них мінімальне.

У нашому прикладі min {b_i/a_ij}= min {400/1; 1800/10; 800/5; 20/1} =

min {400; 180; 160; 20}

Отже мінімальне симплексне відношення знаходиться у п’ятому рядку і відповідає змінній х₈.

Коефіцієнт на перетині розв’язувального рядка з розв’язувальним стовпчиком називають розв’язувальним елементом.

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

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

Так, ресурсу ріллі могло би вистачити на посів 400 га (400:1), ресурсів праці на кінно-ручних роботах – на посів 180 га (1800:10), а ресурсів праці для механізованих робіт – на посів 160 га (800:5). Однак площа посіву цієї культури не повинна перевищувати 20 га. Тому змінна х₃ буде дорівнювати 20 і повинна бути введена на місце змінної х₈, яка прийме нульове значення і буде виключена із базиса.

Поскільки замість змінної х₈ в базис вводиться змінна х₃, необхідно провести повний перерахунок першої симплексної таблиці, тобто знайти другий варіант плану.

Складаємо другу симплексну таблицю (табл.3).

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

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

Таблиця 3 – Друга симплексна таблиця

i	Базисні змінні	Сj	Вільні члени	800	950	1200	0	0	0	0	0
				Х1	Х2	Х3	Х4	Х5	Х6	Х7	Х8
1	Х4	0	380	1	1	0	1	0	0	0	-1
2	Х5	0	1600	1	2	0	0	1	0	0	-10
3	Х6	0	700	0,5	1	0	0	0	1	0	-5
1 4	Х7	0	50	0		0	0	0	0	1	0
5	Х3	1200	20	0	0	1	0	0	0	0	1
m + 1			24000	-800	-950	0	0	0	0	0	1200

Спочатку розраховується рядок змінної, яка вводиться в базисний стовпчик змінних. Цей рядок утворюється за допомогою ключового рядка попередньої таблиці і займає точно таке ж положення як і останній. Поскільки він розраховується першим в наступній (новій) таблиці, його називають початковим. Для того, щоби заповнити початковий рядок, необхідно елементи ключового рядка попередньої таблиці розділити на ключовий елемент і одержану частку записати у відповідну клітку наступної (нової) симплекс-таблиці.

Після цього заповнюємо початковий стовпчик у новій таблиці. В усі клітки цього стовпчика записуємо нулі, за винятком клітки, яка знаходиться на перетині початкового рядка і початкового стовпчика. У цій клітці завжди буде знаходитися число “1”, яке є часткою від ділення елемента, який знаходиться в цій клітці ключового рядка попередньої симплекс-таблиці на ключовий елемент, яким завжди є це ж саме число.

Використовуючи величини елементів початкового рядка можна робити перерахунок величини всіх інших рядків наступної таблиці, включаючи і m+1 рядок (індексний рядок) за формулою: