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

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

Керуюча система створює х={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)

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