Симплекс - алгоритм (2-й етап симплекс - методу)
Основна теорема симплекс-метода.
Симплекс - метод складається з двох етапів:
1) знаходження вихідного опорного рішення ЗЛП;
Знаходження оптимального рішення. Цей етап зветься симплекс - алгоритм.
Знаходження вихідного опорного рішення (1-й етап симплекс-метода).
Розглянемо ЗЛП у стандартній формі, при цьому невідомі у цільовій функції перенесемо вліво та розглянемо наступне завдання.
xj ≥0,j =і maxZ, (1.1)
(1.2)
Зауваження. Вільний член у рівнянні цільової функції дорівнює нулю, але може бути, і відмінний від нуля.
Вважатимемо, що система (1.1) ,(1.2) спільна, система рівнянь (1.2) – лінійно незалежна і все .
Знайдемо опорне рішення системи (1.2), здійснивши послідовність симплексних перетворень, і нехай при цьомуi-е рівняння системи (1.2) виявилося дозволеним щодо змінноїxi(i =):
xi + aim+1xm+1+aim+2xm+2+. + aisxs +. + ainxn = bi(i =), (1.4)
де всіbi0(i = ).
Базовими змінними є змінніx1,x2, . ,xm, а вільними:xm+1,xm+2,. , xs , . , xn(базисними можуть і не обов'язково першіmзмінних). Вихідне невироджене опорне рішення системи (4.4) має вигляд:
Говоритимемо, що система рівнянь (4.4) приведена до опорного рішення. Виключимо з рівняння (4.3) базові змінні. Для цього кожнеi-е рівняння системи (1.4) помножимо насiі потім усі отримані рівняння складемо, отримаємо:
(1.5)
Рівняння (4.3) запишемо так:
Z--cm+1xm+1 -. - csxs- . -cnxn =0.
Складаючи це рівняння з (4.5), отримаємо:
Позначимо:
Тоді рівняння цільової функції матиме вигляд
Рівняння (4.6) називатимемо рівнянням цільової функції, наведеним до вільних змінних, а коефіцієнти Δj(j =) – оцінками вільних змінних, де
(1.7)
В результаті цих перетворень ЗЛП (1.1) - (1.3) наведено до наступної еквівалентної задачі: знайти значення
xj≥ 0,j =і max Z,(1.1)
Завдання (1.1), (1.4), (1.6) називатимемо ЗЛП у канонічній формі або в канонічному вигляді.
Система обмежень цього завдання наведена до опорного розв'язання:
Рівняння цільової функції наведено до вільних змінних.
Зауваження.Рівняння (1.6) додамо до системи рівнянь (1.4) і розглянемо систему з (m + 1) рівнянь, при цьому в рівнянні (1.6) базисною є вільна
Сімплекс - алгоритм (2-й етап симплекс - методу).
У задачі (1.1), (1.4), (1.6) вважаємо рівними нулю вільні змінні та отримуємо вихідне опорне невироджене рішення (невироджений план):
Тепер від цього рішення (плану) треба перейти до іншого опорного рішення (плану) X1з більшим значенням цільової функції, ніж z 0, тобто.Z(Х1)> Z(Х0)= Z0.
Припустимо, що цього хочемо запровадити у базис вільну зміннуxs =0,тобто. хочемо збільшити значенняxs. При цьому вs-му стовпці обов'язково повинен бути хоча б один коефіцієнтais >0. Вибираємоs-й стовпець вирішальним.
Переходимо від одного опорного рішення до іншого. Для цього необхідно роздільну здатність вибирати за правилом
тобто. як роздільна здатність буде рядокr, а в якості роздільної здатностіелемента:ars.
З роздільною здатністюarsвиконаємо перетворення системи рівнянь (1.4) і (1.6) за формулами повного виключення невідомих (методу Жордана – Гауса) і знайдемо нове опорне невироджене рішення Х1 зі значенням цільової функції:
Тепер сформулюємо правила вибору роздільної здатності елемента в симплекс - алгоритмі:
1. У базис вводимо вільну зміннуxsз негативною оцінкою Δs0. Це правило вибору роздільного стовпцяs.
2. З базису виводимо зміннуxrза правилом
Це правило вибору роздільної здатностіr.
3. З роздільним елементомarsвиконаємо перетворення системи (1.4), (1.6).
Коефіцієнти при невідомихa΄ij,Δ΄jта значенняb΄j, z΄0 у новій системі рівнянь обчислюються за формулами:
де введені позначення:
Дії, виконані у пп. 1-3 становлять одну операцію симплекс - алгоритму, виконавши яку, ми перейдемо від опорного рішення Х0 до Х1, при цьому Z (Х1)>Z(Х0)=Z0.
Таким чином, коефіцієнт Δsхарактеризує зміну цільової функціїZ, що припадає на кожну одиницю зміни змінної xs , тобто. він оцінює зміну цільової функціїZ. Тому коефіцієнти Δjі називаються оцінками вільних змінних.
Виконавши одну операцію, можемо переходити до наступної і після низки ітерацій ми отримаємо оптимальне рішення або переконаємося в необмеженості цільової функції. Ці ознаки встановлює основна теорема симплексного методу.
Формулювання:Якщо після виконання чергової ітерації:
1) знайдеться хоча б одна негативна оцінка Δs 0, то можна покращити рішення, виконавши таку ітерацію;
2) знайдеться хоча б одна негативна оцінка Δs 0. Отже, нове опорне рішення буде кращим за попереднє.
За наявностіais>0 величина Xs обмежується мінімумом відносин дляais>0. Якщо всеais≤0 , то значенняXsможна обмежувати, т.к. при будь-якому скільки завгодно великому значенніXs,значення всіх інших базисних зміннихXiзавжди будуть невід'ємними, тому щоXi = bi - aisXsі приais ≤0, Xiзавжди позитивні.
Таким чином, змінноїXsможна надавати скільки завгодно велике значення і при цьому цільова функціяzбуде досягати теж скільки завгодно великого значення, тобто.Zmax → ∞.
3) Якщо всі оцінки Δj ≥0, то тому щоZ(Х1)= Z0–Δsxs, слід, що збільшуючи будь-яку вільну змінну ми зменшуватимемо значення цільової функціїZ. Звідси випливає, що у жодному іншому допустимому рішенні функціяZможе бути збільшена, тобто. Знайдене рішення є оптимальним. Теорему доведено.