नॉनलाइनियर प्रोग्रामिंग

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

प्रयोज्यता

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

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

परिभाषा

मान लीजिए कि n, m और p धनात्मक पूर्णांक हैं। माना X, R का उपसमुच्चय हैⁿ, मान लीजिए f, g_i, और वह_jकम से कम एक f, g के साथ {1, …, m} में प्रत्येक i और {1, …, p} में प्रत्येक j के लिए X पर वास्तविक-मूल्यवान कार्य करें_i, और वह_jअरैखिक होना।

एक गैर-रैखिक न्यूनीकरण समस्या प्रपत्र की एक अनुकूलन समस्या है

${\begin{aligned}{\text{minimize }}&f(x)\\{\text{subject to }}&g_{i}(x)\leq 0{\text{ for each }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ for each }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}$

एक गैर-रैखिक अधिकतमकरण समस्या को इसी तरह परिभाषित किया गया है।

संभावित प्रकार की बाधा सेट

बाधा सेट की प्रकृति के लिए कई संभावनाएं हैं, जिन्हें व्यवहार्य सेट या व्यवहार्य क्षेत्र भी कहा जाता है।

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

एक व्यवहार्य समस्या वह है जिसके लिए सभी बाधाओं को संतुष्ट करने वाले विकल्प चर के लिए मूल्यों का कम से कम एक सेट मौजूद है।

एक असीमित समस्या एक व्यवहार्य समस्या है जिसके लिए उद्देश्य फलन को किसी दिए गए परिमित मान से बेहतर बनाया जा सकता है। इस प्रकार कोई इष्टतम समाधान नहीं है, क्योंकि हमेशा एक व्यवहार्य समाधान होता है जो किसी दिए गए प्रस्तावित समाधान से बेहतर उद्देश्य फ़ंक्शन मान देता है।

समस्या को हल करने के तरीके

यदि उद्देश्य फ़ंक्शन अवतल फ़ंक्शन (अधिकतमकरण समस्या), या उत्तल फ़ंक्शन (न्यूनतम समस्या) है और बाधा सेट उत्तल सेट है, तो प्रोग्राम को उत्तल कहा जाता है और अधिकांश मामलों में उत्तल अनुकूलन से सामान्य तरीकों का उपयोग किया जा सकता है।

यदि उद्देश्य फलन द्विघात फलन है और व्यवरोध रैखिक हैं, तो द्विघात प्रोग्रामिंग तकनीकों का उपयोग किया जाता है।

यदि उद्देश्य फ़ंक्शन अवतल और उत्तल फ़ंक्शन (अधिकतमकरण मामले में) का अनुपात है और बाधाएं उत्तल हैं, तो समस्या को आंशिक प्रोग्रामिंग तकनीकों का उपयोग करके उत्तल अनुकूलन समस्या में परिवर्तित किया जा सकता है।

असमतल समस्याओं को हल करने के लिए कई विधियाँ उपलब्ध हैं। एक दृष्टिकोण रैखिक प्रोग्रामन समस्याओं के विशेष योगों का उपयोग करना है। एक अन्य विधि में शाखा और बाध्य तकनीकों का उपयोग शामिल है, जहां उत्तल (न्यूनीकरण समस्या) या रैखिक सन्निकटन के साथ हल करने के लिए कार्यक्रम को उपवर्गों में विभाजित किया जाता है जो उपखंड के भीतर समग्र लागत पर एक निचली सीमा बनाते हैं। बाद के विभाजनों के साथ, किसी बिंदु पर एक वास्तविक समाधान प्राप्त किया जाएगा जिसकी लागत किसी भी अनुमानित समाधान के लिए प्राप्त सर्वोत्तम निचली सीमा के बराबर है। यह समाधान इष्टतम है, हालांकि संभवतः अद्वितीय नहीं है। एल्गोरिथम को भी जल्दी रोका जा सकता है, इस आश्वासन के साथ कि सबसे अच्छा संभव समाधान सबसे अच्छे बिंदु से सहनशीलता के भीतर है; ऐसे बिंदुओं को ε-इष्टतम कहा जाता है। परिमित समाप्ति सुनिश्चित करने के लिए ε-इष्टतम बिंदुओं को समाप्त करना आम तौर पर आवश्यक है। यह बड़ी, कठिन समस्याओं और अनिश्चित लागत या मूल्यों वाली समस्याओं के लिए विशेष रूप से उपयोगी है जहां अनिश्चितता का अनुमान उचित विश्वसनीयता अनुमान के साथ लगाया जा सकता है।

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

संख्यात्मक उदाहरण

द्वि-आयामी उदाहरण

नीला क्षेत्र संभव क्षेत्र है। संभव क्षेत्र के साथ रेखा की स्पर्शरेखा समाधान का प्रतिनिधित्व करती है। रेखा सर्वश्रेष्ठ प्राप्त करने योग्य समोच्च रेखा है (उद्देश्य फ़ंक्शन के दिए गए मान के साथ लोकस)।

एक साधारण समस्या (आरेख में दिखाया गया) बाधाओं द्वारा परिभाषित किया जा सकता है

एक्स₁ ≥ 0

एक्स₂ ≥ 0

एक्स₁² + एक्स₂² ≥ 1

एक्स₁² + एक्स₂² ≤ 2

अधिकतम करने के लिए एक उद्देश्य समारोह के साथ

एफ ('एक्स') = एक्स₁ + एक्स₂

जहाँ x = (x₁, एक्स₂).

3-आयामी उदाहरण

केंद्र में विवश स्थान के साथ शीर्ष सतह की स्पर्शरेखा समाधान का प्रतिनिधित्व करती है।

एक और सरल समस्या (आरेख देखें) बाधाओं द्वारा परिभाषित की जा सकती है

एक्स₁² − x₂² + एक्स₃² ≤ 2

एक्स₁² + एक्स₂² + एक्स₃² ≤ 10

अधिकतम करने के लिए एक उद्देश्य समारोह के साथ

एफ ('एक्स') = एक्स₁x₂ + एक्स₂x₃

जहाँ x = (x₁, एक्स₂, एक्स₃).

यह भी देखें

• वक्र फिटिंग
• कम से कम वर्गों
• रैखिक प्रोग्रामिंग
• एनएल (प्रारूप)
• अरेखीय कम से कम वर्ग
• अनुकूलन सॉफ्टवेयर की सूची
• द्विघात रूप से विवश द्विघात प्रोग्रामिंग
• वर्नर सौंफ, जिन्होंने अरैखिक प्रोग्रामिंग के लिए नींव तैयार की

अग्रिम पठन

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882.
• Luenberger, David G.; Ye, Yinyu (2008). Linear and nonlinear programming. International Series in Operations Research & Management Science. Vol. 116 (Third ed.). New York: Springer. pp. xiv+546. ISBN 978-0-387-74502-2. MR 2423726.
• Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
• Jan Brinkhuis and Vladimir Tikhomirov, Optimization: Insights and Applications, 2005, Princeton University Press

बाहरी संबंध

• Mathematical Programming Glossary

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}