формули безпосередньо випливає, що перетворений елемент b ij дорівнює різниці творів елементів, розташованих на головної та побічної діагоналях, діленої на РЕ.
2. Ідея симплекс методу
Симплекс-метод, званий також методом поліпшення плану, є одним з універсальних методів вирішення завдань лінійного програмування.
Якщо задача лінійного програмування записана в канонічному вигляді
f = ОЈ c i x j (max)
ОЈ a ij x j = a i0 (i = 1, ..., m)
x j > 0 (j = 1, ..., n)
Тоді, якщо оптимальний план задачі існує, то він збігається принаймні з одним із опорних рішень системи. Це опорне рішення відшукується симплекс-методом в процесі упорядкованого перебору лише опорних рішень сістеми.В зв'язку з цим симплекс-метод і називають методом послідовного поліпшення плану. Пошук початкового опорного плану складає перший етап симплекс-методу. На другому етапі серед опорних планів відшукується оптимальний.
Розглянемо суть симплекс-методу. Якщо в системі m 1 , ..., x m , висловимо їх через вільні змінні x m +1 , ..., x n
x i = B i0 -ОЈ b ij x m +1 (i = 1, .., m)
Підставивши значення x i в цільову функцію, отримуємо:
f = b 00 - ОЈ b 0 j x m + j
Значення базисних змінних x i і цільової функції f повністю визначаються значеннями вільних змінних x m + j .
Покладемо, що все b i 0 > 0. Тоді план x 0 = (b 10 ; ...; b m 0 ; 0 ...; 0), отриманий при нульових значеннях вільних змінних x m + j , буде невироджених опорним, а відповідає йому значення функції f одно, як видно b 00.
Опорний план x 0 відповідає базису Б 0 = {x 1 ; ...; x m }. Для отримання іншого опорного плану перетворюють базис Б 0 в новий базис Б 1 , видаляючи з Б 0 одну змінну і вводячи замість неї іншу з групи вільних. При цьому в базисі Б 1 опорному плану x 1 відповідає значення f (x 1 ), не меншу f (x 0 ) . Діючи таким чином, переходять до близького до оптимального плану. Зважаючи на те що опорних планів не більш С, через кінцеве число кроків або приходять до оптимального плану, або встановлюють, що задача нерозв'язна.
лінійне програмування симплекс завдання
3. Побудова початкового опорного рішення
Рішення задач лінійного програмування вручну найбільш раціонально можна виконувати саме в табличній формі. У таблицю вписують систему обмежувальних рівнянь і цільову функцію у вигляді виразів, дозволених відносите льно початкового базису Б про = {Х 1 ; ...; х т } (табл. 2.). Лівий стовпець займають базисні змінні і цільова функція, а верхній рядок - вільні змінні. Нижній рядок, в яку вписані коефіцієнти цільової функції f, називають f- рядком або рядком цільової функції .. За стовпцем базисних змінних слід стовпець вільних членів. Іноді f-рядок поміщають відразу ж за заголовною рядком, а стовпець вільних членів в кінці; таблиці. Таблиці описаного виду називаються симплексними.
Таблиця 2
базисні змінні
1
вільні змінні
-x m +1 ...-x m + s < sub> ...-x n
x 1 =
...
x k =
...
x m =
b 10
...
b k0
...
b m0
b 11 ... b 1s ... B 1, n-m
..........................................
b k1 ... b ks ... b k, nm
..........................................
b m1 ... b ms ... B m, n-m
f =
b 00
b 01 ... b 0 s ... b 0, nm
Використовуються та інші форми симплексних таблиць, але прийнята нами форма є найбільш компактною і наочною. У ній міститься вся необхідна інформація про хід рішення задачі. Якщо, як передбачалося вище, все b i 0 > 0, то при нульових значеннях верхніх (вільних) змінних стовпець вільних членів дає значення базисних змінних опорного плану x про = (b 10 ; ...; b m 0 ; 0; ... 0) і відповідне значення b 00 цільової функції: f (х 0 ) = b 00 .
Від табличній записи легко перейти до звичайного запису рівнянь. Для цього треба помножити елементи b kj k-го рядка на відповідні змінні, що стоять в заголовній рядку (-x m + i ), отримані твори скласти і суму прирівняти x k Тоді
b ko * 1 + b k1 (-x m + l ) + ... + B ks {-x m + s ) + ... + B k , n-m (-x n ) = X k або x i = b i0 -ОЈ b ij x m +1.
4. Критерії оптимальності
Розглянемо послідовність вирішення завдань лінійного програмування симплекс-методом і викладемо її стосовно до задачі максимізації.
1. За умовою завдання складається її математична модель.
2. Складена модель перетворюється до канонічної форми. При цьому може виділитися базис з початковим опорним планом.
3. Канонічна модель задачі записується у формі симплекс-таблиці так, щоб всі вільні члени були невід'ємними. Якщо початковий опорний план виділений, то переходять до пункту 5.
4. Знаходять початковий опорний план, виробляючи сімплексні перетворення з позитивними вирішуючими елементами, які відповідають мінімальним симплексним відносинам, і не беручи до увагу знаки елементів f-рядки. Якщо в ході перетворень зустрінеться 0-рядок, всі елементи якої, крім вільного члена, нулі, то система обмежувальних рівнянь задачі несовместна. Якщо ж зустрінеться 0-рядок, в якій, крім вільного члена, інших позитивних елементів немає, то система обмежувальних рівнянь не має невід'ємних розв'язків.
5. Знайдений початковий опорний план досліджується на оптимальність:
а) якщо в f-рядку немає негативних елементів (не вважаючи вільного члена), то план оптимальний. Якщо при цьому немає і нульових, то оптимальний план єдиний; якщо ж є хоча б один нульовий, то оптимальних планів нескінченна безліч;
б) якщо в f-рядку є хоча б один негативний елемент, якому відповідає стовпець непозитивно елементів, то f в†’;
в) якщо в f-рядку є хоча б один негативний елемент, а в його стовпці є хоча б один позитивний, то можна перейти до нового опорно...
