Алгоритм симплекс-методу

Теорія симплекс-методу дуже складна: математично улаштовуються формули, які застосовувані при рішенні задач, доводиться оптимальність одержуваного результату. Якщо ж не вникати в теорію методу, а користуватися розробленими алгоритмами, то розрахунки за допомогою симплекс-методу дуже прості і доступні для використання.

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

Розглянемо лінійну модель стандартної форми, що містить m рівнянь з n невідомими (m < n). Тоді всі припустимі екстремальні точки визначаються як всі однозначні невід’ємні рішення системи m рівнянь, у яких n - m змінних дорівнюють нулю.

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

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

Для розв’язування задачі ЛП симплекс-методом користуються алгоритмом, який складається з наступних кроків.

Крок 0. Приводять задачу до канонічного вигляду, і заносять коефіцієнти цільової функції і обмежень у симплекс–таблицю. Визначають початкове допустиме базисне рішення шляхом прирівнювання до нуля n небазисних змінних.

Коментарі до кроку 0.

Правила заповнення таблиці.

Стовпець “Базисні змінні” містить додаткові змінні пробного базису S₁, S₂, …, S_m. Їх числові значення приведені в стовпчику “Рішення”. При цьому припускається, що небазисні змінні х ₁, х ₂,..., х _n, яких немає в першому стовпці, дорівнюють нулю.

Усі складові цільової функцію переносять вліво и так заносять в симплекс-таблицю: F - с₁ х ₁ - с₂ х ₂ -... - с_пх _п = 0. В рядок “F-рівняння” заносяться коефіцієнти цільової функції у клітку відповідної змінної: в стовпчик “F” ® 1; в стовпчики “ х ₁”®“-с₁”, “ х ₂” ® “-с₂”,..., “ х _n”® ”-с_п”, а в стовпчики додаткових змінних S₁, S₂, …, S_m нулі, тому що таких змінних в цільової функції немає. Перемножуючи значення в відповідних клітках, одержимо значення цільової функції “0” і занесемо його в клітку “Рішення.”

Побудований план називається опорним (базисним).

Розглянемо приклад.

Відновити цільову функцію та систему обмежень за даною симплекс-таблицею.

В цій таблиці записано цільову функцію та три рівняння:

F – 3* x ₁ – 2* x ₂ + 0*S₁ + 0*S₂ + 0*S₃ = 0

Спростимо. F = 3 x ₁ + 2 x ₂

віднімаючи додаткові змінні одержимо

Крок 1. З числа поточних небазисних (рівних нулю) змінних вибирається за визначеним критерієм змінна, збільшення якої забезпечує поліпшення значення цільової функції. Цю змінну включають в новий базис, тобто записують в стовпчик “базисні змінні”. Якщо такої змінної не існує, то обчислення припиняються, тому що поточне базисне рішення є оптимальним. У протилежному випадку здійснюється перехід до кроку 2.

Коментарі до кроку 1.

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

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

Яку ж змінну треба ввести до базису, якщо в F- рівнянні є від’ємні коефіцієнти? При розв’язку задачі на отримання максимуму до базису вводиться та змінна, у якої найбільший по модулю від’ємний коефіцієнт в F-рівнянні (для мінімуму – додатний).

Крок 2. З числа базисних змінних вибирається та, яка виключається з базису. Вона прийме нульове значення, тобто стане небазисною.

Коментарі до кроку 2.

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

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

Крок 3. Знаходиться нове базисне рішення, що відповідає новим складам базисних і небазисних змінних. Здійснюється перехід до кроку 1.

Коментарі до кроку 3.

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

1) Ділимо всі елементи ведучого рядку на ведучий елемент, включаючи сам елемент.

2) Замість елементів ведучого стовпця записуємо “0”, крім “1” на місці ведучого елементу.

3) Останні елементи (включаючи елементи F-рівняння) знаходяться за правилом прямокутника.

			x i		Sk	...
F
Sg			а g i		а gk
Sj			а ji		а jk

Тобто елемент нової симплекс-таблиці, який лежить на перетину g -го рядку та k –го стовпця визначається за формулою:

Отриманий план знову перевіряється на оптимальність і якщо треба, то поліпшення плану проводиться до тих пор, поки не буде отримано оптимальний план. Нагадаємо, що ознакою оптимальності має бути наявність усіх додатних коефіцієнтів або нулів в рядку “F-рівняння”.

Пояснимо процедуру симплекс-методу на прикладі, який ми розглянули. У стандартній формі цільова функція та обмеження мають вигляд:

Точку А(0;0) можна використовувати як початкове припустиме рішення, тому що при х1 = х2 = 0 маємо S1 = 6 > 0; S2 = 8 > 0; S3 = 1 > 0; S4 = 2 > 0.

Зауваження. Так можна діяти в тих випадках, коли початковий базис складається з залишкових змінних, якщо при них знак "+".

Отримані результати представимо у вигляді таблиці.

Ця таблиця інтерпретується таким чином. Стовпець "Базисні змінні" містить змінні базису, який випробовується S₁, S₂, S₃, S₄, значення яких наведені в стовпці "Рішення". При цьому мається на увазі, що небазисні змінні х₁ і х₂ (не представлені в першому стовпці) дорівнюють нулю. Значення цільової функції Z = 3*0 + 2*0 + 0*6 + 0*8 + 0*1 + 0*2 = 0 дорівнює нулю, що і показано в останньому стовпці таблиці.

Як визначити, чи є отримане рішення найкращим (оптимальним)? Для відповіді на це питання використовується умова оптимальності. Змінна, що вводиться в задачі максимізації (мінімізації) є небазисна перемінна, що має в Z-рівнянні найбільший за модулем від’ємний (додатній) коефіцієнт. У випадку рівності таких коефіцієнтів для декількох небазисних змінних вибір робиться довільно. Якщо всі коефіцієнти при небазисних перемінних у Z-рівнянні невід’ємні (недодатні), то отримане рішення є оптимальним. Застосовуючи умову оптимальності до вихідної таблиці, виберемо в якості змінної, що включається в базис, змінну х₁. Змінна, що виключається, повинна бути обрана з сукупності базисних змінних S₁ , S₂ , S₃ і S₄ .Процедура вибору змінної, що виключається, припускає перевірку умов допустимості.

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

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

Базисні змінні¯	Z	x1 ведучий стовпець	x2	S1	S2	S3	S4	Рішення	Відношення
Z		-3	-2
S1									6/1 = 6
S2 ведучий рядок		[2]							8/2 = 4
S3		-1							-
S4									-

[2] – ведучий елемент. Виключається S₂.

Після того, як визначені змінні, що включається і виключається (з використанням умов оптимальності і допустимості), наступна ітерація здійснюється методом Гаусса-Жордана. Для цього ми ділимо S₂ – рівняння на ведучий елемент, що дорівнює "2". Потім відомим методом досягаємо того, щоб інші елементи ведучого стовпця стали дорівнювати нулю. У результаті одержимо нову симплекс-таблицю.

Базисні змінні¯	Z	x1	x2 ведучий стовпець	S1	S2	S3	S4	Рішення	Відношення
Z			-1/2		3/2
S1 ведучий рядок			3/2		-1/2
х1			½		½
S3			3/2		½
S4

У новому рішенні х₁ = 4, х₂ = 0 (точка В вказана на малюнку). Значення Z зросло з 0 до 12, при цьому нова симплекс-таблиця має ті ж характеристики, як і попередня: тільки небазисні змінні х₂ і S₂ дорівнюють нулю, а значення базисних змінних, як і раніш, представлені в стовпці "Рішення".

З останньої таблиці випливає, що на черговій ітерації, у відповідність з умовою оптимальності в якості змінної, яку вводять варто вибрати х₂, тому що коефіцієнт при цій змінній у Z-рівнянні дорівнює –1/2.

Виходячи з умови допустимості визначаємо, що змінною, яка виключається, буде S₁. Відношення, що фігурує в правій частині таблиці, вказує, що в новому базисному рішенні значення змінної, що включається х₂ буде дорівнювати 4/3 (=мінімальному відношенню).

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

Базисні змінні¯	Z	x1	x2	S1	S2	S3	S4	Рішення	Відношення
Z				1/3	4/3
х2				2/3	-1/3				4/3
х1				-1/3	2/3				10/3
S3				-1
S4				-2/3	1/3				2/3

У новому базисному рішенні x₁ = 10/3 і x₂ = 4/3 (т.С на малюнку). Значення Z збільшилося з 12 до 12 2/3.

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

Поиск по сайту: