Головна |
Задачам лінійного програмування властиві наступні особливості:
1. Цільова функція є зваженою лінійною сумою від невідомих змінних
xi вигляду:
. (3.7)
де ci - коефіцієнти цільової функції. Таку цільову функцію часто називають лінійною формою.
2. Обмеження, що накладаються на область можливих рішень, мають вид лінійної рівності або нерівності:
. (3.8)
де aij, bi - значення показників цільової функції, причому величини aij, xi, bi позитивні.
Розглянемо приклади вирішення задач лінійного програмування.
Приклад. Фірма виробляє дві моделі А і В збірних книжкових полиць. Їх виробництво обмежено наявністю сировини (високоякісних дощок) і часом машинної обробки. Для кожного виробу моделі А потрібен 3 м2 дощок, а для моделі В - 4 м2. Фірма може одержувати від своїх постачальників до 1700 м2 дощок в тиждень. Для кожного виробу моделі А потрібно 12 хв. машинного часу, а для виробу моделі В - 30 хв. У тиждень можна використовувати 160 годин машинного часу. Скільки виробів кожної моделі слід випускати фірмі в тиждень, якщо кожний вироб моделі А приносить 2 грн. прибутку, а кожний виріб моделі В - 4 грн. прибутку?
Вирішення
Побудова математичної моделі.
Хай x1 - кількість випущених за тиждень полиць моделі А, а x2 - кількість випущених полиць моделі В.
Тоді: 3x1 - кількість дощок, що необхідно на тиждень для виготовлення полиць моделі А
4x2- кількість дощок, що необхідно на тиждень для виготовлення полиць моделі В.
3x1 + 4x2 - кількість дощок, що потрібні на тиждень для виготовлення книжкових полиць двох моделей, а за умовами задачі це число не повинно перевищувати 1700 м2, отже одержуємо перше обмеження:
3x1+ 4x2<=1700 . (3.9)
Знайдемо обмеження на використання машинного часу.
12 хв. складають 0,2 години, а 30 хв. - 0,5 год., таким чином:
0,2x1 - кількість часу, що вимагається на тиждень для виробництва полиць моделі А;
0,5x2 - кількість часу, що вимагається на тиждень для виробництва полиць моделі В;
0,2x1 + 0,5x2 - кількість часу, що необхідна на тиждень для виробництва двох моделей, а за умовою задачі це число не повинно перевищувати 160 годин, отже одержуємо друге обмеження:
0,2x1 + 0,5x2<=160 або 2x1 + 5x2<=1600 . (3.10)
Крім того, оскільки x1 і x2 виражають щотижневий обсяг виробів, що випускаються, то вони не можуть бути негативними, тобто
x1>=0, x2>=0. (3.11)
Ця задача полягає в тому, щоб знайти такі значення x1 і x2, при яких щотижневий прибуток буде максимальним. Складемо вираз для щотижневого прибутку:
2x1 - щотижневий прибуток, одержаний від продажу полиць моделі А.
4x2 - щотижневий прибуток, одержаний від продажу полиць моделі В
Тоді F=2x1+4x2 - щотижневий прибуток, який повинен бути максимальним. Таким чином, маємо наступну математичну модель для даної задачі.
F=2x1 + 4x2->max
Отримана модель є задачею лінійного програмування. Функція F - це цільова функція, вона є лінійною функцією своїх змінних(x1 і x2). Обмеження на ці змінні (3.9) і (3.10) теж є лінійними. Виконана умова позитивності для змінних x1 і x2.
Необхідно знайти значення змінних x1 і x2, при яких дана функція F приймає максимальне значення, при дотриманні обмежень, що накладаються на ці змінні.
Рішення, що задовольняють системі обмежень і вимогою позитивності, є допустимими, а рішення, що задовольняють одночасно і вимогою мінімізації (максимізації) функції в цілому є оптимальними.
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ | ХАРКІВСЬКА НАЦІОНАЛЬНА АКАДЕМІЯ МІСЬКОГО ГОСПОДАРСТВА | Визначення економіко-математичного моделювання. Види моделей. Основні етапи моделювання | Випадкові події і величини, їх числові характеристики | Закони розподілу випадкової величини | Статистичні гіпотези та їх перевірка | Попередня обробка результатів спостережень і техніко-економічної інформації | Сутність економіко-математичних моделей оптимізації | Загальна характеристика задач математичного програмування | Види економіко-математичних моделей оптимізації |