Часть полного текста документа: Завдання 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 Тому від нього необхідно перейти до другого плану, змінивши співвідношення заповнених і порожніх клітинок таблиці. ............ |
