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

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

प्रयोज्यता

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

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

परिभाषा

मान लीजिए कि n, m और p धनात्मक पूर्णांक हैं। माना X, Rⁿ का उपसमुच्चय है, मान लीजिए f, g_i, और h_j प्रत्येक i के लिए {1, …, m} में और प्रत्येक j के लिए {1, …, p} में वास्तविक-मूल्यवान फलन हैं, कम से कम एक के साथ f, g_i और h_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

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

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

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

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

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

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

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

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

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

एफ ('एक्स') = एक्स₁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 =* सॉफ्टवेयर

}}