Цілочисельне програмування

Курсу

“Комбінаторні методи та алгоритми”

Класифікація оптимізаційних задач

 

 

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

NP – функції які не належать до поліномів. Експоненційні функції: ; ; ;

Це задачі, які можуть бути розв’язані за поліноміальний час, але на не детермінованій машині Тюрінга. Не детермінована – наступний крок не відомий.

NPC – задачі до яких можна звести будь-яку задачу NP.

 

 

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

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

Лінійне програмування (лінійна оптимізація)

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

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

Нелінійне програмування (нелінійна оптимізація)

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

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

За умов обмежень:

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

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

Методи:

¾ Метод по координатного спуску

¾ Метод градієнтного спуску

¾ Метод штрафної функції

Цілочисельне програмування

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

Найпростіший метод розв'язання задачі цілочисельного програмування - зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність.

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

1. Задача оптимального розкрою матеріалів.

2. Задача про призначення.

3. Задача про оптимальне використання устаткування.

4. Задача комівояжера.

5. Задача календарного планування.

Для розв'язання ЗЦЛП можуть застосовуватися такі основні групи методів:

1. Методи перерізу (методи відтинаючих площин).

2. Комбінаторні методи.

3. Графічний.

4. Еврістичні.

Булеве програмування

До окремого випадку завдання цілочисельного лінійного програмування відносяться завдання, де змінні X можуть приймати лише два значення - 0 і 1. Відповідні завдання часто називають задачами Булевського програмування.

 

Стохастичні задачі

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

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

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

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

,

,

.

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

,

,

, ,

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

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

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

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

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

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

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

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

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

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

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

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

Комбінаторної оптимізації

Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної. Область теорії оптимізації в прикладної математики, пов'язана з дослідженням операцій, теорією алгоритмів і теорією обчислювальної складності. У комбінаторної оптимізації використовуються як математичні підходи, так і методи штучного інтелекту. Алгоритми комбінаторної оптимізації, одним з найбільш популярних серед них є метод гілок і меж, застосовуються при вирішенні NP-важких завдань, дозволяючи зменшувати простір допустимих рішень за допомогою ефективної процедури пошуку.

Приклади:

В задачі комівояжера задане ціле та відстані між всіма парами міст у вигляді матриці , де . Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.^[1]

Можна взяти F ={всі перестановки з об'єктів}. Кожна перестановка є обходом, якщо інтерпретувати як місто, відвідуване після міста , . Тоді вартість відображає в