Завдання 1
Цех випускає вали і втулки. На виробництво одного вала робочий витрачає 3 год., однієї втулки – 2 год. Від реалізації одного вала підприємство одержує прибуток 80 грн., а від реалізації однієї втулки – 60 грн. Цех має випустити не менше 100 валів і не менше 200 втулок. Скільки валів і скільки втулок має випустити цех, щоб одержати найбільший прибуток, якщо фонд робочого часу робітників становить 900 людино-годин?
Ресурс Вироби Фонд робочого часу Вали Втулки Робітник, год. од. 3 2 900 Вартість, грн. од. 80 60
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1 кількість валів, що виготовляє підприємство за деяким планом, а через х2 кількість втулок. Тоді прибуток, отриманий підприємством від реалізації цих виробів, складає
∫ = 80х1+60х2.
Витрати ресурсів на виготовлення такої кількості виробів складають відповідно:
CI =3х1+2х2,
Оскільки запаси ресурсів обмежені, то повинні виконуватись нерівності:
3х1+2х2≤900
Окрім того, валів потрібно виготовити не менше 100 штук, а втулок – 200 шт., тобто повинні виконуватись ще нерівності: х1≥ 100, х2≥ 200.
Таким чином, приходимо до математичної моделі:
Знайти х1, х2 такі, що функція ∫ = 80х1+60х2 досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом.
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних. Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
3x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 = 900
1x1 + 0x2 + 0x3-1x4 + 0x5 + 1x6 + 0x7 = 100
0x1 + 1x2 + 0x3 + 0x4-1x5 + 0x6 + 1x7 = 200
Для постановки задачі на максимум цільову функцію запишемо так:
F(X) = 80 x1 +60 x2 - M x6 - M x7 => max
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають стосунку до змісту поставленого завдання, проте вони дозволяють побудувати початкову точку, а процес оптимізації змушує ці змінні приймати нульові значення і забезпечити допустимість оптимального рішення.
З метою формулювання задачі для вирішення її в табличній формі скористаємося виразами з системи рівнянь для штучних змінних:
x6 = 100-x1 +x4
x7 = 200-x2 +x5
які підставимо в цільову функцію:
F(X) = 80x1 + 60x2 - M(100-x1 +x4 ) - M(200-x2 +x5 ) => max
або
F(X) = (80+1M)x1 +(60+1M)x2 +(-1M)x4 +(-1M)x5 +(-300M) => max
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
3 2 1 0 0 0 0 1 0 0 -1 0 1 0 0 1 0 0 -1 0 1
Базисні змінні це змінні, які входять лише в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3 , x6 , x7
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,900,0,0,100,200)
Оскільки завдання вирішується на максимум, то ведучий стовпець вибираємо по максимальному негативному кількістю та індексного рядку. Всі перетворення проводимо до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Складаємо симплекс-таблицю:
План Базис В x1 x2 x3 x4 x5 x6 x7 min 1 x3 900 3 2 1 0 0 0 0 300 x6 100 1 0 0 -1 0 1 0 100 x7 200 0 1 0 0 -1 0 1 0 Індексний рядок F(X1) -30000000 -100080 0 -100060 0 100000 0 0 0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. ............
