Optprob/Прокладка водопровода в селе — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «<!-- spex01-pg-91 --> {{checked|}} {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}} File:Прокладка водопровода в селе_2023-12-24_01…») |
StasFomin (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
<!-- spex01-pg-91 --> | <!-- spex01-pg-91 --> | ||
{{checked|}} | {{checked|}} | ||
| + | {{Reserve-task|[[Участник:StasFomin|StasFomin]] 04:06, 8 октября 2024 (UTC)}} | ||
{{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}} | {{Cat4Term2|{{FULLPAGENAME}}|OptimizationProblems}} | ||
Версия 04:06, 8 октября 2024
Задача зарезервирована: StasFomin 04:06, 8 октября 2024 (UTC)
Муниципалитет хочет разработать способ доставки воды из муниципального водохранилища «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 денежные единицы.
Рассчитайте все возможные способы соединения так, чтобы общая стоимость была минимальной. (визуализируйте графы).