Исследование операций и методы оптимизаций [DOC] - Все для студента. Методы оптимизации и исследование операций лекции
Исследование операций и методы оптимизаций [DOC]
- Добавлен пользователем newfeya, дата добавления неизвестна
- Отредактирован 01.04.2010 02:24
Обобщенная формулировка задачи исследования операций.Графический метод. Основные понятия. Алгоритм метода.Метод отсечений. Формулирование верного отсечения. Алгоритм метода.Метод ветвей и границ.Метод ветвей и границ относительно бинарных деревьев. Примеры задач, основные этапы, алгоритм нахождения оптимального решения.Комбинаторные методы.Метод лексикографического перебора.Метод неявного перебора по векторной решетке.Приближенные методы .Симплекс-метод. Основная идея, этапы поиска решений, алгоритм метода.Методы природного и искусственного базиса. Основные понятия, алгоритмы методов.Двойственные задачи линейного программирования. Постановка задач, их свойства.Методы субъективных измерений в задачах с неопределенностями. Основные понятия, суть, достоинства и недостатки методов.Индивидуальный выбор решений в условиях неопределенности. Типовые критерии выбора: их стратегии, суть, алгоритмы в случае оценки достоинств решений количественным методом субъективных измерений.Индивидуальный выбор решений в условиях неопределенности. Типовые критерии выбора: их стратегии, суть, алгоритмы в случае оценки достоинств решений качественным методом субъективных измерений. Групповой выбор решений в условиях неопределенности. Принципы группового выбора.Многокритериальные задачи исследования операций. КРИТЕРИЙ МАКСИМУМА-МИНИМУМА СРЕДНЕГО ВЫИГРЫША.Метод множителей Лагранжа.
- Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
- Регистрация
www.twirpx.com
Лекции - Методы оптимизации и исследования операций 2 (укр)
Лекции - Методы оптимизации и исследования операций 2 (укр)скачать (457 kb.)Доступные файлы (1):
n1.doc
18. Метод штучного базисуУ попередніх параграфах розглядався випадок, коли система обмежень задачі лінійного програмування містила одиничну матрицю порядку 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, а решта змінних вільні. Початковий опорний план задачі такий:
Складемо першу симплексну таблицю цієї задачі:
| Базис | Сбаз | План | 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 | 0 | 5 | 0 | 0 | 0 | 0 | |||
| – 9М | 0 | 0 | –М | 0 | 0 | 0 | М | 0 | |||
Оцінки першого плану не задовольняють умову оптимальності, і тому він є неоптимальним. Згідно з алгоритмом, розглянутим у задачі 2.41, виконуємо перехід до наступного опорного плану задачі. Після першої ітерації з базису виведена штучна змінна х8. Дальше розв’язування продовжуємо за алгоритмом симплексного методу.
Наступні кроки розв’язування задачі наведені у загальній таблиці:
| Базис | План | 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 грн.19. Зациклення в задачах лінійного програмування*
Як доведено вище, оптимальний план задачі лінійного програмування може знаходитись в одній з кутових точок багатогранника розв’язків, кількість яких є скінченною, тому, використовуючи для розв’язування задачі симплексний метод, за скінченну кількість кроків можна знайти оптимальний план або з’ясувати, що задача не має розв’язку. Однак строга монотонність симплексного алгоритму має місце лише у разі невиродженості всіх опорних планів, які отримані в ході ітераційної процедури алгоритму.
Якщо при дослідженні значень у симплексній таблиці існує кілька однакових значень з-поміж , то це означає, що можна вибрати для виключення з базису більш ніж один вектор. Наступна ітерація симплексного методу призведе до виродженого опорного плану, в якому хоча б одна з базисних змінних дорівнюватиме нулю.
Якщо деякий опорний план буде виродженим, тобто один або більше вільних членів основної системи обмежень дорівнюватимуть нулю, то при визначенні вектора, який необхідно на наступному кроці виводити з базису, найменше значення буде дорівнювати нулю і відповідати тому рівнянню, вільний член якого нульовий. Отже, в наступній ітерації буде виведена з базису відповідна змінна, причому всі значення базисних змінних в наступному опорному плані залишаться без змін, тобто значення цільової функції після проведення ітерації не зміниться.
Це означає, що наступні ітерації можуть не привести до покращення значення цільової функції. В такому разі після певного числа ітерацій дістають план, який вже було отримано раніше в процесі розв’язування задачі. Подальші ітерації, проведені аналогічно, приведуть до повторного перебору тих самих опорних планів. Вироджений план є причиною того, що теоретично виникає можливість нескінченного числа повторень однакових послідовностей ітерацій, які не покращують розв’язку, тобто обчислювальна процедура не буде мати кінця. Таку ситуацію називають зацикленням. Циклу можна було б уникнути, запам’ятовуючи опорні плани, що утворили цикл, і не повертаючись до них. Проте, щоб забезпечити однозначність вибору вектора, який виводиться з базису, розроблено ряд спеціальних прийомів. Найцікавішим з них є так званий -метод.
Виродженому плану відповідає вершина множини планів, що утворена більш ніж n гіперплощинами. Інакше кажучи, одна вершина відповідає кільком виродженим планам, що означає злиття кількох вершин багатогранника в одну. Ідея -методу усунення зациклення полягає в роз’єднуванні злитих вершин. Для цього досить, очевидно, ввести замість нулів у відповідні рівняння якісь інші значення, однак зробити це так, щоб не було знову кількох мінімальних співвідношень у наступному кроці. У такий спосіб замість початкової матимемо змінену задачу. Проте можна легко довести, що, діставши оптимальний план зміненої задачі, й допустивши, що введені величини дорівнюють нулю, матимемо оптимальний розв’язок початкової задачі.
На практиці вводять величини, які є дуже малими – це поліноми довільно взятої малої (близької до нуля) додатної величини . Коефіцієнтами поліномів беруть коефіцієнти при невідомих (базисних і небазисних) відповідного рівняння, а степенями -номери цих невідомих, тобто для деякого i-го рівняння маємо поліном виду:
Цілком зрозуміло, що для будь-яких можна вибрати настільки малим, що завжди , бо доданки зі степенями , вищими від і-го, будуть вищого порядку малості у порівнянні з першим . Внаслідок цього всі утворені поліноми різнитимуться за величиною. В оптимальному плані необхідно буде допустити, що .
Зауважимо, що в разі підозри на можливість зациклення (випадок, коли початковий опорний план вироджений) поліноми можна одразу додати до вільних членів системи обмежень, внаслідок чого матимемо: .
20. Геометрична інтерпретація симплексного методу
Геометричну інтерпретацію симплекс-методу подамо способами.
- ілюструється зміна базису, яка здійснюється вибором векторів, які включаються до базису та виключаються з нього.
- процес симплексного методу інтерпретується як послідовний рух через сусідні кутові точки багатогранника розв’язків, що пов’язано зі збільшенням (зменшенням) цільової функції.
Розглянемо задачу максимізації лінійної функції
1 )
Початковий опорний план відповідає кутовій точці А.
Другий крок симплексного методу приведе до точки Q, (),
Третій — до точки K, де лінійна функція набуває максимального значення. 2) Якщо початковим опорним планом є В, то включення вектора до базису за критерієм приводить до того, що пряма проходитиме через точку С і алгоритм симплексного методу приведе до точок С, D, E, F, K, тобто для отримання оптимального плану необхідно буде виконати ще чотири ітерації.
Отже, очевидно, що застосування симплексного методу не дає змоги одразу перейти від опорного плану (точки В) до оптимального (точки К).
Фактично розв’язок отримують, рухаючись вздовж межі (ребер) простору розв’язків, причому не завжди такий шлях буде найкоротшим.
Кількість ітерацій за реалізації симплексного алгоритму визначається вибором початкового опорного плану та кількістю кутових точок на шляху прямої .
21. Модифікації симплексного методу*
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 |
Модифікованим симплексним методом можна скористатись також для зменшення кількості операцій множення
nashaucheba.ru
Курс лекций: Исследование операций, методы оптимизации
Построение экономических и математических моделей принятия решений в условиях неопределенности. Общая методология оптимизационных задач, оценка преимуществ выбранного варианта. Двойственность и симплексный метод решения задач линейного программирования. Краткое сожержание материала:Размещено на
Тема 1: Общая методология оптимизационных задач. Основные понятия
1. Понятие оптимизационных задач, постановка задачи
2. Классификация задач оптимизации
1. Понятие оптимизационных задач, постановка задачи
Специалисты различных направлений часто сталкиваются с необходимостью решения оптимизационных задач. На практике встречаются разнообразные в содержательном смысле задачи оптимизации.
Например:
в экономике: при управлении банком: задача вложения денежных средств в различные проекты с целью получения максимальной прибыли с минимальным риском;
2) в технике: расчет оптимальной траектории полета ракеты; как управлять полетом ракеты добиваясь минимального расхода топлива.
3) в социологии: как распределить ограниченные ресурсы в государстве с целью уменьшения социальной напряженности в обществе.
Можно привести еще много примеров оптимизационных задач. Следует отметить, что важность и актуальность решения оптимизационных задач, возникающих в экономике, науке, технике и социологии, вызвали в последние четыре десятилетия интенсивные разработки моделей и методов оптимизации. Этому способствовало и бурное развитие средств вычислительной техники. Развитие моделей и методов оптимизации стимулировалось также значительным увеличением размерности и сложности оптимизационных задач, вызванных технологическим подъемом последних десятилетий.
Методы оптимизации являются частью дисциплины исследование операций.
Исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами. Природа «организационных систем» может быть различной, т.е. общие математические модели находят применение не только при решении производственных и экономических задач, но и в биологии, социальных исследованиях и других практических сферах.
Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены. Следовательно, цель исследования операций - количественное обоснование принимаемых решений по организации управления.
При решении конкретной задачи управления предполагается:
- построение экономических и математических моделей для принятия решений в сложных ситуациях или в условиях неопределенности;
- изучение взаимосвязей исследуемой системы и установление критериев эффективности, позволяющих оценивать преимущества того или иного варианта действия. Критерии могут быть, в зависимости от конкретной задачи, экономического или технологического характера (минимальная стоимость, максимальный крутящий момент). Независимо от того, какой критерий принят в качестве характеристического, он должен принимать максимальное (или минимальное) значение для наилучшего варианта.
Критериев может быть много, тогда задача становится многокритериальной. Существуют методы решения многокритериальных задач, но можно привести многокритериальную задачу к однокритериальной. Для этого один из критериев выбирается в качестве первичного, а остальные становятся вторичными. Первичный критерий используется как характеристический, а вторичные формируют ограничения задачи.
Примерами задач исследования операций, отражающих его специфику, могут служить следующие задачи.
Задача 1. Для обеспечения высокого качества выпускаемых изделий на заводе организуется система выборочного контроля. Требуется выбрать такие формы его организации назначить размеры контрольных партий, указать последовательность контрольных операций, определить правила отбраковки, чтобы обеспечить необходимое качество при минимальных расходах.
Задача 2. Для реализации определенной партии сезонных товаров создается сеть временных торговых точек. Требуется выбрать параметры сети число точек, их размещение, количество персонала так, чтобы обеспечить максимальную экономическую эффективность распродажи.
В каждой из задач речь идет о каком-то управляемом мероприятии (операции), преследующем определенную цель. В задаче 1 - это организация выборочного контроля с целью обеспечить качество выпускаемой продукции; в задаче 2 - организация временных торговых точек с целью проведения сезонной распродажи. В каждой задаче заданы условия проведения этого мероприятии, в рамках которого следует принять решение - такое, чтобы мероприятие принесло определенную выгоду. Условиями проведения операции в каждой задаче оказываются средства, которыми мы располагаем, формы, оборудование, технологии. А решение в задаче 1 заключается в выборе формы контроля размера контрольных операций, правил отбраковки; в задаче 2 в выборе числа точек размещения, количества персонала.
Таким образом, операция - это любое управляемое мероприятие, направленное на достижение цели. Результат проведения операции зависит от способа ее проведения и выбора параметров. Определенный выбор параметров называется решением. Оптимальными считаются те решения, которые по тем или иным соображениям предпочтительнее других.
Для применения методов оптимизации (количественных методов) требуется построить математическую модель. Модель представляет собой отражение реального объекта или процесса. В общем случае под термином «модель» понимается сложный объект, элементам которого можно поставить в соответствие элементы оригинала. Взаимосвязям или отношениям между элементами оригинала соответствуют взаимосвязи между определенными элементами модели.
При построении модели операция упрощается, схематизируется и схема операции описывается с помощью математического аппарата. Степень соответствия количества элементов модели количеству элементов оригинала, связей и отношений называется адекватностью модели оригиналу. Процесс построения модели называется моделированием.
Функцию, экстремальное значение которой необходимо найти в условиях экономических возможностей, называют целевой функцией, показателем эффективности или критерием оптимальности.
В общем виде математическая модель состоит из:
- совокупности неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи или вектором управления;
- целевой функции. Целевая функция позволяет выбрать наилучший вариант из множества возможных;
- системы ограничений, налагаемых на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми объект располагает в рассматриваемый период времени (ресурсы могут быть материальными, трудовыми и финансовыми). Совокупность ограничений образует область допустимых решений (область экономических возможностей).
Постановка задачи оптимизации.
Заданы множество и функция , определенная на множестве , требуется найти точки минимума или максимума.
Запишем задачу на минимум в виде:
(1)
где - целевая функция;
- допустимое множество;
- допустимая точка задачи
Точка , являющаяся решением задачи, может быть точкой глобального или локального минимума.
Точка называется
1) точкой глобального минимума функции на множестве или глобальным решением задачи (1), если (2)
2) точка х* называется точкой локального минимума, если существует некоторая окрестность этой точки, в любой точки которой значение функции больше, чем в x* - f(x)>f(x*) (3).
Ясно, что глобальное решение является и локальным; обратное неверно.
Проиллюстрируем на рисунке понятия локального и глобального оптимума для функции одной переменной.
Решения оптимизационных задач, то есть точки минимума и максимума функции на множестве , называются также точками экстремума, а сами задачи - экстремальными задачами.
2. Классификация задач оптимизации
Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функции и множества:
1) детерминированные, стохастические, задачи оптимизации с неопределенностями;
а) Детерминированная модель отражает поведение системы с позиции полной определенности в настоящем и будущем. Примеры таких моделей: формулы физических законов, программы обработки деталей и т.д.
б) Вероятностная модель учитывает влияние случайных факторов на поведение системы и, следовательно, оценивает будущее с позиций вероятности тех или иных событий.
в) Игровая модель дает возможность изучать конфликтные ситуации, в которых каждая из конфликтных сторон придерживается своих взглядов, старается получить информацию о намерениях «противника» и действует в соответствии складывающейся обстановке.
2) статические, динамические (например, задачи управления). Математические модели могут отражать состояние, в котором находится исследуемая система в какой-то момент времени, ил...
www.tnu.in.ua
