Lexicographic optimization
लेक्सिकोग्राफिक अनुकूलन एक प्रकार का बहु-उद्देश्य अनुकूलन है। सामान्य तौर पर, बहु-उद्देश्य अनुकूलन दो या दो से अधिक उद्देश्य कार्यों के साथ अनुकूलन समस्याओं से संबंधित है जिन्हें एक साथ अनुकूलित किया जाना है। अक्सर, विभिन्न उद्देश्यों को निर्णय लेने वाले के लिए महत्व के क्रम में क्रमबद्ध किया जा सकता है, ताकि वह उद्देश्य सबसे महत्वपूर्ण हो, उद्देश्य अगला सबसे महत्वपूर्ण हो, और इसी तरह। लेक्सिकोग्राफिक अनुकूलन यह मानता है कि निर्णय लेने वाला बहुत कम वृद्धि, यहां तक कि बहुत बड़ी वृद्धि आदि को भी पसंद करता है। इसी तरह, निर्णय लेने वाला बहुत कम वृद्धि, यहां तक कि बहुत बड़ी वृद्धि आदि को भी पसंद करता है। दूसरे शब्दों में, निर्णय लेने वाले की शब्दकोश संबंधी प्राथमिकताएँ होती हैं, जो संभावित समाधानों को उनके वस्तुनिष्ठ कार्य मूल्यों के शब्दकोश क्रम के अनुसार श्रेणीबद्ध करती हैं। लेक्सिकोग्राफिक ऑप्टिमाइजेशन को कभी-कभी प्रीएम्प्टिव ऑप्टिमाइजेशन कहा जाता है, क्योंकि एक उद्देश्य मूल्य में एक छोटी सी वृद्धि कम महत्वपूर्ण उद्देश्य मूल्यों में बहुत बड़ी वृद्धि को रोकती है। उदाहरण के लिए, एक ऐसी कंपनी पर विचार करें जो सुरक्षा को सबसे ऊपर रखती है। यह अपने कर्मचारियों और ग्राहकों की सुरक्षा को अधिकतम करना चाहता है। अधिकतम संभव सुरक्षा प्राप्त करने के अधीन, यह अधिकतम लाभ प्राप्त करना चाहता है। यह फर्म लेक्सिकोग्राफिक अनुकूलन करती है, जहां सुरक्षा को दर्शाती है और लाभ को दर्शाती है। एक अन्य उदाहरण के रूप में, परियोजना प्रबंधन में, पी. ई. आर. टी. नेटवर्क का विश्लेषण करते समय, कोई भी अक्सर औसत पूरा होने के समय को कम करना चाहता है, और इसके अधीन, पूरा होने के समय की भिन्नता को कम करना चाहता है। संकेतन एक लेक्सिकोग्राफिक अधिकतमकरण समस्या को अक्सर इस प्रकार लिखा जाता हैः अधिकतम करने के लिए कार्य कहाँ हैं, सबसे कम से कम महत्वपूर्ण तक क्रमबद्ध; निर्णय चर का वेक्टर है; और व्यवहार्य सेट है-के संभावित मूल्यों का सेट। एक लेक्सिकोग्राफिक न्यूनतम समस्या को समान रूप से परिभाषित किया जा सकता है। एल्गोरिदम लेक्सिकोग्राफिक अनुकूलन समस्याओं को हल करने के लिए कई एल्गोरिदम हैं। सामान्य उद्देश्यों के लिए अनुक्रमिक एल्गोरिथ्म n उद्देश्यों के साथ एक लेक्सिमिन अनुकूलन समस्या को n एकल-उद्देश्य अनुकूलन समस्याओं के अनुक्रम का उपयोग करके हल किया जा सकता है, निम्नानुसारः t = 1 के लिए, n निम्नलिखित एकल-उद्देश्य समस्या को हल करता हैः यदि समस्या अव्यवहारिक या असीमित है, तो रुकें और घोषित करें कि कोई समाधान नहीं है। अन्यथा, इष्टतम समाधान का मान डालें और जारी रखें। तो, पहली पुनरावृत्ति में, हम सबसे महत्वपूर्ण उद्देश्य का अधिकतम व्यवहार्य मूल्य पाते हैं, और इस अधिकतम मूल्य को इसमें डालते हैं। दूसरी पुनरावृत्ति में, हम दूसरे सबसे महत्वपूर्ण उद्देश्य का अधिकतम व्यवहार्य मूल्य पाते हैं, इस अतिरिक्त बाधा के साथ कि सबसे महत्वपूर्ण उद्देश्य को अपना अधिकतम मूल्य रखना चाहिए; और इसी तरह। अनुक्रमिक एल्गोरिथ्म सामान्य है-इसे तब लागू किया जा सकता है जब भी हमारे पास एकल-उद्देश्य कार्यों के लिए समाधानकर्ता हो। रैखिक उद्देश्यों के लिए लेक्सिकोग्राफिक सिम्प्लेक्स एल्गोरिथ्म रैखिक लेक्सिकोग्राफिक अनुकूलन लेक्सिकोग्राफिक अनुकूलन का एक विशेष मामला है जिसमें उद्देश्य रैखिक होते हैं, और व्यवहार्य सेट को रैखिक असमानताओं द्वारा वर्णित किया जाता है। इसे इस प्रकार लिखा जा सकता हैः जहाँ वेक्टर अधिकतम करने के लिए रैखिक उद्देश्यों का प्रतिनिधित्व करते हैं, सबसे कम से कम महत्वपूर्ण तक क्रमबद्ध हैं; निर्णय चर का वेक्टर है; और व्यवहार्य सेट मैट्रिक्स और वेक्टर द्वारा निर्धारित किया जाता है। इसर्मन ने रैखिक प्रोग्रामिंग द्वैत के सिद्धांत को लेक्सिकोग्राफिक रैखिक कार्यक्रमों तक विस्तारित किया, और एक लेक्सिकोग्राफिक सिम्प्लेक्स एल्गोरिथ्म विकसित किया। अनुक्रमिक एल्गोरिथ्म के विपरीत, यह सिम्प्लेक्स एल्गोरिथ्म सभी वस्तुनिष्ठ कार्यों को एक साथ मानता है। रैखिक उद्देश्यों के लिए भारित औसत शेराली और सोयस्टर साबित करते हैं कि, किसी भी रैखिक शब्दकोश अनुकूलन समस्या के लिए, भार का एक समूह मौजूद है जैसे कि शब्दकोश-इष्टतम समाधानों का समूह निम्नलिखित एकल-उद्देश्य समस्या के समाधानों के समूह के समान हैः भार की गणना करने का एक तरीका यागेर द्वारा दिया गया है। वह मानता है कि सभी वस्तुनिष्ठ मान 0 और 1 के बीच वास्तविक संख्याएँ हैं, और किसी भी दो संभावित मानों के बीच सबसे छोटा अंतर कुछ स्थिरांक d <1 है (ताकि d से छोटे अंतर वाले मानों को बराबर माना जाए)। फिर, का वजन लगभग निर्धारित किया जाता है। यह गारंटी देता है कि भारित राशि को अधिकतम करना लेक्सिकोग्राफिक अधिकतमकरण के बराबर है। कोकोसियोनी, पाप्पालार्डो और सर्गेयेव बताते हैं कि, एक ऐसे कंप्यूटर को देखते हुए जो असीम के साथ संख्यात्मक गणना कर सकता है, ऐसे भार चुनना संभव है जो असीम हैं (विशेष रूप सेः; असीम है; असीम-वर्ग है; आदि)। ), और इस प्रकार असीम के साथ एकल-उद्देश्य रैखिक प्रोग्रामिंग के लिए रैखिक शब्दकोश अनुकूलन को कम करें। वे असीम के लिए सिम्प्लेक्स एल्गोरिथ्म का एक अनुकूलन प्रस्तुत करते हैं, और कुछ चल रहे उदाहरण प्रस्तुत करते हैं। गुण (1) विशिष्टता। सामान्य तौर पर, एक शब्दकोश अनुकूलन समस्या में एक से अधिक इष्टतम समाधान हो सकते हैं। हालाँकि, यदि और दो इष्टतम समाधान हैं, तो उनका मूल्य सभी के लिए समान होना चाहिए। इसके अलावा, यदि व्यवहार्य क्षेत्र एक उत्तल समूह है, और वस्तुनिष्ठ कार्य सख्ती से अवतल हैं, तो समस्या का अधिकतम एक इष्टतम समाधान है, क्योंकि यदि दो अलग-अलग इष्टतम समाधान थे, तो उनका माध्य एक और व्यवहार्य समाधान होगा जिसमें वस्तुनिष्ठ कार्य एक उच्च मूल्य प्राप्त करते हैं-जो मूल समाधानों की इष्टतमता का खंडन करता है। (2) आंशिक राशि। 1,., n में सभी t के लिए, सबसे महत्वपूर्ण से लेकर t-th सबसे महत्वपूर्ण तक सभी कार्यों के योग को परिभाषित करें। फिर, मूल शब्दकोश अनुकूलन समस्या निम्नलिखित के बराबर हैः कुछ मामलों में, दूसरी समस्या को हल करना आसान हो सकता है। लेक्सिकोग्राफिक मैक्स-मिन ऑप्टिमाइजेशन लेक्सिकोग्राफिक ऑप्टिमाइजेशन का एक प्रकार है जिसमें सभी उद्देश्य समान रूप से महत्वपूर्ण हैं, और लक्ष्य सबसे छोटे उद्देश्य को अधिकतम करना है, फिर दूसरा सबसे छोटा उद्देश्य, और इसी तरह। खेल सिद्धांत में, न्यूक्लियोलस को एक लेक्सिकोग्राफिक-न्यूनतम समाधान सेट के रूप में परिभाषित किया गया है। संदर्भ बहु-मानदंड निर्णय विश्लेषण अनुकूलन एल्गोरिदम और विधियाँ