Optprob/Прокладка водопровода в селе — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- spex01-pg-91 --> {{checked|}} {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}} File:Прокладка водопровода в селе_2023-12-24_01…») |
(нет различий)
|
Версия 22:31, 23 декабря 2023
Муниципалитет хочет разработать способ доставки воды из муниципального водохранилища «D» в 7 сельских домов, не обязательно напрямую, с наименьшими возможными затратами.
Возможные варианты трубопроводов между водохранилищем и домами с соответствующими затратами в денежных единицах приведены в следующей таблице (приведен только верхний треугольник симметричной матрицы):
| . | D | C1 | C2 | C3 | C4 | C5 | C6 | C7 | |
| D | x | 10 | 12 | 14 | x | x | x | x | |
| C1 | x | x | x | x | 3 | x | x | x | |
| C2 | x | x | x | x | 2 | 4 | x | x | |
| C3 | x | x | x | x | x | 3 | x | x | |
| C4 | x | x | x | x | x | 3 | 5 | 6 | |
| C5 | x | x | x | x | x | x | 7 | 5 | |
| C6 | x | x | x | x | x | x | x | 4 | |
| C7 | x | x | x | x | x | x | x | x |
Например, проезд между 2-м и 5-м домами стоит 4 денежные единицы.
Рассчитайте все возможные способы соединения так, чтобы общая стоимость была минимальной. (визуализируйте графы).