Математичне програмування (стр. 1 из 3)
Завдання 1
Зібраний врожай зерна трьох сільськогосподарських артілей повинен бути перевезений на три елеватори, а саме: елеватор А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 |
Розпочинаємо будувати математичну модель даної задачі:
Економічний зміст записаних обмежень полягає в тому, що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна записати відносно замовників: вантаж, що може надходити до споживача від чотирьох баз, має повністю задовольняти його попит. Математично це записується так:
Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:
minZ=12,5x11+24x12+18,4x13+28,3x21+14,5x22+25,7x23+15,7x31+20,6x32+16,3x33.
Загалом математична модель сформульованої задачі має вигляд:
minZ=12,5x11+24x12+18,4x13+28,3x21+14,5x22+25,7x23+15,7x31+20,6x32+16,3x33.
за умов:
Запишемо умови задачі у вигляді транспортної таблиці та складемо її перший опорний план у цій таблиці методом «північно-західного кута».
| 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): 21.9 + 12.5 > 15.7; ∆31 = 21.9 + 12.5 - 15.7 = 18.7
Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. Вибираємо максимальну оцінку вільної клітини (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): 15.8 + 13.1 > 25.7; ∆23 = 15.8 + 13.1 - 25.7 = 3.2
Вибираємо максимальну оцінку вільної клітини (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.
Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний.
Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:
F(x) = 12.5*80 + 14.5*90 + 15.7*20 + 16.3*80 = 3923
За оптимальним планом перевезень загальна вартість перевезень всієї продукції є найменшою і становить 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
Отриманий базис називається штучним, а метод рішення називається методом штучного базису.
Причому штучні змінні не мають відношення до змісту поставленого завдання, однак вони дозволяють побудувати стартову точку, а процес оптимізації змушує ці змінні приймати нульові значення та забезпечити допустимість оптимального рішення.