Завдання 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 +1 M) x1 + (60 +1 M) 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
Оскількі, в індексному рядку знаходяться негатівні коефіцієнті, поточний опорний план неоптимальним, тому Будуємо новий план. У ЯКОСТІ ведучого віберемо елемент у стовбці х1, оскількі Значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
min
2
x3
600
0
2
2
0
3
-3
0
300
x1
100
1
0
0
0
-1
1
0
0
x7
200
0
1
1
0
0
0
1
200
Індексній рядок
F (X2)
-19992000
0
0
-100060
0
-80
100080
0
0
Сейчас план, кож не оптимальний, тому Будуємо Знову нову с...
