Problema cu 1 centru

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 martie 2017; verificarea necesită 1 editare .

Problema cu 1 centru sau problema de plasare a obiectelor minimax este o problemă clasică de optimizare combinatorie , o problemă în disciplina cercetării operaționale , este un caz special al problemei de plasare a obiectelor . În cel mai general caz, se formulează după cum urmează:

Sunt date un set de locații ale consumatorilor, un spațiu de locații posibile ale obiectelor (producție sau serviciu) și o funcție a costului de transport din orice punct de locație posibilă până la punctul de consum. Este necesar să se găsească locația optimă a obiectelor, minimizând costul maxim de livrare de la obiect la consumator.

Un caz special simplu în care locurile de cazare și punctele de consum sunt într-un avion, iar costul de livrare este distanța euclidiană ( problema de plasare euclidiană minimax plană, problema planului euclidian cu 1 centru ) este, de asemenea, cunoscut ca problema cel mai mic cerc . Generalizarea sa la spații euclidiene de dimensiuni superioare este cunoscută ca problema sferei cu cea mai mică limită . Într-o generalizare ulterioară ( problema de locație euclidiană ponderată ), ponderile sunt atribuite punctelor de consum, iar costul transportului este suma distanțelor înmulțită cu ponderile corespunzătoare. Un alt caz special este problema celei mai apropiate linii , când intrarea problemei este șirul , iar distanța este măsurată ca distanța Hamming .

Există numeroase cazuri speciale ale problemei, în funcție atât de alegerea locației punctelor de consum și a obiectelor de producție (sau de serviciu), cât și de alegerea unei funcții care calculează distanța.

Problema cu 1 centru în termenii teoriei grafurilor

Formularea unei astfel de variante a problemei constă în faptul că este dat un grafic , precum și o funcție de cost și este necesar să se găsească o mulțime astfel încât să fie minimă, i.e. o mulțime astfel încât costul maxim al unei căi de la vârful cel mai apropiat de orice vârf să rămână minim. De asemenea, problema poate fi completată de funcția de cost de vârf, iar apoi raza acesteia va fi definită ca . $G=(V,E)$ $k\in {\mathbb {N}}$ $c\colon E\la \mathbb {Q} ^{+)$ $Z\subset V$ $\operatorname {rad} (Z)=\max _{v\in V}\min _{z\in Z}c(z,v)$ $Z$ $Z$ $w\colon V\la \mathbb {Q} ^{+)$ $\operatorname {rad} (Z)=\max _{v\in V}[w(v)\cdot \min _{z\in Z}c(z,v)]$

Ideea unei soluții aproximative a problemei este de a căuta printr-un algoritm lacom o rază fixă . Atâta timp cât există vârfuri care nu sunt acoperite de , trebuie să alegeți cu lăcomie un vârf și să luați în considerare toate celelalte vârfuri disponibile . Algoritmul se repetă pentru diferite valori ale . Mai jos este o descriere a metodei într-o formă formală: $Z$ $R$ $Z$ $z$ $2R$ $R$

Instalați și . $Z=\emptyset$ $U=V$
pa : $U\neq \emptyset$
1. $z=\operatorname {argmax} \{w(u)\mid u\in U\)$ .
2. $Z=Z\cup\{z\)$ .
3. $U=U\setminus \{v\in U\mid w(v)\cdot \operatorname {dist} (v,z)\leqslant 2R\)$ .
Scoateți afară . $Z$

Să fie soluția optimă pentru . În cazul în care , algoritmul lacom va returna un set astfel încât . Pe baza acestui lucru, definim și observăm că funcția nu este monotonă . În continuare, notăm raza , cu ajutorul căreia un singur vârf în poate acoperi toate vârfurile graficului, i.e. , a . $R^{*}$ $Z^*$ $R\geqslant R^{*}$ $Z$ $|Z|\leqslant |Z^{*}|$ $f(R)=|\operatorname {GreedyCenter} (G,c,w,R)|$ $f$ $R'=\max _{v\in V}[w(v)\cdot \sum _{e\in E}c(e)]$ $Z$ $f(R')=1$ $f(0)=|V|=n$

Lema. Pentru orice grafic cu o mulțime și o rază optime , inegalitatea este valabilă pentru toate . $G=(V,E)$ $Z^*$ $R^{*}=\operatorname {rad} (Z^{*})$ $f(R)\leqslant k$ $R\geqslant R^{*}$

Dovada. Fie și vârful selectat în ciclul algoritmului . Atunci inegalitatea reală este: $V_{i}=\{v\in V\mid w(v)\cdot \operatorname {dist} (v,z_{i})\leqslant R^{*}\)$ $z\in V_{i)$ $\operatorname {GreedyCenter}$

{\begin{aligned}w(v)\cdot \operatorname {dist} (v,z)&\leqslant w(v)\cdot (\operatorname {dist} (v,v_{i})+\ operatorname {dist} (v_{i},z))\\&\leqslant w(v)\cdot \operatorname {dist} (v,v_{i})+w(z)\cdot \operatorname {dist} ( v_{i},z)\\&\leqslant 2\cdot R^{*}\leqslant 2\cdot R\end{aligned}}

Toate vârfurile din vor fi eliminate la sfârșitul iterației, ceea ce înseamnă că bucla se va încheia într-un maxim de iterații și, prin urmare, . $V_i$ $k=|Z^{*}|$ $|Z|\leqslant k$

Din lemă rezultă că algoritmul greedy poate fi rulat până când setul rezultat devine mai mic decât cel necesar , folosind matricea distanțelor pentru a calcula razele . Astfel, complexitatea generală de timp a algoritmului este , iar factorul de aproximare este . $Z$ $k$ $O(n^{4})$ $2$

Rezolvabilitate

Cu condiția ca clasele P și NP să nu fie egale, pentru oricare nu există un algoritm polinomial cu factor de aproximare . Dovada acestei afirmații se reduce la o reducere la problema mulțimii dominante : Să fie dată ca intrare la algoritmul care rezolvă problema mulțimii dominante. De asemenea, lăsați pentru toate marginile . Apoi conține un set dominant de mărime dacă mulțimea conține vârfuri și raza ( ) este egală cu . Dacă ar exista un algoritm de -aproximare cu , atunci ar găsi o mulțime dominantă cu exact același factor de aproximare, ceea ce este imposibil. $r<2$ $r$ $(G,k)$ $c(e)=1$ $e\in E(G)$ $G$ $k$ $Z$ $k$ $\operatorname {rad} (Z)$ $unu$ $r$ ${\mathcal {A}}$ $r<2$ ${\mathcal {A}}(G,1,k,c)$

Vezi și

Problema plasării obiectelor cu minimizarea sumei distanțelor (aka „Problema 1-mediană”) cu mediana mulțimii de puncte ca caz special
Problema amplasării maxime a obiectelor (pe cât posibil, plasarea obiectelor dăunătoare)
Problema centrului k
Problema k-mediană

Note

Literatură

Nimrod Megiddo. Problema euclidiană ponderată cu un centru // Matematica cercetării operaționale. — Hanovra: Institutul pentru Cercetare Operațională și Științe de Management. - T. 8 , nr. 4 . — S. 498–504 . - doi : 10.1287/moor.8.4.498 .
Abdelaziz Fault. O problemă cu 1 centru în avion cu puncte de cerere distribuite uniform // Operations Research Letters. - Elsevier, 2006. - T. 34 , nr. 3 . — S. 264–268 . - doi : 10.1016/j.orl.2005.04.011 .
R. Chandrasekaran. Problema euclidiană ponderată cu un centru // Scrisori de cercetare operațională. - Elsevier, iulie 1982. - Vol. 1 , nr. 3 . — S. 111–112 . - doi : 10.1016/0167-6377(82)90009-8 .
M. Colebrook, S. Alonso Gutierrez, J. Sicilia. Un nou algoritm pentru problema nedorită a unui centru pe rețele // Journal of the Operational Research Society . - Palgrave Macmillan Journals, 2002. - V. 53 , nr. 12 . - S. 1357-1366 . doi : 10.1057 / palgrave.jors.2601468 . — .
Rainer E. Burkard, Helidon Dollani. O notă despre problema robustă a unui singur centru asupra copacilor // Analele cercetării operaționale. - Kluwer Academic Publishers, 2002. - T. 110 , nr. 1-4 . — p. 69–82 . — ISSN 1572-9338 . - doi : 10.1023/A:1020711416254 .