Лабораторна робота № 2. Обчислювальні методи лінійного програмування.

При кількості змінних більш трьох задача не може бути вирішена геометрично. Однак ідея одержання рішення зберігає зміст і для випадку багатьох змінних.

2.1. Загальна ідея симплекс-метода.

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

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

Алгоритм симплекс-методу вимагає привести задачу ЛП до канонічного вигляду, тобто:

1) всі обмеженнязаписуються у вигляді рівностей з невід’ємною правою частиною;

2) значення всіх змінних мають бути невід’ємними.

Будь-яку лінійну модель можна привести до канонічного вигляду, використовуючи такий спосіб:

• Обмеження у вигляді нерівностей типу  () можна представити у вигляді рівності, додаючи залишкову (віднімаючи надлишкову) додаткову змінну до лівої частини обмеження.

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

• Будь-яку змінну, що не має обмеження в знаку, можна представити як різницю двох невід’ємних змінних , де.

Приклад. Представити у канонічній формі наступну задачу ЛП.

.

Здійснивши зазначені операції приведемо вихідну модель до канонічного вигляду:

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

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

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

Розглянемо лінійну модель стандартної форми, що містить 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	х1	xi ...	хп	S1	...	Sm	Рішення	Відношення
F	1	-с1	max	сп	0	0	0	0		F-рівняння
S1	0	а11	а1і	а1п	1	0	0	b1		S1-рівняння
…	0	...	...	...	0	1	0	...	…
Sj	0	аj1	аji	аjn	0	0	1	bj	min	Ведучий рядок
Sm	0	аm1	аmi	аmm	0	0	0	bm		Sm-рівняння

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

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

Базисні змінні	F	x1	x2	S1	S2	S3	Рішення
F	1	-3	-2	0	0	0	0
S1	0	1	2	1	0	0	6
S2	0	2	1	0	1	0	8
S3	0	-1	1	0	0	1	1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

			xi		Sk	...
F
Sg			аgi		аgk
Sj			аji		аjk

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

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

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

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

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

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

Базисні змінні	Z	x1	x2	S1	S2	S3	S4	Рішення	Відно-шення
Z	1	-3	-2	0	0	0	0	0		Z-рівняння
S1	0	1	2	1	0	0	0	6		S1-рівняння
S2	0	2	1	0	1	0	0	8		S2-рівняння
S3	0	-1	1	0	0	1	0	1		S3-рівняння
S4	0	0	1	0	0	0	1	0		S4-рівняння

Ця таблиця інтерпретується таким чином. Стовпець "Базисні змінні" містить змінні базису, який випробовується 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	1	-3	-2	0	0	0	0	0
S1	0	1	2	1	0	0	0	6	6/1 = 6
S2 ведучий рядок	0	[2]	1	0	1	0	0	8	8/2 = 4
S3	0	-1	1	0	0	1	0	1	-
S4	0	0	1	0	0	0	1	2	-

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

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

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

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

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

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

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

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

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

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