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

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

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

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

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

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

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

Особливості

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

Розв’язування задачі динамічного програмування полягає в знаходженні такого управління   процесом у цілому, яке максимізує загальну ефективність:   (max  ).

Оптимальним розв’язком цієї задачі є управління   що складається з сукупності оптимальних покрокових управлінь:

і уможливлює досягнення максимальної ефективності:

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

Цей факт є основою методу динамічного програмування і є сутністю так званого принципу оптимальності Р. Белмана, який формулюється так:

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

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

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

, , .

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

,

,

,  ,

де Ω — простір подій ω.

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

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

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

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

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

• Детермінованим чи випадковим є вектор Х. Якщо вектор Х є детермінованим, то він не залежить від випадкових параметрів моделі. Якщо ж він випадковий, то тоді Х є функцією від ω —  , тобто залежить від випадкових змінних.

• Як розуміти максимізацію (мінімізацію) цільової функції — як абсолютну (для всіх значень  ) чи як максимізацію її математичного сподівання або деякої іншої ймовірнісної характеристики цієї функції (моди, медіани), або як мінімізацію середнього квадратичного відхилення? Наприклад, що краще мати: платню 500 ± 200 чи 450 ± 50? У першому разі платня може змінюватися в межах від 300 до 700 гривень, а у другому — лише від 400 до 500.

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

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

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

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