Розділ І. Моделі та методи лінійного, дискретного та динамічного програмування

Вступ

 

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

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

Методом дослідження операцій є моделювання.

Моделювання – один із загально-наукових методів дослідження, що застосовується для аналізу та синтезу систем. Це спосіб дослідження, коли замість реального об’єкту вивчається його умовний образ – модель.

Модель – це умовний образ об’єкту чи процесу, який вивчається, та відображає його основні характеристики і використовується в ході дослідження.

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

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

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

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

Класифікацію самих економіко-математичних моделей можна робити за різними ознаками, основними з яких є:

1) за цільовим призначенням – теоретико-аналітичні та прикладні моделі;

2) за ступінню агрегованості об’єктів – макроекономічні (функціонування економіки як єдиного цілого) та мікроекономічні (підприємства, фірми) моделі;

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

4) за характером інформації – детерміновані (на базі фіксованих значень вхідних даних) та стохастичні (вхідні дані є випадковими величинами) моделі;

5) за характеристикою математичного апарату – лінійного та нелінійного програмування, дискретного та стохастичного програмування, кореляційно-регресійні моделі, моделі теорії масового обслуговування, моделі сітьового планування та управління тощо;

6) за підходом до вивчення системи – дескриптивні та нормативні моделі.

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

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

- методів конструювання оптимізаційних моделей;

- методів розв’язування оптимізаційних задач;

- методів якісного, економіко-математичного аналізу;

- методів інформаційного забезпечення.

Таким чином, теорія дослідження операцій охоплює всі етапи дослідження систем:

- ідентифікація проблеми (формування проблеми, мети її розв’язання, виявлення умов та обмежень);

- побудова оптимізаційної моделі (встановлення математичних співвідношень між метою розв’язання проблеми та існуючими обмежуючими факторами);

- інформаційне наповнення моделі;

- знаходження розв’язку сформульованої задачі;

- аналіз моделі на чутливість щодо змін вхідних параметрів системи;

- перевірка адекватності моделі (модель можна вважати адекватною, якщо рішення, яке отримали на її основі, здатне достатньо надійно передбачити поведінку системи);

- реалізація отриманих та відповідним чином перевірених рішень для аналізу, планування або управління системою.

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

Задачі та методи дослідження розбиваються на окремі класи в залежності від типу операцій та процесу, для аналізу яких вони використовуються. Тому курс „Дослідження операцій” складається з наступних розділів: математичне програмування, імітаційне моделювання, теорія ігор, теорія управління запасами, сітьове планування та теорія масового обслуговування.

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

(1)

за умов

, (2)

Функція називається цільовою функцією і є критерієм якості управлінського рішення .

Умови задачі (2) називаються обмеженнями задачі і утворюють множину допустимих альтернативних управлінських рішень.

Оптимізаційні задачі дослідження операцій розв’язуються методами математичного програмування.

Математичне програмування – це розділ математики, який розробляє теорію та методи розв’язування екстремальних задач типу (1), (2).

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

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

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

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

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

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

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

Таким чином, математичне програмування, як теорія методів розв’язування екстремальних задач виду (1) – (2), в залежності від типу задач поділяється на наступні підрозділи:

- лінійне програмування;

- нелінійне програмування;

- дискретне програмування;

- динамічне програмування;

- стохастичне програмування.

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

Процедура побудови математичних моделей є загальною для всіх задач математичного програмування і складається з таких кроків:

- ідентифікація керованих змінних;

- запис цільової функції через змінні задачі;

- запис обмежень через змінні задачі.

Розглянемо приклади побудови задач математичного програмування.

Приклад. Завод виробляє мінеральну воду у пляшках по півлітра, одному, півтора та два літри. Виробництво обмежено запасом мінеральної води на заводі – 10 т, а також виробничими потужностями обладнання, яке дозволяє щодня випускати не більше 5 тис. пляшок. Прибуток від реалізації кожної півлітрової пляшки мінеральної води складає 20 коп., однолітрової – 18 коп., півторалітрової – 16 коп. та дволітрової – 15 коп. Скільки пляшок мінеральної води має щодня виробляти завод з точки зору максимізації прибутку.

Визначимо змінні задачі. В результаті розв’язання задачі повинно бути прийняте рішення щодо виробництва кожного виду пляшок. Тоді змінні задачі – кількість пляшок певного виду: - кількість півлітрових пляшок, - кількість однолітрових, - півторалітрових, - дволітрових.

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

0,2 + 0,18 + 0,16 + 0,15

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

0,5 + + 1,5 + 2 .

Максимальна кількість розлитої у пляшки мінеральної води не повинна перевищувати 10 т, тому перше обмеження задачі має вигляд:

0,5 + + 1,5 + 2 10000.

Другою умовою – є виробничі потужності обладнання, які не дозволяють щодня випускати більше 5 тис. пляшок. Тому друге обмеження задачі –

5000.

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

Таким чином математична модель має наступний вигляд:

0,2 + 0,18 + 0,16 + 0,15 max,

0,5 + + 1,5 + 2 10000,

5000,

0,

- цілі.

Приклад. Інвестиційна компанія розглядає можливість інвестицій в акції трьох підприємств з метою отримання прибутку не менше 500 тис. грн. при мінімальних витратах. Акції першого підприємства дозволять отримати 20% прибутку від вартості, другого – 22%, а третього – 25%. Вартість однієї акції кожного підприємства відповідно дорівнює: 1тис. грн., 1,5 тис. грн. та 1,4 тис. грн. Кількість кожного виду акцій обмежена відповідно: 10 тис.шт., 20 тис. шт. та 8 тис. шт.

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

Введемо змінні ( 1, 2, 3), які означають кількість акцій відповідно першого, другого та третього підприємства. Критерієм якості інвестицій будуть найменші витрати. Тоді цільова функція задачі -

1000 +1500 +1400 min

за умов забезпечення необхідного рівня прибутку

0,2 1000 +0,22 1500 +0,25 1400 500000,

врахування обмежень на кількість акцій

10000, 20000, 8000

і невід’ємності та цілочисельності змінних

0,

- цілі.

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

Приклад. Менеджер з цінних паперів вирішив розмістити 100 тис. грн. таким чином, щоб отримати максимальний річний прибуток. Його вибір обмежений трьома видами вкладів: в облігації внутрішньої державної позики (ОВДП), в акції фабрики та в екологічний проект. Доходність кожного виду вкладів описується залежностями , та , де ( 1, 2, 3) відповідно кількість гривень вкладу в ОВДП, в акції та в екологічний проект. Залишок грошей може залишатися на банківському рахунку під 20% річних.

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

Побудуємо модель оптимального розподілу вкладів. Змінні моделі ( 1, 2, 3) будуть означати розмір вкладу, змінна - кількість грошей, які залишаться на банківському рахунку.

Цільова функція задачі – величина прибутку, яку треба максимізувати:

+ + +0,2 max

за умов загальної вартості всіх вкладів

=100000,

вимог щодо величини ризикових вкладів

0,75 100000,

а також, враховуючи зміст змінних, їх невід’ємності

0.

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

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

Приклад. Агрофірма займається вирощуванням капусти, помідорів, огірків та моркви. Посівна площа обмежена га. Урожайність овочів, як відомо, підпадає під вплив погодних умов, тому точне значення передбачити неможливо і слід розглядати як випадкові величини. Маркетингові дослідження свідчать, що попит на овочі має певні пропорції: % - капуста, % - помідори та по % - огірки та морква. ( + + 2 =100). Побудувати модель оптимального розподілу площ під овочеві культури з точки зору максимізації кількості комплектів продукції.

Розмір площі, яка виділяється під певний вид овочів, позначимо за змінні задачі ( 1, 2, 3). Залежність урожайності кожної культури від погодних умов позначимо ( 1, 2, 3), де - стан погоди.

Тоді кількість комплектів овочів визначається як

,

де – математичне сподівання.

Цільова функція моделі розподілу площ – максимальна кількість комплектів овочів.

,

обмеження: по загальній площі агрофірми

та по знаку змінних

.

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

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

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

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

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

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

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

Підручник складається з шести частин – „Математичне програмування”, „Імітаційне моделювання”, „Теорія ігор”, „Теорія управління запасами”, „Сітьове планування та управління” та „Теорія масового обслуговування”, в кожній з яких викладаються теоретичні основи розв’язування відповідного типу задач, розглядаються приклади їх застосування, даються завдання для самостійної роботи та контрольні запитання.

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

Підручник містить термінологічний словник.

 

Таблиця 1.1.

Вид сировини	Запас сировини	Витрати сировини для виробництва одиниці продукції
	300 () 450 () 260 ()	10 () 8 () 6 ()	7 () 14 () 13 ()
Прибуток	35 гр.	50 гр.

 

Математична модель цієї задачі має такий вигляд

Приклад 1.5.

 

Рис. 1.2.

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

Приклад 1.6.

У цьому прикладі допустима область така ж сама, що і у прикладі 1.4, а цільові функції різні.

 

Рис. 1. 3.

Аналізуючи рис.1.3, приходимо до висновку, що максимальне значення цільової функції дорівнює 9, а оптимальний розв’язок — будь-яка точка сторони чотирикутника .

Множину точок, які належать до відрізку можна описати як точки, які лежать на прямій за умови , де числа та - координати по осі точок відповідно та . Або межі по змінній можна замінити на межі по змінній : , де та - координати по осі точок відповідно та . Множину точок, які належать відрізку можна також описати так: , де . Тоді .

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

ЗЛП на максимум (мінімум) тоді і тільки тоді має оптимальний розв’язок, коли її цільова функція обмежена зверху (знизу) у допустимій множині.

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

Ще одна істотна властивість ЗЛП полягає в тому, що розв’язок задачі, коли він існує, досягається, як правило, на межі допустимої множини. Більш того, якщо допустима множина ЗЛП має вершини, то принаймні одна з них відповідає оптимальному плану. Строге доведення цих властивостей подамо у наступному пункті.

 

Доведення.

Нехай і — опуклі множини і . Тоді і . З означення опуклої множини і . Отже , а це і означає, що — опукла множина.

Теорема 1.3.1. Допустима множина ЗЛП опукла (якщо вона непорожня).

Доведення.

Оскільки допустима множина ЗЛП є перетин множин точок, які задовольняють окремим обмеженням, то згідно з лемою 1.3.1, достатньо довести, що множина точок, які задовольняють окремому обмеженню, опукла.

Окремим обмеженням ЗЛП може бути або гіперплощина, або півпростір.

Нехай — довільні точки такі що і .

Тоді для будь-якої точки ,

,

тобто належить гіперплощині.

Аналогічно для півпростору. Нехай і ,

. Тоді і

,

тобто і . Теорему доведено.

Теорема 1.3.2. Множина оптимальних точок допустимої множини ЗЛП опукла (якщо вона непорожня).

Доведення.

Якщо оптимальна точка єдина, то теорема вірна в силу нашої умови вважати опуклою множину, що складається з однієї точки.

Нехай оптимальних точок більше ніж одна. Візьмемо дві з них, і .

Нехай і — оптимальне значення цільової функції.

Розглянемо будь-яку точку : . Очевидно, що .

Тоді

.

Отже, — також оптимальна точка. Цим і доводиться опуклість множини оптимальних точок ЗЛП.

З теореми 1.3.2 випливає, що множина оптимальних точок не може бути скінченною, якщо оптимальна точка не єдина.

Теорема 1.3.3. Якщо цільова функція ЗЛП на максимум (мінімум) обмежена зверху (знизу) на допустимій множині, то ця задача має оптимальний розв’язок.

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

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

Тобто — вершина многогранника , якщо не існує точок таких що , і , де .

Лема 1.3.2. Будь-яка точка опуклого обмеженого многогранника є опуклою лінійною комбінацією його вершин.

Тобто, якщо — вершини многогранника , то будь-яку точку можна подати у вигляді:

.

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

Доведення.

Нехай — вершини допустимого многогранника і нехай задача максимізації за умови розв’язувана.

Припустимо, що . Тоді

.

(1.3.1)

 

Нехай не є вершиною , то в силу леми 1.3.2

.

Далі

,

де .

З (1.3.1) випливає, що , а це і означає, що існує вершина , у якій цільова функція набуває найбільшого значення.

Теорему доведено.

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

Тому на початку 50-х років було винайдено американським математиком Дж.Данцигом досить раціональний спосіб перебору вершин: симплекс-метод або метод послідовного поліпшення плану для розв’язування задач лінійного програмування [14].

Нехай розглядається задача з непорожньою допустимою множиною. Загальна ідея симплекс-методу:

1) тим чи іншим способом знаходиться одна з вершин допустимої області і по певному правилу перевіряється, чи є вона оптимальною точкою; якщо вона оптимальна — задача розв’язана; якщо ні, то

2) по певному правилу перевіряється, чи не можна стверджувати, що задача не має оптимальних розв’язків (цільова функція необмежена зверху або, відповідно, знизу на допустимій множині); якщо стверджувати це можна, то задача нерозв’язувана; якщо не можна, то

3) по певному правилу шукаємо нову, ліпшу з точки зору значення цільової функції вершину і повертаємося на 1-й крок.

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

Симплекс-метод

Доведення.

Необхідність. Нехай — базисний розв’язок задачі (1.4.1). Припустимо, що перші координат більші нуля, тобто .

Тоді і — лінійно незалежні вектори.

Доведемо необхідність від супротивного, а саме, припустимо, що не є вершиною . Тоді існують точки і такі що і .

Але тоді

, і

.

(1.4.2)

З (1.4.2) отримаємо

.

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

Достатність. Нехай — вершина допустимого многогранника . Покажемо, що — базисний розв’язок. Якщо , то — базисний розв’язок. Нехай тепер і .

Нам треба довести, що — лінійно незалежні. Припустимо, що ці вектори лінійно залежні, тобто існують , не всі нульові і такі що

.

(1.4.3)

За умовою — допустимий розв’язок, тоді