Звіт про проходження практики на кафедре економічної кібернетики Київського національного університету імені Тараса Шевченка

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

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

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

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

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

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

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

 (4.10)

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

 (4.11)

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

, (4.12)

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

. (4.13)

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

, (4.14)

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

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

, (4.15)

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

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

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

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

Продовжимо розгляд задачі (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. Відповідний рядок симплексної таблиці називають напрямним.

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

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

 (4.16)

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

. (4.17)

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

. (4.18)

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

.

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

 (4.19)

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

. (4.20)

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

.

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

 (4.21)

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

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

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

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

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

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

 

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

 

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

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