План викладу і засвоєння лштеріалу

Імітаційне моделювання. Реалізація методів дослідження операцій. Обмеження в моделі лінійного програмування. Моделі транспортних задач.

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

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

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

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

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

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

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

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

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

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

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

На практиці реалізація методів дослідження операцій повинна включати наступні етапи:

1)   формалізація початкової проблеми;

2)   побудова математичної моделі;

3)   рішення моделі;

4)   перевірка адекватності моделі;

5)   реалізація рішення.

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

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

1) опис можливих альтернативних рішень;

2) визначення цільової функції;

3) побудова системи обмежень, що накладаються на можливі рішення.

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

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

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

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

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