Оптимізаційні задачі. Моделі та методи лінійного та нелінійного програмування (графічний метод, симплекс-метод, метод множників Лагранжа)

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

Означення.Оптимізаційна модель – це математична модель виду , де - деяка функція (вона називається "цільова функція"), а - система обмежень. Дуже часто ставиться вимога знайти найбільше або найменше значення , враховуючи .

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

Лінійні оптимізаційні моделі:

Цільова функція: z = c₁x₁ + c₂x₂ +…+ c_nx_n → max (min)

Умови (обмеження):

x_i ≥ 0, i = (1,n)

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

1.Графічний (при розв’язку задачі використовується малювання);

2.Симплекс-метод (при розв’язку задачі будується багатовимірна фігура-симплекс, по ребрам якого ми і "ходимо")

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

1.Графічний (при розв’язку задачі використовується малювання);

2.Метод множників Лагранжа. Суть методу:

a.Початкові дані: цільова функція , система обмежень

b.Складається вираз

c.Обчислюються часткові похідні по всіх та по всіх від виразу ;

d.Ці похідні прирівнюються до нуля. Отриманий набір розв’язків містить всі екстремуми функції .

Задачі лінійної оптимізації: Оптимальне планування виробництва, Оптимальне використання ресурсів, Транспортні задачі, Задачі оптимального управління вир. Процесом (задача про призначення на роботу; оптимального планування штатного розкладу; Оптимальне управління обіговим капіталом).

Нелінійні оптимізаційні моделі

Z= f(x₁, x₂, …, x_n) → max (min)

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

z = c₁x₁ + c₂x₂ → max (min)

Умови (обмеження):

Будуємо , його початок знаходиться в початку координат. Будуємо лінію рівня і рухаючи її вздовж вектора приходимо до висновку: 1. Точка або множина точок яких пряма залишає множину обмежень (G) і будуть тими точками, де функція набуває максимального значення. 2. Рухаючи пряму в протилежному напрямку до аналогічно отримаємо мн-ни точок, де пряма набуває свого мінімального значення.

Метод множників Лагранжа

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

Суть методу: точка з координатами (х₁^*, х₂^* ,…, х_n^*) є точкою умовного екстремуму функції z= f(х₁, х₂ , …, х_n) тоді і тільки тоді, коли вона є точкою екстремуму ф-ї Лагранжа, яка має такий вигляд:

Метод розв’язання:

1. Якщо система обмежень поч. задачі містить нерівності, то можна додати до лівих частин нерівності штучні змінні.

2. Скласти функцію Лагранжа.

3. Знайти стаціонарні точки з системи рівнянь:

4. Визначити тип стаціонарних точок за допомогою достатньої умови екстремуму.

Z=f(x₁,x₂), (x₁^*,x₂^*) – стаціонарні точки

1) >0 – т. екстремуму. А>0 – мінімум, А<0 – максимум, А=0 – то «дивимося по С», С>0 – мінімум, С<0 – максимум. 2) <0 – не т. екстремуму. 3) =0 – не має відповіді.

1) >0 – т. екстремуму. >0 – мінімум, <0 – максимум. 2) <0 – не т. екстремуму. 3) =0 – не має відповіді.