Навігація
Головна
Нелінійне і динамічне програмування; поняття про імітаційне...Метод лінійного програмування, симплекс-метод і лінійні оцінкиМетод динамічного програмування та оцінки для задач оптимального...Основи лінійного програмуванняОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯІмітаційні динамічні моделіІмітаційне моделюванняТеорія статистичних випробувань, або статистичного імітаційного...Прогнозування ймовірності пригод методом імітаційного моделюванняНедоліки лінійного програмування
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Нелінійне і динамічне програмування; поняття про імітаційне моделювання

Завдання нелінійного програмування формулюється так само, як і спільне завдання оптимального програмування, тобто у вигляді (3.37) - (3.39), з наступними вимогами до цільової функції і допустимої області: цільова функція або (і) хоча б одна з функцій є нелінійними:

(3.37)

(3.38)

(3.39)

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

• Безліч допустимих рішень опукло. Це опукле безліч має кінцеве число вершин, званих зазвичай крайніми (кутовими) точками.

• Безліч усіх точок n -мірного простору, в яких цільова функція приймає задане значення, є гіперплоскость (лінія) рівня. Крім того, гіперплощини, відповідні різним значенням цільової функції, паралельні.

• Локальний max або min є також глобальним шах або min цільової функції на множині допустимих рішень, тобто не існує локального оптимуму цільової функції, відмінного від глобального оптимуму.

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

У довільній задачі нелінійного програмування деякі або всі наведені вище властивості ЗЛП відсутні. Внаслідок цього задачі нелінійного програмування незрівнянно складніше завдань ЛЗ і для них не існує загального універсального методу рішення (аналогічного сімплексному методу).

Приклад 3.8. Знайти шах і min функції при обмеженнях

Рішення. Лінії рівня цільової функції (Z = const) являють собою кола з центром на початку координат; область допустимих рішень не є опуклою і складається з двох окремих частин (на рис. 3.6 ці частини заштриховані, лінії рівня показані пунктиром). Мінімальне значення функції Z = 17 досягається в точках А (1; 4) і L (4; 1). Функція Z має два локальних максимуму: у точці 0 (2/3; 6), де функція, і в точці М (7; 4/7), в якій функція Z (M) = 2417/49.

Точка М - точка глобального максимуму (рис. 3.6).

data-override-format="true" data-page-url = "http://stud.com.ua">

Особливе місце займають завдання типу

(3.40)

(3.41)

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

Для вирішення завдання складають функцію Лагранжа

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

Мал. 3.6

(3.42)

В основі методу Лагранжа вирішення класичної задачі оптимізації (3.40), (3.41) лежить твердження, що якщо функція в точці має екстремум, то існує такий вектор, що точка

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

Приклад 3.9. Знайти екстремум функції при обмеженнях

data-override-format="true" data-page-url = "http://stud.com.ua">

Рішення. Складаємо функцію Лагранжа

диференціюємо її по змінним і отримані вирази прирівнюємо нулю:

З першого і третього рівнянь випливає, що, тому

звідки • Оскільки, наприклад, точка (0; 2; 0) належить допустимої області і в ній Ζ = 0, то робимо висновок, що точка (1; 1; 1) - точка глобального максимуму.

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

знайти,

Відзначимо, що навіть для задач з лінійними обмеженнями обчислювальні методи розроблені лише в тих випадках, коли цільова функція має певні властивості, наприклад, функція Z - Сепарабельне, тобто

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

Такі нелінійні задачі називаються завданнями квадратичного програмування. Щоб бути впевненим, що оптимальне рішення і в цьому випадку може бути знайдено, на величини d ij слід накласти деякі обмеження.

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

(3.43)

(3.44)

(3.45)

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

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

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

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

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

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

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

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

• Кожен крок (вибір чергового рішення) пов'язаний з певним ефектом, який залежить від поточного стану та прийнятого рішення:

• Загальний ефект (дохід) за N кроків складається з доходів на окремих кроках, тобто критерій оптимальності повинен бути адитивним (або приводиться до нього).

Потрібно знайти таке рішення для кожного кроку (n = 1, 2, 3, ..., N), тобто послідовність (), щоб отримати максимальний ефект (дохід) за N кроків.

Будь-яка можлива допустима послідовність рішень () називається стратегією управління. Стратегія управління, що доставляє максимум критерію оптимальності, називається оптимальною.

В основі загальної концепції методу ДП лежить принцип оптимальності Веллман.

Оптимальна стратегія має таку властивість, що незалежно від того, яким чином система опинилася в розглянутому конкретному стані, наступні рішення повинні складати оптимальну стратегію, прив'язують до цього стану. Математично цей принцип записується у вигляді рекурентного співвідношення ДП (РДП):

де - всі допустимі управління за умови, що система перебуває в стані;

- Ефект від прийняття рішення;

- Ефект за решту п кроків.

Завдяки принципу оптимальності вдається при наступних переходах випробовувати нс всі можливі варіанти, а лише оптимальні виходи. РДП дозволяють замінити трудомістке обчислення оптимуму по N змінним у вихідній задачі рішенням N завдань, у кожній з яких оптимум знаходить лише по одній змінній.

Є дуже багато практично важливих завдань, які ставляться і вирішуються як завдання ДП (задачі про заміну обладнання, про ранці, розподілу ресурсів і т.д.)

Як приклад побудови РДII розглянемо використання принципу оптимальності для реалізації математичної моделі задачі оптимального розподілу деякого ресурсу в обсязі х.

де - кількість ресурсу, що використовується j-му способом;

- Дохід від застосування способу j,

Рекурентні співвідношення, за допомогою яких знаходиться вирішення цього завдання, мають вигляд:

Приклад 3.10. Знайти максимум функції при обмеженнях

- Цілі; j = 1, 2, 3.

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

де

Знаходимо. Оскільки на змінні накладаються умови целочисленности і неотрицательности, то (знак позначає цілу частину числа, тобто найбільшу ціле число, не перевершує дане); таким чином,. Для кожного фіксованого значення λ обчислюємо значення функції і вибираємо серед них максимальне, при цьому відповідно до обмеженнями задачі λ може приймати всі цілі значення від 0 до 8. Далі обчислюємо:

для всіх

для всіх

Всі обчислення наведені в табл. 3.16.

Таким чином, • Оптимальну стратегію знаходимо наступним чином. Спочатку встановлюємо, що (відповідає максимальному значенню 192).

Значення знаходимо з відповідних граф табл. 3.16 для при).

Далі знаходимо значення для при). Таким чином, оптимальна стратегія має вигляд (0; 0; 4).

Таблиця 3.16

Результати розрахунків відповідно до РДП

l

0

0

0

1

0

0

2

0

0

3

0

0

-4

4

0

3

0

-4

5

0

3

0

-4

6

0

3

0

-4

-8

7

0

3

0

-1

-8

8

0

3

12

0

-1

-8

12

6

27

81

192 *

Розглянемо далі ряд основних понять, пов'язаних з імітаційним моделюванням [20]. У всіх розглянутих вище оптимізаційних моделях, так чи інакше, передбачалася можливість використання аналітичних методів рішення, однак для багатьох завдань аналізу та управління в економіці такої можливості не існує. Якщо досліджувані процеси мають явно нелінійний характер і при цьому ускладнені різного роду імовірнісними характеристиками, то про практично корисному аналітичному рішенні не може бути й мови. У цих випадках можуть бути застосовані методи машинної імітації, тобто методи експериментального вивчення соціально-економічних систем за допомогою ЕОМ. Машинна імітація застосовується тоді, коли реальний економічний експеримент але якихось причин неможливий, і тоді імітація виступає в якості заміни реального експерименту або в якості попереднього етапу, що дозволяє прийняти більш обгрунтоване рішення про проведення такого експерименту.

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

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

1. Формування проблеми: опис досліджуваної проблеми і визначення цілей дослідження.

2. Розробка моделі: логіко-математичний опис модельованої системи в відповідності з формулюванням проблеми.

3. Підготовка даних: ідентифікація, специфікація і збір даних.

4. Трансляція моделі: переклад моделі зі спеціальних імітаційних мов, що використовуються на етапі 2 (СИМУЛА, Слами та ін.), На мову, прийнятний для використовуваної ЕОМ.

5. Верифікація: встановлення правильності машинних програм.

6. Валідація: оцінка необхідної точності й адекватності імітаційної моделі.

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

8. Експериментування: багаторазовий прогін імітаційної моделі на ЕОМ для отримання необхідної інформації.

9. Аналіз результатів: вивчення результатів імітаційного експерименту для підготовки висновків і рекомендацій щодо вирішення проблеми.

10. Реалізація та документування: реалізація рекомендацій, отриманих на основі імітації, і складання документації по моделі і її використанню.

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

У цьому випадку в основі імітаційного моделювання лежить метод статистичного моделювання (метод Монте-Карло). Цей метод дозволяє відтворювати на комп'ютері випадкові величини (с.в.) із заданими законами розподілу. Так як окремі реалізації цих с.в. отримані штучно, то їх реалізації називають псевдовипадковими числами. Процедури отримання псевдовипадкових чисел називають генераторами (датчиками) псевдовипадкових чисел.

Наприклад, при проведенні імітаційних експериментів у середовищі MS Excel (при використанні стандартних офісних засобів) можуть бути використані вбудовані датчики, генеруючі сім типів розподілів: рівномірний, Пуассона, нормальне, Бернуллі, біноміальний, модельне і дискретне (опції Інструменти аналізу / Генерація випадкових чисел надбудови Пакет аналізу).

Приклади імітаційного моделювання систем управління запасами і масового обслуговування засобами MS Excel наведені, наприклад, в літературі [1].[1]

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

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

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

Так, імітуючи роботу одноканальної СМО з відмовами, треба отримати N раз реалізації х i- відповідно с.в. тривалості інтервалів між окремими надходженнями вимог і с.в. тривалості інтервалів з обслуговування вимог і за допомогою "моделює алгоритму" зафіксувати число відмов в такій системі. При великому числі випробувань N отримаємо, наприклад, досить точну статистичну оцінку ймовірності відмови в обслуговуванні (звичайно, попередньо проводиться статистична оцінка гіпотез про характер законів розподілу вхідного потоку вимог і тривалості інтервалів обслуговування).

  • [1] Гармаш А. Н., Орлова І. В. Математичні методи в управлінні: навч. допомога. М .: Вузівський підручник, 2012.
 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >

Cхожі теми

Нелінійне і динамічне програмування; поняття про імітаційне моделювання
Метод лінійного програмування, симплекс-метод і лінійні оцінки
Метод динамічного програмування та оцінки для задач оптимального керування
Основи лінійного програмування
ОСНОВИ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Імітаційні динамічні моделі
Імітаційне моделювання
Теорія статистичних випробувань, або статистичного імітаційного моделювання
Прогнозування ймовірності пригод методом імітаційного моделювання
Недоліки лінійного програмування
 
Дисципліни
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук