Нерівності будь-якого типу (зі знаками нерівностей <или>) Можна перетворити
в рівності шляхом додавання в ліву частину нерівностей додаткових змінних - залишкових або ізбиточних1, які пов'язані з нерівностями типу "<"
і ">" відповідно.
Для нерівностей типу "<" в левую часть неравенства вводится неотрицательная
залишкова змінна. Наприклад, в моделі компанії Reddy Mikks (приклад 2.1.1)
обмеження на кількість сировини Ml задається у вигляді нерівності 6х, + 4х2 <24. Вводя новую неотрицательную переменную s. которая показывает остаток
(Неспользованное кількість) сировини Ml, це обмеження перетворюється в рівність
6х, + 4 ^ 2 + s, = 24, s,> 0.
Нерівності типу ">" в задачах ЛП зазвичай встановлюють нижню межу чогось. Надлишкова змінна визначає перевищення значення лівої частини
нерівності над цією межею. Так, в моделі "дієти" (приклад 2.2.2) нерівність
xi + х2> 800 показує, що добове виробництво харчової добавки не повинно
бути менше 800 фунтів. Математично це нерівність еквівалентно рівності
х, + х2 - Sj = 800, S,> 0.
Позитивне значення надлишкової змінної S, показує перевищення
добового виробництва добавки над мінімальним значенням в 800 фунтів.
Важливо ще раз підкреслити, що додаткові змінні - залишкова st
і надлишкова S, - завжди невід'ємні.
Праву частину рівності завжди можна зробити неотрицательной, помноживши всі
рівність на -1. Крім того, зауважимо, що нерівність типу "<" также преобразуется в неравенство типа ">"За допомогою множення обох частин нерівності на -1.
Наприклад, нерівність -jc, + х2 <-3 эквивалентно равенству
-хх + ХГ + в1 = -3, з,> 0.
Тепер, множачи обидві частини цієї рівності на -1, отримаємо рівність з неотріца-
котельної правою частиною: х, - х2 - s, = 3.
5. Алгоритм симплекс методу
Алгоритм симплекс-методу знаходить оптимальне рішення, розглядаючи обмежена кількість допустимих базисних рішень. Алгоритм симплекс-методу завжди починається з деякого допустимого базисного рішення і потім намагається знайти інше допустиме базисне рішення, "поліпшує" значення цільової функції. Це можливо тільки в тому випадку, якщо зростання будь-якої нульовий (небазисной) змінної веде до поліпшення значення цільової функції. Але для того, щоб небазисная змінна стала позитивною, треба одну з поточних базисних змінних зробити нульовий, тобто перевести в небазисних. Це необхідно, щоб нове рішення містило в точності m базисних змінних. Відповідно до термінології симплекс-методу обрана нульова змінна називається вводиться (в базис), а видаляється базисна змінна - исключаемой (з базису).
Два правила вибору вводяться і виключають змінних в симплекс-методі назвемо умовою оптимальності іумов допустимості. Сформулюємо ці правила, а також розглянемо послідовність дій, які виконуються при реалізації симплекс-методу.
Умова оптимальності. Введеної перемінної в завданню максимізації (мінімізації) є небазисная змінна, яка має найбільший негативний (позитивний) коефіцієнт в z-рядку. Якщо в z-рядку є кілька таких коефіцієнтів, то вибір введеної перемінної робиться довільно. Оптимальне рішення досягнуто тоді, коли в z-рядку всі коефіцієнти при небазисних змінних будуть невід'ємними (непозитивним).
Умова допустимості. Як в задачі максимізації, так і в задачі мінімізації як исключаемой вибирається базисна змінна, для якої відношення значення правої частини обмеження до позитивного коефіцієнту ведучого шпальти мінімально. Якщо базисних змінних з такою властивістю кілька, то вибір исключаемой змінної виконується довільно.
Послідовність дій, які виконуються в симплекс-методі.
Крок 1. Знаходиться початкова дозволене базисне рішення.
Крок 2. На основі умови оптимальності визначається вводиться змінна. Якщо вводяться змінних немає, обчислення закінчуються.
Крок 3. На основі умови допустимості вибирається исключаемая змінна.
Крок 4. Методом Гаусса-Жордана обчислюється нове базисне рішення. Перехід до кроку 2.
Обчислення в симплекс-методі виконуються ітераційно в тому сенсі, що умови оптимальності і допустимості, а також обчислення застосовуються до поточної симплекс-таблиці, в результаті чого виходить наступна таблиця. Ми будемо називати послідовні симплекс-таблиці ітераціями.
ШТУЧНЕ ПОЧАТКОВЕ РІШЕННЯ
У прикладі 3.3.1 при початковому допустимому базисному рішенні гарантірова-
лось, що всі наступні базисні рішення, одержувані при виконанні симплекс-методу, також будуть допустимими. У завданнях лінійного програмування,
де всі обмеження є нерівностями типу "<" (с неотрицательной правой
частиною), додаткові (залишкові) змінні дозволяють сформувати початкова дозволене базисне рішення. Природно, виникає питання: як знайти
початкова дозволене базисне рішення в задачах ЛП, де є обмеження у вигляді
рівності або нерівностей типу ">"?
Найбільш загальним способом побудови початкового допустимого базисного рішення задачі ЛП є використання штучних змінних. Ці змінні в першій ітерації грають роль додаткових залишкових змінних, але
на наступних ітераціях від них звільняються. Розроблено два тісно пов'язаних між собою методу знаходження початкового рішення, які використовують
штучні змінні: М-метод5 і двоетапний метод.
Нехай задача ЛП записана в стандартній формі (див. Розділ 3.1). Для будь-якого рівності i, в якому не міститься додаткова залишкова змінна, введемо
штучну змінну Д, яка далі увійде в початкове базисне рішення. Але, оскільки ця змінна штучна (іншими словами, не має ні-
якого "фізичного сенсу" в даній задачі), необхідно зробити так, щоб на
подальших ітераціях вона звернулася в нуль. Для цього в вираз цільової
функції вводять штраф.
Мінлива R, за допомогою досить великого позитивного числа М штрафується шляхом введення в цільову функцію вираження -MRj в разі максимізації
цільової функції і вирази + MR, - в разі мінімізації. Внаслідок цього
штрафу природно припустити, що процес оптимізації симплекс-методу
призведе до нульового значення змінної Д. Наступний приклад прояснює дета-
Чи цього методу.
7. Двоетапний метод.
Двоетапний метод позбавлений недоліків, які притаманні М-методу внаслідок
помилок округлення. Як випливає з назви цього методу, процес вирішення завдання ЛП розбивається на два етапи. На першому етапі ведеться пошук початкового допустимого базисного рішення. Якщо таке рішення знайдено, то на другому етапі вирішується вихідна завдання.
Етап 1. Завдання ЛП записується в стандартній формі, а в обмеження додаються необхідні штучні змінні (як і в М-методі)
для отримання початкового базисного рішення. Вирішується задача ЛП
мінімізації суми штучних змінних з вихідними обмеженнями. Якщо мінімальне значення цієї нової цільової функції
більше нуля, отже, вихідна задача не має допустимого рішення, і процес обчислень закінчується. (Нагадаємо, що позитивні значення штучних змінних вказують на те,
що вихідна система обмежень несумісна.) Якщо нова цільова функція дорівнює нулю, переходимо до другого етапу.
Етап 2. Оптимальне базисне рішення, отримане на першому етапі, використовується як початкова дозволене базисне рішення вихідної задачі.
8. Особливі випадки застосування симплекс-методу.
чотири особливих випадки, що зустрічаються при використанні симплекс-методу.
2. Альтернативні оптимальні рішення.
3. Необмежені рішення.
4. Відсутність допустимих рішень.
При вивченні цих випадків основну увагу ми приділимо, по-перше, теоретичного обгрунтування причин, що призводять до таких ситуацій, і, по-друге,
їх практичним інтерпретацій стосовно до реальних завдань.