दोहरी रैखिक कार्यक्रम: Difference between revisions

From Vigyanwiki
m (removed Category:Vigyan Ready using HotCat)
Line 334: Line 334:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 06/05/2023]]
[[Category:Created On 06/05/2023]]
[[Category:Vigyan Ready]]

Revision as of 09:21, 17 May 2023

किसी दिए गए रैखिक प्रोग्राम (एलपी) का दोहरा एक और रैखिक प्रोग्राम है जो निम्नलिखित योजनाबद्ध तरीके से मूल (प्राइमल) रैखिक प्रोग्राम से प्राप्त होता है:

  • मौलिक रैखिक प्रोग्राम में प्रत्येक चर दोहरी रैखिक प्रोग्राम में बाधा बन जाता है;
  • मौलिक रैखिक प्रोग्राम में प्रत्येक बाधा दोहरी रैखिक प्रोग्राम में एक चर बन जाती है;
  • वस्तुनिष्ठ दिशा व्युत्क्रमित होती है - मूल में अधिकतम द्वैत में न्यूनतम हो जाता है और इसके विपरीत।

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

मजबूत द्वैत प्रमेय में कहा गया है कि, इसके अलावा, यदि प्राइमल का एक इष्टतम समाधान है, तो दोहरे का एक इष्टतम समाधान भी है, और दो ऑप्टिमा बराबर हैं[1] ये प्रमेय द्वैत (अनुकूलन) के एक बड़े वर्ग से संबंधित हैं। मजबूत द्वैत प्रमेय उन मामलों में से एक है जिसमें द्वैत अंतर (प्रारंभिक के इष्टतम और द्वैत के इष्टतम के बीच का अंतर) 0 है।

दोहरी रैखिक प्रोग्राम का रूप

मान लीजिए कि हमारे पास रैखिक प्रोग्राम है: Maximize cTx Ax ≤ b, x ≥ 0 के अधीन है। हम समाधान पर ऊपरी सीमा बनाना चाहते हैं। इसलिए हम धनात्मक गुणांकों के साथ व्यवरोधों का एक रैखिक संयोजन बनाते हैं, जैसे कि विवशताओं में x के गुणांक कम से कम c होंटी</सुप>. यह रैखिक संयोजन हमें उद्देश्य पर ऊपरी सीमा प्रदान करता है। दोहरे रैखिक प्रोग्राम के चर y इस रैखिक संयोजन के गुणांक हैं। दोहरी रैखिक प्रोग्राम ऐसे गुणांक खोजने की कोशिश करता है जो परिणामी ऊपरी सीमा को कम से कम करते हैं। यह निम्नलिखित रैखिक प्रोग्राम देता है:[1]{{Rp|81–83}छोटा करें bटीवाई के अधीन। इस LP को मूल LP का द्वैत कहा जाता है।

व्याख्या

द्वैत प्रमेय की आर्थिक व्याख्या है।[2][3] यदि हम प्रारंभिक रैखिक प्रोग्राम को शास्त्रीय संसाधन आवंटन समस्या के रूप में समझते हैं, तो इसकी दोहरी रैखिक प्रोग्राम को संसाधन मूल्यांकन समस्या के रूप में व्याख्या किया जा सकता है।

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

फिर, विवश राजस्व अधिकतमकरण प्राथमिक रैखिक प्रोग्राम है:Maximize cTx Ax ≤ b, x ≥ 0 के अधीन है। अब एक अन्य कारखाने पर विचार करें जिसमें कोई कच्चा माल नहीं है, और पिछले कारखाने से कच्चे माल का पूरा स्टॉक खरीदना चाहता है। यह का मूल्य सदिश प्रदान करता है (कच्चे माल की एक इकाई के लिए ). प्रस्ताव को स्वीकार करने के लिए, यह मामला होना चाहिए कि , अन्यथा फ़ैक्टरी अच्छे उत्पादन के लिए प्रयुक्त कच्चे माल को बेचने की तुलना में एक निश्चित उत्पाद का उत्पादन करके अधिक नकदी कमा सकती है। होना भी चाहिए , क्योंकि कारखाना किसी भी कच्चे माल को नकारात्मक कीमत पर नहीं बेचेगा। फिर, दूसरी फैक्ट्री की अनुकूलन समस्या दोहरी रैखिक प्रोग्राम है:टीवाई के अधीन द्वंद्व प्रमेय बताता है कि दो रैखिक प्रोग्राम समस्याओं के बीच द्वंद्व अंतर कम से कम शून्य है। आर्थिक रूप से, इसका मतलब यह है कि यदि पहले कारखाने को कच्चे माल के पूरे स्टॉक को y के प्रति-आइटम मूल्य पर खरीदने का प्रस्ताव दिया जाता है, जैसे कि टीवाई ≥ सी, वाई ≥ 0, तो इसे प्रस्ताव लेना चाहिए। यह कम से कम उतना ही राजस्व कमाएगा जितना कि यह तैयार माल का उत्पादन कर सकता है।

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

यह देखने के लिए, कच्चे माल की कीमतों पर विचार करें ऐसे हैं कुछ के लिए , तो कारखाना अधिक अच्छा उत्पादन करने के लिए अधिक कच्चा माल खरीदेगा चूंकि कीमतें बहुत कम हैं। इसके विपरीत, अगर कच्चे माल की कीमतें संतुष्ट हैं , लेकिन कम नहीं करता , तो कारखाने माल का उत्पादन करने की तुलना में अपना कच्चा माल बेचकर अधिक पैसा कमाएंगे, क्योंकि कीमतें बहुत अधिक हैं। संतुलन कीमत पर कच्चा माल खरीदकर या बेचकर कारखाना अपना लाभ नहीं बढ़ा सकता।

द्वैत प्रमेय की भौतिक व्याख्या भी है।[1]: 86–87 

दोहरी रैखिक प्रोग्राम का निर्माण

सामान्य तौर पर, एक प्राथमिक रैखिक प्रोग्राम दिया गया है, इसके दोहरे रैखिक प्रोग्राम के निर्माण के लिए निम्न एल्गोरिथम का उपयोग किया जा सकता है।[1]: 85  प्रारंभिक रैखिक प्रोग्राम द्वारा परिभाषित किया गया है:

  • एन चर का एक सेट: .
  • प्रत्येक चर के लिए , एक सांकेतिक बाधा - यह या तो गैर-नकारात्मक होनी चाहिए (), या गैर-सकारात्मक (), या अप्रतिबंधित ().
  • एक उद्देश्य समारोह:
  • एम बाधाओं की एक सूची। प्रत्येक बाधा j है: जहां प्रतीक से पहले में से एक हो सकता है या या .

दोहरे रैखिक प्रोग्राम का निर्माण निम्नानुसार किया गया है।

  • प्रत्येक मौलिक बाधा एक दोहरी चर बन जाती है। तो एम चर हैं: .
  • प्रत्येक द्वैत चर का चिह्न अवरोध इसके मौलिक अवरोध के चिह्न के विपरीत है। इसलिएबन जाता है औरबन जाता है औरबन जाता है .
  • दोहरा उद्देश्य कार्य है
  • प्रत्येक मूल चर एक दोहरी बाधा बन जाता है। तो वहाँ n बाधाएँ हैं। दोहरी बाधा में एक दोहरे चर का गुणांक इसके मौलिक चर का गुणांक इसकी मौलिक बाधा में है। तो प्रत्येक बाधा i है: , जहां प्रतीक से पहले प्रारंभिक रैखिक प्रोग्राम में वेरिएबल i पर साइन बाधा के समान है। इसलिए बन जाता हैऔर बन जाता हैऔर बन जाता है.

इस एल्गोरिथम से, यह देखना आसान है कि द्वैत का द्वैत मौलिक है।

वेक्टर फॉर्मूलेशन

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

प्रथम द्विक टिप्पणी
Maximize cTx subject to Axb, x ≥ 0 Minimize bTy subject to ATyc, y ≥ 0 This is called a "symmetric" dual problem
Maximize cTx subject to Axb Minimize bTy subject to ATy = c, y ≥ 0 This is called an "asymmetric" dual problem
Maximize cTx subject to Ax = b, x ≥ 0 Minimize bTy subject to ATyc


द्वैत प्रमेय

नीचे, मान लीजिए कि मौलिक रैखिक प्रोग्राम अधिकतम सी हैTx [बाधाओं] के अधीन है और दोहरी LP न्यूनतम b हैTy [बाधाओं] के अधीन है।

कमजोर द्वैत

दुर्बल द्वैत प्रमेय कहता है कि, मूल के प्रत्येक सुसंगत हल x और द्वैत के प्रत्येक सुसंगत हल y के लिए: cटीx ≤ खटी</सुप>य। दूसरे शब्दों में, द्वैत के प्रत्येक संभव समाधान में वस्तुनिष्ठ मूल्य मूल के वस्तुनिष्ठ मूल्य पर एक ऊपरी सीमा है, और मूल के प्रत्येक व्यवहार्य समाधान में वस्तुनिष्ठ मूल्य द्वैत के वस्तुनिष्ठ मूल्य पर निचली सीमा है। यहाँ मूल LP Maximize c के लिए एक प्रमाण दिया गया हैTx Ax ≤ b, x ≥ 0 के अधीन :

  • सीटीएक्स
  • = एक्सTc [क्योंकि यह केवल दो सदिशों का एक अदिश गुणनफल है]
  • ≤ एक्सटी(टी</सुप>वाई) ['ए के बाद सेTy ≥ c दोहरी बाधाओं द्वारा, और x ≥ 0]
  • = (एक्सटी</सुप>एटी)y [साहचर्य द्वारा]
  • = (कुल्हाड़ी)Ty [ट्रांसपोज़ के गुणों द्वारा]
  • ≤ बीTy [चूँकि Ax ≤ b प्राथमिक बाधाओं द्वारा]

कमजोर द्वैत का अर्थ है:maxx cटीx ≤ मिyबीTyविशेष रूप से, यदि प्राइमल अनबाउंड (ऊपर से) है तो डुअल का कोई व्यवहार्य समाधान नहीं है, और यदि डुअल अनबाउंड (नीचे से) है तो प्राइमल का कोई व्यवहार्य समाधान नहीं है।

प्रबल द्वैत

मजबूत द्वैत प्रमेय कहता है कि यदि दो समस्याओं में से एक का इष्टतम समाधान है, तो दूसरे का भी और कमजोर द्वैत प्रमेय द्वारा दी गई सीमाएं तंग हैं, यानी:

maxx cटीx = मिनटyबीTy

मजबूत द्वैत प्रमेय को सिद्ध करना कठिन है; सबूत आमतौर पर उप-दिनचर्या के रूप में कमजोर द्वंद्व प्रमेय का उपयोग करते हैं।

एक प्रमाण सिंप्लेक्स एल्गोरिदम का उपयोग करता है और इस प्रमाण पर निर्भर करता है कि, उपयुक्त धुरी नियम के साथ, यह एक सही समाधान प्रदान करता है। प्रमाण यह स्थापित करता है कि, एक बार सिम्प्लेक्स एल्गोरिथम प्राइमल रैखिक प्रोग्राम के समाधान के साथ समाप्त हो जाने पर, अंतिम झांकी से दोहरी रैखिक प्रोग्राम के समाधान को पढ़ना संभव है। इसलिए, सिम्प्लेक्स एल्गोरिथम को चलाकर, हम एक साथ प्राइमल और डुअल दोनों का समाधान प्राप्त करते हैं।[1]: 87–89 

एक अन्य प्रमाण भेड़िया लेम्मा का उपयोग करता है।[1]: 94 

सैद्धांतिक निहितार्थ

1. कमजोर द्वैत प्रमेय का अर्थ है कि एक एकल व्यवहार्य समाधान खोजना उतना ही कठिन है जितना कि एक इष्टतम संभव समाधान खोजना। मान लीजिए कि हमारे पास एक ऑरेकल है, जो एक रैखिक प्रोग्राम दिया गया है, एक मनमाना व्यवहार्य समाधान पाता है (यदि कोई मौजूद है)। रैखिक प्रोग्राम अधिकतम 'सी' को देखते हुएTx Ax ≤ b, x ≥ 0 के अधीन है, हम इस LP को इसके दोहरे के साथ जोड़कर एक और LP बना सकते हैं। संयुक्त रैखिक प्रोग्राम में चर के रूप में x और y दोनों हैं:Maximize 1 Ax ≤ b, A के अधीनटी</सुप>वाई ≥ सी, सी टी x ≥ खT y, x ≥ 0, y ≥ 0 यदि संयुक्त LP का एक व्यवहार्य समाधान (x,y) है, तो कमजोर द्वैत द्वारा, खय। अतः x को मूल LP का अधिकतम हल होना चाहिए और y को द्वैत LP का न्यूनतम हल होना चाहिए। यदि संयुक्त रैखिक प्रोग्राम का कोई संभव समाधान नहीं है, तो मूल रैखिक प्रोग्राम का भी कोई संभव समाधान नहीं है।

2. मजबूत द्वैत प्रमेय एक रैखिक प्रोग्राम के इष्टतम मूल्य का एक अच्छा लक्षण वर्णन प्रदान करता है जिसमें यह हमें आसानी से साबित करने की अनुमति देता है कि कुछ मूल्य 'टी' कुछ रैखिक प्रोग्राम का इष्टतम है। प्रमाण दो चरणों में आगे बढ़ता है:[4]: 260–261 

  • वैल्यू टी के साथ प्राइमल रैखिक प्रोग्राम के लिए एक व्यवहार्य समाधान दिखाएं; इससे सिद्ध होता है कि इष्टतम कम से कम t है।
  • मूल्य टी के साथ दोहरी रैखिक प्रोग्राम के लिए एक व्यवहार्य समाधान दिखाएं; यह साबित करता है कि इष्टतम अधिकतम टी पर है।

उदाहरण

छोटा उदाहरण

प्राथमिक रैखिक प्रोग्राम पर विचार करें, दो चर और एक बाधा के साथ:

उपरोक्त नुस्खा को लागू करने से निम्नलिखित दोहरी रैखिक प्रोग्राम मिलती है, एक चर और दो बाधाओं के साथ:

यह देखना आसान है कि प्रारंभिक LP का अधिकतम मान तब प्राप्त होता है जब x1 इसकी निचली सीमा (0) और x तक न्यूनतम है2 बाधा (7/6) के तहत इसकी ऊपरी सीमा तक अधिकतम है। अधिकतम 4· 7/6 = 14/3 है।

इसी प्रकार, दोहरी रैखिक प्रोग्राम का न्यूनतम y होने पर प्राप्त होता है1 बाधाओं के तहत इसकी निचली सीमा तक न्यूनतम किया जाता है: पहली बाधा 3/5 की निचली सीमा देती है जबकि दूसरी बाधा 4/6 की एक सख्त निचली सीमा देती है, इसलिए वास्तविक निचली सीमा 4/6 और न्यूनतम 7 है · 4/6 = 14/3।

प्रबल द्वैत प्रमेय के अनुसार, मूल का अधिकतम द्वैत के न्यूनतम के बराबर होता है।

हम इस उदाहरण का उपयोग कमजोर द्वैत प्रमेय के प्रमाण को दर्शाने के लिए करते हैं। मान लीजिए कि, मूल रैखिक प्रोग्राम में, हम उद्देश्य पर ऊपरी सीमा प्राप्त करना चाहते हैं . हम बाधा को कुछ गुणांक से गुणा करके उपयोग कर सकते हैं, कहते हैं . किसी के लिए हम पाते हैं: . अब अगर और , तब , इसलिए . इसलिए, दोहरे रैखिक प्रोग्राम का उद्देश्य मौलिक रैखिक प्रोग्राम के उद्देश्य पर एक ऊपरी सीमा है।

किसान उदाहरण

किसान उदाहरण के लिए चित्रमय समाधान - शर्तों का उल्लंघन करने वाले क्षेत्रों को छायांकित करने के बाद, शेष व्यवहार्य क्षेत्र का शीर्ष मूल से सबसे दूर धराशायी रेखा के साथ इष्टतम संयोजन देता है

एक ऐसे किसान पर विचार करें जो कुछ एल भूमि, एफ उर्वरक और पी कीटनाशक के निर्धारित प्रावधान के साथ गेहूं और जौ उगा सकता है।

एक यूनिट गेहूँ, एक यूनिट ज़मीन उगाने के लिए, उर्वरक की इकाइयां और कीटनाशी की ईकाइयों का प्रयोग करना चाहिए। इसी प्रकार, जौ की एक इकाई, भूमि की एक इकाई उगाने के लिए, उर्वरक की इकाइयां और कीटनाशी की ईकाइयों का प्रयोग करना चाहिए।

सबसे बड़ी समस्या यह होगी कि किसान यह तय करेगा कि कितना गेहूँ () और जौ () बढ़ने के लिए अगर उनके विक्रय मूल्य हैं और प्रति यूनिट।

Maximize: (maximize the revenue from producing wheat and barley)
subject to: (cannot use more land than available)
(cannot use more fertilizer than available)
(cannot use more pesticide than available)
(cannot produce negative quantities of wheat or barley).

मैट्रिक्स रूप में यह बन जाता है:

अधिकतम करें:
का विषय है:

दोहरी समस्या के लिए मान लें कि उत्पादन के इन साधनों (इनपुट्स) में से प्रत्येक के लिए y इकाई मूल्य एक योजना बोर्ड द्वारा निर्धारित किए गए हैं। योजना बोर्ड का काम किसान को उसकी प्रत्येक फसल (उत्पादन) के इकाई मूल्य पर एक फ्लोर उपलब्ध कराते हुए निविष्टियों की निर्धारित मात्रा की खरीद की कुल लागत को न्यूनतम करना है।1 गेहूं के लिए और एस2 जौ के लिए। यह निम्नलिखित रैखिक प्रोग्राम से मेल खाता है:

Minimize: (minimize the total cost of the means of production as the "objective function")
subject to: (the farmer must receive no less than S1 for his wheat)
(the farmer must receive no less than S2 for his barley)
(prices cannot be negative).

मैट्रिक्स रूप में यह बन जाता है:

छोटा करना:
का विषय है:

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

प्रारंभिक स्थान में प्रत्येक चर के लिए दोहरी स्थान में संतुष्ट करने के लिए एक असमानता से मेल खाती है, दोनों आउटपुट प्रकार द्वारा अनुक्रमित हैं। प्रारंभिक स्थान में प्रत्येक असमानता को संतुष्ट करने के लिए दोहरे स्थान में एक चर से मेल खाता है, दोनों को इनपुट प्रकार द्वारा अनुक्रमित किया गया है।

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

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

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

अव्यवहार्य प्रोग्राम

एक रैखिक प्रोग्राम असीमित या अव्यवहार्य भी हो सकता है। द्वैत सिद्धांत हमें बताता है कि:

  • यदि प्राण अबाध है, तो द्वैत अक्षम्य है;
  • यदि द्वैत असीम है, तो प्राण अव्यवहार्य है।

हालाँकि, यह संभव है कि द्वैत और मौलिक दोनों ही अव्यवहार्य हों। यहाँ एक उदाहरण है:

Maximize:
Subject to:


अनुप्रयोग

मैक्स-फ्लो मिन-कट प्रमेय मजबूत द्वैत प्रमेय का एक विशेष मामला है: फ्लो-मैक्सिमाइजेशन प्राइमल रैखिक प्रोग्राम है, और कट-मिनिमाइजेशन डुअल रैखिक प्रोग्राम है। मैक्स-फ्लो मिन-कट थ्योरम#लीनियर प्रोग्राम फॉर्म्युलेशन देखें।

ग्राफ से संबंधित अन्य प्रमेयों को मजबूत द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है, विशेष रूप से, कोनिग प्रमेय (ग्राफ सिद्धांत) | कोनिग प्रमेय।[5] जीरो-सम गेम के लिए मिनिमैक्स प्रमेय को मजबूत-द्वैत प्रमेय का उपयोग करके सिद्ध किया जा सकता है।[1]: sub.8.1 

वैकल्पिक एल्गोरिदम

कभी-कभी, प्रोग्राम मैट्रिक्स को देखे बिना दोहरे प्रोग्राम को प्राप्त करना अधिक सहज हो सकता है। निम्नलिखित रैखिक प्रोग्राम पर विचार करें:

Minimize
subject to

हमारे पास एम + एन स्थितियां हैं और सभी चर गैर-नकारात्मक हैं। हम m+n दोहरे चर परिभाषित करेंगे: 'y'j और एसi. हम पाते हैं:

Minimize
subject to

चूंकि यह एक न्यूनीकरण समस्या है, हम एक दोहरा प्रोग्राम प्राप्त करना चाहेंगे जो कि मूल की निचली सीमा है। दूसरे शब्दों में, हम चाहते हैं कि बाधाओं के सभी दाहिने हाथ का योग इस शर्त के तहत अधिकतम हो कि प्रत्येक मूल चर के लिए इसके गुणांकों का योग रैखिक फलन में इसके गुणांक से अधिक न हो। उदाहरण के लिए, एक्स1 n + 1 बाधाओं में प्रकट होता है। यदि हम इसके व्यवरोधों के गुणांकों का योग करते हैं तो हमें a मिलता है1,1y1+ ए1,2y2+ ... + ए1,;;n;;yn+ च1s1. यह राशि अधिकतम सी होनी चाहिए1. परिणामस्वरूप, हमें मिलता है:

Maximize
subject to

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

संदर्भ

  1. 1.0 1.1 1.2 1.3 1.4 1.5 1.6 Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN 3-540-30697-8. Pages 81–104.
  2. Sakarovitch, Michel (1983), "Complements on Duality: Economic Interpretation of Dual Variables", Springer Texts in Electrical Engineering, New York, NY: Springer New York, pp. 142–155, ISBN 978-0-387-90829-8, retrieved 2022-12-23
  3. Dorfman, Robert (1987). रैखिक प्रोग्रामिंग और आर्थिक विश्लेषण. Paul A. Samuelson, Robert M. Solow. New York: Dover Publications. ISBN 0-486-65491-5. OCLC 16577541.
  4. Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
  5. A. A. Ahmadi (2016). "Lecture 6: linear programming and matching" (PDF). Princeton University.