Математичне програмування (стр. 1 из 3)
Завдання 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 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х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) = 2x1+x2 при наступних умовах-обмежень.
-x1+4x2≤8
x1-x2≤3
2x1+x2≥9
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
Оскільки маємо змішані умови-обмеження, то введемо штучні змінні x.
-1x1 + 4x2 + 1x3 + 0x4 + 0x5 + 0x6 = 8
1x1-1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 3
2x1 + 1x2 + 0x3 + 0x4-1x5 + 1x6 = 9
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = 2 x1 + x2 +M x6 =>min
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | Min |
| 1 | x3 | 8 | -1 | 4 | 1 | 0 | 0 | 0 | 0 |
| x4 | 3 | 1 | -1 | 0 | 1 | 0 | 0 | 3 | |
| x6 | 9 | 2 | 1 | 0 | 0 | -1 | 1 | 4.5 | |
| Індексний рядок | F(X1) | 900000 | 199998 | 99999 | 0 | 0 | -100000 | 0 | 0 |
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | x3 | 11 | 0 | 3 | 1 | 1 | 0 | 0 | 3.67 |
| x1 | 3 | 1 | -1 | 0 | 1 | 0 | 0 | 0 | |
| x6 | 3 | 0 | 3 | 0 | -2 | -1 | 1 | 1 | |
| Індексний рядок | F(X2) | 300006 | 0 | 299997 | 0 | -199998 | -100000 | 0 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х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 |
Остаточнийваріант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.