Розв’язування задачі лінійного програмування симплексним методом

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

Графічний метод для визначення оптимального плану задач лінійного програмування доцільно застосовувати лише для задач із двома змінними. За більшої кількості змінних необхідно застосовувати інший метод. З властивостей розв’язків задачі лінійного програмування відомо: оптимальний розв’язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв’язків. Тому найпростіший спосіб відшукання оптимального плану потребує перебору всіх кутових точок (допустимих планів задачі, які ще називають опорними). Порівняння вершин багатогранника можна здійснювати тільки після відшукання якоїсь однієї з них, тобто знайшовши початковий опорний план. Кожний опорний план визначається системою m лінійно незалежних векторів, які містяться в системі обмежень задачі з n векторів . Отже, загальна кількість опорних планів визначається кількістю комбінацій . Задачі, що описують реальні економічні процеси, мають велику розмірність, і простий перебір всіх опорних планів таких задач є дуже складним, навіть за умови застосування сучасних ЕОМ. Тому необхідне використання методу, який уможливлював би скорочення кількості обчис­лень. 1949 року такий метод був запропонований американським вченим Дж.Данцігом – так званий симплексний метод, або симплекс-метод.

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

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

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

Початковий опорний план

Розглянемо задачу лінійного програмування, записану в канонічній формі:

.

Не порушуючи загальності, допустимо, що система рівнянь містить перші m одиничних векторів. Отримаємо:

(4.1)

(4.2)

(4.3)

Система обмежень (4.2) у векторній формі матиме вигляд:

, (4.4)

де

, ,..., ,

, …, , ,

– лінійно незалежні одиничні вектори m-вимірного простору, що утворюють одиничну матрицю і становлять базис цього простору. Тому в розкладі (4.4) базисними змінними будуть , а інші змінні – вільні. Прирівняємо всі вільні змінні до нуля, тобто . Оскільки , а вектори – одиничні, то отримаємо один із розв’язків системи обмежень (4.2):

(4.5)

тобто допустимий план.

Такому плану відповідає розклад

(4.6)

де — лінійно незалежні вектори і за властивістю 3 розв’язків задачі лінійного програмування (п.3.4) план є кутовою точкою багатогранника розв’язків, а отже, може бути почат­ковим опорним планом.

4.3 Перехід від одного опорного плану до іншого

Розглянемо, як, виходячи з початкового опорного плану (4.6), перейти до наступного опорного плану, що відповідає ціле­спрямованому процесу перебору кутових точок багатогранника розв’язків.

Оскільки є базисом m-вимірного простору, то кожен з векторів співвідношення (4.5) може бути розкладений за цими векторами базису, причому у єдиний спосіб:

Розглянемо такий розклад для довільного небазисного вектора, наприклад, для :

(4.7)

Припустимо, що у виразі (4.7) існує хоча б один додатний коефіцієнт .

Введемо деяку поки що невідому величину , помножимо на неї обидві частини рівності (4.7) і віднімемо результат з рівності (4.6). Отримаємо:

(4.8)

Отже, вектор

є планом задачі у тому разі, якщо його компоненти невід’ємні. За допущенням , отже, ті компоненти вектора , в які входять , будуть невід’ємними, тому необхідно розглядати лише ті компоненти, які містять додатні . Тобто необхідно знайти таке значення , за якого для всіх буде виконуватися умова невід’ємності плану задачі:

(4.9)

З (4.9) отримуємо, що для шуканого має виконуватися умова . Отже, вектор буде планом задачі для будь-якого q, що задовольняє умову:

,

де мінімум знаходимо для тих i, для яких .

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

.

Підставимо значення у вираз (4.8):

,

якщо позначити , , то рівняння можна подати у вигляді:

,

якому відповідає такий опорний план:

.

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

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

Необхідно зазначити, що для випадку, коли вектор підлягає включенню в базис, а в його розкладі (4.7) всі , то, очевидно, не існує такого значення , яке виключало б один з векторів. У такому разі план містить m+1 додатних компонент, отже, система векторів буде лінійно залежною і визначає не кутову точку багатогранника розв’язків. Функціонал не може в ній набирати максимального значення. Це означає, що функціонал є необмеженим на багатограннику розв’язків.

4.4 Оптимальний розв’язок. Критерій оптимальності плану

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

Розглянемо задачу лінійного програмування (4.1)-(4.3).

Допустимо, що вона має опорні плани і вони є невиродженими. Розглянемо початковий опорний план виду (4.5):

Такому плану відповідає розклад за базисними векторами

(4.10)

та значення функціонала:

(4.11)

Кожен з векторів можна розкласти за векторами базису, причому у єдиний спосіб:

, (4.12)

тому такому розкладу відповідатиме і єдине значення функ­ціонала:

. (4.13)

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

, (4.14)

то план є оптимальним розв’язком задачі лінійного програмування (4.1)-(4.3).

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

, (4.15)

то план Х₀ є оптимальним розв’язком задачі лінійного програмування.

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

Розв’язування задачі лінійного програмування симплексним методом

Розглянемо, як, виходячи з початкового опорного плану задачі лінійного програмування, за допомогою симплексного методу знайти оптимальний план.

Продовжимо розгляд задачі (4.1)-(4.3), опорний план якої . Для дослідження даного плану на оптимальність (за умовою оптимальності плану задачі лінійного програмування) необхідно вектори системи обмежень (4.2) розкласти за базисними векторами і розрахувати значення оцінок .

Всі подальші обчислення зручно проводити в симплексній таблиці (табл.4.1).

У стовпці «Базис» записані змінні, що відповідають базисним векторам, а в стовпці «С_баз» – коефіцієнти функціонала відповідних базисних векторів. У стовпці «План» – початковий опорний план , в цьому ж стовпці в результаті обчислень отримують оптимальний план. У стовпцях записані коефіцієн­ти розкладу кожного j-го вектора за базисом, які відповідають у пер­шій симплексній таблиці коефіцієнтам при змінних у системі (4.2). У (m+1)-му рядку в стовпці «План» записують значення функціонала для початкового опорного плану , а в інших стовпцях – значення оцінок . Цей рядок симплексної таблиці називають оцінковим.

Значення знаходять підстановкою компонент опорного плану в цільову функцію, а значення – при підстанов­ці коефіцієнтів розкладу кожного j-го вектора за векторами ба­зису, тобто ці значення в табл.4.1 отримують як скалярний добуток:

,

де с_і – коефіцієнти функціонала, що відповідають векторам базису.

Таблиця 4.1 – Перша симплексна таблиця для розв’язку задач лінійного програмування

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

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

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

Для того, щоб вибрати вектор, який необхідно вивести з базису (згідно з процедурою переходу від одного опорного плану задачі до іншого – п.4.2), розраховують останній стовпчик табл.4.1 – значення .

.

З розрахованих значень необхідно вибрати найменше . Тоді з базису виключають i-ий вектор, якому відповідає .

Допустимо, що відповідає вектору, що знаходиться в l-му рядку табл.4.1. Відповідний рядок симплексної таблиці називають напрямним.

Перетином напрямного стовпчика та напрямного рядка визначається елемент симплексної таблиці a_lk, який називають розв’язувальним елементом. За допомогою елемента a_lk і методу Жордана-Гаусса розраховують нову симплексну таблицю, що визначатиме наступний опорний план задачі.

Для визначення нового опорного плану необхідно всі вектори розкласти за векторами нового базису. Вектор А_k, який необхідно вводити до базису, в розкладі за початковим базисом має вигляд:

(4.16)

Вектор А_l виходить з базису, і його розклад за новим базисом отримаємо з виразу (4.16):

. (4.17)

Розклад вектора А₀ за початковим базисом має вигляд:

. (4.18)

Для запису розкладу вектора в новому базисі підставимо вираз (4.17) у рівняння (4.18), маємо:

.

Отже, значення компонент наступного опорного плану розраховуються за формулами:

(4.19)

Розклад за початковим базисом будь-якого з векторів має вигляд:

. (4.20)

Розклад за новим базисом отримаємо підстановкою (4.17)
у (4.20):

.

Новий план: , де

(4.21)

Формули (4.19) та (4.21) є формулами повних виключень Жор­дана-Гаусса.

Отже, щоб отримати коефіцієнти розкладу векторів за векторами нового базису (перехід до наступного опорного плану та створення нової симплексної табл.4.2), необхідно:

1) розділити всі елементи напрямного рядка на розв’язуваль­ний елемент;

2) розрахувати всі інші елементи за формулами повних виключень Жордана—Гаусса (правило прямокутника).

Потім необхідно здійснити перевірку нових значень оцінкового рядка. Якщо всі F_j – с_j ³ 0, то план Х₁ — оптимальний, інакше переходять до відшукання наступного опорного плану. Процес продовжують до отримання оптимального плану, чи встановлення факту відсутності розв’язку задачі.

Якщо в оцінковому рядку останньої симплексної таблиці оцінка F_j – с_j ³ 0 відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибираючи розв’язувальний елемент у зазначеному стовпчику таблиці та здійснивши один крок (одну ітерацію) симплекс-методом. У результаті отримаємо новий опор­ний план, якому відповідає те саме значення функціонала, що і для попереднього плану, тобто функціонал досягає максимального значення в двох точках багатогранника розв’язків, а отже, за властивістю 2 (п.3.2) розв’язків задачі лінійного програмування така задача має нескінченну множину оптимальних планів.

Розв’язання задачі лінійного програмування на відшукання мінімального значення функціонала відрізняється лише умовою оптимальності опорного плану. До базису включають вектор, для якого , де максимум знаходять для тих j, яким відповідають . Всі інші процедури симплексного методу здійснюються аналогічно, як у задачі лінійного програмування на відшукання максимального значення функціонала.

Таблиця 4.2 – Друга симплексна таблиця для відшукання опорного (оптимального) плану

4.6 Метод штучного базису (самостійна робота)

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

Розглянемо задачу лінійного програмування:

(4.22)

(4.23)

(4.24)

Задача подана в канонічному вигляді і система обмежень (4.23) не містить одиничної матриці. Отримати одиничну матрицю можна, якщо до кожного рівняння в системі обмежень задачі додати одну змінну . Такі змінні називають штуч­ними. (Не обов’язково кількість введених штучних змінних має дорівнювати m. Їх необхідно вводити лише в ті рівняння системи обмежень, які не розв’язані відносно базисних змінних.) Допустимо, що система рівнянь (4.23) не містить жодного одиничного вектора, тоді штучну змінну вводять у кожне рівняння:

(4.25)

У результаті додавання змінних у рівняння системи (4.23) область допустимих розв’язків задачі розширилась. Задачу з системою обмежень (4.25) називають розширеною, або М-задачею. Розв’язок розширеної задачі збігатиметься з розв’язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві. Тоді система обмежень (4.25) набуде вигляду (4.23) (не міститиме штучних змінних), а розв’язок розширеної задачі буде розв’язком і задачі (4.22)-(4.24).

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

(У разі розв’язання задачі на відшукання мінімального значення цільової функції вводять коефіцієнти, які є досить великими числами. Цільова функція тоді має вигляд:

.

Припускається, що величина М є досить великим числом. Тоді якого б малого значення не набувала відповідна коефіцієнту штучна змінна , значення цільової функції буде від’ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні .

Якщо в оптимальному плані розширеної задачі існує хоча б одне значення , то це означає, що початкова задача не має розв’язку, тобто система обмежень несумісна.

Для розв’язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му – ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.

Взаємозв’язок між розв’язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.

Теорема 4.1. Якщо в оптимальному плані розширеної задачі штучні змінні , то план є оптимальним планом початкової задачі.

Отже, загалом алгоритм розв’язування задачі лінійного програмування симплекс-методом складається з п’яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

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

4. Перехід до нового опорного плану задачі здійснюється визначенням розв’язувального елемента та розрахунками елементів нової симплексної таблиці.

5. Повторення дій, починаючи з п.3.

Далі ітераційний процес повторюють, доки не буде визначено оптимальний план задачі.

У разі застосування симплекс-методу для розв’язування задач лінійного програмування можливі такі випадки.

1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв’язуваль­ний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.

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

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