ВАРІАНТ 10

1. Метод віток і меж.

Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж.

Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм.

Ефективнішим за метод Гоморі розв’язування задач цілочислового програмування є метод «віток і меж». Спочатку, як і в разі методу Гоморі, розв’язується послаблена (відкиданням умови цілочисловості) задача.

З цією метою застосовується симплексний метод.

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

Наприклад, якщо дістаємо інтервал (2,3), де, очевидно, немає хj, яке набуває цілого значення.

Значенню відповідає інтервал (–3; –2), де також не існує цілого значення хj. Отже, допустиме ціле значення xj має задовольняти одну з нерівностей

або .

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

(6.5)

за умов

(6.6)

,

, (6.7)

— цілі, (6.8)

; (6.9)

(6.10)

за умов

(6.11)

,

, (6.12)

— цілі, (6.13)

, (6.14)

де — компонент розв’язку задачі (6.1)—(6.4).

Далі симплекс-методом розв’язуємо послаблені задачі (6.6)—(6.9) і (6.10)—(6.14), тобто з відкиданням обмежень (6.8) і (6.13). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв’язками задачі (6.1)—(6.4). Інакше пошук розв’язку задачі триває. Для подальшого розгалуження беремо задачу з найбільшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки — з найменшим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення роз­в’язку. Здобутий план — оптимальний.

2. Четверта задача прийняття багатоцільових рішень за умов ризику. Ст. 253

ВАРІАНТ 11

1. Предмет і задачі дослідження операцій

1.1 Предмет дослідження операцій

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

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

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

 Ціль дослідження операцій - попереднє кількісне обгрунтування оптимальних рішень.

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

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

1.2. Прямі і зворотні задачі дослідження операцій

Задача дослідження операцій діляться на два класи: прямі і зворотні.

 Прямі задачі відповідають на запитання: що буде, якщо в заданих умовах буде прийняте рішення   ЗОКРЕМА, чому буде дорівнює, при даному рішенні х, обраний показник ефективності L(х).

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

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

Для рішення зворотних задач для багатьох економічних задач використовуються методи математичного програмування. Вони дозволяють відшукати значення змінних, що забезпечують екстремум показника ефективності при наявності обмежень, що накладаються на ці перемінні. Слово програмування в даному випадку є невдалим перекладом слова “program”, що у розглянутому випадку означає “планування”.

У загальному виді задача математичного програмування може бути записана в такий спосіб:

знайти максимум або мінімум функції багатьох перемінних

 (1.1 )

при обмеженнях

 (1.2 )

 (1.3.)

Функція L(х₁, х₂, ... , хn) називається цільовою функцією, вона характеризує ефективність досліджуваної моделі. Обмеження (1.2) і (1.3) визначають область припустимих значень вектора невідомий змінних

х=/ х₁, х₂, ... , хn/.

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

 

 

 

 

Мал. 1.1

До задач лінійного програмування відносяться ті, у яких цільова функція f(x) лінійно залежить від невідомих х₁, х₂, ... , хn, а обмеження, що накладаються на ці невідомі мають вид лінійних рівностей або нерівностей. У лінійному програмуванні існують класи задач, структура яких дозволяє розробити для їхнього рішення більш прості спеціальні методи. Так у лінійному програмуванні з'явилися поділи транспортних задач і задач про призначення.

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

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

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

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

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