Завдання 1
Для виготовлення виробів №1 і №2 є 100 кг металу. На виготовлення виробу №1 витрачається 2 кг металу, а на виріб №2 – 4 кг.
Скласти план виробництва, що забезпечує одержання найбільшого прибутку від продажу виробів, якщо відпускна вартість одного виробу №1 становить 3 грн. од., а виробу №2 – 2 грн. од., причому виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт.
Сировина Вироби Кількість сировини В1 В2 Метал 2 4 100 Вартість, грн. кг 3 2
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість виробу №1, що виготовляє підприємство за деяким планом, а через х2 кількість виробу №2. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає
∫ = 3х1+2х2.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
CI =2х1+4х2,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
2х1+4х2≤100
Окрім того, виробів №1 потрібно виготовити не більше 40 штук, а виробів №2 – 20 шт., тобто повинні виконуватись ще нерівності: х1≤40, х2≤20.
Таким чином, приходимо до математичної моделі:
Знайти х1, х2такі, що функція ∫ = 3х1+2х2досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
2x1 + 4x2 + 1x3 + 0x4 + 0x5 = 100
1x1 + 0x2 + 0x3 + 1x4 + 0x5 = 40
0x1 + 1x2 + 0x3 + 0x4 + 1x5 = 20
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3, x4, x5
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,100,40,20)
Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
План Базис В x1 x2 x3 x4 x5 min 1 x3 100 2 4 1 0 0 50 x4 40
1
0 0 1 0
40
x5 20 0 1 0 0 1 0 Індексний рядок F(X1) 0
-3
-2 0 0 0 0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
План Базис В x1 x2 x3 x4 x5 min 2 x3 20 0
4
1 -2 0
5
x1 40 1 0 0 1 0 0 x5 20 0 1 0 0 1 20 Індексний рядок F(X2) 120 0
-2
0 3 0 0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
План Базис В x1 x2 x3 x4 x5 min 3 x2 5 0 1 0,25 -0,5 0 5 x1 40 1 0 0 1 0 0 x5 15 0 0 -0,25 0,5 1 20 Індексний рядок F(X3) 130 0 0 0,5 2 0 0
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=40, х2=5. ............