На підприємстві виготовляються вироби двох видів А і В. Для цього використовується сировина чотирьох типів – І, ІІ, ІІІ, І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
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Визначимо мінімальне значення цільової функції F(X) = 3x1
+2x2
за таких умов-обмежень.
2x1
+4x2
≥10
3x1
+2x2
≥11
4x1
+7x2
≤32
Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
2x1
+ 4x2
-1x3
+ 0x4
+ 0x5
= 10
3x1
+ 2x2
+ 0x3
-1x4
+ 0x5
= 11
4x1
+ 7x2
+ 0x3
+ 0x4
+ 1x5
= 32
Введемо штучні змінні x.
2x1
+ 4x2
-1x3
+ 0x4
+ 0x5
+ 1x6
+ 0x7
= 10
3x1
+ 2x2
+ 0x3
-1x4
+ 0x5
+ 0x6
+ 1x7
= 11
4x1
+ 7x2
+ 0x3
+ 0x4
+ 1x5
+ 0x6
+ 0x7
= 32
Для постановки завдання на мінімум цільову функцію запишемо так:
F(X) = 3x1
+2x2
+Mx6
+Mx7
=> min
За використання штучних змінних, що вводяться в цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
F(X) = (3-5M)x1
+(2-6M)x2
+(1M)x3
+(1M)x4
+(21M) => min
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
2
4
-1
0
0
1
0
3
2
0
-1
0
0
1
4
7
0
0
1
0
0
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і при тому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x6
, x7
, x5
,
Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:
X1 = (0,0,0,0,32,10,11)
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
0
x6
10
2
4
-1
0
0
1
0
x7
11
3
2
0
-1
0
0
1
x5
32
4
7
0
0
1
0
0
Індексний
рядок
F(X0)
21M
-3+5M
-2+6M
-1M
-1M
0
0
0
Переходимо до основного алгоритму симплекс-методу.
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
min
1
x6
10
2
4
-1
0
0
1
0
2.5
x7
11
3
2
0
-1
0
0
1
5.5
x5
32
4
7
0
0
1
0
0
4.57
Індексний
рядок
F(X1)
21M
-3+5M
-2+6M
-1M
-1M
0
0
0
0
Оскільки, в індексному рядку знаходяться позитивні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х2
, оскільки значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
min
2
x2
2.5
0.5
1
-0.25
0
0
0.25
0
5
x7
6
2
0
0.5
-1
0
-0.5
1
3
x5
14.5
0.5
0
1.75
0
1
-1.75
0
29
Індексний
рядок
F(X2)
5+6M
-2+2M
0
-0.5+0.5M
-1M
0
0.5-1.5M
0
0
Даний план, також не оптимальний, тому будуємо знову нову симплексну таблицю. У якості ведучого виберемо елемент у стовбці х1
.
План
Базис
В
x1
x2
x3
x4
x5
x6
x7
3
x2
1
0
1
-0.375
0.25
0
0.375
-0.25
x1
3
1
0
0.25
-0.5
0
-0.25
0.5
x5
13
0
0
1.63
0.25
1
-1.63
-0.25
Індексний
рядок
F(X3)
11
0
0
0
-1
0
-1M
1-1M
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.
Оптимальний план можна записати так:
x2
= 1
x1
= 3
x5
= 13
F(X) = 3*3 + 2*1 = 11
Складемо двоїсту задачу до прямої задачі.
2y1
+3y2
+4y3
≤3
4y1
+2y2
+7y3
≤2
10y1
+11y2
+32y3
=> max
y1
≥ 0
y2
≥ 0
y3
≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1
.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1
розташована в стовпцях додаткових змінних.
Тогда Y = C*A-1
=
Оптимальний план двоїстоїзадачідорівнює:
y1
= 0
y2
= 1
y3
= 0
Z(Y) = 10*0+11*1+32*0 = 11
Завдання 3
Розв’язати транспортну задачу.
1
4
2
1
2
300
2
2
3
1
3
90
3
4
5
6
7
70
100
20
70
90
180
Розв’язок
Побудова математичної моделі
. Нехай xij
— кількість продукції, що перевозиться з і
-го пункту виробництва до j
-го споживача
. Перевіримо необхідність і достатність умоврозв'язання задачі:
Умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.
Занесемо вихідні дані у таблицю.
В1
В2
В3
В4
В5
Запаси
А1
1
4
2
1
2
300
А2
2
2
3
1
3
90
А3
3
4
5
6
7
70
Потреби
100
20
70
90
180
Розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai
Bj
ui
b1
= 100
b2
= 20
b3
= 70
b4
=90
b5
=180
а1
= 300
1
100
4
[-]20
2
70
1
90
2
[+]20
u1
= 0
а2
= 90
2
2
3
1
3
90
u2
= 1
а3
= 70
3
4
[+]
5
6
7
[-]70
u3
= 5
vj
v1
=1
v2
=4
v3
=2
v4
=1
v5
=2
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m+n-1=7. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0:
u1
=0, u2
=1, u3
=5, v1
=1, v2
=4, v3
=2 v4
=1, v5
=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui
+ vj
≤ cij
(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
(2;2): 1 + 4 > 2; ∆22
= 1 + 4 - 2 = 3
(2;4): 1 + 1 > 1; ∆24
= 1 + 1 - 1 = 1
(3;1): 5 + 1 > 3; ∆31
= 5 + 1 - 3 = 3
(3;2): 5 + 4 > 4; ∆32
= 5 + 4 - 4 = 5
(3;3): 5 + 2 > 5; ∆33
= 5 + 2 - 5 = 2
max(3,1,3,5,2) = 5
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;2): 4. Для цього в перспективну клітку (3;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з хij
, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n
+ m
– 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai
Bj
ui
b1
= 100
b2
= 20
b3
= 70
b4
=90
b5
=180
а1
= 300
1
[-]100
4
2
70
1
90
2
[+] 40
u1
= 0
а2
= 90
2
2
3
1
3
90
u2
= 1
а3
= 70
3
[+]
4
20
5
6
7
[-] 50
u3
= 5
vj
v1
=1
v2
=-1
v3
=2
v4
=1
v5
=2
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
(2;4): 1 + 1 > 1; ∆24
= 1 + 1 - 1 = 1
(3;1): 5 + 1 > 3; ∆31
= 5 + 1 - 3 = 3
(3;3): 5 + 2 > 5; ∆33
= 5 + 2 - 5 = 2
max(1,3,2) = 3
Вибираємо максимальну оцінку вільної клітини (3;1): 3
Для цього в перспективну клітку (3;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 5) = 50. Додаємо 50 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 50 з Хij
, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Ai
Bj
ui
b1
= 100
b2
= 20
b3
= 70
b4
=90
b5
=180
а1
= 300
1
[-] 50
4
2
70
1
90
2
[+] 90
u1
= 0
а2
= 90
2
2
[+]
3
1
3
[-]90
u2
= 1
а3
= 70
3
[+] 50
4
[-] 20
5
6
7
u3
= 2
vj
v1
=1
v2
=2
v3
=2
v4
=1
v5
=2
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
(2;2): 1 + 2 > 2; ∆22
= 1 + 2 - 2 = 1
(2;4): 1 + 1 > 1; ∆24
= 1 + 1 - 1 = 1
max(1,1) = 1
Вибираємомаксимальнуоцінкувільноїклітини (2;2): 2
Для цього в перспективну клітку (2;2) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з Хij
, що стоять в мінусових клітинах.
В результаті отримаємо новий опорний план.
Ai
Bj
ui
b1
= 100
b2
= 20
b3
= 70
b4
=90
b5
=180
а1
= 300
1
30
4
2
70
1
[-]90
2
[+] 110
u1
= 0
а2
= 90
2
2
20
3
1
[+]
3
[-] 70
u2
= 1
а3
= 70
3
70
4
5
6
7
u3
= 2
vj
v1
=1
v2
=1
v3
=2
v4
=1
v5
=2
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
(2;4): 1 + 1 > 1; ∆24
= 1 + 1 - 1 = 1
Вибираємомаксимальнуоцінкувільноїклітини (2;4): 1
Для цього в перспективну клітку (2;4)поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 5) = 70. Додаємо 70 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 70 з Хij
, що стоять в мінусових клітинах.