Математичні моделі задач лінійного програмування (стр. 1 из 3)
Завдання 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 |
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х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 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х2.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 3 | x3 | 200 | 0 | 0 | 1 | 3 | 2 | -3 | -2 | 66,67 |
| x1 | 100 | 1 | 0 | 0 | -1 | 0 | 1 | 0 | 0 | |
| x2 | 200 | 0 | 1 | 0 | 0 | -1 | 0 | 1 | 0 | |
| Індексний рядок | F(X3) | 20000 | 0 | 0 | 0 | -80 | -60 | 100080 | 100060 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х4.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 4 | x4 | 66,67 | 0 | 0 | 0,33 | 1 | 0,67 | -1 | -0,67 | 100 |
| x1 | 166,67 | 1 | 0 | 0,33 | 0 | 0,67 | 0 | -0,67 | 250 | |
| x2 | 200 | 0 | 1 | 0 | 0 | -1 | 0 | 1 | 0 | |
| Індексний рядок | F(X4) | 25333,33 | 0 | 0 | 26,67 | 0 | -6,67 | 100000 | 100006,67 | 0 |
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х5.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | min |
| 5 | x5 | 100 | 0 | 0 | 0,5 | 1,5 | 1 | -1,5 | -1 | 100 |
| x1 | 100 | 1 | 0 | 0 | -1 | 0 | 1 | 0 | 250 | |
| x2 | 300 | 0 | 1 | 0,5 | 1,5 | 0 | -1,5 | 0 | 0 | |
| Індексний рядок | F(X5) | 26000 | 0 | 0 | 30 | 10 | 0 | 99990 | 100000 | 0 |
Оскільки всі оцінки >0, то знайдено оптимальний план, що забезпечує максимальний прибуток: х1=100, х2=300. Прибуток, при випуску продукції за цим планом, становить 26000 грн.
Завдання 2
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо мінімальне значення цільової функції F(X) = 3x1+x2 при наступних умовах-обмежень.
x1+2x2≤6
-5x1+4x2≤2
7x1+5x2≥35
Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних.
1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 6
-5x1 + 4x2 + 0x3 + 1x4 + 0x5 = 2
7x1 + 5x2 + 0x3 + 0x4-1x5 = 35
Введемо штучні змінні x.
1x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 = 6
-5x1 + 4x2 + 0x3 + 1x4 + 0x5 + 0x6 = 2
7x1 + 5x2 + 0x3 + 0x4-1x5 + 1x6 = 35
Для постановки задачі на мінімум цільову функцію запишемо так:
F(X) = 3x1+x2 - Mx6 => max
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,6,2,0,35)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | х6 |
| 0 | х3 | 6 | 1 | 2 | 1 | 0 | 0 | 0 |
| x4 | 2 | -5 | 4 | 0 | 1 | 0 | 0 | |
| х6 | 35 | 7 | 5 | 0 | 0 | -1 | 1 | |
| Індексний рядок | F(X0) | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Переходимо до основного алгоритму симплекс-методу.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 1 | х3 | 6 | 1 | 2 | 1 | 0 | 0 | 0 | 6 |
| x4 | 2 | -5 | 4 | 0 | 1 | 0 | 0 | 0 | |
| х6 | 35 | 7 | 5 | 0 | 0 | -1 | 1 | 5 | |
| Індексний рядок | F(X1) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | min |
| 2 | х3 | 1 | 0 | 1,29 | 1 | 0 | 0,1429 | -0,1429 | 7 |
| x4 | 27 | 0 | 7,57 | 0 | 1 | -0,7143 | 0,7143 | 0 | |
| х1 | 5 | 1 | 0,7143 | 0 | 0 | -0,1429 | 0,1429 | 0 | |
| Індексний рядок | F(X2) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х5, оскільки значення коефіцієнта за модулем найбільше.
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 |
| 3 | х5 | 7 | 0 | 9 | 7 | 0 | 1 | -1 |
| x4 | 32 | 0 | 14 | 5 | 1 | 0 | 0 | |
| х1 | 6 | 1 | 2 | 1 | 0 | 0 | 0 | |
| Індексний рядок | F(X3) | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Оптимальний план можна записати так:
x5 = 7
x4 = 32
x1 = 6
F(X) = 3*6 = 18
Складемо двоїсту задачу до поставленої задачі лінійного програмування.
y1+5y2+7y3≥3
2y1-4y2+5y3≥1
6y1-2y2+35y3 => min
y1 ≥ 0
y2 ≤ 0
y3 ≤ 0
двоїстий симплексний задача лінійний програмування
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів. Використовуючи останню інтеграцію прямої задачі знайдемо, оптимальний план двоїстої задачі. Із теореми двоїстості слідує, що Y = C*A-1. Сформуємо матрицю A із компонентів векторів, які входять в оптимальний базис.