Так само числу
Ухилення точки x від площини (*) пропорційно відстань від точки x до цієї площини.
Таким чином, геометричний сенс задачі лінійного програмування полягає в знаходженні в многограннике? точки, яка найбільш (найменш) ухилився від площини (*).
. Про метод вирішення задачі лінійного програмування. Неважко зрозуміти, що звичайні методи класичного математичного аналізу для відшукання найбільшого (найменшого значення функції незастосовні до розглянутій задачі.
Ці методи, зводячи задачу до відшукування безлічі точок, «підозрілих на екстремум», і до порівняння значень функції в цих точках, стають малопридатними, якщо число таких точок велике.
Лінійна ж форма (2.1), визначена на многограннике?, заданому нерівностями (2.2), досягає свого найбільшого (найменшого) значення в деякій вершині цього багатогранника, так що безліч точок, «підозрілих на екстремум», є безліч всіх вершин багатогранника?, число яких зазвичай буває величезним.
Основним методом вирішення загальної задачі лінійного програмування, що дозволяє подолати ці труднощі, є так званий симплекс-метод Данцингом.
Симплекс-метод складається з алгоритму відшукання якого-небудь опорного серед рішень системи лінійних нерівностей (2.2), тобто рішення-вершини багатогранника? (Або з встановлення факту несумісності системи), і з алгоритму послідовного переходу від отриманого вже опорного рішення системи (2.2) до нового опорного рішенням, для якого форма (2.1) має більше (менша) значення (до отримання максимизирующего (минимизирующего), т. е. оптимального рішення).
Основу обчислювальної схеми симплекс-методу складають модифіковані жорданову винятку.
2.2 Симплекс-метод для відшукання опорного рішення системи лінійних нерівностей
. Перехід до таблиці. Форму (2.1) та умови (2.2) записуємо у вигляді такої таблиці (2.3):
... 1 ... .. ............ .. ............. .......... ........................ ... ..................... 0
Якщо серед обмежень (2.2) зустрічаються обмеження лише на знак змінної, тобто виду, то їх не включають в таблицю (2.3). При цьому заміною переводять кожне обмеження виду в обмеження виду.
Змінні, на знаки яких не накладені ніякі обмеження, називають вільними; змінні ж, на знаки яких накладені обмеження, називають невільними.
. Виняток вільних змінних. Будемо вважати, що всі змінні вільні і що ранг матриці коефіцієнтів системи (2.2) дорівнює n. Тоді за допомогою n послідовних кроків модифікованих Жорданових винятків можна буде перенести всі з верхнього рядка таблиці (2.3) в її лівий стовпець і на їх місце поставити відповідні. При цьому ніяких обмежень на вибір дозвільних елементів не накладається, лише б вони були відмінні від нуля.
Для зручності запису можна вважати, що на верх таблиці перекинуті, так що отримана, наприклад, таблиця (2.4)
... 1 ... .. ............ .. ............. .......... ........................ ... ................ .. ... .. ............ .. ............. .......... ........................ ... ................ .. ......??? ... .. ............. .......... ........................ ... ..................... Q
Вирази для замінених знадобляться лише після отримання рішення, щоб висловити його в старих координатах. Тому виписуємо окремо:
і продовжуємо надалі працювати лише з залишилася частиною таблиці (2.4):
... 1 ... .. ............ .. ............. .......... ........................ ... ................ .. ............ .. ............. .......... ........................ ... ..................... Q
Оскільки за умовою (2.2), то ми перейшли до наступної звичайної формулюванні задачі лінійного програмування:
Дана лінійна функція
і система нерівностей (обмежень)
Причому
З усіх невід'ємних розв'язків системи знайти таке, яке максимізує лінійну функцію
Приклад: Максимізувати форму
при виконанні обмежень
і при
Переходимо до таблиці
1=- 2-2-1-2=3-326=3-3-26=02-22z=- 1-1-10
Змінні невід'ємні, тому ми їх не виключаємо.
Перший рядок містить негативний вільний член. З негативних коефіцієнтів цього рядка вибираємо - 1. Зробивши крок модифікованого жорданова в...
