Завдання 1
Побудувати математичну модель задачі.
На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів – І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно, 21; 4; 6; 10 од. Для виготовлення одного виробу А необхідна така кількість одиниць сировини чотирьох видів: 2; 1; 0; 2. Для виробу В – 3; 0; 1; 1 од. відповідно. Випуск одного виробу А дає 3 грн. од. прибутку, типу В – 2 грн. од. Скласти план виробництва, який забезпечує найбільший прибуток.
Сировина Норма витрат сировини, од Запаси сировини, од. А В І 2 3 21 ІІ 1 0 4 ІІІ 0 1 6 ІV 2 1 10 Ціна, грн. од. 3 2
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість виробів 1-ї моделі, що виготовляє підприємство за деяким планом, а через х2 кількість виробів 2-ї моделі. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає
∫ = 3х1+2х2.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
CI =2х1 + 3х2,
CII =1х1 + 0х2,
CIII =0х1 + 1х2,
CIV =2х1 + 1х2,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
2х1 + 3х2≤ 21
1х1≤ 4
1х2≤ 6
2х1 + 1х2≤ 10
Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0.
Таким чином, приходимо до математичної моделі (задачі лінійного програмування):
Знайти х1 , х2 такі, що функція ∫ = 3х1+2х2досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних. Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 21
1x1 + 0x2 + 0x3 + 0x4 + 0x5 + 1x6 = 4
0x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 6
2x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 = 10
де х1,...,х6>0
Для постановки задачі на максимум цільову функцію запишемо так:
F(X) = 3 x1 +2 x2 - M x6 =>max
Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
План Базис В
x1
x2
x3
x4
x5
x6
min 1
x3
21 2 3 1 0 0 0 10.5
x6
4
1
0 0 0 0 1
4
x4
6 0 1 0 1 0 0 0
x5
10 2 1 0 0 1 0 5 Індексний рядок F(X1) -400000
-100003
-2 0 0 0 0 0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
План Базис В
x1
x2
x3
x4
x5
x6
min 2
x3
13 0 3 1 0 0 -2 4.33
x1
4 1 0 0 0 0 1 0
x4
6 0 1 0 1 0 0 6
x5
2 0
1
0 0 1 -2
2
Індексний рядок F(X2) 12 0
-2
0 0 0 100003 0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. ............
