НОУ ІНТУЇТ | лекція | Графічний метод оптимізації лінійних моделей

1. Ключові терміни
2. короткі підсумки
3. питання

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

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

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

У наступних лекціях будуть детально розібрані приклади розв'язання типових задач оптимізації та прийняття управлінських рішень за допомогою надбудови MS Excel "Пошук рішення". Завдання, які найкраще вирішуються даними засобом, мають три основні властивості:

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

Параметри завдань обмежуються такими граничними показниками:

• кількість невідомих - 200;
• кількість формульних обмежень на невідомі - 100;
• кількість граничних умов на невідомі - 400.

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

• підготовчі роботи;
• налагодження рішення;
• аналіз рішення.

Послідовність необхідних підготовчих робіт, які виконуються при вирішенні задач економіко-математичного моделювання за допомогою MS Excel, наведена на блок-схемі малюнка 1.6 .

Мал.1.6.

Схема підготовчих робіт

З наведених п'яти пунктів плану підготовчих робіт тільки п'ятий пункт є формалізованих. Решта робіт вимагають творчості - і різними людьми вони можуть бути виконані по-різному. Коротко пояснимо суть формулювань пунктів плану.

1. Визначення структури, постановка завдання вимагає чіткості в завданні обґрунтованих значень констант, змінних і цілей. Потрібно заздалегідь бачити можливі варіанти і до початку роботи сформулювати цілі подальшого аналізу рішення. Як говорив Цицерон, "Хто ясно мислить, той ясно викладає".
2. Під "складанням формалізованої моделі" тут розуміється графічне опис завдання у вигляді схеми або малюнка. Такий опис аналогічно складанню блок-схем алгоритму програми. Хорошим поданням умов завдання можуть служити ментальні карти, побудова яких описано в курсі [1]. Слід враховувати, що картинка завжди інформативніше тексту, а мислення людини здійснюється образами, а не буквами і словами.
3. Математична модель діяльності даної реальної системи зводиться до зв'язування формулами окремих елементів цієї системи. У попередньому прикладі ми висловили через формули витрата трудових і матеріальних ресурсів, а цільову функцію висловили через задані константи нормативних витрат і нормативного прибутку.
4. Подання математичної моделі у вигляді таблиці MS Excel також має відповідати вимогам ясності уявлення завдання. У таблиці слід чітко виділяти області:

   область змінних ;

   область вихідних нормованих коефіцієнтів ;

   область цільових коефіцієнтів ;

   область завдання ресурсів ;

   область цільової функції .

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

5. У діалозі "Пошук рішень" ми задаємо програмі оптимізації алгоритм мети. нехай - заданий число вихідних елементів, - заданий число ресурсів. У попередньому прикладі , - це полки типу і полки типу , а , - ми враховували тільки ресурс сировини (дошки) і ресурс машинного часу.

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

Крім того, завжди відомі значення ресурсів . У попередньому прикладі це був тижневий запас дощок і можливості використовувати машинний час: , . Часто в задачах значення змінних потрібно обмежити. Тому потрібно визначити нижній і верхній межі області їх змін.

Таким чином, в діалоговому вікні оптимизационной програми "Пошук рішення" ми повинні поставити наступне цільової алгоритм:

- цільова функція дорівнює добутку вектора шуканих значень змінних на вектор цільових коефіцієнтів

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

- значення змінної повинні знаходитися в заданих межах число вихідних елементів системи

- число вихідних елементів системи

- число заданих видів ресурсів

Налагодження рішення необхідна в разі, коли програма видає повідомлення про негативні результати ( малюнок 1.7 ):

Мал.1.7.

Схема налагодження і аналізу рішення

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

• якщо ніхто не почув допустиме рішення, то виконати коригування моделі вихідних даних;
• якщо не отримано оптимальне рішення, то ввести додаткові обмеження.

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

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

Економічний аналіз ставить перед собою наступні цілі [2]:

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

Можливі методи аналізу представлені в схемі на малюнку 1.8 .

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

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

• "що буде якщо…"
• "що треба, щоб ..."

Аналіз з метою відповіді на перше питання називається варіантним аналізом; аналіз з метою відповіді на друге питання називається рішеннями на замовлення.

Варіантний аналіз буває наступних видів:

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

Після проведення аналізу слід представити результати в графічній формі і скласти звіт з рекомендаціями про прийняття рішення з урахуванням конкретної економічної ситуації.

Ключові терміни

Лінійне програмування - математична дисципліна, присвячена теорії і методам вирішення екстремальних задач на множинах n-мірного векторного простору, що задаються системами лінійних рівнянь і нерівностей.

Математична модель - наближений опис об'єкта, виражене за допомогою математичної символіки, що відображає кількісні співвідношення між його елементами.

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

Цільова функція - функція, що зв'язує мета (що оптимізуються змінну) з керованими змінними в задачі оптимізації.

Матриця нормованих коефіцієнтів - постійні параметри об'єкта моделювання.

Ресурс - кількісна міра можливості виконання будь-якої діяльності; умови, що дозволяють за допомогою певних перетворень отримати бажаний результат.

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

Оптимальне рішення - допустиме рішення, для якого значення цільової функції максимально.

Аналіз рішення - заключний етап математичного моделювання економічних процесів.

короткі підсумки

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

питання

1. Сформулюйте в загальному вигляді задачу лінійного програмування.
2. Що таке симплекс-метод рішення задач оптимізації?
3. Що називається областю допустимих рішень?
4. Які рішення називаються оптимальними?
5. Як визначити, з якого боку від обмежувальної прямій лінії знаходиться область допустимих рішень?
6. Що таке пряма рівня?
7. Чи є оптимальне рішення єдиним?
8. Як провести аналіз рішення?