Меню
Головна
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

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

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

(3.37)

(3.38)

(3.39)

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

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

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

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

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

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

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

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

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

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

(3.40)

(3.41)

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

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

Рис. 3.6

(3.42)

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

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

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

диференціюючи її за змінним .р)2,ХзД)Д2 і отримані вирази прирівнюємо нулю:

З першого і третього рівнянь слід, що тому

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

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

знайти ,

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

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

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

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

(3.43)

(3.44)

(3.45)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

де un(Sn) - всі допустимі управління за умови, що система знаходиться в стані Sn;

φn(Sn, un) - ефект від прийняття рішення un;

fn(Sn) - ефект за п кроків.

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

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

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

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

φn(xj) - дохід від застосування способу .

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

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

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

де

Знаходимо Оскільки на змінні xj накладаються умови целочисленности і неотрицательности, то знак (знак [] позначає цілу частину числа, тобто найбільше ціле число, яке не перевищує дане); таким чином, x1 Î {0,1,2}. Для кожного фіксованого значення l обчислюємо значення функції f1(l) вибираємо серед них максимальну, при цьому у відповідності з обмеженнями задачі X може приймати всі цілі значення від 0 до 8. Далі обчислюємо:

для всіх ;

для всіх

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

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

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

Таблиця 3.16

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

l

f1(l)

f2(l)

f3(l)

x1 = 0

x1 = 1

x1 = 2

x2 = 0

x2 = 1

x2 = 2

x3 = 0

x3 = 1

x3 = 2

x3 = 3

x3 = 4

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*

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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