सुविधा स्थान की समस्या: Difference between revisions

Revision as of 22:34, 9 August 2023

सुविधा स्थान समस्याओं का अध्ययन (एफएलपी), जिसे स्थान विश्लेषण के रूप में भी जाना जाता है, संचालन अनुसंधान और कम्प्यूटेशनल ज्यामिति की एक शाखा है जो आवास के पास खतरनाक सामग्री रखने से बचने और प्रतिस्पर्धियों के कारकों पर विचार करते हुए परिवहन लागत को कम करने के लिए सुविधाओं के इष्टतम स्थान से संबंधित है। तकनीकें क्लस्टर विश्लेषण पर भी लागू होती हैं।

न्यूनतम सुविधा स्थान

एक सरल सुविधा स्थान समस्या वेबर समस्या है, जिसमें एक एकल सुविधा को रखा जाना है, जिसमें एकमात्र अनुकूलन मानदंड बिंदु साइटों के दिए गए सेट से दूरियों के भारित योग को कम करना है। इस अनुशासन में विचार की जाने वाली अधिक जटिल समस्याओं में कई सुविधाओं की नियुक्ति, सुविधाओं के स्थानों पर बाधाएं और अधिक जटिल अनुकूलन मानदंड सम्मिलित हैं।

बुनियादी सूत्रीकरण में, सुविधा स्थान की समस्या में संभावित सुविधा साइटों एल का एक सेट सम्मिलित होता है जहां एक सुविधा खोली जा सकती है, और मांग बिंदु D का एक सेट होता है जिसे सेवा प्रदान की जानी चाहिए। लक्ष्य खोलने के लिए सुविधाओं का एक उपसमूह F चुनना है, प्रत्येक मांग बिंदु से उसकी निकटतम सुविधा तक की दूरी के योग को कम करना है, साथ ही सुविधाओं की प्रारंभिक लागत का योग भी कम करना है।

सामान्य ग्राफ़ पर सुविधा स्थान की समस्या को (उदाहरण के लिए) सेट कवर समस्या से कम करके, इष्टतम तरीके से हल करना एनपी-कठिन है। सुविधा स्थान समस्या और इसके कई प्रकारों के लिए कई सन्निकटन एल्गोरिदम विकसित किए गए हैं।

ग्राहकों और साइटों के बीच दूरियों के सेट पर धारणाओं के बिना (विशेष रूप से, यह माने बिना कि दूरियां त्रिकोण असमानता को संतुष्ट करती हैं), समस्या को 'गैर-मीट्रिक सुविधा स्थान' के रूप में जाना जाता है और इसे एक कारक O(log n) के भीतर अनुमानित किया जा सकता है ).^[1] सेट कवर समस्या से सन्निकटन-संरक्षण कमी के माध्यम से, यह कारक तंग (टाइट) है।

यदि हम मानते हैं कि ग्राहकों और साइटों के बीच की दूरी अप्रत्यक्ष है और त्रिकोण असमानता को संतुष्ट करती है, तो हम मीट्रिक सुविधा स्थान (एमएफएल) समस्या के बारे में बात कर रहे हैं। एमएफएल अभी भी एनपी-हार्ड है और 1.463 से बेहतर कारक के भीतर अनुमान लगाना कठिन है।^[2] वर्तमान में सबसे अच्छा ज्ञात सन्निकटन एल्गोरिथ्म 1.488 का सन्निकटन अनुपात प्राप्त करता है।^[3]

मिनीमैक्स सुविधा स्थान

मिनिमैक्स सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों की अधिकतम दूरी को कम करती है, जहां एक बिंदु से साइटों की दूरी बिंदु से उसके निकटतम साइट की दूरी है। एक औपचारिक परिभाषा इस प्रकार है: एक बिंदु सेट P ⊂ ℝ^d दिया गया है, एक बिंदु सेट 'S' ⊂ ℝ^d ख, |'S'| = k, ताकि (अधिकतम) max_p ∈ P(min_q ∈ S(d(p, q)) ) को न्यूनतम किया गया है।

k = 1 के लिए यूक्लिडियन मीट्रिक के स्थिति में, इसे सबसे छोटी संलग्न क्षेत्र समस्या या 1-केंद्र समस्या के रूप में जाना जाता है। इसका अध्ययन कम से कम 1860 के वर्ष का है। अधिक विवरण के लिए सबसे छोटा घेरने वाला वृत्त और सीमा क्षेत्र देखें।

एनपी कठोरता

यह सिद्ध हो चुका है कि वर्टेक्स के-सेंटर समस्या|के-सेंटर समस्या का सटीक समाधान एनपी कठिन है।^[4] ^[5] ^[6] त्रुटि छोटी होने पर समस्या का अनुमान भी एनपी कठिन पाया गया। सन्निकटन एल्गोरिथ्म में त्रुटि स्तर को सन्निकटन कारक के रूप में मापा जाता है, जिसे सन्निकटन और इष्टतम के बीच के अनुपात के रूप में परिभाषित किया जाता है। यह सिद्ध हो गया है कि जब सन्निकटन कारक 1.822 (आयाम = 2) से कम है तो के-केंद्र समस्या सन्निकटन एनपी कठिन है।^[7] या 2 (आयाम > 2).^[6]

एल्गोरिदम

सटीक सॉल्वर

इस समस्या का सटीक समाधान निकालने के लिए एल्गोरिदम मौजूद हैं। एक सटीक सॉल्वर समय में चलता है $n^{O({\sqrt {k}})}$ .^[8]^[9]

1 + ε सन्निकटन

1+ε सन्निकटन का तात्पर्य सन्निकटन कारक के साथ एक समाधान ढूंढना है जो 1+ε से अधिक न हो। यह सन्निकटन एनपी कठिन है क्योंकि ε मनमाना है। कोर सेट अवधारणा पर आधारित एक दृष्टिकोण निष्पादन जटिलता के साथ प्रस्तावित है $O(2^{O(k\log k/\varepsilon ^{2})}dn)$ .^[10] विकल्प के रूप में, कोर सेट पर आधारित एक अन्य एल्गोरिदम भी उपलब्ध है। यह अंदर चलता है $O(k^{n})$ .^[11] लेखक का दावा है कि चलने का समय सबसे खराब स्थिति से बहुत कम है और इस प्रकार k छोटा होने पर कुछ समस्याओं को हल करना संभव है (कहें k <5)।

'सबसे दूर बिंदु क्लस्टरिंग'

समस्या की कठोरता के लिए, सटीक समाधान या सटीक अनुमान प्राप्त करना अव्यावहारिक है। इसके बजाय, बड़े k मामलों के लिए कारक = 2 के साथ एक सन्निकटन का व्यापक रूप से उपयोग किया जाता है। सन्निकटन को सबसे दूर-बिंदु क्लस्टरिंग (फार्थेस्ट -पॉइंट) (एफपीसी) एल्गोरिदम, या सबसे दूर-पहले ट्रैवर्सल के रूप में जाना जाता है।^[6]एल्गोरिथ्म काफी सरल है: सेट से किसी भी बिंदु को एक केंद्र के रूप में चुनें; किसी अन्य केंद्र के रूप में शेष सेट से सबसे दूर बिंदु की खोज करें; प्रक्रिया को तब तक दोहराएँ जब तक कि k केंद्र न मिल जाएँ।

यह देखना आसान है कि यह एल्गोरिदम रैखिक समय में चलता है। चूंकि 2 से कम कारक के साथ सन्निकटन एनपी कठिन साबित हुआ है, एफपीसी को सबसे अच्छा सन्निकटन माना जाता था जिसे कोई भी पा सकता है।

निष्पादन के प्रदर्शन के अनुसार, समय जटिलता को बाद में बॉक्स अपघटन तकनीक के साथ ओ n log k) में सुधार किया गया है।^[7]

मैक्समिन सुविधा स्थान

मैक्समिन (अधिकतम) सुविधा स्थान या अप्रिय सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों से न्यूनतम दूरी को अधिकतम कर दे। यूक्लिडियन मीट्रिक के स्थिति में, इसे सबसे बड़ी खाली क्षेत्र समस्या के रूप में जाना जाता है। समतलीय मामला (सबसे बड़ी खाली वृत्त समस्या) को समय जटिलता Θ(n log n) में हल किया जा सकता है।^[12]^[13]

पूर्णांक (इंटीजर) प्रोग्रामिंग फॉर्मूलेशन

सुविधा स्थान की समस्याओं को प्रायः इंटीजर प्रोग्रामिंग के रूप में हल किया जाता है। इस संदर्भ में, सुविधा स्थान की समस्याएं प्रायः इस प्रकार सामने आती हैं: मान लीजिए कि हैं $n$ सुविधाएं और $m$ ग्राहक. हम इनमें से (1) किसे चुनना चाहते हैं $n$ खोलने के लिए सुविधाएं, और (2) आपूर्ति के लिए कौन सी (खुली) सुविधाओं का उपयोग करना है $m$ ग्राहकों को, न्यूनतम लागत पर कुछ निश्चित मांग को पूरा करने के लिए। हम निम्नलिखित संकेतन प्रस्तुत करते हैं: मान लीजिए कि $f_{i}$ सुविधा खोलने की (निश्चित) लागत को निरूपित करें $i$ , के लिए $i=1,\dots ,n$ . होने देना $c_{ij}$ किसी उत्पाद को सुविधा से शिप करने की लागत को दर्शाता है $i$ ग्राहक को $j$ के लिए $i=1,\dots ,n$ और $j=1,\dots ,m$ . मान लीजिए कि $d_{j}$ ग्राहक की मांग को निरूपित करें $j$ के लिए $j=1,\dots ,m$ . इसके अलावा मान लीजिए कि प्रत्येक सुविधा का अधिकतम आउटपुट है। मान लीजिए कि $u_{i}$ सुविधा द्वारा उत्पादित किए जा सकने वाले उत्पाद की अधिकतम मात्रा को निरूपित करें $i$ , अर्थात् मान लीजिए कि $u_{i}$ सुविधा की क्षमता को निरूपित करें $i$ . इस खंड का शेष भाग इस प्रकार है^[14]

क्षमतायुक्त सुविधा स्थान

हमारे प्रारंभिक सूत्रीकरण में, एक बाइनरी वैरिएबल का परिचय दें $x_{i}$ के लिए $i=1,\dots ,n$ , जहाँ $x_{i}=1$ यदि सुविधा $i$ खुला है, और $x_{i}=0$ अन्यथा। आगे वेरिएबल का परिचय दें $y_{ij}$ के लिए $i=1,\dots ,n$ और $j=1,\dots ,m$ जो मांग के अंश को दर्शाता है $d_{j}$ सुविधा द्वारा भरा गया $i$ . तथाकथित कैपेसिटेटेड सुविधा स्थान समस्या तब दी जाती है

{\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}y_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}y_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}d_{j}y_{ij}\leqslant u_{i}x_{i}{\text{ for all }}i=1\dots ,n\\&y_{ij}\geqslant 0{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}

ध्यान दें कि बाधाओं का दूसरा सेट यह सुनिश्चित करता है कि यदि

x_{i}=0

, यानी सुविधा

i

तो फिर, खुला नहीं है

y_{ij}=0

सभी के लिए

j

यानी सुविधा से किसी भी ग्राहक की कोई डिमांड नहीं भरी जा सकेगी

i

.

अनकैपेसिटीड सुविधा स्थान की समस्या

उपरोक्त कैपेसिटेटेड सुविधा स्थान समस्या का एक सामान्य मामला तब होता है जब $u_{i}=+\infty$ सभी के लिए $i=1,\dots ,n$ . इस स्थिति में, ग्राहक की सभी मांगों को पूरा करना हमेशा इष्टतम होता है $j$ निकटतम खुली सुविधा से. इस वजह से, हम सतत चरों को प्रतिस्थापित कर सकते हैं $y_{ij}$ ऊपर से बाइनरी डेटा के साथ $z_{ij}$ , जहाँ $z_{ij}=1$ यदि ग्राहक $j$ सुविधा द्वारा आपूर्ति की जाती है $i$ , और $z_{ij}=0$ अन्यथा। अनकैपेसिटीड सुविधा स्थान की समस्या तब दी जाती है

{\begin{array}{rl}\min &\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{m}c_{ij}d_{j}z_{ij}+\sum _{i=1}^{n}f_{i}x_{i}\\{\text{s.t.}}&\displaystyle \sum _{i=1}^{n}z_{ij}=1{\text{ for all }}j=1,\dots ,m\\&\displaystyle \sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1\dots ,n\\&z_{ij}\in \{0,1\}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m\\&x_{i}\in \{0,1\}{\text{ for all }}i=1,\dots ,n\end{array}}

जहाँ

M

उपयुक्त रूप से बड़े होने के लिए चुना गया एक स्थिरांक है। का चुनाव

M

गणना परिणामों को प्रभावित कर सकता है - इस उदाहरण में सबसे अच्छा विकल्प स्पष्ट है: लेना

M=m

. तो अगर

x_{i}=1

, का कोई भी विकल्प

z_{ij}

बाधाओं के दूसरे सेट को संतुष्ट करेगा।

अप्रतिबंधित सुविधा स्थान समस्या के लिए एक अन्य सूत्रीकरण संभावना क्षमता बाधाओ को अलग करना है (बड़ा- $M$ प्रतिबंध)। यानी बाधाओं को बदलें है

\sum _{j=1}^{m}z_{ij}\leqslant Mx_{i}{\text{ for all }}i=1,\dots ,n

बाधाओं के साथ

z_{ij}\leqslant x_{i}{\text{ for all }}i=1,\dots ,n{\text{ and }}j=1,\dots ,m

व्यवहार में, यह नया फॉर्मूलेशन काफी बेहतर प्रदर्शन करता है, इस अर्थ में कि इसमें पहले फॉर्मूलेशन की तुलना में अधिक सख्त रैखिक प्रोग्रामिंग छूट है।^[14]ध्यान दें कि नई बाधाओं को एक साथ जोड़ने पर मूल बड़ा परिणाम प्राप्त होता है-

M

प्रतिबंध। कैपेसिटेटेड स्थिति में, ये फॉर्मूलेशन समकक्ष नहीं हैं। असंबद्ध सुविधा स्थान समस्या के बारे में अधिक जानकारी ''असतत स्थान सिद्धांत'' के अध्याय 3 में पाई जा सकती है।^[15]

अनुप्रयोग

स्वास्थ्य देखभाल

स्वास्थ्य देखभाल में, गलत सुविधा स्थान निर्णयों का साधारण लागत और सेवा मेट्रिक्स से परे समुदाय पर गंभीर प्रभाव पड़ता है; उदाहरण के लिए, हार्ड-टू-एक्सेस (कठिन पहुंच वाली) स्वास्थ्य सुविधाएं रुग्णता और मृत्यु दर में वृद्धि से जुड़ी होने की संभावना है। इस दृष्टिकोण से, स्वास्थ्य देखभाल के लिए सुविधा स्थान मॉडलिंग अन्य क्षेत्रों के लिए समान मॉडलिंग की तुलना में अधिक महत्वपूर्ण है।^[16]

ठोस अपशिष्ट प्रबंधन

बढ़ते अपशिष्ट उत्पादन और अपशिष्ट प्रबंधन से जुड़ी उच्च लागत के कारण नगरपालिका ठोस अपशिष्ट प्रबंधन अभी भी विकासशील देशों के लिए एक चुनौती बनी हुई है। किसी सुविधा स्थान की समस्या के निर्माण और सटीक समाधान के माध्यम से अपशिष्ट निपटान के लिए लैंडफिल के स्थान को अनुकूलित करना संभव है।^[17]

क्लस्टरिंग

क्लस्टर विश्लेषण समस्याओं के एक विशेष उपसमूह को सुविधा स्थान समस्याओं के रूप में देखा जा सकता है। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, उद्देश्य विभाजन करना है $n$ डेटा बिंदुओं (एक सामान्य मीट्रिक स्थान के तत्व) को समतुल्य वर्गों में - जिन्हें प्रायः रंग कहा जाता है - जैसे कि एक ही रंग के बिंदु एक दूसरे के निकट हों (समान रूप से, जैसे कि विभिन्न रंगों के बिंदु एक दूसरे से दूर हों)।^[18]

यह देखने के लिए कि कोई सेंट्रोइड-आधारित क्लस्टरिंग समस्या को (मीट्रिक) सुविधा स्थान समस्या के रूप में कैसे देख सकता है (परिवर्तन या कम करें पढ़ें), पूर्व में प्रत्येक डेटा बिंदु को बाद में मांग बिंदु (डिमांड पॉइंट) के रूप में देखें। मान लीजिए कि क्लस्टर किया जाने वाला डेटा मीट्रिक स्पेस के तत्व हैं $M$ (उदा. मान लीजिए कि $M$ होना $p$ कुछ निश्चित के लिए -आयामी यूक्लिडियन स्थान $p$ ). हम जिस सुविधा स्थान की समस्या का निर्माण कर रहे हैं, उसमें हम सुविधाओं को इस मीट्रिक स्थान के भीतर किसी भी बिंदु पर रखने की अनुमति देते हैं $M$ ; यह अनुमत सुविधा स्थानों के सेट को परिभाषित करता है $L$ . हम लागतों को परिभाषित करते हैं $c_{\ell ,d}$ स्थान-मांग बिंदु जोड़े के बीच जोड़ीवार दूरी होना (उदाहरण के लिए, मीट्रिक के-केंद्र देखें)। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, डेटा को विभाजित किया जाता है $k$ समतुल्य वर्ग (अर्थात रंग) जिनमें से प्रत्येक में एक केन्द्रक होता है। आइए देखें कि हमारी निर्मित सुविधा स्थान समस्या का समाधान भी इस तरह के विभाजन को कैसे प्राप्त करता है। एक व्यवहार्य समाधान एक गैर-रिक्त उपसमुच्चय है $L'\subseteq L$ का $k$ स्थान. हमारी सुविधा स्थान समस्या में इन स्थानों का एक सेट सम्मिलित है $k$ हमारी सेंट्रोइड-आधारित क्लस्टरिंग समस्या में सेंट्रोइड्स। अब, प्रत्येक मांग बिंदु निर्दिष्ट करें $d$ स्थान के लिए $\ell ^{*}$ जो इसकी सर्विसिंग-लागत को कम करता है; अर्थात्, डेटा बिंदु निर्दिष्ट करें $d$ केन्द्रक को $\ell ^{*}:=\mathrm {arg\,min} _{\ell \in L}\{c_{\ell ,d}\}$ (मनमाने ढंग से संबंध तोड़ें)। यह विभाजन को प्राप्त करता है बशर्ते कि सुविधा स्थान की समस्या की लागत हो $c_{\ell ,d}$ परिभाषित किया गया है कि वे सेंट्रोइड-आधारित क्लस्टरिंग समस्या के दूरी फ़ंक्शन की छवियां हैं।

लोकप्रिय एल्गोरिदम पाठ्यपुस्तक एल्गोरिदम डिज़ाइन ^[19] संबंधित समस्या-विवरण और एक सन्निकटन एल्गोरिदम प्रदान करता है। लेखक मीट्रिक सुविधा स्थान समस्या (अर्थात सेंट्रोइड-आधारित क्लस्टरिंग समस्या या मीट्रिक) का उल्लेख करते हैं $k$ -केंद्र समस्या) केंद्र चयन समस्या के रूप में, जिससे समानार्थक शब्दों की सूची बढ़ती जा रही है।

इसके अलावा, देखें कि सुविधा स्थान समस्या की हमारी उपरोक्त परिभाषा में उद्देश्य कार्य करता है $f$ सामान्य है. के विशिष्ट विकल्प $f$ सुविधा स्थान समस्या के विभिन्न प्रकार उत्पन्न होते हैं, और इसलिए सेंट्रोइड-आधारित क्लस्टरिंग समस्या के विभिन्न प्रकार होते हैं। उदाहरण के लिए, कोई व्यक्ति प्रत्येक स्थान से उसके प्रत्येक निर्दिष्ट मांग बिंदु (ए ला वेबर समस्या) की दूरी के योग को कम करने का विकल्प चुन सकता है, या कोई ऐसी सभी दूरियों को अधिकतम करने का विकल्प चुन सकता है (ए ला 1-केंद्र समस्या) ).

यह भी देखें

संदर्भ

↑ Hochbaum, D. S. (1982). "निश्चित लागत माध्यिका समस्या के लिए अनुमान". Mathematical Programming. 22: 148–162. doi:10.1007/BF01581035. S2CID 3451944.
↑ Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: Improved Facility Location Algorithms". Journal of Algorithms. 31: 228–248. CiteSeerX 10.1.1.47.2033. doi:10.1006/jagm.1998.0993. S2CID 5363214.
↑ Li, S. (2011). "A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem". ऑटोमेटा, भाषाएँ और प्रोग्रामिंग. LNCS. Vol. 6756. pp. 77–88. CiteSeerX 10.1.1.225.6387. doi:10.1007/978-3-642-22012-8_5. ISBN 978-3-642-22011-1.
↑ Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L. (1981), "Optimal packing and covering in the plane are NP-complete", Information Processing Letters, 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3.
↑ Megiddo, Nimrod; Tamir, Arie (1982), "On the complexity of locating linear facilities in the plane" (PDF), Operations Research Letters, 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6.
↑ ^6.0 ^6.1 ^6.2 Gonzalez, Teofilo (1985), "Clustering to minimize the maximum intercluster distance", Theoretical Computer Science, 38: 293–306, doi:10.1016/0304-3975(85)90224-5.
↑ ^7.0 ^7.1 Feder, Tomás; Greene, Daniel (1988), "Optimal algorithms for approximate clustering", Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing: 434–444, doi:10.1145/62212.62255, ISBN 0897912640, S2CID 658151
↑ HWang, R. Z.; Lee, R. C. T.; Chang, R. C. (1993), "The slab dividing approach to solve the Euclidean p-center problem", Algorithmica, 9 (1): 1–22, doi:10.1007/BF01185335, S2CID 5680676
↑ HWang, R. Z.; Chang, R. C.; Lee, R. C. T. (1993), "The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time", Algorithmica, 9 (4): 398–423, doi:10.1007/bf01228511, S2CID 2722869
↑ Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing: 250–257, doi:10.1145/509907.509947, ISBN 1581134959, S2CID 5409535
↑ Kumar, Pankaj; Kumar, Piyush (2010), "Almost optimal solutions to k-clustering problems" (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431–447, doi:10.1142/S0218195910003372
↑ Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. ISBN 978-0-387-96131-6. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989., p. 256
↑ G. T. Toussaint, "Computing largest empty circles with location constraints," International Journal of Computer and Information Sciences, vol. 12, No. 5, October, 1983, pp. 347–358.
↑ ^14.0 ^14.1 Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Integer Programming | SpringerLink. Graduate Texts in Mathematics (in British English). Vol. 271. doi:10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.
↑ असतत स्थान सिद्धांत. Mirchandani, Pitu B., Francis, R. L. New York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449.{{cite book}}: CS1 maint: others (link)
↑ Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "स्वास्थ्य सेवा सुविधा स्थान का एक सर्वेक्षण". Computers & Operations Research. 79: 223–263. doi:10.1016/j.cor.2016.05.018.
↑ Franco, D. G. B.; Steiner, M. T. A.; Assef, F. M. (2020). "Optimization in waste landfilling partitioning in Paraná State, Brazil". Journal of Cleaner Production. 283: 125353. doi:10.1016/j.jclepro.2020.125353. S2CID 229429742.
↑ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). सांख्यिकीय सबक के तत्व (Second ed.). Springer.
↑ Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिज़ाइन. Pearson.

बाहरी संबंध

EWGLA EURO Working Group on Locational Analysis.
INFORMS section on location analysis, a professional society concerned with facility location.
Bibliography on facility location collected by Trevor Hale, containing over 3400 articles.
Library of location algorithms
Web-based facility location utility (single facility)
Facility Location Optimizer, a MATLAB-based tool for solving facility location problems.

[1] Hochbaum, D. S. (1982). "निश्चित लागत माध्यिका समस्या के लिए अनुमान". Mathematical Programming. 22: 148–162. doi:10.1007/BF01581035. S2CID 3451944.

[2] Guha, S.; Khuller, S. (1999). "Greedy Strikes Back: Improved Facility Location Algorithms". Journal of Algorithms. 31: 228–248. CiteSeerX 10.1.1.47.2033. doi:10.1006/jagm.1998.0993. S2CID 5363214.

[3] Li, S. (2011). "A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem". ऑटोमेटा, भाषाएँ और प्रोग्रामिंग. LNCS. Vol. 6756. pp. 77–88. CiteSeerX 10.1.1.225.6387. doi:10.1007/978-3-642-22012-8_5. ISBN 978-3-642-22011-1.

[4] Fowler, R. J.; Paterson, M. S.; Tanimoto, S. L. (1981), "Optimal packing and covering in the plane are NP-complete", Information Processing Letters, 12 (3): 133–137, doi:10.1016/0020-0190(81)90111-3.

[5] Megiddo, Nimrod; Tamir, Arie (1982), "On the complexity of locating linear facilities in the plane" (PDF), Operations Research Letters, 1 (5): 194–197, doi:10.1016/0167-6377(82)90039-6.

[Gonzalez1985-6] 6.0 ^6.1 ^6.2 Gonzalez, Teofilo (1985), "Clustering to minimize the maximum intercluster distance", Theoretical Computer Science, 38: 293–306, doi:10.1016/0304-3975(85)90224-5.

[Feder1988-7] 7.0 ^7.1 Feder, Tomás; Greene, Daniel (1988), "Optimal algorithms for approximate clustering", Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing: 434–444, doi:10.1145/62212.62255, ISBN 0897912640, S2CID 658151

[8] HWang, R. Z.; Lee, R. C. T.; Chang, R. C. (1993), "The slab dividing approach to solve the Euclidean p-center problem", Algorithmica, 9 (1): 1–22, doi:10.1007/BF01185335, S2CID 5680676

[9] HWang, R. Z.; Chang, R. C.; Lee, R. C. T. (1993), "The generalized searching over separators strategy to solve some NP-Hard problems in subexponential time", Algorithmica, 9 (4): 398–423, doi:10.1007/bf01228511, S2CID 2722869

[10] Bādoiu, Mihai; Har-Peled, Sariel; Indyk, Piotr (2002), "Approximate clustering via core-sets" (PDF), Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing: 250–257, doi:10.1145/509907.509947, ISBN 1581134959, S2CID 5409535

[11] Kumar, Pankaj; Kumar, Piyush (2010), "Almost optimal solutions to k-clustering problems" (PDF), International Journal of Computational Geometry & Applications, 20 (4): 431–447, doi:10.1142/S0218195910003372

[ps256-12] Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. ISBN 978-0-387-96131-6. 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989., p. 256

[13] G. T. Toussaint, "Computing largest empty circles with location constraints," International Journal of Computer and Information Sciences, vol. 12, No. 5, October, 1983, pp. 347–358.

[:0-14] 14.0 ^14.1 Conforti, Michele; Cornuéjols, Gérard; Zambelli, Giacomo (2014). Integer Programming | SpringerLink. Graduate Texts in Mathematics (in British English). Vol. 271. doi:10.1007/978-3-319-11008-0. ISBN 978-3-319-11007-3.

[15] असतत स्थान सिद्धांत. Mirchandani, Pitu B., Francis, R. L. New York: Wiley. 1990. ISBN 9780471892335. OCLC 19810449.{{cite book}}: CS1 maint: others (link)

[Ahmadi-16] Ahmadi-Javid, A.; Seyedi, P.; Syam, S. (2017). "स्वास्थ्य सेवा सुविधा स्थान का एक सर्वेक्षण". Computers & Operations Research. 79: 223–263. doi:10.1016/j.cor.2016.05.018.

[17] Franco, D. G. B.; Steiner, M. T. A.; Assef, F. M. (2020). "Optimization in waste landfilling partitioning in Paraná State, Brazil". Journal of Cleaner Production. 283: 125353. doi:10.1016/j.jclepro.2020.125353. S2CID 229429742.

[18] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). सांख्यिकीय सबक के तत्व (Second ed.). Springer.

[19] Kleinberg, Jon; Tardos, Éva (2006). एल्गोरिथम डिज़ाइन. Pearson.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

@@ Line 1: / Line 1: @@
-{{More citations needed|date=May 2009}}
+'''सुविधा स्थान समस्याओं''' का अध्ययन (एफएलपी), जिसे '''स्थान विश्लेषण''' के रूप में भी जाना जाता है, संचालन अनुसंधान और [[कम्प्यूटेशनल ज्यामिति]] की एक शाखा है जो आवास के पास खतरनाक सामग्री रखने से बचने और प्रतिस्पर्धियों के कारकों पर विचार करते हुए परिवहन लागत को कम करने के लिए सुविधाओं के इष्टतम स्थान से संबंधित है। तकनीकें [[क्लस्टर विश्लेषण]] पर भी लागू होती हैं।
-सुविधा स्थान समस्याओं का अध्ययन (एफएलपी), जिसे स्थान विश्लेषण के रूप में भी जाना जाता है, संचालन अनुसंधान और [[कम्प्यूटेशनल ज्यामिति]] की एक शाखा है जो आवास के पास खतरनाक सामग्री रखने से बचने और प्रतिस्पर्धियों के कारकों पर विचार करते हुए परिवहन लागत को कम करने के लिए सुविधाओं के इष्टतम स्थान से संबंधित है। सुविधाएँ। तकनीकें [[क्लस्टर विश्लेषण]] पर भी लागू होती हैं।
 ==न्यूनतम सुविधा स्थान==
-एक सरल सुविधा स्थान समस्या [[वेबर समस्या]] है, जिसमें एक एकल सुविधा को रखा जाना है, जिसमें एकमात्र अनुकूलन मानदंड बिंदु साइटों के दिए गए सेट से दूरियों के भारित योग को कम करना है। इस अनुशासन में विचार की जाने वाली अधिक जटिल समस्याओं में कई सुविधाओं की नियुक्ति, सुविधाओं के स्थानों पर बाधाएं और अधिक जटिल अनुकूलन मानदंड शामिल हैं।
+एक सरल सुविधा स्थान समस्या [[वेबर समस्या]] है, जिसमें एक एकल सुविधा को रखा जाना है, जिसमें एकमात्र अनुकूलन मानदंड बिंदु साइटों के दिए गए सेट से दूरियों के भारित योग को कम करना है। इस अनुशासन में विचार की जाने वाली अधिक जटिल समस्याओं में कई सुविधाओं की नियुक्ति, सुविधाओं के स्थानों पर बाधाएं और अधिक जटिल अनुकूलन मानदंड सम्मिलित हैं।
-बुनियादी सूत्रीकरण में, सुविधा स्थान की समस्या में संभावित सुविधा साइटों एल का एक सेट शामिल होता है जहां एक सुविधा खोली जा सकती है, और मांग बिंदु डी का एक सेट होता है जिसे सेवा प्रदान की जानी चाहिए। लक्ष्य खोलने के लिए सुविधाओं का एक उपसमूह एफ चुनना है, प्रत्येक मांग बिंदु से उसकी निकटतम सुविधा तक की दूरी के योग को कम करना है, साथ ही सुविधाओं की शुरुआती लागत का योग भी कम करना है।
+बुनियादी सूत्रीकरण में, सुविधा स्थान की समस्या में संभावित सुविधा साइटों एल का एक सेट सम्मिलित होता है जहां एक सुविधा खोली जा सकती है, और मांग बिंदु ''D'' का एक सेट होता है जिसे सेवा प्रदान की जानी चाहिए। लक्ष्य खोलने के लिए सुविधाओं का एक उपसमूह ''F'' चुनना है, प्रत्येक मांग बिंदु से उसकी निकटतम सुविधा तक की दूरी के योग को कम करना है, साथ ही सुविधाओं की प्रारंभिक लागत का योग भी कम करना है।
 सामान्य ग्राफ़ पर सुविधा स्थान की समस्या को (उदाहरण के लिए) [[सेट कवर समस्या]] से कम करके, इष्टतम तरीके से हल करना एनपी-कठिन है। सुविधा स्थान समस्या और इसके कई प्रकारों के लिए कई सन्निकटन एल्गोरिदम विकसित किए गए हैं।
-ग्राहकों और साइटों के बीच दूरियों के सेट पर धारणाओं के बिना (विशेष रूप से, यह माने बिना कि दूरियां त्रिकोण असमानता को संतुष्ट करती हैं), समस्या को 'गैर-मीट्रिक सुविधा स्थान' के रूप में जाना जाता है और इसे एक कारक O(लॉग एन) के भीतर अनुमानित किया जा सकता है ).<ref>{{Cite journal | last1 = Hochbaum | first1 = D. S. | author-link = Dorit S. Hochbaum| doi = 10.1007/BF01581035 | title = निश्चित लागत माध्यिका समस्या के लिए अनुमान| journal = [[Mathematical Programming]] | volume = 22 | pages = 148–162 | year = 1982 | s2cid = 3451944 }}</ref> सेट कवर समस्या से [[सन्निकटन-संरक्षण कमी]] के माध्यम से, यह कारक तंग है।
+ग्राहकों और साइटों के बीच दूरियों के सेट पर धारणाओं के बिना (विशेष रूप से, यह माने बिना कि दूरियां त्रिकोण असमानता को संतुष्ट करती हैं), समस्या को '<nowiki/>'''गैर-मीट्रिक सुविधा स्थान'''' के रूप में जाना जाता है और इसे एक कारक O(log ''n'') के भीतर अनुमानित किया जा सकता है ).<ref>{{Cite journal | last1 = Hochbaum | first1 = D. S. | author-link = Dorit S. Hochbaum| doi = 10.1007/BF01581035 | title = निश्चित लागत माध्यिका समस्या के लिए अनुमान| journal = [[Mathematical Programming]] | volume = 22 | pages = 148–162 | year = 1982 | s2cid = 3451944 }}</ref> सेट कवर समस्या से [[सन्निकटन-संरक्षण कमी]] के माध्यम से, यह कारक तंग (टाइट) है।
 यदि हम मानते हैं कि ग्राहकों और साइटों के बीच की दूरी अप्रत्यक्ष है और त्रिकोण असमानता को संतुष्ट करती है, तो हम मीट्रिक सुविधा स्थान (एमएफएल) समस्या के बारे में बात कर रहे हैं। एमएफएल अभी भी एनपी-हार्ड है और 1.463 से बेहतर कारक के भीतर अनुमान लगाना कठिन है।<ref>{{Cite journal | doi = 10.1006/jagm.1998.0993| title = Greedy Strikes Back: Improved Facility Location Algorithms| journal = Journal of Algorithms| volume = 31| pages = 228–248| year = 1999| last1 = Guha | first1 = S. | last2 = Khuller | first2 = S. | citeseerx = 10.1.1.47.2033| s2cid = 5363214}}</ref> वर्तमान में सबसे अच्छा ज्ञात सन्निकटन एल्गोरिथ्म 1.488 का सन्निकटन अनुपात प्राप्त करता है।<ref>{{Cite book | last1 = Li | first1 = S. | chapter = A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem | doi = 10.1007/978-3-642-22012-8_5 | title = ऑटोमेटा, भाषाएँ और प्रोग्रामिंग| series = [[Lecture Notes in Computer Science|LNCS]]| volume = 6756 | pages = 77–88 | year = 2011 | isbn = 978-3-642-22011-1 | citeseerx = 10.1.1.225.6387 }}</ref>
 ==मिनीमैक्स सुविधा स्थान==
-मिनिमैक्स सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों की अधिकतम दूरी को कम करती है, जहां एक बिंदु से साइटों की दूरी बिंदु से उसके निकटतम साइट की दूरी है। एक औपचारिक परिभाषा इस प्रकार है:
+'''मिनिमैक्स सुविधा स्थान''' समस्या एक ऐसे स्थान की तलाश करती है जो साइटों की अधिकतम दूरी को कम करती है, जहां एक बिंदु से साइटों की दूरी बिंदु से उसके निकटतम साइट की दूरी है। एक औपचारिक परिभाषा इस प्रकार है:
-एक बिंदु सेट ''P'' ⊂ ℝ दिया गया है<sup>d</sup>, एक बिंदु सेट 'S' ⊂ ℝ खोजें<sup>घ</sup>, |'S'| = k, ताकि अधिकतम<sub>'''p'''&nbsp;∈&nbsp;'''''P'''''</sub>(मिन<sub>'''q'''&nbsp;∈&nbsp;'''''S'''''</sub>(d(p, q)) ) को न्यूनतम किया गया है।
+एक बिंदु सेट ''P'' ⊂ ℝ<sup>d</sup> दिया गया है, एक बिंदु सेट 'S' ⊂ ℝ<sup>d</sup> ख, |'S'| = k, ताकि (अधिकतम) max<sub>'''p'''&nbsp;∈&nbsp;'''''P'''''</sub>(min<sub>'''q'''&nbsp;∈&nbsp;'''''S'''''</sub>(d('''p, q''')) ) को न्यूनतम किया गया है।
-''k'' = 1 के लिए यूक्लिडियन मीट्रिक के मामले में, इसे सबसे छोटी संलग्न क्षेत्र समस्या या [[1-केंद्र समस्या]] के रूप में जाना जाता है। इसका अध्ययन कम से कम 1860 के वर्ष का है। अधिक विवरण के लिए [[सबसे छोटा घेरने वाला वृत्त]] और [[सीमा क्षेत्र]] देखें।
+''k'' = 1 के लिए यूक्लिडियन मीट्रिक के स्थिति में, इसे सबसे छोटी संलग्न क्षेत्र समस्या या [[1-केंद्र समस्या]] के रूप में जाना जाता है। इसका अध्ययन कम से कम 1860 के वर्ष का है। अधिक विवरण के लिए [[सबसे छोटा घेरने वाला वृत्त]] और [[सीमा क्षेत्र]] देखें।
 ===एनपी कठोरता===
@@ Line 64: / Line 61: @@
   | s2cid = 658151
   }}</ref> या 2 (आयाम > 2).<ref name = Gonzalez1985/>
 ===एल्गोरिदम===
-सटीक सॉल्वर
+'''सटीक सॉल्वर'''
 इस समस्या का सटीक समाधान निकालने के लिए एल्गोरिदम मौजूद हैं। एक सटीक सॉल्वर समय में चलता है <math>n^{O(\sqrt{k})}</math>.<ref>{{citation
@@ Line 90: / Line 85: @@
   | pages = 398–423 | doi=10.1007/bf01228511 |s2cid=	2722869
   }}</ref>
-+ ''ε'' सन्निकटन
-+''ε'' सन्निकटन का तात्पर्य सन्निकटन कारक के साथ एक समाधान ढूंढना है जो 1+''ε'' से अधिक न हो। यह सन्निकटन एनपी कठिन है क्योंकि ''ε'' मनमाना है। [[ कोर सेट ]] अवधारणा पर आधारित एक दृष्टिकोण निष्पादन जटिलता के साथ प्रस्तावित है  <math>O(2^{O(k \log k/\varepsilon^2)}dn)</math>.<ref>{{citation
+'''1 + ''ε'' सन्निकटन'''
++''ε'' सन्निकटन का तात्पर्य सन्निकटन कारक के साथ एक समाधान ढूंढना है जो 1+''ε'' से अधिक न हो। यह सन्निकटन एनपी कठिन है क्योंकि ''ε'' मनमाना है। [[ कोर सेट | कोर सेट]] अवधारणा पर आधारित एक दृष्टिकोण निष्पादन जटिलता के साथ प्रस्तावित है  <math>O(2^{O(k \log k/\varepsilon^2)}dn)</math>.<ref>{{citation
   |first1=Mihai |last1= Bādoiu
   |first2=Sariel |last2=Har-Peled | author2-link = Sariel Har-Peled
@@ Line 104: / Line 100: @@
   |isbn= 1581134959
   |s2cid= 5409535
-  }}</ref>
+  }}</ref> विकल्प के रूप में, कोर सेट पर आधारित एक अन्य एल्गोरिदम भी उपलब्ध है। यह अंदर चलता है <math>O(k^n)</math>.<ref>{{citation
-विकल्प के रूप में, कोर सेट पर आधारित एक अन्य एल्गोरिदम भी उपलब्ध है। यह अंदर चलता है <math>O(k^n)</math>.<ref>{{citation
   |first1=Pankaj |last1= Kumar
   |first2=Piyush |last2= Kumar
@@ Line 118: / Line 113: @@
   }}</ref> लेखक का दावा है कि चलने का समय सबसे खराब स्थिति से बहुत कम है और इस प्रकार k छोटा होने पर कुछ समस्याओं को हल करना संभव है (कहें k <5)।
-'सबसे दूर बिंदु क्लस्टरिंग'
+''''सबसे दूर बिंदु क्लस्टरिंग'''<nowiki/>'
-समस्या की कठोरता के लिए, सटीक समाधान या सटीक अनुमान प्राप्त करना अव्यावहारिक है। इसके बजाय, बड़े k मामलों के लिए कारक = 2 के साथ एक सन्निकटन का व्यापक रूप से उपयोग किया जाता है। सन्निकटन को सबसे दूर-बिंदु क्लस्टरिंग (एफपीसी) एल्गोरिदम, या सबसे दूर-पहले ट्रैवर्सल के रूप में जाना जाता है।<ref name=Gonzalez1985/>एल्गोरिथ्म काफी सरल है: सेट से किसी भी बिंदु को एक केंद्र के रूप में चुनें; किसी अन्य केंद्र के रूप में शेष सेट से सबसे दूर बिंदु की खोज करें; प्रक्रिया को तब तक दोहराएँ जब तक कि k केंद्र न मिल जाएँ।
+समस्या की कठोरता के लिए, सटीक समाधान या सटीक अनुमान प्राप्त करना अव्यावहारिक है। इसके बजाय, बड़े k मामलों के लिए कारक = 2 के साथ एक सन्निकटन का व्यापक रूप से उपयोग किया जाता है। सन्निकटन को सबसे दूर-बिंदु क्लस्टरिंग (फार्थेस्ट -पॉइंट) (एफपीसी) एल्गोरिदम, या सबसे दूर-पहले ट्रैवर्सल के रूप में जाना जाता है।<ref name="Gonzalez1985" />एल्गोरिथ्म काफी सरल है: सेट से किसी भी बिंदु को एक केंद्र के रूप में चुनें; किसी अन्य केंद्र के रूप में शेष सेट से सबसे दूर बिंदु की खोज करें; प्रक्रिया को तब तक दोहराएँ जब तक कि k केंद्र न मिल जाएँ।
 यह देखना आसान है कि यह एल्गोरिदम रैखिक समय में चलता है। चूंकि 2 से कम कारक के साथ सन्निकटन एनपी कठिन साबित हुआ है, एफपीसी को सबसे अच्छा सन्निकटन माना जाता था जिसे कोई भी पा सकता है।
-निष्पादन के प्रदर्शन के अनुसार, समय जटिलता को बाद में बॉक्स अपघटन तकनीक के साथ ओ (एन लॉग के) में सुधार किया गया है।<ref name=Feder1988/>
+निष्पादन के प्रदर्शन के अनुसार, समय जटिलता को बाद में बॉक्स अपघटन तकनीक के साथ ओ ''n'' log ''k'') में सुधार किया गया है।<ref name=Feder1988/>
 ==मैक्समिन सुविधा स्थान==
-अधिकतम सुविधा स्थान या अप्रिय सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों से न्यूनतम दूरी को अधिकतम कर दे। यूक्लिडियन मीट्रिक के मामले में, इसे सबसे बड़ी खाली क्षेत्र समस्या के रूप में जाना जाता है। समतलीय मामला (सबसे बड़ी खाली वृत्त समस्या) को समय जटिलता Θ(''n'' लॉग एन) में हल किया जा सकता है।<ref name=ps256>{{cite book | author = [[Franco P. Preparata]] and [[Michael Ian Shamos]] | title = Computational Geometry – An Introduction | publisher = Springer-Verlag | year = 1985 | id = 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989 | isbn = 978-0-387-96131-6 | url-access = registration | url = https://archive.org/details/computationalgeo0000prep }}, [https://books.google.com/books?id=gFtvRdUY09UC&dq=%22minimax+facilities+location%22&pg=PA256 p.&nbsp;256]</ref><ref>G. T. Toussaint, "Computing largest empty circles with location constraints," ''International Journal of Computer and Information Sciences'', vol. 12, No. 5, October, 1983, pp. 347–358.</ref>
+'''मैक्समिन''' ('''अधिकतम''') '''सुविधा स्थान''' या अप्रिय सुविधा स्थान समस्या एक ऐसे स्थान की तलाश करती है जो साइटों से न्यूनतम दूरी को अधिकतम कर दे। यूक्लिडियन मीट्रिक के स्थिति में, इसे सबसे बड़ी खाली क्षेत्र समस्या के रूप में जाना जाता है। समतलीय मामला (सबसे बड़ी खाली वृत्त समस्या) को समय जटिलता Θ(''n'' log n) में हल किया जा सकता है।<ref name=ps256>{{cite book | author = [[Franco P. Preparata]] and [[Michael Ian Shamos]] | title = Computational Geometry – An Introduction | publisher = Springer-Verlag | year = 1985 | id = 1st edition; 2nd printing, corrected and expanded, 1988; Russian translation, 1989 | isbn = 978-0-387-96131-6 | url-access = registration | url = https://archive.org/details/computationalgeo0000prep }}, [https://books.google.com/books?id=gFtvRdUY09UC&dq=%22minimax+facilities+location%22&pg=PA256 p.&nbsp;256]</ref><ref>G. T. Toussaint, "Computing largest empty circles with location constraints," ''International Journal of Computer and Information Sciences'', vol. 12, No. 5, October, 1983, pp. 347–358.</ref>
+== [[पूर्णांक प्रोग्रामिंग|पूर्णांक (इंटीजर) प्रोग्रामिंग]] फॉर्मूलेशन ==
+सुविधा स्थान की समस्याओं को प्रायः इंटीजर प्रोग्रामिंग के रूप में हल किया जाता है। इस संदर्भ में, सुविधा स्थान की समस्याएं प्रायः इस प्रकार सामने आती हैं: मान लीजिए कि हैं <math>n</math> सुविधाएं और <math>m</math> ग्राहक. हम इनमें से (1) किसे चुनना चाहते हैं <math>n</math> खोलने के लिए सुविधाएं, और (2) आपूर्ति के लिए कौन सी (खुली) सुविधाओं का उपयोग करना है <math>m</math> ग्राहकों को, न्यूनतम लागत पर कुछ निश्चित मांग को पूरा करने के लिए। हम निम्नलिखित संकेतन प्रस्तुत करते हैं: मान लीजिए कि <math>f_i</math> सुविधा खोलने की (निश्चित) लागत को निरूपित करें <math>i</math>, के लिए <math>i=1,\dots,n</math>. होने देना <math>c_{ij}</math>किसी उत्पाद को सुविधा से शिप करने की लागत को दर्शाता है <math>i</math> ग्राहक को <math>j</math> के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math>. मान लीजिए कि <math>d_j</math> ग्राहक की मांग को निरूपित करें <math>j</math> के लिए <math>j=1,\dots,m</math>. इसके अलावा मान लीजिए कि प्रत्येक सुविधा का अधिकतम आउटपुट है। मान लीजिए कि <math>u_i</math> सुविधा द्वारा उत्पादित किए जा सकने वाले उत्पाद की अधिकतम मात्रा को निरूपित करें <math>i</math>, अर्थात् मान लीजिए कि <math>u_i</math> सुविधा की क्षमता को निरूपित करें <math>i</math>. इस खंड का शेष भाग इस प्रकार है<ref name=":0">{{Cite book|title=Integer Programming {{!}} SpringerLink|volume = 271|last1=Conforti|first1=Michele|last2=Cornuéjols|first2=Gérard|last3=Zambelli|first3=Giacomo|language=en-gb|doi=10.1007/978-3-319-11008-0|series = Graduate Texts in Mathematics|year = 2014|isbn = 978-3-319-11007-3}}</ref>
-== [[पूर्णांक प्रोग्रामिंग]] फॉर्मूलेशन ==
-सुविधा स्थान की समस्याओं को अक्सर इंटीजर प्रोग्रामिंग के रूप में हल किया जाता है। इस संदर्भ में, सुविधा स्थान की समस्याएं अक्सर इस प्रकार सामने आती हैं: मान लीजिए कि हैं <math>n</math> सुविधाएं और <math>m</math> ग्राहक. हम इनमें से (1) किसे चुनना चाहते हैं <math>n</math> खोलने के लिए सुविधाएं, और (2) आपूर्ति के लिए कौन सी (खुली) सुविधाओं का उपयोग करना है <math>m</math> ग्राहकों को, न्यूनतम लागत पर कुछ निश्चित मांग को पूरा करने के लिए। हम निम्नलिखित संकेतन प्रस्तुत करते हैं: चलो <math>f_i</math> सुविधा खोलने की (निश्चित) लागत को निरूपित करें <math>i</math>, के लिए <math>i=1,\dots,n</math>. होने देना <math>c_{ij}</math>किसी उत्पाद को सुविधा से शिप करने की लागत को दर्शाता है <math>i</math> ग्राहक को <math>j</math> के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math>. होने देना <math>d_j</math> ग्राहक की मांग को निरूपित करें <math>j</math> के लिए <math>j=1,\dots,m</math>. इसके अलावा मान लीजिए कि प्रत्येक सुविधा का अधिकतम आउटपुट है। होने देना <math>u_i</math> सुविधा द्वारा उत्पादित किए जा सकने वाले उत्पाद की अधिकतम मात्रा को निरूपित करें <math>i</math>, अर्थात् चलो <math>u_i</math> सुविधा की क्षमता को निरूपित करें <math>i</math>. इस खंड का शेष भाग इस प्रकार है<ref name=":0">{{Cite book|title=Integer Programming {{!}} SpringerLink|volume = 271|last1=Conforti|first1=Michele|last2=Cornuéjols|first2=Gérard|last3=Zambelli|first3=Giacomo|language=en-gb|doi=10.1007/978-3-319-11008-0|series = Graduate Texts in Mathematics|year = 2014|isbn = 978-3-319-11007-3}}</ref>
 === क्षमतायुक्त सुविधा स्थान ===
-हमारे प्रारंभिक सूत्रीकरण में, एक बाइनरी वैरिएबल का परिचय दें <math>x_i</math> के लिए <math>i=1,\dots,n</math>, कहाँ <math>x_i=1</math> यदि सुविधा <math>i</math> खुला है, और <math>x_i=0</math> अन्यथा। आगे वेरिएबल का परिचय दें <math>y_{ij}</math> के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math> जो मांग के अंश को दर्शाता है <math>d_j</math> सुविधा द्वारा भरा गया <math>i</math>. तथाकथित कैपेसिटेटेड सुविधा स्थान समस्या तब दी जाती है<math display="block">\begin{array}{rl}
+हमारे प्रारंभिक सूत्रीकरण में, एक बाइनरी वैरिएबल का परिचय दें <math>x_i</math> के लिए <math>i=1,\dots,n</math>, जहाँ <math>x_i=1</math> यदि सुविधा <math>i</math> खुला है, और <math>x_i=0</math> अन्यथा। आगे वेरिएबल का परिचय दें <math>y_{ij}</math> के लिए <math>i=1,\dots,n</math> और <math>j=1,\dots,m</math> जो मांग के अंश को दर्शाता है <math>d_j</math> सुविधा द्वारा भरा गया <math>i</math>. तथाकथित कैपेसिटेटेड सुविधा स्थान समस्या तब दी जाती है<math display="block">\begin{array}{rl}
 \min & \displaystyle\sum_{i=1}^n\sum_{j=1}^mc_{ij} d_j y_{ij}+\sum_{i=1}^nf_ix_i \\
 \text{s.t.} & \displaystyle\sum_{i=1}^ny_{ij}=1 \text{ for all }j=1,\dots,m \\
@@ Line 145: / Line 134: @@
 ध्यान दें कि बाधाओं का दूसरा सेट यह सुनिश्चित करता है कि यदि <math>x_i=0</math>, यानी सुविधा <math>i</math> तो फिर, खुला नहीं है <math>y_{ij}=0</math> सभी के लिए <math>j</math>यानी सुविधा से किसी भी ग्राहक की कोई डिमांड नहीं भरी जा सकेगी <math>i</math>.
-=== असंबद्ध सुविधा स्थान ===
+=== '''अनकैपेसिटीड सुविधा स्थान की समस्या''' ===
-उपरोक्त कैपेसिटेटेड सुविधा स्थान समस्या का एक सामान्य मामला तब होता है जब <math>u_i=+\infty</math> सभी के लिए <math>i=1,\dots,n</math>. इस मामले में, ग्राहक की सभी मांगों को पूरा करना हमेशा इष्टतम होता है <math>j</math> निकटतम खुली सुविधा से. इस वजह से, हम सतत चरों को प्रतिस्थापित कर सकते हैं <math>y_{ij}</math> ऊपर से [[बाइनरी डेटा]] के साथ <math>z_{ij}</math>, कहाँ <math>z_{ij}=1</math> यदि ग्राहक <math>j</math> सुविधा द्वारा आपूर्ति की जाती है <math>i</math>, और <math>z_{ij}=0</math> अन्यथा। अनकैपेसिटीड सुविधा स्थान की समस्या तब दी जाती है<math display="block">\begin{array}{rl}
+उपरोक्त कैपेसिटेटेड सुविधा स्थान समस्या का एक सामान्य मामला तब होता है जब <math>u_i=+\infty</math> सभी के लिए <math>i=1,\dots,n</math>. इस स्थिति में, ग्राहक की सभी मांगों को पूरा करना हमेशा इष्टतम होता है <math>j</math> निकटतम खुली सुविधा से. इस वजह से, हम सतत चरों को प्रतिस्थापित कर सकते हैं <math>y_{ij}</math> ऊपर से [[बाइनरी डेटा]] के साथ <math>z_{ij}</math>, जहाँ <math>z_{ij}=1</math> यदि ग्राहक <math>j</math> सुविधा द्वारा आपूर्ति की जाती है <math>i</math>, और <math>z_{ij}=0</math> अन्यथा। '''अनकैपेसिटीड सुविधा स्थान की समस्या''' तब दी जाती है<math display="block">\begin{array}{rl}
 \min & \displaystyle\sum_{i=1}^n\sum_{j=1}^mc_{ij} d_j z_{ij}+\sum_{i=1}^nf_ix_i \\
 \text{s.t.} & \displaystyle\sum_{i=1}^nz_{ij}=1 \text{ for all }j=1,\dots,m \\
@@ Line 153: / Line 142: @@
 &x_i\in\{0,1\}\text{ for all } i=1,\dots,n
 \end{array}</math>
-कहाँ <math>M</math> उपयुक्त रूप से बड़े होने के लिए चुना गया एक स्थिरांक है। का चुनाव <math>M</math> गणना परिणामों को प्रभावित कर सकता है - इस उदाहरण में सबसे अच्छा विकल्प स्पष्ट है: लेना <math>M=m</math>. तो अगर <math>x_i=1</math>, का कोई भी विकल्प <math>z_{ij}</math> बाधाओं के दूसरे सेट को संतुष्ट करेगा।
+जहाँ <math>M</math> उपयुक्त रूप से बड़े होने के लिए चुना गया एक स्थिरांक है। का चुनाव <math>M</math> गणना परिणामों को प्रभावित कर सकता है - इस उदाहरण में सबसे अच्छा विकल्प स्पष्ट है: लेना <math>M=m</math>. तो अगर <math>x_i=1</math>, का कोई भी विकल्प <math>z_{ij}</math> बाधाओं के दूसरे सेट को संतुष्ट करेगा।
-अप्रतिबंधित सुविधा स्थान समस्या के लिए एक अन्य सूत्रीकरण संभावना क्षमता बाधाओं (बड़ी-) को अलग करना है<math>M</math> प्रतिबंध)। यानी बाधाओं को बदलें<math display="block">\sum_{j=1}^{m}z_{ij}\leqslant Mx_i\text{ for all }i=1,\dots,n</math>बाधाओं के साथ<math display="block">z_{ij}\leqslant x_i\text{ for all }i=1,\dots,n \text{ and }j=1,\dots,m</math>व्यवहार में, यह नया फॉर्मूलेशन काफी बेहतर प्रदर्शन करता है, इस अर्थ में कि इसमें पहले फॉर्मूलेशन की तुलना में अधिक सख्त [[रैखिक प्रोग्रामिंग]] छूट है।<ref name=":0" />ध्यान दें कि नई बाधाओं को एक साथ जोड़ने पर मूल बड़ा परिणाम प्राप्त होता है-<math>M</math> प्रतिबंध। कैपेसिटेटेड मामले में, ये फॉर्मूलेशन समकक्ष नहीं हैं। असंबद्ध सुविधा स्थान समस्या के बारे में अधिक जानकारी असतत स्थान सिद्धांत के अध्याय 3 में पाई जा सकती है।<ref>{{Cite book|title=असतत स्थान सिद्धांत|date=1990|publisher=Wiley|others=Mirchandani, Pitu B., Francis, R. L.|isbn=9780471892335|location=New York|oclc=19810449}}</ref>
+अप्रतिबंधित सुविधा स्थान समस्या के लिए एक अन्य सूत्रीकरण संभावना क्षमता बाधाओ को अलग करना है (बड़ा-<math>M</math> प्रतिबंध)। यानी बाधाओं को बदलें है<math display="block">\sum_{j=1}^{m}z_{ij}\leqslant Mx_i\text{ for all }i=1,\dots,n</math>बाधाओं के साथ<math display="block">z_{ij}\leqslant x_i\text{ for all }i=1,\dots,n \text{ and }j=1,\dots,m</math>व्यवहार में, यह नया फॉर्मूलेशन काफी बेहतर प्रदर्शन करता है, इस अर्थ में कि इसमें पहले फॉर्मूलेशन की तुलना में अधिक सख्त [[रैखिक प्रोग्रामिंग]] छूट है।<ref name=":0" />ध्यान दें कि नई बाधाओं को एक साथ जोड़ने पर मूल बड़ा परिणाम प्राप्त होता है-<math>M</math> प्रतिबंध। कैपेसिटेटेड स्थिति में, ये फॉर्मूलेशन समकक्ष नहीं हैं। असंबद्ध सुविधा स्थान समस्या के बारे में अधिक जानकारी <nowiki>''असतत स्थान सिद्धांत''</nowiki> के अध्याय 3 में पाई जा सकती है।<ref>{{Cite book|title=असतत स्थान सिद्धांत|date=1990|publisher=Wiley|others=Mirchandani, Pitu B., Francis, R. L.|isbn=9780471892335|location=New York|oclc=19810449}}</ref>
 ==अनुप्रयोग==
 ===स्वास्थ्य देखभाल===
-स्वास्थ्य देखभाल में, गलत सुविधा स्थान निर्णयों का साधारण लागत और सेवा मेट्रिक्स से परे समुदाय पर गंभीर प्रभाव पड़ता है; उदाहरण के लिए, कठिन पहुंच वाली स्वास्थ्य सुविधाएं रुग्णता और मृत्यु दर में वृद्धि से जुड़ी होने की संभावना है। इस दृष्टिकोण से, स्वास्थ्य देखभाल के लिए सुविधा स्थान मॉडलिंग अन्य क्षेत्रों के लिए समान मॉडलिंग की तुलना में अधिक महत्वपूर्ण है।<ref name="Ahmadi">{{Cite journal | doi = 10.1016/j.cor.2016.05.018| title = स्वास्थ्य सेवा सुविधा स्थान का एक सर्वेक्षण| year = 2017| last1 = Ahmadi-Javid | first1 = A. | last2 = Seyedi | first2 = P. | last3 = Syam | first3 = S. | journal = Computers & Operations Research| volume = 79| pages = 223–263}}</ref>
+स्वास्थ्य देखभाल में, गलत सुविधा स्थान निर्णयों का साधारण लागत और सेवा मेट्रिक्स से परे समुदाय पर गंभीर प्रभाव पड़ता है; उदाहरण के लिए, हार्ड-टू-एक्सेस (कठिन पहुंच वाली) स्वास्थ्य सुविधाएं रुग्णता और मृत्यु दर में वृद्धि से जुड़ी होने की संभावना है। इस दृष्टिकोण से, स्वास्थ्य देखभाल के लिए सुविधा स्थान मॉडलिंग अन्य क्षेत्रों के लिए समान मॉडलिंग की तुलना में अधिक महत्वपूर्ण है।<ref name="Ahmadi">{{Cite journal | doi = 10.1016/j.cor.2016.05.018| title = स्वास्थ्य सेवा सुविधा स्थान का एक सर्वेक्षण| year = 2017| last1 = Ahmadi-Javid | first1 = A. | last2 = Seyedi | first2 = P. | last3 = Syam | first3 = S. | journal = Computers & Operations Research| volume = 79| pages = 223–263}}</ref>
 ===ठोस अपशिष्ट प्रबंधन===
 बढ़ते अपशिष्ट उत्पादन और अपशिष्ट प्रबंधन से जुड़ी उच्च लागत के कारण नगरपालिका ठोस अपशिष्ट प्रबंधन अभी भी विकासशील देशों के लिए एक चुनौती बनी हुई है। किसी सुविधा स्थान की समस्या के निर्माण और सटीक समाधान के माध्यम से अपशिष्ट निपटान के लिए लैंडफिल के स्थान को अनुकूलित करना संभव है।<ref>{{Cite journal | last1 = Franco | first1 = D. G. B. | last2 = Steiner | first2 = M. T. A. | last3 = Assef | first3 = F. M. | doi = 10.1016/j.jclepro.2020.125353 | title = Optimization in waste landfilling partitioning in Paraná State, Brazil | journal = Journal of Cleaner Production | volume = 283 | year = 2020 | page = 125353 | s2cid = 229429742 }}</ref>
+===क्लस्टरिंग===
+क्लस्टर विश्लेषण समस्याओं के एक विशेष उपसमूह को सुविधा स्थान समस्याओं के रूप में देखा जा सकता है। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, उद्देश्य विभाजन करना है <math> n </math> डेटा बिंदुओं (एक सामान्य मीट्रिक स्थान के तत्व) को समतुल्य वर्गों में - जिन्हें प्रायः रंग कहा जाता है - जैसे कि एक ही रंग के बिंदु एक दूसरे के निकट हों (समान रूप से, जैसे कि विभिन्न रंगों के बिंदु एक दूसरे से दूर हों)।<ref>{{cite book |last1=Hastie |first1=Trevor |last2=Tibshirani |first2=Robert |last3=Friedman |first3=Jerome |title=सांख्यिकीय सबक के तत्व|date=2009 |publisher=Springer |edition=Second}}</ref>
+यह देखने के लिए कि कोई सेंट्रोइड-आधारित क्लस्टरिंग समस्या को (मीट्रिक) सुविधा स्थान समस्या के रूप में कैसे देख सकता है (परिवर्तन या कम करें पढ़ें), पूर्व में प्रत्येक डेटा बिंदु को बाद में मांग बिंदु (डिमांड पॉइंट) के रूप में देखें। मान लीजिए कि क्लस्टर किया जाने वाला डेटा मीट्रिक स्पेस के तत्व हैं <math> M </math> (उदा. मान लीजिए कि <math> M </math> होना <math> p </math>कुछ निश्चित के लिए -आयामी [[यूक्लिडियन स्थान]] <math> p </math>). हम जिस सुविधा स्थान की समस्या का निर्माण कर रहे हैं, उसमें हम सुविधाओं को इस मीट्रिक स्थान के भीतर किसी भी बिंदु पर रखने की अनुमति देते हैं <math> M </math>; यह अनुमत सुविधा स्थानों के सेट को परिभाषित करता है <math> L </math>. हम लागतों को परिभाषित करते हैं <math> c_{\ell, d} </math> स्थान-मांग बिंदु जोड़े के बीच जोड़ीवार दूरी होना (उदाहरण के लिए, [[मीट्रिक के-केंद्र]] देखें)। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, डेटा को विभाजित किया जाता है <math> k </math> समतुल्य वर्ग (अर्थात रंग) जिनमें से प्रत्येक में एक केन्द्रक होता है। आइए देखें कि हमारी निर्मित सुविधा स्थान समस्या का समाधान भी इस तरह के विभाजन को कैसे प्राप्त करता है। एक व्यवहार्य समाधान एक गैर-रिक्त उपसमुच्चय है <math> L' \subseteq L </math> का <math> k </math> स्थान. हमारी सुविधा स्थान समस्या में इन स्थानों का एक सेट सम्मिलित है <math> k </math> हमारी सेंट्रोइड-आधारित क्लस्टरिंग समस्या में सेंट्रोइड्स। अब, प्रत्येक मांग बिंदु निर्दिष्ट करें <math> d </math> स्थान के लिए <math> \ell^* </math> जो इसकी सर्विसिंग-लागत को कम करता है; अर्थात्, डेटा बिंदु निर्दिष्ट करें <math> d </math> केन्द्रक को <math> \ell^* :=
-===क्लस्टरिंग===
-क्लस्टर विश्लेषण समस्याओं के एक विशेष उपसमूह को सुविधा स्थान समस्याओं के रूप में देखा जा सकता है। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, उद्देश्य विभाजन करना है <math> n </math> डेटा बिंदुओं (एक सामान्य मीट्रिक स्थान के तत्व) को समतुल्य वर्गों में - जिन्हें अक्सर रंग कहा जाता है - जैसे कि एक ही रंग के बिंदु एक दूसरे के करीब हों (समान रूप से, जैसे कि विभिन्न रंगों के बिंदु एक दूसरे से दूर हों)।<ref>{{cite book |last1=Hastie |first1=Trevor |last2=Tibshirani |first2=Robert |last3=Friedman |first3=Jerome |title=सांख्यिकीय सबक के तत्व|date=2009 |publisher=Springer |edition=Second}}</ref>
-यह देखने के लिए कि कोई सेंट्रोइड-आधारित क्लस्टरिंग समस्या को (मीट्रिक) सुविधा स्थान समस्या के रूप में कैसे देख सकता है (परिवर्तन या कम करें पढ़ें), पूर्व में प्रत्येक डेटा बिंदु को बाद में मांग बिंदु के रूप में देखें। मान लीजिए कि क्लस्टर किया जाने वाला डेटा मीट्रिक स्पेस के तत्व हैं <math> M </math> (उदा. चलो <math> M </math> होना <math> p </math>कुछ निश्चित के लिए -आयामी [[यूक्लिडियन स्थान]] <math> p </math>). हम जिस सुविधा स्थान की समस्या का निर्माण कर रहे हैं, उसमें हम सुविधाओं को इस मीट्रिक स्थान के भीतर किसी भी बिंदु पर रखने की अनुमति देते हैं <math> M </math>; यह अनुमत सुविधा स्थानों के सेट को परिभाषित करता है <math> L </math>. हम लागतों को परिभाषित करते हैं <math> c_{\ell, d} </math> स्थान-मांग बिंदु जोड़े के बीच जोड़ीवार दूरी होना (उदाहरण के लिए, [[मीट्रिक के-केंद्र]] देखें)। सेंट्रोइड-आधारित क्लस्टरिंग समस्या में, डेटा को विभाजित किया जाता है <math> k </math> समतुल्य वर्ग (अर्थात रंग) जिनमें से प्रत्येक में एक केन्द्रक होता है। आइए देखें कि हमारी निर्मित सुविधा स्थान समस्या का समाधान भी इस तरह के विभाजन को कैसे प्राप्त करता है। एक व्यवहार्य समाधान एक गैर-रिक्त उपसमुच्चय है <math> L' \subseteq L </math> का <math> k </math> स्थान. हमारी सुविधा स्थान समस्या में इन स्थानों का एक सेट शामिल है <math> k </math> हमारी सेंट्रोइड-आधारित क्लस्टरिंग समस्या में सेंट्रोइड्स। अब, प्रत्येक मांग बिंदु निर्दिष्ट करें <math> d </math> स्थान के लिए <math> \ell^* </math> जो इसकी सर्विसिंग-लागत को कम करता है; अर्थात्, डेटा बिंदु निर्दिष्ट करें <math> d </math> केन्द्रक को <math> \ell^* :=
 \mathrm{arg\,min}_{\ell \in L} \{c_{\ell, d}\} </math> (मनमाने ढंग से संबंध तोड़ें)। यह विभाजन को प्राप्त करता है बशर्ते कि सुविधा स्थान की समस्या की लागत हो <math> c_{\ell, d} </math> परिभाषित किया गया है कि वे सेंट्रोइड-आधारित क्लस्टरिंग समस्या के दूरी फ़ंक्शन की छवियां हैं।

Anonymous

Search

सुविधा स्थान की समस्या: Difference between revisions

Namespaces

More

Page actions

Revision as of 22:34, 9 August 2023

Contents

न्यूनतम सुविधा स्थान