Економіко-математичне моделювання

Размещено на http://www.allbest.ru/

1. Економіка як об'єкт математичного моделювання. Особливості та принципи математичного моделювання економіки. Класифікація економіко-математичних моделей

Математичні методи і моделі в аналізі, плануванні, прогнозуванні й управлінні економічними об'єктами та процесами отримали назву економіко-математичні методи ЕММ - це поєднання економіки, математики і кібернетики. Практичним завданням економіко-математичного моделювання є: по-перше, аналіз економічних об'єктів і процесів; який дає поглиблене вивчення об'єкту дослідження і також спрямоване на отримання нових знань про цей об'єкт. по-друге, передбачення розвитку економічних процесів та прогнозування наслідків від тих чи інших заходів (прогнозувати доходи та видатки, науково обґрунтувати необхідні зміни у фіскальній політиці);по-третє, вироблення управлінських рішень на всіх рівнях господарської ієрархії управління.Принципи:1. Модель має адекватно описувати реальні економ процеси.2. У моделі потрібно враховувати все істотне, суттєве в досліджуванному явищі, не зважаючи на другорядне, неістотне у ньому. З одного боку модель повинна бути достатньо точною, з іншого - по можливості простою. 3. Модель має бути зрозумілою для користувача, зручною для реалізації на ЕОМ. В якості загальних принципів економіко-математичного моделювання доцільно прийняти такі принципи: системності, інтегрованості, невизначеності, головних видів діяльності, достатності, інваріантності, наступності та ефективності.

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

Відповідно до загальної класифікації математичних моделей вони поділяються на функціональні та структурні. За способами відображення чинника часу економіко-математичні моделі поділяються на статичні й динамічні. Класифікація видів математичний моделей може проводитися й за такими ознаками: аналітичне та комп'ютерне моделювання. Існують різні форми зображення математичної моделі -- інваріантна, алгоритмічна, аналітична, схемна.Інваріантна форма -- зображення математичної моделі безвідносно до методів, за допомогою яких може розв'язуватись поставлена задача моделювання.Алгоритмічна форма -- зображення математичної моделі у вигляді послідовності дій. (Симплекс-метод).Аналітична форма -- зображення математичної моделі у вигляді формул та співвідношень між математичними виразами.Схемна форма -- зображення математичної моделі у вигляді графів, таблиць, діаграм.

2. Особливості та принципи математичного моделювання економіки. Етапи побудови економіко-математичних моделей

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

Процес моделювання включає три елементи, що утворюють систему:

* суб'єкт дослідження (системний аналітик);* об'єкт дослідження;

* модель, яка опосередковує відносини між об'єктом, який

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

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

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

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

3. Загальна постановка оптимізаційної задачі, її структура. Цільова функція задачі ЛП. Система лінійних обмежень та її геометрична інтерпретація

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

K1, k2,k3 - знаки нерівності

A,b,c - заздалегіть задані і фіксовані числа, некеровані змінні

Х1,х2,х3 - керовані змінні

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

. (2.4)

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

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

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

1. Модель має адекватно описувати реальні технологічні та економічні процеси.

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

3. Модель має бути зрозумілою для користувача, зручною для реалізації на ЕОМ.

Будь-який набір змінних x₁, x₂, ..., x_n, що задовольняє умови, називають допустимим планом, або планом. Очевидно, що кожний допустимий план є відповідною стратегією економічної системи, програмою дій. Кожному допустимому плану відповідає певне значення цільової функції.

Сукупність усіх розв'язків системи обмежень, тобто множина всіх допустимих планів утворює область існування планів.

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

4. Приклади задач математичного моделювання в економіці. Класифікація задач і методів математичного програмування

1. Задача оптимального планування виробництва. Визначити план виробництва х=(х1,…,хn)`(xj - шукана кількість одиниць продукції Pj), який би при заданих умовах виробництва максимізував сумарну вартість виготовл. продукції.

2. Задача про дієту. Це класична задача планування найбільш економічного(дешевшого) раціону, який відповідає всім медичним вимогам. Така задача виникає там, де потрібно нагодувати велику кількість людей, напр. в армії, санаторіях… х=(х1,…,хn)`- шуканий раціон (xj - шукана кількість продукту Pj),

3. Транспортна задача. Розглядає процес виробництва та споживання однорідної продукції. Записується у вигляді матриці С - вартості перевезень однієї одиниці продукції з пункту Vi до пункту Sj, та матриці Х - кількості одиниць, що перевозяться з пункту Vi до пункту Sj. Т-задача полягає в тому, щоб знайти такий план Х перевезень продукції, при якому: вся продукція буде перевезенна з пункту Vi, всі пункти споживання Sj будуть забезпеченні продукцією, сумарна вартість перевезень буде мінімальною.

4. Задача максимізації рентабельності виробництва. Знайти план виробництва продукції, який би забезпечив максимальну рентабельність, якщо відомо di- затрати виробничих фондів, необхідних для виготовлення однієї одиниці продукції Pi, ci - вартість одиниці продукції, aij - норми витрат ресурсів, bj - об'єм ресурсів. матем модель має вигляд дробово лінійної задачі.

5. задача максимізації функції корисності споживача.

Задача на знаходження таких значень х1,х2,…хn,(деякі блага), що дають максимум функції Z=x1*x2*…*xn при обмеженнях:

, де I-дохід споживача; p1,p2,pn-ціна цих благ.

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

Методи математичного програмування:

Графічний метод

Симплексний метод

Штучний базис

5. Система лінійних обмежень та її геометрична інтерпретація. Допустимий та оптимальний розвязки задачі ЛП, властивості розв'язків

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

. (2.4)

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою a_i1x₁ + a_i2x₂ = b_i (i=1,2, ..., т). Умови невід'ємності змінних визначають півплощини з граничними прямими х₁ = 0 та х₂ = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв'язком даної системи Сукупність цих точок (розв'язків) називають багатокутником розв'язків, або областю допустимих планів (розв'язків) задачі лінйного програмування. Це може бути точка (єдиний розв'язок), відрізок, промінь, багатокутник, необмежена багатокутна область.

Будь-який набір змінних x₁, x₂, ..., x_n, що задовольняє умови (2.3)системи і (2.4), називають допустимим планом, або планом.

План, за якого цільова функція набуває екстремального значення, називається оптимальним. Оптимальний план є розв'язком задачі економіко-математичного моделювання (2.2)--(2.4).

6. Алгоритм графічного методу розвязку задач ЛП, що містять дві змінні

1. записуємо цільову функцію та обмеження

2.приводимо систему обмежень до канонічної форми

3.знаходимо рівняння прямої. Будуємо ці прямі в системі координат х1Ох2

4. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

5. Знаходимо багатокутник (область допустими розв'язків) розв'язків задачі лінійного програмування.

6. Будуємо градієнт (вектор із координатами: ), що задає напрям зростання значення цільової функції задачі.

7. Будуємо пряму с₁х₁+с₂х₂=const, перпендикулярну до вектора (лінію рівня) .

8. Рухаючи пряму с₁х₁+с₂х₂=const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набирає екстремального значення.

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

7. Форми запису задач ЛП, їх еквівалентність та способи перетворення

Існують три форми запису математичних моделей задач лінійного програмування:

1. Загальна форма запису:

max (min) Z = c₁x₁ + c₂x₂ +…+ c_nx_n

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

2. Стандартна форма запису або симетрична

Особливості форми запису:

1. На усі невідомі, що є в задачі обов'язково накладається умова невід'ємності.

2. Якщо задача на мінімум, то усі основні обмеження є нерівностями виду "?".

3. Якщо задача на максимум, то усі основні обмеження є нерівностями виду "?".

3. Канонічна форма запису:

Особливості форми запису:

1. Усі основні обмеження є рівняння.

2. На усі невідомі задачі обов'язково накладається умова невід'ємності.

Усі три форми є еквівалентними

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

8. Знаходження опорного розвязку . Симплексні таблиці, симплексні перетворення. Критерії оптимального розвязку задачі ЛП

Опорний розвязок(план) - невідємний базисний розв'язок. Базисні розвязки - це частинний розвязок, який знаходиться якщо надати всім вільним змінним значення нуля і обчислити базисні.

Базисні змінні - це змінні які не повторюються в рівнянні двічі і перед ними стоїть коефіцієнт додатній.

Алгоритм симплексного методу

1) Визначення опорного розвязку

2) Побудова симплексної таблиці -

3) Перевірка опорного плану на оптимальність за допомогою чисел індексного рядка. Якщо умова оптимальності не виконується, то переходять до нового опорного плану з визначенням ключового елементу, поки не отримаємо оптимальний план.

4) Критерієм оптимального розвязку задачі на максимум є відсутність відємних чисел в рядку оцінок, критерієм оптимального розвязку задачі на мінімумм є відсутність додатніх чисел в рядку оцінок.

У стовпці «Базис» записані змінні, що відповідають базисним векторам, а в стовпці «С_баз» - коефіцієнти функціонала відповідних базисних векторів. У стовпці «План» - початковий опорний план , в цьому ж стовпці в результаті обчислень отримують оптимальний план. У стовпцяхРазмещено на http://www.allbest.ru/

записані коефіцієнти розкладу кожного j-го вектора за базисом, які відповідають у першій симплексній таблиці коефіцієнтам при змінних у системі (4.2). У (m+1)-му рядку в стовпці «План» записують значення функціонала для початкового опорного плану, а в інших стовпцях - значення оцінок . Цей рядок симплексної таблиці називають оцінковим.

Для того, щоб задачу можна було розв'язати симплексним методом необхідно:

1. Математичну модель представити у канонічній формі.

2. Знайти опорний розв'язок.

3. Скласти початкову симплексну таблицю.

Для того, щоб знайти опорний розв'язок, необхідно щоб:

1. Вільні члени рівнянь стояли з правої сторони і були невід'ємними.

2. В системі обмежень повинен бути виділений базис.

Базисними називають змінні, які задовольняють наступні умови:

1. Біля базисної змінної стоїть коефіцієнт +1.

2. Базисна змінна міститься тільки в 1 рівнянні.

3. Різні базисні змінні повинні міститись в різних рівняннях.

4. Кількість базисних змінних повинна бути рівна кількості рівнянь, тобто кожне рівняння повинно містити свою змінну.

Усі інші змінні в системі називаються вільними. Якщо вільним змінним надати значення 0 і обчислити чому рівні базисні, то знайдемо базисний розв'язок системи.

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

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

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

Початкова симплексна таблиця

Стовпчик БЗ - записують базисні змінні.

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

Стовпчик х₀ - значення базисних змінних в опорному розв'язку.

Рядок 1 - коефіцієнти цільової функції задачі.

Рядок 2 - записуються коефіцієнти, які стоять при відповідних змінних в системі основних обмежень.

Клітинка 3 - значення цільової функції при даному опорному розв'язку. Необхідно число стовпчика Сб помножити на відповідні числа стовпчика х₀ і добутки додати.

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

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

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

9. Опорний розвязок. Штучний базис, запис цільової функції та розвязок М-задачі лінійного програмування

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

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

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

Очевидно, що в кінцевому розв'язку штучна базисна змінна може дорівнювати 0.

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

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

Якщо задача на пошук мінімуму, то цільові функції біля штучної базисної змінної ставиться коефіцієнт +М, якщо задача на максимум, то записується коефіцієнт -М, де М - дуже велике число.

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

В останній симплексній таблиці існує змінна, яка не є базисною, проте її оцінка рівна 0. Якщо в останній симплексній таблиці змінна, що не є базисною, має нульову оцінку, це означає, що задача має не один розв'язок.

Для того, щоб знайти інший розв'язок, необхідно в базис ввести ту змінну, яка має нульову оцінку.

Між оптимальними розв'язками вихідної задачі і М-задачі існує наступний зв'язок: якщо в оптимальному розв'язку М-задачі усі штучні змінні щ_і рівні нулю, то значення усіх інших координат розв'язку х? дадуть оптимальний розв'язок вихідної задачі. Якщо хоча б одна із змінних щ_і не дорівнює нулю, то вихідна задача немає розв'язку.

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



10. Основна та двоїста задачі як пара взаємоспряжених задач. Правила побудови двоїстої задачі. Знаходження розв'язків однієї задачі по розвязках іншої

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

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

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

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі -- на визначення найменшого значення (min), і навпаки.

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

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

6. Матриця

,

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

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків -- рядками.

11. Правила побудови двоїстої задачі. Основні теореми двоїстості та їх економічний зміст

Правила побудови двоїстих задач

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі - на визначення найменшого значення (min), і навпаки.

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

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

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

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків - рядками.

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

Теорема (друга теорема двоїстості для симетричних задачДля того, щоб плани X^* та Y^* відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої не жорсткості

Економічний зміст другої теореми двоїстості стосовно оптимального плану Х^* прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом Х^*, витрати одного і-го ресурсу строго менші, ніж його загальний обсяг , то відповідна оцінка такого ресурсу (компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».

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

(5.13)

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

12. Актуальність задачі цілочисельного ЛП. Математична постановка цілочисельних задач ЛП. Алгоритм Гоморі

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

Задачу цілочислового програмування записують так : [xі є z, і=1,2,…п]

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

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

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

2. Складається додаткове обмеження для перемінної B [i], яка в оптимальному плані має максимальне дробове значення, хоча повинна бути цілою. Тоді величини коефіцієнтів елементів A [i, j] , B [i] обчислюються так:

де - ціла частина числа A [i, j] . Тоді додаткове обмеження формується таким чином:

Воно буде цілим невід'ємним при цілих невід'ємних в [i, j] і о [j] Після складання обмеження воно вводиться в систему лінійних обмежень і завдання вирішується заново при вихідних обмеженнях і додаткове обмеження. Якщо отримано цілочисельне рішення, задача вирішена. В іншому випадку необхідно повторити другий етап.

13. Задачі цілочисельного ЛП. Геометрична інтерпретація системи обмежень задач цілочислового програмування

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

Загальна цілочислова задача лінійного програмування записується так: за умов: ; ;-- цілі числа .

Скажімо, множина допустимих розв'язків деякої нецілочислової задачі лінійного програмування має вигляд, зображений на рис. 13.1

Геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв'язків відповідної нецілочислової задачі. Отже, для розглянутого на рис. 13.1 випадку множина допустимих планів складається з дев'яти точок (рис. 13.2), які утворені перетинами сім'ї прямих, що паралельні осям Ох₁ та Oх₂ і проходять через точки з цілими координатами 0, 1, 2. Для знаходження цілочислового оптимального розв'язку пряму, що відповідає цільовій функції, пересуваємо у напрямку вектора нормалі до перетину з кутовою точкою утвореної цілочислової сітки. Координати цієї точки і є оптимальним цілочисловим розв'язком задачі. У нашому прикладі оптимальний цілочисловий розв'язок відповідає точці М ().

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

Рис 13.1 Рис 13.2

14. Постановка транспортної задачі і її цільова функція. Види транспортних задач. Математичні моделі відкритих і закритих транспортних задач

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

Постановка транспортної задачі.

Задано певну к-ть постачальників деякого товару (m) токаж вказується скільки одиниць цього товару кожен із постачальників пропонує(Ai, i=1,m)

Задано певну кількість споживачів цього товару (n), а також вказано потреби кожного із них(Bj, j=1,n). Задано вартість перевезень одиниці товару від і-го постачальника до jго споживача(Cij). Необхідно скласти такий план перевезень, який задовольняє такі умови: - потреби споживачів повинні бути максимально забезпеченні; - загальна вартість перевезень повинна бути мінімальною. Розв'язок ТЗ записують у вигляді матриці.

Мат модель ТЗ: економіка математичний модель програмування

Z=

де хij -- кількість продукції, що перевозиться від і-го постачальника до j-го споживача; сij -- вартість перевезення одиниці продукції від і-го постачальника до j-го споживача; аi -- запаси продукції і-го постачальника; bj -- попит на продукцію j-го споживача.

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

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

Математична модель відкритої транспортної задачі має вигляд:

Пропозиція більше за потреб:

? x_ij ? А_і (і= 1,m)

Потреби більше за пропозицію:

? x_ij ? В_j ( j= 1,m)

Математична модель закритої транспортної задачі має вигляд:

Пропозиція більше за потреб:

min z =

Теорема: Будь-яка трансп зад закритого типу має хоча б один розв'язок.

15. Транспортна задача закритого типу. Методи північно-західного кута та найменшого елемента для побудови опорного розв'язку транспортної задачі і умова його невиродженості

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

.

Теорема:Будь-яка задача закритого типу має хоча б один розв'язок.

Методи побудови опорних розв'язків ТЗ:

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

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

Метод найменшої елемента

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

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

16. Метод потенціалів та умова існування оптимального розв'язку транспортної задачі. Побудова циклів пере розрахунку для знаходження нового опорного розв'язку

Методом розв'язку ТЗ є метод потенціалів. для того, щоб можна було застосувати цей метод, необхідне виконання 2х умов: - ТЗ є закритою; - побудовано деякий опорний розв'язок цієї задачі( метод півн-зах кута і метод найм. елемента)

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

· Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу.

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

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

· Перевірка плану транспортної задачі на оптимальність.

· Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить , отже, з цих клітин обов'язково утвориться цикл. У межах даного циклу здійснюють перерахування, які приводять до перерозподілу постачань продукції. Кожній вершині циклу приписують певний знак, причому вільній клітинці -- знак «+», а всім іншим -- за черговістю знаки «-» та «+». У клітинках зі знаком «-» вибирають значення q і переносять його у порожню клітинку. Одночасно це число додають до відповідних чисел, які містяться в клітинках зі знаком «+», та віднімають від чисел, що позначені знаком «-». Якщо значенню q відповідає кілька однакових перевезень, то при відніманні залишаємо у відповідних клітинках нульові величини перевезень у такій кількості, що дає змогу зберегти невиродженість опорного плану.

· Внаслідок наведеного правила вибору q дістаємо новий опорний план, який не містить від'ємних перевезень і задовольняє умови транспортної задачі.

Знайдений опорний розв'язок є оптимальним, якщо серед оцінок пустих клітинок відсутні від'ємні числа.

17. Відкрита транспортна задача, її математична модель. Розвязок відкритої транспортної задачі

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

Математична модель відкритої транспортної задачі має вигляд:

Пропозиція більше за потреб:

? x_ij ? А_і (і= 1,m)

Потреби більше за пропозицію:

? x_ij ? В_j ( j= 1,m)

18. Загальна задача нелінійного програмування. Алгоритм застосування графічного методу розвязку задач НЛП

У загальній постановці задачу нелінійного програмування (НЛП) записують так:

(1)

(max)z(x1, x2, …, xn), (2)

де F1(x), …, Fn(x),z(x), x=(x1, x2, …,xn) - довільні функції. У конкретних задачах частина обмежень (або всі) можуть бути нерівностями. Крім того, на невідомі можуть накладатися умови невід'ємності і т.п.

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

Алгоритм:

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

2.Побудувати гіперповерхню F(x1,x2,…,xn)=h для деякого значення h.

3.Змінюючи значення h, знайти гіперповерхню найвищого(найнижчого) рівня, яка мала хоча б одну спільну точку з областю D. Якщо виявиться, що функція F не обмежена зверху(знизу)на множини D , то відповідна задача на максимум(мінімум) не має розвязку.

4.Для того, щоб знайти оптимальний розв'язок задачі, неодбідно порбудувати лінії рівня цільової функції.

Якщо розвязок задачі існує, то кожна точка X є D, яка належить гіперповерхні найвищого(найнижчого) рівня,є оптимальною, а відповідне значення функції F(X)- є оптимальним.

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

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

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

max(min) z=

Особливості:

1. цільова функція є дробом, чисельник і знаменник якого є лінійними функціями.

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

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

Розв'язування задачі симплексним методом:

1. Візьмемо цільову функцію. Поділимо почленно чисельник на знаменник.

Введемо нові змінні.Завжди вводиться змінна у0, яка дорівнює дробу чисельник якого = 1, а знаменник = знаменнику цільової функції. Усі інші змінні вводяться по принципу у1=х1у0; у2=х2у0;і т.д.

2. Множимо обидві частини основних обмежень на у0

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

Отже матем модель має вигляд:

max(min) z= с0у0+с1у0+с2у0+…+сnуn

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

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



х1=у1/у0; х2= у2/у0 і т.д.

Якщо в кінцевому розв'язку у0=0 то це означає, що задача взагалі не має розв'язку.

20. Економічний зміст, деякі основні типи задач та моделі динамічного програмування. Алгоритм методу динамічного програмування

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

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

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

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

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

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

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

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

Розглянемо зразок розв'язання задачі про комівояжера методом динамічного програмування:

1. Введення даних про пункти і відстані між пунктами i та j d_ij (d_ij =0 при i=j) .2. Обчислення всіх можливих варіантів відстаней, що складаються з трьох дільниць A_0, A_i1, A_i2, A_i3. Вони групуються по останньому пункту і з них залишаються ті варіанти, що об'єднують однакові пункти, але мають найменший шлях.3. До тих варіантів, що залишились додають ще четверту дільницю і повторюють процедуру з пункту 2. Це повторюється для п'ятої, шостої і т. д. дільниць, доки не повертається в пункт А₀. Той варіант (чи варіанти), що залишилися, і визначають найкоротший шлях, по якому комівояжеру можна об'їздити всі місті А_i (i=0,…,n), якщо він почне та закінчить свою подорож в А_0.

21. Поняття про принципи оптимальності Беллмана та його застосування

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

22.Загальна постановка задачі схоластичного програмування, її особливості щодо оперативного управління та перспективного планування. Класифікація

Задача стохастичного програмування:

,

,

, ,

де Щ -- простір подій щ.

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

стохастичні коефіцієнти цільової функції та детерміновані обмеження;

детерміновані коефіцієнти цільової функції та стохастичні вільні члени і коефіцієнти системи обмежень;

стохастичні коефіцієнти цільової функції, вільні члени і коефіцієнти системи обмежень.

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

Задачі стохастичного програмування поділяються на статичні та динамічні.

Для того щоб задача стохастичного програмування мала сенс, необхідно відповісти на три запитання:

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

2. Як розуміти максимізацію цільової функції? Як максиміза-цію абсолютну для усіх COEQ, чи максимізацію її математичного сподівання, чи максимізацію деякої іншої її імовірнісної харак-теристики?

3. Як розуміти виконання обмежень: абсолютно для всіх COEQ, чи у середньому, чи допускати їх порушення з малою ймо-вірністю тощо?

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



23. Методи розв'язання задач схоластичного програрамування (непрямі, прямі), приклади їх реалізації

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

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

24. Основні поняття теорії ігор. Приклади ігрових задач в економіці та менеджменті. Матричні ігри двох осіб. Платжна матриця

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

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