Алгоритм симплекс-методу та його реалізація за допомогою симплекс-таблиць


 

Алгоритм симплекс-методу застосовується для КЗЛП:

,

,

,

де і .

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

Алгоритм симплекс-методу складається з таких процедур:

1. Розкладаються вектори за базисом .

Розклад вектора по початковому базису відомий:

.

Розклад базисних векторів також відомий.

Для вектора : і .

Розклад інших небазисних векторів знаходиться за формулою:

, — базисна матриця.

Позначимо через номер ітерації. На першій ітерації .

2. Для кожного обчислюємо оцінку

.

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

Якщо є хоча б одна від’ємна оцінка , тоді переходимо на 3-й крок.

3. З’ясовуємо, чи існує хоча б одна оцінка , для якої всі .

Якщо така оцінка існує, тоді цільова функція КЗЛП необмежена зверху на допустимій множині. Кінець алгоритму.

Якщо ж таких оцінок немає (тобто для будь-яких є хоча б одна координата ), тоді переходимо на 4-й крок.

4. Вибираємо одну з . Нехай це буде і підраховуємо відношення для усіх , таких що .

Знаходимо мінімальне з цих відношень (нехай це буде -те відношення):

.

5. Переходимо до нового базисного розв’язку, базис якого отримується заміною вектора на .

Координати усіх векторів у новому базисі підраховуємо за формулами:

,

. . Повертаємося на 2-й крок алгоритму.

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

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

.

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

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

При проведенні розрахунків вручну, пов’язаних з розв’язуванням ЗЛП симплекс-методом, зручно усі обчислення на кожній ітерації записувати у симплекс-таблиці (табл. 1.5):

Таблиця 1.5.

                   
  Базис
 
 
 
 
 
     

 

- значення цільової функції при даному опорному розв’язку, тобто

.

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

Приклад 1.9. Розв’язати ЗЛП:

,

,

,

.

Переходимо до канонічної ЗЛП:

,

,

,

.

Базисним розв’язком цієї задачі є, наприклад, вектор .

Очевидно, що ранг матриці

дорівнює 2.

Даний базисний розв’язок невироджений, бо він має 2 додатні координати.

.

Розкладаємо небазисні вектори за базисом:

,

.

При цьому з базисного розв’язку

.

Далі заповнюємо таблицю 1.6.

Таблиця 1.6.

Базис – 4 – 15 – 12 – 2
– 4 2/3     7/3     – 4/3   1/3   – 1  
  2/7   3/7       – 4/7   1/7   – 3/7
  – 12 1/3 2/3 1/3 – 1/3
      – 20/3 – 7/3 10/3 8/3

 

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

Підраховуємо відношення:

.

. Отже, з базису виводимо вектор , а вводимо .

Заповнюємо симплекс-таблицю, що відповідає новому базисному розв’язку, при цьому координати усіх векторів у новому базисі обчислюємо за правилами, описаними у пункті 1.4.1:

Таблиця 1.7.

Базис – 4 – 15 – 12 – 2
– 15 2/7 3/7 – 4/7 1/7 – 3/7
– 12 1/7 – 2/7 5/7 – 3/7 2/7
    – 6

 

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

 

Приклад 1.10. Розв’язати ЗЛП:

,

,

,

.

Переходимо до канонічної ЗЛП:

,

,

,

.

Базисний розв’язок .

. Враховуючи зауваження 1, заповнюємо таблицю 1.8.

Таблиця 1.8.

                 
Базис
    – 1        
  1/5     – 1/5   1/5   1/5  
 
      – 8 – 1 – 2

 

Базисному розв’язку відповідає нульове значення цільової функції. Оскільки не виконуються умови теорем 1.4.3 та 1.4.4, переходимо до наступного базисного розв’язку у таблиці 1.9.

Таблиця 1.9.

                 
  Базис
2/5 – 1/5 1/5 1/5
18/5     11/5   9/5   –1/5    
  18/11       9/11   –1/11   5/11
      16/5 – 13/5 – 2/5 8/5

 

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

Таблиця 1.10.

Базис
8/11 4/11 2/11 1/11
18/11 9/11 -1/11 5/11
    82/11 19/11 15/11 13/11

 

За даними таблиці 1.10 видно, що виконується критерій оптимальності (всі ). Оптимальним базисним розв’язком є вектор , якому відповідає максимальне значення цільової функції .

Економічну інтерпретацію правил симплекс-методу розглянемо на наступному прикладі.

Приклад 1.11. Для виробництва трьох видів продукції А, В, С використовується три види ресурсів, запаси яких відповідно дорівнюють 60, 36 та 80 умовних одиниць. Норми витрат ресурсів на одиницю продукції наведено у таблиці 1.11.

 

Таблиця 1.11.

Продукти   Ресурси   А В С
І
ІІ
ІІІ

 

Ціна одиниці продукції виду А – 10 грн., виду В – 5 грн. та виду С – 12 грн. Знайти оптимальний план виробництва продукції.

Побудуємо модель задачі. Змінні , означають кількість продукції відповідно виду А, В та С. Цільову функцію – виручку від реалізації продукції – запишемо так:

.

Обмеження задачі пов’язані з витратами ресурсів, тобто

,

,

,

а також невід’ємністю змінних

.

Розглянемо КЗЛП:

,

,

,

,

.

Економічний зміст додаткових невід’ємних змінних - залишки відповідно першого, другого та третього виду ресурсів.

Початковий базисний розв’язок задачі - , якому відповідає базис

.

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

Таблиця 1.12.

Базис
      -10 -5 -12

 

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

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

Так, означає, що при виробництві одиниці продукції виду А буде забезпечено збільшення виручки на 10 грн. Якщо включити до плану по одному виробу виду В і С, тоді загальна виручка збільшиться відповідно на 5 грн. або 12 грн. Тому з економічної точки зору доцільно включити до плану виробництво саме продукту виду С.

Те ж саме необхідно зробити і згідно з правилами симплекс-методу. Введення до базису вектора говорить про те, що необхідно розпочати виробництво продукції виду С. Яку ж максимальну кількість цього продукту можна виробляти з урахування запасів ресурсів та норм їх витрат? Для відповіді на це питання знаходимо відношення

= 60, = 18, =40,

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

В результаті виробництва 18 одиниць продукту С запас другого ресурсу буде повністю використаний, тому змінна і стає небазисною. Згідно алгоритму симплекс-методу вектор виводимо з базису та переходимо до нового базисного плану (табл. 1.13).

Таблиця 1.13.

Базис
  -1
    -4

 

Наступний базисний план - , якому відповідає значення цільової функції .

З економічної точки зору новий план означає, що виробництво продукту виду С у кількості 18 одиниць забезпечить виручку 216 грн. Залишок першого ресурсу – 42 умовні одиниці, третього – 44, а другий ресурс використовується повністю.

Якщо у таблиці 1.12 елементи стовпчика означали запаси ресурсів, а елементи стовпчиків , , - нормативи витрат ресурсів, тоді у таблиці 1.12 економічний зміст цих стовпчиків став більш складним. Наприклад, число у стовпчику означає на скільки треба зменшити виробництво продукту С, якщо запланувати виробництво одиниці продукції виду . Числа та 4 у першому та третьому рядках стовпчика показують відповідно, скільки треба ресурсів першого та третього виду для включення до плану одиниці продукції виду . Число –4 у четвертому рядку стовпчика показує на скільки буде збільшена виручка підприємства, якщо запланувати виробництво одиниці продукції . Таким чином числа та 4 треба розглядати як нові нормативи витрат першого та третього ресурсів на виробництво одиниці продукції . Аналогічний економічний зміст у елементів стовпчика .

Дещо іншу економічну інтерпретацію мають елементи стовпчика . Збільшення на одиницю запасу другого ресурсу призведе до збільшення виробництва продукту С на , при цьому залишки першого ресурсу зменшаться на , а третього на 1 умовну одиницю.

З економічної інтерпретації елементів таблиці 1.13 випливає, що знайдений план не є оптимальним. Якщо розпочати ще виробництво і продукту виду , тоді виручка буде збільшена на величину 4 , де - об’єм виробництва цього продукту, який визначається як

.

На величину випуску продукту найбільшою мірою вплинув запас третього виду ресурсу. Таким чином вводимо до базису вектор , а виводимо вектор та переходимо до нового базисного плану (табл. 1.14).

Таблиця 1.14

Базис
25,5
12,5
   

 

Новий базисний план ,якому відповідає значення цільової функції .

З економічної точки зору новий план означає, що виробництво продукту А складає 11 одиниць, продукту С – 12,5 одиниць, а продукт В не виробляється. В результаті такого плану другий та третій ресурси витрачаються повністю, а залишок першого ресурсу складає 25,5 умовних одиниць. У порівнянні з попереднім планом виручка зросла на 44 грн. і складає 260 грн.

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

 









Последнее изменение этой страницы: 2016-04-06; Нарушение авторского права страницы

infopedia.su не принадлежат авторские права, размещенных материалов. Все права принадлежать их авторам. Обратная связь