Задачі лінійного програмування

Для економічних систем характерною є наявність керуючої та керованої системи.

Керуюча система створює х={x₁,x₂…x_m}.

U={u₁,u₂…u_k}- описує стан системи.

Як керована так і керуюча система повинні враховувати L={L₁,L₂…L_m} – обмежень, що накладаються на процес.

Y={y­₁,y₂…y_р} – компонент зовнішнього середовища, що не залежить ні від керуючої, ні від керованої системи.

Узагальненням Y є ЦФ.

Цільова функція, яка є мірою ефективності роботи системи і залежить від х керування. Цільову функцію позначають F(x), у цю функцію входять і постійні величини, що залежать від L,Y,U.

Мета керування: задовольнивши задані обмеження досягнути екстремуму цільової функції.

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

Математичне програмування є складовою частиною «ДО».

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

Функція мінімуму чи максимуму якої якої шукаємо називається цільовою.

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

1. Потрібно знайти екстремальне значення Цільової функції F(x)=F(x1,x2…xm)->min(max) (1)

X={x1,x2…xn}- має задовольняти систему співвідношень.

 

 

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

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

- Нелінійне;

- Динамічне(процес розв`язку є багатоетапним)

Нелінійне програмування поділяється на:

- Опукле (знаходження екстремуму опуклої цільової функції на опуклому просторі

- Дробово-лінійне(ЦФ є відношенням двох лінійних функцій)

- Квадратичне(ЦФ є квадратична)

- Параметричне(залежність від параметрів)

- Цілочислове

- Стохастичне

ЦФ та обмеження є випадковими величинами.

Методи МП застосовують до розв’язання наступних задач:

1) Управління ресурсами для виробництва;

2) Про розподіл ресурсів;

3) Про суміші;

4) Ремонту і заміни устаткування;

5) Упорядкування;

6) Синтез мережі транспортних сполучень;

7) Найвигіднішого розташування продуктів;

Означення: Х що задовольняє умови (2) і (3) називається допустимим розв’язком або планом задачі.

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

Означення: множина наборів х₁,х₂,…х­_к, що задовольняють умови (2),(3) називаються областю визначення задачі або допустимою областю.

Означення: план задачі х*={x₁*,x₂*…x_n*} – при якому ЦФ досягає екстремуму називається оптимальним планом або розв’язком задачі.

Якщо обмеження та ЦФ містять х_i в І степені то задача (1)-(3) назив. Задачею лінійного програмування.

Необхідно знайти екстремум ЦФ F(x)=cx₁+c₂x₂+…+c_nx_n->min(max) (4)

який задовольняє систему обмежень

 

Існує три форми запису ЗЛП:

- Загальна (необхідно знайти максимальне або мінімальне значення функції за обмежень рівнянь та нерівностей F(x)->min(max)

 

 

При чому умова невід`ємності може накладатися на всі змінні, на деякі з них або не накладатися взагалі.

- Стандартна

 

 

- Канонічна

 

 

Задача знаходження min ЦФ F(x) еквівалента задачі знаходження max ЦФ –F(x)->max (7)