- •Тема 1. Побудова моделей задач математичного програмування
- •1.1. Формальна постановка задачі мп
- •1.2. Побудова моделей задач мп
- •Завдання для розв’язування
- •1). Побудувати математичну модель задачі. Задані:
- •2). Побудувати математичну модель задачі:
- •3). Привести до канонічного виду та представити у матричній формі:
- •5). Побудувати математичну модель задачі:
- •6). Привести до канонічного виду та представити у матричній формі:
- •7). Побудувати математичну модель задачі.
Тема 1. Побудова моделей задач математичного програмування
1.1. Формальна постановка задачі мп
Математичне програмування (МП) – математична дисципліна, що вивчає екстремальні задачі та розробляє методи їх вирішення.
У загальному вигляді задача МП полягає у визначенні найбільшого або найменшого значення функції мети
за умов
,
де bi – деякі дійсні чила.
Якщо функція мети та обмеження є лінійні, то задача МП є задачою лінійного програмування (ЛП).
Задача ЛП в канонічній формі є наступною:
,
,
1.2. Побудова моделей задач мп
Прикладами моделей задач МП є задача виробничого планування, задача про розкрій, транспортна задача, задача про суміш.
Задача про розкрій.
Паперова фабрика випускає рулони шириною 2 м. За замовленнями постачаються рулони шириною 0.5, 0.7, 0,9 м. Наявні наступні замовлення:
№ замовл. |
Потрібна ширина |
Потрібна к-ть рулонів |
1 |
0.5 |
150 |
2 |
0.7 |
200 |
3 |
0.9 |
300 |
Необхідно визначити такий спосіб розрізання рулонів, щоб кількість відходів була мінімальною.
Cформуємо варіанти розрізання:
Ширина |
1 |
2 |
3 |
4 |
5 |
6 |
Мінімальна к-ть рулонів |
|
0.5 |
0 |
2 |
2 |
4 |
1 |
0 |
150 |
y1 |
0.7 |
1 |
1 |
0 |
0 |
2 |
0 |
200 |
y2 |
0.9 |
1 |
0 |
1 |
0 |
0 |
2 |
300 |
y3 |
Втрати |
0.4 |
0.3 |
0.1 |
0 |
0.1 |
0.2 |
|
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
де: xj - кількість стандартних рулонів, що розрізаються за допомогою j-го способу;
yi - залишкова к-ть рулонів і-го типу.
0.4x1+ 0.3x2+ 0.1x3+ 0x4+ 0.1x5+ 0.2x6+ 0.5y1 +0.7y2 + 0.9y3 Min
0 x1+ 2 x2+ 2 x3 + 4x4 + 1 x5 + 0 x6 - 150 = y1
1 x1+ 1 x2+ 0 x3 + 0x4 + 2 x5 + 0 x6 - 200 =y2
1 x1+ 0 x2+ 1 x3 + 0x4 + 0 x5 + 2 x6 - 300 =y3
.
Визначення оптимального асортименту.
Наявно p видів ресурсів в кількостях та q видів виробів. Задана матриця , де характеризує норми витрат i-го ресурсу на одиницю k-го виробу (k=1,2,...,q).
Ефективніть випуску одиниці k-го виробу характеризується показником , що задовільняє умові лінійності.
Визначити план випуску виробів (оптимальний асортимент), при якому сумарна ефективність приймає найбільше значення.
Кількість одиниць k-го виробу, що випускається підприємством, позначимо . Тоді математична модель задачі має такий вигляд:
максимізувати
при обмеженнях
Крім обмеження за ресурсами, в модель можуть бути введені додаткові обмеження на плановий випуск продукції , умови комплектності для складання для усіх i, j, k та ін.
Оптимальне розподілення взаємозамінних ресурсів.
Наявно m видів взаємозамінних ресурсів , що використовуються при виконанні n різних робіт в об’ємах .
Задано числа , що вказують скільки одиниць j-ї роботи можна отримати з одиниці i-го ресурсу, а також - витрати при виготовленні одиниці j-го продукту з i-го ресурсу.
Необхідно розподілити ресурси за роботами таким чином, щоб сумарна ефективність була найбільшою (або сумарні затрати - найменшими).
Кількість одиниць i-го ресурсу, яка виділена для виконання робіт j-го виду, позначимо .
Математична модель задачі буде наступною:
мінімізувати
при обмеженнях
Перше обмеження означає, що план усіх робіт повинен бути виконаний повністю, а друге - що ресурси повинні бути використані повністю.
Задача про суміші.
Наявні p компонентів і = 1,2,...,р, при сполученні яких в різних пропорціях отримують різні суміші. До складу кожного компоненту, а відповідно і до суміші входить q речовин. Кількість k-ї речовини k = 1,2,...,q, що входить до складу одиниці і-го компоненту і до складу одиниці суміші, позначимо, відповідно і . Вважатимемо, що залежить від лінійно, тобто якщо суміш складається з одиниць першого компоненту; - одиниць другого компоненту і т.д., то .
Задано р значень , що характеризують ціну, масу або калорійність одиниці і-го компоненту і q величин , що вказують мінімально необхідний процентний склад k-ї речовини у суміші.
Необхідно визначити склад суміші, при якому сумарна характеристика (ціна, маса або калорійність) виявиться найкращою.
Позначимо через величину компоненту p-го виду, що входить до суміші.
Математична модель має такий вигляд:
мінімізувати
при умові
Умова означає, що процентний склад k-ї речовини і одиниці суміші повинно бути не менше величини .
До цієї ж моделі зводиться, наприклад, задача визначення оптимального раціону.
Задача про розкрій матеріалів.
На розкрій поступає m різних матеріалів. Необхідно виготовити з них k різних комплектів виробів в кількостях, пропорційних (умова комплектності).
Нехай кожна одиниця j-го матеріалу, j = 1,2,...,m, може бути розкроєна n різними способами, так що при використанні і-го способу розкрою, і = 1,2,...,n, вийде одиниць k-го виробу.
Визначити план розкрою, що забезпечує максимальну кількість комплектів, якщо відомо, що обсяг запасу j-го матеріалу рівний одиниць.
Кількість одиниць j-го матеріалу, що розкроюються і-тим способом, позначимо , а кількість комплектів виробів, що виготовляються - .
Математична модель задачі виглядає наступним чином:
максимізувати
при умовах
Перша умова означає обмеження запасу j-го матеріалу, а друга - умову комплектності.
Оптимальні балансові моделі.
Розглянемо n-галузеву балансову модель з постійними технологічними коефіцієнтами, що задаються матрицею затрат , де - затрати продуктів i-ї галузі на виробництво одиниці продукції j-ї залузі. Виробничі потужності i-ї галузі обмежують її валовий випуск величиною (і=1,...,n) і ціна остаточного продукту i-ї галузі складає .
Визначити оптимальний валовий випуск продукції кожної галузі, при якому буде досягнено максимальний сумарний випуск рстаточного продукту в грошовому представленні.
Позначимо вектор валової продукції усіх галузей , а вектор остаточного продукту . Тоді - обсяг продукту i-ї галузі, що йде на накопичення.
Між векторами X та Y існує наступний зв’язок: X = AX + Y — де AX — продукт, що витрачається на споживання.
Звідси Y = X [E-A], X = [E-A]-1Y.
Математична модель задачі має вигляд:
максимізувати
при умовах .
Крім того, в задачі можуть бути додатково вказані обмеження, що накладаються на остаточні продукти, наприклад:
а) — умова комплектності;
б) - умова обмеженості випуску остаточного продукту.