Зібраний врожай зерна трьох сільськогосподарських артілей повинен бути перевезений на три елеватори, а саме: елеватор А1
потужністю 100 тис. тонн, елеватор А2
– 80 тис. тонн; А3
– 90 тис. тонн. Визначити план перевезення зерна на елеватори, який мінімізує транспортні витрати.
С/г артіль
Затрати на перевезення 1 т зерна на елеватори, грн.
Запас зерна,
тис. т
В1
В2
В3
А1
12,5
24,0
18,4
80
А2
28,3
14,5
25,7
90
А3
15,7
20,6
16,3
100
Потужність елеваторів
100
80
90
Розв’язок
Побудова математичної моделі
. Нехай xij
— кількість продукції, що перевозиться з і
-го пункту виробництва до j
-го споживача
.
Перевіримо необхідність і достатність умов розв'язання задачі:
Оскільки
, то умова балансу дотримується. Запаси рівні потребам. Отже, модель транспортної задачі є закритою.
Занесемо вихідні дані у таблицю.
В1
В2
В3
Запаси
А1
12,5
24,0
18,4
80
А2
28,3
14,5
25,7
90
А3
15,7
20,6
16,3
100
Потреби
100
80
90
Розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai
Bj
ui
b1
= 100
b2
= 80
b3
= 90
а1
= 80
12,5
80
24,0
18,4
u1
= 0
а2
= 90
28,3
[-]20
14,5
[+]70
25,7
u2
= 15,8
а3
= 100
15,7
[+]
20,6
[-]20
16,3
80
u3
= 21,9
vj
v1
=12,5
v2
=-1,3
v3
=-5,6
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 5, а має бути m+n-1=5. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0:
u1
=0, u2
=15,8, u3
=21,9, v1
=12,5, v2
=-1,3, v3
=-5,6. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui
+ vj
≤ cij
(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (3;1): 15.7. Для цього в перспективну клітку (3;1) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (3, 2) = 20. Додаємо 20 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 20 з хij
, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n
+ m
– 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai
Bj
ui
b1
= 100
b2
= 80
b3
= 90
а1
= 80
12,5
80
24,0
18,4
u1
= 0
а2
= 90
28,3
[-] 0
14,5
90
25,7
[+]
u2
= 15,8
а3
= 100
15,7
[+] 20
20,6
16,3
[-]80
u3
= 3,2
vj
v1
=12,5
v2
=-1,3
v3
=13,1
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
Вибираємо максимальну оцінку вільної клітини (2;3): 25.7
Для цього в перспективну клітку (2;3) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (2, 1) = 0. Додаємо 0 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 0 з Хij
, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Ai
Bj
ui
b1
= 100
b2
= 80
b3
= 90
а1
= 80
12,5
80
24,0
18,4
u1
= 0
а2
= 90
28,3
14,5
90
25,7
0
u2
= 12,6
а3
= 100
15,7
20
20,6
16,3
80
u3
= 3,2
vj
v1
=12,5
v2
=1,9
v3
=13,1
Перевіримо оптимальність опорного плану, тобто повторюємо описані раніше дії.
Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 3923 грн.
Завдання 2
математична модель екстремум транспортна задача
Записати двоїсту задачу до поставленої задачі лінійного програмування. Розв’язати одну із задач симплексним методом і визначити оптимальний план іншої задачі. Оптимальні результати перевірити графічно.
Розв’язок
Розв’яжемо задачу лінійного програмування симплексним методом.
Визначимо максимальне значення цільової функції F(X) = 3x1
+x2
за таких умов-обмежень.
-2x1
+6x2
≤2
4x1
-3x2
≤12
x1
-x2
≥3
Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми).
-2x1
+ 6x2
+ 1x3
+ 0x4
+ 0x5
= 2
4x1
-3x2
+ 0x3
+ 1x4
+ 0x5
= 12
1x1
-1x2
+ 0x3
+ 0x4
-1x5
= 3
Введемо штучні змінні x.
-2x1
+ 6x2
+ 1x3
+ 0x4
+ 0x5
+ 0x6
= 2
4x1
-3x2
+ 0x3
+ 1x4
+ 0x5
+ 0x6
= 12
1x1
-1x2
+ 0x3
+ 0x4
-1x5
+ 1x6
= 3
Для постановки завдання на максимум цільову функцію запишемо так:
F(X) = 3x1
+x2
- Mx6
=>max
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.
З рівнянь висловлюємо штучні змінні:
x6
= 3-x1
+x2
+x5
які підставимо в цільову функцію:
F(X) = 3x1
+ x2
- M(3-x1
+x2
+x5
) =>max
або
F(X) = (3+1M)x1
+(1-1M)x2
+(-1M)x5
+(-3M) =>max
Матриця коефіцієнтів A = a(ij) цієї системи рівнянь має вигляд:
Базисні перемінні це змінні, які входять тільки в одне рівняння системи обмежень і притому з одиничним коефіцієнтом.
Вирішимо систему рівнянь відносно базисних змінних:
x3
, x4
, x6
,
Вважаючи, що вільні змінні рівні 0, отримаємо перші опорний план:
X1 = (0,0,2,12,0,3)
План
Базис
В
x1
x2
x3
x4
x5
x6
0
x3
2
-2
6
1
0
0
0
x4
12
4
-3
0
1
0
0
x6
3
1
-1
0
0
-1
1
Індексний рядок
F(X0)
-3M
-3-1M
-1+1M
0
0
1M
0
Переходимо до основного алгоритму симплекс-методу.
План
Базис
В
x1
x2
x3
x4
x5
x6
min
1
x3
2
-2
6
1
0
0
0
0
x4
12
4
-3
0
1
0
0
3
x6
3
1
-1
0
0
-1
1
3
Індексна рядок
F(X1)
-3M
-3-1M
-1+1M
0
0
1M
0
0
Оскільки, в індексному рядку знаходяться негативні коефіцієнти, поточний опорний план неоптимальний, тому будуємо новий план. У якості ведучого виберемо елемент у стовбці х1
, оскільки значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
x6
2
x3
8
0
4.5
1
0.5
0
0
x1
3
1
-0.75
0
0.25
0
0
x6
0
0
-0.25
0
-0.25
-1
1
Індексна рядок
F(X2)
9
0
-3.25+0.25M
0
0.75+0.25M
1M
0
Остаточний варіант симплекс-таблиці оптимальний, тому що в індексному рядку знаходяться позитивні коефіцієнти.
Оптимальний план можна записати так:
x3
= 8
x1
= 3
x6
= 0
F(X) = 3*3 = 9
Складемо двоїсту задачу до прямої задачі.
-2y1
+4y2
+y3
≥3
6y1
-3y2
-y3
≥1
2y1
+12y2
+3y3
=>min
y1
≥ 0
y2
≥ 0
y3
≤ 0
Рішення двоїстої задачі дає оптимальну систему оцінок ресурсів.
Використовуючи останню ітерацію прямої задачі знайдемо, оптимальний план двоїстої задачі.
З першої теореми двоїстості випливає, що Y = C*A-1
.
Складемо матрицю A з компонентів векторів, що входять в оптимальний базис.
Визначивши зворотну матрицю А-1
через алгебраїчні доповнення, отримаємо:
Як видно з останнього плану симплексного таблиці, зворотна матриця A-1
розташована в стовпцях додаткових змінних .
Тоді Y = C*A-1
=
Оптимальний план двоїстої задачі дорівнює:
y1
= 0
y2
= 0.75
y3
= 0
Z(Y) = 2*0+12*0.75+3*0 = 9
Завдання 3
Розв’язати транспортну задачу.
1
4
7
9
1
250
2
3
1
2
4
300
2
1
3
1
4
150
110
80
100
90
70
Розв’язок
Побудова математичної моделі
. Нехай xij
— кількість продукції, що перевозиться з і
-го пункту виробництва до j
-го споживача
. Оскільки
, то задачу треба закрити, тобто збалансувати (зрівняти) поставки й потреби:
У нашому випадку робиться це введенням фіктивного постачальника, оскільки
. З уведенням фіктивного споживача транспортній таблиці додатково заявляється n робочих клітинок.
Ціни, додатковим клітинкам, щоб фіктивний стовбець був нейтральним щодо оптимального вибору планових перевезень, призначаються усі рівні нулю.
Занесемо вихідні дані у таблицю.
В1
В2
В3
В4
В5
В6
Запаси
А1
1
4
7
9
1
0
250
А2
2
3
1
2
4
0
300
А3
2
1
3
1
4
0
150
Потреби
110
80
100
90
70
250
Забезпечивши закритість розв'язуваної задачі, розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
Ai
Bj
ui
b1
= 110
b2
= 80
b3
= 100
b4
=90
b5
=70
b6
=250
а1
= 250
1
110
4
80
7
[-] 60
9
1
[+]
0
u1
= 0
а2
= 300
2
3
1
[+] 40
2
90
4
[-] 70
0
100
u2
= -6
а3
= 150
2
1
3
1
4
0
150
u3
= -6
vj
v1
= 1
v2
= 4
v3
= 7
v4
= 8
v5
= 10
v6
= 6
В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.
Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є не виродженим.
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0:
u1
+ v1
= 1; 0 + v1
= 1; v1
= 1
u1
+ v2
= 4; 0 + v2
= 4; v2
= 4
u1
+ v3
= 7; 0 + v3
= 7; v3
= 7
u2
+ v3
= 1; 7 + u2
= 1; u2
= -6
u2
+ v4
= 2; -6 + v4
= 2; v4
= 8
u2
+ v5
= 4; -6 + v5
= 4; v5
= 10
u2
+ v6
= 0; -6 + v6
= 0; v6
= 6
u3
+ v6
= 0; 6 + u3
= 0; u3
= -6
Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui
+ vj
≤ cij
(для порожніх клітинок таблиці).
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij
(1;5): 0 + 10 > 1; ∆15
= 0 + 10 - 1 = 9
(1;6): 0 + 6 > 0; ∆16
= 0 + 6 - 0 = 6
(3;4): -6 + 8 > 1; ∆34
= -6 + 8 - 1 = 1
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (1;5): 1. Для цього в перспективну клітку (1;5) поставимо знак «+», а в інших вершинах багатокутника чергуються знаки «-», «+», «-». Цикл наведено в таблиці.
Тепер необхідно перемістити продукцію в межах побудованого циклу. З вантажів хij
що стоять в мінусових клітинах, вибираємо найменше, тобто у = min (1, 3) = 60. Додаємо 60 до обсягів вантажів, що стоять в плюсових клітинах і віднімаємо 60 з хij
, що стоять в мінусових клітинах. В результаті отримаємо новий опорний план.
Для цього у порожню клітинку (1;5) переносимо менше з чисел хij
, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij
додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».
Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n
+ m
– 1).
Отже, другий опорний план транспортної задачі матиме такий вигляд:
Ai
Bj
ui
b1
= 110
b2
= 80
b3
= 100
b4
=90
b5
=70
b6
=250
а1
= 250
1
110
4
[-] 80
7
9
1
[+] 60
0
u1
= 0
а2
= 300
2
3
1
100
2
90
4
[-] 10
0
[+] 100
u2
= 3
а3
= 150
2
1
[+]
3
1
4
0
[-] 150
u3
= 3
vj
v1
= 1
v2
= 4
v3
= -2
v4
= -1
v5
= 1
v6
= -3
Перевіримо оптимальність опорного плану. Знайдемо потенціали ui
, vi
. по зайнятих клітинам таблиці, в яких ui
+ vi
= cij
, вважаючи, що u1
= 0.
Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui
+ vi
>cij