Методи оптимізації і дослідження операцій
Метод штучного базису. Етапи алгоритму розв’язування розширеної задачі лінійного програмування. Визначення початкового опорного плану. Побудова симплексної таблиці. Зациклення обчислювальної процедури. Способи геометричної інтерпретації симплекс-методу.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лекция |
| Язык | украинский |
| Дата добавления | 08.09.2013 |
| Размер файла | 121,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
1. Метод штучного базису
У попередніх параграфах розглядався випадок, коли система обмежень задачі лінійного програмування містила одиничну матрицю порядку m. Проте більшість задач не можна звести до потрібного вигляду. В такому разі застосовується метод штучного базису.
Розглянемо задачу лінійного програмування:
(2.60)
(2.61)
(2.62)
Отримаємо одиничну матрицю додаванням штучних змінних
лише в ті рівняння, які не розв'язані відносно базисних змінних.
Нехай штучну змінну введено у кожне рівняння:
(2.63)
область допустимих розв'язків задачі розширилась.
Задача з системою обмежень (2.63) - розширена, або М-задача
Розв'язок розширеної задачі збігатиметься з розв'язком початкової лише за умови, що всі введені штучні змінні в оптимальному плані задачі будуть виведені з базису, тобто дорівнюватимуть нулеві
Для того, щоб у результаті процедур симплексних перетворень виключалися з базису штучні змінні, потрібно ввести їх у цільову функцію з великими від'ємними коефіцієнтами.
Нехай величина М є достатньо великим за модулем числом.
Цільова функція для задачі максимізації (мінімізації):
.
Якого б малого значення не набувала відповідна коефіцієнту штучна змінна , значення цільової функції буде від'ємним для задачі на максимум та додатним для задачі на мінімум і водночас значним за модулем. Тому процедура симплексного методу одразу вилучає відповідні змінні з базису і забезпечує знаходження плану, в якому всі штучні змінні .
Якщо в оптимальному плані розширеної задачі існує хоча б одне значення , то це означає, що початкова задача не має розв'язку, тобто система обмежень несумісна.
Для розв'язання розширеної задачі за допомогою симплексних таблиць зручно використовувати таблиці, оцінкові рядки яких поділені на дві частини-рядки. Тоді в (m+2)-му рядку записують коефіцієнти з М, а в (m+1)-му -- ті, які не містять М. Вектор, який підлягає включенню до базису, визначають за (m+2)-м рядком. Ітераційний процес по (m+2)-му рядку проводять до повного виключення всіх штучних змінних з базису, потім процес визначення оптимального плану продовжують за (m+1)-им рядком.
Взаємозв'язок між розв'язками початкової та розширеної задач лінійного програмування не є очевидним і визначається такою теоремою.
Теорема 2.8. Якщо в оптимальному плані розширеної задачі штучні змінні
,
то план є оптимальним планом початкової задачі.
Доведення. Зазначимо, що коли план є оптимальним планом розширеної задачі, то план -- план початкової задачі. При цьому
.
Доведемо, що план -- оптимальний план початкової задачі. Допустимо, що не є оптимальним планом. Тоді існує такий оптимальний план , для якого . Звідси для вектора , що є планом розширеної задачі, маємо:
,
тобто
.
Отже, план розширеної задачі не є оптимальним, що суперечить умові теореми, а тому зроблене допущення щодо неоптимальності плану є неправильним.
Отже, загалом алгоритм розв'язування задачі лінійного програмування симплекс-методом складається з п'яти етапів:
Визначення початкового опорного плану задачі лінійного програмування.
Побудова симплексної таблиці.
Перевірка опорного плану на оптимальність за допомогою оцінок . Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.
Перехід до нового опорного плану задачі здійснюється визначенням розв'язувального елемента та розрахунками елементів нової симплексної таблиці.
Повторення дій, починаючи з п. 3.
Далі ітераційний процес повторюють, доки не буде визначено оптимальний план задачі.
У разі застосування симплекс-методу для розв'язування задач лінійного програмування можливі такі випадки.
1. Якщо в оцінковому рядку останньої симплексної таблиці оцінка відповідає вільній (небазисній) змінній, то це означає, що задача лінійного програмування має альтернативний оптимальний план. Отримати його можна, вибравши розв'язувальний елемент у зазначеному стовпчику таблиці та здійснивши один крок симплекс-методом.
2. Якщо при переході у симплекс-методі від одного опорного плану задачі до іншого в напрямному стовпчику немає додатних елементів , тобто неможливо вибрати змінну, яка має бути виведена з базису, то це означає, що цільова функція задачі лінійного програмування є необмеженою й оптимальних планів не існує.
3. Якщо для опорного плану задачі лінійного програмування всі оцінки задовольняють умову оптимальності, але при цьому хоча б одна штучна змінна є базисною і має додатне значення, то це означає, що система обмежень задачі несумісна й оптимальних планів такої задачі не існує.
Розв'язати задачу з прикладу 2.10 із додатковою умовою: продукція С має виготовлятися обсягом не менш як 9 одиниць.
Розв'язання. Математичну модель сформульованої задачі запишемо так:
Застосовуючи для розв'язування поставленої задачі симплекс-метод, спочатку запишемо систему обмежень у канонічній формі:
Зауважимо, що нерівність типу «?» перетворюємо у рівняння введенням у ліву частину обмеження додаткової змінної зі знаком «-».
Система містить лише два одиничні вектори -- та , а базис у тривимірному просторі має складатися з трьох одиничних векторів. Ще один одиничний вектор можна дістати, увівши в третє обмеження з коефіцієнтом + 1 штучну змінну х8, якій відповідатиме одиничний вектор .
Тепер можемо розглянути розширену задачу лінійного програмування:
за умов:
На відміну від додаткових змінних штучна змінна х8 має в цільовій функції Z коефіцієнт +М (для задачі на min) або -М (для задачі на max), де М -- досить велике додатне число.
У розширеній задачі базисними змінними є х5, х6, х8, а решта змінних вільні. Початковий опорний план задачі такий:
Складемо першу симплексну таблицю цієї задачі:
Таблиця 1
|
Базис |
Сбаз |
План |
8 |
10 |
0 |
- 5 |
0 |
0 |
0 |
- М |
||
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
|||||
|
х5 |
0 |
450 |
2 |
3 |
4 |
2 |
1 |
0 |
0 |
0 |
112,5 |
|
|
х6 |
0 |
380 |
3 |
2 |
1 |
2 |
0 |
1 |
0 |
0 |
380 |
|
|
х8 |
- М |
9 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
1 |
9 |
|
|
Zj - сj 0 |
0 |
- 8 |
- 10 |
0 |
5 |
0 |
0 |
0 |
0 |
|||
|
- 9М |
0 |
0 |
-М |
0 |
0 |
0 |
М |
0 |
Розраховуючи оцінки першого опорного плану, дістаємо: Z0 = -9M; Z1 - с1 = -8; Z2 - с2 = -10, Z3 - с3 = -М і т. д. Отже, ми отримуємо оцінки двох видів: одні з них містять М, а інші є звичайними числами. Тому для зручності розділимо оцінковий рядок на два. У перший оцінковий рядок будемо записувати звичайні числа, а в другий -- числа з коефіцієнтом М.
Оцінки першого плану не задовольняють умову оптимальності, і тому він є неоптимальним. Згідно з алгоритмом, розглянутим у задачі 2.41, виконуємо перехід до наступного опорного плану задачі. Після першої ітерації з базису виведена штучна змінна х8. Дальше розв'язування продовжуємо за алгоритмом симплексного методу.
Наступні кроки розв'язування задачі наведені у загальній таблиці:
Таблиця 2
|
Базис |
Сбаз |
План |
8 |
10 |
0 |
- 5 |
0 |
0 |
0 |
- М |
||
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
|||||
|
х5 |
0 |
414 |
2 |
3 |
0 |
2 |
1 |
0 |
4 |
-4 |
138 |
|
|
х6 |
0 |
371 |
3 |
2 |
0 |
2 |
0 |
1 |
1 |
-1 |
185,5 |
|
|
х3 |
0 |
9 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
1 |
-- |
|
|
Zj - сj 0 |
0 |
-8 |
-10 |
0 |
5 |
0 |
0 |
0 |
0 |
|||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
М |
|
|||
|
х2 |
10 |
138 |
2/3 |
1 |
0 |
2/3 |
1/3 |
0 |
4/3 |
-4/3 |
207 |
|
|
х6 |
0 |
93 |
5/3 |
0 |
0 |
2/3 |
-2/3 |
1 |
-5/3 |
5/3 |
57 |
|
|
х3 |
0 |
9 |
0 |
0 |
1 |
0 |
0 |
0 |
- 1 |
1 |
-- |
|
|
Zj - сj 0 |
1380 |
-4/3 |
0 |
0 |
35/3 |
10/3 |
0 |
40/3 |
-40/3 |
|||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
М |
||||
|
х2 |
10 |
100 |
0 |
1 |
0 |
2/5 |
3/5 |
-2/5 |
2 |
-2 |
||
|
х1 |
8 |
57 |
1 |
0 |
0 |
2/5 |
-2/5 |
3/5 |
-1 |
1 |
||
|
х3 |
0 |
9 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 |
1 |
||
|
Zj - сj 0 |
1456 |
0 |
0 |
0 |
61/5 |
14/5 |
4/5 |
12 |
-12 |
|||
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
М |
|
Оптимальним планом задачі є вектор:
Х* = (57; 100; 9; 0; 0; 0; 0),
Отже, оптимальним є виробництво 57 одиниць продукції А, 100 одиниць продукції В і 9 одиниць продукції С.
Тоді прибуток буде найбільшим і становитиме 1456 грн.
2. Зациклення в задачах лінійного програмування
Як доведено вище, оптимальний план задачі лінійного програмування може знаходитись в одній з кутових точок багатогранника розв'язків, кількість яких є скінченною, тому, використовуючи для розв'язування задачі симплексний метод, за скінченну кількість кроків можна знайти оптимальний план або з'ясувати, що задача не має розв'язку. Однак строга монотонність симплексного алгоритму має місце лише у разі невиродженості всіх опорних планів, які отримані в ході ітераційної процедури алгоритму.
Якщо при дослідженні значень у симплексній таблиці існує кілька однакових значень з-поміж , то це означає, що можна вибрати для виключення з базису більш ніж один вектор. Наступна ітерація симплексного методу призведе до виродженого опорного плану, в якому хоча б одна з базисних змінних дорівнюватиме нулю.
Якщо деякий опорний план буде виродженим, тобто один або більше вільних членів основної системи обмежень дорівнюватимуть нулю, то при визначенні вектора, який необхідно на наступному кроці виводити з базису, найменше значення буде дорівнювати нулю і відповідати тому рівнянню, вільний член якого нульовий. Отже, в наступній ітерації буде виведена з базису відповідна змінна, причому всі значення базисних змінних в наступному опорному плані залишаться без змін, тобто значення цільової функції після проведення ітерації не зміниться.
Це означає, що наступні ітерації можуть не привести до покращення значення цільової функції. В такому разі після певного числа ітерацій дістають план, який вже було отримано раніше в процесі розв'язування задачі. Подальші ітерації, проведені аналогічно, приведуть до повторного перебору тих самих опорних планів. Вироджений план є причиною того, що теоретично виникає можливість нескінченного числа повторень однакових послідовностей ітерацій, які не покращують розв'язку, тобто обчислювальна процедура не буде мати кінця. Таку ситуацію називають зацикленням. Циклу можна було б уникнути, запам'ятовуючи опорні плани, що утворили цикл, і не повертаючись до них. Проте, щоб забезпечити однозначність вибору вектора, який виводиться з базису, розроблено ряд спеціальних прийомів. Найцікавішим з них є так званий -метод.
Виродженому плану відповідає вершина множини планів, що утворена більш ніж n гіперплощинами. Інакше кажучи, одна вершина відповідає кільком виродженим планам, що означає злиття кількох вершин багатогранника в одну. Ідея -методу усунення зациклення полягає в роз'єднуванні злитих вершин. Для цього досить, очевидно, ввести замість нулів у відповідні рівняння якісь інші значення, однак зробити це так, щоб не було знову кількох мінімальних співвідношень у наступному кроці. У такий спосіб замість початкової матимемо змінену задачу. Проте можна легко довести, що, діставши оптимальний план зміненої задачі, й допустивши, що введені величини дорівнюють нулю, матимемо оптимальний розв'язок початкової задачі.
На практиці вводять величини, які є дуже малими - це поліноми довільно взятої малої (близької до нуля) додатної величини . Коефіцієнтами поліномів беруть коефіцієнти при невідомих (базисних і небазисних) відповідного рівняння, а степенями -номери цих невідомих, тобто для деякого i-го рівняння маємо поліном виду:
Цілком зрозуміло, що для будь-яких можна вибрати настільки малим, що завжди , бо доданки зі степенями , вищими від і-го, будуть вищого порядку малості у порівнянні з першим . Внаслідок цього всі утворені поліноми різнитимуться за величиною. В оптимальному плані необхідно буде допустити, що .
Зауважимо, що в разі підозри на можливість зациклення (випадок, коли початковий опорний план вироджений) поліноми можна одразу додати до вільних членів системи обмежень, внаслідок чого матимемо:
.
3. Геометрична інтерпретація симплексного методу
Геометричну інтерпретацію симплекс-методу подамо способами.
· ілюструється зміна базису, яка здійснюється вибором векторів, які включаються до базису та виключаються з нього.
· процес симплексного методу інтерпретується як послідовний рух через сусідні кутові точки багатогранника розв'язків, що пов'язано зі збільшенням (зменшенням) цільової функції.
Дві кутові точки назвемо сусідніми, якщо вони розташовані на одному ребрі багатогранника.
Розглянемо задачу максимізації лінійної функції
1) Початковий опорний план відповідає кутовій точці А.
Другий крок симплексного методу приведе до точки Q, (),
Третій -- до точки K, де лінійна функція набуває максимального значення.
2) Якщо початковим опорним планом є В, то включення вектора до базису за критерієм приводить до того, що пряма проходитиме через точку С і алгоритм симплексного методу приведе до точок С, D, E, F, K, тобто для отримання оптимального плану необхідно буде виконати ще чотири ітерації.
Отже, очевидно, що застосування симплексного методу не дає змоги одразу перейти від опорного плану (точки В) до оптимального (точки К).
Фактично розв'язок отримують, рухаючись вздовж межі (ребер) простору розв'язків, причому не завжди такий шлях буде найкоротшим.
Кількість ітерацій за реалізації симплексного алгоритму визначається вибором початкового опорного плану та кількістю кутових точок на шляху прямої .
4. Модифікації симплексного методу
1. Двохетапний симплекс-метод. Проблеми зустрічаються тоді, коли штучні змінні є частиною початкового базисного розв'язку. Використання як М у цільовій функції дуже великих чисел може призвести до помилки округлення
Розглянемо задачу (2.60)--(2.61). Процес розв'язування у два етапи.
На першому етапі розв'язується задача виду:
лінійний програмування симплекс
за обмежень:
де - штучні змінні. Перший етап характеризується використанням лише великих чисел як коефіцієнтів цільової функції. Очевидно значення цільової функції для оптимального плану буде . Отже, при початкова задача має допустимий базисний розв'язок, причому такий, що не містить штучних змінних.
На другому етапі розв'язування задачі як початковий опорний план береться Х0, і процес продовжується за звичайним алгоритмом симплексного методу. На другому етапі задача не містить штучних змінних, отже, значення, що відповідають М, не розглядаються.
Крім того, якщо на першому етапі розв'язання задачі , то це означає, що деякі зі штучних змінних додатні, тобто допустимих планів для початкової задачі не існує, її система обмежень несумісна, задача розв'язків не має. Отже, немає потреби переходити до другого етапу .
Двохетапний метод застосовують до задач, що вимагають операцій над дуже великими числами, які входять у цільову функцію.
2. Модифікований симплексний метод. Застосування методу виключення змінних Жордана--Гаусса для отримання послідовного ряду симплексних таблиць призводить до накопичення і поширення помилок округлення в такій мірі, що вони спотворюють початкові дані задачі.
З метою зменшення впливу помилок округлення був розроблений модифікований симплексний метод. Основні етапи його алгоритму по суті такі ж, як і для симплексного методу. Головна відмінність полягає в тому, що для отримання послідовності симплексних таблиць у модифікованому симплексному методі не застосовується метод виключення змінних Жордана--Гаусса. Допустимо, що розглядається задача лінійного програмування, де базис утворюють останні n + m векторів, які позначимо через Х2, а відповідні їм коефіцієнти цільової функції -- через С2. Аналогічно перші n змінних позначимо через Х1, а відповідні коефіцієнти цільової функції -- через С1. Коефіцієнти векторів Х1 у системі обмежень утворюють матрицю А. Тоді схематично першу та останню симплексні таблиці можна подати у вигляді (табл. 2.11):
Таблиця 2.11
|
Базис |
План |
C1 |
C2 |
|
|
Х1 |
Х2 |
|||
|
Х2 |
b |
A |
E |
|
|
?j |
C2X2 |
C2A - C1 |
0 |
|
|
XВ |
b |
B-1A |
B-1 |
|
|
?j |
CB B-1b |
CB B-1A - C1 |
CB B-1A - C2 |
де В-1 -- матриця, обернена до одиничної, з першої симплексної таблиці. Як видно з наведеної табл. 2.11, вся симплексна таблиця сформована шляхом використання початкових даних (матриця А) та обернення поточного базису В-1. Отже, в обчислювальних процедурах модифікованого симплексного методу головна увага зосереджена на мінімізації помилок округлення при обчисленні матриці В-1.
Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення.
Размещено на Allbest.ru
Подобные документы
Початковий опорний план, перехід від одного до іншого. Оптимальний розв’язок, його головні критерії. Знаходження опорного плану задачі, складання симплексної таблиці. Приклад оформлення першої та другої таблиці для розв’язку задач лінійного програмування.
лекция [479,7 K], добавлен 10.10.2013Основні визначення дослідження операцій. Модель "затрати-випуск" В.В. Леонтьєва. Загальний вигляд задачі лінійного програмування. Розв'язання за допомогою симплекс-методу. Економічна інтерпретація основної та спряженої задач. Поліпшення плану перевезень.
учебное пособие [1,1 M], добавлен 27.12.2010Використання мови програмуванння Java при виконанні "задачі лінійного програмування": її лексична структура і типи даних. Методи розв’язання задачі. Особливості логічної структури програми, побудова її зручного інтерфейсу за допомогою симплекс методу.
курсовая работа [437,9 K], добавлен 24.01.2011Застосування симплекс-методу для розв’язання оптимізаційних задач лінійного програмування, що містять три змінні. Функції ітераційної обчислювальної процедури, що виконують приведення до зручного для розв’язання оптимального вигляду ЗЛП за кілька кроків.
курсовая работа [359,5 K], добавлен 18.09.2013Задача лінійного програмування. Розв’язання задачі геометричним методом. Приведення системи рівнянь до канонічного вигляду. Розв’язання симплекс-методом. Розв’язок двоїстої задачі. Задача цілочислового програмування і дробово-лінійного програм.
контрольная работа [385,2 K], добавлен 04.06.2009Постановка задачі багатокритеріальної оптимізації та її та математична модель. Проблеми і класифікація методів вирішення таких задач, способи їх зведення до однокритеріальних. Метод послідовних поступок. Приклад розв'язування багатокритеріальної задачі.
курсовая работа [207,3 K], добавлен 22.12.2013Використання графічного методу і симплекс-методу при вирішенні задач лінейного програмування. Сутність двоякого симплекс-методу і М-методу, приклади використання. Аналіз методу динамичного програмування. Специфіка вирішення матричної, антагоністичної гри.
контрольная работа [1,1 M], добавлен 02.07.2011Метод Якобі є узагальненням симплекса-методу лінійного програмування. Він використовується для дослідження чутливості оптимального значення функції до змін у правих частинах обмежень. Умови існування екстремумів функцій при відсутності обмежень.
курсовая работа [326,6 K], добавлен 09.01.2009Теоретичні основи та приклади економічних задач лінійного програмування. Розробка математичної моделі задачі (запис цільової функції і системи обмежень) і програмного забезпечення її вирішення за допомогою "Пошуку рішень" в Excel симплекс-методом.
курсовая работа [993,9 K], добавлен 10.12.2010Постановка та описання алгоритму розв’язання задачі про оптимальне призначення, формулювання вимог. Обґрунтування вибору засобів програмування. Розробка структури програми та системи її візуалізації, тестування та верифікація, оцінка ефективності.
курсовая работа [1,1 M], добавлен 12.05.2013
