रैखिक क्रमादेशन: Difference between revisions

Revision as of 12:58, 4 December 2022

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

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

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

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

रैखिक क्रमादेशन में ऐसी समस्याएं हैं जिन्हें विहित रूप में व्यक्त किया जा सकता है,

{\begin{aligned}&{\text{Find a vector}}&&\mathbf {x} \\&{\text{that maximize}}&&\mathbf {c} ^{T}\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{and}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}

यहाँ पर x के घटक को निर्धारित किए जाने वाले चर हैं, c और b सदिश दिए गए हैं ( $\mathbf {c} ^{T}$ द्वारा यह दर्शाया गया है कि c के गुणांक का प्रयोग आव्यूह उत्पाद के निर्माण के प्रयोजन हेतु एकल पंक्ति आव्यूह के रूप में किया जाता है), और A दिया गया आव्यूह (गणित) है। फलन जिसका मान अधिकतम या न्यूनतम किया जाना है ( $\mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x}$ इस स्थिति में ) उसको उद्देश्य फलन कहा जाता है। असमिकाएँ Ax ≤ b और x ≥ 0 ऐसी व्यवरोधएँ हैं जो एक उत्तल पॉलीटॉप निर्दिष्ट करती हैं जिसके ऊपर उद्देश्य फलन को अनुकूलित किया जाता है। इस संदर्भ में, दो सदिश तुलनीय हैं जब उनके पास समान आयाम होते हैं। अगर पहले में प्रत्येक प्रविष्टि दूसरे में संबंधित प्रविष्टि से कम या बराबर होती है, तो यह कहा जा सकता है कि पहले सदिश दूसरी सदिश से कम या बराबर है।

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

इतिहास

लियोनिद कांटोरोविच

जॉन वॉन न्यूमैन

रैखिक असमिका की एक प्रणाली को हल करने की समस्या कम से कम फूरियर तक है, जिन्होंने 1827 में उन्हें हल करने के लिए एक विधि प्रकाशित की थी,^[1] और बाद में जिसे फूरियर मोटाकिन उन्मूलन की विधि का नाम दिया गया था।

1939 में एक ऐसी समस्या का रैखिक क्रमादेशन निरूपण जो सामान्य रैखिक क्रमादेशन समस्या के समतुल्य है, सोवियत संघ के गणितज्ञ और अर्थशास्त्री लियोनिद कांटोरोविच ने दिया था, जिन्होंने इसको हल करने के लिए भी एक तरीका प्रस्थापित किया था।^[2] यह एक तरीका है जिसे उन्होंने द्वितीय विश्व युद्ध के दौरान विकसित किया, सेना की लागत कम करने और शत्रु पर लगाये गये हानियों को बढ़ाने के लिए व्ययों और वापसी की योजना बनाने का एक तरीका है।^{[citation needed]} कांटोरोविच का काम शुरू में यूएसएसआर में उपेक्षित था।^[3] लगभग उसी समय कांटोरोविच के रूप में,डच अमेरिकन अर्थशास्त्री टी. सी. कोआपंस ने रैखिक क्रमादेशन के रूप में शास्त्रीय आर्थिक समस्याओं का निर्माण किया। कंटोरोविच और कूपमैन ने बाद में अर्थशास्त्र में 1975 का नोबेल पुरस्कार साझा किया।^[1] सन 1941 में फ्रांक लॉरेन हिचकॉक ने परिवहन समस्याओं को रैखिक क्रमादेशन के रूप में भी तैयार किया और इसमें बाद के सिंप्लेक्स विधि के समान समाधान दिया।^[2] 1957 में हैचकॉक की मृत्यु हो गई थी और नोबेल पुरस्कार मरणोपरांत नहीं दिया गया था।

1946 से 1947 तक जॉर्ज बी. डेंटजिग ने संयुक्त राज्य अमेरिका की वायुसेना में आयोजित समस्याओं के लिए उपयोग किए जाने वाले सामान्य रैखिक क्रमादेशन सूत्रीकरण का स्वतंत्र रूप से विकास किया।^[4] 1947 में, डेंटज़िग ने सिम्पलेक्स विधि का भी आविष्कार किया, जो कि, पहली बार कुशलता से, ज्यादातर स्थितियों में रैखिक क्रमादेशन समस्या का समाधान किया।^[4] जब डेंटजिग ने जॉन वॉन न्यूमैन के साथ उनकी सिम्पलेक्स विधि पर चर्चा करने के लिए एक बैठक की व्यवस्था की, न्यूमैन ने तत्काल द्वैत के सिद्धांत का अनुमान लगाया कि खेल के सिद्धांत में जो समस्या वह काम कर रहा था वह बराबर है।^[4] डेंटजिग ने 5 जनवरी, 1948 को एक अप्रकाशित रिपोर्ट "रैखिक असमिकाओं पर एक प्रमेय" में औपचारिक प्रमाण प्रदान किया।^[3] डेंटज़िग का काम 1951 में जनता के लिए उपलब्ध कराया गया था। युद्धोपरांत के वर्षों में, अनेक उद्योगों ने इसे अपने दैनिक नियोजन में लागू किया।

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

रैखिक क्रमादेशन समस्या को पहली बार 1979 में लियोनिड खाचियान द्वारा बहुपद समय में व्याख्या करने योग्य दिखाया गया था,^[5] परंतु इस क्षेत्र में एक व्यापक सैद्धांतिक और आभ्यासिक सफलता 1984 में मिली, जब नरेंद्र करमरकर ने रैखिक-क्रमादेशन समस्याओं के समाधान के लिए एक नई आंतरिक-बिंदु विधि शुरू की।^[6]

उपयोग

रैखिक क्रमादेशन, कई कारणों से अनुकूलन के व्यापक रूप से प्रयुक्त क्षेत्र है। संचालन अनुसंधान में कई आभ्यासिक समस्याओं को रैखिक क्रमादेशन समस्याओं के रूप में व्यक्त किया जा सकता है।^[3] रैखिक क्रमादेशन के कुछ विशेष स्थिति, जैसे कि नेटवर्क प्रवाह समस्याएँ और बहु-कमोडिटी प्रवाह समस्या, विशेष एल्गोरिथ्म पर काफी अनुसंधान करने के लिए काफी महत्वपूर्ण माने जाते हैं। अन्य प्रकार के अनुकूलन समस्याओं के लिए कुछ एल्गोरिथ्म, रैखिक क्रमादेशन समस्याओं को उप-समस्याओं के रूप में हल करके काम करता है। ऐतिहासिक रूप से, रैखिक क्रमादेशन के विचारों ने अनुकूलन सिद्धांत की कई केंद्रीय अवधारणाओं को प्रेरित किया है, जैसे द्वैत, अपघटन, और उत्तलता के महत्व और इसके सामान्यीकरण इसी तरह, रैखिक क्रमादेशन सूक्ष्मअर्थशास्त्र के प्रारंभिक गठन में भारी उपयोग किया गया था, और यह वर्तमान में कंपनी प्रबंधन, जैसे योजना, उत्पादन, परिवहन, और प्रौद्योगिकी में उपयोग किया जाता है। चूंकि आधुनिक प्रबंधन के मुद्दे कभी भी बदल रहे हैं, अधिकांश कंपनियां सीमित संसाधनों से लाभ को अधिकतम और लागत को कम करना चाहेंगी। गूगल यूट्यूब विडियो को स्थिर करने के लिए रैखिक क्रमादेशन भी प्रयोग करता है।^[7]

मानक रूप

मानक रूप, रैखिक क्रमादेशन समस्या का वर्णन करने का एक सामान्य और सबसे सहज रूप होता है। इसमें निम्न तीन भाग होते हैं:

एक रैखिक फलन को अधिकतम किया जाना

जैसे

f(x_{1},x_{2})=c_{1}x_{1}+c_{2}x_{2}

निम्नलिखित रूप की समस्या व्यवरोध

जैसे

{\begin{matrix}a_{11}x_{1}+a_{12}x_{2}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}&\leq b_{2}\\a_{31}x_{1}+a_{32}x_{2}&\leq b_{3}\\\end{matrix}}

ऋणेतर-संख्या चर

जैसे

{\begin{matrix}x_{1}\geq 0\\x_{2}\geq 0\end{matrix}}

समस्या सामान्यतः आव्यूह (गणित) के रूप में व्यक्त की जाती है, और फिर बन जाती है:

\max\{\,\mathbf {c} ^{\mathrm {T} }\mathbf {x} \mid \mathbf {x} \in \mathbb {R} ^{n}\land A\mathbf {x} \leq \mathbf {b} \land \mathbf {x} \geq 0\,\}

अन्य रूपों, जैसे कि न्यूनतमीकरण समस्याएं, वैकल्पिक रूपों पर व्यवरोध वाली समस्याएं, और नकारात्मक चर (क्रमादेशन) को सम्मिलित करने वाली समस्याओं को हमेशा मानक रूप में एक समान समस्या में लिखा जा सकता है।

उदाहरण

मान लीजिए कि एक किसान के पास कृषि भूमि का एक टुकड़ा है, जो L कि.मी² है, गेहूं या जौ या फिर दोनों के संयोजन के साथ लगाया जाना। किसान के पास सीमित मात्रा में उर्वरक, F किलोग्राम और कीटनाशक, P किलोग्राम है। गेहूं के हर वर्ग किलोमीटर में F₁ किलोग्राम उर्वरक और P₁ किलोग्राम कीटनाशक की आवश्यकता होती है, जबकि जौ के प्रत्येक वर्ग किलोमीटर में F₂ किलोग्राम उर्वरक और P₂ किलोग्राम कीटनाशक की आवश्यकता होती है। मान लीजिए S₁ प्रति वर्ग किलोमीटर गेहूं का विक्रय मूल्य है, और S₂ जौ का विक्रय मूल्य है। अगर हम क्रमशः x₁ और x₂ द्वारा गेहूं और जौ के साथ लगाए गए भूमि के क्षेत्र को दर्शाते हैं, तो x₁ और x₂ के लिए इष्टतम मान चुनकर लाभ को अधिकतम किया जा सकता है। इस समस्या को मानक रूप में निम्नलिखित रैखिक क्रमादेशन समस्या के साथ व्यक्त किया जा सकता है:

अधिकतम: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(राजस्व को अधिकतम करें (कुल गेहूं की बिक्री और कुल जौ की बिक्री) – राजस्व "उद्देश्य फलन" है)
विषय है:	$x_{1}+x_{2}\leq L$	(कुल क्षेत्र पर सीमा)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F$	(उर्वरक की सीमा)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P$	(कीटनाशक पर सीमा)
	$x_{1}\geq 0,x_{2}\geq 0$	(एक नकारात्मक क्षेत्र नहीं लगा सकते).

आव्यूह रूप में यह बन जाता है:

अधिकतम

{\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}

विषय है

{\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq {\begin{bmatrix}0\\0\end{bmatrix}}.

संवर्धित रूप (शिथिल रूप)

सिम्प्लेक्स एल्गोरिथ्म के सामान्य रूप को लागू करने के लिए रैखिक क्रमादेशन समस्याओं को संवर्धित फार्म में परिवर्तित किया जा सकता है। इस प्रपत्र में व्यवरोधओं में समानता के साथ असमानताओं को बदलने के लिए ऋणेतर-संख्या शिथिल चर का परिचय है। तब समस्याओं को निम्न ब्लॉक आव्यूह रूप में लिखा जा सकता है:

अधिकतम

z

:

{\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}

\mathbf {x} \geq 0,\mathbf {s} \geq 0

जहां $\mathbf {s}$ नव प्रवर्तित निम्न शिथिल चर हैं, $\mathbf {x}$ निर्णय चर हैं, और $z$ अधिकतम किया जाने वाला चर है।

उदाहरण

ऊपर दिए गए उदाहरण को निम्नलिखित संवर्धित रूप में परिवर्तित किया गया है:

अधिकतम: $S_{1}\cdot x_{1}+S_{2}\cdot x_{2}$		(उद्देश्य फलन)
विषय है:	$x_{1}+x_{2}+x_{3}=L$	(संवर्धित व्यवरोध)
	$F_{1}\cdot x_{1}+F_{2}\cdot x_{2}+x_{4}=F$	(संवर्धित व्यवरोध)
	$P_{1}\cdot x_{1}+P_{2}\cdot x_{2}+x_{5}=P$	(संवर्धित व्यवरोध)
	$x_{1},x_{2},x_{3},x_{4},x_{5}\geq 0.$

जहां $x_{3},x_{4},x_{5}$ (ऋणेतर-संख्या) शिथिल चर हैं, जो इस उदाहरण में अप्रयुक्त क्षेत्र, अप्रयुक्त उर्वरक की मात्रा और अप्रयुक्त कीटनाशक की मात्रा का प्रतिनिधित्व करते हैं।

आव्यूह रूप में यह बन जाता है:

अधिकतम

z

:

{\begin{bmatrix}1&-S_{1}&-S_{2}&0&0&0\\0&1&1&1&0&0\\0&F_{1}&F_{2}&0&1&0\\0&P_{1}&P_{2}&0&0&1\\\end{bmatrix}}{\begin{bmatrix}z\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}={\begin{bmatrix}0\\L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\end{bmatrix}}\geq 0.

द्वैत

प्रत्येक रैखिक क्रमादेशन समस्या, जिसे मूल समस्या कहा जाता है, जिसको द्वैत समस्या में परिवर्तित किया जा सकता है, जो मूल समस्या के इष्टतम मूल्य के लिए एक ऊपरी बाध्य प्रदान करता है। आव्यूह रूप में, हम मूल समस्या को इस रूप में व्यक्त कर सकते हैं:

अधिकतम c^Tx का विषय है Ax ≤ b, x ≥ 0;

इसी सममित द्वैत समस्या के साथ,

न्यूनतम b^Ty का विषय है A^Ty ≥ c, y ≥ 0.

एक वैकल्पिक प्रारंभिक सूत्रीकरण है:

अधिकतम c^Tx का विषय है Ax ≤ b;

संबंधित असममित द्वैत समस्या के साथ,

न्यूनतम b^Ty का विषय है A^Ty ≥ c, y ≥ 0.

द्वैत सिद्धांत के दो मौलिक विचार हैं। एक तथ्य है कि (सममित द्वैत के लिए) एक द्वैत रैखिक क्रमादेशन का मूल रैखिक क्रमादेशन है। इसके अलावा, रैखिक क्रमादेशन का हर सुसंगत हल यह है कि वह इस द्वैती फलन के अनुकूलतम प्रकार्य के इष्टतम मान को बाध्य करता है। दुर्बल द्वैत प्रमेय का मत है कि द्वैत के आभ्यासिक मान का किसी भी आभ्यासिक हल में वस्तुनिष्ठ फलन मान किसी भी आभ्यासिक समाधान में आदि की तुलना में बड़ा या बराबर होता है। प्रबल द्वैत प्रमेय के अनुसार, यदि मूल में इष्टतम विलयन होता है, तो x^*, तो द्वैत भी एक इष्टतम समाधान है, y^**, और cTx*=bTy*

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

विविधताएं

द्वैत को ढंकना/पैक करना।

आवरण एलपी प्रपत्र का एक रैखिक क्रमादेशन है:

न्यूनतम: b^Ty,

विषय है: A^Ty ≥ c, y ≥ 0,

जैसे कि आव्यूह ए और सदिश बी और सी ऋणेतर-संख्या हैं।

आवरण एलपी का द्वैती एक पैकिंग एलपी है, जो कि प्रपत्र का एक रैखिक क्रमादेशन है:

अधिकतम c^Tx,

विषय है: Ax ≤ b, x ≥ 0,

जैसे कि आव्यूह ए और सदिश बी और सी ऋणेतर-संख्या हैं।

उदाहरण

ढ़कने और पैकिंग एलपीएस सामान्यतः एक रैखिक क्रमादेशन समस्या के रूप में उत्पन्न होते हैं और सन्निकटन एल्गोरिथ्म के अध्ययन में महत्वपूर्ण होते हैं।^[8] उदाहरण के लिए, समुच्चय पैकिंग समस्या के एल. पी. छूट, स्वतंत्र समुच्चय समस्या और मिलान समस्या एलपीएस पैक कर रही है। समुच्चय कवर समस्या के एलपी छूट शिरोबिंदु आवरण समस्या, और लंबित समुच्चय समस्या भी एलपीएस को कवर कर रहे हैं।

ग्राफ का भिन्नात्मक रंग ढूँढना आच्छादी एलपी का एक अन्य उदाहरण है। इस स्थिति में एक व्यवरोध ग्राफ के प्रत्येक शीर्ष के लिए और एक चर के लिए ग्राफ के प्रत्येक स्वतंत्र समुच्चय के लिए है।

पूरक शिथिलता

जब प्रथम के अनुकूलतम समाधान को पूरक शिथिलता प्रमेय के प्रयोग से ही जाना जाता है तो इस द्वैती इष्टतम समाधान को प्राप्त करना संभव होता है। प्रमेय कहता है:

मान लीजिए x = (x1, x2,…, एक्सएन) प्राथमिक सुसंगत है और वह y = (y1, y2,…, ym) द्वैत सुसंगत है। मानलो की (w1, w2,…, डब्ल्यूएम) इसी प्राथमिक शिथिल चर को दर्शाता है, और मानलो (z1, z2, ... , zn) संगत द्वैती शिथिल चर को निरूपित करते हैं। तब x और y उनकी संबंधित समस्याओं के लिए इष्टतम हैं यदि और केवल यदि

x_j z_j = 0, के लिए j = 1, 2, ... , n, और
w_i y_i = 0, के लिए i = 1, 2, ... , m.

इसलिए यदि प्रारंभिक का i-th शिथिल चर शून्य नहीं है, तो द्वैती का i-th चर शून्य के बराबर है। इसी तरह, यदि द्वैती का j-th शिथिल चर शून्य नहीं है, तो प्रारंभिक का j-th चर शून्य के बराबर है।

अनुकूलतम अर्थव्यवस्था की यह आवश्यक शर्त काफी सरल आर्थिक सिद्धांत को दर्शाती है। मानक रूप में (अधिकतम करते समय), अगर एक विवश प्राथमिक संसाधन में शिथिल है (यानी, "बचे हुए" हैं), फिर उस संसाधन की अतिरिक्त मात्रा का कोई मूल्य नहीं होना चाहिए। इसी तरह, यदि द्वैत (छाया) कीमत में ऋणेतर-संख्याता व्यवरोध आवश्यकता में कमी है, यानी कीमत शून्य नहीं है, तो वहाँ दुर्लभ आपूर्ति (कोई "बचा नहीं" होना चाहिए)।

सिद्धांत

इष्टतम समाधानों का अस्तित्व

ज्यामितीय दृष्टि से, रैखिक व्यवरोधएं सुसंगत क्षेत्र को परिभाषित करती हैं, जो उत्तल बहुफलक है। रैखिक प्रकार्य, एक उत्तल फलन है, जिसका अर्थ है कि प्रत्येक स्थानीय न्यूनतम वैश्विक न्यूनतम होता है; इसी तरह रैखिक प्रकार्य भी अवतल ही होता है, जिसका अर्थ है कि प्रत्येक स्थानीय अधिकतम एक वैश्विक अधिकतम है।

एक इष्टतम समाधान की आवश्यकता नहीं है, दो कारणों से सबसे पहले, यदि व्यवरोधएँ असंगत हैं, तो कोई संभव समाधान मौजूद नहीं है: उदाहरण के लिए व्यवरोधओं x ≥ 2 और x ≤ 1 संयुक्त रूप से संतुष्ट नहीं किया जा सकता है; इस स्थिति में, हम कहते हैं कि एलपी अक्षम्य है। दूसरा, जब बहुटोपी वस्तुनिष्ठ प्रकार्य की प्रवणता की दिशा में असीम होता है (जहाँ वस्तुनिष्ठ फलन की प्रवणता वस्तुनिष्ठ फलन के गुणांकों का सदिश है), तब कोई इष्टतम मान प्राप्त नहीं होता है क्योंकि उद्देश्य फलन के किसी परिमित मान से बेहतर करना हमेशा संभव होता है।

बहुफलक के इष्टतम शीर्ष (और किरणें)

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

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

एल्गोरिथम

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

आधार विनिमय एल्गोरिथम

डेंटज़िग की सिंप्लेक्स एल्गोरिथम

1947 में जॉर्ज डेंट्ज़िग द्वारा विकसित सिंप्लेक्स एल्गोरिथम, एलपी समस्याओं को पॉलिटोपे के शीर्ष पर सुसंगत समाधान के निर्माण द्वारा हल करता है और फिर पॉलीटोपे के कोर पर एक पथ के साथ वस्तुनिष्ठ फलन के गैरघटते मूल्यों के शीर्ष पर चलना जब तक निश्चित रूप से अधिकतम नहीं पहुंच जाता है। कई आभ्यासिक समस्याओं में, "स्टॉलिंग" होता है: कई पिवोट्स उद्देश्य फलन में कोई वृद्धि के साथ किए जाते हैं।^[9]^[10] दुर्लभ आभ्यासिक समस्याओं में, सिम्प्लेक्स एल्गोरिथम के सामान्य संस्करण वास्तव में "चक्र" हो सकते हैं।^[10] चक्रों से बचने के लिए शोधकर्ताओं ने मतदान के नए नियम बनाये।^[11]

प्रयोग में, सिम्पलेक्स एल्गोरिथम काफी कुशल है और अगर चक्र चलाने के खिलाफ कुछ सावधानियां बरती जाएं तो वैश्विक इष्टतम खोजने की गारंटी दी जा सकती है। सिम्पलेक्स एल्गोरिथम "यादृच्छिक" समस्याओं को कुशलता से हल करने के लिए सिद्ध हुआ है, अर्थात चरणों की एक घन संख्या में, ^[12] जो आभ्यासिक समस्याओं पर अपने व्यवहार के समान है।^[9]^[13]

चूकि, सिम्पलेक्स एल्गोरिथम में यह सबसे खराब करने वाली स्थिति है: क्ले और मिन्टी ने रैखिक क्रमादेशन समस्याओं के एक परिवार का निर्माण किया, जिसके लिए सिंप्लेक्स विधि समस्या के आकार में कई चरणों की गणना की।^[9]^[14]^[15] वास्तव में, कुछ समय के लिए यह ज्ञात नहीं था कि क्या रैखिक क्रमादेशन समस्या बहुपद समय में व्याख्या करने योग्य था, वास्तव में, कुछ समय के लिए यह ज्ञात नहीं था कि क्या रैखिक क्रमादेशन समस्या बहुपद समय में व्याख्या करने योग्य थी, यानी पी (जटिलता) वर्ग।

क्रिस-क्रॉस एल्गोरिथम

डेंटज़िग के सिंप्लेक्स एल्गोरिथम की तरह, क्रिस-क्रॉस एल्गोरिथम एक आधार-विनिमय एल्गोरिथम है जो आधारों के बीच पिवट करता है। चूंकि, क्रॉस क्रॉस एल्गोरिथम को सुसंगतता बनाए रखने की आवश्यकता नहीं है, बल्कि एक सुसंगत आधार से एक अक्षम्य आधार पर धुरी कर सकता है। क्रस-क्रॉस एल्गोरिथ्म में रैखिक क्रमादेशन के लिए बहुपदीय समय की जटिलता नहीं होती है। दोनों एल्गोरिथम आयाम D में एक (परेशान)इकाई घन के सभी 2^D कोनों पर जाते हैं, क्ले-मिन्टी क्यूब, सबसे खराब स्थिति में है।^[11]^[16]

आंतरिक बिंदु

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

खाचियां के बाद दीर्घवृत्ताभ एल्गोरिथम

रैखिक क्रमादेशन के लिए यह अब तक का सबसे खराब स्थिति वाला बहुपद-समय एल्गोरिथम है। एक समस्या है जो n चर है हल करने के लिए और L इनपुट बिट्स में एन्कोडेड किया जा सकता है, यह एल्गोरिथ्म $O(n^{6}L)$ समय में चलता है।^[5] लियोनिद खाचियान ने 1979 में दीर्घवृत्ताभ पद्धति की शुरुआत के साथ इस लंबे समय से चली आ रही जटिलता के मुद्दे को हल किया।अभिसरण विश्लेषण में (वास्तविक संख्या) पूर्ववर्ती हैं, विशेष रूप से Naum Z.Shore द्वारा विकसित पुनरावृत्ति विधियाँ और Arkadi Nemirovski और D. Yudin द्वारा सन्निकटन एल्गोरिथम।

कर्मकार का प्रक्षेपी एल्गोरिथम

रैखिक क्रमादेशनों की बहुपद-समय विलेयता स्थापित करने के लिए खाचियां की एल्गोरिथ्म ऐतिहासिकता को महत्व दी थी। एल्गोरिथ्म एक अभिकलनी ब्रेक-थ्रू नहीं था, एक सिंप्लेक्स विधि रैखिक क्रमादेशनों के विशेष रूप से निर्मित परिवारों के अलावा सभी के लिए अधिक कुशल है।

चूंकि, खाचियां की एल्गोरिथ्म ने रैखिक क्रमादेशन में अनुसंधान की नई पंक्तियों को प्रेरित किया। 1984 में, एन.कर्मरकर ने रैखिक क्रमादेशन के लिए एक प्रक्षेपी विधि प्रस्तावित की। कारमार्कर की एल्गोरिथ्म^[6] से खाचियां^[5] की सबसे खराब बहुपद बाउंड में सुधार हुआ और (दिया $O(n^{3.5}L)$ ). कारमार्कर ने दावा किया कि उनके एल्गोरिथ्म सिंप्लेक्स विधि की तुलना में आभ्यासिक एलपी में बहुत तेज थे, एक दावा जिसने इंटीरियर-पॉइंट विधियों में बहुत रुचि पैदा की।^[17] कर्मकार की खोज के बाद से, कई आंतरिक-बिंदु विधियों का प्रस्ताव और विश्लेषण किया गया है।

वैद्य की 87 एल्गोरिथ्म

1987 में वैद्य ने एक एल्गोरिथ्म भी प्रस्तावित किया जो $O(n^{3})$ समय में चलता है।^[18]

वैद्य की 89 एल्गोरिथ्म

1989 में वैद्य ने एक अल्गोरिथ्म विकसित किया जो $O(n^{2.5})$ समय में चलता है।^[19] औपचारिक रूप से, एल्गोरिथ्म सबसे खराब स्थिति में $O((n+d)^{1.5}nL)$ अंकगणितीय संचालन लेता है, जहां $d$ व्यवरोधओं की संख्या है, $n$ चर की संख्या है, और $L$ बिट्स की संख्या है।

इनपुट स्पार्सिटी टाइम एल्गोरिथम

2015 में, ली और सिद्फोर्ड ने दिखाया कि, इसे में हल किया जा सकता है ${\tilde {O}}((nnz(A)+d^{2}){\sqrt {d}}L)$ समय में^[20], जहां $nnz(A)$ गैर शून्य तत्वों की संख्या का प्रतिनिधित्व करता है, और यह सबसे खराब स्थिति में $O(n^{2.5}L)$ लेता रहता है।

वर्तमान आव्यूह गुणन समय एल्गोरिथ्म

2019 में, कोहेन, ली और सॉन्ग ने रनिंग टाइम को ${\tilde {O}}((n^{\omega }+n^{2.5-\alpha /2}+n^{2+1/6})L)$ समय में सुधार किया, $\omega$ आव्यूह गुणन का घातांक है और $\alpha$ आव्यूह गुणन का द्वैती घातांक है।^[21] α को (मोटे तौर पर) सबसे बड़ी संख्या के रूप में परिभाषित किया गया है जैसे कि एक $n\times n$ आव्यूह को $n\times n^{\alpha }$ आव्यूह द्वारा $O(n^{2})$ समय में गुणा किया जा सकता है। ली, सोंग और झांग द्वारा अनुवर्ती कार्य में, ये भिन्न पद्धति से एक ही परिणाम देते हैं।^[22] ये दो एल्गोरिथम ${\tilde {O}}(n^{2+1/6}L)$ रहते हैं जब ω = 2 और α = 1, जियांग, सोंग, वीनस्टीन और झांग के कारण ${\tilde {O}}(n^{2+1/6}L)$ से ${\tilde {O}}(n^{2+1/18}L)$ में सुधार हुआ।^[23]

आंतरिक-बिंदु विधियों और सिंप्लेक्स एल्गोरिथम की तुलना

वर्तमान राय यह है कि सिप्लेक्स आधारित पद्धतियों तथा आंतरिक बिंदु पद्धतियों के अच्छे कार्यान्वयन की क्षमता रैखिक क्रमादेशन के सामान्य अनुप्रयोगों के लिए समान होती है। चूंकि, एलपी समस्याओं के विशिष्ट प्रकार के लिए, यह हो सकता है कि एक प्रकार का सॉल्वर दूसरे से बेहतर हो (कभी-कभी बहुत बेहतर), और यह कि आंतरिक बिंदु पद्धति बनाम सिम्प्लेक्स आधारित विधियों द्वारा उत्पन्न समाधानों की संरचना, सामान्यतया बाद वाले के लिए सक्रिय चर के समर्थन समुच्चय से बहुत भिन्न होती है।^[24]

खुली समस्याएं और हाल का काम

Unsolved problem in कंप्यूटर विज्ञान:

रैखिक प्रोग्रामिंग एक जोरदार बहुपद समय एल्गोरिथ्म स्वीकार करता है?

(more unsolved problems in कंप्यूटर विज्ञान)

रैखिक क्रमादेशन के सिद्धांत में कई खुली समस्याएं हैं, जिसका समाधान गणित में मूलभूत उपलब्धियों का प्रतिनिधित्व करता है और बड़े पैमाने पर रैखिक क्रमादेशनों को हल करने की हमारी क्षमता में संभावित बड़ी प्रगति का प्रतिनिधित्व करता है।

क्या एलपी दृढ़ता से बहुपद-समय एल्गोरिथम स्वीकार करता है?
क्या एलपी सख्ती से पूरक समाधान खोजने के लिए दृढ़ता से बहुपद-समय एल्गोरिथम स्वीकार करता है?
क्या एलपी गणना के वास्तविक संख्या (इकाई लागत) मॉडल में बहुपद-समय एल्गोरिथम स्वीकार करता है?

21 वीं सदी की 18 सबसे बड़ी अनसुलझी समस्याओं में से स्टीफन स्मेल द्वारा समस्याओं के इस निकट संबंधी समूह का हवाला दिया गया है। स्मेल के शब्दों में, समस्या का तीसरा संस्करण "रैखिक क्रमादेशन सिद्धांत की मुख्य अनसुलझी समस्या है " जबकि एल्गोरिथम कमजोर बहुपद समय में रैखिक क्रमादेशन को हल करने के लिए मौजूद हैं, जैसे दीर्घवृत्ताभ विधियाँ और आंतरिक बिंदु विधि, कोई एल्गोरिथ्म अभी तक नहीं पाया गया है जो व्यवरोधओं की संख्या और चर की संख्या में दृढ़ता से बहुपद समय प्रदर्शन की अनुमति देता है। इस तरह के अल्गोरिथ्म का विकास अत्यंत सैद्धांतिक रुचि का होगा और संभवतः बड़े पैमाने पर एलपी के समाधान में आभ्यासिक लाभ की अनुमति देता है।

हालाँकि हाल ही में उच्च आयामों के लिए हिर्श अनुमान को अस्वीकृत कर दिया गया था, फिर भी यह निम्नलिखित प्रश्नों को खुला छोड़ देता है।

क्या वहां धुरी नियम हैं जो बहुपद समय सिम्प्लेक्स विचरण को जन्म देते हैं?
क्या सभी पॉलीटोपल ग्राफ़ का बहुपद रूप से बाध्य व्यास है?

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

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

सिम्पलेक्स पिवट विधियाँ मौलिक (या द्वैत) सुसंगतता को संरक्षित करती हैं। दूसरी ओर, क्रिस-क्रॉस धुरी विधियां (प्राथमिक या द्वैत) सुसंगतता को संरक्षित नहीं रखती हैं - वे किसी भी क्रम में प्राथमिक सुसंगत, द्वैत या मौलिक और असाध्य आधार पर जा सकते हैं। इस प्रकार की धुराग्र प्रणालियों का 1970 के दशक से अध्ययन किया गया था।^[25] अनिवार्य रूप से, ये विधियाँ रैखिक क्रमादेशन समस्या के तहत व्यवस्था पॉलीटॉप पर सबसे छोटी धुरी पथ खोजने का प्रयास करती हैं। पॉलीटॉपल ग्राफ़ के विपरीत, व्यवस्था पॉलीटोप्स के ग्राफ़ को छोटे व्यास के लिए जाना जाता है, सामान्य बहुपदीय के व्यास के बारे में प्रश्नों के समाधान के बिना प्रबल बहुपद समय क्रिस-क्रॉस धुरी अल्गोरिथ्म की संभावना की अनुमति मिलती है।^[11]

पूर्णांक अज्ञात

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

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

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

पूर्णांक रैखिक क्रमादेशनों को हल करने के लिए उन्नत एल्गोरिथम में शामिल हैं:

कटिंग-समतल विधि
शाखा और बंधन
शाखा और कट
शाखा और मूल्य
यदि इस समस्या के संरचना में कुछ अतिरिक्त है, तो देरी से स्तंभ निर्माण लागू करना संभव हो सकता है।

इस तरह के पूर्णांक-क्रमादेशन एल्गोरिथम पर पैडबर्ग और ब्यासले द्वारा चर्चा की गई है।

इंटीग्रल लीनियर क्रमादेशन

वास्तविक चर में रैखिक क्रमादेशन को अभिन्न कहा जाता है यदि इसमें कम से कम एक इष्टतम समाधान होता है जो अभिन्न है, यानी, केवल पूर्णांक मूल्यों से बना है। इसी तरह, एक बहुध्रुव $P=\{x\mid Ax\geq 0\}$ को अभिन्न माना जाता है यदि सभी बाध्य सुसंगत उद्देश्य कार्यों के लिए सी रैखिक क्रमादेशन $\{\max cx\mid x\in P\}$ इष्टतम है, $x^{*}$ पूर्णांक निर्देशांक के साथ। जैसा कि 1977 में एडमंड्स और जाइल्स द्वारा देखा गया था, इस प्रकार कहा जा सकता है कि बहुध्रुव $P$ अभिन्न है अगर हर बाध्य सुसंगत अभिन्न उद्देश्य फलन सी के लिए, रैखिक क्रमादेशन का इष्टतम मूल्य $\{\max cx\mid x\in P\}$ एक पूर्णांक है।

अभिन्न रैखिक क्रमादेशन संयोजक अनुकूलन के बहुह्यादिक पहलू में केंद्रीय महत्व के होते हैं क्योंकि वे समस्या के वैकल्पिक लक्षण निर्धारण प्रदान करते हैं। किसी भी समस्या के लिए विशेष रूप से, समाधानों के उत्तल पतवार एक एकीकृत बहुफलक है; इस बहुध्रुव के पास यदि बढ़िया/सुसंहत विवरण है तो हम किसी रैखिक उद्देश्य से इष्टतम सुसंगत हल की खोज कर सकते हैं। इसके विपरीत, यदि हम यह साबित कर सकें कि एक रैखिक क्रमादेशन विश्रांति समाकलित है तो यह सुसंगत (अभिन्न) समाधानों के उत्तल पतवार का वांछित वर्णन है।

शब्दावली पूरे साहित्य में सुसंगत नहीं है, इसलिए किसी को निम्नलिखित दो अवधारणाओं में अंतर करने के लिए सावधान रहना चाहिए,

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

यह साबित करने का एक सामान्य तरीका है कि बहुध्रुव अभिन्न है, यह दिखाने के लिए कि यह पूरी तरह से यूनिमॉड्यूलर है। पूर्णांक अपघटन संपत्ति और कुल द्वैत अभिन्नता सहित अन्य सामान्य विधियाँ हैं। अन्य विशिष्ट प्रसिद्ध अभिन्न एलपीएस में मिलान पॉलीटोप, लैटिस बहुफलक, सबमॉड्यूलर प्रवाह बहुफलक शामिल हैं, और दो सामान्यीकृत पॉलीमैट्रोइड्स/जी-पॉलीमेट्रोइड्स का प्रतिच्छेदन - उदा. श्रिजवर 2003 देखें।

सॉल्वर और स्क्रिप्टिंग (क्रमादेशन) भाषाएँ

अनुज्ञेय मुफ्त सॉफ्टवेयर लाइसेंस लाइसेंस:

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

कॉपीलेफ़्ट (पारस्परिक) लाइसेंस:

नाम	लाइसेंस	संक्षिप्त जानकारी
एएलजीएलआईबी	जीपीएल 2+	एएलजीएलआईबी परियोजना से एक एलपी सॉल्वर (C++, C#, Python)
कैसोवेरी व्यवरोध सॉल्वर	एलजीपीएल	एक वृद्धिशील व्यवरोध को हल करने वाला टूलकिट जो कुशलतापूर्वक रैखिक समानता और असमानता की प्रणालियों को हल करता है
सीएलपी	सीपीएल	सीओआईएन-ओआर से एक एलपी सॉल्वर
जीएलपीके	जीपीएल	जीएनयू रैखिक क्रमादेशन किट, एक एलपी/एमआईएलपी सॉल्वर के साथ नेटिव सी एपीआई और अन्य भाषाओं के लिए कई (15) तीसरे पक्ष के रैपर। प्रवाह नेटवर्क के लिए विशेषज्ञ समर्थन। एएमपीएल की तरह जीएनयू मैथप्रोग मॉडलिंग भाषा और अनुवादक को बंडल करता है।
क्यूओसीए	जीपीएल	विभिन्न लक्ष्य कार्यों के साथ रैखिक समीकरणों की क्रमिक रूप से हल करने वाली प्रणालियों के लिए एक पुस्तकालय
आर-परियोजना	जीपीएल	सांख्यिकीय अभिकलन और ग्राफिक्स के लिए एक क्रमादेशन भाषा और सॉफ्टवेयर वातावरण

मिंटो (मिश्रित पूर्णांक अनुकूलक, एक पूर्णांक क्रमादेशन सोलवर जो शाखा और परिबद्ध एल्गोरिथ्म का प्रयोग करता है) के पास सार्वजनिक रूप से उपलब्ध स्रोत कोड है,^[26] लेकिन ओपन स्रोत नहीं है।

मालिकाना सॉफ्टवेयर लाइसेंस:

नाम	संक्षिप्त जानकारी
एआईएमएमएस	एक मॉडलिंग भाषा जो रैखिक, मिश्रित पूर्णांक और गैर-रैखिक अनुकूलन मॉडलों के माडल को अनुमति देती है। यह व्यवरोध क्रमादेशन के लिए एक उपकरण भी उपलब्ध कराता है। एल्गोरिथ्म, अनुमानी या सही विधियों, जैसे शाखा-और-कट या स्तंभ उत्पादन के रूप में भी कार्यान्वित किया जा सकता है। उपकरण हाथ में अनुकूलन समस्या को हल करने के लिए एक उपयुक्त सॉल्वर जैसे सीपीएलइएक्स या इसी तरह की कॉल करता है। शैक्षणिक लाइसेंस निःशुल्क हैं।
एएलजीएलआईबी	कापीलेफ्ट लाइसेंसधारी पुस्तकालय का एक वाणिज्यिक संस्करण। C++, C#, Python.
एएमपीएल	बड़े पैमाने पर रैखिक, मिश्रित पूर्णांक और गैर-रैखिक अनुकूलन के लिए एक लोकप्रिय मॉडलिंग भाषा, एक मुफ्त छात्र सीमित संस्करण उपलब्ध है (500 चर और 500 व्यवरोध)।
विश्लेषणात्मक	एक सामान्य मॉडलिंग भाषा और इंटरैक्टिव विकास पर्यावरण। इसका प्रभाव आरेख उपयोगकर्ताओं को निर्णय चर, उद्देश्यों और व्यवरोधओं के लिए नोड्स के साथ ग्राफ़ के रूप में समस्याओं को तैयार करने में सक्षम बनाता है। एनालिटिका ऑप्टिमाइज़र संस्करण में रैखिक, मिश्रित पूर्णांक और गैर-रैखिक सॉल्वर शामिल हैं और समस्या से मेल खाने के लिए सॉल्वर का चयन करता है। यह अन्य इंजनों को भी प्लग-इन के रूप में स्वीकार करता है, जिसमें एक्सप्रेस, गयूरोबी, आर्टिलिस नाइट्रो, और एमओएसइके शामिल हैं।
एपीमॉनिटर	मैटलैब और पायथन के लिए एपीआई। मैटलैब, पायथन, या वेब-इंटरफ़ेस के माध्यम से उदाहरण रैखिक क्रमादेशन (एलपी) समस्याओं को हल करें।
सीपीएलइएक्स	कई क्रमादेशन भाषाओं के लिए एक एपीआई के साथ लोकप्रिय सॉल्वर, और एक मॉडलिंग भाषा भी है और एक मॉडलिंग भाषा भी है और एआईएमएमएस, एएमपीएल, जीएएमएस, एमपीएल, ओपेन-ऑप्ट, ओपीएल डेवलपमेंट स्टूडियो और टॉमलैब के साथ काम करती है।शैक्षणिक उपयोग के लिए निशुल्क।
एक्सेल सॉल्वर फलन	स्प्रैडशीट्स में समायोजित एक अरैखिक सॉल्वर, जिसमें प्रकार्य मूल्यांकन, पुनर्गणना कोशिकाओं पर आधारित होता है। मूल संस्करण एक्सेल के लिए एक मानक ऐड-ऑन के रूप में उपलब्ध है।
फोर्टएमपी
जीएएमएस
आईएमएसएल संख्यात्मक पुस्तकालय	गणित और सांख्यिकीय एल्गोरिथम का संग्रह C/C++, Fortran, Java and C#/.NET. में उपलब्ध है। आईएमएसएल लाइब्रेरी में अनुकूलन नेमका में अनियंत्रित, रैखिक और अनालिनोरैली कंसल्टेंट न्यूमेरिजेशन तथा रैखिक क्रमादेशन एल्गोरिथ्म शामिल हैं।
एलआईएनडीओ	रैखिक, पूर्णांक, वर्ग, शंकु और स्टॉचस्टिक क्रमादेशन एक्सटेंशन्स के साथ सामान्य गैर-रैखिक क्रमादेशन के बड़े पैमाने पर अनुकूलन के लिए एक एपीआई के साथ एकल प्रयोक्ता है। यह निरंतर एवं विविक्त चर वाले सामान्य अरैखिक क्रमादेशनों के लिए वैश्विक इष्टतम समाधान की गारंटी के लिए वैश्विक अनुकूलन प्रक्रिया प्रदान करता है। इसमें मोंटे-कार्लो अनुरूपण को ऑप्टिमाइज़ेशन फ्रेमवर्क में एकीकृत करने के लिए सांख्यिकीय प्रतिचयन एपीआई भी है। इसमें एक बीजगणितीय मॉडलिंग भाषा (एलआईएनजीओ) है और एक स्प्रेडशीट (सबसे अच्छा क्या) के भीतर मॉडलिंग की अनुमति देता है।
मेपल	प्रतीकात्मक और संख्यात्मक अभिकलन के लिए एक सामान्य-उद्देश्य क्रमादेशन-भाषा।
मैटलैब	संख्यात्मक अभिकलन के लिए एक सामान्य-उद्देश्य और आव्यूह-उन्मुख क्रमादेशन-भाषा। मैटलैब में रैखिक क्रमादेशन के लिए आधार मैटलैब उत्पाद के अतिरिक्त अनुकूलन टूलबॉक्स की आवश्यकता होती है; उपलब्ध रूटीन में इनटलीनप्रोग और लीनप्रोग शामिल हैं
मैथकैड	एक वाइसिविग गणित संपादक। यह रैखिक और अरैखिक दोनों अनुकूलन समस्याओं को हल करने का कार्य करता है।
गणितज्ञों	प्रतीकात्मक और संख्यात्मक क्षमताओं सहित गणित के लिए एक सामान्य-उद्देश्य क्रमादेशन-भाषा।
एमओएसइके	कई भाषाओं के लिए एपीआई के साथ बड़े पैमाने पर अनुकूलन के लिए सॉल्वर (C++,java,.net, Matlab and python).
एनकोरी संख्यात्मक लाइब्रेरी	कई क्रमादेशन भाषाओं के लिए संख्यात्मक एल्गोरिथम समूह द्वारा विकसित गणितीय और सांख्यिकीय दिनचर्या का संग्रह (C, C++, Fortran, Visual Basic, Java and C#) और पैकेज (मैटलैब, एक्सेल, आर, लैबव्यू)। एनकोरी लाइब्रेरी के अनुकूलन अध्याय में विरल दोनों के साथ रैखिक क्रमादेशन समस्याओं के लिए रूटीन शामिल हैं और गैर-विरल रैखिक व्यवरोध मैट्रिसेस, एक साथ द्विघात, गैर-रैखिक, रैखिक या गैर-रैखिक कार्यों के वर्गों के योगों के अनुकूलन के लिए दिनचर्या के साथ-साथ गैर-रैखिक, परिबद्ध या कोई व्यवरोध नहीं। एनकोरी लाइब्रेरी में स्थानीय और वैश्विक अनुकूलन दोनों के लिए और निरंतर या पूर्णांक समस्याओं के लिए रूटीन हैं।
ऑप्टीमजे	अनुकूलन के लिए एक जावा-आधारित मॉडलिंग भाषा, जिसका मुफ़्त संस्करण उपलब्ध है।^[27]^[28]
एसएएस/ओआर	रैखिक, पूर्णांक, अरैखिक, व्युत्पन्न मुक्त, नेटवर्क, संयोजक और व्यवरोध अनुकूलन के लिए अयस्कों का एक समूह; बीजगणितीय मॉडलिंग भाषा ओपीटीमॉडल; और विभिन्न प्रकार के ऊर्ध्वाधर समाधानों का उद्देश्य विशिष्ट समस्याओं/बाजारों पर है, जिनमें से सभी एसएएस प्रणाली के साथ पूरी तरह से जुड़ गए हैं।
एससीआईपी	एक सामान्य प्रयोजन के लिए व्यवरोध पूर्णांक क्रमादेशन सॉल्वर, एमआईपी पर जोर देते हुए। ज़िम्पल मॉडलिंग भाषा के साथ संगत। शैक्षणिक उपयोग के लिए निःशुल्क और स्रोत कोड में उपलब्ध है।
एक्सप्रेस	बड़े पैमाने पर रैखिक क्रमादेशनों, द्विघात क्रमादेशनों, सामान्य गैर-रैखिक और मिश्रित-पूर्णांक क्रमादेशनों के लिए सॉल्वर। कई क्रमादेशन भाषाओं के लिए एपीआई है, एक मॉडलिंग भाषा मोसेल भी है और एएमपीएल, जीएएमएस के साथ काम करती है। शैक्षणिक उपयोग के लिए निशुल्क।
विस्सिम	गतिशील प्रणालियों के अनुकरण के लिए एक दृश्य ब्लॉक आरेख भाषा।

यह भी देखें

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

↑ ^1.0 ^1.1 Gerard Sierksma; Yori Zwols (2015). रैखिक और पूर्णांक अनुकूलन: सिद्धांत और व्यवहार (3rd ed.). CRC Press. p. 1. ISBN 978-1498710169.
↑ ^2.0 ^2.1 Alexander Schrijver (1998). रैखिक और पूर्णांक प्रोग्रामिंग के सिद्धान्त. John Wiley & Sons. pp. 221–222. ISBN 978-0-471-98232-6.
↑ ^3.0 ^3.1 ^3.2 George B. Dantzig (April 1982). "रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें" (PDF). Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Archived from the original on May 20, 2015.
↑ ^4.0 ^4.1 ^4.2 Dantzig, George B.; Thapa, Mukund Narain (1997). रैखिक प्रोग्रामिंग. New York: Springer. p. xxvii. ISBN 0387948333. OCLC 35318475.
↑ ^5.0 ^5.1 ^5.2 Leonid Khachiyan (1979). "रैखिक प्रोग्रामिंग के लिए एक बहुपद एल्गोरिथम". Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.
↑ ^6.0 ^6.1 Narendra Karmarkar (1984). "रैखिक प्रोग्रामिंग के लिए एक नया बहुपद-समय एल्गोरिथम". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150. S2CID 7257867.
↑ (PDF) https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf. {{cite web}}: Missing or empty |title= (help)
↑ Vazirani (2001, p. 112)
↑ ^9.0 ^9.1 ^9.2 Dantzig & Thapa (2003)
↑ ^10.0 ^10.1 Padberg (1999)
↑ ^11.0 ^11.1 ^11.2 Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य". Mathematical Programming, Series B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.
↑ Borgwardt (1987)
↑ Todd (2002)
↑ Murty (1983)
↑ Papadimitriou & Steiglitz
↑ Roos, C. (1990). "क्रिस-क्रॉस सिम्प्लेक्स विधि के लिए टेरलाकी के धुरी नियम के लिए एक घातीय उदाहरण". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483.
↑ Strang, Gilbert (1 June 1987). "कर्मकार का एल्गोरिथ्म और अनुप्रयुक्त गणित में उसका स्थान". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.
↑ Vaidya, Pravin M. (1987). रैखिक प्रोग्रामिंग के लिए एक एल्गोरिदम जिसके लिए <गणित> {O} (((m+ n) n^2+(m+ n)^{1.5} n) L)</math> अंकगणितीय संचालन की आवश्यकता होती है. 28th Annual IEEE Symposium on Foundations of Computer Science. FOCS.
↑ Vaidya, Pravin M. (1989). "Speeding-up linear programming using fast matrix multiplication". कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी. कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी. FOCS. pp. 332–337. doi:10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.
↑ Lee, Yin-Tat; Sidford, Aaron (2015). रैखिक प्रोग्रामिंग के लिए कुशल उलटा रखरखाव और तेज एल्गोरिदम. FOCS '15 Foundations of Computer Science. arXiv:1503.01752.
↑ Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018). वर्तमान मैट्रिक्स गुणन समय में रेखीय कार्यक्रमों को हल करना. 51st Annual ACM Symposium on the Theory of Computing. STOC'19. arXiv:1810.07896.
↑ Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). वर्तमान मैट्रिक्स गुणन समय में अनुभवजन्य जोखिम न्यूनीकरण को हल करना. Conference on Learning Theory. COLT'19. arXiv:1905.04447.
↑ Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). तेज़ एलपी के लिए तेज़ गतिशील मैट्रिक्स व्युत्क्रम. arXiv:2004.07470.
↑ Illés, Tibor; Terlaky, Tamás (2002). "धुरी बनाम आंतरिक बिंदु विधियाँ: पेशेवरों और विपक्ष". European Journal of Operational Research. 140 (2): 170. CiteSeerX 10.1.1.646.3539. doi:10.1016/S0377-2217(02)00061-9.
↑ Anstreicher, Kurt M.; Terlaky, Tamás (1994). "रैखिक प्रोग्रामिंग के लिए एक मोनोटोनिक बिल्ड-अप सिम्प्लेक्स एल्गोरिदम". Operations Research. 42 (3): 556–561. doi:10.1287/opre.42.3.556. ISSN 0030-364X. JSTOR 171894.
↑ "COR@L - लेहघ में कम्प्यूटेशनल अनुकूलन अनुसंधान". lehigh.edu.
↑ http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ used in an optimization model for mixed-model assembly lines, University of Münster
↑ http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 Archived 2011-06-29 at the Wayback Machine OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games

संदर्भ

Kantorovich, L. V. (1940). "Об одном эффективном методе решения некоторых классов экстремальных проблем" [A new method of solving some classes of extremal problems]. Doklady Akad Sci SSSR. 28: 211–214.
F. L. Hitchcock: The distribution of a product from several sources to numerous localities, Journal of Mathematics and Physics, 20, 1941, 224–230.
G.B Dantzig: Maximization of a linear function of variables subject to linear inequalities, 1947. Published pp. 339–347 in T.C. Koopmans (ed.):Activity Analysis of Production and Allocation, New York-London 1951 (Wiley & Chapman-Hall)
J. E. Beasley, editor. Advances in Linear and Integer Programming. Oxford Science, 1996. (Collection of surveys)
Bland, Robert G. (1977). "New Finite Pivoting Rules for the Simplex Method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647.
Karl-Heinz Borgwardt, The Simplex Algorithm: A Probabilistic Analysis, Algorithms and Combinatorics, Volume 1, Springer-Verlag, 1987. (Average behavior on random problems)
Richard W. Cottle, ed. The Basic George B. Dantzig. Stanford Business Books, Stanford University Press, Stanford, California, 2003. (Selected papers by George B. Dantzig)
George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag. (Comprehensive, covering e.g. pivoting and interior-point algorithms, large-scale problems, decomposition following Dantzig–Wolfe and Benders, and introducing stochastic programming.)
Edmonds, Jack; Giles, Rick (1977). "A Min-Max Relation for Submodular Functions on Graphs". Studies in Integer Programming. Annals of Discrete Mathematics. Vol. 1. pp. 185–204. doi:10.1016/S0167-5060(08)70734-9. ISBN 978-0-7204-0765-5.
Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.
Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley (ed.). Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. Vol. 4. New York: Oxford University Press. pp. 103–144. MR 1438311. Postscript file at website of Gondzio and at McMaster University website of Terlaky.
Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547. (comprehensive reference to classical approaches).
Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999. (carefully written account of primal and dual simplex algorithms and projective algorithms, with an introduction to integer linear programming – featuring the traveling salesman problem for Odysseus.)
Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover. (computer science)
Michael J. Todd (February 2002). "The many facets of linear programming". Mathematical Programming. 91 (3): 417–436. doi:10.1007/s101070100261. S2CID 6464735. (Invited survey, from the International Symposium on Mathematical Programming.)
Vanderbei, Robert J. (2001). Linear Programming: Foundations and Extensions. Springer Verlag.
Vazirani, Vijay V. (2001). Approximation Algorithms. Springer-Verlag. ISBN 978-3-540-65367-7. (Computer science)

अग्रिम पठन

Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Solutions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised ed.). Springer-Verlag. ISBN 978-3-540-65620-3.{{cite book}}: CS1 maint: multiple names: authors list (link) Chapter 4: Linear Programming: pp. 63–94. Describes a randomized half-plane intersection algorithm for linear programming.
Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 978-0-7167-1045-5. A6: MP1: INTEGER PROGRAMMING, pg.245. (computer science, complexity theory)
Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. (elementary introduction for mathematicians and computer scientists)
Cornelis Roos, Tamás Terlaky, Jean-Philippe Vial, Interior Point Methods for Linear Optimization, Second Edition, Springer-Verlag, 2006. (Graduate level)
Alexander Schrijver (2003). Combinatorial optimization: polyhedra and efficiency. Springer.
Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)
Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice. CRC Press. ISBN 978-1-498-71016-9.
Gerard Sierksma; Diptesh Ghosh (2010). Networks in Action; Text and Computer Exercises in Network Optimization. Springer. ISBN 978-1-4419-5512-8. (linear optimization modeling)
H. P. Williams, Model Building in Mathematical Programming, Fifth Edition, 2013. (Modeling)
Stephen J. Wright, 1997, Primal-Dual Interior-Point Methods, SIAM. (Graduate level)
Yinyu Ye, 1997, Interior Point Algorithms: Theory and Analysis, Wiley. (Advanced graduate-level)
Ziegler, Günter M., Chapters 1–3 and 6–7 in Lectures on Polytopes, Springer-Verlag, New York, 1994. (Geometry)

बाहरी संबंध

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

Software

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

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

}}

[SierksmaZwols2015-1] 1.0 ^1.1 Gerard Sierksma; Yori Zwols (2015). रैखिक और पूर्णांक अनुकूलन: सिद्धांत और व्यवहार (3rd ed.). CRC Press. p. 1. ISBN 978-1498710169.

[Schrijver1998-2] 2.0 ^2.1 Alexander Schrijver (1998). रैखिक और पूर्णांक प्रोग्रामिंग के सिद्धान्त. John Wiley & Sons. pp. 221–222. ISBN 978-0-471-98232-6.

[dantzig1982-3] 3.0 ^3.1 ^3.2 George B. Dantzig (April 1982). "रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें" (PDF). Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Archived from the original on May 20, 2015.

[:0-4] 4.0 ^4.1 ^4.2 Dantzig, George B.; Thapa, Mukund Narain (1997). रैखिक प्रोग्रामिंग. New York: Springer. p. xxvii. ISBN 0387948333. OCLC 35318475.

[khachiyan79-5] 5.0 ^5.1 ^5.2 Leonid Khachiyan (1979). "रैखिक प्रोग्रामिंग के लिए एक बहुपद एल्गोरिथम". Doklady Akademii Nauk SSSR. 224 (5): 1093–1096.

[karmarkar84-6] 6.0 ^6.1 Narendra Karmarkar (1984). "रैखिक प्रोग्रामिंग के लिए एक नया बहुपद-समय एल्गोरिथम". Combinatorica. 4 (4): 373–395. doi:10.1007/BF02579150. S2CID 7257867.

[7] (PDF) https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf. {{cite web}}: Missing or empty |title= (help)

[8] Vazirani (2001, p. 112)

[DT03-9] 9.0 ^9.1 ^9.2 Dantzig & Thapa (2003)

[Padberg-10] 10.0 ^10.1 Padberg (1999)

[FukudaTerlaky-11] 11.0 ^11.1 ^11.2 Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य". Mathematical Programming, Series B. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181.

[12] Borgwardt (1987)

[Todd-13] Todd (2002)

[Murty-14] Murty (1983)

[PS-15] Papadimitriou & Steiglitz

[Roos-16] Roos, C. (1990). "क्रिस-क्रॉस सिम्प्लेक्स विधि के लिए टेरलाकी के धुरी नियम के लिए एक घातीय उदाहरण". Mathematical Programming. Series A. 46 (1): 79–84. doi:10.1007/BF01585729. MR 1045573. S2CID 33463483.

[Strang-17] Strang, Gilbert (1 June 1987). "कर्मकार का एल्गोरिथ्म और अनुप्रयुक्त गणित में उसका स्थान". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.

[18] Vaidya, Pravin M. (1987). रैखिक प्रोग्रामिंग के लिए एक एल्गोरिदम जिसके लिए <गणित> {O} (((m+ n) n^2+(m+ n)^{1.5} n) L)</math> अंकगणितीय संचालन की आवश्यकता होती है. 28th Annual IEEE Symposium on Foundations of Computer Science. FOCS.

[19] Vaidya, Pravin M. (1989). "Speeding-up linear programming using fast matrix multiplication". कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी. कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी. FOCS. pp. 332–337. doi:10.1109/SFCS.1989.63499. ISBN 0-8186-1982-1.

[20] Lee, Yin-Tat; Sidford, Aaron (2015). रैखिक प्रोग्रामिंग के लिए कुशल उलटा रखरखाव और तेज एल्गोरिदम. FOCS '15 Foundations of Computer Science. arXiv:1503.01752.

[21] Cohen, Michael B.; Lee, Yin-Tat; Song, Zhao (2018). वर्तमान मैट्रिक्स गुणन समय में रेखीय कार्यक्रमों को हल करना. 51st Annual ACM Symposium on the Theory of Computing. STOC'19. arXiv:1810.07896.

[22] Lee, Yin-Tat; Song, Zhao; Zhang, Qiuyi (2019). वर्तमान मैट्रिक्स गुणन समय में अनुभवजन्य जोखिम न्यूनीकरण को हल करना. Conference on Learning Theory. COLT'19. arXiv:1905.04447.

[23] Jiang, Shunhua; Song, Zhao; Weinstein, Omri; Zhang, Hengjie (2020). तेज़ एलपी के लिए तेज़ गतिशील मैट्रिक्स व्युत्क्रम. arXiv:2004.07470.

[24] Illés, Tibor; Terlaky, Tamás (2002). "धुरी बनाम आंतरिक बिंदु विधियाँ: पेशेवरों और विपक्ष". European Journal of Operational Research. 140 (2): 170. CiteSeerX 10.1.1.646.3539. doi:10.1016/S0377-2217(02)00061-9.

[25] Anstreicher, Kurt M.; Terlaky, Tamás (1994). "रैखिक प्रोग्रामिंग के लिए एक मोनोटोनिक बिल्ड-अप सिम्प्लेक्स एल्गोरिदम". Operations Research. 42 (3): 556–561. doi:10.1287/opre.42.3.556. ISSN 0030-364X. JSTOR 171894.

[26] "COR@L - लेहघ में कम्प्यूटेशनल अनुकूलन अनुसंधान". lehigh.edu.

[27] ttp://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ used in an optimization model for mixed-model assembly lines, University of Münster

[28] ttp://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 Archived 2011-06-29 at the Wayback Machine OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

v t e Complementarity problems and algorithms
Complementarity Problems	Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear(NCP)
Basis-exchange algorithms	Simplex (Dantzig) Revised simplex Criss-cross Lemke

@@ Line 1: / Line 1: @@
 {{short description|Method to solve some optimization problems}}
-{{for|यहाँ दी गई उपनाम निर्देशक टेलीविजन प्रसारण के लिए|प्रसारण प्रोग्रामिंग}}
+{{for|यहाँ दी गई उपनाम निर्देशक टेलीविजन प्रसारण के लिए|प्रसारण क्रमादेशन}}
-[[File:Linear optimization in a 2-dimensional polytope.svg|thumb|दो चर और छह असमानताओं के साथ एक सरल रेखीय कार्यक्रम का सचित्र प्रतिनिधित्व। व्यवहार्य समाधानों का सेट पीले रंग में दर्शाया गया है और एक [[ बहुभुज ]], एक 2-आयामी [[ polytope ]] बनाता है। रैखिक लागत फलन का इष्टतम वह स्थान है जहां लाल रेखा बहुभुज को काटती है। लाल रेखा लागत फलन का स्तर सेट है, और तीर उस दिशा को इंगित करता है जिसमें हम अनुकूलन कर रहे हैं।]]
+[[File:Linear optimization in a 2-dimensional polytope.svg|thumb|दो चर और छह असमानताओं के साथ एक सरल रैखिक क्रमादेशन का सचित्र प्रतिनिधित्व। सुसंगत समाधानों का समुच्चय पीले रंग में दर्शाया गया है और एक [[ बहुभुज ]], एक 2-आयामी [[ polytope | पॉलीटोप]] बनाता है। रैखिक लागत फलन का इष्टतम वह स्थान है जहां लाल रेखा बहुभुज को काटती है। लाल रेखा लागत फलन का स्तर समुच्चय है, और तीर उस दिशा को इंगित करता है जिसमें हम अनुकूलन कर रहे हैं।]]
-[[File:3dpoly.svg|thumb|right|तीन चरों वाली समस्या का एक बंद सुसंगत क्षेत्र एक उत्तल बहुफलक है। उद्देश्य फलन का निश्चित मान देने वाली सतहें समतल (ज्यामिति) हैं (दिखाया नहीं गया)। रैखिक प्रोग्रामिंग समस्या [[ बहुतल ]] पर एक बिंदु खोजने के लिए है जो उच्चतम संभव मान वाले समतल पर है।]][[रैखिक]] प्रोग्रामिंग (एलपी), जिसे रैखिक अनुकूलन भी कहा जाता है, गणितीय मॉडल में, जिनकी आवश्यकताओं को रैखिक संबंधों द्वारा दर्शाया जाता है, सर्वोत्तम परिणाम (जैसे अधिकतम लाभ या न्यूनतम लागत) प्राप्त करने की एक विधि है, रैखिक प्रोग्रामिंग, गणितीय प्रोग्रामिंग (जिसे [[ गणितीय अनुकूलन ]]भी कहते हैं) का एक विशेष मामला है।
+[[File:3dpoly.svg|thumb|right|तीन चरों वाली समस्या का एक बंद सुसंगत क्षेत्र एक उत्तल बहुफलक है। उद्देश्य फलन का निश्चित मान देने वाली सतहें समतल (ज्यामिति) हैं (दिखाया नहीं गया)। रैखिक क्रमादेशन समस्या [[ बहुतल ]] पर एक बिंदु खोजने के लिए है जो उच्चतम संभव मान वाले समतल पर है।]]रैखिक क्रमादेशन (एलपी), जिसे रैखिक अनुकूलन भी कहा जाता है, गणितीय मॉडल में, जिनकी आवश्यकताओं को रैखिक संबंधों द्वारा दर्शाया जाता है, सर्वोत्तम परिणाम (जैसे अधिकतम लाभ या न्यूनतम लागत) प्राप्त करने की एक विधि है, रैखिक क्रमादेशन, गणितीय क्रमादेशन (जिसे [[ गणितीय अनुकूलन ]]भी कहते हैं) का एक विशेष स्थिति है।
-अधिक औपचारिक रूप से, रैखिक प्रोग्रामिंग एक रैखिक उद्देश्य फलन के अनुकूलन के लिए एक तकनीक है, जो [[ रैखिक समानता ]] और [[ रैखिक असमानता ]] [[ बाधा (गणित) ]] के अधीन है।इसका व्यवहार्य क्षेत्र एक उत्तल पॉलीटोपे है, जो एक समुच्चय है जिसे परिमित रूप से कई आधे स्थानों के प्रतिच्छेदन के रूप में परिभाषित किया गया है, जिनमें से प्रत्येक एक रैखिक असमानता द्वारा परिभाषित किया गया है। इसका उद्देश्य फलन इस पॉलिहेड्रोन पर परिभाषित एक [[ वास्तविक संख्या ]]-मूल्यवान [[एफिन (रैखिक) फलन]] है। एक रेखीय प्रोग्रामिंग एल्गोरिथ्म, बहुतप में एक बिंदु ढूँढता है, जहां इस फलन का सबसे छोटा (या सबसे बड़ा) मान होता है, यदि ऐसा बिंदु मौजूद है।
+अधिक औपचारिक रूप से, रैखिक क्रमादेशन एक रैखिक उद्देश्य फलन के अनुकूलन के लिए एक तकनीक है, जो [[ रैखिक समानता ]] और [[ रैखिक असमानता | रैखिक असमिका]] [[ बाधा (गणित) | व्यवरोध (गणित)]] के अधीन है। इसका सुसंगत क्षेत्र उत्तल पॉलीटोपे है, जो एक समुच्चय है, जिसे परिमित रूप से कई आधी समष्टियों के प्रतिच्छेदन के रूप में परिभाषित किया गया है, जिनमें से प्रत्येक को रैखिक असमिका द्वारा परिभाषित किया गया है। इसका उद्देश्य फलन इस बहुफलक पर परिभाषित एक [[ वास्तविक संख्या ]]-मूल्यवान [[एफिन (रैखिक) फलन]] है। रैखिक क्रमादेशन एल्गोरिथ्म, बहुतप में एक बिंदु ढूँढता है, जहां इस फलन का सबसे छोटा (या सबसे बड़ा) मान होता है, यदि ऐसी बिंदु पहले से मौजूद है।
-रैखिक कार्यक्रम ऐसी समस्याएं हैं जिन्हें विहित रूप में व्यक्त किया जा सकता है,
+रैखिक क्रमादेशन में ऐसी समस्याएं हैं जिन्हें विहित रूप में व्यक्त किया जा सकता है,
 :<math> \begin{align}
 & \text{Find a vector} && \mathbf{x} \\
@@ Line 13: / Line 13: @@
 & \text{and} && \mathbf{x} \ge \mathbf{0}.
 \end{align} </math>
-यहाँ x के घटक निर्धारित किए जाने वाले चर हैं, c और b सदिश दिए गए हैं (<math>\mathbf{c}^T</math> द्वारा यह दर्शाया गया है कि c के गुणांक का प्रयोग मैट्रिक्स उत्पाद के निर्माण के प्रयोजन हेतु एकल पंक्ति मैट्रिक्स के रूप में किया जाता है), और ''A'' एक दिया गया [[ मैट्रिक्स (गणित) | मैट्रिक्स (गणित)]] है। फलन जिसका मान अधिकतम या न्यूनतम किया जाना है ( <math>\mathbf x\mapsto\mathbf{c}^T\mathbf{x}</math> इस स्थिति में ) को उद्देश्य फलन कहा जाता है। असमिकाएँ Ax ≤ b और x ≥ 0 ऐसी बाधाएँ हैं जो एक उत्तल पॉलीटॉप निर्दिष्ट करती हैं जिसके ऊपर उद्देश्य फ़ंक्शन को अनुकूलित किया जाना है। इस संदर्भ में, दो सदिश तुलनीय होते हैं जब उनके पास समान आयाम होते हैं। अगर पहले में प्रत्येक प्रविष्टि दूसरे में संबंधित प्रविष्टि से कम या बराबर होती है, तो यह कहा जा सकता है कि पहले सदिश दूसरी सदिश से कम या बराबर है।
+यहाँ पर x के घटक को निर्धारित किए जाने वाले चर हैं,  c और b सदिश दिए गए हैं (<math>\mathbf{c}^T</math> द्वारा यह दर्शाया गया है कि c के गुणांक का प्रयोग आव्यूह उत्पाद के निर्माण के प्रयोजन हेतु एकल पंक्ति आव्यूह के रूप में किया जाता है), और ''A'' दिया गया [[ मैट्रिक्स (गणित) | आव्यूह (गणित)]] है। फलन जिसका मान अधिकतम या न्यूनतम किया जाना है ( <math>\mathbf x\mapsto\mathbf{c}^T\mathbf{x}</math> इस स्थिति में ) उसको उद्देश्य फलन कहा जाता है। असमिकाएँ Ax ≤ b और x ≥ 0 ऐसी व्यवरोधएँ हैं जो एक उत्तल पॉलीटॉप निर्दिष्ट करती हैं जिसके ऊपर उद्देश्य फलन को अनुकूलित किया जाता है। इस संदर्भ में, दो सदिश तुलनीय हैं जब उनके पास समान आयाम होते हैं। अगर पहले में प्रत्येक प्रविष्टि दूसरे में संबंधित प्रविष्टि से कम या बराबर होती है, तो यह कहा जा सकता है कि पहले सदिश दूसरी सदिश से कम या बराबर है।
-रैखिक प्रोग्रामिंग अध्ययन के विभिन्न क्षेत्रों में लागू किया जा सकता है। यह व्यापक रूप से गणित में और कुछ हद तक व्यापार, अर्थशास्त्र और कुछ इंजीनियरिंग समस्याओं में उपयोग किया जाता है। रैखिक प्रोग्रामिंग मॉडलों के प्रयोग में आने वाले उद्योग हैं परिवहन, ऊर्जा, दूरसंचार और निर्माण। यह [[ स्वचालित योजना और शेड्यूलिंग |स्वचालित योजना]], रूटिंग, [[शेड्यूलिंग]] (उत्पादन प्रक्रिया), असाइनमेंट और डिज़ाइन में विभिन्न प्रकार की समस्याओं के मॉडलिंग में उपयोगी साबित हुआ है।
+रैखिक क्रमादेशन अध्ययन के विभिन्न क्षेत्रों में लागू किया जा सकता है। यह व्यापक रूप से गणित में और कुछ हद तक व्यापार, अर्थशास्त्र और कुछ इंजीनियरिंग समस्याओं में उपयोग किया जाता है। रैखिक क्रमादेशन मॉडलों के प्रयोग में आने वाले उद्योग हैं परिवहन, ऊर्जा, दूरसंचार और निर्माण। यह [[ स्वचालित योजना और शेड्यूलिंग |स्वचालित योजना]], रूटिंग, [[शेड्यूलिंग]] (उत्पादन प्रक्रिया), असाइनमेंट और डिज़ाइन में विभिन्न प्रकार की समस्याओं के मॉडलिंग में उपयोगी साबित हुआ है।
 == इतिहास ==
 [[File:Leonid Kantorovich 1975.jpg|thumb|[[ लियोनिद कांटोरोविच ]]]]
-[[File:JohnvonNeumann-LosAlamos.gif|thumb|[[ जॉन वॉन न्यूमैन ]]]]रैखिक असमानता की एक प्रणाली को हल करने की समस्या कम से कम फूरियर तक है, जिन्होंने 1827 में उन्हें हल करने के लिए एक विधि प्रकाशित की थी,<ref name="SierksmaZwols2015">{{cite book|author1=Gerard Sierksma|author2=Yori Zwols|title=रैखिक और पूर्णांक अनुकूलन: सिद्धांत और व्यवहार|edition=3rd|year=2015|publisher=CRC Press|isbn=978-1498710169|page=1}}</ref> और बाद में जिसे फूरियर मोटाकिन उन्मूलन की विधि का नाम दिया गया था।
+[[File:JohnvonNeumann-LosAlamos.gif|thumb|[[ जॉन वॉन न्यूमैन ]]]]रैखिक असमिका की एक प्रणाली को हल करने की समस्या कम से कम फूरियर तक है, जिन्होंने 1827 में उन्हें हल करने के लिए एक विधि प्रकाशित की थी,<ref name="SierksmaZwols2015">{{cite book|author1=Gerard Sierksma|author2=Yori Zwols|title=रैखिक और पूर्णांक अनुकूलन: सिद्धांत और व्यवहार|edition=3rd|year=2015|publisher=CRC Press|isbn=978-1498710169|page=1}}</ref> और बाद में जिसे फूरियर मोटाकिन उन्मूलन की विधि का नाम दिया गया था।
-में एक ऐसी समस्या का रेखीय प्रोग्रामन निरूपण जो सामान्य रेखीय प्रोग्रामिंग समस्या के समतुल्य है, [[ सोवियत संघ |सोवियत संघ]] के [[ गणितज्ञ |गणितज्ञ]] और [[ अर्थशास्त्री |अर्थशास्त्री]] लियोनिद कांटोरोविच ने दिया था, जिन्होंने इसे हल करने के लिए भी एक तरीका प्रस्थापित किया था।<ref name="Schrijver1998">{{cite book|author=Alexander Schrijver|title=रैखिक और पूर्णांक प्रोग्रामिंग के सिद्धान्त|year=1998|publisher=John Wiley & Sons|isbn=978-0-471-98232-6|pages=221–222}}</ref> यह एक तरीका है जिसे उन्होंने [[द्वितीय विश्व युद्ध]] के दौरान विकसित किया, सेना की लागत कम करने और शत्रु पर लगाये गये हानियों को बढ़ाने के लिए व्ययों और वापसी की योजना बनाने का एक तरीका है।{{Citation needed|date=August 2017}} कंटोरविच का काम शुरू में यूएसएसआर में उपेक्षित था।<ref name="dantzig1982">{{cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें|author=George B. Dantzig|date = April 1982|journal = Operations Research Letters|volume = 1|issue = 2|pages = 43–48|doi = 10.1016/0167-6377(82)90043-8}}</ref> लगभग उसी समय कांटोरोविच के रूप में,डच अमेरिकन अर्थशास्त्री टी. सी. कोआपंस ने रैखिक प्रोग्राम के रूप में शास्त्रीय आर्थिक समस्याओं का निर्माण किया। कंटोरोविच और कूपमैन ने बाद में [[अर्थशास्त्र में]] 1975 का [[नोबेल पुरस्कार]] साझा किया।<ref name="SierksmaZwols2015" /> सन 1941 में [[फ्रांक लॉरेन हिचकॉक]] ने परिवहन समस्याओं को रेखीय कार्यक्रम के रूप में भी तैयार किया और इसमें बाद के सरल विधि के समान समाधान दिया।<ref name="Schrijver1998" /> 1957 में हैचकॉक की मृत्यु हो गई थी और नोबेल पुरस्कार मरणोपरांत नहीं दिया गया है।
+में एक ऐसी समस्या का रैखिक क्रमादेशन निरूपण जो सामान्य रैखिक क्रमादेशन समस्या के समतुल्य है, [[ सोवियत संघ |सोवियत संघ]] के [[ गणितज्ञ |गणितज्ञ]] और [[ अर्थशास्त्री |अर्थशास्त्री]] लियोनिद कांटोरोविच ने दिया था, जिन्होंने इसको हल करने के लिए भी एक तरीका प्रस्थापित किया था।<ref name="Schrijver1998">{{cite book|author=Alexander Schrijver|title=रैखिक और पूर्णांक प्रोग्रामिंग के सिद्धान्त|year=1998|publisher=John Wiley & Sons|isbn=978-0-471-98232-6|pages=221–222}}</ref> यह एक तरीका है जिसे उन्होंने [[द्वितीय विश्व युद्ध]] के दौरान विकसित किया, सेना की लागत कम करने और शत्रु पर लगाये गये हानियों को बढ़ाने के लिए व्ययों और वापसी की योजना बनाने का एक तरीका है।{{Citation needed|date=August 2017}} कांटोरोविच का काम शुरू में यूएसएसआर में उपेक्षित था।<ref name="dantzig1982">{{cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें|author=George B. Dantzig|date = April 1982|journal = Operations Research Letters|volume = 1|issue = 2|pages = 43–48|doi = 10.1016/0167-6377(82)90043-8}}</ref> लगभग उसी समय कांटोरोविच के रूप में,डच अमेरिकन अर्थशास्त्री टी. सी. कोआपंस ने रैखिक क्रमादेशन के रूप में शास्त्रीय आर्थिक समस्याओं का निर्माण किया। कंटोरोविच और कूपमैन ने बाद में [[अर्थशास्त्र में]] 1975 का [[नोबेल पुरस्कार]] साझा किया।<ref name="SierksmaZwols2015" /> सन 1941 में [[फ्रांक लॉरेन हिचकॉक]] ने परिवहन समस्याओं को रैखिक क्रमादेशन के रूप में भी तैयार किया और इसमें बाद के सिंप्लेक्स विधि के समान समाधान दिया।<ref name="Schrijver1998" /> 1957 में हैचकॉक की मृत्यु हो गई थी और नोबेल पुरस्कार मरणोपरांत नहीं दिया गया था।
-से 1947 तक जॉर्ज बी. डेंटजिग ने संयुक्त राज्य अमेरिका की वायुसेना में आयोजित समस्याओं के लिए उपयोग किए जाने वाले सामान्य रैखिक प्रोग्रामिंग सूत्रीकरण का स्वतंत्र रूप से विकास किया।<ref name=":0">{{Cite book|title=रैखिक प्रोग्रामिंग|last1=Dantzig|first1=George B.|last2=Thapa|first2=Mukund Narain|date=1997|publisher=Springer|isbn=0387948333|location=New York|page=xxvii|oclc=35318475}}</ref> 1947 में, डेंटज़िग ने [[सिम्पलेक्स विधि]] का भी आविष्कार किया, जो कि, पहली बार कुशलता से, ज्यादातर मामलों में रैखिक प्रोग्रामिंग समस्या का समाधान किया।<ref name=":0" /> जब डेंटजिग ने जॉन वॉन न्यूमैन के साथ उनकी सिम्पलेक्स विधि पर चर्चा करने के लिए एक बैठक की व्यवस्था की, न्यूमैन ने तत्काल द्वैत के सिद्धांत का अनुमान लगाया कि [[खेल के सिद्धांत]] में जो समस्या वह काम कर रहा था वह बराबर है।<ref name=":0" /> डेंटजिग ने 5 जनवरी, 1948 को एक अप्रकाशित रिपोर्ट "रैखिक असमानताओं पर एक प्रमेय" में औपचारिक प्रमाण प्रदान किया।<ref name="dantzig1982"/> डेंटज़िग का काम 1951 में जनता के लिए उपलब्ध कराया गया था। युद्धोपरांत के वर्षों में, अनेक उद्योगों ने इसे अपने दैनिक नियोजन में लागू किया।
+से 1947 तक जॉर्ज बी. डेंटजिग ने संयुक्त राज्य अमेरिका की वायुसेना में आयोजित समस्याओं के लिए उपयोग किए जाने वाले सामान्य रैखिक क्रमादेशन सूत्रीकरण का स्वतंत्र रूप से विकास किया।<ref name=":0">{{Cite book|title=रैखिक प्रोग्रामिंग|last1=Dantzig|first1=George B.|last2=Thapa|first2=Mukund Narain|date=1997|publisher=Springer|isbn=0387948333|location=New York|page=xxvii|oclc=35318475}}</ref> 1947 में, डेंटज़िग ने [[सिम्पलेक्स विधि]] का भी आविष्कार किया, जो कि, पहली बार कुशलता से, ज्यादातर स्थितियों में रैखिक क्रमादेशन समस्या का समाधान किया।<ref name=":0" /> जब डेंटजिग ने जॉन वॉन न्यूमैन के साथ उनकी सिम्पलेक्स विधि पर चर्चा करने के लिए एक बैठक की व्यवस्था की, न्यूमैन ने तत्काल द्वैत के सिद्धांत का अनुमान लगाया कि [[खेल के सिद्धांत]] में जो समस्या वह काम कर रहा था वह बराबर है।<ref name=":0" /> डेंटजिग ने 5 जनवरी, 1948 को एक अप्रकाशित रिपोर्ट "रैखिक असमिकाओं पर एक प्रमेय" में औपचारिक प्रमाण प्रदान किया।<ref name="dantzig1982"/> डेंटज़िग का काम 1951 में जनता के लिए उपलब्ध कराया गया था। युद्धोपरांत के वर्षों में, अनेक उद्योगों ने इसे अपने दैनिक नियोजन में लागू किया।
-डेंटजिग का मूल उदाहरण 70 लोगों को 70 नौकरियों के लिए सबसे अच्छा काम मिलना था। सर्वोत्तम असाइनमेंट का चयन करने के लिए सभी क्रमपरिवर्तनों का परीक्षण करने के लिए आवश्यक कंप्यूटिंग शक्ति विशाल है; संभाव्य विन्यास की संख्या प्रेक्षण योग्य ब्रह्मांड में [[ रासायनिक तत्वों की प्रचुरता |रासायनिक तत्वों की प्रचुरता]] से अधिक है। हालांकि, समस्या को रैखिक प्रोग्राम के रूप में प्रस्तुत करके और सिम्प्लेक्स एल्गोरिथ्म को लागू करके इष्टतम समाधान प्राप्त करने के लिए इसको एक क्षण का समय लगता है। रैखिक प्रोग्रामन के पीछे का सिद्धांत प्रबल रूप से उन संभावित समाधानों की संख्या को कम करता है जिनकी जाँच होनी चाहिए।
+डेंटजिग का मूल उदाहरण 70 लोगों को 70 नौकरियों के लिए सबसे अच्छा काम मिलना था। सर्वोत्तम असाइनमेंट का चयन करने के लिए सभी क्रमपरिवर्तनों का परीक्षण करने के लिए आवश्यक अभिकलन घात विशाल है; संभाव्य विन्यास की संख्या प्रेक्षण योग्य ब्रह्मांड में [[ रासायनिक तत्वों की प्रचुरता |रासायनिक तत्वों की प्रचुरता]] से अधिक है। चूंकि, समस्या को रैखिक क्रमादेशन के रूप में प्रस्तुत किया और सिम्प्लेक्स एल्गोरिथ्म को लागू करके इष्टतम समाधान प्राप्त करने के लिए इसको एक क्षण का समय लगता है। रैखिक क्रमादेशन के पीछे का सिद्धांत प्रबल रूप से उन संभावित समाधानों की संख्या को कम करता है जिनकी जाँच होनी चाहिए।
-रैखिक प्रोग्रामिंग समस्या को पहली बार 1979 में [[लियोनिड खाचियान]] द्वारा बहुपद समय में व्याख्या करने योग्य दिखाया गया था,<ref name="khachiyan79">{{cite journal|title = रैखिक प्रोग्रामिंग के लिए एक बहुपद एल्गोरिथम|author = Leonid Khachiyan|date = 1979|journal = Doklady Akademii Nauk SSSR|volume=224|issue=5|pages=1093–1096}}</ref> परंतु इस क्षेत्र में एक व्यापक सैद्धांतिक और व्यावहारिक सफलता 1984 में मिली, जब [[ नरेंद्र करमरकर |नरेंद्र करमरकर]] ने रैखिक-प्रोग्रामन समस्याओं के समाधान के लिए एक नई आंतरिक-बिंदु विधि शुरू की।<ref name="karmarkar84">{{cite journal|title = रैखिक प्रोग्रामिंग के लिए एक नया बहुपद-समय एल्गोरिथम|author = Narendra Karmarkar|date = 1984|journal = Combinatorica|volume=4|issue = 4|pages=373–395|doi = 10.1007/BF02579150|s2cid = 7257867}}</ref>
+रैखिक क्रमादेशन समस्या को पहली बार 1979 में [[लियोनिड खाचियान]] द्वारा बहुपद समय में व्याख्या करने योग्य दिखाया गया था,<ref name="khachiyan79">{{cite journal|title = रैखिक प्रोग्रामिंग के लिए एक बहुपद एल्गोरिथम|author = Leonid Khachiyan|date = 1979|journal = Doklady Akademii Nauk SSSR|volume=224|issue=5|pages=1093–1096}}</ref> परंतु इस क्षेत्र में एक व्यापक सैद्धांतिक और आभ्यासिक सफलता 1984 में मिली, जब [[ नरेंद्र करमरकर |नरेंद्र करमरकर]] ने रैखिक-क्रमादेशन समस्याओं के समाधान के लिए एक नई आंतरिक-बिंदु विधि शुरू की।<ref name="karmarkar84">{{cite journal|title = रैखिक प्रोग्रामिंग के लिए एक नया बहुपद-समय एल्गोरिथम|author = Narendra Karmarkar|date = 1984|journal = Combinatorica|volume=4|issue = 4|pages=373–395|doi = 10.1007/BF02579150|s2cid = 7257867}}</ref>
 == उपयोग ==
-रैखिक क्रमादेशन, कई कारणों से अनुकूलन के व्यापक रूप से प्रयुक्त क्षेत्र है। [[ संचालन अनुसंधान |संचालन अनुसंधान]] में कई व्यावहारिक समस्याओं को रैखिक प्रोग्रामन समस्याओं के रूप में व्यक्त किया जा सकता है।<ref name="dantzig1982"/> रैखिक प्रोग्रामिंग के कुछ विशेष मामले, जैसे कि नेटवर्क प्रवाह समस्याएँ और बहु-कमोडिटी प्रवाह समस्या, विशेष एल्गोरिथ्म पर काफी अनुसंधान करने के लिए काफी महत्वपूर्ण माने जाते हैं। अन्य प्रकार के अनुकूलन समस्याओं के लिए कुछ एल्गोरिथ्म, रैखिक प्रोग्रामिंग समस्याओं को उप-समस्याओं के रूप में हल करके काम करता है। ऐतिहासिक रूप से, रैखिक प्रोग्रामिंग के विचारों ने अनुकूलन सिद्धांत की कई केंद्रीय अवधारणाओं को प्रेरित किया है, जैसे द्वैत, अपघटन, और उत्तलता के महत्व और इसके सामान्यीकरण इसी तरह, रैखिक प्रोग्रामिंग सूक्ष्मअर्थशास्त्र के प्रारंभिक गठन में भारी इस्तेमाल किया गया था, और यह वर्तमान में कंपनी प्रबंधन, जैसे योजना, उत्पादन, परिवहन, और प्रौद्योगिकी में उपयोग किया जाता है। हालांकि आधुनिक प्रबंधन के मुद्दे कभी भी बदल रहे हैं, अधिकांश कंपनियां सीमित संसाधनों से लाभ को अधिकतम और लागत को कम करना चाहेंगी। गूगल यूट्यूब विडियो को स्थिर करने के लिए रैखिक प्रोग्रामन भी प्रयोग करता है।<ref>{{cite web |url=https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf}}</ref>
+रैखिक क्रमादेशन, कई कारणों से अनुकूलन के व्यापक रूप से प्रयुक्त क्षेत्र है। [[ संचालन अनुसंधान |संचालन अनुसंधान]] में कई आभ्यासिक समस्याओं को रैखिक क्रमादेशन समस्याओं के रूप में व्यक्त किया जा सकता है।<ref name="dantzig1982"/> रैखिक क्रमादेशन के कुछ विशेष स्थिति, जैसे कि नेटवर्क प्रवाह समस्याएँ और बहु-कमोडिटी प्रवाह समस्या, विशेष एल्गोरिथ्म पर काफी अनुसंधान करने के लिए काफी महत्वपूर्ण माने जाते हैं। अन्य प्रकार के अनुकूलन समस्याओं के लिए कुछ एल्गोरिथ्म, रैखिक क्रमादेशन समस्याओं को उप-समस्याओं के रूप में हल करके काम करता है। ऐतिहासिक रूप से, रैखिक क्रमादेशन के विचारों ने अनुकूलन सिद्धांत की कई केंद्रीय अवधारणाओं को प्रेरित किया है, जैसे द्वैत, अपघटन, और उत्तलता के महत्व और इसके सामान्यीकरण इसी तरह, रैखिक क्रमादेशन सूक्ष्मअर्थशास्त्र के प्रारंभिक गठन में भारी उपयोग किया गया था, और यह वर्तमान में कंपनी प्रबंधन, जैसे योजना, उत्पादन, परिवहन, और प्रौद्योगिकी में उपयोग किया जाता है। चूंकि आधुनिक प्रबंधन के मुद्दे कभी भी बदल रहे हैं, अधिकांश कंपनियां सीमित संसाधनों से लाभ को अधिकतम और लागत को कम करना चाहेंगी। गूगल यूट्यूब विडियो को स्थिर करने के लिए रैखिक क्रमादेशन भी प्रयोग करता है।<ref>{{cite web |url=https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37041.pdf}}</ref>
 == मानक रूप ==
-मानक रूप, रैखिक प्रोग्रामन समस्या का वर्णन करने का एक सामान्य और सबसे सहज रूप होता है। इसमें निम्न तीन भाग होते हैं:
+मानक रूप, रैखिक क्रमादेशन समस्या का वर्णन करने का एक सामान्य और सबसे सहज रूप होता है। इसमें निम्न तीन भाग होते हैं:
 * एक रैखिक फलन को अधिकतम किया जाना
 : जैसे <math> f(x_{1},x_{2}) = c_1 x_1 + c_2 x_2</math>
@@ Line 41: / Line 41: @@
    a_{31} x_1 + a_{32} x_2 &\leq b_3 \\
 \end{matrix}</math>
-* गैर-नकारात्मक चर
+* ऋणेतर-संख्या चर
 : जैसे
 :: <math>\begin{matrix}
@@ Line 47: / Line 47: @@
   x_2 \geq 0
 \end{matrix}</math>
-समस्या आमतौर पर आव्यूह (गणित) के रूप में व्यक्त की जाती है, और फिर बन जाती है:
+समस्या सामान्यतः आव्यूह (गणित) के रूप में व्यक्त की जाती है, और फिर बन जाती है:
 : <math>\max \{\, \mathbf{c}^\mathrm{T} \mathbf{x} \mid \mathbf{x}\in\mathbb{R}^n\land A \mathbf{x} \leq \mathbf{b} \land \mathbf{x} \geq 0 \,\}</math>
-अन्य रूपों, जैसे कि न्यूनतमीकरण समस्याएं, वैकल्पिक रूपों पर व्यवरोध वाली समस्याएं, और नकारात्मक [[ चर (प्रोग्रामिंग) |चर (प्रोग्रामिंग)]] को सम्मिलित करने वाली समस्याओं को हमेशा मानक रूप में एक समान समस्या में लिखा जा सकता है।
+अन्य रूपों, जैसे कि न्यूनतमीकरण समस्याएं, वैकल्पिक रूपों पर व्यवरोध वाली समस्याएं, और नकारात्मक [[ चर (प्रोग्रामिंग) |चर (क्रमादेशन)]] को सम्मिलित करने वाली समस्याओं को हमेशा मानक रूप में एक समान समस्या में लिखा जा सकता है।
 === उदाहरण ===
-मान लीजिए कि एक किसान के पास कृषि भूमि का एक टुकड़ा है, जो  L कि.मी<sup>2</sup> है, गेहूं या जौ या फिर दोनों के संयोजन के साथ लगाया जाना। किसान के पास सीमित मात्रा में उर्वरक, F किलोग्राम और कीटनाशक, P किलोग्राम है। गेहूं के हर वर्ग किलोमीटर में  ''F''<sub>1</sub> किलोग्राम उर्वरक और ''P''<sub>1</sub> किलोग्राम कीटनाशक की आवश्यकता होती है, जबकि जौ के प्रत्येक वर्ग किलोमीटर में ''F''<sub>2</sub> किलोग्राम उर्वरक और ''P''<sub>2</sub> किलोग्राम कीटनाशक की आवश्यकता होती है। मान लीजिए S<sub>1</sub> प्रति वर्ग किलोमीटर गेहूं का विक्रय मूल्य है, और S<sub>2</sub> जौ का विक्रय मूल्य है। अगर हम क्रमशः ''x''<sub>1</sub> और ''x''<sub>2</sub> द्वारा गेहूं और जौ के साथ लगाए गए भूमि के क्षेत्र को दर्शाते हैं, तो  ''x''<sub>1</sub> और ''x''<sub>2</sub> के लिए इष्टतम मान चुनकर लाभ को अधिकतम किया जा सकता है। इस समस्या को मानक रूप में निम्नलिखित रैखिक प्रोग्रामिंग समस्या के साथ व्यक्त किया जा सकता है:
+मान लीजिए कि एक किसान के पास कृषि भूमि का एक टुकड़ा है, जो  L कि.मी<sup>2</sup> है, गेहूं या जौ या फिर दोनों के संयोजन के साथ लगाया जाना। किसान के पास सीमित मात्रा में उर्वरक, F किलोग्राम और कीटनाशक, P किलोग्राम है। गेहूं के हर वर्ग किलोमीटर में  ''F''<sub>1</sub> किलोग्राम उर्वरक और ''P''<sub>1</sub> किलोग्राम कीटनाशक की आवश्यकता होती है, जबकि जौ के प्रत्येक वर्ग किलोमीटर में ''F''<sub>2</sub> किलोग्राम उर्वरक और ''P''<sub>2</sub> किलोग्राम कीटनाशक की आवश्यकता होती है। मान लीजिए S<sub>1</sub> प्रति वर्ग किलोमीटर गेहूं का विक्रय मूल्य है, और S<sub>2</sub> जौ का विक्रय मूल्य है। अगर हम क्रमशः ''x''<sub>1</sub> और ''x''<sub>2</sub> द्वारा गेहूं और जौ के साथ लगाए गए भूमि के क्षेत्र को दर्शाते हैं, तो  ''x''<sub>1</sub> और ''x''<sub>2</sub> के लिए इष्टतम मान चुनकर लाभ को अधिकतम किया जा सकता है। इस समस्या को मानक रूप में निम्नलिखित रैखिक क्रमादेशन समस्या के साथ व्यक्त किया जा सकता है:
 {|
 |-
@@ Line 79: / Line 79: @@
-== संवर्धित रूप (सुस्त रूप) ==
+== संवर्धित रूप (शिथिल रूप) ==
-सिम्प्लेक्स एल्गोरिथ्म के सामान्य रूप को लागू करने के लिए रैखिक प्रोग्रामिंग समस्याओं को संवर्धित फार्म में परिवर्तित किया जा सकता है। इस प्रपत्र में बाधाओं में समानता के साथ असमानताओं को बदलने के लिए गैर-नकारात्मक [[सुस्त चर]] का परिचय है। तब समस्याओं को निम्न [[ब्लॉक आव्यूह]] रूप में लिखा जा सकता है:
+सिम्प्लेक्स एल्गोरिथ्म के सामान्य रूप को लागू करने के लिए रैखिक क्रमादेशन समस्याओं को संवर्धित फार्म में परिवर्तित किया जा सकता है। इस प्रपत्र में व्यवरोधओं में समानता के साथ असमानताओं को बदलने के लिए ऋणेतर-संख्या [[सुस्त चर|शिथिल चर]] का परिचय है। तब समस्याओं को निम्न [[ब्लॉक आव्यूह]] रूप में लिखा जा सकता है:
 : अधिकतम <math>z</math>:
 : <math>
@@ Line 95: / Line 95: @@
 </math>
 :<math>\mathbf{x} \ge  0, \mathbf{s} \ge 0</math>
-जहां <math>\mathbf{s}</math> नव प्रवर्तित निम्न सुस्त चर हैं, <math>\mathbf{x}</math> निर्णय चर हैं, और <math>z</math> अधिकतम किया जाने वाला चर है।
+जहां <math>\mathbf{s}</math> नव प्रवर्तित निम्न शिथिल चर हैं, <math>\mathbf{x}</math> निर्णय चर हैं, और <math>z</math> अधिकतम किया जाने वाला चर है।
 === उदाहरण ===
@@ Line 120: / Line 120: @@
 |
 |}
-जहां <math>x_3, x_4, x_5</math> (गैर-नकारात्मक) सुस्त चर हैं, जो इस उदाहरण में अप्रयुक्त क्षेत्र, अप्रयुक्त उर्वरक की मात्रा और अप्रयुक्त कीटनाशक की मात्रा का प्रतिनिधित्व करते हैं।
+जहां <math>x_3, x_4, x_5</math> (ऋणेतर-संख्या) शिथिल चर हैं, जो इस उदाहरण में अप्रयुक्त क्षेत्र, अप्रयुक्त उर्वरक की मात्रा और अप्रयुक्त कीटनाशक की मात्रा का प्रतिनिधित्व करते हैं।
 आव्यूह रूप में यह बन जाता है:
@@ Line 144: / Line 144: @@
 {{Main|द्वैत रैखिक प्रोग्राम}}
-प्रत्येक रैखिक प्रोग्रामिंग समस्या, जिसे मूल समस्या कहा जाता है, जिसको [[द्वैत समस्या]] में परिवर्तित किया जा सकता है, जो मूल समस्या के इष्टतम मूल्य के लिए एक ऊपरी बाध्य प्रदान करता है। आव्यूह रूप में, हम मूल समस्या को इस रूप में व्यक्त कर सकते हैं:
+प्रत्येक रैखिक क्रमादेशन समस्या, जिसे मूल समस्या कहा जाता है, जिसको [[द्वैत समस्या]] में परिवर्तित किया जा सकता है, जो मूल समस्या के इष्टतम मूल्य के लिए एक ऊपरी बाध्य प्रदान करता है। आव्यूह रूप में, हम मूल समस्या को इस रूप में व्यक्त कर सकते हैं:
 : अधिकतम '''c'''<sup>T</sup>'''x''' का विषय है ''A'''''x''' ≤ '''b''', '''x''' ≥ 0;
-:इसी सममित दोहरी समस्या के साथ,
+:इसी सममित द्वैत समस्या के साथ,
 :न्यूनतम '''b'''<sup>T</sup>'''y''' का विषय है ''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0.
@@ Line 153: / Line 153: @@
 : अधिकतम '''c'''<sup>T</sup>'''x''' का विषय है ''A'''''x''' ≤ '''b''';
-:: संबंधित असममित दोहरी समस्या के साथ,
+:: संबंधित असममित द्वैत समस्या के साथ,
 ::न्यूनतम '''b'''<sup>T</sup>'''y''' का विषय है ''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0.
-द्वैत सिद्धांत के दो मौलिक विचार हैं। एक तथ्य है कि (सममित द्वैत के लिए) एक दोहरी रेखीय प्रोग्राम का मूल रेखीय प्रोग्राम है। इसके अलावा, रैखिक प्रोग्राम का हर व्यवहार्य हल यह है कि वह इस दोहरे फंक्शन के अनुकूलतम प्रकार्य के इष्टतम मान को बाध्य करता है। दुर्बल द्वैत प्रमेय का मत है कि द्वैत के व्यावहारिक मान का किसी भी व्यावहारिक हल में वस्तुनिष्ठ फलन मान किसी भी व्यावहारिक समाधान में आदि की तुलना में बड़ा या बराबर होता है। प्रबल द्वैत प्रमेय के अनुसार, यदि मूल में इष्टतम विलयन होता है,  तो x<sup>*</sup>, तो दोहरी भी एक इष्टतम समाधान है,  y<sup>**</sup>, और cTx*=bTy*
+द्वैत सिद्धांत के दो मौलिक विचार हैं। एक तथ्य है कि (सममित द्वैत के लिए) एक द्वैत रैखिक क्रमादेशन का मूल रैखिक क्रमादेशन है। इसके अलावा, रैखिक क्रमादेशन का हर सुसंगत हल यह है कि वह इस द्वैती फलन के अनुकूलतम प्रकार्य के इष्टतम मान को बाध्य करता है। दुर्बल द्वैत प्रमेय का मत है कि द्वैत के आभ्यासिक मान का किसी भी आभ्यासिक हल में वस्तुनिष्ठ फलन मान किसी भी आभ्यासिक समाधान में आदि की तुलना में बड़ा या बराबर होता है। प्रबल द्वैत प्रमेय के अनुसार, यदि मूल में इष्टतम विलयन होता है,  तो x<sup>*</sup>, तो द्वैत भी एक इष्टतम समाधान है,  y<sup>**</sup>, और cTx*=bTy*
-एक रैखिक प्रोग्राम भी असीम या अपरिमेय हो सकता है। द्वैत सिद्धांत में कहा गया है कि यदि मूल अबद्ध है तो द्वैत के दुर्बल प्रमेय के द्वारा द्वय असाध्य है। इसी तरह यदि द्वय असाध्य है तो मूलज को अपाय नहीं किया जा सकता। दुहरे और आदि दोनों के लिए अव्यावहारिक होना सम्भव है। विवरण और कई और उदाहरण के लिए [[ दोहरी रैखिक कार्यक्रम |दोहरी रैखिक कार्यक्रम]] देखें।
+एक रैखिक क्रमादेशन भी असीम या अपरिमेय हो सकता है। द्वैत सिद्धांत में कहा गया है कि यदि मूल अबद्ध है तो द्वैत के दुर्बल प्रमेय के द्वारा द्वय असाध्य है। इसी तरह यदि द्वय असाध्य है तो मूलज को अपाय नहीं किया जा सकता। द्वैत और आदि दोनों के लिए अआभ्यासिक होना सम्भव है। विवरण और कई और उदाहरण के लिए [[ दोहरी रैखिक कार्यक्रम |द्वैत रैखिक क्रमादेशन]] देखें।
 == विविधताएं ==
-=== दोहरी सामग्री को ढंकना। ===
+=== द्वैत को ढंकना/पैक करना। ===
-आवरण एलपी प्रपत्र का एक रैखिक प्रोग्राम है:
+आवरण एलपी प्रपत्र का एक रैखिक क्रमादेशन है:
 : न्यूनतम: '''b'''<sup>T</sup>'''y,'''
 : विषय है: <big>''A''<sup>T</sup>'''y''' ≥ '''c''', '''y''' ≥ 0</big>,
-जैसे कि मैट्रिक्स ए और वैक्टर बी और सी गैर-नकारात्मक हैं।
+जैसे कि आव्यूह ए और सदिश बी और सी ऋणेतर-संख्या हैं।
-आवरण एलपी का दोहरा एक पैकिंग एलपी है, जो कि प्रपत्र का एक रैखिक प्रोग्राम है:
+आवरण एलपी का द्वैती एक पैकिंग एलपी है, जो कि प्रपत्र का एक रैखिक क्रमादेशन है:
 : अधिकतम '''c'''<sup>T</sup>'''x,'''
 : विषय है: <big>''A'''''x''' ≤ '''b''', '''x''' ≥ 0</big>,
-जैसे कि मैट्रिक्स ए और वैक्टर बी और सी गैर नकारात्मक हैं।
+जैसे कि आव्यूह ए और सदिश बी और सी ऋणेतर-संख्या हैं।
 ==== उदाहरण ====
-ढ़कने और पैकिंग एलपीएस सामान्यतः एक रेखीय प्रोग्रामिंग समस्या के रूप में उत्पन्न होते हैं और सन्निकटन एल्गोरिथ्म के अध्ययन में महत्वपूर्ण होते हैं।<ref>{{harvtxt|Vazirani|2001|p=112}}</ref> उदाहरण के लिए, सेट पैकिंग समस्या के एल. पी. छूट, स्वतंत्र सेट समस्या और मिलान समस्या एलपीएस पैक कर रही है। सेट कवर समस्या के एलपी छूट शिरोबिंदु आवरण समस्या, और लंबित सेट समस्या भी एलपीएस को कवर कर रहे हैं।
+ढ़कने और पैकिंग एलपीएस सामान्यतः एक रैखिक क्रमादेशन समस्या के रूप में उत्पन्न होते हैं और सन्निकटन एल्गोरिथ्म के अध्ययन में महत्वपूर्ण होते हैं।<ref>{{harvtxt|Vazirani|2001|p=112}}</ref> उदाहरण के लिए, समुच्चय पैकिंग समस्या के एल. पी. छूट, स्वतंत्र समुच्चय समस्या और मिलान समस्या एलपीएस पैक कर रही है। समुच्चय कवर समस्या के एलपी छूट शिरोबिंदु आवरण समस्या, और लंबित समुच्चय समस्या भी एलपीएस को कवर कर रहे हैं।
-ग्राफ का भिन्नात्मक रंग ढूँढना आच्छादी एलपी का एक अन्य उदाहरण है। इस स्थिति में एक बाधा ग्राफ के प्रत्येक शीर्ष के लिए और एक चर के लिए ग्राफ के प्रत्येक स्वतंत्र सेट के लिए है।
+ग्राफ का भिन्नात्मक रंग ढूँढना आच्छादी एलपी का एक अन्य उदाहरण है। इस स्थिति में एक व्यवरोध ग्राफ के प्रत्येक शीर्ष के लिए और एक चर के लिए ग्राफ के प्रत्येक स्वतंत्र समुच्चय के लिए है।
 == पूरक शिथिलता ==
-जब प्रथम के अनुकूलतम समाधान को पूरक ढलवां प्रमेय के प्रयोग से ही जाना जाता है तो इस दोहरे इष्टतम समाधान को प्राप्त करना संभव होता है। प्रमेय कहता है:
+जब प्रथम के अनुकूलतम समाधान को पूरक शिथिलता प्रमेय के प्रयोग से ही जाना जाता है तो इस द्वैती इष्टतम समाधान को प्राप्त करना संभव होता है। प्रमेय कहता है:
-मान लीजिए x = (x1, x2,…, एक्सएन) प्राथमिक सुसंगत है और वह y = (y1, y2,…, ym) दोहरी सुसंगत है। मानलो की (w1, w2,…, डब्ल्यूएम) इसी प्राथमिक सुस्त चर को दर्शाता है, और मानलो (z1, z2, ... , zn) संगत दोहरे सुस्त चर को निरूपित करते हैं। तब x और y उनकी संबंधित समस्याओं के लिए इष्टतम हैं यदि और केवल यदि
+मान लीजिए x = (x1, x2,…, एक्सएन) प्राथमिक सुसंगत है और वह y = (y1, y2,…, ym) द्वैत सुसंगत है। मानलो की (w1, w2,…, डब्ल्यूएम) इसी प्राथमिक शिथिल चर को दर्शाता है, और मानलो (z1, z2, ... , zn) संगत द्वैती शिथिल चर को निरूपित करते हैं। तब x और y उनकी संबंधित समस्याओं के लिए इष्टतम हैं यदि और केवल यदि
 * '''x'''<sub>''j''</sub> '''z'''<sub>''j''</sub> = 0, के लिए ''j'' = 1, 2, ... , ''n'', और
 * '''w'''<sub>''i''</sub> '''y'''<sub>''i''</sub> = 0, के लिए ''i'' = 1, 2, ... , ''m.''
-इसलिए यदि प्रारंभिक का i-th सुस्त चर शून्य नहीं है, तो दोहरे का i-th चर शून्य के बराबर है। इसी तरह, यदि दोहरे का j-th सुस्त चर शून्य नहीं है, तो प्रारंभिक का j-th चर शून्य के बराबर है।
+इसलिए यदि प्रारंभिक का i-th शिथिल चर शून्य नहीं है, तो द्वैती का i-th चर शून्य के बराबर है। इसी तरह, यदि द्वैती का j-th शिथिल चर शून्य नहीं है, तो प्रारंभिक का j-th चर शून्य के बराबर है।
-अनुकूलतम अर्थव्यवस्था की यह आवश्यक शर्त काफी सरल आर्थिक सिद्धांत को दर्शाती है। मानक रूप में (अधिकतम करते समय), अगर एक विवश प्राथमिक संसाधन में सुस्त है (यानी, "बचे हुए" हैं), फिर उस संसाधन की अतिरिक्त मात्रा का कोई मूल्य नहीं होना चाहिए। इसी तरह, यदि दोहरी (छाया) कीमत में गैर-नकारात्मकता बाधा आवश्यकता में कमी है, यानी कीमत शून्य नहीं है, तो वहाँ दुर्लभ आपूर्ति (कोई "बचा नहीं" होना चाहिए)।
+अनुकूलतम अर्थव्यवस्था की यह आवश्यक शर्त काफी सरल आर्थिक सिद्धांत को दर्शाती है। मानक रूप में (अधिकतम करते समय), अगर एक विवश प्राथमिक संसाधन में शिथिल है (यानी, "बचे हुए" हैं), फिर उस संसाधन की अतिरिक्त मात्रा का कोई मूल्य नहीं होना चाहिए। इसी तरह, यदि द्वैत (छाया) कीमत में ऋणेतर-संख्याता व्यवरोध आवश्यकता में कमी है, यानी कीमत शून्य नहीं है, तो वहाँ दुर्लभ आपूर्ति (कोई "बचा नहीं" होना चाहिए)।
 == सिद्धांत ==
 === इष्टतम समाधानों का अस्तित्व ===
-ज्यामितीय दृष्टि से, रैखिक बाधाएं व्यवहार्य क्षेत्र को परिभाषित करती हैं, जो उत्तल बहुफलक है। रैखिक प्रकार्य, एक उत्तल फलन है, जिसका अर्थ है कि प्रत्येक स्थानीय न्यूनतम वैश्विक न्यूनतम होता है; इसी तरह रैखिक प्रकार्य भी अवतल ही होता है, जिसका अर्थ है कि प्रत्येक स्थानीय अधिकतम एक वैश्विक अधिकतम है।
+ज्यामितीय दृष्टि से, रैखिक व्यवरोधएं सुसंगत क्षेत्र को परिभाषित करती हैं, जो उत्तल बहुफलक है। रैखिक प्रकार्य, एक उत्तल फलन है, जिसका अर्थ है कि प्रत्येक स्थानीय न्यूनतम वैश्विक न्यूनतम होता है; इसी तरह रैखिक प्रकार्य भी अवतल ही होता है, जिसका अर्थ है कि प्रत्येक स्थानीय अधिकतम एक वैश्विक अधिकतम है।
-एक इष्टतम समाधान की आवश्यकता नहीं है, दो कारणों से सबसे पहले, यदि बाधाएँ असंगत हैं, तो कोई संभव समाधान मौजूद नहीं है: उदाहरण के लिए बाधाओं  x ≥ 2 और x ≤ 1 संयुक्त रूप से संतुष्ट नहीं किया जा सकता है; इस मामले में, हम कहते हैं कि एलपी अक्षम्य है। दूसरा, जब बहुटोपी वस्तुनिष्ठ प्रकार्य की प्रवणता की दिशा में असीम होता है (जहाँ वस्तुनिष्ठ फलन की प्रवणता वस्तुनिष्ठ फलन के गुणांकों का सदिश है), तब कोई इष्टतम मान प्राप्त नहीं होता है क्योंकि उद्देश्य फलन के किसी परिमित मान से बेहतर करना हमेशा संभव होता है।
+एक इष्टतम समाधान की आवश्यकता नहीं है, दो कारणों से सबसे पहले, यदि व्यवरोधएँ असंगत हैं, तो कोई संभव समाधान मौजूद नहीं है: उदाहरण के लिए व्यवरोधओं  x ≥ 2 और x ≤ 1 संयुक्त रूप से संतुष्ट नहीं किया जा सकता है; इस स्थिति में, हम कहते हैं कि एलपी अक्षम्य है। दूसरा, जब बहुटोपी वस्तुनिष्ठ प्रकार्य की प्रवणता की दिशा में असीम होता है (जहाँ वस्तुनिष्ठ फलन की प्रवणता वस्तुनिष्ठ फलन के गुणांकों का सदिश है), तब कोई इष्टतम मान प्राप्त नहीं होता है क्योंकि उद्देश्य फलन के किसी परिमित मान से बेहतर करना हमेशा संभव होता है।
 === बहुफलक के इष्टतम शीर्ष (और किरणें) ===
-अन्यथा, यदि कोई व्यवहार्य समाधान मौजूद है और यदि बाधा सेट बाध्य है, तो इष्टतम मूल्य हमेशा बाधा सेट की सीमा पर प्राप्त होता है, उत्तल कार्यों के लिए [[ अधिकतम सिद्धांत |अधिकतम सिद्धांत]]  द्वारा (अवतल कार्यों के लिए न्यूनतम सिद्धांत द्वारा वैकल्पिक रूप से) चूंकि रैखिक कार्य दोनों उत्तल और अवतल हैं। हालांकि कुछ समस्याओं में अलग इष्टतम समाधान है; उदाहरण के लिए, रैखिक असमानताओं की एक प्रणाली के लिए एक व्यवहार्य समाधान खोजने की समस्या एक रैखिक प्रोग्रामिंग समस्या है जिसमें उद्देश्य फलन शून्य कार्य है (अर्थात, हर जगह मान शून्य लेने वाला निरंतर कार्य) इस व्यवहार्यता समस्या के लिए इसके उद्देश्य-कार्य के लिए शून्य-फ़ंक्शन के साथ, यदि दो भिन्न समाधान हैं, तो समाधानों का प्रत्येक उत्तल संयोजन एक समाधान है।
+अन्यथा, यदि कोई सुसंगत समाधान मौजूद है और यदि व्यवरोध समुच्चय बाध्य है, तो इष्टतम मूल्य हमेशा व्यवरोध समुच्चय की सीमा पर प्राप्त होता है, उत्तल कार्यों के लिए [[ अधिकतम सिद्धांत |अधिकतम सिद्धांत]]  द्वारा (अवतल कार्यों के लिए न्यूनतम सिद्धांत द्वारा वैकल्पिक रूप से) चूंकि रैखिक कार्य दोनों उत्तल और अवतल हैं। चूंकि कुछ समस्याओं में अलग इष्टतम समाधान है; उदाहरण के लिए, रैखिक असमिकाओं की एक प्रणाली के लिए एक सुसंगत समाधान खोजने की समस्या एक रैखिक क्रमादेशन समस्या है जिसमें उद्देश्य फलन शून्य कार्य है (अर्थात, हर जगह मान शून्य लेने वाला निरंतर कार्य) इस सुसंगतता समस्या के लिए इसके उद्देश्य-कार्य के लिए शून्य-फलन के साथ, यदि दो भिन्न समाधान हैं, तो समाधानों का प्रत्येक उत्तल संयोजन एक समाधान है।
-पॉलीटॉप के शीर्षों को मूल व्यवहार्य समाधान भी कहा जाता  है। नाम के इस चुनाव का कारण इस प्रकार है। मान लीजिए d चरों की संख्या को निरूपित करता है। तब रैखिक असमानताओं का मूलभूत प्रमेय निकलता है (व्यवहार्य समस्याओं के लिए) कि हर शीर्ष के लिए एलपी व्यवहार्य क्षेत्र का x* एलपी से डी (या कम) असमानता बाधाओं का एक सेट मौजूद है जैसे कि, जब हम उन d व्यवरोधों को समानता के रूप में मानते हैं, तो अद्वितीय समाधान x* होता है। जिससे हम एलपी समाधानों की निरंतरता के बजाय सभी बाधाओं (एक असतत सेट) के सेट के कुछ सबसेट को देखकर इन शिखरों का अध्ययन कर सकते हैं। यह सिद्धांत रैखिक कार्यक्रमों को हल करने के लिए सिम्पलेक्स एल्गोरिथम को रेखांकित करता है।
+पॉलीटॉप के शीर्षों को मूल सुसंगत समाधान भी कहा जाता  है। नाम के इस चुनाव का कारण इस प्रकार है। मान लीजिए d चरों की संख्या को निरूपित करता है। तब रैखिक असमिकाओं का मूलभूत प्रमेय निकलता है (सुसंगत समस्याओं के लिए) कि हर शीर्ष के लिए एलपी सुसंगत क्षेत्र का x* एलपी से डी (या कम) असमानता व्यवरोधओं का एक समुच्चय मौजूद है जैसे कि, जब हम उन d व्यवरोधों को समानता के रूप में मानते हैं, तो अद्वितीय समाधान x* होता है। जिससे हम एलपी समाधानों की निरंतरता के बजाय सभी व्यवरोधओं (एक असतत समुच्चय) के समुच्चय के कुछ सबसमुच्चय को देखकर इन शिखरों का अध्ययन कर सकते हैं। यह सिद्धांत रैखिक क्रमादेशनों को हल करने के लिए सिम्पलेक्स एल्गोरिथम को रेखांकित करता है।
-== एल्गोरिदम ==
+== एल्गोरिथम ==
-{{See also|संख्यात्मक विश्लेषण विषयों की सूची $  रैखिक प्रोग्रामिंग}}
+{{See also|संख्यात्मक विश्लेषण विषयों की सूची $  रैखिक क्रमादेशन}}
-[[File:Linear Programming Feasible Region.svg|frame|एक रैखिक प्रोग्रामिंग समस्या में, रैखिक बाधाओं की एक श्रृंखला उन चरों के संभावित मानों का एक उत्तल सेट व्यवहार्य क्षेत्र उत्पन्न करती है। द्वि-चर मामले में यह क्षेत्र उत्तल सरल बहुभुज के आकार में है।]]
+[[File:Linear Programming Feasible Region.svg|frame|एक रैखिक क्रमादेशन समस्या में, रैखिक व्यवरोधओं की एक श्रृंखला उन चरों के संभावित मानों का एक उत्तल समुच्चय सुसंगत क्षेत्र उत्पन्न करती है। द्वि-चर स्थिति में यह क्षेत्र उत्तल सरल बहुभुज के आकार में है।]]
-=== आधार विनिमय एल्गोरिदम ===
+=== आधार विनिमय एल्गोरिथम ===
 ==== डेंटज़िग की सिंप्लेक्स एल्गोरिथम ====
-में [[ जॉर्ज डेंट्ज़िग |जॉर्ज डेंट्ज़िग]] द्वारा विकसित सिंप्लेक्स एल्गोरिदम, एलपी समस्याओं को पॉलिटोपे के शीर्ष पर व्यवहार्य समाधान के निर्माण द्वारा हल करता है और फिर पॉलीटोपे के किनारों पर एक पथ के साथ वस्तुनिष्ठ समारोह के गैरघटते मूल्यों के शीर्ष पर चलना जब तक निश्चित रूप से अधिकतम नहीं पहुंच जाता है। कई व्यावहारिक समस्याओं में, "स्टॉलिंग" होता है: कई पिवोट्स उद्देश्य फलन में कोई वृद्धि के साथ किए जाते हैं।<ref name="DT03">{{harvtxt|Dantzig|Thapa|2003}}</ref><ref name="Padberg">{{harvtxt|Padberg|1999}}</ref> दुर्लभ व्यावहारिक समस्याओं में, सिम्प्लेक्स एल्गोरिथम के सामान्य संस्करण वास्तव में "चक्र" हो सकते हैं।<ref name="Padberg" /> चक्रों से बचने के लिए शोधकर्ताओं ने मतदान के नए नियम बनाये।<ref name="FukudaTerlaky">{{cite journal|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य|journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor=Thomas M. Liebling |editor2=Dominique de Werra|year=1997|doi=10.1007/BF02614325|mr=1464775|citeseerx=10.1.1.36.9373|s2cid=2794181}}</ref>
+में [[ जॉर्ज डेंट्ज़िग |जॉर्ज डेंट्ज़िग]] द्वारा विकसित सिंप्लेक्स एल्गोरिथम, एलपी समस्याओं को पॉलिटोपे के शीर्ष पर सुसंगत समाधान के निर्माण द्वारा हल करता है और फिर पॉलीटोपे के कोर पर एक पथ के साथ वस्तुनिष्ठ फलन के गैरघटते मूल्यों के शीर्ष पर चलना जब तक निश्चित रूप से अधिकतम नहीं पहुंच जाता है। कई आभ्यासिक समस्याओं में, "स्टॉलिंग" होता है: कई पिवोट्स उद्देश्य फलन में कोई वृद्धि के साथ किए जाते हैं।<ref name="DT03">{{harvtxt|Dantzig|Thapa|2003}}</ref><ref name="Padberg">{{harvtxt|Padberg|1999}}</ref> दुर्लभ आभ्यासिक समस्याओं में, सिम्प्लेक्स एल्गोरिथम के सामान्य संस्करण वास्तव में "चक्र" हो सकते हैं।<ref name="Padberg" /> चक्रों से बचने के लिए शोधकर्ताओं ने मतदान के नए नियम बनाये।<ref name="FukudaTerlaky">{{cite journal|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य|journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor=Thomas M. Liebling |editor2=Dominique de Werra|year=1997|doi=10.1007/BF02614325|mr=1464775|citeseerx=10.1.1.36.9373|s2cid=2794181}}</ref>
-प्रयोग में, सिम्पलेक्स एल्गोरिदम काफी कुशल है और अगर चक्र चलाने के खिलाफ कुछ सावधानियां बरती जाएं तो वैश्विक इष्टतम खोजने की गारंटी दी जा सकती है। सिम्पलेक्स एल्गोरिथम "यादृच्छिक" समस्याओं को कुशलता से हल करने के लिए सिद्ध हुआ है, अर्थात चरणों की एक घन संख्या में, <ref>{{harvtxt|Borgwardt|1987}}</ref> जो व्यावहारिक समस्याओं पर अपने व्यवहार के समान है।<ref name="DT03" /><ref name="Todd">{{harvtxt|Todd|2002}}</ref>
+प्रयोग में, सिम्पलेक्स एल्गोरिथम काफी कुशल है और अगर चक्र चलाने के खिलाफ कुछ सावधानियां बरती जाएं तो वैश्विक इष्टतम खोजने की गारंटी दी जा सकती है। सिम्पलेक्स एल्गोरिथम "यादृच्छिक" समस्याओं को कुशलता से हल करने के लिए सिद्ध हुआ है, अर्थात चरणों की एक घन संख्या में, <ref>{{harvtxt|Borgwardt|1987}}</ref> जो आभ्यासिक समस्याओं पर अपने व्यवहार के समान है।<ref name="DT03" /><ref name="Todd">{{harvtxt|Todd|2002}}</ref>
-चूकि, सिम्पलेक्स एल्गोरिथम में यह सबसे बुरी करने वाली  स्थिति है: क्ले और मिन्टी ने रैखिक प्रोग्रामिंग समस्याओं के एक परिवार का निर्माण किया, जिसके लिए सिंप्लेक्स विधि समस्या के आकार में कई चरणों की गणना की।<ref name="DT03" /><ref name="Murty">{{harvtxt|Murty|1983}}</ref><ref name="PS">{{harvtxt|Papadimitriou|Steiglitz|}}</ref> वास्तव में, कुछ समय के लिए यह ज्ञात नहीं था कि क्या रैखिक प्रोग्रामिंग समस्या बहुपद समय में व्याख्या करने योग्य था, वास्तव में, कुछ समय के लिए यह ज्ञात नहीं था कि क्या रैखिक प्रोग्रामिंग समस्या बहुपद समय में व्याख्या करने योग्य थी, यानी [[ पी (जटिलता) |पी (जटिलता)]] वर्ग।
+चूकि, सिम्पलेक्स एल्गोरिथम में यह सबसे खराब करने वाली  स्थिति है: क्ले और मिन्टी ने रैखिक क्रमादेशन समस्याओं के एक परिवार का निर्माण किया, जिसके लिए सिंप्लेक्स विधि समस्या के आकार में कई चरणों की गणना की।<ref name="DT03" /><ref name="Murty">{{harvtxt|Murty|1983}}</ref><ref name="PS">{{harvtxt|Papadimitriou|Steiglitz|}}</ref> वास्तव में, कुछ समय के लिए यह ज्ञात नहीं था कि क्या रैखिक क्रमादेशन समस्या बहुपद समय में व्याख्या करने योग्य था, वास्तव में, कुछ समय के लिए यह ज्ञात नहीं था कि क्या रैखिक क्रमादेशन समस्या बहुपद समय में व्याख्या करने योग्य थी, यानी [[ पी (जटिलता) |पी (जटिलता)]] वर्ग।
 ==== [[ क्रिस-क्रॉस एल्गोरिथम ]] ====
-डेंटज़िग के सिंप्लेक्स एल्गोरिथम की तरह, क्रिस-क्रॉस एल्गोरिथम एक आधार-विनिमय एल्गोरिथम है जो आधारों के बीच पिवट करता है। हालांकि, क्रॉस क्रॉस एल्गोरिदम को व्यवहार्यता बनाए रखने की आवश्यकता नहीं है, बल्कि एक व्यवहार्य आधार से एक अक्षम्य आधार पर धुरी कर सकता है। क्रस-क्रॉस एल्गोरिथ्म में रेखीय प्रोग्रामिंग के लिए बहुपदीय [[समय की जटिलता]] नहीं होती है। दोनों एल्गोरिदम आयाम D में एक (परेशान)[[ इकाई घन ]]के सभी 2<sup>''D''</sup> कोनों पर जाते हैं, क्ले-मिन्टी क्यूब, सबसे खराब स्थिति में।<ref name="FukudaTerlaky" /><ref name="Roos">{{cite journal|last=Roos|first=C.|title=क्रिस-क्रॉस सिम्प्लेक्स विधि के लिए टेरलाकी के धुरी नियम के लिए एक घातीय उदाहरण|journal=Mathematical Programming|volume=46|year=1990|series=Series A|doi=10.1007/BF01585729|mr=1045573 |issue=1|pages=79–84|s2cid=33463483}}</ref>
+डेंटज़िग के सिंप्लेक्स एल्गोरिथम की तरह, क्रिस-क्रॉस एल्गोरिथम एक आधार-विनिमय एल्गोरिथम है जो आधारों के बीच पिवट करता है। चूंकि, क्रॉस क्रॉस एल्गोरिथम को सुसंगतता बनाए रखने की आवश्यकता नहीं है, बल्कि एक सुसंगत आधार से एक अक्षम्य आधार पर धुरी कर सकता है। क्रस-क्रॉस एल्गोरिथ्म में रैखिक क्रमादेशन के लिए बहुपदीय [[समय की जटिलता]] नहीं होती है। दोनों एल्गोरिथम आयाम D में एक (परेशान)[[ इकाई घन ]]के सभी 2<sup>''D''</sup> कोनों पर जाते हैं, क्ले-मिन्टी क्यूब, सबसे खराब स्थिति में है।<ref name="FukudaTerlaky" /><ref name="Roos">{{cite journal|last=Roos|first=C.|title=क्रिस-क्रॉस सिम्प्लेक्स विधि के लिए टेरलाकी के धुरी नियम के लिए एक घातीय उदाहरण|journal=Mathematical Programming|volume=46|year=1990|series=Series A|doi=10.1007/BF01585729|mr=1045573 |issue=1|pages=79–84|s2cid=33463483}}</ref>
 === आंतरिक बिंदु ===
-सिम्पलेक्स एल्गोरिथम के विपरीत, जो पॉलीहेड्रल समुच्चय पर शीर्षों के बीच किनारों को पार करके इष्टतम समाधान ढूंढता है, आंतरिक-बिंदु विधियाँ व्यवहार्य क्षेत्र के आंतरिक भाग  के माध्यम से  गुजरती हैं।
+सिम्पलेक्स एल्गोरिथम के विपरीत, जो पॉलीहेड्रल समुच्चय पर शीर्षों के बीच कोर को पार करके इष्टतम समाधान ढूंढता है, आंतरिक-बिंदु विधियाँ सुसंगत क्षेत्र के आंतरिक भाग  के माध्यम से  गुजरती हैं।
 ==== खाचियां के बाद दीर्घवृत्ताभ एल्गोरिथम ====
-रैखिक प्रोग्रामिंग के लिए यह अब तक का सबसे खराब स्थिति वाला बहुपद-समय एल्गोरिथम है। एक समस्या है जो ''n'' चर है हल करने के लिए और  ''L'' इनपुट बिट्स में एन्कोडेड किया जा सकता है, यह एल्गोरिथ्म <math> O(n^6 L) </math> समय में चलता है।<ref name = "khachiyan79" /> लियोनिद खाचियान ने 1979 में दीर्घवृत्ताभ पद्धति की शुरुआत के साथ इस लंबे समय से चली आ रही जटिलता के मुद्दे को हल किया।अभिसरण विश्लेषण में (वास्तविक संख्या) पूर्ववर्ती हैं, विशेष रूप से Naum Z.Shore द्वारा विकसित [[पुनरावृत्ति विधियाँ]] और Arkadi Nemirovski और D. Yudin द्वारा सन्निकटन एल्गोरिदम।
+रैखिक क्रमादेशन के लिए यह अब तक का सबसे खराब स्थिति वाला बहुपद-समय एल्गोरिथम है। एक समस्या है जो ''n'' चर है हल करने के लिए और  ''L'' इनपुट बिट्स में एन्कोडेड किया जा सकता है, यह एल्गोरिथ्म <math> O(n^6 L) </math> समय में चलता है।<ref name = "khachiyan79" /> लियोनिद खाचियान ने 1979 में दीर्घवृत्ताभ पद्धति की शुरुआत के साथ इस लंबे समय से चली आ रही जटिलता के मुद्दे को हल किया।अभिसरण विश्लेषण में (वास्तविक संख्या) पूर्ववर्ती हैं, विशेष रूप से Naum Z.Shore द्वारा विकसित [[पुनरावृत्ति विधियाँ]] और Arkadi Nemirovski और D. Yudin द्वारा सन्निकटन एल्गोरिथम।
 ==== कर्मकार का प्रक्षेपी एल्गोरिथम ====
 {{main|कर्मरकर्स एल्गोरिथम}}
-रेखीय कार्यक्रमों की बहुपद-समय विलेयता स्थापित करने के लिए खाचियां की एल्गोरिथ्म ऐतिहासिकता को महत्व दी थी। एल्गोरिथ्म एक कम्प्यूटेशनल ब्रेक-थ्रू नहीं था, एक सिंप्लेक्स विधि रैखिक कार्यक्रमों के विशेष रूप से निर्मित परिवारों के अलावा सभी के लिए अधिक कुशल है।
+रैखिक क्रमादेशनों की बहुपद-समय विलेयता स्थापित करने के लिए खाचियां की एल्गोरिथ्म ऐतिहासिकता को महत्व दी थी। एल्गोरिथ्म एक अभिकलनी ब्रेक-थ्रू नहीं था, एक सिंप्लेक्स विधि रैखिक क्रमादेशनों के विशेष रूप से निर्मित परिवारों के अलावा सभी के लिए अधिक कुशल है।
-हालांकि, खाचियां की एल्गोरिथ्म ने रैखिक प्रोग्रामिंग में अनुसंधान की नई पंक्तियों को प्रेरित किया। 1984 में, एन.कर्मरकर ने रैखिक प्रोग्रामिंग के लिए एक [[प्रक्षेपी विधि]] प्रस्तावित की। कारमार्कर की एल्गोरिथ्म<ref name = "karmarkar84" /> से खाचियां<ref name = "khachiyan79" /> की सबसे बुरी बहुपद बाउंड में सुधार हुआ और (दिया <math>O(n^{3.5}L)</math>). कारमार्कर ने दावा किया कि उनके एल्गोरिथ्म सरल विधि की तुलना में व्यावहारिक एलपी में बहुत तेज थे, एक दावा जिसने इंटीरियर-पॉइंट विधियों में बहुत रुचि पैदा की।<ref name="Strang">{{cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=कर्मकार का एल्गोरिथ्म और अनुप्रयुक्त गणित में उसका स्थान|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> कर्मकार की खोज के बाद से, कई आंतरिक-बिंदु विधियों का प्रस्ताव और विश्लेषण किया गया है।
+चूंकि, खाचियां की एल्गोरिथ्म ने रैखिक क्रमादेशन में अनुसंधान की नई पंक्तियों को प्रेरित किया। 1984 में, एन.कर्मरकर ने रैखिक क्रमादेशन के लिए एक [[प्रक्षेपी विधि]] प्रस्तावित की। कारमार्कर की एल्गोरिथ्म<ref name = "karmarkar84" /> से खाचियां<ref name = "khachiyan79" /> की सबसे खराब बहुपद बाउंड में सुधार हुआ और (दिया <math>O(n^{3.5}L)</math>). कारमार्कर ने दावा किया कि उनके एल्गोरिथ्म सिंप्लेक्स विधि की तुलना में आभ्यासिक एलपी में बहुत तेज थे, एक दावा जिसने इंटीरियर-पॉइंट विधियों में बहुत रुचि पैदा की।<ref name="Strang">{{cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=कर्मकार का एल्गोरिथ्म और अनुप्रयुक्त गणित में उसका स्थान|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> कर्मकार की खोज के बाद से, कई आंतरिक-बिंदु विधियों का प्रस्ताव और विश्लेषण किया गया है।
 ==== वैद्य की 87 एल्गोरिथ्म ====
@@ Line 234: / Line 234: @@
 में वैद्य ने एक एल्गोरिथ्म भी प्रस्तावित किया जो <math> O(n^3) </math> समय में चलता है।<ref>{{cite conference|title= रैखिक प्रोग्रामिंग के लिए एक एल्गोरिदम जिसके लिए <गणित> {O} (((m+ n) n^2+(m+ n)^{1.5} n) L)</math> अंकगणितीय संचालन की आवश्यकता होती है| conference = 28th Annual IEEE Symposium on Foundations of Computer Science | series = FOCS |last1=Vaidya|first1=Pravin M. |year=1987 }}</ref>
 ==== वैद्य की 89 एल्गोरिथ्म ====
-में वैद्य ने एक अल्गोरिथ्म विकसित किया जो <math>O(n^{2.5})</math> समय में चलता है।<ref>{{cite conference|chapter= Speeding-up linear programming using fast matrix multiplication | conference = कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी| series = FOCS |last1=Vaidya|first1=Pravin M. | title = कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी|year=1989| pages = 332–337| doi = 10.1109/SFCS.1989.63499 | isbn = 0-8186-1982-1}}</ref>  औपचारिक रूप से, एल्गोरिथ्म सबसे खराब स्थिति में  <math>O( (n+d)^{1.5} n L)</math> अंकगणितीय संचालन लेता है, जहां <math>d</math> बाधाओं की संख्या है, <math> n </math> चर की संख्या है, और <math>L</math> बिट्स की संख्या है।
+में वैद्य ने एक अल्गोरिथ्म विकसित किया जो <math>O(n^{2.5})</math> समय में चलता है।<ref>{{cite conference|chapter= Speeding-up linear programming using fast matrix multiplication | conference = कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी| series = FOCS |last1=Vaidya|first1=Pravin M. | title = कंप्यूटर विज्ञान की नींव पर 30वीं वार्षिक संगोष्ठी|year=1989| pages = 332–337| doi = 10.1109/SFCS.1989.63499 | isbn = 0-8186-1982-1}}</ref>  औपचारिक रूप से, एल्गोरिथ्म सबसे खराब स्थिति में  <math>O( (n+d)^{1.5} n L)</math> अंकगणितीय संचालन लेता है, जहां <math>d</math> व्यवरोधओं की संख्या है, <math> n </math> चर की संख्या है, और <math>L</math> बिट्स की संख्या है।
-==== इनपुट स्पार्सिटी टाइम एल्गोरिदम ====
+==== इनपुट स्पार्सिटी टाइम एल्गोरिथम ====
 में, ली और सिद्फोर्ड ने दिखाया कि, इसे में हल किया जा सकता है <math>\tilde O((nnz(A) + d^2)\sqrt{d}L)</math> समय में<ref>{{cite conference|title= रैखिक प्रोग्रामिंग के लिए कुशल उलटा रखरखाव और तेज एल्गोरिदम| conference = FOCS '15 Foundations of Computer Science |last1=Lee|first1=Yin-Tat|last2=Sidford|first2=Aaron |year=2015| arxiv = 1503.01752 }}</ref>, जहां <math>nnz(A)</math> गैर शून्य तत्वों की संख्या का प्रतिनिधित्व करता है, और यह सबसे खराब स्थिति में <math>O(n^{2.5}L)</math> लेता रहता है।
-==== वर्तमान मैट्रिक्स गुणन समय एल्गोरिथ्म ====
+==== वर्तमान आव्यूह गुणन समय एल्गोरिथ्म ====
-में, कोहेन, ली और सॉन्ग ने रनिंग टाइम को <math>\tilde O( ( n^{\omega} + n^{2.5-\alpha/2} + n^{2+1/6} ) L)</math> समय में सुधार किया,  <math> \omega </math> [[ मैट्रिक्स गुणन |आव्यूह गुणन]] का घातांक है और <math> \alpha </math> आव्यूह गुणन का दोहरा घातांक है।<ref>{{cite conference|title= वर्तमान मैट्रिक्स गुणन समय में रेखीय कार्यक्रमों को हल करना| conference = 51st Annual ACM Symposium on the Theory of Computing  |last1=Cohen|first1=Michael B.|last2=Lee|first2=Yin-Tat|last3=Song|first3=Zhao |year=2018| arxiv =  1810.07896 | series = STOC'19 }}</ref> α को (मोटे तौर पर) सबसे बड़ी संख्या के रूप में परिभाषित किया गया है जैसे कि एक <math> n \times n </math> आव्यूह को <math> n \times n^\alpha </math> आव्यूह द्वारा <math> O(n^2) </math> समय में गुणा किया जा सकता है। ली, सोंग और झांग द्वारा अनुवर्ती कार्य में, ये भिन्न पद्धति से एक ही परिणाम देते हैं।<ref>{{cite conference|title= वर्तमान मैट्रिक्स गुणन समय में अनुभवजन्य जोखिम न्यूनीकरण को हल करना| conference = Conference on Learning Theory |last1=Lee|first1=Yin-Tat|last2=Song|first2=Zhao |last3=Zhang|first3=Qiuyi|year=2019| arxiv = 1905.04447 | series = COLT'19 }}</ref> ये दो एल्गोरिदम <math>\tilde O( n^{2+1/6} L ) </math> रहते हैं जब ω = 2 और α = 1, जियांग, सोंग, वीनस्टीन और झांग के कारण <math> \tilde O ( n^{2+1/6} L) </math> से <math> \tilde O ( n^{2+1/18} L) </math> में सुधार हुआ।<ref>{{cite conference|title= तेज़ एलपी के लिए तेज़ गतिशील मैट्रिक्स व्युत्क्रम|last1=Jiang|first1=Shunhua|last2=Song|first2=Zhao |last3=Weinstein|first3=Omri|last4=Zhang|first4=Hengjie|year=2020| arxiv = 2004.07470 }}</ref>
+में, कोहेन, ली और सॉन्ग ने रनिंग टाइम को <math>\tilde O( ( n^{\omega} + n^{2.5-\alpha/2} + n^{2+1/6} ) L)</math> समय में सुधार किया,  <math> \omega </math> [[ मैट्रिक्स गुणन |आव्यूह गुणन]] का घातांक है और <math> \alpha </math> आव्यूह गुणन का द्वैती घातांक है।<ref>{{cite conference|title= वर्तमान मैट्रिक्स गुणन समय में रेखीय कार्यक्रमों को हल करना| conference = 51st Annual ACM Symposium on the Theory of Computing  |last1=Cohen|first1=Michael B.|last2=Lee|first2=Yin-Tat|last3=Song|first3=Zhao |year=2018| arxiv =  1810.07896 | series = STOC'19 }}</ref> α को (मोटे तौर पर) सबसे बड़ी संख्या के रूप में परिभाषित किया गया है जैसे कि एक <math> n \times n </math> आव्यूह को <math> n \times n^\alpha </math> आव्यूह द्वारा <math> O(n^2) </math> समय में गुणा किया जा सकता है। ली, सोंग और झांग द्वारा अनुवर्ती कार्य में, ये भिन्न पद्धति से एक ही परिणाम देते हैं।<ref>{{cite conference|title= वर्तमान मैट्रिक्स गुणन समय में अनुभवजन्य जोखिम न्यूनीकरण को हल करना| conference = Conference on Learning Theory |last1=Lee|first1=Yin-Tat|last2=Song|first2=Zhao |last3=Zhang|first3=Qiuyi|year=2019| arxiv = 1905.04447 | series = COLT'19 }}</ref> ये दो एल्गोरिथम <math>\tilde O( n^{2+1/6} L ) </math> रहते हैं जब ω = 2 और α = 1, जियांग, सोंग, वीनस्टीन और झांग के कारण <math> \tilde O ( n^{2+1/6} L) </math> से <math> \tilde O ( n^{2+1/18} L) </math> में सुधार हुआ।<ref>{{cite conference|title= तेज़ एलपी के लिए तेज़ गतिशील मैट्रिक्स व्युत्क्रम|last1=Jiang|first1=Shunhua|last2=Song|first2=Zhao |last3=Weinstein|first3=Omri|last4=Zhang|first4=Hengjie|year=2020| arxiv = 2004.07470 }}</ref>
-=== आंतरिक-बिंदु विधियों और सिंप्लेक्स एल्गोरिदम की तुलना ===
+=== आंतरिक-बिंदु विधियों और सिंप्लेक्स एल्गोरिथम की तुलना ===
-वर्तमान राय यह है कि सिप्लेक्स आधारित पद्धतियों तथा आंतरिक बिंदु पद्धतियों के अच्छे कार्यान्वयन की क्षमता रैखिक प्रोग्रामिंग के सामान्य अनुप्रयोगों के लिए समान होती है। हालांकि, एलपी समस्याओं के विशिष्ट प्रकार के लिए, यह हो सकता है कि एक प्रकार का सॉल्वर दूसरे से बेहतर हो (कभी-कभी बहुत बेहतर), और यह कि आंतरिक बिंदु पद्धति बनाम सिम्प्लेक्स आधारित विधियों द्वारा उत्पन्न समाधानों की संरचना, सामान्यतया बाद वाले के लिए सक्रिय चर के समर्थन सेट से बहुत भिन्न होती है।<ref>{{cite journal|doi=10.1016/S0377-2217(02)00061-9|title=धुरी बनाम आंतरिक बिंदु विधियाँ: पेशेवरों और विपक्ष|journal=European Journal of Operational Research|volume=140|issue=2|pages=170|year=2002|last1=Illés|first1=Tibor|last2=Terlaky|first2=Tamás|url=https://strathprints.strath.ac.uk/9200/|citeseerx=10.1.1.646.3539}}</ref>
+वर्तमान राय यह है कि सिप्लेक्स आधारित पद्धतियों तथा आंतरिक बिंदु पद्धतियों के अच्छे कार्यान्वयन की क्षमता रैखिक क्रमादेशन के सामान्य अनुप्रयोगों के लिए समान होती है। चूंकि, एलपी समस्याओं के विशिष्ट प्रकार के लिए, यह हो सकता है कि एक प्रकार का सॉल्वर दूसरे से बेहतर हो (कभी-कभी बहुत बेहतर), और यह कि आंतरिक बिंदु पद्धति बनाम सिम्प्लेक्स आधारित विधियों द्वारा उत्पन्न समाधानों की संरचना, सामान्यतया बाद वाले के लिए सक्रिय चर के समर्थन समुच्चय से बहुत भिन्न होती है।<ref>{{cite journal|doi=10.1016/S0377-2217(02)00061-9|title=धुरी बनाम आंतरिक बिंदु विधियाँ: पेशेवरों और विपक्ष|journal=European Journal of Operational Research|volume=140|issue=2|pages=170|year=2002|last1=Illés|first1=Tibor|last2=Terlaky|first2=Tamás|url=https://strathprints.strath.ac.uk/9200/|citeseerx=10.1.1.646.3539}}</ref>
 == खुली समस्याएं और हाल का काम ==
 {{unsolved|कंप्यूटर विज्ञान|रैखिक प्रोग्रामिंग एक जोरदार बहुपद समय एल्गोरिथ्म स्वीकार करता है?}}
-रैखिक प्रोग्रामन के सिद्धांत में कई खुली समस्याएं हैं, जिसका समाधान गणित में मूलभूत उपलब्धियों का प्रतिनिधित्व करता है और बड़े पैमाने पर रैखिक कार्यक्रमों को हल करने की हमारी क्षमता में संभावित बड़ी प्रगति का प्रतिनिधित्व करता है।
+रैखिक क्रमादेशन के सिद्धांत में कई खुली समस्याएं हैं, जिसका समाधान गणित में मूलभूत उपलब्धियों का प्रतिनिधित्व करता है और बड़े पैमाने पर रैखिक क्रमादेशनों को हल करने की हमारी क्षमता में संभावित बड़ी प्रगति का प्रतिनिधित्व करता है।
-* क्या एलपी दृढ़ता से बहुपद-समय एल्गोरिदम स्वीकार करता है?
+* क्या एलपी दृढ़ता से बहुपद-समय एल्गोरिथम स्वीकार करता है?
-* क्या एलपी सख्ती से पूरक समाधान खोजने के लिए दृढ़ता से बहुपद-समय एल्गोरिदम स्वीकार करता है?
+* क्या एलपी सख्ती से पूरक समाधान खोजने के लिए दृढ़ता से बहुपद-समय एल्गोरिथम स्वीकार करता है?
-* क्या एलपी गणना के वास्तविक संख्या (इकाई लागत) मॉडल में बहुपद-समय एल्गोरिदम स्वीकार करता है?
+* क्या एलपी गणना के वास्तविक संख्या (इकाई लागत) मॉडल में बहुपद-समय एल्गोरिथम स्वीकार करता है?
-वीं सदी की 18 सबसे बड़ी अनसुलझी समस्याओं में से [[स्टीफन स्मेल]] द्वारा समस्याओं के इस निकट संबंधी समूह का हवाला दिया गया है। स्मेल के शब्दों में, समस्या का तीसरा संस्करण "रैखिक प्रोग्रामिंग सिद्धांत की मुख्य अनसुलझी समस्या है " जबकि एल्गोरिदम कमजोर बहुपद समय में रैखिक प्रोग्रामिंग को हल करने के लिए मौजूद हैं, जैसे दीर्घवृत्ताभ विधियाँ और [[ आंतरिक बिंदु विधि |आंतरिक बिंदु विधि]], कोई एल्गोरिथ्म अभी तक नहीं पाया गया है जो बाधाओं की संख्या और चर की संख्या में दृढ़ता से बहुपद समय प्रदर्शन की अनुमति देता है। इस तरह के अल्गोरिथ्म का विकास अत्यंत सैद्धांतिक रुचि का होगा और संभवतः बड़े पैमाने पर एलपी के समाधान में व्यावहारिक लाभ की अनुमति देता है।
+वीं सदी की 18 सबसे बड़ी अनसुलझी समस्याओं में से [[स्टीफन स्मेल]] द्वारा समस्याओं के इस निकट संबंधी समूह का हवाला दिया गया है। स्मेल के शब्दों में, समस्या का तीसरा संस्करण "रैखिक क्रमादेशन सिद्धांत की मुख्य अनसुलझी समस्या है " जबकि एल्गोरिथम कमजोर बहुपद समय में रैखिक क्रमादेशन को हल करने के लिए मौजूद हैं, जैसे दीर्घवृत्ताभ विधियाँ और [[ आंतरिक बिंदु विधि |आंतरिक बिंदु विधि]], कोई एल्गोरिथ्म अभी तक नहीं पाया गया है जो व्यवरोधओं की संख्या और चर की संख्या में दृढ़ता से बहुपद समय प्रदर्शन की अनुमति देता है। इस तरह के अल्गोरिथ्म का विकास अत्यंत सैद्धांतिक रुचि का होगा और संभवतः बड़े पैमाने पर एलपी के समाधान में आभ्यासिक लाभ की अनुमति देता है।
 हालाँकि हाल ही में उच्च आयामों के लिए [[ हिर्श अनुमान ]] को अस्वीकृत कर दिया गया था, फिर भी यह निम्नलिखित प्रश्नों को खुला छोड़ देता है।
-* क्या वहां धुरी नियम हैं जो बहुपद समय सिम्प्लेक्स वेरिएंट को जन्म देते हैं?
+* क्या वहां धुरी नियम हैं जो बहुपद समय सिम्प्लेक्स विचरण को जन्म देते हैं?
 * क्या सभी पॉलीटोपल ग्राफ़ का बहुपद रूप से बाध्य व्यास है?
-ये प्रश्न निष्पादन विश्लेषण और सिम्प्लेक्स जैसे तरीकों के विकास से संबंधित हैं। सिम्प्लेक्स एल्गोरिथ्म की, अपने घातीय समय सैद्धांतिक प्रदर्शन संकेत के बावजूद, व्यवहार में अत्यधिक दक्षता की यह बात है कि बहुपदीय या अत्यंत बहुपदीय समय में संचालित सिम्प्लेक्स की भिन्नता हो सकती है। यह जानने के लिए महान व्यावहारिक और सैद्धांतिक महत्व होगा कि क्या इस तरह के किसी भी संस्करण विशेष रूप से यह तय करने के दृष्टिकोण के रूप में मौजूद हैं कि एलपी को दृढ़ता से बहुपद समय में हल किया जा सकता है या नहीं।
+ये प्रश्न निष्पादन विश्लेषण और सिम्प्लेक्स जैसे तरीकों के विकास से संबंधित हैं। सिम्प्लेक्स एल्गोरिथ्म की, अपने घातीय समय सैद्धांतिक प्रदर्शन संकेत के बावजूद, व्यवहार में अत्यधिक दक्षता की यह बात है कि बहुपदीय या अत्यंत बहुपदीय समय में संचालित सिम्प्लेक्स की भिन्नता हो सकती है। यह जानने के लिए महान आभ्यासिक और सैद्धांतिक महत्व होगा कि क्या इस तरह के किसी भी संस्करण विशेष रूप से यह तय करने के दृष्टिकोण के रूप में मौजूद हैं कि एलपी को दृढ़ता से बहुपद समय में हल किया जा सकता है या नहीं।
-सिम्पलेक्स एल्गोरिथम और इसके वेरिएंट एज-फॉलोइंग एल्गोरिदम के परिवार में आते हैं, यह नाम इसलिए रखा गया क्योंकि वे पॉलिटोप के किनारों के साथ-साथ रेखीय प्रोग्रामिंग समस्याओं को वर्टेक्स से शीर्ष पर ले जाते हैं। इसका मतलब यह है कि उनका सैद्धांतिक प्रदर्शन एलपी पॉलीटॉप पर किन्हीं दो सिरों के बीच किनारों की अधिकतम संख्या तक सीमित है। परिणामस्वरूप, हम पॉलिटोपल ग्राफ के अधिकतम [[ग्राफ]] सैद्धांतिक [[व्यास]] को जानने में रुचि रखते हैं। यह सिद्ध किया जा चुका है कि सभी पॉलीटोप्स में सबक्स्पेन्सियल व्यास होता है। हिर्श अनुमान का हालिया खंडन यह साबित करने के लिए पहला कदम है कि क्या किसी पॉलीटोप में सुपरपोलिनोमियल व्यास है। यदि कोई ऐसी पॉलिटोप मौजूद है तो बहुपद के समय में कोई भिन्नता नहीं चल सकती है। पॉलीटोप व्यास के बारे में प्रश्न स्वतंत्र गणितीय हित के हैं।
+सिम्पलेक्स एल्गोरिथम और इसके विचरण कोर-फॉलोइंग एल्गोरिथम के परिवार में आते हैं, यह नाम इसलिए रखा गया क्योंकि वे पॉलिटोप के कोर के साथ-साथ रैखिक क्रमादेशन समस्याओं को शीर्ष से शीर्ष पर ले जाते हैं। इसका मतलब यह है कि उनका सैद्धांतिक प्रदर्शन एलपी पॉलीटॉप पर किन्हीं दो सिरों के बीच कोर की अधिकतम संख्या तक सीमित है। परिणामस्वरूप, हम पॉलिटोपल ग्राफ के अधिकतम [[ग्राफ]] सैद्धांतिक [[व्यास]] को जानने में रुचि रखते हैं। यह सिद्ध किया जा चुका है कि सभी पॉलीटोप्स में सबक्स्पेन्सियल व्यास होता है। हिर्श अनुमान का हालिया खंडन यह साबित करने के लिए पहला कदम है कि क्या किसी पॉलीटोप में सुपरपोलिनोमियल व्यास है। यदि कोई ऐसी पॉलिटोप मौजूद है तो बहुपद के समय में कोई भिन्नता नहीं चल सकती है। पॉलीटोप व्यास के बारे में प्रश्न स्वतंत्र गणितीय हित के हैं।
-सिम्पलेक्स पिवट विधियाँ मौलिक (या दोहरी) व्यवहार्यता को संरक्षित करती हैं। दूसरी ओर, क्रिस-क्रॉस धुरी विधियां (प्राथमिक या दोहरी) व्यवहार्यता को संरक्षित नहीं रखती हैं - वे किसी भी क्रम में प्राथमिक व्यवहार्य, दोहरी या मौलिक और असाध्य आधार पर जा सकते हैं। इस प्रकार की धुराग्र प्रणालियों का 1970 के दशक से अध्ययन किया गया था।<ref>{{Cite journal |last1=Anstreicher |first1=Kurt M. |last2=Terlaky |first2=Tamás |date=1994 |title=रैखिक प्रोग्रामिंग के लिए एक मोनोटोनिक बिल्ड-अप सिम्प्लेक्स एल्गोरिदम|url=https://www.jstor.org/stable/171894 |journal=Operations Research |volume=42 |issue=3 |pages=556–561 |doi=10.1287/opre.42.3.556 |jstor=171894 |issn=0030-364X}}</ref> अनिवार्य रूप से, ये विधियाँ रैखिक प्रोग्रामिंग समस्या के तहत व्यवस्था पॉलीटॉप पर सबसे छोटी धुरी पथ खोजने का प्रयास करती हैं। पॉलीटॉपल ग्राफ़ के विपरीत, व्यवस्था पॉलीटोप्स के ग्राफ़ को छोटे व्यास के लिए जाना जाता है, सामान्य बहुपदीय के व्यास के बारे में प्रश्नों के समाधान के बिना प्रबल बहुपद समय क्रिस-क्रॉस धुरी अल्गोरिथ्म की संभावना की अनुमति मिलती है।<ref name="FukudaTerlaky" />
+सिम्पलेक्स पिवट विधियाँ मौलिक (या द्वैत) सुसंगतता को संरक्षित करती हैं। दूसरी ओर, क्रिस-क्रॉस धुरी विधियां (प्राथमिक या द्वैत) सुसंगतता को संरक्षित नहीं रखती हैं - वे किसी भी क्रम में प्राथमिक सुसंगत, द्वैत या मौलिक और असाध्य आधार पर जा सकते हैं। इस प्रकार की धुराग्र प्रणालियों का 1970 के दशक से अध्ययन किया गया था।<ref>{{Cite journal |last1=Anstreicher |first1=Kurt M. |last2=Terlaky |first2=Tamás |date=1994 |title=रैखिक प्रोग्रामिंग के लिए एक मोनोटोनिक बिल्ड-अप सिम्प्लेक्स एल्गोरिदम|url=https://www.jstor.org/stable/171894 |journal=Operations Research |volume=42 |issue=3 |pages=556–561 |doi=10.1287/opre.42.3.556 |jstor=171894 |issn=0030-364X}}</ref> अनिवार्य रूप से, ये विधियाँ रैखिक क्रमादेशन समस्या के तहत व्यवस्था पॉलीटॉप पर सबसे छोटी धुरी पथ खोजने का प्रयास करती हैं। पॉलीटॉपल ग्राफ़ के विपरीत, व्यवस्था पॉलीटोप्स के ग्राफ़ को छोटे व्यास के लिए जाना जाता है, सामान्य बहुपदीय के व्यास के बारे में प्रश्नों के समाधान के बिना प्रबल बहुपद समय क्रिस-क्रॉस धुरी अल्गोरिथ्म की संभावना की अनुमति मिलती है।<ref name="FukudaTerlaky" />
 == पूर्णांक अज्ञात ==
-यदि सभी अज्ञात चर को पूर्णांक होने की आवश्यकता होती है, तब इस समस्या को [[ पूर्णांक प्रोग्रामिंग | पूर्णांक प्रोग्रामिंग]] (आईपी) या पूर्णांक रैखिक प्रोग्रामन (आईएलपी) समस्या कहते हैं। रैखिक प्रोग्रामिंग के विपरीत, जो बुरी स्थिति में कुशलतापूर्वक हल किया जा सकता है, पूर्णांक प्रोग्रामिंग समस्याएँ कई व्यावहारिक स्थितियों में होती हैं (उनमें परिबद्ध चर होते हैं) [[ एनपी कठिन |एनपी कठिन]]। 0-1 पूर्णांक प्रोग्रामिंग या द्विआधारी पूर्णांक प्रोग्रामन (बीआईपी) पूर्णांक प्रोग्रामिंग का विशेष मामला है जहां चर को 0 या 1 (मनमानी पूर्णांक के बजाय)  होना आवश्यक है। इस समस्या को एनपी-हार्ड के रूप में भी वर्गीकृत किया गया है, और वास्तव में निर्णय संस्करण कार्प की 21 एनपी-पूर्ण समस्याओं में से एक था।
+यदि सभी अज्ञात चर को पूर्णांक होने की आवश्यकता होती है, तब इस समस्या को [[ पूर्णांक प्रोग्रामिंग | पूर्णांक क्रमादेशन]] (आईपी) या पूर्णांक रैखिक क्रमादेशन (आईएलपी) समस्या कहते हैं। रैखिक क्रमादेशन के विपरीत, जो खराब स्थिति में कुशलतापूर्वक हल किया जा सकता है, पूर्णांक क्रमादेशन समस्याएँ कई आभ्यासिक स्थितियों में होती हैं (उनमें परिबद्ध चर होते हैं) [[ एनपी कठिन |एनपी हार्ड]]। 0-1 पूर्णांक क्रमादेशन या द्विआधारी पूर्णांक क्रमादेशन (बीआईपी) पूर्णांक क्रमादेशन का विशेष स्थिति है जहां चर को 0 या 1 (मनमानी पूर्णांक के बजाय)  होना आवश्यक है। इस समस्या को एनपी-हार्ड के रूप में भी वर्गीकृत किया गया है, और वास्तव में निर्णय संस्करण कार्प की 21 एनपी-पूर्ण समस्याओं में से एक था।
-अगर केवल कुछ अज्ञात चरों को पूर्णांक होने की आवश्यकता होती है, तब इस प्रश्न को मिश्रित पूर्णांक (रैखिक) प्रोग्रामन (एमआईपी या मिल्प) समस्या कहते हैं। ये आम तौर पर एनपी-हार्ड भी होते हैं क्योंकि ये आईएलपी प्रोग्राम से भी अधिक सामान्य होते हैं।
+अगर केवल कुछ अज्ञात चरों को पूर्णांक होने की आवश्यकता होती है, तब इस प्रश्न को मिश्रित पूर्णांक (रैखिक) क्रमादेशन (एमआईपी या मिल्प) समस्या कहते हैं। ये आम तौर पर एनपी-हार्ड भी होते हैं क्योंकि ये आईएलपी क्रमादेशन से भी अधिक सामान्य होते हैं।
-हालांकि आईपी और एमआईपी समस्याओं के कुछ महत्वपूर्ण उपवर्ग हैं जो कुशलता से हल करने योग्य हैं,सर्वाधिक प्रमुख समस्या जिसमें बाधा मैट्रिक्स [[ पूरी तरह से एकरूप |पूरी तरह से एकरूप]] है और बाधाओं के दाईं ओर के पक्ष पूर्णांक या उससे भी अधिक सामान्य हैं-जहां सिस्टम में [[ कुल दोहरी अखंडता | कुल दोहरी अखंडता]] है (टीडीआई) संपत्ति है।
+चूंकि आईपी और एमआईपी समस्याओं के कुछ महत्वपूर्ण उपवर्ग हैं जो कुशलता से हल करने योग्य हैं,सर्वाधिक प्रमुख समस्या जिसमें व्यवरोध आव्यूह [[ पूरी तरह से एकरूप |पूरी तरह से एकरूप]] है और व्यवरोधओं के दाईं ओर के पक्ष पूर्णांक या उससे भी अधिक सामान्य हैं-जहां सिस्टम में [[ कुल दोहरी अखंडता | कुल द्वैत अखंडता]] है (टीडीआई) संपत्ति है।
-पूर्णांक रेखीय कार्यक्रमों को हल करने के लिए उन्नत एल्गोरिदम में शामिल हैं:
+पूर्णांक रैखिक क्रमादेशनों को हल करने के लिए उन्नत एल्गोरिथम में शामिल हैं:
-* [[ कटिंग-प्लेन विधि ]]
+* [[ कटिंग-प्लेन विधि | कटिंग-समतल विधि]]
 * [[ शाखा और बंधन ]]
 * [[ शाखा और कट ]]
 * शाखा और मूल्य
 * यदि इस समस्या के संरचना में कुछ अतिरिक्त है, तो देरी से स्तंभ निर्माण लागू करना संभव हो सकता है।
-इस तरह के पूर्णांक-प्रोग्रामिंग एल्गोरिदम पर पैडबर्ग और ब्यासले द्वारा चर्चा की गई है।
+इस तरह के पूर्णांक-क्रमादेशन एल्गोरिथम पर पैडबर्ग और ब्यासले द्वारा चर्चा की गई है।
-== इंटीग्रल लीनियर प्रोग्राम ==
+== इंटीग्रल लीनियर क्रमादेशन ==
 {{further|अभिन्न पॉलीटोप}}
-वास्तविक चर में रैखिक प्रोग्राम को अभिन्न कहा जाता है यदि इसमें कम से कम एक इष्टतम समाधान होता है जो अभिन्न है, यानी, केवल पूर्णांक मूल्यों से बना है। इसी तरह, एक बहुध्रुव <math>P = \{x \mid Ax \ge 0\}</math> को अभिन्न माना जाता है यदि सभी बाध्य व्यवहार्य उद्देश्य कार्यों के लिए सी रैखिक कार्यक्रम ''<math>\{\max cx \mid x \in P\}</math>'' इष्टतम है, ''<math>x^*</math>पूर्णांक निर्देशांक के साथ। जैसा कि 1977 में एडमंड्स और जाइल्स द्वारा देखा गया था, इस प्रकार कहा जा सकता है कि बहुध्रुव  <math>P</math>''  अभिन्न है अगर हर बाध्य व्यवहार्य अभिन्न उद्देश्य समारोह सी के लिए, रैखिक कार्यक्रम का इष्टतम मूल्य ''<math>\{\max cx \mid x \in P\}</math>एक पूर्णांक है।''
+वास्तविक चर में रैखिक क्रमादेशन को अभिन्न कहा जाता है यदि इसमें कम से कम एक इष्टतम समाधान होता है जो अभिन्न है, यानी, केवल पूर्णांक मूल्यों से बना है। इसी तरह, एक बहुध्रुव <math>P = \{x \mid Ax \ge 0\}</math> को अभिन्न माना जाता है यदि सभी बाध्य सुसंगत उद्देश्य कार्यों के लिए सी रैखिक क्रमादेशन ''<math>\{\max cx \mid x \in P\}</math>'' इष्टतम है, ''<math>x^*</math>पूर्णांक निर्देशांक के साथ। जैसा कि 1977 में एडमंड्स और जाइल्स द्वारा देखा गया था, इस प्रकार कहा जा सकता है कि बहुध्रुव  <math>P</math>''  अभिन्न है अगर हर बाध्य सुसंगत अभिन्न उद्देश्य फलन सी के लिए, रैखिक क्रमादेशन का इष्टतम मूल्य ''<math>\{\max cx \mid x \in P\}</math>एक पूर्णांक है।''
-अभिन्न रैखिक प्रोग्राम [[संयोजक अनुकूलन]] के बहुह्यादिक पहलू में केंद्रीय महत्व के होते हैं क्योंकि वे समस्या के वैकल्पिक लक्षण निर्धारण प्रदान करते हैं। किसी भी समस्या के लिए विशेष रूप से, समाधानों के उत्तल पतवार एक एकीकृत बहुफलक है; इस बहुध्रुव के पास यदि बढ़िया/सुसंहत विवरण है तो हम किसी रैखिक उद्देश्य से इष्टतम व्यवहार्य हल की खोज कर सकते हैं। इसके विपरीत, यदि हम यह साबित कर सकें कि एक रैखिक प्रोग्रामिंग विश्रांति समाकलित है तो यह व्यवहार्य (अभिन्न) समाधानों के उत्तल पतवार का वांछित वर्णन है।
+अभिन्न रैखिक क्रमादेशन [[संयोजक अनुकूलन]] के बहुह्यादिक पहलू में केंद्रीय महत्व के होते हैं क्योंकि वे समस्या के वैकल्पिक लक्षण निर्धारण प्रदान करते हैं। किसी भी समस्या के लिए विशेष रूप से, समाधानों के उत्तल पतवार एक एकीकृत बहुफलक है; इस बहुध्रुव के पास यदि बढ़िया/सुसंहत विवरण है तो हम किसी रैखिक उद्देश्य से इष्टतम सुसंगत हल की खोज कर सकते हैं। इसके विपरीत, यदि हम यह साबित कर सकें कि एक रैखिक क्रमादेशन विश्रांति समाकलित है तो यह सुसंगत (अभिन्न) समाधानों के उत्तल पतवार का वांछित वर्णन है।
 शब्दावली पूरे साहित्य में सुसंगत नहीं है, इसलिए किसी को निम्नलिखित दो अवधारणाओं में अंतर करने के लिए सावधान रहना चाहिए,
-* एक पूर्णांक रैखिक कार्यक्रम में, पिछले खंड में वर्णित, चर जबरन पूर्णांक होने के लिए विवश हैं, और यह समस्या सामान्य रूप से एनपी-हार्ड है,
+* एक पूर्णांक रैखिक क्रमादेशन में, पिछले खंड में वर्णित, चर जबरन पूर्णांक होने के लिए विवश हैं, और यह समस्या सामान्य रूप से एनपी-हार्ड है,
-*इस खंड में वर्णित एक अभिन्न रैखिक कार्यक्रम में, चर को पूर्णांक नहीं होने के लिए विवश नहीं किया जाता है बल्कि एक ने किसी तरह से साबित कर दिया है कि निरंतर समस्या का हमेशा एक इष्टतम मूल्य होता है (सी को मानना अभिन्न है), और इसे इष्टतम मूल्य कुशलता से पाया जा सकता है क्योंकि सभी बहुपद आकार के रेखीय कार्यक्रमों को बहुपद समय में हल किया जा सकता है।
+*इस खंड में वर्णित एक अभिन्न रैखिक क्रमादेशन में, चर को पूर्णांक नहीं होने के लिए विवश नहीं किया जाता है बल्कि एक ने किसी तरह से साबित कर दिया है कि निरंतर समस्या का हमेशा एक इष्टतम मूल्य होता है (सी को मानना अभिन्न है), और इसे इष्टतम मूल्य कुशलता से पाया जा सकता है क्योंकि सभी बहुपद आकार के रैखिक क्रमादेशनों को बहुपद समय में हल किया जा सकता है।
-यह साबित करने का एक सामान्य तरीका है कि बहुध्रुव अभिन्न है, यह दिखाने के लिए कि यह पूरी तरह से यूनिमॉड्यूलर है। पूर्णांक अपघटन संपत्ति और कुल दोहरी अभिन्नता सहित अन्य सामान्य विधियाँ हैं। अन्य विशिष्ट प्रसिद्ध अभिन्न एलपीएस में मिलान पॉलीटोप, लैटिस पॉलीहेड्रा, [[सबमॉड्यूलर]] प्रवाह पॉलीहेड्रा शामिल हैं, और दो सामान्यीकृत पॉलीमैट्रोइड्स/जी-पॉलीमेट्रोइड्स का प्रतिच्छेदन - उदा. श्रिजवर 2003 देखें।
+यह साबित करने का एक सामान्य तरीका है कि बहुध्रुव अभिन्न है, यह दिखाने के लिए कि यह पूरी तरह से यूनिमॉड्यूलर है। पूर्णांक अपघटन संपत्ति और कुल द्वैत अभिन्नता सहित अन्य सामान्य विधियाँ हैं। अन्य विशिष्ट प्रसिद्ध अभिन्न एलपीएस में मिलान पॉलीटोप, लैटिस बहुफलक, [[सबमॉड्यूलर]] प्रवाह बहुफलक शामिल हैं, और दो सामान्यीकृत पॉलीमैट्रोइड्स/जी-पॉलीमेट्रोइड्स का प्रतिच्छेदन - उदा. श्रिजवर 2003 देखें।
-== सॉल्वर और स्क्रिप्टिंग (प्रोग्रामिंग) भाषाएँ ==
+== सॉल्वर और स्क्रिप्टिंग (क्रमादेशन) भाषाएँ ==
 अनुज्ञेय मुफ्त सॉफ्टवेयर लाइसेंस लाइसेंस:
@@ Line 301: / Line 301: @@
 | [[Gekko_(optimization_software)|गेक्को]]||[[MIT License|एमआईटी लाइसेंस]]||बड़े पैमाने पर एलपी, [[क्यूपी]], [[क्यूसीक्यूपी]], [[एनएलपी]], और [[एमआईपी]] अनुकूलन को सुलझाने के लिए ओपन सोर्स लाइब्रेरी।
 |-
-| [[GLOP|जीएलओपी]]||[[Apache_License|अपाचे वी2]]||गूगल का ओपन-सोर्स लीनियर प्रोग्रामिंग सॉल्वर।
+| [[GLOP|जीएलओपी]]||[[Apache_License|अपाचे वी2]]||गूगल का ओपन-सोर्स लीनियर क्रमादेशन सॉल्वर।
 |-
 | [[Pyomo|पयोमो]]||[[BSD licenses|बीएसडी]]||व्यापक रैखिक, मिश्रित पूर्णांक और रैखिक अनुकूलन के लिए एक ओपन सोर्स मॉडलिंग भाषा।
 |-
-| [[SuanShu_numerical_library|सुआन शू]]||[[Apache_License|अपाचे वी2]]|| एलपी, [[क्यूपी, एसओसीपी]], [[एसडीपी]],[[एसक्यूपी]], जावा में वर्ग पी, को हल करने के लिए अनुकूलन एल्गोरिदम का एक ओपन-सोर्स सूट।
+| [[SuanShu_numerical_library|सुआन शू]]||[[Apache_License|अपाचे वी2]]|| एलपी, [[क्यूपी, एसओसीपी]], [[एसडीपी]],[[एसक्यूपी]], जावा में वर्ग पी, को हल करने के लिए अनुकूलन एल्गोरिथम का एक ओपन-सोर्स सूट।
 |}
 [[कॉपीलेफ़्ट]] (पारस्परिक) लाइसेंस:
@@ Line 316: / Line 316: @@
 |[[ALGLIB|एएलजीएलआईबी]]||जीपीएल 2+|| एएलजीएलआईबी परियोजना से एक एलपी सॉल्वर (C++, C#, Python)
 |-
-|[[Cassowary constraint solver|कैसोवेरी कंस्ट्रेंट् सॉल्वर]]||एलजीपीएल||एक वृद्धिशील कंस्ट्रेंट् को हल करने वाला टूलकिट जो कुशलतापूर्वक रैखिक समानता और असमानता की प्रणालियों को हल करता है
+|[[Cassowary constraint solver|कैसोवेरी व्यवरोध सॉल्वर]]||एलजीपीएल||एक वृद्धिशील व्यवरोध को हल करने वाला टूलकिट जो कुशलतापूर्वक रैखिक समानता और असमानता की प्रणालियों को हल करता है
 |-
 |[[COIN-OR CLP|सीएलपी]]||सीपीएल|| सीओआईएन-ओआर से एक एलपी सॉल्वर
 |-
-|[[GNU Linear Programming Kit|जीएलपीके]]||जीपीएल|| जीएनयू रैखिक प्रोग्रामिंग किट, एक एलपी/एमआईएलपी सॉल्वर के साथ नेटिव सी एपीआई और अन्य भाषाओं के लिए कई (15) तीसरे पक्ष के रैपर। [[प्रवाह नेटवर्क]] के लिए विशेषज्ञ समर्थन। [[एएमपीएल]] की तरह [[जीएनयू मैथप्रोग]] मॉडलिंग भाषा और अनुवादक को बंडल करता है।
+|[[GNU Linear Programming Kit|जीएलपीके]]||जीपीएल|| जीएनयू रैखिक क्रमादेशन किट, एक एलपी/एमआईएलपी सॉल्वर के साथ नेटिव सी एपीआई और अन्य भाषाओं के लिए कई (15) तीसरे पक्ष के रैपर। [[प्रवाह नेटवर्क]] के लिए विशेषज्ञ समर्थन। [[एएमपीएल]] की तरह [[जीएनयू मैथप्रोग]] मॉडलिंग भाषा और अनुवादक को बंडल करता है।
 |-
 |[[Qoca|क्यूओसीए]]||जीपीएल||विभिन्न लक्ष्य कार्यों के साथ रैखिक समीकरणों की क्रमिक रूप से हल करने वाली प्रणालियों के लिए एक पुस्तकालय
 |-
-|[[R-Project|आर-परियोजना]]||जीपीएल||सांख्यिकीय कंप्यूटिंग और ग्राफिक्स के लिए एक प्रोग्रामिंग भाषा और सॉफ्टवेयर वातावरण
+|[[R-Project|आर-परियोजना]]||जीपीएल||सांख्यिकीय अभिकलन और ग्राफिक्स के लिए एक क्रमादेशन भाषा और सॉफ्टवेयर वातावरण
 |}
-[[मिंटो]] (मिश्रित पूर्णांक अनुकूलक, एक पूर्णांक प्रोग्रामिंग सोलवर जो शाखा और परिबद्ध एल्गोरिथ्म का प्रयोग करता है) के पास सार्वजनिक रूप से उपलब्ध स्रोत कोड है,<ref>{{cite web|url=http://coral.ie.lehigh.edu/~minto/download.html|title=COR@L - लेहघ में कम्प्यूटेशनल अनुकूलन अनुसंधान|work=lehigh.edu}}</ref> लेकिन खुला स्रोत नहीं है।
+[[मिंटो]] (मिश्रित पूर्णांक अनुकूलक, एक पूर्णांक क्रमादेशन सोलवर जो शाखा और परिबद्ध एल्गोरिथ्म का प्रयोग करता है) के पास सार्वजनिक रूप से उपलब्ध स्रोत कोड है,<ref>{{cite web|url=http://coral.ie.lehigh.edu/~minto/download.html|title=COR@L - लेहघ में कम्प्यूटेशनल अनुकूलन अनुसंधान|work=lehigh.edu}}</ref> लेकिन ओपन स्रोत नहीं है।
 [[ मालिकाना सॉफ्टवेयर ]] लाइसेंस:
@@ Line 334: / Line 334: @@
 !संक्षिप्त जानकारी
 |-
-|[[AIMMS|एआईएमएमएस]]|| एक मॉडलिंग भाषा जो रैखिक, मिश्रित पूर्णांक और गैर-रेखीय अनुकूलन मॉडलों के माडल को अनुमति देती है। यह कंस्ट्रेंट् प्रोग्रामन के लिए एक उपकरण भी उपलब्ध कराता है। एल्गोरिथ्म, अनुमानी या सही विधियों, जैसे शाखा-और-कट या स्तंभ उत्पादन के रूप में भी कार्यान्वित किया जा सकता है। उपकरण हाथ में अनुकूलन समस्या को हल करने के लिए एक उपयुक्त सॉल्वर जैसे सीपीएलइएक्स या इसी तरह की कॉल करता है। शैक्षणिक लाइसेंस निःशुल्क हैं।
+|[[AIMMS|एआईएमएमएस]]|| एक मॉडलिंग भाषा जो रैखिक, मिश्रित पूर्णांक और गैर-रैखिक अनुकूलन मॉडलों के माडल को अनुमति देती है। यह व्यवरोध क्रमादेशन के लिए एक उपकरण भी उपलब्ध कराता है। एल्गोरिथ्म, अनुमानी या सही विधियों, जैसे शाखा-और-कट या स्तंभ उत्पादन के रूप में भी कार्यान्वित किया जा सकता है। उपकरण हाथ में अनुकूलन समस्या को हल करने के लिए एक उपयुक्त सॉल्वर जैसे सीपीएलइएक्स या इसी तरह की कॉल करता है। शैक्षणिक लाइसेंस निःशुल्क हैं।
 |-
 |[[ALGLIB|एएलजीएलआईबी]]|| कापीलेफ्ट लाइसेंसधारी पुस्तकालय का एक वाणिज्यिक संस्करण। C++, C#, Python.
 |-
-|[[AMPL|एएमपीएल]]|| बड़े पैमाने पर रैखिक, मिश्रित पूर्णांक और गैर-रैखिक अनुकूलन के लिए एक लोकप्रिय मॉडलिंग भाषा, एक मुफ्त छात्र सीमित संस्करण उपलब्ध है (500 चर और 500 कंस्ट्रेंट्)।
+|[[AMPL|एएमपीएल]]|| बड़े पैमाने पर रैखिक, मिश्रित पूर्णांक और गैर-रैखिक अनुकूलन के लिए एक लोकप्रिय मॉडलिंग भाषा, एक मुफ्त छात्र सीमित संस्करण उपलब्ध है (500 चर और 500 व्यवरोध)।
 |-
-|[[Analytica (software)|विश्लेषणात्मक]]|| एक सामान्य मॉडलिंग भाषा और इंटरैक्टिव विकास पर्यावरण। इसका प्रभाव आरेख उपयोगकर्ताओं को निर्णय चर, उद्देश्यों और बाधाओं के लिए नोड्स के साथ ग्राफ़ के रूप में समस्याओं को तैयार करने में सक्षम बनाता है। एनालिटिका ऑप्टिमाइज़र संस्करण में रैखिक, मिश्रित पूर्णांक और गैर-रैखिक सॉल्वर शामिल हैं और समस्या से मेल खाने के लिए सॉल्वर का चयन करता है। यह अन्य इंजनों को भी प्लग-इन के रूप में स्वीकार करता है, जिसमें [[एक्सप्रेस]], गयूरोबी, [[आर्टिलिस नाइट्रो]], और [[एमओएसइके]] शामिल हैं।
+|[[Analytica (software)|विश्लेषणात्मक]]|| एक सामान्य मॉडलिंग भाषा और इंटरैक्टिव विकास पर्यावरण। इसका प्रभाव आरेख उपयोगकर्ताओं को निर्णय चर, उद्देश्यों और व्यवरोधओं के लिए नोड्स के साथ ग्राफ़ के रूप में समस्याओं को तैयार करने में सक्षम बनाता है। एनालिटिका ऑप्टिमाइज़र संस्करण में रैखिक, मिश्रित पूर्णांक और गैर-रैखिक सॉल्वर शामिल हैं और समस्या से मेल खाने के लिए सॉल्वर का चयन करता है। यह अन्य इंजनों को भी प्लग-इन के रूप में स्वीकार करता है, जिसमें [[एक्सप्रेस]], गयूरोबी, [[आर्टिलिस नाइट्रो]], और [[एमओएसइके]] शामिल हैं।
 |-
-|[[APMonitor|एपीमॉनिटर]]|| मैटलैब और पायथन के लिए एपीआई। मैटलैब, पायथन, या वेब-इंटरफ़ेस के माध्यम से उदाहरण रैखिक प्रोग्रामिंग (एलपी) समस्याओं को हल करें।
+|[[APMonitor|एपीमॉनिटर]]|| मैटलैब और पायथन के लिए एपीआई। मैटलैब, पायथन, या वेब-इंटरफ़ेस के माध्यम से उदाहरण रैखिक क्रमादेशन (एलपी) समस्याओं को हल करें।
 |-
-|[[CPLEX|सीपीएलइएक्स]]|| कई प्रोग्रामिंग भाषाओं के लिए एक एपीआई के साथ लोकप्रिय सॉल्वर, और एक मॉडलिंग भाषा भी है और एक मॉडलिंग भाषा भी है और एआईएमएमएस, एएमपीएल, [[जीएएमएस]], एमपीएल, ओपेन-ऑप्ट, ओपीएल डेवलपमेंट स्टूडियो और [[टॉमलैब]] के साथ काम करती है।शैक्षणिक उपयोग के लिए निशुल्क।
+|[[CPLEX|सीपीएलइएक्स]]|| कई क्रमादेशन भाषाओं के लिए एक एपीआई के साथ लोकप्रिय सॉल्वर, और एक मॉडलिंग भाषा भी है और एक मॉडलिंग भाषा भी है और एआईएमएमएस, एएमपीएल, [[जीएएमएस]], एमपीएल, ओपेन-ऑप्ट, ओपीएल डेवलपमेंट स्टूडियो और [[टॉमलैब]] के साथ काम करती है।शैक्षणिक उपयोग के लिए निशुल्क।
 |-
-|[[एक्सेल]] सॉल्वर फलन|| स्प्रैडशीट्स में समायोजित एक अरेखीय सॉल्वर, जिसमें प्रकार्य मूल्यांकन, पुनर्गणना कोशिकाओं पर आधारित होता है। मूल संस्करण एक्सेल के लिए एक मानक ऐड-ऑन के रूप में उपलब्ध है।
+|[[एक्सेल]] सॉल्वर फलन|| स्प्रैडशीट्स में समायोजित एक अरैखिक सॉल्वर, जिसमें प्रकार्य मूल्यांकन, पुनर्गणना कोशिकाओं पर आधारित होता है। मूल संस्करण एक्सेल के लिए एक मानक ऐड-ऑन के रूप में उपलब्ध है।
 |-
 |[[FortMP|फोर्टएमपी]]||
@@ Line 352: / Line 352: @@
 |[[General Algebraic Modeling System|जीएएमएस]]||
 |-
-|[[IMSL Numerical Libraries|आईएमएसएल संख्यात्मक पुस्तकालय]]|| गणित और सांख्यिकीय एल्गोरिदम का संग्रह C/C++, Fortran, Java and C#/.NET. में उपलब्ध है। आईएमएसएल लाइब्रेरी में अनुकूलन नेमका में अनियंत्रित, रैखिक और अनालिनोरैली कंसल्टेंट न्यूमेरिजेशन तथा रैखिक प्रोग्रामिंग एल्गोरिथ्म शामिल हैं।
+|[[IMSL Numerical Libraries|आईएमएसएल संख्यात्मक पुस्तकालय]]|| गणित और सांख्यिकीय एल्गोरिथम का संग्रह C/C++, Fortran, Java and C#/.NET. में उपलब्ध है। आईएमएसएल लाइब्रेरी में अनुकूलन नेमका में अनियंत्रित, रैखिक और अनालिनोरैली कंसल्टेंट न्यूमेरिजेशन तथा रैखिक क्रमादेशन एल्गोरिथ्म शामिल हैं।
 |-
-|[[LINDO|एलआईएनडीओ]]|| रैखिक, पूर्णांक, वर्ग, शंकु और स्टॉचस्टिक प्रोग्रामिंग एक्सटेंशन्स के साथ सामान्य गैर-रेखीय प्रोग्राम के बड़े पैमाने पर अनुकूलन के लिए एक एपीआई के साथ एकल प्रयोक्ता है। यह निरंतर एवं विविक्त चर वाले सामान्य अरैखिक प्रोग्रामों के लिए वैश्विक इष्टतम समाधान की गारंटी के लिए वैश्विक अनुकूलन प्रक्रिया प्रदान करता है। इसमें मोंटे-कार्लो अनुरूपण को ऑप्टिमाइज़ेशन फ्रेमवर्क में एकीकृत करने के लिए सांख्यिकीय प्रतिचयन एपीआई भी है। इसमें एक बीजगणितीय मॉडलिंग भाषा ([[एलआईएनजीओ]]) है और एक स्प्रेडशीट ([[सबसे अच्छा क्या]]) के भीतर मॉडलिंग की अनुमति देता है।
+|[[LINDO|एलआईएनडीओ]]|| रैखिक, पूर्णांक, वर्ग, शंकु और स्टॉचस्टिक क्रमादेशन एक्सटेंशन्स के साथ सामान्य गैर-रैखिक क्रमादेशन के बड़े पैमाने पर अनुकूलन के लिए एक एपीआई के साथ एकल प्रयोक्ता है। यह निरंतर एवं विविक्त चर वाले सामान्य अरैखिक क्रमादेशनों के लिए वैश्विक इष्टतम समाधान की गारंटी के लिए वैश्विक अनुकूलन प्रक्रिया प्रदान करता है। इसमें मोंटे-कार्लो अनुरूपण को ऑप्टिमाइज़ेशन फ्रेमवर्क में एकीकृत करने के लिए सांख्यिकीय प्रतिचयन एपीआई भी है। इसमें एक बीजगणितीय मॉडलिंग भाषा ([[एलआईएनजीओ]]) है और एक स्प्रेडशीट ([[सबसे अच्छा क्या]]) के भीतर मॉडलिंग की अनुमति देता है।
 |-
-|[[Maple (software)|मेपल]]|| प्रतीकात्मक और संख्यात्मक कंप्यूटिंग के लिए एक सामान्य-उद्देश्य प्रोग्रामिंग-भाषा।
+|[[Maple (software)|मेपल]]|| प्रतीकात्मक और संख्यात्मक अभिकलन के लिए एक सामान्य-उद्देश्य क्रमादेशन-भाषा।
 |-
-|[[MATLAB|मैटलैब]]|| संख्यात्मक कंप्यूटिंग के लिए एक सामान्य-उद्देश्य और मैट्रिक्स-उन्मुख प्रोग्रामिंग-भाषा। मैटलैब में रैखिक प्रोग्रामिंग के लिए आधार मैटलैब उत्पाद के अतिरिक्त [[अनुकूलन टूलबॉक्स]] की आवश्यकता होती है; उपलब्ध रूटीन में इनटलीनप्रोग और लीनप्रोग शामिल हैं
+|[[MATLAB|मैटलैब]]|| संख्यात्मक अभिकलन के लिए एक सामान्य-उद्देश्य और आव्यूह-उन्मुख क्रमादेशन-भाषा। मैटलैब में रैखिक क्रमादेशन के लिए आधार मैटलैब उत्पाद के अतिरिक्त [[अनुकूलन टूलबॉक्स]] की आवश्यकता होती है; उपलब्ध रूटीन में इनटलीनप्रोग और लीनप्रोग शामिल हैं
 |-
-|[[Mathcad|मैथकैड]]|| एक वाइसिविग गणित संपादक। यह रैखिक और अरेखीय दोनों अनुकूलन समस्याओं को हल करने का कार्य करता है।
+|[[Mathcad|मैथकैड]]|| एक वाइसिविग गणित संपादक। यह रैखिक और अरैखिक दोनों अनुकूलन समस्याओं को हल करने का कार्य करता है।
 |-
-|[[Mathematica|गणितज्ञों]]|| प्रतीकात्मक और संख्यात्मक क्षमताओं सहित गणित के लिए एक सामान्य-उद्देश्य प्रोग्रामिंग-भाषा।
+|[[Mathematica|गणितज्ञों]]|| प्रतीकात्मक और संख्यात्मक क्षमताओं सहित गणित के लिए एक सामान्य-उद्देश्य क्रमादेशन-भाषा।
 |-
 |[[MOSEK|एमओएसइके]]|| कई भाषाओं के लिए एपीआई के साथ बड़े पैमाने पर अनुकूलन के लिए सॉल्वर (C++,java,.net, Matlab and python).
 |-
-|[[NAG Numerical Library|एनएजी संख्यात्मक लाइब्रेरी]]|| कई प्रोग्रामिंग भाषाओं के लिए [[संख्यात्मक एल्गोरिदम समूह]] द्वारा विकसित गणितीय और सांख्यिकीय दिनचर्या का संग्रह (C, C++, Fortran, Visual Basic, Java and C#) और पैकेज (मैटलैब, एक्सेल, आर, लैबव्यू)। एनएजी लाइब्रेरी के अनुकूलन अध्याय में विरल दोनों के साथ रैखिक प्रोग्रामिंग समस्याओं के लिए रूटीन शामिल हैं और गैर-विरल रेखीय बाधा मैट्रिसेस, एक साथ द्विघात, गैर-रैखिक, रैखिक या गैर-रैखिक कार्यों के वर्गों के योगों के अनुकूलन के लिए दिनचर्या के साथ-साथ गैर-रैखिक, परिबद्ध या कोई बाधा नहीं। एनएजी लाइब्रेरी में स्थानीय और वैश्विक अनुकूलन दोनों के लिए और निरंतर या पूर्णांक समस्याओं के लिए रूटीन हैं।
+|[[NAG Numerical Library|एनकोरी संख्यात्मक लाइब्रेरी]]|| कई क्रमादेशन भाषाओं के लिए [[संख्यात्मक एल्गोरिदम समूह|संख्यात्मक एल्गोरिथम समूह]] द्वारा विकसित गणितीय और सांख्यिकीय दिनचर्या का संग्रह (C, C++, Fortran, Visual Basic, Java and C#) और पैकेज (मैटलैब, एक्सेल, आर, लैबव्यू)। एनकोरी लाइब्रेरी के अनुकूलन अध्याय में विरल दोनों के साथ रैखिक क्रमादेशन समस्याओं के लिए रूटीन शामिल हैं और गैर-विरल रैखिक व्यवरोध मैट्रिसेस, एक साथ द्विघात, गैर-रैखिक, रैखिक या गैर-रैखिक कार्यों के वर्गों के योगों के अनुकूलन के लिए दिनचर्या के साथ-साथ गैर-रैखिक, परिबद्ध या कोई व्यवरोध नहीं। एनकोरी लाइब्रेरी में स्थानीय और वैश्विक अनुकूलन दोनों के लिए और निरंतर या पूर्णांक समस्याओं के लिए रूटीन हैं।
 |-
 |[[OptimJ|ऑप्टीमजे]]|| अनुकूलन के लिए एक जावा-आधारित मॉडलिंग भाषा, जिसका मुफ़्त संस्करण उपलब्ध है।<ref>http://www.in-ter-trans.eu/resources/Zesch_Hellingrath_2010_Integrated+Production-Distribution+Planning.pdf OptimJ used in an optimization model for mixed-model assembly lines, University of Münster</ref><ref>http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 {{Webarchive|url=https://web.archive.org/web/20110629022829/http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1769/2076 |date=2011-06-29 }} OptimJ used in an Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games</ref>
 |-
-|[[एसएएस]]/ओआर|| रेखीय, पूर्णांक, अरैखिक, व्युत्पन्न मुक्त, नेटवर्क, संयोजक और बाधा अनुकूलन के लिए अयस्कों का एक समूह;  [[बीजगणितीय मॉडलिंग भाषा]] ओपीटीमॉडल; और विभिन्न प्रकार के ऊर्ध्वाधर समाधानों का उद्देश्य विशिष्ट समस्याओं/बाजारों पर है, जिनमें से सभी [[एसएएस प्रणाली]] के साथ पूरी तरह से जुड़ गए हैं।
+|[[एसएएस]]/ओआर|| रैखिक, पूर्णांक, अरैखिक, व्युत्पन्न मुक्त, नेटवर्क, संयोजक और व्यवरोध अनुकूलन के लिए अयस्कों का एक समूह;  [[बीजगणितीय मॉडलिंग भाषा]] ओपीटीमॉडल; और विभिन्न प्रकार के ऊर्ध्वाधर समाधानों का उद्देश्य विशिष्ट समस्याओं/बाजारों पर है, जिनमें से सभी [[एसएएस प्रणाली]] के साथ पूरी तरह से जुड़ गए हैं।
 |-
-|[[SCIP (optimization software)|एससीआईपी]]||एक सामान्य प्रयोजन के लिए बाधा पूर्णांक प्रोग्रामिंग सॉल्वर, एमआईपी पर जोर देते हुए। ज़िम्पल मॉडलिंग भाषा के साथ संगत। शैक्षणिक उपयोग के लिए निःशुल्क और स्रोत कोड में उपलब्ध है।
+|[[SCIP (optimization software)|एससीआईपी]]||एक सामान्य प्रयोजन के लिए व्यवरोध पूर्णांक क्रमादेशन सॉल्वर, एमआईपी पर जोर देते हुए। ज़िम्पल मॉडलिंग भाषा के साथ संगत। शैक्षणिक उपयोग के लिए निःशुल्क और स्रोत कोड में उपलब्ध है।
 |-
-|[[FICO Xpress|एक्सप्रेस]]||बड़े पैमाने पर रैखिक कार्यक्रमों, द्विघात कार्यक्रमों, सामान्य गैर-रैखिक और मिश्रित-पूर्णांक कार्यक्रमों के लिए सॉल्वर। कई प्रोग्रामिंग भाषाओं के लिए एपीआई है, एक मॉडलिंग भाषा मोसेल भी है और एएमपीएल, [[जीएएमएस]] के साथ काम करती है। शैक्षणिक उपयोग के लिए निशुल्क।
+|[[FICO Xpress|एक्सप्रेस]]||बड़े पैमाने पर रैखिक क्रमादेशनों, द्विघात क्रमादेशनों, सामान्य गैर-रैखिक और मिश्रित-पूर्णांक क्रमादेशनों के लिए सॉल्वर। कई क्रमादेशन भाषाओं के लिए एपीआई है, एक मॉडलिंग भाषा मोसेल भी है और एएमपीएल, [[जीएएमएस]] के साथ काम करती है। शैक्षणिक उपयोग के लिए निशुल्क।
 |-
 |[[VisSim|विस्सिम]]|| [[गतिशील प्रणालियों]] के अनुकरण के लिए एक [[दृश्य ब्लॉक]] आरेख भाषा।

Anonymous

Search

रैखिक क्रमादेशन: Difference between revisions

Revision as of 12:58, 4 December 2022

इतिहास

उपयोग

मानक रूप

उदाहरण

संवर्धित रूप (शिथिल रूप)

उदाहरण

द्वैत

विविधताएं

द्वैत को ढंकना/पैक करना।

उदाहरण

पूरक शिथिलता

सिद्धांत

इष्टतम समाधानों का अस्तित्व

बहुफलक के इष्टतम शीर्ष (और किरणें)

एल्गोरिथम

आधार विनिमय एल्गोरिथम

डेंटज़िग की सिंप्लेक्स एल्गोरिथम

क्रिस-क्रॉस एल्गोरिथम

आंतरिक बिंदु

खाचियां के बाद दीर्घवृत्ताभ एल्गोरिथम

कर्मकार का प्रक्षेपी एल्गोरिथम

वैद्य की 87 एल्गोरिथ्म

वैद्य की 89 एल्गोरिथ्म

इनपुट स्पार्सिटी टाइम एल्गोरिथम

वर्तमान आव्यूह गुणन समय एल्गोरिथ्म

आंतरिक-बिंदु विधियों और सिंप्लेक्स एल्गोरिथम की तुलना

खुली समस्याएं और हाल का काम

पूर्णांक अज्ञात

इंटीग्रल लीनियर क्रमादेशन

सॉल्वर और स्क्रिप्टिंग (क्रमादेशन) भाषाएँ

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories