Завдання 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
розв'язок
Побудова математичної Моделі . Нехай x ij - кількість продукції, Що перевозитися з и -го пункту виробництва до 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
Розпочінаємо будуваті математичних модель даної Задачі:
Економічний Зміст записаних обмежень полягає в тому, Що весь вантаж потрібно перевезти по пунктах повністю.
Аналогічні обмеження можна запісаті відносно замовніків: вантаж, Що Може надходіті до Споживача від чотірьох баз, має повністю задовольняти Його Попит. Математичних Це запісується так:
Загальні витрати, пов'язані з Транспортування продукції, визначаються Як торба добутків обсягів перевезеної продукції на вартості Транспортування од. продукції до відповідного замовника и за умів Задачі мают буті мінімальнімі. Тому формально Це можна запісаті так:
загаль математична модель сформульованої Задачі має Вигляд:
за умов:
Запішемо Умови Задачі у вігляді транспортної табліці та складемо її Перший опорний план у Цій табліці методом В«Північно-західного кутаВ».
A i
B j
u i
b 1 = 100
b 2 = 80
b 3 = 90
а 1 = 80
12,5
80
24,0
18,4
u 1 = 0
а 2 = 90
28,3
[-] 20
14,5
[+] 70
25,7
u 2 = 15,8
а 3 = 100
15,7
[+]
20,6
[-] 20
16,3
80
u 3 = 21,9
v j
v 1 = 12,5
v 2 = -1,3
v 3 = -5,6
В результаті ОТРИМАНО Перший опорний план, Який є допустимим, оскількі ВСІ вантажі з баз вівезені, потреба магазинів задоволена, а план відповідає сістемі обмежень транспортної Задачі.
Підрахуємо число зайнятості клітін табліці, їх 5, а має буті m + n-1 = 5. Отже, опорний план є не вироджених.
Перевірімо оптімальність опорного плану. Знайдемо потенціалі u i , v i . по зайнятості клітінам табліці, в якіх u i + V i = c ij , вважаючі, Що u 1 = 0:
u 1 = 0, u 2 = 15,8, u 3 = 21,9 , v 1 = 12,5, v 2 = -1,3, v 3 = -5,6. Ці Значення потенціалів Першого опорного плану запісуємо у транспортних таблиці.
Потім згідно з алгоритмом методу потенціалів перевіряємо виконан Другої Умови оптімальності u i + v j ≤ c ij (для порожніх клітінок табліці).
Опорний план не є оптимальним, ТОМУ ЩО існують оцінкі вільніх клітін для якіх u i + v i > c ij
(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).
Отже, інші опорні план транспортної Задачі матіме такий Вигляд:
A i
B j
u i
|
