Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Симплексний метод є універсальним методом розв’язання задач лінійного програмування. Свою назву метод бере від слова «симплекс» (найпростіші багатокутник, багатогранник). N-мірні симплекси розглядав американський вчений Дж. Данциг при розробці ним у 50-і рр. ХХ ст. даного методу рішення ЗЛП.

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

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

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

Алгоритм симплекс-методу складається з кількох етапів, які розглянемо на прикладі.

 

Приклад. На підприємстві є дві категорії робітників: основні і допоміжні. Норми витрат праці (в деяких одиницях виміру трудомісткості) на виробництво одиниці двох видів продукції, наявність трудових ресурсів на підприємстві та ціни одиниць продукції наведені в таблиці 1.

Таблиця 1 – Вихідні дані

Категорія персоналу Норми витрат праці на виробництво одиниці продукції Наявні трудові ресурси
П1 П2
Основні      
Допоміжні      

 

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

У розглянутому прикладі цільова функція, що виражає вимогу максимізації прибутку, має вигляд:

F = 2х1 + 3х2 ® max.

Обмеження визначають залежність між величинами необхідних і наявних ресурсів і можуть бути записані так:

1 + 3х2 £ 300;

х1 + х2 £ 150.

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

х1 ³ 0, х2 ³ 0.

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

F = 2х1 + 3х2 ® max

1 + 3х2 £ 300;

х1 + х2 £ 150.

х1 ³ 0, х2 ³ 0

Для приведення її до канонічної (стандартної) форми в ліву частину кожної з нерівностей введемо додаткову змінну. Отримаємо:

F = 2х1 + 3х2 + 0х3 + 0х4 → max

х1 + 3х2 + х3 = 300;

х1 + х2 + х4 = 150.

xj ≥ 0

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

Матрична форма запису моделі:

(6)

(7)

, (8)

де

- Матриця умов завдання.

 

1. Визначення початкового (опорного) плану ЗЛП.

Перепишемо систему обмежень у вигляді:

 
 


х3= 300 – (х1 + 3х2);

х4= 150 – (х1 + х2).

В отриманій системі змінні, що знаходяться у правій частині (х1, х2), називаються вільними (неосновними). А змінні, розташовані зліва (тобто додаткові змінні х3, х4), називаються базисними. Дорівнюючи вільні змінні нулю, отримаємо базисне рішення. вважаючи х1 = 0, х2 = 0, отримаємо значення базисних змінних х3 = 300, х4 =150.

Таким чином, отримано початковий опорний план: Х0 = (0; 0; 300; 150).

При цьому цільова функція F, очевидно, дорівнює нулю.

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

Отримане рішення внесемо до таблиці:

Базис сi (цільов. ф-ція) План (bi)         α  
х1 х2 х3 х4  
х3                
х4                
j= zj - cj              
 

3. Перевірка опорного плану.

Умова оптимальності: опорне рішення ЗЛП на максимум (мінімум) цільової функції є оптимальним тоді і тільки тоді, коли всі Δ j ненегативні (непозитивні): Обчислимо величину оцінок для розглянутого прикладу:

1 = z1 – c1 = (0 ∙ 1 + 0 ∙ 1) - 2 = -2;

2 = z2 – c2 = (0 ∙ 3 + 0 ∙ 1) - 3 = -3;

3 = z3 – c3 = (0 ∙ 1 + 0 ∙ 0) - 0 = 0;

4 = z4 – c4 = (0 ∙ 0 + 0 ∙ 1) - 0 = 0.

 

Базис сi (цільоев. ф-ція) План (bi)         α  
х1 х2 х3 х4  
х3                
х4                
j= zj - cj   -2 -3        
 

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

4. Перехід до нового опорного плану.

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

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

У цільовому рядку є негативні оцінки, максимально по модулю з яких - Δ 2 = -3, тому, слідуючи правилу в якості введеної змінної треба взяти х2.

2. Вибір тієї, що виводиться з числа базисних (в розряд вільних) змінної здійснюється наступним чином. Змінна, що виводиться з числа базисних, незалежно від спрямованості оптимізації, визначається за мінімальним симплекс-відношенням. Симплекс-відношення являє собою відношення елементів підсумкового стовпця «Опорний план» симплекс-таблиці до відповідних позитивних елементів ключового стовпця. Якщо елемент ключового стовпця ≤ 0, то симплекс-відношення не розраховується (ставиться прочерк або знак ∞). Якщо в ключовому стовпці всі елементи ≤ 0, це свідчить про те, що ЗЛП не має рішення виходячи з необмеженості цільової функції.

Відповідний виведеній змінній рядок в симплекс-таблице називається ключовим.

Так, у нульовій симплексній таблиці розв'язуваної задачі симплекс-відношення для базисної змінної х3 дорівнює 300: 3 = 100, а для базисної змінної х4 – 150: 1 = 150. Ці значення записуються в останній графі симплексної таблиці. Мінімальне з симплекс-відношень визначає ключовий рядок і виведену з числа базисних змінну – це х3.

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

 

Базис сi (цільов.ф-ція) План (bi)         α  
х1 х2 х3 х4  
← х3                
х4                
j= zj - cj   -2 -3        
 

 

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

1) елементи ключового рядка діляться на ключовий елемент. Отримані таким чином величини поміщають в нову таблицю. Так в першій симплексній таблиці елементи рядка х2 дорівнюють:

.

2) всі інші елементи, включаючи цільовий рядок, перераховуються за правилом «прямокутного трикутника»:

Базис сi (цільов.ф-ція) План (bi)         α  
х1 х2 х3 х4  
← х3                
х4                
j= zj - cj   -2 -3        
 
→ х2     1/3   1/3      
х4                
j= zj - cj              
 

 

а) до стовпчика β записуються відношення елементів ключового стовпця до ключового елементу:

б) перерахунок елементів виконується відповідно до схеми:

 

а нове = а стареbс

b

a
c

 

де b – елемент, що знаходиться на перехресті стовпчика, що містить число, що перераховується, та ключового рядка;

с – елемент, що знаходиться на перехресті рядка, що містить число, що перераховується, та стовпчика β.

 

150-300·1/3=50; 1-1·1/3=2/3; 1-3·1/3=0; 0-1·1/3=-1/3; 1-0·1/3=1.

Базис сi (цільов.ф-ція) План (bi)         α β
х1 х2 х3 х4
← х3   300            
х4               1/3
j= zj - cj   -2 -3        
→ х2     1/3   1/3      
х4                
j= zj - cj              

 

Отримані значення заносяться до нової симплекс таблиці:

 

Базис сi (цільов.ф-ція) План (bi)         α β
х1 х2 х3 х4
х3                
х4               1/3
j= zj - cj   -2 -3        
х2     1/3   1/3      
х4     2/3   -1/3      
j= zj - cj              

Розрахуємо величини оцінок:

1 = z1 – c1 = (3 ∙ 1/3 + 0 ∙ 2/3) - 2 = -1;

2 = z2 – c2 = (3 ∙ 1 + 0 ∙ 0) - 3 = 0;

3 = z3 – c3 = (3 ∙ 1/3 + 0 ∙ -1/3) - 0 = 1;

4 = z4 – c4 = (3 ∙ 0 + 0 ∙ 1) - 0 = 0.

 

 

Результати заносимо до таблиці:

Базис сi (цільов.ф-ція) План (bi)         α β
х1 х2 х3 х4
х3                
х4               1/3
j= zj - cj   -2 -3        
х2     1/3   1/3      
← х4     2/3   -1/3      
j= zj - cj   -1          

 

 

Оскільки серед оцінок ще є негативна Δ 1 = -1, то робимо висновок про те, що нове рішення не є оптимальним. Змінна х1 тепер буде вводитися, х4 – виводитися (мінімальне симплекс-відношення дорівнює 75).

Виконавши перерахунок, приходимо до наступної симплексної таблиці.

100-50·1/2=75; 1/3-2/3·1/2=0; 1-0·1/2=1; 1/3-(-1/3·1/2)=1/2; 0-1·1/2=-1/2.

Розрахуємо оцінки:

1 = z1 – c1 = (3 ∙ 0 + 2 ∙ 1) - 2 = 0;

2 = z2 – c2 = (3 ∙ 1 + 2 ∙ 0) - 3 = 0;

3 = z3 – c3 = (3 ∙ 1/2 + 2 ∙ (-1/2)) - 0 = 1/2;

4 = z4 – c4 = (3 ∙ (-1/2) + 2 ∙ 3/2) - 0 = 3/2.

 

 

Базис сi (цільов.ф-ція) План (bi)         α β
х1 х2 х3 х4
← х3                
х4               1/3
j= zj - cj   -2 -3        
→ х2     1/3   1/3     1/2
← х4     2/3   -1/3      
j= zj - cj   -1          
х2         1/2 -1/2    
→ х1         -1/2 3/2    
j= zj - cj       1/2 3/2    

 

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

Питання для самоконтролю:

1. Яким чином формується система обмежень задачі?

2. Що таке рівняння зв’язку?

3. Рішення економіко-математичної моделі – що це таке?

4. У чому різниця між допустимим рішенням та допустимим планом?

5. Які практичні задачі дозволяє розв’язати симплексний метод?

Рекомендована література:

основна: [1, 2, 4, 5, 6, 9];

додаткова: [3, 7, 8, 10-21].

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.017 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал