Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Інститут прикладної математики та фундаментальних наук
Факультет:
Не вказано
Кафедра:
Кафедра прикладної математики
Інформація про роботу
Рік:
2003
Тип роботи:
Конспект лекцій
Предмет:
Методи оптимізації
Частина тексту файла (без зображень, графіків і формул):
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
КАФЕДРА ПРИКЛАДНОЇ МАТЕМАТИКИ
Конспект лекцій з курсу
“МЕТОДИ ОПТИМІЗАЦІЇ”
( для студентів ІІІ курсу
Інституту прикладної математики та фундаментальних наук)
Підготувала
доцент кафедри ПМ
Уханська О.М.
2003
ВСТУП
Під задачами оптимізації підрозумівають будь-які задачі, переважно економічного характеру, в яких шукаються екстремуми функцій або функціоналів. Суть цих задач полягає в тому, щоб із множини можливих варіантів досліджуваного процесу вибрати за деякою ознакою найкращий (оптимальний) варіант.
Задачі оптимізації можна поділити на такі види:
задачі математичного програмування;
задачі варіаційного числення;
задачі оптимального управління.
Кожна велика система – фінансові чи банківські організації, великі промислові підприємства, військові з’єднання, системи охорони здоров’я, освіти тощо – функціонує заради досягнення певної мети. Усе те, що відбувається в системі, і ступінь досягнення мети, може бути описане математично. І одним з основних інструментів дослідження таких задач ( задач оптимізації) є математичне програмування.
Позначимо через z величину, якою вимірюється ступінь досягнення мети системи, а через - кількісні характеристики, від яких залежить досягнення мети, то зв’язок між і можна подати у вигляді функціональної залежності
(1)
Ця функція називається цільовою функцією або функцією мети.
Завдання математичного програмування полягає в тому, щоб знайти екстремум функції z при обмеженнях, які накладені на змінні :
(2)
Очевидно, що можливості вибору значень практично завжди обмежені. Система нерівностей (2) називається системою обмежень або системою умов задачі.
Зауважимо, що при складанні математичної моделі досліджуваного процесу необхідно дотримуватися загального правила: врахувати все істотне, суттєве в даному явищі чи процесі і відкинути все другорядне.
Множина точок (), що задовольняє систему обмежень (2), називається допустимою множиною або планом задачі математичного програмування. Сукупність усіх розв’язків системи (2), тобто множина всіх планів, утворює область існування планів або область визначення задачі математичного програмування. Допустима множина ( план ), що надає цільовій функції (функції мети) екстремального значення, називається оптимальним. Саме оптимальний план і є розв’язком задачі математичного програмування.
Перехід від постановки задачі до її розв’язку здійснюється за таким алгоритмом:
Побудова математичної моделі задачі – визначення факторів, що вважаються невідомими; побудова системи обмежень; побудова цільової функції на основі умови оптимізації.
Вибір методу розв’язку задачі.
Коригування математичної моделі.
Дослідження отриманого розв’язку і прийняття рішення.
Класифікація задач математичного програмування.
Класифікація задач математичного програмування залежить від критерію, згідно з яким вона проводиться, причому з погляду різних математичних критеріїв та сама задача може належати одночасно до декількох класів, оскільки кожен критерій підкреслює лише одну якість задачі на противагу деякій іншій.
Два основні класи становлять лінійні і нелінійні задачі математичного програмування. Критерієм лінійності задачі є лінійність цільової функції та всіх обмежень. У всіх інших випадках задача буде нелінійною. Перевага лінійних задач у тому, що вони завжди розв’язуються й існують універсальні методи їх розв’язування. Загальних методів розв’язування нелінійних задач не існує. Лише для окремих типів цих задач розроблено спеціальні методи пошуку розв’язку.
Задачі математичного програмування поділяють на дискретні та неперервні. Дискретні – це задачі, в яких усі або деякі змінні набувають дискретних значень. У деяких задачах умову дискретності кожної змінної можна подати умовою цілочисельності цих змінних. Методи розв’язування таких задач увійшли до розділу дискретного або цілочисельного програмування, який належить до нелінійного програмування. Якщо всі змінні задачі можуть набувати всіх значень із деякого інтервалу числової осі, то задача буде неперервною.
Важливим є критерій, за яким задачі поділяють на детерміновані та стохастичні. Детерміновані – це задачі, які не містять випадкових змінних і параметрів, що підлягають статистичним розподілам. Якщо ж випадкові явища становлять суть деякого процесу, то відповідна математична модель буде стохастичною, а відповідний розділ математичного програмування, що займається розв’язуванням таких задач, називається стохастичним програмуванням.
Крім того, задачі математичного програмування можна поділити на однокрокові та багатокрокові ( або динамічні ). Методи розв’язування багатокрокових задач об’єднано в розділ, що називається динамічним програмуванням.
РОЗДІЛ 1. ЛІНІЙНЕ ПРОГРАМУВАННЯ.
§ 1.1. Загальна постановка задачі лінійного програмування.
Розглянемо задачу про визначення оптимального асортименту продукції.
Підприємство може виготовляти два види виробів (№ 1 і № 2), використовуючи для їх виготовлення обмежену кількість матеріалів ( виду А і В відповідно не більше 1650 і 1200 кг ) і обладнання ( у кількості 2060 станко-годин).
Види
ресурсів
Об’єм
ресурсів
Затрати на одиницю продукції
Виріб №1
Виріб №2
А
1650 кг
10 кг
30 кг
В
1200 кг
10 кг
20 кг
Обладнання
2060 ст.-год.
23 ст.-год.
18 ст.-год.
Прибуток у
тис.грн..
34
40
Необхідно визначити, скільки виробів №1 і №2 повинне виготовити підприємство, щоб отримати найбільший прибуток, при умові, що виробів №1 має бути виготовлено не менше 20, а виробів №2 – не менше 15 одиниць.
Щоб розв’язати поставлену задачу, необхідно побудувати її математичну модель. Нехай - відповідно кількість виробів №1 і №2, які повинне виготовити підприємство (шукані невідомі). Очевидно, що повинні задовольняти умови
Тут перша умова вказує на те, що кількість сировини виду А, яка йде на виготовлення виробів №1 та виробів №2, не повинна перевищувати загальної кількості сировини А. Наведені нерівності є умовами обмеження по ресурсах. Крім того, невідомі і пов’язані обмеженнями по асортименту
.
Очевидно, що шукані невідомі повинні задовольняти умову невід’ємності.
Записані нерівності виражають всі умови обмежень, які накладаються на і . Будь-яка пара цілочисельних значень і , яка задовольняє системі цих нерівностей, визначає один із допустимих варіантів плану підприємства по випуску виробів №1 і №2. Таких допустимих варіантів буде безліч. Але нам, відповідно до умови задачі, необхідно вибрати такий варіант плану, для якого сумарний прибуток буде найбільшим. Цей варіант плану буде оптимальним. Якщо позначити через L прибуток підприємства, то . Отже, математично задачу можна сформулювати так: серед множини розв’язків системи нерівностей
знайти такий, для якого функція досягає найбільшого значення. Отримана задача і є задачею лінійного програмування.
Узагальнюючи наведений приклад, розглянемо задачу про максимальну рентабельність підприємства: запланувати виробництво продукції так, щоб при використанні наявних ресурсів (сировини, електроенергії, виробничих потужностей, праці та ін.) загальний прибуток від виробництва був найбільшим.
Запишемо загальну математичну модель задачі. Нехай
m – кількість наявних ресурсів;
n – кількість видів продукції, яку необхідно виготовити;
- кількість одиниць i –го ресурсу (), що використовується для виготовлення j – го виду продукції ();
- максимальна кількість одиниць i –го ресурсу, яку можна використати у виробництві (запас одиниць i –го ресурсу);
- прибуток від реалізації одиниці j – го виду продукції;
- запланований рівень виробництва одиниць j – го виду продукції.
Загальна кількість одиниць i –го ресурсу, що використовується у виробництві відповідно до плану, не може перевищувати запас i –го ресурсу, тобто
.
Крім того, .
Загальний прибуток від виробництва продукції дорівнює
,
де - прибуток, отриманий від виробництва одиниць j – го виду продукції. У термінах ЛП поставлену економічну задачу можна сформулювати так: знайти значення n змінних , при яких лінійна форма
досягає максимуму за умов
У реальних задачах лінійного програмування запис лінійної форми й умов обмежень неоднаковий: в одних задачах потрібно знайти мінімум лінійної форми, в інших- максимум; в одних задачах обмеження задані у вигляді системи лінійних нерівностей, в других – у вигляді рівнянь, в третіх – частина обмежень є у вигляді нерівностей, а інша частина обмежень має вигляд лінійних рівнянь. Також не у всіх задачах вимагається невід’ємність змінних.
Означення 1. Загальною формою задачі лінійного програмування є задача на знаходження екстремуму (мінімуму чи максимуму) лінійної цільової функції при лінійній системі обмежень, що включає як рівності, так і нерівності обох знаків, і при невідомих змінних, з яких одні пов’язані умовою невід’ємності, інші – умовою недодатності, а на знак третіх ніяких умов не накладено:
(1.1′ )
(1.2′ )
(1.2′′ )
(1.2′′′)
(1.3′ )
- умови не накладені.
Означення 2. Будь-який вектор , компоненти якого задовольняють умови (1.2′ )-(1.3′ ), називається планом (допустимим розв’язком) задачі лінійного програмування.
Множина всіх планів задачі лінійного програмування утворює область існування планів (область допустимих розв’язків).
Ранг матриці системи обмежень (1.2′) при умові, що визначає кількість базових змінних (залежних), усі решта змінні вважаються вільними (незалежними).
Позначимо
Тоді систему обмежень (1.2′)-(1.2′′′) можна записати у вигляді
.
Означення 3. План Х називається опорним планом (базисним допустимим розв’язком), якщо вектори , які відповідають додатним компонентам плану Х, утворюють лінійно-незалежну систему (максимальне число таких векторів не більше m).
Означення 4. Опорний план, вільні змінні якого дорівнюють нулю, а базові змінні дорівнюють значенням , називається базовим планом.
Означення 5. Опорний план називається невиродженим, якщо він містить рівно m додатних компонент, і виродженим, якщо додатних компонент є менше, ніж m.
Означення 6. План, що надає цільовій функції максимального значення називається оптимальним.
§ 1.2. Канонічна форма задачі лінійного програмування.
Записана модель задачі лінійного програмування є незручною для дослідження. Тому загальні властивості та методи розв’язування вивчають, записавши задачу лінійного програмування у канонічній формі, яка має вигляд
(1.1)
(1.2)
, (1.3)
де , , - задані постійні величини, причому .
Задача лінійного програмування вважається записаною у канонічній формі, якщо
система обмежень зведена до системи рівностей;
базова невідома входить лише в одне рівняння системи обмежень з коефіцієнтом 1, причому немає рівностей, у які б не входила хоча б одна базова невідома;
вільні члени системи обмежень невід’ємні;
оптимізуюча форма залежить тільки від вільних невідомих.
Будь-яку задачу лінійного програмування можна звести до канонічної форми:
Якщо необхідно знайти minL, то врахувавши. що minL=-max(-L), задача зводиться до пошуку максимуму лінійної форми -L.
Якщо в системі обмежень є нерівності виду
(1.4)
то ввівши додаткові невід’ємні змінні , перейдемо до рівності
(1.5)
Якщо в системі обмежень є нерівності виду
(1.4′ )
то аналогічно до попереднього випадку, отримаємо рівність
(1.5′ )
4. Якщо на змінні не накладено умов невід’ємності, то вводимо нові змінні , де .
У кожному з випадків 2, 3, 4 одержимо розширену задачу з n+k змінними: - для випадків 2 і 3 та - для випадку 3. Введені нові змінні вважаються базовими, а змінні - вільними.
Приклад. Звести задачу лінійного програмування до канонічного виду:
Перейдемо до задачі на знаходження максимуму
Введемо додаткові змінні .Замість змінної , на яку не накладено умови невід’ємності, введемо , .
§ 1.3. Властивості розв’язків задач лінійного програмування.
Запишемо задачу (1.1)-(1.3) у матричному вигляді
(1.6)
де
Нагадаємо означення опуклої множини.
Означення 1. Множина точок n-вимірного простору, яка містить разом із будь-якими двома точками А і В всі точки відрізка АВ , називається опуклою множиною.
Внутрішньою називається точка множини, для якої існує ε-окіл, що містить лише точки даної множини. Граничною називається точка, для якої існує ε-окіл, що містить як точки даної множини, так і ті, які не належать множині.
Означення 2. Граничні точки, які не лежать всередині відрізка, що з’єднує дві інші точки множини, називаються вершинами ( кутовими точками або крайніми точками ).
Якщо множина Q n-вимірного простору є опуклою і , то , або в загальному випадку .
Теорема 1. Множина всіх планів задачі лінійного програмування (1.6) є опуклою.
Доведення. ► Нехай - будь-які два плани задачі. Доведемо, що опукла комбінація цих планів є також планом. Оскільки - плани, то . Тоді , тобто X задовольняє умову (1.6)2 . Крім того , оскільки . Отже, X – план задачі. ◄
Як бачимо, для будь-яких двох планів їх опукла комбінація також є планом.
Теорема 2. Будь-який опорний план задачі лінійного програмування визначається вершиною опуклого многокутника.
Таким чином, пошук оптимального плану задачі лінійного програмування можна обмежити перевіркою вершин опуклої множини планів задачі.
Теорема 3. ( Критерій крайності точки опуклої множини ). Для того щоб точка опуклої множини планів задачі лінійного програмування була вершиною (крайньою точкою) необхідно і достатньо, щоб вектори , які відповідають додатним компонентам , утворювали лінійно незалежну систему.
Наслідок. Кожній вершині множини планів задачі лінійного програмування відповідає m лінійно незалежних векторів із системи векторів .
§ 1.4. Графічний метод розв’язування задач лінійного програмування.
Графічний метод використовують для розв’язування задач лінійного програмування з двома (трьома) змінними.
Нехай треба знайти max (min) лінійної функції
(1.7)
(1.8)
.
Розв’язок задачі шукаємо у такій послідовності:
На площині будуємо многокутник розв’язків, тобто ті точки площини, що задовольняють умови (1.8).
Знаходимо оптимальну точку, яка розміщена у вершині многокутника. Для цього використовуємо вектор нормалі , який є перпендикулярним до лінії рівня, що задається рівнянням . ( Нагадаємо, що лінією рівня функції називають лінію . Якщо - лінійна функція, то лінії рівня є паралельні прямі). Лінію рівня ще називають гіпер- прямою. Отже, проводимо через многокутник розв’язків гіпер-пряму, перпендикулярну до вектора нормалі . При паралельному перенесенні гіпер-прямої у напрямку у напрямку вектора значення цільової функції зростає. Знаходимо вершину многокутника, в якій досягається найбільше значення функції L (для знаходження точки мінімуму гіпер-пряму треба переміщувати у напрямку, протилежному до ). Лінії рівня (гіпер-прямі), що проходять через оптимальні вершини многокутників розв’язків, називають опорними (оптимальними).
Обчислюємо оптимальні значення. Знаходимо координати точки максимуму (мінімуму), отримані значення підставляємо у рівність (1.7) і обчислюємо .
Приклад. Знайти максимальне і мінімальне значення функції
при обмеженнях
Побудуємо многокутник розв’язків (ACBO).
Рис.1.1.
Будуємо вектор нормалі і гіпер-пряму . Переміщуючи гіпер-пряму в напрямку нормалі до перетину з останньою вершиною многокутника, знаходимо, що максимум досягається в точці С(3;4), а мінімум – в точці О. Обчислюємо оптимальні значення:
Зауважимо, що при розв’язуванні задач лінійного програмування графічним методом, область допустимих планів може мати вигляд
Рис.1.2 Рис.1.3
Рис.1.4. Рис.1.5.
Рис.1.6.
З рис.1.2 бачимо, що задача має єдиний розв’язок; рис.1.3 – задача має безліч розв’язків (гіперпряма паралельна до сторони ); рис.1.4 – цільова функція необмежена зверху; рис.1.5 – задача несумісна; рис.1.6 – задача має єдиний розв’язок (область допустимих значень складається з однієї точки).
§ 1.5. Симплексний метод розв’язування задач лінійного програмування .
Симплексний метод ( метод послідовного покращення плану ) є універсальним методом розв’язування задачі лінійного програмування, записаної у канонічній формі. Суть методу полягає у послідовному переході від одного опорного плану до іншого так, що значення лінійної форми весь час зростає (при умові, що задача має оптимальний розв’язок і всі опорні плани невироджені).
Розглянемо задачу лінійного програмування, записану в канонічній формі (1.1)-(1.3). Спочатку приведемо систему обмежень (1.2) до одиничного базису і припустимо для визначеності, що цей базис складається з перших m стовпців. Тобто система обмежень (1.2) матиме вигляд
.
Запишемо тепер задачу лінійного програмування у вигляді
(1.9)
. (1.10)
де
Припустимо, що всі . Поклавши вільні невідомі рівними нулю, із співвідношення (1.10) знаходимо, що базисний опорний план має вигляд і значення лінійної форми L для опорного плану дорівнює .
Побудова опорних планів задачі лінійного програмування.
Нехай - деякий невироджений опорний план задачі. Тоді виконується співвідношення (1.10). Невиродженому опорному планові відповідає система лінійно незалежних векторів , які утворюють базис в m-вимірному просторі. Тому кожен вектор із системи векторів можна єдиним чином розкласти за векторами базису, наприклад,
(1.11)
Припустимо, що для деякого вектора, наприклад ,який не належить до базису, хоча б один із коефіцієнтів у розкладі є додатним. Помножимо обидві частини останньої рівності на деяке число θ і віднімемо від (1.10):
.
Це означає, що вектор у випадку невід’ємності своїх компонент буде також планом. Очевидно, що компоненти вектора будуть невід’ємними при умові, що і для всіх i , для яких . Звідси . Тому при будь-якому θ, що задовольняє умову , де мінімум береться по тих i, для яких , вектор буде новим планом. Оскільки новий план повинен бути опорним, то θ треба вибрати так, щоб план мав не більше, ніж m додатних компонент. Якщо прийняти , де мінімум береться по тих i, для яких , то принаймні одна з перших m компонент вектора буде дорівнювати нулю. Нехай мінімум досягається при , тобто
.
Тоді при новий план матиме вигляд , де . Перехід до нового опорного плану здійснено шляхом введення в базис вектора замість . Аналогічно можна перейти до наступного опорного плану.
Зауваження 1. Ми припускали, що серед компонент у співвідношенні (1.11) є хоча б один додатний. Якщо ця умова не виконується , то лінійна форма на множині планів є необмеженою.
Зауваження 2. Якщо оптимальний план вироджений, то можливо, що ми не зможемо при обраному векторі , який вводимо в базис, перейти до нового опорного плану. У цьому випадку треба спробувати ввести в новий базис інший вектор або змінити базис, що відповідає X.
Теоретичні основи симплекс-методу.
Задача лінійного програмування має скінчене число опорних планів і після скінченого числа ітерацій процес послідовного покращення розв’язку повинен обірватися. Це означатиме, що знайдено найкращий опорний розв’язок, при якому цільова функція досягає максимуму. Проте, якщо функція необмежена в області допустимих розв’язків, то отриманий опорний розв’язок є лише найкращим серед опорних, але не оптимальним . Виникає питання, чи можна про це довідатися в процесі виконання послідовних ітерацій. Відповідь на ці запитання дають теореми, які є основними для симплексного методу.
Покладемо
( - координати розкладу вектора через вектори базису ). Оскільки базис утворюють одиничні вектори, то .
Теорема 1. (Ознака оптимальності опорного плану).
Якщо , то опорний план є оптимальним.
Теорема 2. (Ознака необмеженості лінійної форми на множині планів).
Якщо для деякого і всі , то для заданої задачі цільова функція необмежена зверху.
Теорема 3. (Ознака переходу до нового опорного плану).
Якщо для деякого , але серед коефіцієнтів є хоча б один додатний, то можна перейти до нового опорного плану , для якого , якщо опорний план невироджений.
Результати послідовних ітерацій симплексних перетворень зручно записувати у вигляді таблиць, які називаються симплексними таблицями.
№
Б
Сб
P0
с1
с2
...
сm
cm+1
…
ck
…
cn
P1
P2
…
Pm
Pm+1
…
Pk
…
Pn
1
P1
с1
b1
1
0
…
0
a1m+1
…
a1k
…
a1n
2
P2
с2
b2
0
1
…
0
a2m+1
…
a2k
…
a2n
…
…
…
...
…
…
…
…
…
…
…
…
…
r
Pr
cr
br
0
0
…
0
ar m+1
…
ar k
…
ar n
…
…
…
…
…
…
…
…
…
…
…
…
…
m
Pm
cm
bm
0
0
…
1
amm+1
…
amk
…
amn
m+1
L0
0
0
…
0
Δm+1
…
Δk
…
Δn
В перших m рядках симплекс-таблиці розміщені вектори базису ( стовпець Б ), відповідні компоненти лінійної форми ( стовпець Сб ), компоненти опорного плану (стовпець Р0), коефіцієнти розкладів векторів через вектори базису (стовпці ). В останньому рядку симплекс-таблиці записуємо значення лінійної форми, що відповідає розглянутому опорному планові і різниці .
Якщо після побудови першої симплекс-таблиці виявилось, що виконуються умови першої або другої теореми, то розв’язування задачі припиняється. Якщо виконуються умови третьої теореми, то будуємо нову симплекс-таблицю і переходимо до нового опорного плану.
Для переходу до нового опорного плану необхідно один вектор вивести з базису і на його місце ввести новий, який не належав до базису. Цей новий вектор визначається найбільшим по модулю від’ємним значенням . Якщо таких декілька, то вибираємо те, для якого максимальне. Якщо , то вводимо в базис вектор . Вектор, який виводиться з базису, визначається величиною , де мінімум береться по тих , для яких . Стовпець з номером , рядок з номером і елемент називаються відповідно ключовим (або розв’язуючим) стовпцем, рядком та елементом. Опорний план, що відповідає новому базисові, матиме координати, які визначаються за формулами
Нове значення цільової функції обчислюють за формулою
.
При розв’язуванні вихідної задачі припускалось, що всі опорні плани не вироджені (). Якщо серед опорних планів задачі лінійного програмування є вироджені, то при переході від одного виродженого плану до іншого може статися так, що опорний план не зміниться, а зміниться лише базис, що йому відповідає. Такий перехід може відбутися декілька разів. Якщо при цьому ми повертаємося до базису, що вже мав місце, то в алгоритмі симплексного методу утворюється цикл (відбувається зациклення). У цьому випадку доводиться використовувати спеціальні додаткові прийоми виходу з циклу. В реальних умовах таких задач майже не зустрічається.
Приклад. Знайти найбільше значення лінійної функції на множині невід’ємних розв’язків системи нерівностей
Зведемо задачу до канонічного вигляду
Оскільки ранг матриці системи обмежень дорівнює 2, то матимемо два базисні вектори. За базисні змінні приймемо ( базисні вектори ), а змінні є вільними. Запишемо першу симплекс-таблицю:
№
Б
Сб
Р0
3
2
0
0
Р1
Р2
Р3
Р4
1
Р3
0
12
2
3
1
0
2
Р4
0
4
2
-1
0
1
3
0
-3
-2
0
0
Початковий опорний план має вигляд . Значення лінійної форми . Обчислимо значення
.
Згідно з теоремою 3 можна перейти до нового опорного плану ( , а серед коефіцієнтів у відповідному стовпці є додатні ). Оскільки , то в базис необхідно ввести вектор . Визначимо, який вектор потрібно вивести з базису. Складемо відношення вільних членів ( чисел стовпчика ) до відповідних додатних чисел ключового стовпчика ( ): 12/2=6, 4/2=2 і вибираємо з них найменше. Отже, елемент 2, що стоїть на перетині стовпця і рядка , буде ключовим, а з базису необхідно вивести вектор . Переходимо до наступної ітерації.
Кожен елемент ключового рядка (2), починаючи зі стовпчика , ділимо на ключовий елемент 2 і результат записуємо в нову таблицю у другий рядок. До елементів першого рядка старої таблиці, починаючи зі стовпчика , додаємо відповідні елементи другого рядка нової таблиці, помножені на таке число, щоб у клітинках ключового стовпчика були нулі ( тобто від відповідних елементів першого рядка старої таблиці віднімаємо відповідні елементи другого рядка нової таблиці, помножені на 2). В результаті отримуємо новий опорний план , для якого , .
Отриманий новий опорний план знову не є оптимальним і згідно з теоремою 3 переходимо до нового опорного плану. Провівши аналогічні міркування, приходимо до висновку, що в базис необхідно ввести вектор , а вивести з базису – вектор .Новий ключовий елемент дорівнює 4. Остаточно отримуємо (див. останню симплекс-таблицю) опорний план , для якого , .
№
Б
Сб
Р0
3
2
0
0
Р1
Р2
Р3
Р4
1
Р3
0
8
0
4
1
-1
2
Р1
3
2
1
-1/2
0
1/2
3
6
0
-7/2
0
3/2
1
Р2
2
2
0
1
1/4
-1/4
2
Р1
3
3
1
0
1/8
3/8
3
13
0
0
7/8
5/8
Отже, всі , і опорний план є оптимальним, тобто при лінійна функція досягає максимуму і .
§ 1.6. Метод штучного базису пошуку початкового опорного плану (М-метод).
Якщо початковий опорний план задачі лінійного програмування не є очевидним (тобто система умов задачі не містить одиничну матрицю і не всі вільні члени невід’ємні), то для його знаходження застосовують метод штучного базису. Ідея методу полягає в тому, що в ліву частину кожного -го рівняння системи обмежень задачі, яка задана в канонічній формі, і не має одиничного базису, додають по одній штучній змінній , утворюючи таким чином штучний базис. Отже, в початковій симплекс-таблиці всі основні змінні будуть вільними і будуть дорівнювати нулю в штучному базовому розв’язку, а штучні змінні (фактичні нулі) дорівнюватимуть правим частинам системи обмежень. Вектори називаються штучними векторами, а базис, який вони утворюють – штучним базисом. Початковий опорний план матиме вигляд . Щоб знайти оптимальний план задачі, потрібно всі штучні змінні вивести з базису; якщо цього зробити не можна, маємо суперечливі умови задачі.
Побудуємо нову цільову функцію
,
де М – довільне велике число, і розглянемо так звану розширену задачу ( або М-задачу ):
.
Якщо в оптимальному плані розширеної задачі всі штучні змінні дорівнюють нулю, то відповідний йому план вихідної задачі буде оптимальним.
Для зручності обчислень у симплекс-таблиці цільову функцію розкладають на два доданки: перший, що залежить від основних змінних, і другий – від штучних, тобто
У симплекс-таблицю вводять два індексних рядки: -й для L і -й для доданка , причому, оскільки M є спільним множником для всіх елементів другого індексного рядка, то його можна вивести за межі рядка. Всі обчислення здійснюють на основі звичайних симплекс-перетворень. Ітераційний процес починають по -му рядку. Вектор, який потрібно ввести в базис, визначається за найбільшим по модулю від’ємним числом -го рядка. Цей процес триває доти, доки:
Всі штучні вектори не будуть виведені з базису.
Не всі штучні вектори виведені з базису, але в -му рядку немає від’ємних елементів.
У першому випадку переходимо до опорного плану вихідної задачі і ітераційний процес продовжуємо по -му рядку. У другому випадку, якщо поточне значення цільової функції , то задача немає розв’язку; якщо , то опорний план буде виродженим ( у базис входитиме як мінімум один штучний вектор).
Зауважимо, якщо в системі обмежень вихідної задачі є декілька одиничних векторів, то їх необхідно врахувати при побудові розширеної задачі.
Приклад.
В цьому прикладі система обмежень не містить одиничної матриці, тому вводимо штучні змінні і будуємо розширену задачу:
.
Будуємо симплекс-таблиці.
Початковий опорний план розширеної задачі має вигляд , , , , , .
Вводимо в базис вектор (), а виводимо з базису вектор (18/4=4.5 – min).
№
Б
Сб
Р0
2
-1
3
-1
-М
-М
Р1
Р2
Р3
Р4
Р5
Р6
1
Р5
-М
18
4
-2
1
3
1
0
2
Р6
-М
16
3
1
2
1
0
1
3
L0=0
-2
1
-3
1
0
0
4
-34
-7
1
-3
-4
0
0
1
Р1
2
9/2
1
-1/2
1/4
3/4
0
2
Р6
-М
5/2
0
5/2
5/4
-5/4
1
3
9
0
0
-5/2
5/2
0
4
-5/2
0
-5/2
-5/4
5/4
0
1
Р1
2
5
1
0
1/2
1/2
2
Р2
-1
1
0
1
1/2
-1/2
3
9
0
0
-5/2
5/2
4
0
0
0
0
0
1
Р1
2
4
1
-1
0
1
2
Р3
3
2
0
2
1
-1
14
0
5
0
0
У -му рядку передостанньої симплекс-таблиці немає додатних чисел серед значень , оптимальний план розширеної задачі має вигляд , а план - початковий опорний план для вихідної задачі. З останньої симплекс-таблиці знаходимо оптимальний план .
РОЗДІЛ 2. ЕЛЕМЕНТИ ТЕОРІЇ ДВОЇСТОСТІ.
§ 2.1. Постановка двоїстої задачі лінійного програмування.
На прикладі задачі про одержання максимального прибутку від виготовлення різнотипної продукції з обмеженої кількості сировини можна розглянути обернену задачу: яку мінімальну кількість різнотипної сировини потрібно для виготовлення встановленої кількості продукції різних видів. Першу задачу вважають основною (прямою), а обернену до неї – двоїстою.
З кожною задачею лінійного програмування тісно пов’язана двоїста. Розглянемо пряму задачу лінійного програмування
(2.1)
(2.2)
(2.3)
Означення. Двоїстою до основної задачі (2.1)-(2.3) називається така задача:
знайти сукупність значень , які задовольняють систему нерівностей
і умови невід’ємності , для яких функція досягає мінімуму.
Отже, двоїста задача має вигляд
(2.4)
(2.5)
(2.6)
Пряма і двоїста задача утворюють пару задач лінійного програмування, яка називається двоїстою парою. Двоїста пара називається спряженою ( симетричною ), якщо в системі обмежень прямої задачі є лише нерівності із знаком “≤”, а в системі обмежень двоїстої задачі – лише знаки“≥”.
Поняття двоїстості є взаємним. Якщо одна з пари двоїстих задач має розв’язок (існує оптимальний план), то і друга задача також має розв’язок, причому . Якщо цільова функція однієї з пари двоїстих задач є необмеженою на множині своїх планів, то відповідна двоїста задача має суперечливу систему умов. Якщо одна з пари двоїстих задач має суперечливу систему умов, то друга або має необмежену цільову функцію на множині своїх планів, або також має суперечливу систему умов.
Зв’язок між прямою і двоїстою задачами лінійного програмування.
Теорема 1. (Перша теорема двоїстості). Якщо одна з пари двоїстих задач має розв’язок, то й інша також має розв’язок, причому для довільних планів і виконується співвідношення .
Теорема 2. (Друга теорема двоїстості). Для того щоб плани прямої і двоїстої задач були оптимальними, необхідно і достатньо, щоб для кожного виконувалась умова додаткової нежорсткості
Зауважимо, що для пари спряжених задач умов додаткової не жорсткості є дві:
Теорема 3. (Критерій оптимальності планів двоїстих задач). Для того щоб плани прямої і двоїстої задач були оптимальними, необхідно і достатньо, щоб .
Для знаходження розв’язку несиметричної пари задач достатньо розв’язати сиплекс-методом одну з них. Припустимо, що - оптимальний план прямої задачі лінійного програмування , знайдений симплекс-методом. Якщо вектори утворюють базис, що відповідає плану , - матриця, складена з компонент базисних векторів, то . Виявляється, що при перетворенні симплекс-таблиць матриця отримується автоматично. Вона записана в перших рядках останньої симплекс-таблиці в стовпчиках базисних векторів при розв’язуванні прямої задачі. Тоді нема необхідності визначати оптимальний план двоїстої задачі за допомогою множення , оскільки компоненти цього плану дорівнюють сумі відповідних елементів -го рядка стовпців одиничних векторів і .
Це стосується і спряженої (симетричної) пари задач. Причому оскільки система обмежень прямої задачі містить нерівності виду “≤”, то компоненти оптимального плану двоїстої задачі співпадають з відповідними числами -го рядка останньої симплекс-таблиці вихідної задачі, які стоять у стовпцях, що відповідають додатковим змінним.
Якщо пара двоїстих задач містить дві змінні, то її можна розв’язати графічним методом.
Приклад. Знайти розв’язки пари двоїстих задач.
Пряма задача Двоїста задача
Графічні розв’язки цих задач мають вигляд
§ 2.2. Економічна інтерпретація двоїстої задачі.
Нехай необхідно знайти оптимальний виробничий план чотирьох видів продукції, при виготовленні яких використовують три види сировини , щоб отримати максимум товарної продукції, і оцінити кожний вид сировини так, щоб оцінка сировини, що використовується, була мінімальною, а сумарна .оцінка сировини, яка йде на виготовлення одиниці продукції кожного виду, - не меншою від ціни одиниці продукції даного виду.
Вид
сировини
К-ть
сировини
Норма сировини на одиницю продукції
Ціна
одиниці
сировини
1
2
3
4
А
35
4
2
2
3
у1
В
30
1
1
2
3
у2
С
40
3
1
2
1
у3
Ціна одиниці продукції
14
10
14
11
Позначимо через кількість одиниць кожного з видів продукції, що випускається. Запишемо задачу лінійного програмування:
Побудуємо двоїсту задачу. Оцінимо кожну одиницю використовуваних ресурсів, які визначають максимальні виробничі можливості підприємства, тобто одиниці сировини кожного виду поставимо у відповідність умовну двоїсту оцінку: .Тоді загальна оцінка сировини, що використовується на випуск продукції, буде дорівнювати:
[сумарна вартість сировини]
Двоїсті оцінки повинні бути такими, щоб сумарна оцінка сировини, яка йде на виготовлення одиниці продукції кожного виду, була не меншою від ціни одиниці продукції даного виду, тобто повинні задовольняти систему нерівностей:
[ продаж запасів сировини ]
Отже, пряма задача полягає у визначенні оптимального плану випуску продукції при заданих обмежених ресурсах сировини, що забезпечує максимум товарної продукції, а двоїста задача полягає у визначенні оцінок одиниці кожного з ресурсів при умові їх мінімальної сумарної вартості.
Застосувавши симплекс-метод до розв’язування прямої задачі, отримаємо останню симплекс-таблицю:
№
Б
Сб
Р0
14
10
14
11
0
0
0
Р1
Р2
Р3
Р4
Р5
Р6
Р7
1
Р2
10
5
3
1
0
-2
1
-1
0
2
Р3
14
25/2
-1
0
1
35/14
-1/2
1
0
3
Р7
0
10
2
0
0
-2
0
-1
1
4
225
2
0
0
4
3
4
0
Оптимальний план, при якому досягається максимум товарної продукції , буде , при якому виготовляється 5 одиниць виробів 2-го виду і 12.5 одиниць 3-го виду. При цьому залишається невикористаним 10 одиниць сировини виду (). З таблиці бачимо, що оптимальний розв’язок двоїстої задачі (оцінки для одиниці кожного з видів сировини) має вигляд: (елементи останнього рядка, які відповідають базисним змінним ).
Ті види сировини, які повністю використовуються при оптимальному плані виробництва, мають додатні двоїсті оцінки. Іншими словами, додатні двоїсті оцінки вказують на дефіцитність сировини. Отже, умовні двоїсті оцінки означають, що сировина видів та використовуються повністю. Крім того, додатні умовні двоїсті оцінки вказують на скільки грошових одиниць збільшиться максимальне значення цільової функції прямої задачі при збільшенні відповідних ресурсів на одиницю. Так збільшення використання ресурсів виду на 1 одиницю приведе до нового оптимального плану, при якому вартість збільшиться на 3 одиниці ( одиниці ) за рахунок того, що збільшиться випуск продукції 2-го виду на 1 одиницю і зменшиться кількість випущеної продукції 3-го виду на 1/2; при цьому кількість використаної сировини виду не зміниться. (Усі ці дані ми беремо зі стовпця ).
Аналогічно збільшення використання сировини виду на 1 одиницю приведе до
збільшення на 4 одиниці за рахунок зменшення випуску продукції 2-го виду на 1 одиницю і збільшення випуску продукції 3-го виду на 1 одиницю; при цьому використання сировини виду збільшиться на 1 одиницю ( ці дані беремо зі стовпця ).
Умовна двоїста оцінка означає, що сировина виду повністю не використовується при даному оптимальному плані виробництва ( ця сировина є у надлишку ).
Підставивши значення умовних двоїстих оцінок у цільову функцію і в систему обмежень двоїстої задачі, отримаємо і :
Перша строга нерівність означає, що двоїста оцінка сировини, яка йде на випуск одного виробу 1-го виду, є вищою від вартості цього виробу, тому випускати продукцію першого виду економічно невигідно ( це передбачено й оптимальним планом - ). Аналогічно невигідно випускати і продукцію четвертого виду (четверта нерівність; ). Строгі рівності означають, що з економічної точки зору вигідно випускати продукцію 2-го і 3-го виду ( двоїсті оцінки сировини, що використовуються для виробництва одиниці виробів відповідно 2-го і 3-го видів, точно дорівнюють їх цінам; в оптимальному плані маємо, що ).
Отже, двоїсті оцінки тісно пов’язані з оптимальним планом прямої задачі. Зміна даних прямої задачі впливатиме як на оптимальний план, так і на систему двоїстих оцінок. Тому виникає питання про інтервал стійкості двоїстих оцінок.
Розглянемо значення як функцію від вільних членів системи обмежень прямої задачі, записаної у канонічній формі, тобто .
Теорема. В оптимальному плані двоїстої задачі (2.4)-(2.6) значення змінної чисельно дорівнює частинній похідній від функції по даному аргументу
.
Остання рівність означає, що зміна значень величин приводить до збільшення або зменшення . Ця зміна визначається величиною . Виникає проблема: міняти вхідні дані ( кількість використовуваних ресурсів ) так, щоб значення умовних двоїстих оцінок не змінювалися. Іншими словами, необхідно знайти такі інтервали зміни , в межах яких оптимальний план двоїстої задачі залишається незмінним. Це має місце для тих значень , при яких стовпчик вектора останньої симплекс-таблиці прямої задачі не містить від’ємних чисел, тобто компоненти вектора
повинні бути невід’ємними. Тут - матриця, обернена до матриці , утвореної з компонент векторів базису, який визначає оптимальний план прямої задачі.
Визначимо інтервали стійкості двоїстих оцінок по відношенню до зміни ресурсів кожного типу для останнього прикладу. Знайдемо компоненти вектора
.
( компоненти матриці записані у стовпцях , оскільки ці вектори утворюють початковий базис прямої задачі). З умови невід’ємності компонент знаходимо:
.
Нехай : тоді .
Якщо кількість ресурсів виду належить вказаному інтервалові, а кількість решти видів ресурсів не змінюється, то двоїста задача має такий самий оптимальний план .
Нехай : тоді .
Нехай : тоді .
Остання нерівність означає: якщо кількість сировини виду буде збільшено чи зменшено в межах 10 одиниць, оптимальний план двоїстої задачі не зміниться.
Знайдемо тепер як зміниться значення цільової функції при оптимальному плані прямої задачі, якщо зменшити кількість сировини виду на 3 одиниці, а кількість сировини видів збільшити відповідно на 4 і 5 одиниць. Спочатку перевіримо, чи можна проводити вказані зміни. Для цього знайдемо
Отже вказані зміни у використанні сировини можна вносити ( оптимальний план двоїстої задачі при цьому не зміниться ). Знайдемо приріст функції
.
Це означає, що значення цільової функції збільшиться на 7 одиниць, тобто можна побудувати такий план виробництва продукції, що прибуток від реалізації буде на 7 одиниць вищим від запланованого при початково заданих кількостях сировини. Зауважимо, що збільшення кількості сировини виду не впливає на величину прибутку, в той час як збільшення кількості сировини виду на 4 од. веде до збільшення значення на 16 од., а зменшення сировини виду на 3 од. веде до зменшення на 9 од.
Якщо значення величин змінюються одночасно, то дослідження стійкості двоїстих оцінок значно ускладнюється.
§ 2.3. Двоїстий симплекс-метод.
Двоїстий сипмлекс-метод використовується для знаходження розв’язку задач лінійного програмування, записаних у формі прямої задачі у випадку, коли вільні члени в системі обмежень приймають довільні значення ( а не лише невід’ємні ). Розглянемо задачу лінійного прог...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора