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

(1.2)

За типом змінних розрізняють задачі МП з неперервними та дискретними змінними. Останні створюють окремий клас задач дискретного програмування, підкласом якого є задачі цілочисельного програмування.

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

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

Коротка класифікація моделей математичного програмування представлена на рис. 1.1.

Рис. 1.1. Класифікація моделей математичного програмування.

4. Задача лінійного програмування як задача розподілу обмежених ресурсів.

Зауважимо, що задача ЛП у багатьох випадках виявляється асоційованою із задачею розподільчого типу, яка спрямована на пошук найбільш вигідного способу розподілу обмежених ресурсів за декількома видами виробничої діяльності. У сформульованій вище задачі (1.2) представлено п видів виробничої діяльності, інтенсивності використання котрих (шукані величини) скаладають x1, x2, … xn . Для здійснення усіх видів виробничої діяльності є в наявності т видів ресурсів, можливі обсяги споживання яких обмежені значеннями b1, b2, …, bm. Витрати і-го ресурсу на одиницю продукції j-го виду виробництва дорівнюють aij. Тому сума , яка являє собою загальний обсяг і-го ресурсу, що використовується n видами виробництва, не може перевищувати величини bi.Структура цільової функції z відбиває внесок кожного виду виробничої діяльності в загальний результат, У випадку максимізації величинаCj являє собою прибуток від j-го виду виробничої діяльності на одиницю відповідної продукції, а у випадку мінімізації Cj характеризує питомі витрати. Зауважимо, що «корисність» деякого виду виробничої діяльности не можна встановити тільки за значенням відповідного коефіцієнта цільової функції, оскільки обсяг споживання обмежених ресурсів також є важливим чинником. Оскільки усі види виробничої діяльності, подані в моделі, претендують на використання обмежених ресурсів, відносна корисність деякого виду виробництва (у порівнянні з іншими видами виробничої діяльності) залежить як від величини коефіцієнта цільової функції сj, так і від інтенсивності споживання ресурсів aij. Тому можлива ситуація, коли через занадто великі витрати обмежених ресурсів деякий j-й вид виробничої діяльності, що характеризується високим прибутком, використовувати недоцільно (тобто в оптимальному розв'язку відповідна змінна виявиться небазисною).

5. Побудова моделі задачі лінійного програмування.

Приклад 1.1. Для виробництва фарб двох видів підприємство використовує два види сировини: А та Б. Норми витрат та максимальні добові витрати сировини кожного виду, а також питомий прибуток від продажу 1т фарби кожного виду наведені в табл. 1.1.

Таблиця 1.1

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

Для прикладу, що розглядається, математична модель матиме наступну структуру:

Змінні: x1, x2 - добовий обсяг виробництва фарби, відповідно першого та другого видів, у тоннах.

Цільова функція: Позначивши загальний прибуток через Z, можна подати цільову функцію у вигляді такої формули:

Z= З x 1+2 x 2 ® max