Послідовність рішення завдань лінійного програмування симплекс-методом

Введення

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

Методи рішення задач лінійного програмування відносяться до обчислювальної математики. З ростом потужності комп'ютерів необхідність застосування витончених методів обчислення знижується, оскільки в багатьох випадках час рахунку перестає бути лімітуючим фактором, оскільки вельми мало (частки секунд). Можна виділити лише три таких методу.

1. Простий перебір. Візьмемо деякий багатовимірний паралелепіпед, в якому лежить багатогранник, що задається обмеженнями. Як його побудувати? Наприклад, якщо є обмеження типу 2Х 1 + 5Х 2 ≤ 10, то, очевидно, 0 ≤ Х 1 ≤ 10/2 = 5 і 0 ≤ Х 2 ≤ 10/2 = 5. Аналогічним чином від лінійних обмежень загального вигляду можна перейти до обмежень на окремі змінні. Залишається взяти максимальні межі за кожної змінної. Якщо багатогранник, що задається обмеженнями, необмежений, як було в задачі про дієту, можна схожим, але трохи більш складним чином виділити його "звернену" до початку координат частину, що містить рішення, і укласти її в багатовимірний паралелепіпед.

Проведемо перебір точок паралелепіпеда з кроком 1/10 n послідовно при n = 2,3, ..., обчислюючи значення цільової функції та перевіряючи наявність обмежень. З усіх точок, задовольняють обмеженням, візьмемо ту, в якій цільова функція максимальна. Рішення знайдено!

2. Спрямований перебір. Почнемо з точки, що задовольняє обмеженням (її можна знайти простим перебором). Будемо послідовно (або випадково - т.зв. метод випадкового пошуку) міняти її координати на певну величину О”, кожен раз в точку з більш високим значенням цільової функції. Якщо вийдемо на площину обмеження, будемо рухатися по ній (знаходячи одну з координат по рівнянню обмеження). Потім рух по ребру (коли два обмеження-нерівності переходять в рівності) ... Зупинка - у вершині лінійного багатогранника. Рішення знайдено! (Більш строго висловлюючись, знайдено з точністю до О”; якщо необхідно, в околиці знайденого рішення проводимо спрямований перебір з кроком О”/2, О”/4 і т.д.)

3. Симплекс-метод. Цей один з перших спеціалізованих методів оптимізації, націлений на вирішення завдань лінійного програмування, в той час як методи простого і спрямованого перебору можуть бути застосовані для вирішення практично будь-якої задачі оптимізації. Він був запропонований американцем Г. Данцигом в 1951 р. Симплекс-метод полягає в просуванні по опуклого багатогранника обмежень від вершини до вершини, при якому на кожному кроці значення цільової функції поліпшується до тих пір, поки не буде досягнутий оптимум.

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

Загальним завданням для лінійного програмування є знаходження неотрицательного рішення системи лінійних обмежень, яке оптимізує лінійну цільову функцію:

max (min)

Виділяють дві форми завдань лінійного програмування:

1. стандартна форма

2. канонічна форма

Планом називається вектор x = (x 1 , x 2 , ..., x n ) R n , що задовольняє умовам (1) - (3). Безліч всіх допустимих рішень задачі будемо позначати через X. Допустиме рішення x X, при якому цільова функція досягає найбільшого (max) або найменшого значення (min), називається оптимальним рішенням задачі лінійного програмування. Базисне ненегативне рішення x = (x 1 , x 2 , ..., x r , 0, ..., 0), де r-ранг системи обмежень, називається опорним рішенням.

1. Звичайні і модифіковані Жорданових виключення

Для розгляду суті симплекс методу в задачах лінійного програмування необхідно зупинитися на понятті В«звичайні й модифіковані Жорданових виключенняВ».

Нехай дана система з m лінійних функцій y 1 , ..., y m від n невідомих x 1 , x 2 , ..., x n : y i = ОЈ a ij x j (1.1), де a ij - постійні величини (i = 1, m; j = 1, n).

Уявімо систему (1.1) в формі таблиці 1.3, яку в подальшому будемо називати Жорданових.

Таблиця 1.3

x 1 ... x j ... X s ... x n

y 1 =

...

y i =

...

y j =

...

y m =

a 11 ... a 1j ... A 1s ... a 1n

........................................

a i1 ... a ij ... A is ... a in

.......................................

a k1 ... a k j ... A ks ... A kn

.......................................

a m1 ... a mj ... a ms ... a mn

Перейдемо до звичайного запису системи шляхом множення елементів a ij i-го рядка на відповідні невідомі x j , що стоять у верхній заголовної рядку, потім отримані твори складаємо і прирівнюємо до y i .

Вибираємо з (1.1) k-е рівняння y k = ОЈa kj x j (1.2 ), і, покладемо, коефіцієнт при x s відмінний від нуля. Висловимо x s :

x s = ОЈ

Така операція називається кроком жорданова виключення виробленим над табл.1.3 з дозволяючим елементом a ks з k-й роздільною рядком і s-му дозволяючим стовпцем. Далі для з'ясування як зміняться інші елементи у табл. 1.3. підставляємо значення x s з в інші рівності системи

Система запишеться у вигляді

y i = ОЈ (i = 1, ..., m)

перетворити систему переписуємо у формі Жорданових таблиці (табл. 1.4)

Таблиця 1.4

x 1 ... y до ... x n

y 1 =

...

x s =

...

y m =

b 11 ...... b 1n

...........................

......

...........................

b m1 ...... b mn

Зіставляючи табл. 1.3 і 1.4, необхідно звернути увагу, що крок звичайного жорданова виключення з дозволяючим елементом a ks переводить одну таблицю в іншу за схемою з чотирьох правил:

1. дозволяє елемент (РЕ) замінюється зворотною величиною;

2. інші елементи роздільної рядка діляться на РЕ та міняють знаки;

3. інші елементи дозволяючого стовпця діляться на РЕ;

4. інші елементи обчислюються за формулою (1.5).

На практиці зручно користуватися правилом прямокутника:

..................................

......... a ij ......... a is .........

.................................

........ a kj ......... a ks .........

.................................

Тоді з... формули безпосередньо випливає, що перетворений елемент 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-рядку є хоча б один негативний елемент, а в його стовпці є хоча б один позитивний, то можна перейти до нового опорно...го плану, більш близькому до оптимального. Для цього зазначений стовпець треба призначити дозволяючим, по мінімальному симплексних відношенню знайти роздільну рядок і виконати симплексних перетворення. Отриманий опорний план знову досліджувати на оптимальність. Описаний процес повторюється до отримання оптимального плану або до встановлення нерозв'язності задачі.

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

В пункті 3 алгоритму передбачається, що всі елементи стовпця вільних членів ненегативні. Ця вимога не обов'язково, але якщо воно виконане, то всі наступні сімплексні перетворення виробляються тільки з позитивними вирішуючими елементами, що зручно при розрахунках. Якщо в стовпці вільних членів є негативні числа, то дозволяє елемент вибирають наступним чином:

1) переглядають рядок, що відповідає якому-небудь негативного вільному члену, наприклад t-рядок, і вибирають в ній небудь негативний елемент, а відповідний йому стовпець приймають за дозволяючий (припускаючи, що обмеження завдання спільної);

2) складають відносини елементів стовпця вільних членів до відповідних елементів розв'язного стовпця, мають однакові знаки (сімплексні відносини);

3) з симплексних відносин вибирають найменше. Воно і визначить роздільну рядок. Нехай нею буде, наприклад, р-рядок;

4) на перетині дозвільних стовпця і рядка знаходять дозволяє елемент. Якщо дозволяючим виявився елемент t-рядки, то після симплексного перетворення вільний член цього рядка стане позитивним. В Інакше на наступному кроці знову звертаються до t-рядку. Якщо задача розв'язана, то через деякий число кроків у стовпці вільних членів не залишиться негативних елементів. Якщо в форму задачі лінійного програмування одягнена деяка реальна виробнича ситуація, то додаткові змінні, які доводиться вводити в модель в процесі перетворення її до канонічної формі, завжди мають певний економічний зміст.

4.1 Ознака оптимальності опорного плану

Якщо в симплекс-таблиці, містить деякий опорний план, усі елементи f-рядки (не рахуючи вільного члена) невід'ємні, то цей опорний план є оптимальним .. Нехай в f-рядку табл. 2.b 0 j > (i = 1, ..., n m). В опорному плані х 0 , що міститься в цій таблиці, значення всіх вільних змінних x m + j дорівнюють нулю і f (х 0 ) = b 00 . Якщо ж збільшувати яку-небудь з вільних змінних x m + j, то, як видно з рівності (2.5), в силу неотрицательности b 0 j значення f (х) почне зменшуватися. Отже, при x про функція f (х) досягає найбільшої величини, а значить, х 0 дійсно є оптимальним опорним планом.

4.2 Можливість перехід від одного опорного плану до іншого

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

Доведемо ця ознака. Встановимо правила вибору змінних для такого перетворення початкового базису Б про з опорним планом х 0 в новий базис Б 1 з опорним планом х 1 при якому; значення функції f збільшується, тобто f (x i )> f (x 0 ) . Тоді за правилом перерахунку елементів з симплекс-таблиці перетворимо до нового базису, що дозволить знайти компоненти нового опорного плану.

Припустимо, що в табл. 2.1, наприклад, b 0 s <0, а серед елементів b is s-го стовпця є хоча б один позитивний. Вважаючи в рівності (2.5) всі вільні змінні х m + j крім x m + s , рівними нулю, отримуємо f = b oo - b os xm + s . З цієї рівності видно, що при збільшенні x m + s значення f теж зростає. Таким чином, при зазначених в ознаці умовах дійсно є можливість збільшити f (x), переходячи до планам, в яких x m + s приймає додатні значення, а всі інші компоненти x m + j як і раніше дорівнюють нулю. Покажемо, що серед таких планів існує і опорний. Тим самим буде знайдено шлях спрямованого перетворення базису Б про в новий базис Б 1 . У самому справі, якщо змінна x m + s приймає позитивне значення в деякому опорному плані, значить, вона є в ньому базисної компонентою (в опорному плані x про вона була вільною компонентою і дорівнювала нулю). Тому колишній базис слід перетворити за рахунок включення в нього змінної x m + s . Але тут належить вирішити два питання:

1) яку зі змінних слід вивести з колишнього базису, щоб звільнити місце

2)

Для дорівнюють нулю. Тоді

З позитивними. Цього допустити не можна. змінних.

......................

Базисні

т.

Нехай

Тоді позитивні.

1)

2)

Змінна,

Трохи Для цього

Отже,

Відзначимо,

Коефіцієнт В

Аналогічно

Приведення Якщо

Якщо в f-рядку симплекс-таблиці, що містить

Доведемо це твердження. Тоді,

З> Is )> 0, а значить, і x i > 0 при будь-яких x m + s > 0. У той же час, як видно, де (- b 0 s )> 0, значення f (х) буде монотонно зростати, і якщо

x m +. s в†’, то і f в†’.

4.4 Ознака нескінченності безлічі оптимальних планів

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

Доведемо це твердження. Припустимо, що міститься в табл. 2 опорний план є оптимальним. Позначимо його через х 1 *. Нехай при цьому елемент b os f-рядки дорівнює нулю, а всі інші елементи цього рядка додатні. Тоді, піддавши табл. 2 симплексного перетворенню з s-му дозволяючим стовпцем, ми прийдемо до іншої таблиці з новим опорним планом, який також буде оптимальним, оскільки елементи f-рядки не змінилися (нульовий елемент b os f-рядки розташований в вирішуючому стовпці). Позначимо цей новий опорний оптимальний план через х 2 *. У відповідності з основною теоремою лінійного програмування стверджуємо, що будь-який план х *, що є опуклою лінійною комбінацією планів х 1 * і х 2 *, теж буде оптимальним.

Якщо в f-рядку буде t (t 1 *, ще t оптимальних опорних планів х 2 *; ...; х t +1 *, і тоді все нескінченну безліч оптимальних планів запишемо так:

x * = О» 1 x 1 * + ... + О» t +1 x t +1 * , де О» l > 0 (l = 1, ..., t +1) і О» 1 + ... + О» t +1 = 1

Всі безліч оптимальних планів можна записати у вигляді

х * = О»х 1 * + (1 - О») х 2 *

4.5 Поняття про про...блему виродження. Зациклення

Розглядаючи перетворення одного базису до іншого, ми припускали, що серед симплексних відносин є тільки одне найменше, і тому питання про вибір змінної, исключаемой з базису, вирішувалося однозначно. Але якщо припустити, що в вирішуючому стовпці min b i 0 /b is досягається для декількох індексів, наприклад для i = l і i = t, тобто

b lo b ts = b to b ls

і роздільної обрана l-й рядок. Тоді в новому опорному плані базисна змінна x t відповідно до формули (2.8) буде дорівнює

b ' to = (b to b ls - b lo b ts ): b is

Звідси отримуємо x t = b ' t 0 = 0. Таким чином, новий опорний план буде виродженим. Задача лінійного програмування, що має хоча б один вироджений опорний план, називається виродженої.

Якщо при вирішенні виродженої задачі на черговому кроці симплексних перетворень роздільної виявиться рядок, в якій вільний план дорівнює нулю, то нулю буде дорівнює і нова базисна компонента чергового опорного плану, тоді як значення інших базисних компонент і цільової функції залишаться колишніми. Як правило, після декількох кроків, що супроводжуються постійністю значення f, приходять все ж до опорному плану з великим, ніж раніше, значенням f, і рішення задачі благополучно закінчується. Разом з тим не виключається випадок, коли після декількох ітерацій отримують вже зустрічався базис, виявляється явище зациклення в схемі розрахунків. Одне з правил, що дозволяють запобігти це небажане явище, формулюється так: якщо в процесі симплексних перетворень з'являється кілька мінімальних симплексних відносин, то вибирають той рядок, для якої буде найменшим відношення елементів першого стовпця до дозволяючим. Якщо при цьому знову опиняється кілька мінімальних відносин, то складаються відносини елементів наступного (Другого) стовпця, і так до тих пір, поки роздільна рядок не визначиться однозначно.

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

Висновок

Аналізуючи все вищевикладене, ми приходимо до висновку про те, що при вирішенні задач лінійного програмування В«вручнуВ» оптимально використовувати симплекс - метод. Оскільки він дозволяє при вірному складанні опорного плану рішення швидко знайти результат. Для цього необхідно знати послідовність кроків при цьому методі і вміти виробляти різні перетворення в симплекс-таблиці.

Список літератури

1 Ашманов С.А., Лінійне програмування. М.: Наука 1981.

2. Кузнєцов А.В., Холод Н.І., Математичне програмування. Мн.: Вищу школу 1984

3. Кузнєцов А.В., Холод Н.І., Костевич Л.С., Керівництво вирішення задач з математичного програмування. Мн.: 2001

4. Кузнєцов А.В., Холод Н.І., Новикова Т.І. збірник задач з математичного програмування. Мн.: Вища школа 1994

5. Кузнєцов А.В., Холод Н.І., Сокович В.А.., Вища математика. Математичне програмування. Мн.: Вища школа 1987