Завдання 1
Побудуватиматематичну модель задачі.
Напідприємстві виготовляються вироби двох видів А і В. Для цього використовуєтьсясировина чотирьох типів – І, ІІ, ІІІ, ІV, запаси якої дорівнюють, відповідно,21; 4; 6; 10 од. Для виготовлення одного виробу А необхідна така кількістьодиниць сировини чотирьох видів: 2; 1; 0; 2. Для виробу В – 3; 0; 1; 1 од.відповідно. Випуск одного виробу А дає 3 грн. од. прибутку, типу В – 2 грн. од.Скласти план виробництва, який забезпечує найбільший прибуток.Сировина Норма витрат сировини, од Запаси сировини, од. А В І 2 3 21 ІІ 1 4 ІІІ 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.
2×1 + 3×2 + 1×3 + 0x4+ 0x5 + 0x6 = 21
1×1 + 0x2 + 0x3 + 0x4+ 0x5 + 1×6 = 4
0x1 + 1×2 + 0x3 + 1×4+ 0x5 + 0x6 = 6
2×1 + 1×2 + 0x3 + 0x4+ 1×5 + 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 10.5
x6 4
1 1
4
x4 6 1 1
x5 10 2 1 1 5 Індексний рядок F(X1) -400000
-100003 -2
Оскільки, в індексному рядку знаходяться негативні коефіцієнти,поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучоговиберемо елемент у стовбці х1, оскільки значення коефіцієнта замодулем найбільше.
математична модель симплекс транспортна задача екстремумПлан Базис В
x1
x2
x3
x4
x5
x6 min 2
x3 13 3 1 -2 4.33
x1 4 1 1
x4 6 1 1 6
x5 2
1 1 -2
2 Індексний рядок F(X2) 12
-2 100003
Даний план, також не оптимальний, тому будуємо знову новусимплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.План Базис В
x1
x2
x3
x4
x5
x6 Min 3
x3 7 0 0 1 0 -3 4 4.33
x1 4 1 0 0 0 0 1 0
x4 4 0 0 0 1 -1 2 6
x2 2 0 1 0 0 1 -2 2 Індексний рядок F(X3) 16 0 0 0 0 2 99999 0
Оскількивсі оцінки >0, то знайдено оптимальний план, що забезпечуємаксимальний прибуток: х1=4, х2=2. Прибуток, при випускупродукції за цим планом, становить 16 грн.
Завдання 2
Записатидвоїсту задачу до поставленої задачі лінійного програмування. Розв’язати однуіз задач симплексним методом і визначити оптимальний план іншої задачі.Оптимальні результати перевірити графічно.
/>/>
/>
Розв’язок
Прямазадача лінійного програмування має вигляд:
/>
Приобмеженнях:
/>
Оскільки,у прямій задачі лінійного програмування необхідно знайти мінімум функції, топриведемо першопочаткову умову до вигляду:
/>
Длядосягнення відповідного вигляду помножимо 1-у та 2-у нерівність на -1
1х1-4ч2≥-8
-1х1+1х2≥-3
Врезультаті отримаємо наступні матриці:
/>
/>
/>
Дляскладання двоїстої задачі лінійного програмування знайдемо матриці А, В, СТ.
/>
/>
/>
Відповідно,двоїста задача лінійного програмування матиме вигляд:
F(Y)=-8Y1-3Y2+9Y3 (max)
Обмеження:
1Y1-1Y2+2Y3≤2
-4Y1+1Y2+1Y3≤1
Y1≥0
Y2≥0
Y3≥0
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимомінімальне значення цільової функції F(X) = 2×1+x2 принаступних умовах-обмежень.
-x1+4×2≤8
x1-x2≤3
2×1+x2≥9
Дляпобудови першого опорного плану систему нерівностей приведемо до системирівнянь шляхом введення додаткових змінних.
Оскількимаємо змішані умови-обмеження, то введемо штучні змінні x.
-1×1+ 4×2 + 1×3 + 0x4 + 0x5 + 0x6= 8
1×1-1×2+ 0x3 + 1×4 + 0x5 + 0x6 = 3
2×1+ 1×2 + 0x3 + 0x4-1×5 + 1×6= 9
Дляпостановки задачі на мінімум цільову функцію запишемо так:
F(X)= 2 x1 + x2 +M x6 =>min
Переходимо до основного алгоритму симплекс-методу.План Базис В
x1
x2
x3
x4
x5
x6 Min 1
x3 8 -1 4 1
x4 3
1 -1 1
3
x6 9 2 1 -1 1 4.5 Індексний рядок F(X1) 900000
199998 99999 -100000
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти,поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучоговиберемо елемент у стовбці х1, оскільки значення коефіцієнта замодулем найбільше.План Базис В
x1
x2
x3
x4
x5
x6 min 2
x3 11 3 1 1 3.67
x1 3 1 -1 1
x6 3
3 -2 -1 1
1 Індексний рядок F(X2) 300006
299997 -199998 -100000
Даний план, також не оптимальний, тому будуємо знову новусимплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.План Базис В
x1
x2
x3
x4
x5
x6 min 3
x3 8 0 0 1 3 1 -1 3.67
x1 4 1 0 0 0.33 -0.33 0.33 0
x2 1 0 1 0 -0.67 -0.33 0.33 1 Індексний рядок F(X3) 9 0 0 0 0 -1 -99999 0
Остаточнийваріантсимплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативнікоефіцієнти.
Оптимальний план можна записати так:
x3 = 8
x1 = 4
x2 = 1
F(X) = 2*4 + 1*1 = 9
Визначаємооптимальний план двоїстої задачі до поставленої задачі лінійного програмування.
F(Y)=-8Y1-3Y2+9Y3 (max)
Обмеження:
1Y1-1Y2+2Y3≤2
-4Y1+1Y2+1Y3≤1
Y1≥0
Y2≥0
Y3≥0
Дляпобудови першого опорного плану систему нерівностей приведемо до системирівнянь шляхом введення додаткових змінних.
1×1-1×2+ 2×3 + 1×4 + 0x5 = 2
-4×1+ 1×2 + 1×3 + 0x4 + 1×5 = 1
Вважаючи,що вільні змінні рівні 0, отримаємо перший опорний план:План Базис В
x1
x2
x3
x4
x5
x4 2 1 -1 2 1
x5 1 -4 1 1 1 Індексний рядок F(X0) 8 3 -9
Перейдемодо основного алгоритму симплекс-метода.Оскільки в останньому стовбці присутньокілька мінімальних елементів 1, то номер рядка вибираємо по правилу Креко.