रैखिक क्रमादेशन

For यहाँ दी गई उपनाम निर्देशक टेलीविजन प्रसारण के लिए, see प्रसारण प्रोग्रामिंग.

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

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

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

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

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

${\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 में उन्हें हल करने के लिए एक विधि प्रकाशित की थी, और बाद में जिसे फूरियर मोटाकिन उन्मूलन की विधि का नाम दिया गया था।

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

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

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

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

उपयोग

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

मानक रूप

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

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

जैसे $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.$

द्वैत

Main article: Dual linear program

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

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

अधिकतम 'सी'^Tx Ax ≤ b, x ≥ 0 के अधीन;

इसी सममित दोहरी समस्या के साथ,

मिनिमाइज़ b^टीवाई ए के अधीन^टीy ≥ c, y ≥ 0.

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

अधिकतम c^Tx Ax ≤ b के अधीन;

इसी असममित दोहरी समस्या के साथ,

मिनिमाइज़ b^टीy ए के अधीन^टीy = c, y 0.

द्वैत सिद्धांत के मूल में दो विचार हैं। एक तथ्य यह है कि (सममित दोहरे के लिए) दोहरे रैखिक कार्यक्रम का दोहरी मूल प्रारंभिक रैखिक कार्यक्रम है। इसके अतिरिक्त, एक रैखिक कार्यक्रम के लिए प्रत्येक व्यवहार्य समाधान इसके दोहरे के उद्देश्य कार्य के इष्टतम मूल्य पर एक बाध्यता देता है। कमजोर द्वैत प्रमेय में कहा गया है कि किसी भी व्यवहार्य समाधान पर दोहरे का उद्देश्य कार्य मूल्य हमेशा किसी भी व्यवहार्य समाधान पर प्रारंभिक के उद्देश्य कार्य मूल्य से अधिक या बराबर होता है। मजबूत द्वैत प्रमेय कहता है कि यदि प्रारंभिक का इष्टतम समाधान है, तो x^*, तो द्वैत का भी एक इष्टतम समाधान है, y^**, और c^टीएक्स^*=बी^{टी</सुप>य**</सुप>.}

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

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

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

विविधताएं

दोहरी सामग्री को ढंकना।

आवरण एलपी प्रपत्र का एक रैखिक कार्यक्रम है:

छोटा करें: <बड़ा>बी^टीय</बड़ा>,

के अधीन: <बड़ा>ए^टीवाई ≥ सी, वाई ≥ 0</बड़ा>,

ऐसा है कि मैट्रिक्स 'ए' और वैक्टर बी और सी गैर-नकारात्मक हैं।

एक कवरिंग एलपी का दोहरा एक पैकिंग समस्या है, फॉर्म का एक रैखिक कार्यक्रम:

अधिकतम करें: <बड़ा>सी^टीएक्स</बड़ा>,

इसके अधीन: <बड़ा>Ax ≤ b, x ≥ 0,

ऐसा है कि मैट्रिक्स 'ए' और वैक्टर बी और सी गैर-नकारात्मक हैं।

उदाहरण

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

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

पूरक शिथिलता

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

मान लीजिए कि x = (x₁, एक्स₂, ... , एक्स_n) प्रारंभिक संभव है और वह y = (y₁, यू₂, ... , वाई_m) दोहरी व्यवहार्य है। चलो (w₁, में₂, ..., में_m) संबंधित प्राइमल स्लैक वेरिएबल्स को निरूपित करें, और चलो (z₁, साथ₂, ... , साथ_n) संगत दोहरे सुस्त चरों को निरूपित करते हैं। तब x और y अपनी संबंधित समस्याओं के लिए इष्टतम हैं यदि और केवल यदि

• एक्स_j z_j= 0, j = 1, 2, ..., n, और . के लिए
• 'डब्ल्यू'_i y_i= 0, मैं के लिए = 1, 2, ... , एम.

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

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

सिद्धांत

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

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

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

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

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

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

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

बहुतप के शीर्ष को बुनियादी व्यवहार्य समाधान भी कहा जाता है।

एल्गोरिदम

See also: List of numerical analysis topics § Linear programming

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

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

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

1947 में जॉर्ज डेंट्ज़िग द्वारा विकसित सिंप्लेक्स एल्गोरिथ्म, एलपी समस्याओं को हल करता है, पॉलीटॉप के शीर्ष पर एक व्यवहार्य समाधान का निर्माण करता है और फिर पॉलीटॉप के किनारों पर एक पथ के साथ चलकर उद्देश्य फलन के गैर-घटते मूल्यों के साथ कोने तक चलता है। इष्टतम निश्चित रूप से पहुँच गया है। कई व्यावहारिक समस्याओं में, सिम्पलेक्स एल्गोरिथम#डीजेनेरेसी: स्टालिंग और साइकलिंग होता है: ऑब्जेक्टिव फलन में कोई वृद्धि नहीं होने के कारण कई पिवोट्स बनाए जाते हैं। दुर्लभ व्यावहारिक समस्याओं में, सिम्प्लेक्स एल्गोरिथम के सामान्य संस्करण वास्तव में चक्र हो सकते हैं।चक्र से बचने के लिए, शोधकर्ताओं ने नए धुरी नियम विकसित किए।

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

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

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

आंतरिक बिंदु

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

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

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

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

Main article: Karmarkar's algorithm

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

हालांकि, खाचियां के एल्गोरिदम ने रैखिक प्रोग्रामिंग में अनुसंधान की नई पंक्तियों को प्रेरित किया। 1984 में, नरेंद्र करमारकर|एन. करमार्कर ने प्रस्तावित किया रैखिक प्रोग्रामिंग के लिए प्रक्षेपी विधि । कर्मकार का एल्गोरिदमइम्प्रोवेद ों खाचियाँ'ससबसे खराब स्थिति बहुपद बाध्य (देना .) $O(n^{3.5}L)$). करमार्कर ने दावा किया कि उनका एल्गोरिथ्म सरल विधि की तुलना में व्यावहारिक एलपी में बहुत तेज था, एक ऐसा दावा जिसने आंतरिक-बिंदु विधियों में बहुत रुचि पैदा की। करमार्कर की खोज के बाद से, कई आंतरिक-बिंदु विधियों का प्रस्ताव और विश्लेषण किया गया है।

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

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

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

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

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

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

वर्तमान मैट्रिक्स गुणन समय एल्गोरिथ्म

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

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

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

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

Unsolved problem in computer science:

Does linear programming admit a strongly polynomial-time algorithm?

(more unsolved problems in computer science)

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

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

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

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

• क्या ऐसे धुरी नियम हैं जो बहुपद-समय सिंप्लेक्स वेरिएंट की ओर ले जाते हैं?
• क्या सभी पॉलीटोपल ग्राफ में बहुपद से घिरा व्यास होता है?

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

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

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

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

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

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

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

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

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

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

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

Further information: Integral polytope

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

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

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

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

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

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

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

Name	License	Brief info
Gekko	MIT License	Open-source library for solving large-scale LP, QP, QCQP, NLP, and MIP optimization
GLOP	Apache v2	Google's open-source linear programming solver
Pyomo	BSD	An open-source modeling language for large-scale linear, mixed integer and nonlinear optimization
SuanShu	Apache v2	an open-source suite of optimization algorithms to solve LP, QP, SOCP, SDP, SQP in Java

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

Name	License	Brief info
ALGLIB	GPL 2+	an LP solver from ALGLIB project (C++, C#, Python)
Cassowary constraint solver	LGPL	an incremental constraint solving toolkit that efficiently solves systems of linear equalities and inequalities
CLP	CPL	an LP solver from COIN-OR
glpk	GPL	GNU Linear Programming Kit, an LP/MILP solver with a native C API and numerous (15) third-party wrappers for other languages. Specialist support for flow networks. Bundles the AMPL-like GNU MathProg modelling language and translator.
Qoca	GPL	a library for incrementally solving systems of linear equations with various goal functions
R-Project	GPL	a programming language and software environment for statistical computing and graphics

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

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

Name	Brief info
AIMMS	A modeling language that allows to model linear, mixed integer, and nonlinear optimization models. It also offers a tool for constraint programming. Algorithm, in the forms of heuristics or exact methods, such as Branch-and-Cut or Column Generation, can also be implemented. The tool calls an appropriate solver such as CPLEX or similar, to solve the optimization problem at hand. Academic licenses are free of charge.
ALGLIB	A commercial edition of the copyleft licensed library. C++, C#, Python.
AMPL	A popular modeling language for large-scale linear, mixed integer and nonlinear optimisation with a free student limited version available (500 variables and 500 constraints).
Analytica	A general modeling language and interactive development environment. Its influence diagrams enable users to formulate problems as graphs with nodes for decision variables, objectives, and constraints. Analytica Optimizer Edition includes linear, mixed integer, and nonlinear solvers and selects the solver to match the problem. It also accepts other engines as plug-ins, including XPRESS, Gurobi, Artelys Knitro, and MOSEK.
APMonitor	API to MATLAB and Python. Solve example Linear Programming (LP) problems through MATLAB, Python, or a web-interface.
CPLEX	Popular solver with an API for several programming languages, and also has a modelling language and works with AIMMS, AMPL, GAMS, MPL, OpenOpt, OPL Development Studio, and TOMLAB. Free for academic use.
Excel Solver Function	A nonlinear solver adjusted to spreadsheets in which function evaluations are based on the recalculating cells. Basic version available as a standard add-on for Excel.
FortMP
GAMS
IMSL Numerical Libraries	Collections of math and statistical algorithms available in C/C++, Fortran, Java and C#/.NET. Optimization routines in the IMSL Libraries include unconstrained, linearly and nonlinearly constrained minimizations, and linear programming algorithms.
LINDO	Solver with an API for large scale optimization of linear, integer, quadratic, conic and general nonlinear programs with stochastic programming extensions. It offers a global optimization procedure for finding guaranteed globally optimal solution to general nonlinear programs with continuous and discrete variables. It also has a statistical sampling API to integrate Monte-Carlo simulations into an optimization framework. It has an algebraic modeling language (LINGO) and allows modeling within a spreadsheet (What'sBest).
Maple	A general-purpose programming-language for symbolic and numerical computing.
MATLAB	A general-purpose and matrix-oriented programming-language for numerical computing. Linear programming in MATLAB requires the Optimization Toolbox in addition to the base MATLAB product; available routines include INTLINPROG and LINPROG
Mathcad	A WYSIWYG math editor. It has functions for solving both linear and nonlinear optimization problems.
Mathematica	A general-purpose programming-language for mathematics, including symbolic and numerical capabilities.
MOSEK	A solver for large scale optimization with API for several languages (C++,java,.net, Matlab and python).
NAG Numerical Library	A collection of mathematical and statistical routines developed by the Numerical Algorithms Group for multiple programming languages (C, C++, Fortran, Visual Basic, Java and C#) and packages (MATLAB, Excel, R, LabVIEW). The Optimization chapter of the NAG Library includes routines for linear programming problems with both sparse and non-sparse linear constraint matrices, together with routines for the optimization of quadratic, nonlinear, sums of squares of linear or nonlinear functions with nonlinear, bounded or no constraints. The NAG Library has routines for both local and global optimization, and for continuous or integer problems.
OptimJ	A Java-based modeling language for optimization with a free version available.
SAS/OR	A suite of solvers for Linear, Integer, Nonlinear, Derivative-Free, Network, Combinatorial and Constraint Optimization; the Algebraic modeling language OPTMODEL; and a variety of vertical solutions aimed at specific problems/markets, all of which are fully integrated with the SAS System.
SCIP	A general-purpose constraint integer programming solver with an emphasis on MIP. Compatible with Zimpl modelling language. Free for academic use and available in source code.
XPRESS	Solver for large-scale linear programs, quadratic programs, general nonlinear and mixed-integer programs. Has API for several programming languages, also has a modelling language Mosel and works with AMPL, GAMS. Free for academic use.
VisSim	A visual block diagram language for simulation of dynamical systems.

यह भी देखें

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

संदर्भ

• 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)

बाहरी संबंध

• Guidance On Formulating LP Problems
• Mathematical Programming Glossary
• The Linear Programming FAQ
• Benchmarks For Optimisation Software

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

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

| below =

• Software

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

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

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

}}