няють рівняння F (x) = Const. Лінія рівня і вектор градієнт в кожній точці взаємно перпендикулярні. br/>
Постановка ЗЛП, різні форми запису. Приклади економічних задач
Лінійне програмування - розділ математичного програмування, який розглядає задачі оптимізації лінійних функцій багатьох змінних при лінійних обмеженнях на область зміни змінних.
Особливістю ЗЛП є те, що лінійна цільова функція не має екстремуму і досягає найбільшого або найменшого значення на кордоні допустимої області.
Розглянемо постановку ЗЛП на прикладі завдання і найкращому використанні ресурсів. Мається m видів ресурсів в обмеженій кількості b = (b 1 , b 2 , ..., b m ). Ресурси використовуються підприємством для випуску n видів продукції. Відома економічна вигода виробництва кожного виду продукції, що обчислюється, наприклад, ціною реалізації С = (С 1 , С < span align = "justify"> 2 , ..., С n ) . Відомі технологічні коефіцієнти а ij , які відповідають кількості i-го виду ресурсу, необхідної для виробництва одиниці j-го виду продукції - А = (а ij ). Необхідно скласти план виробництва х = (х 1 , х 2 , ..., х n ), що приносить підприємству максимальний прибуток.
У загальному вигляді математичну модель задачі (ЗЛП) можна записати таким чином:
F (x) = C 1 x 1 + C 2 x 2 + ... + C n x n ? max
a11x1 + a12x2 + ... + a1nxn? b1, xj? 0, j = 21x1 + a22x2 + ... + a2nxn? b2,
............ m1x1 + am2x2 + ... + amnxn? bm.
Розглянемо завдання про дієту. Необхідно скласти дієту (раціон), що містить певні поживні речовини. Маємо n видів продуктів, кожен з яких сожержіт необхідні m видів поживних речовин. Одиниця j-го продукту містить аij одиниць i-го поживної речовини. Для нормальної життєдіяльності необхідно не менше bi одиниць i-го речовини. Відома вартість одиниці кожного виду продукту С = (С1, С2, ..., Сn). Необхідно скласти дієту мінімальної вартості. p> Математична модель задачі прийме вигляд:
F (x) = C1x1 + C2x2 + ... + Cnxn? min 11x1 + a12x2 + ... + a1nxn? b1, xj? 0, j = 21x1 + a22x2 + ... + a2nxn? b2,
............ m1x1 + am2x2 + ... + amnxn? bm.
Тут хj - кількість j - го продукту в раціоні.
У матричної формі загальна ЗЛП виглядає так:
F (x) = C T x? max (min)? (=,?) B; x? 0.
Крім того, для запису ЗЛП можна використовувати знак суми:
F (x) =? max (min)
,.
Розглянемо завдання про розміщення замовлення. Мається m однорідних груп устаткування, на якому потрібно виконати замовлення на випуск n видів продукції в обсягах х * j,. Потужність обладнання обмежена, наприклад, часом Тi. Продуктивність обладнання задана коефіцієнтами аij. Відомі коефіцієнти витрат Сij - витрати i - го обладнання на виробництво j - го продукту. Побудувати план хij розміщення замовлення (завантаження обладнання). Складемо математичну модель задачі. br/>
F (x) =? min, xij? 0, j =,,
за потужністю -,,
за видами продукції, план за якою може бути перевиконано
, j =,
за видами продукції, план по якій повинен відповідати замовленням
, j =,
за видами продукції, замовлення на яку приймається для більш повного завантаження
обладнання
, j =.
4. Графічний метод розв'язання ЗЛП. Основні властивості ЗЛП
Графічний метод розв'язання ЗЛП використовується, якщо число невідомих завдання не більш як 2 або якщо різниця між числом невідомих і обмежень задачі, записаних у вигляді рівнянь не більше двох.
Схема рішенн...
