Завдання 1
Побудувати математичну модель задачі.
Меблева фабрика виготовляє столи, стільці, тумби і книжкові шафи використовуючи дошки двох видів, причому фабрика має 500 м2дошок першого виду і 1000 м2дошок другого виду. Задані також трудові ресурси в кількості 800 людино-годин. У таблиці наведені нормативи витрат кожного виду ресурсів на виготовлення одного виду і прибуток від реалізації одиниці виробу.
Ресурси Витрати на один виріб Запас сировини, м2 Столи Стільці Тумби Книжкові шафи Дошки І виду, м2 5 1 9 12 500 Дошки ІІ виду, м2 2 3 4 1 1000 Трудові ресурси, люд.год. 3 2 5 10 800 Прибуток від реалізації одного виробу, грн.од. 12 5 15 10
Визначити асортимент, що максимізує прибуток.
Розв’язок
Складаємо математичну модель задачі. Позначимо через х1кількість виробів 1-ї моделі, що виготовляє фірма за деяким планом, а через х2 кількість виробів 2-ї моделі та через та через х3і х4кількість виробів 3-ї і 4-ї моделі відповідно. Тоді прибуток, отриманий фабрикою від реалізації цих виробів, складає
∫ = 12х1+5х2 + 15х3+ 10х4.
Витрати сировини на виготовлення такої кількості виробів складають відповідно:
А =5х1+1х2 + 9х3+ 12х4,
В =2х1+3х2 + 4х3+ 1х4,
С =3х1+2х2 + 5х3+ 10х4,
Оскільки запаси сировини обмежені, то повинні виконуватись нерівності:
5х1+1х2 + 9х3+ 12х4≤ 500
2х1+3х2 + 4х3+ 1х4≤ 1000
3х1+2х2 + 5х3+ 10х4≤ 800
Оскільки, кількість виробів є величина невід'ємна, то додатково повинні виконуватись ще нерівності: х1> 0, х2> 0, х3> 0, х4> 0.
Таким чином, приходимо до математичної моделі (задачі лінійного програмування):
Знайти х1 , х2, х3 та х4 такі, що функція ∫ = 12х1+5х2 + 15х3+ 10х4 досягає максимуму при системі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом. Введемо балансні змінні х5 ≥ 0, х6≥ 0, х7≥ 0. Їх величина поки що невідома, але така, що перетворює відповідну нерівність у точну рівність. Після цього, задача лінійного програмування набуде вигляду: ∫ = 12х1+5х2 + 15х3+ 10х4 → max при обмеженнях
де х1,...,х7>0
Оскільки завдання вирішується на максимум, то ведучий стовпець вибирають по максимальному негативному кількістю та індексного рядку. Всі перетворення проводять до тих пір, поки не вийдуть в індексному рядку позитивні елементи.
Переходимо до основного алгоритму симплекс-методу.
План Базис В x1 x2 x3 x4 x5 x6 x7 min 1 x5 500 5 1 9 12 1 0 0 55.56 x6 1000 2 3 4 1 0 1 0 250 x7 800 3 2 5 10 0 0 1 160 Індексний рядок F(X1) 0 -12 -5 -15 -10 0 0 0 0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х3, оскільки значення коефіцієнта за модулем найбільше.
План Базис В x1 x2 x3 x4 x5 x6 x7 min 2 x3 55.56 0.56 0.11 1 1.33 0.11 0 0 100 x6 777.78 -0.22 2.56 0 -4.33 -0.44 1 0 0 x7 522.22 0.22 1.44 0 3.33 -0.56 0 1 2350 Індексний рядок F(X2) 833.33 -3.67 -3.33 0 10 1.67 0 0 0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1.
План Базис В x1 x2 x3 x4 x5 x6 x7 min 3 x1 100 1 0.2 1.8 2.4 0.2 0 0 500 x6 800 0 2.6 0.4 -3.8 -0.4 1 0 307.69 x7 500 0 1.4 -0.4 2.8 -0.6 0 1 357.14 Індексний рядок F(X3) 1200 0 -2.6 6.6 18.8 2.4 0 0 0
Даний план, знову не оптимальний, тому будуємо знову нову симплексну таблицю. ............
