रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए दोहरी सिम्प्लेक्स विधि। दोहरी समस्या का समाधान इष्टतम उत्पादन कार्यक्रम की दोहरी समस्या का समाधान

प्रथम एवं द्वितीय द्वैत प्रमेय का सूत्रीकरण दिया गया है। यह दिखाया गया है कि द्वैत प्रमेयों का उपयोग करके प्रत्यक्ष समाधान से दोहरी समस्या का समाधान कैसे प्राप्त किया जा सकता है। समस्या समाधान के उदाहरण.

सामग्री

यह सभी देखें: दोहरी समस्याएँ लिखने के नियम

यहां हम इस प्रश्न पर विचार करेंगे कि प्रत्यक्ष समस्या के समाधान से दोहरी समस्या का समाधान कैसे प्राप्त किया जाए।

द्वैत प्रमेय

पहला द्वैत प्रमेय

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

यदि उद्देश्य फ़ंक्शन की असीमितता के कारण दोहरी समस्याओं में से एक का समाधान नहीं है, तो बाधाओं की प्रणाली की असंगतता के कारण दोहरी समस्या का समाधान नहीं है।

दूसरा द्वैत प्रमेय

;

.

आइए दूसरा द्वैत प्रमेय लागू करें। आइए हम चर के इष्टतम मूल्यों को प्रत्यक्ष समस्या की बाधाओं की प्रणाली में प्रतिस्थापित करें।
(ए1.1.1) ;
(ए1.1.2) ;
(ए1.1.3) ;
(ए1.1.4) .
चूँकि पहली और चौथी पंक्तियाँ सख्त असमानताएँ हैं (वे समानताएँ नहीं हैं), तो
और ।

चूँकि और, तो दोहरी समस्या की दूसरी और चौथी पंक्तियाँ समानताएँ हैं:

आइए पहले से पाए गए मानों को प्रतिस्थापित करें और, हमारे पास है:

यहाँ से
;
; .

दोहरी समस्या का रूप है:
;

उसका निर्णय
;

उदाहरण 2

एक रैखिक प्रोग्रामिंग समस्या को देखते हुए:
(ए2.1.1) ;
(ए2.1.2)
दोहरी समस्या को रेखांकन द्वारा हल करके इस समस्या का समाधान खोजें।

(ए2.2.1) ;
(ए2.2.2)

समस्या का समाधान (ए2.2) पृष्ठ पर दिया गया है "ग्राफ़िकल विधि का उपयोग करके रैखिक प्रोग्रामिंग समस्याओं को हल करना।" समस्या का समाधान (A2.2) इस प्रकार है:
; .

प्रथम द्वैत प्रमेय के अनुसार, उद्देश्य फलन का इष्टतम मान बराबर होता है
.

आइए दूसरा द्वैत प्रमेय लागू करें। आइए हम चरों के इष्टतम मानों को प्रत्यक्ष समस्या (A2.2) की बाधाओं की प्रणाली में प्रतिस्थापित करें।
;
;
.
चूँकि तीसरी पंक्ति एक सख्त असमानता है (वे समानता नहीं हैं), तो
.

चूँकि और, तो दोहरी समस्या (A2.1) की पहली और दूसरी पंक्तियाँ समानताएँ हैं:

आइए पाए गए मान को प्रतिस्थापित करें।

हम समीकरणों की एक प्रणाली को हल करते हैं।
;
;
;
; ;
.

मूल समस्या का समाधान (A2.1) इस प्रकार है:
; .

यह सभी देखें:

वह विधि जिसमें पारस्परिक रूप से दोहरी समस्याओं में से एक को पहले सिंप्लेक्स विधि का उपयोग करके हल किया जाता है, और फिर दूसरी समस्या का इष्टतम और इष्टतम समाधान द्वैत प्रमेय का उपयोग करके पाया जाता है, कहलाती है दोहरी सिम्प्लेक्स विधि.

प्रमेय 1 (प्रथम द्वैत प्रमेय). यदि पारस्परिक रूप से दोहरी समस्याओं में से किसी एक का इष्टतम समाधान है, तो ऐसा ही होता है

दूसरा, और उनके उद्देश्य कार्यों के इष्टतम मूल्य इसके बराबर हैं:

यदि मूल समस्या का उद्देश्य कार्य अप्रतिबंधित है, तो दोहरी समस्या की बाधाओं की प्रणाली असंगत है।

टिप्पणी:प्रथम द्वैत प्रमेय के दूसरे भाग का व्युत्क्रम सामान्य स्थिति में सत्य नहीं है।

प्रमेय 2. दोहरी समस्या के लिए इष्टतम योजना के घटक ( गैर-नकारात्मकता की स्थिति होना) बराबर हैं गुणांकों का निरपेक्ष मान

दोहरी समस्या के लिए इष्टतम योजना के घटक ( संकेत तक सीमित नहीं) बराबर हैं गुणांक मानमूल समस्या के उद्देश्य फ़ंक्शन के संगत चर के साथ, इसके इष्टतम समाधान के मुक्त चर के संदर्भ में व्यक्त किया गया।

प्रमेय 3. किसी एक समस्या के इष्टतम समाधान के सकारात्मक (गैर-शून्य) घटक सममित दोहरी जोड़ीकिसी अन्य समस्या के इष्टतम समाधान के शून्य घटकों के अनुरूप, अर्थात्। किसी के लिए और:

प्रमेय 4 (तीसरा द्वैत प्रमेय). दोहरी समस्या के इष्टतम डिज़ाइन के घटक रैखिक फ़ंक्शन के आंशिक व्युत्पन्न के मूल्यों के बराबर हैं संबंधित तर्कों के अनुसार, अर्थात्

. (7.2)

तृतीय द्वैत प्रमेय की आर्थिक व्याख्या: दोहरी समस्या के लिए इष्टतम योजना के घटक दिखाते हैं कि उत्पादों की बिक्री से अधिकतम लाभ (राजस्व) कितनी मौद्रिक इकाइयों में बदल जाएगा जब संबंधित संसाधन का स्टॉक एक इकाई द्वारा बदल जाता है।

उदाहरण 9.1.उदाहरण 5.2 (फ़ाइल "एल्गोरिदम और सिंप्लेक्स विधि के उदाहरण") के समाधान के आधार पर, हम दोहरी समस्या का इष्टतम समाधान निर्धारित करने के लिए दोहरी सिम्प्लेक्स विधि का उपयोग करेंगे।

मूल समस्या	दोहरी समस्या

यह दोहरा जोड़ा सममित है। समस्याएँ मानक रूप में लिखी गई हैं; आइए उन्हें विहित रूप में लिखें:

मूल समस्या	दोहरी समस्या

आइए हम परस्पर दोहरी समस्याओं के चरों के बीच एक पत्राचार स्थापित करें।

उदाहरण 5.2 के समाधान के आधार पर। अंतिम पुनरावृत्ति की सिंप्लेक्स तालिका (तालिका 5.10) इस प्रकार दिखती है:

तालिका 9.3

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

तालिका 9.3 का उपयोग करते हुए, हम मूल समस्या के उद्देश्य फ़ंक्शन को लिखते हैं, जो इसके इष्टतम समाधान के मुक्त चर के संदर्भ में व्यक्त किया गया है:

इस तरह, , ।

चर , , और उद्देश्य फ़ंक्शन में मौजूद नहीं हैं (यानी, उनके गुणांक शून्य के बराबर हैं), इसलिए, संबंधित चर , , और के इष्टतम मान शून्य के बराबर हैं।

प्रमेय 1 के अनुसार, .

इस प्रकार, उद्देश्य फ़ंक्शन का इष्टतम मान, जो प्राप्त किया जाता है।

उदाहरण 9.2.मूल समस्या के समाधान के आधार पर, दोहरी सिम्प्लेक्स विधि का उपयोग करके दोहरी समस्या का इष्टतम समाधान खोजें।

मूल समस्या	दोहरी समस्या

यह दोहरी जोड़ी असममित है। आइए हम दोहरी समस्या को विहित रूप में लाएँ।

मूल समस्या	दोहरी समस्या

दोहरी जोड़ी के चरों के बीच पत्राचार स्थापित करने के लिए, हम मूल समस्या में दो लापता काल्पनिक चर पेश करते हैं।

मूल समस्या	दोहरी समस्या

आइए हम परस्पर दोहरी समस्याओं के चरों के बीच एक पत्राचार स्थापित करें।

तालिका 9.4

दोहरी जोड़ी के मिलान चर

आइए सिंप्लेक्स विधि का उपयोग करके मूल समस्या को हल करें।

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

परिवर्तनों के परिणामस्वरूप, हमें गुणांकों का निम्नलिखित मैट्रिक्स प्राप्त होता है:

.

मूल समस्या की बाधाओं की प्रणाली निम्नलिखित रूप लेगी:

आइए हम मूल चर को मुक्त चर के रूप में व्यक्त करें, परिणामस्वरूप, मूल समस्या निम्नलिखित रूप लेगी:

मूल चर के प्राप्त मूल्यों को उद्देश्य फ़ंक्शन में प्रतिस्थापित करने पर, यह निम्नलिखित रूप लेगा:

अंतिम पुनरावृत्ति में सिंप्लेक्स विधि का उपयोग करके रूपांतरित मूल समस्या को हल करने के परिणामस्वरूप, हमें निम्नलिखित सिंप्लेक्स तालिका प्राप्त होती है:

तालिका 9.5

मूल समस्या के इष्टतम समाधान की सिम्पलेक्स तालिका

दोहरी समस्या की संरचना और गुण

आर्थिक दृष्टिकोण से एलपी को अधिकतम करने की किसी भी समस्या को विभिन्न उपभोक्ताओं के बीच सीमित संसाधनों बी 1, बी 2,…, बी एम को वितरित करने की समस्या के रूप में माना जा सकता है, उदाहरण के लिए, कुछ तकनीकी प्रक्रियाओं के बीच, जिन्हें कॉलम ए 1 द्वारा दर्शाया गया है। समस्या बाधा मैट्रिक्स का A 2,…A n। समस्या का कोई भी व्यवहार्य समाधान एलपीएक्स 1 ,एक्स 2 ,…एक्स एन प्रत्येक संसाधन के हिस्से को इंगित करते हुए एक विशिष्ट वितरण देता है जिसका उपयोग संबंधित तकनीकी प्रक्रिया के कार्यान्वयन में किया जाना चाहिए।

आइए एक उदाहरण देखें. संयंत्र तीन प्रकार के उत्पाद x 1, x 2 और x 3 का उत्पादन करता है, जिनमें से प्रत्येक को लेथ, मिलिंग और ड्रिलिंग मशीनों पर प्रसंस्करण पर समय खर्च करने की आवश्यकता होती है। प्रत्येक मशीन के लिए मशीन समय की मात्रा सीमित है। Letc 1,c 2,c 3 - संबंधित प्रकार के उत्पाद की एक इकाई की बिक्री से लाभ। अधिकतम लाभ प्राप्त करने के लिए यह निर्धारित करना आवश्यक है कि सप्ताह के दौरान प्रत्येक प्रकार के उत्पाद का कितना उत्पादन किया जाना चाहिए।

औपचारिक रूप से, यह कार्य इस प्रकार लिखा गया है:

अधिकतम (सी 1 एक्स 1 +सी 2 एक्स 2 +सी 3 एक्स 3) (1)

प्रतिबंधों के तहत

ए 11 x 1 + ए 12 x 2 + ए 13 x 3 ≤ बी 1 ;

ए 21 x 1 + ए 22 x 2 + ए 23 x 3 ≤ बी 2 ;

ए 31 एक्स 1 +ए 32 एक्स 2 +ए 33 एक्स 3 ≤बी 3, (2)

जहां a 1 j , a 2 j , a 3 j खराद, मिलिंग और ड्रिलिंग मशीनों पर क्रमशः jवें प्रकार के उत्पाद की एक इकाई को संसाधित करने के लिए आवश्यक समय है (j = 1, 2, 3); 2, बी 3 - टर्निंग, मिलिंग और ड्रिलिंग मशीनों के लिए क्रमशः मशीन समय का साप्ताहिक संसाधन।

आइए हम निरूपित करें y 1 , y 2 और y 3 - टर्निंग, मिलिंग और ड्रिलिंग मशीनों पर परिचालन समय की एक इकाई की कीमत। फिर a 11 y 1 +a 21 y 2 +a 31 y 3 - की व्याख्या पहले प्रकार के उत्पाद की एक इकाई के उत्पादन की लागत के रूप में की जा सकती है a 12 y 1 +a 22 y 2 +a 32 y 3 - लागत; दूसरे प्रकार के उत्पाद की एक इकाई का निर्माण, आदि।

आइए मान लें कि संसाधन की कीमतें y 1 ,y 2 ,…,y m चुनी गई हैं ताकि निम्नलिखित संबंध संतुष्ट हों:

ए 11 वाई 1 + ए 21 वाई 2 + ए 31 वाई 3 ≥ सी 1 ;

ए 12 वाई 1 + ए 22 वाई 2 + ए 32 वाई 3 ≥ सी 2 ;

ए 13 वाई 1 +ए 23 वाई 2 +ए 33 वाई 3 ≥ सी 3। (3)

चूँकि b 1, b 2 और b 3 प्रत्येक मशीन के लिए प्रयुक्त मशीन समय संसाधन हैं, तो b 1 y 1 + b 2 y 2 + b 3 y 3 कुल उत्पादन लागत हैं।

ऐसे y 1 , y 2 और y 3 को ढूंढना आवश्यक है जो शर्तों (3) को संतुष्ट करते हैं, जिसके तहत कुल उत्पादन लागत कम हो जाती है:

न्यूनतम g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

शर्तों के अधीन

y 1 ≥0;y 2 ≥0;y 3 ≥0.

इस समस्या को कहा जाता है दोहरा कार्यसमस्या (1) के संबंध में, जिसे प्रत्यक्ष कहा जाता है।

आइए अब हम सामान्य स्थिति में प्रत्यक्ष और दोहरी समस्याओं को लिखें।

सीधा कार्य:

अधिकतम

शर्तों के अधीन

(7)

दोहरी समस्या:

छोटा करना

शर्तों के अधीन

(10)

मैट्रिक्स रूप में, दोहरी समस्याओं की एक जोड़ी इस प्रकार लिखी जाती है:

अधिकतम

शर्तों के अधीन

छोटा करना

शर्तों के अधीन

ए टी y≥c; (15)

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

यदि प्रत्यक्ष समस्या अधिकतमीकरण समस्या है, तो दोहरी समस्या न्यूनतमकरण समस्या होगी, और इसके विपरीत;

प्रत्यक्ष समस्या के वस्तुनिष्ठ कार्य के गुणांकसी 1 ,सी 2 ,…,सी एन दोहरी समस्या की बाधाओं से मुक्त सदस्य बनें;

प्रत्यक्ष समस्या की बाधाओं की मुक्त शर्तेंबी 1 , बी 2 ,…, बी एम दोहरी समस्या के वस्तुनिष्ठ कार्य के गुणांक बनें;

दोहरी समस्या का बाधा मैट्रिक्स प्रत्यक्ष समस्या के बाधा मैट्रिक्स को स्थानांतरित करके प्राप्त किया जाता है;

प्रतिबंधों में असमानताओं के संकेत उलट दिए गए हैं;

प्रत्यक्ष समस्या की बाधाओं की संख्या दोहरी समस्या के चरों की संख्या के बराबर है, और दोहरी समस्या की बाधाओं की संख्या प्रत्यक्ष समस्या के चरों की संख्या के बराबर है।

दोहरी समस्या के चर y 1 , y 2 ,…,y m को कभी-कभी छाया कीमतें कहा जाता है।

यदि सीधी रेखा में हो तो मूल सीधी रेखा की तुलना में दोहरी समस्या को हल करना अधिक लाभदायक है

कम संख्या में चर वाली समस्या में बड़ी संख्या में बाधाएं (एम एन) होती हैं।

प्रत्यक्ष और दोहरी समस्याओं के इष्टतम समाधान के बीच संबंध निम्नलिखित द्वैत प्रमेयों के माध्यम से स्थापित किया गया है।

प्रमेय 1.अगर - प्रत्यक्ष और दोहरी समस्याओं का स्वीकार्य समाधान,यानी फिर

वे। प्रत्यक्ष समस्या के वस्तुनिष्ठ फलन के मान कभी भी दोहरी समस्या के वस्तुनिष्ठ फलन के मान से अधिक नहीं होते।

प्रमेय 2 (मौलिक द्वैत प्रमेय)।अगर -प्रत्यक्ष और दोहरी समस्याओं का स्वीकार्य समाधान और यदि , वह - दोहरी समस्याओं की एक जोड़ी का इष्टतम समाधान।

प्रमेय 3.यदि प्रत्यक्ष समस्या का इष्टतम समाधान है(5) – (7) मैं-वें अवरोध को सख्त असमानता के रूप में संतुष्ट किया जाता है, तो संबंधित दोहरे चर का इष्टतम मान शून्य के बराबर होता है, यानी।

कहाँ - मैंमैट्रिक्स ए की वीं पंक्ति.

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

प्रमेय 3 को प्रमेय 4 द्वारा पूरक किया गया है, जो प्रत्यक्ष समस्या के इष्टतम समाधान और दोहरी समस्या की बाधाओं के बीच संबंध स्थापित करता है।

प्रमेय 4. यदि दोहरी समस्या के इष्टतम समाधान में बाधा हैजेसख्त असमानता के रूप में संतुष्ट है, तो प्रत्यक्ष समस्या के संबंधित चर का इष्टतम मूल्य शून्य के बराबर होना चाहिए, यानी यदि वह

आइए हम प्रमेय 4 की आर्थिक व्याख्या करें।

मात्राओं के बाद से फिर, संबंधित संसाधनों की कीमतों का प्रतिनिधित्व करें

जेवें तकनीकी प्रक्रिया की लागत है, मूल्य उत्पाद की प्रति इकाई बिक्री से होने वाला लाभ है। इसलिए, आर्थिक दृष्टिकोण से, प्रमेय 2.7 का अर्थ निम्नलिखित है: यदि जे-वें तकनीकी प्रक्रिया इष्टतम संसाधन कीमतों के दृष्टिकोण से सख्ती से लाभहीन हो जाती है, तो प्रत्यक्ष समस्या के इष्टतम समाधान में की तीव्रता यह तकनीकी प्रक्रिया 0 के बराबर होनी चाहिए.

इस प्रकार, प्रमेय 4 व्यक्त करता है लाभप्रदता सिद्धांतइष्टतम रूप से व्यवस्थित उत्पादन।

इससे यह भी पता चलता है कि

(20)

आइए मान लें कि प्रत्यक्ष समस्या के चर x 1 ,x 2 ,…,x n के बीच mचरों का एक सेट है जिसका इष्टतम समाधान में गैर-शून्य मान है। उदाहरण के लिए, मान लीजिए कि क्रम में ये पहले चर हैं।

फिर, समीकरण (22) के आधार पर, लाभप्रदता की स्थितियाँ प्राप्त की जाती हैं:

(21)

आइए हम द्वैत सिद्धांत के दो और महत्वपूर्ण प्रमेय प्रस्तुत करें।

प्रमेय 5 (अस्तित्व प्रमेय)।प्रत्यक्ष और दोहरी समस्याओं का इष्टतम समाधान तभी होता है जब उन दोनों के पास व्यवहार्य समाधान हों।

प्रमेय 6 (द्वैत प्रमेय)।वैध वेक्टरएक्स 0 यह तभी इष्टतम है जब दोहरी समस्या का कोई व्यवहार्य समाधान होय 0 , क्या

प्रत्यक्ष और दोहरी समस्याओं के इष्टतम समाधान और इन समाधानों के अनुरूप सिंप्लेक्स तालिकाओं की सूचकांक पंक्तियों के तत्वों के बीच निम्नलिखित संबंध मौजूद है:

i=1, 2, …,m;j=1, 2, …,n,

जहाँ n प्रत्यक्ष समस्या के चरों की संख्या है; m इसकी बाधाओं की संख्या है; क्रमशः प्रत्यक्ष और दोहरी समस्याओं की सूचकांक रेखा के संगत तत्व हैं। इसके अलावा, यदि n+i, जहां 1 ≤i≤m संबंधित समस्या के विस्तारित रूप के बाधा मैट्रिक्स के कॉलम वैक्टर की संख्या से अधिक है, तो सूचकांक पंक्ति के तत्वों को चक्रीय रूप से पुनर्व्यवस्थित करके तत्व पाए जाते हैं। तत्व के साथ

द्वंद्व का सामान्य मामला

पिछले अनुभाग में, असमानताओं के रूप में बाधाओं के तहत दोहरी एलपी समस्याओं की एक जोड़ी के लिए बुनियादी संबंध स्थापित किए गए थे। आइए अब इन परिणामों को मनमाने प्रतिबंधों के मामले में सामान्यीकृत करें।

आइए प्रत्यक्ष एलपी समस्या को इस रूप में दिया जाए:

अधिकतम

शर्तों के अधीन

फिर (24)-(26) (या इससे संयुग्मित) के संबंध में दोहरी समस्या रैखिक रूप को कम करना है:

छोटा करना

शर्तों के अधीन

इस प्रकार, मिश्रित परिस्थितियों वाली समस्या से जुड़ी समस्या को निम्नलिखित नियमों के अनुसार संकलित किया जाता है:

यदि प्रत्यक्ष समस्या के चर x j को गैर-नकारात्मक माना जाता है, तो बाधाओं की प्रणाली (28) की jth स्थिति एक असमानता है।

यदि x j पर ऐसी कोई बाधा नहीं लगाई गई है, तो दोहरी समस्या की jth बाधा समानता होगी।

दोहरी समस्या y i के चर के संकेत और प्रत्यक्ष समस्या के संबंधित प्रतिबंध समान तरीके से संबंधित हैं। ध्यान दें कि यदि हम m 1 = min 1 = n सेट करते हैं, तो हमें असमानताओं के रूप में बाधाओं के साथ दोहरी समस्याओं की एक जोड़ी का एक विशेष मामला प्राप्त होता है।

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

समस्या का निरूपण

प्रकाशनों ने रैखिक प्रोग्रामिंग पद्धति का उपयोग करके प्रत्यक्ष अनुकूलन समस्याओं के समाधान पर विचार किया और स्किपी सॉल्वर का उचित विकल्प सुझाया। अनुकूलन.

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

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

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

इष्टतम उत्पादन कार्यक्रम की सीधी समस्या का समाधान

इस संसाधन के अधिकांश उपयोगकर्ताओं के गणितीय प्रशिक्षण के उच्च स्तर को ध्यान में रखते हुए, मैं ऊपरी और निचले प्रतिबंधों और समानता की ओर बढ़ने के लिए अतिरिक्त चर की शुरूआत के साथ संतुलन समीकरण प्रस्तुत नहीं करूंगा। इसलिए, मैं तुरंत समाधान में प्रयुक्त चर के पदनाम दूंगा:
एन - उत्पादित उत्पादों के प्रकार की संख्या;
एम - प्रयुक्त कच्चे माल के प्रकार की संख्या;
b_ub - आयाम m के उपलब्ध संसाधनों का वेक्टर;
A_ub आयाम m×N का एक मैट्रिक्स है, जिसका प्रत्येक तत्व j प्रकार के उत्पाद की एक इकाई के उत्पादन के लिए प्रकार i के संसाधन की खपत है;
सी प्रत्येक प्रकार के उत्पाद की एक इकाई के उत्पादन से लाभ का वेक्टर है;
x - प्रत्येक प्रकार के उत्पादित उत्पादों की आवश्यक मात्रा (इष्टतम उत्पादन योजना) जो अधिकतम लाभ सुनिश्चित करती है।

लक्ष्य समारोह
अधिकतमF(x)=c×x

प्रतिबंध
A×x≤b

चरों के संख्यात्मक मान:
एन=5; एम=4; b_ub = ; A_ub = [, , ,]; सी = .

कार्य
1. अधिकतम लाभ सुनिश्चित करने के लिए x ज्ञात करें
2. चरण 1 निष्पादित करते समय उपयोग किए गए संसाधनों का पता लगाएं
3. चरण 1 निष्पादित करते समय शेष संसाधन (यदि कोई हो) ढूंढें

अधिकतम निर्धारित करने के लिए (डिफ़ॉल्ट रूप से, न्यूनतम निर्धारित किया जाता है, उद्देश्य फ़ंक्शन के गुणांक को नकारात्मक चिह्न c = [-25, -35,-25,-40,-30] के साथ लिखा जाना चाहिए और ऋण चिह्न को अनदेखा करना चाहिए लाभ के सामने.

परिणाम प्रदर्शित करने के लिए प्रयुक्त नोटेशन:
एक्स- चर मानों की एक सरणी जो लक्ष्य फ़ंक्शन का न्यूनतम (अधिकतम) प्रदान करती है;
ढीला– अतिरिक्त चर के मान. प्रत्येक चर एक असमानता बाधा से मेल खाता है। शून्य के एक परिवर्तनीय मान का अर्थ है कि संबंधित बाधा सक्रिय है;
सफलता- सच है, यदि फ़ंक्शन इष्टतम समाधान ढूंढने में कामयाब रहा;
स्थिति- निर्णय की स्थिति:
0 - इष्टतम समाधान की खोज सफलतापूर्वक पूरी हुई;
1 - पुनरावृत्तियों की संख्या की सीमा समाप्त हो गई है;
2 - समस्या का कोई समाधान नहीं है;
3 - वस्तुनिष्ठ कार्य सीमित नहीं है।
एनआईटी- निष्पादित पुनरावृत्तियों की संख्या.

प्रत्यक्ष अनुकूलन समस्या के समाधान की सूची

#!/usr/bin/python # -*- कोडिंग: utf-8 -*- scipy से आयात scipy.optimize आयात linprog # लोडिंग एलपी लाइब्रेरी सी = [-25, -35,-25,-40,-30] # लक्ष्य फ़ंक्शन के गुणांकों की सूची b_ub = # संसाधन मात्राओं की सूची A_ub = [, # विशिष्ट संसाधन मानों का मैट्रिक्स, , ] d=linprog(c, A_ub, b_ub) # key,val in के लिए समाधान खोजें d.items(): print(key ,val) # समाधान आउटपुट यदि key=='x': q=# प्रयुक्त संसाधन प्रिंट('A_ub*x',q) q1= scipy.array(b_ub)-scipy.array (क्यू) #शेष संसाधन प्रिंट(" b_ub-A_ub*x", q1)

समस्या के समाधान के परिणाम
नाइट 3
स्थिति 0

सफलता सच है
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
मज़ा -5863.63636364
सुस्त [0.0.0.90.90909091]

निष्कर्ष

1. उत्पाद प्रकारों के लिए इष्टतम योजना पाई गई
2. वास्तविक संसाधन उपयोग मिला
3. अप्रयुक्त चौथे प्रकार के संसाधन का शेष भाग पाया गया [ 0. 0 0.0 0.0 90.909]
4. चरण 3 के अनुसार गणना की कोई आवश्यकता नहीं है, क्योंकि वही परिणाम स्लैक वेरिएबल में प्रदर्शित होता है

इष्टतम उत्पादन कार्यक्रम पर दोहरी समस्या का समाधान

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

आइए हम वांछित चर x के लिए एक निश्चित "छाया" मूल्य के रूप में एक नया उद्देश्य पेश करें जो निर्मित उत्पादों की बिक्री से लाभ के संबंध में किसी दिए गए संसाधन का मूल्य निर्धारित करता है।

सी - उपलब्ध संसाधनों का वेक्टर;
b_ub प्रत्येक प्रकार के उत्पाद की एक इकाई के उत्पादन से लाभ का वेक्टर है;
A_ub_T - ट्रांसपोज़्ड मैट्रिक्स A_ub।

लक्ष्य समारोह
minF(x)=c×x

प्रतिबंध
A_ub_T ×x≥ b_ub

चरों के लिए संख्यात्मक मान और संबंध:
सी = ; A_ub_T स्थानांतरण(A_ub); b_ub = .

काम:
प्रत्येक प्रकार के संसाधन के निर्माता के लिए मूल्य दर्शाने वाला x ज्ञात कीजिए।

scipy लाइब्रेरी के साथ समाधान की विशेषताएं। अनुकूलन
ऊपर से प्रतिबंधों को नीचे से प्रतिबंधों से बदलने के लिए, बाधा के दोनों हिस्सों को शून्य से एक से गुणा करना आवश्यक है - A_ub_T ×x≥ b_ub... ऐसा करने के लिए, प्रारंभिक डेटा को फॉर्म में लिखें: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

दोहरी अनुकूलन समस्या के समाधान की सूची

#!/usr/bin/python # -*- कोडिंग: utf-8 -*- scipy.optimize से आयात scipy आयात linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) for key,val in d.items(): print(key,val)

समस्या के समाधान के परिणाम
नाइट 7
संदेश अनुकूलन सफलतापूर्वक समाप्त हो गया.
मज़ा 5863.63636364
x [2.27272727 1.81818182 6.36363636 0. ]
सुस्त [5.45454545 2.27272727 0. 0. 0. ]
स्थिति 0
सफलता सच है

निष्कर्ष

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

प्रत्यक्ष और दोहरी समस्याओं की तुलना के परिणाम

1. दोहरी समस्या उत्पाद योजना की क्षमताओं का विस्तार करती है, लेकिन scipy का उपयोग करती है। ऑप्टिमाइज़ को प्रत्यक्ष पुनरावृत्तियों की दोगुनी संख्या में हल किया जाता है।
2. स्लैक वैरिएबल असमानताओं के रूप में बाधाओं की गतिविधि के बारे में जानकारी प्रदर्शित करता है, जिसका उपयोग, उदाहरण के लिए, कच्चे माल के संतुलन का विश्लेषण करने के लिए किया जा सकता है।
3. प्रत्यक्ष समस्या एक अधिकतमीकरण समस्या है, और दोहरी समस्या एक न्यूनतमकरण समस्या है, और इसके विपरीत।
4. प्रत्यक्ष समस्या में उद्देश्य फ़ंक्शन के गुणांक दोहरी समस्या में बाधाएं हैं।
5. प्रत्यक्ष समस्या में बाधाएं दोहरी समस्या में उद्देश्य फ़ंक्शन के गुणांक बन जाती हैं।
6. प्रतिबंधों में असमानताओं के संकेत उलटे हैं।
7. समानता की प्रणाली का मैट्रिक्स स्थानांतरित हो गया है।

लिंक

चूँकि वहाँ तीन इकाई सदिश हैं
आप तुरंत संदर्भ योजना लिख ​​सकते हैं
एक्स=(0,0,0,360,192,180).
आइए एक शून्य सिम्प्लेक्स तालिका बनाएं

हम परिणामी संदर्भ योजना की जाँच करते हैं
इष्टतमता के लिए.
हम उद्देश्य फ़ंक्शन के मूल्य की गणना करते हैं और
सिम्प्लेक्स मतभेद.
एफ0 सी पी0 0 360 0 192 0 180 0,
1 z1 c1 c P1 c1 9,
2 z2 c2 cP2 c2 10,...

जैसा कि 0वीं तालिका से देखा जा सकता है, गैर-शून्य
चर x4 , x5 , x6 , और x , x , x हैं
1
2
3
शून्य के बराबर हैं, क्योंकि वे बुनियादी नहीं हैं, लेकिन मुफ़्त हैं।
अतिरिक्त चर x4 , x5 , x6
उनके मूल्यों को अपने अनुसार लें
प्रतिबंध।
ये परिवर्तनीय मान इसके अनुरूप हैं
"योजना" जिसके तहत कुछ भी उत्पादित नहीं किया जाता है, कच्चा माल
का उपयोग नहीं किया जाता है और उद्देश्य फ़ंक्शन का मान है
शून्य, यानी निर्मित उत्पादों की लागत
अनुपस्थित।
निःसंदेह, यह योजना इष्टतम नहीं है।
इसे तालिका की चौथी पंक्ति से भी देखा जा सकता है, जिसमें
तीन नकारात्मक अंक हैं -9, -16 और -10।

10.

नकारात्मक संख्याएँ ही नहीं हैं
बढ़ने की संभावना बतायें
विनिर्मित उत्पादों की कुल लागत (इंच)
नकारात्मक रेटिंग के ऊपर कॉलम
सकारात्मक संख्याएं हैं), लेकिन यह भी
दिखाओ ये रकम कितनी बढ़ेगी
योजना में इस या उस की एक इकाई को शामिल करते समय
उत्पाद के प्रकार।
तो, संख्या -9 का मतलब है कि जब शामिल किया जाए
एक उत्पाद ए के लिए उत्पादन योजना
लागत में वृद्धि प्रदान करता है
9 इकाइयों के लिए उत्पाद

11.

यदि आप के लिए उत्पादन योजना में शामिल करते हैं
एक उत्पाद बी और सी, फिर कुल लागत
विनिर्मित उत्पादों में वृद्धि होगी
क्रमशः 10 और 16 इकाइयों द्वारा। इसलिए, साथ
आर्थिक रूप से संभव
योजना में उत्पाद सी को शामिल करना है।
उस बिंदु से भी ऐसा ही किया जाना चाहिए
देखें कि -16 सबसे छोटा है
नकारात्मक मूल्यांकन. तो, आधार के लिए
आइए वेक्टर P3 का परिचय दें।

12.

आइए संख्या Q ज्ञात करें।
360 192 180
क्यूमिन
;
;
न्यूनतम 30; 24;60
3
12 8
आइए इसे तालिका के अंतिम कॉलम में दर्ज करें।
संख्या 24 वेक्टर P5 से मेल खाती है।
आर्थिक दृष्टि से 192/8=24
मतलब कितने उत्पाद C
उद्यम ध्यान में रखकर उत्पादन कर सकता है
उपभोग दर और कच्चे माल की उपलब्ध मात्रा
प्रत्येक प्रकार।

13.

चूँकि प्रत्येक प्रकार का कच्चा माल उपलब्ध है
क्रमशः 360, 192 और 180 किग्रा, और एक के लिए
उत्पाद सी के लिए प्रत्येक के लिए कच्चे माल के व्यय की आवश्यकता होती है
प्रकार 12, 8 और 3 किग्रा, फिर अधिकतम संख्या
उत्पाद C जिनका निर्माण किया जा सकता है
उद्यम बराबर है
मिनट(360/12,192/8,180/3)=192/8=24, यानी।
उत्पादन के लिए सीमित कारक
उत्पाद सी कच्चे माल की उपलब्ध मात्रा है
दूसरा प्रकार. उसके उद्यम को ध्यान में रखते हुए कर सकते हैं
24 उत्पादों का उत्पादन करें सी। इस मामले में, दूसरे प्रकार के कच्चे माल का पूरी तरह से उपयोग किया जाएगा और,
इसका मतलब है कि वेक्टर को बाहर रखा जाना चाहिए
पी 5
आधार.

14.

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

15.

16.

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

17.

एक नकारात्मक रेटिंग है -2.
योजना में सुधार किया जा सकता है. आइये आधार से परिचय कराते हैं
वेक्टर पी2. चलिए हिसाब लगाते हैं
72 24 108
क्यू मिनट ;
;
न्यूनतम 8; 48;72 8.
9 1/ 2 3 / 2
.
हम आधार P4 से प्राप्त करते हैं।

18.

अनुमेय रेखाएँ पहली पंक्ति और दूसरी होंगी
स्तंभ। अनुज्ञेय तत्व 9.
पहली पंक्ति को 9 से विभाजित करें, भरें
फिर, नई तालिका की पहली पंक्ति
चलिए दूसरा कॉलम रीसेट करें। इसके लिए
पहली पंक्ति को (-1/2) से गुणा करें और
दूसरे को जोड़ें और फिर पहले को गुणा करें
पंक्ति को (-3/2) से जोड़ें और तीसरी पंक्ति में जोड़ें।
आइए तालिका 2 भरें।

19.

20.

हम इस बात से आश्वस्त हैं
सिंप्लेक्स अंतर की गणना
1 सीपी1 सी1 10 1 16 0.25 9 5,
2 सीपी2 सी2 10 1 16 0 10 0,
3 सीपी3 सी3 10 0 16 1 0 0 16 0,
4 सीपी4 सी4 10 1/9 16 1/8 0 (1/6) 2/9,
5 सीपी5 -सी5 =10 (-1/6)+16 5/24+0(-1/2)=5/3,
6 0.

21.

इष्टतम उत्पादन योजना नहीं है
उत्पादों के उत्पादन की परिकल्पना की गई है
प्रकार ए उत्पादों के लिए उत्पादन योजना को बढ़ावा मिलेगा
संकेतित कुल लागत में कमी.
इसे कॉलम की चौथी पंक्ति से देखा जा सकता है, जहां संख्या 5 है
दर्शाता है कि इस योजना के साथ समावेशन किया गया है
उत्पाद A की एक इकाई का आउटपुट इसकी ओर ले जाता है
केवल कुल मूल्य में कमी के लिए
5 इकाइयों द्वारा मूल्य
तो, योजना 8 उत्पादों को जारी करने का प्रावधान करती है
बी और 20 उत्पाद सी. प्रकार 1 और 2 के कच्चे माल
पूरी तरह से उपयोग किया जाता है, और टाइप 3 96 किलोग्राम अप्रयुक्त रहता है।

22. दोहरी रैखिक प्रोग्रामिंग समस्याएं

प्रत्येक ZLP का मिलान किया जा सकता है
समस्या को मूल से द्वैत कहा जाता है
काम।
उपयोग की समस्या पर विचार करें
संसाधन। आइए मान लें कि कंपनी ए
n प्रकार के उत्पाद, मूल्य उत्पन्न करता है
जिनकी रिहाई चर द्वारा निर्धारित होती है
X1, x2, ..., xn
.
उत्पादन में मैं अलग हूँ
संसाधनों के प्रकार, जिनकी मात्रा सीमित है
मान b1, b2, ..., bn।

23.

प्रत्येक संसाधन की प्रति इकाई लागत दरें ज्ञात होती हैं
प्रत्येक प्रकार का उत्पाद एक मैट्रिक्स बनाता है,
a11
ए21
ए
...
am1
ए12
a22
...
मैं 2 हूँ
...a1n
... ए2 एन
... ...
...हूँ
साथ ही प्रत्येक प्रकार के उत्पाद की इकाई लागत
सी1, सी2, ..., सीएन
इसके लिए उत्पादन को व्यवस्थित करना आवश्यक है
उद्यम ए को अधिकतम प्रदान किया गया था
लाभ।

24.

कार्य खोजने तक सीमित हो जाता है
गैर-नकारात्मक चर
x1, x2, ..., xn,
जिसमें संसाधन की खपत नहीं है
उनकी निर्दिष्ट संख्या से अधिक है, और
सभी उत्पादों की लागत पहुंच जाएगी
अधिकतम।

25.

गणितीय रूप में समस्या
निम्नलिखित रूप में लिखा गया है:
एफ सी1 एक्स1 सी2 एक्स2 ... सी जे एक्स जे ... सीएन एक्सएन मैक्स
शर्तों के अधीन
a11 x1 a12 x2 ... a1 j x j ... a1n xn b1 ,
a21 x2 a22 x2 ... a2 j x j ... a2 n xn b2 ,
.
...............................................................,
ए एक्स ए एक्स ... ए एक्स ... ए एक्स बी
एमजे जे
एम.एन.
एम
एम 1 1 एम 2 2
एक्स जे 0, जे 1, एन।

26.

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

27.

यदि y1 , y2 , ..., yn द्वारा निरूपित किया जाए
किस उद्यम पर कीमतें बी
फिर, एंटरप्राइज़ ए से संसाधन खरीदता है
कार्य निम्नलिखित तक सिमट कर रह जाता है: ढूँढ़ें
चर y1, y2, ..., yn, के ऐसे मान
जिस पर संसाधनों की लागत,
किसी भी प्रकार की प्रति यूनिट खर्च की गई
उत्पाद लाभ से कम नहीं (कीमतें)
उत्पादन की इस इकाई और कुल के लिए
संसाधनों की लागत पहुंचती है
न्यूनतम,

28.

यानी यूनिट रेटिंग क्या होनी चाहिए
प्रत्येक संसाधन y1, y2, ..., yn,
ताकि दिए गए वॉल्यूम के लिए
उपलब्ध संसाधन द्वि, दिया गया
लागत सी जे (जे 1, एन) इकाइयां
उत्पाद और लागत मानक ai
समग्र लागत अनुमान को न्यूनतम करें
सभी उत्पादों के लिए.

29. मैट. दोहरी समस्या मॉडल

गणितीय रूप में समस्या
इस प्रकार लिखा गया है:
*
एफ बी1 वाई1 बी2 वाई2...बीएम वाईएम मिनट
प्रतिबंधों के तहत
a11 y1 a21 y2 ... am1 ym c1 ,
ए वाई ए वाई... ए वाई सी,
एम2 एम
2
12 1 22 2
..................................................
ए वाई ए वाई... ए वाई सी,
एमएन एम
एन
1एन 1 2 एन 2
यि 0, मैं 1, 2,..., म.

30. दोहरी समस्या के चरों का आर्थिक अर्थ

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

31.

रैखिक की दोहरी समस्याएँ
प्रोग्रामिंग को कहा जाता है
यदि वे संतुष्ट हों तो सममित
निम्नलिखित गुण:
दोहरी समस्या में चरों की संख्या
मूल समस्या की बाधाओं की संख्या के बराबर है, और
दोहरी समस्या की बाधाओं की संख्या
में चरों की संख्या के बराबर संख्या के बराबर
मूल;
एक समस्या में अधिकतम लक्ष्य मांगा जाता है
कार्य, दूसरे में - न्यूनतम;
लक्ष्य में चर के लिए गुणांक
एक कार्य के कार्य निःशुल्क हैं
किसी अन्य समस्या की बाधा प्रणाली के सदस्य;

32.

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

33. सममित दोहरी समस्याओं को हल करना

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

34. प्रथम द्वैत प्रमेय की आर्थिक सामग्री

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

35. दोहरी समस्याओं के एक जोड़े को एक साथ हल करने की विधि

मूल समस्या: दोहरी समस्या:
एफ सी1एक्स1 सी2 एक्स2 ... सी जे एक्स जे ... एफ * बी1 वाई1 बी2 वाई2 ...
सीएन एक्सएन मैक्स
a11 x1 a12 x2 ... a1n xn xn 1 b1 ,
a21 x1 a22 x2 ... a2 n xn xn 2 b2 ,
..........................................................
ए एक्स ए एक्स ... ए एक्स एक्स बी,
एम.एन.
एन एम
एम
एम 1 1 एम 2 2
एक्स जे 0, जे 1, 2,..., एन एम।
बीएम वाईएम मिनट,
a11 y1 a21 y2 ...am1 ym ym 1 c1 ,
ए वाई ए वाई... ए वाई वाई सी,
एम2 एम
मी 2
2
12 1 22 2
.............................................................
ए वाई ए वाई... ए वाई वाई सी,
एमएन एम
एम एन
एन
1एन 1 2 एन 2
यी 0, आई 1, 2,..., एम एन।

36.

समस्याओं में चरों की संख्या समान होती है
और m + n के बराबर है। मूल समस्या में
मूल चर हैं

चर xn 1 , xn 2 , ..., xn m
,
और दोहरी समस्या में -
सहायक गैर-नकारात्मक
चर yn 1, yn 2, ..., yn m।
एक समस्या के मूल चर
मुक्त चर अनुरूप हैं
एक अन्य कार्य, और इसके विपरीत।

37.

38.

सारणीबद्ध सिम्प्लेक्स विधि का उपयोग करके ZLP को हल करते समय, दोहरी समस्या को हल करना
तालिका की अंतिम पंक्ति में निहित है।
यह जे है.
इसके अलावा, दोहरे के मुख्य चर

संगत अतिरिक्त
मूल समस्या के चर, और
दोहरे के अतिरिक्त चर
कार्य स्तंभों में समाहित हैं,
मुख्य के अनुरूप
(मूल) प्रारंभिक चर
कार्य.

39. उदाहरण.

आइए हम समस्या दोहरे का एक मॉडल तैयार करें
उदाहरण 2 से समस्या पर (व्याख्यान की शुरुआत):
किसी फ़ंक्शन का अधिकतम ज्ञात करें

40.

41.

मूल समस्या के चर x1, x2, x3 उत्पादों A, B और C की संख्या हैं। आइए परिचय दें
दोहरी समस्या चर y1, y2, y3
किसी फ़ंक्शन का न्यूनतम ज्ञात करें
एफ * 360 वाई1 192 वाई2 180 वाई3 मिनट
प्रतिबंधों के तहत
18 y1 6 y2 5 y3 9,
15 y1 4 y2 3 y3 10,
12 वर्ष 8 वर्ष 3 वर्ष 16,
2
3
1
y1 , y2 , y3 0.

42. मूल समस्या की अंतिम तालिका पर विचार करें

43.

स्तंभ P4 की अंतिम पंक्ति में y1 का मान,
वे। y1 2 ;
9य 5
स्तंभ P5 की अंतिम पंक्ति में मान 2 3,
स्तंभ P6 की अंतिम पंक्ति में y3 का मान 0 है।
शेष मान कॉलम 1,2,3 में पाए जाते हैं।
2 5
वाई (; ;0;5;0;0)
9 3
जिसमें
2
5
एफ 360 192 180 0 0 5 0 0 0 0 400
9
3
*
- यह सभी उत्पादों के लिए न्यूनतम लागत है।
2/9 और 5/3 1 और 2 के कच्चे माल की छाया कीमतें हैं
क्रमशः प्रजातियाँ.