Завдання 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
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.
Визначимо мінімальне значення цільової функції 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
За використання штучних змінних, що вводяться в цільову функцію, накладається так званий штраф величиною М, дуже велике позитивне число, яке зазвичай не задається.
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь висловлюємо штучні змінні:
x6
= 10-2x1
-4x2
+x3
x7
= 11-3x1
-2x2
+x4
які підставимо в цільову функцію:
F(X) = 3x1
+ 2x2
+ M(10-2x1
-4x2
+x3
) + M(11-3x1
-2x2
+x4
) => 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 з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1
черезалгебраїчнідоповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця 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 |
Розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ
=1x
11
+4x
12
+2x
13
+1x
14
+2x
15
+2x
21
+2x
22
+3x
23
+1x
24
+3x
25
+3x
31
+4x
32
+5x
33
+6x
34
+ +7x
35
.
Загалом математична модель сформульованої задачі має вигляд:
minZ
=1x
11
+4x
12
+2x
13
+1x
14
+2x
15
+2x
21
+2x
22
+3x
23
+1x
24
+3x
25
+3x
31
+4x
32
+5x
33
+6x
34
+ +7x
35
.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai
|
Bj
|
ui
|
b
1
= 100 |
b
2
= 20 |
b
3
= 70 |
b
4
=90 |
b
5
=180 |
а
1
= 300 |
1
100
|
4
[-]20
|
2
70
|
1
90
|
2
[+]20
|
u
1
= 0 |
а
2
= 90 |
2
|
2
|
3
|
1
|
3
90
|
u
2
= 1 |
а
3
= 70 |
3
|
4
[+]
|
5
|
6
|
7
[-]70
|
u
3
= 5 |
vj
|
v
1
=1 |
v
2
=4 |
v
3
=2 |
v
4
=1 |
v
5
=2 |
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 7, а має бути m+n-1=7. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0:
u
1
=0, u
2
=1, u
3
=5, v
1
=1, v
2
=4, v
3
=2 v
4
=1, v
5
=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
|
b
1
= 100 |
b
2
= 20 |
b
3
= 70 |
b
4
=90 |
b
5
=180 |
а
1
= 300 |
1
[-]100
|
4
|
2
70
|
1
90
|
2
[+] 40
|
u
1
= 0 |
а
2
= 90 |
2
|
2
|
3
|
1
|
3
90
|
u
2
= 1 |
а
3
= 70 |
3
[+]
|
4
20
|
5
|
6
|
7
[-] 50
|
u
3
= 5 |
vj
|
v
1
=1 |
v
2
=-1 |
v
3
=2 |
v
4
=1 |
v
5
=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
|
b
1
= 100 |
b
2
= 20 |
b
3
= 70 |
b
4
=90 |
b
5
=180 |
а
1
= 300 |
1
[-] 50
|
4
|
2
70
|
1
90
|
2
[+] 90
|
u
1
= 0 |
а
2
= 90 |
2
|
2
[+]
|
3
|
1
|
3
[-]90
|
u
2
= 1 |
а
3
= 70 |
3
[+] 50
|
4
[-] 20
|
5
|
6
|
7
|
|