Hardprob/Minimum Facility Location — различия между версиями

Версия 18:00, 17 апреля 2023

Полный граф G=(V,E), стоимости перемещения , с неравенством треугольника, — места, где можно построить место обслуживания (туалеты, магазины, заправки), — стоимость этого строительства, — потребности в разных местах.
Найти места для строительства мест обслуживания, .
Минимизировать

@@ Строка 1: / Строка 1: @@
 <!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
-* Полный граф <em>G=(V,E)</em>, стоимости перемещения <m>с(v_i,v_j)\in N</m>, с неравенством треугольника, <m>F⊆ V</m> — места, где можно построить место обслуживания (туалеты, магазины, заправки), <m>∀v\in F, f(v)>0</m> — стоимость этого строительства, <m>∀v\in V, d(v)>0</m> — потребности в разных местах.
+* Полный граф <em>G=(V,E)</em>, стоимости перемещения <m>с(v_i,v_j)∈  N</m>, с неравенством треугольника, <m>F⊆ V</m> — места, где можно построить место обслуживания (туалеты, магазины, заправки), <m>∀v∈  F, f(v)>0</m> — стоимость этого строительства, <m>∀v∈  V, d(v)>0</m> — потребности в разных местах.
 * Найти места для строительства мест обслуживания, <m>F'⊆ F</m>.
 * Минимизировать
 <m>
-\sum_{v\in F'} f(v)+\sum_{u\in F'}\sum_{v\in V} d(v)\cdot c(u,v) → \min
+\sum_{v∈  F'} f(v)+\sum_{u∈  F'}\sum_{v∈  V} d(v)\cdot c(u,v) → \min
 </m>