आइए हम विमान पर सिस्टम के स्वीकार्य समाधानों के सेट का निर्माण करें रैखिक असमानताएंऔर ज्यामितीय रूप से न्यूनतम मान ज्ञात करें वस्तुनिष्ठ कार्य.

हम समन्वय प्रणाली x 1 ओह 2 लाइनों में निर्माण करते हैं

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

हम एक सदिश और उसके लिए लंबवत शून्य स्तर की एक रेखा बनाते हैं।

रेखा (5) को सदिश की दिशा में ले जाने पर, हम देखते हैं कि क्षेत्र का अधिकतम बिंदु रेखा (3) और रेखा (2) के प्रतिच्छेदन के बिंदु A पर होगा। हम समीकरणों की प्रणाली का हल पाते हैं:

तो, हमें बिंदु (13;11) और मिला।

रेखा (5) को सदिश की दिशा में ले जाने पर, हम देखते हैं कि क्षेत्र का न्यूनतम बिंदु रेखा (1) और रेखा (4) के प्रतिच्छेदन के बिंदु B पर होगा। हम समीकरणों की प्रणाली का हल पाते हैं:

तो, हमें बिंदु (6; 6) और मिला।

2. एक फर्नीचर कंपनी संयुक्त कैबिनेट और कंप्यूटर टेबल बनाती है। उनका उत्पादन कच्चे माल (उच्च गुणवत्ता वाले बोर्ड, फिटिंग) की उपलब्धता और उन्हें संसाधित करने वाली मशीनों के संचालन समय तक सीमित है। प्रत्येक कैबिनेट को 5 एम 2 बोर्ड की आवश्यकता होती है, एक टेबल के लिए - 2 एम 2। $ 10 के लिए फिटिंग एक कैबिनेट पर और $ 8 एक टेबल पर खर्च की जाती है। कंपनी अपने आपूर्तिकर्ताओं से प्रति माह 600 m2 बोर्ड और $ 2000 के लिए सहायक उपकरण प्राप्त कर सकती है। प्रत्येक कैबिनेट के लिए, 7 घंटे मशीन के काम की आवश्यकता होती है, एक टेबल के लिए - 3 घंटे। प्रति माह मशीन के संचालन के केवल 840 घंटे का उपयोग करना संभव है।

लाभ को अधिकतम करने के लिए एक फर्म को प्रति माह कितने संयोजन कैबिनेट और कंप्यूटर टेबल का उत्पादन करना चाहिए यदि एक कैबिनेट $ 100 में लाता है और प्रत्येक तालिका $ 50 बनाती है?

• 1. लिखें गणित का मॉडलसिंप्लेक्स विधि का उपयोग करके समस्या का समाधान करें।
• 2. दोहरी समस्या का गणितीय मॉडल बनाएं, मूल समस्या के समाधान के आधार पर उसका समाधान लिखें।
• 3. उपयोग किए गए संसाधनों की कमी की डिग्री निर्धारित करें और इष्टतम योजना की लाभप्रदता का औचित्य साबित करें।
• 4. प्रत्येक प्रकार के संसाधन के उपयोग के आधार पर, उत्पादन में और वृद्धि की संभावनाओं का अन्वेषण करें।
• 5. एक नए प्रकार के उत्पाद - बुकशेल्फ़ को पेश करने की व्यवहार्यता का मूल्यांकन करें, यदि एक शेल्फ के निर्माण पर $ 5 के लिए 1 मीटर 2 बोर्ड और सहायक उपकरण खर्च किए जाते हैं, और मशीन संचालन के 0.25 घंटे की आवश्यकता होती है और बिक्री से लाभ होता है एक शेल्फ $ 20 है।
• 1. आइए इस समस्या के लिए एक गणितीय मॉडल बनाएं:

x 1 से निरूपित करें - अलमारियाँ के उत्पादन की मात्रा, और x 2 - तालिकाओं के उत्पादन की मात्रा। आइए हम बाधाओं की एक प्रणाली और एक लक्ष्य कार्य की रचना करें:

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

आइए कार्य डेटा को तालिका के रूप में लिखें:

तालिका एक

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

लैब # 1 रैखिक प्रोग्रामिंग समस्याओं का समाधान

उद्देश्यसमस्या समाधान कौशल का अधिग्रहण रैखिक प्रोग्रामिंगएक्सेल की ग्राफिकल, सिम्प्लेक्स विधि और साधन।

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

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

उदाहरण. उद्देश्य फलन का अधिकतम मान ज्ञात कीजिए ली=2एक्स 1 +2एक्स 2 दी गई बाधाओं के तहत

समाधान।आइए हम असमानताओं के संकेतों को सटीक समानता के संकेतों में बदलकर बाधा प्रणाली के समाधान डोमेन का निर्माण करें:

मैं 1: 3एक्स 1 -2एक्स 2 +6=0,

मैं 2: 3एक्स 1 +एक्स 2 -3=0,

मैं 3:एक्स 1 -3=0.

डीसे

2 0 1 3 एक्स 1

(मैं 1) (मैं 3)

सीधा मैं 1 विमान को विभाजित करता है एक्सहे परदो आधे विमानों में, जिनमें से एक को चुना जाना चाहिए जो सिस्टम (3) में पहली असमानता को संतुष्ट करता है। इसके लिए हम टी. हे(0; 0) और असमानता में स्थानापन्न करें। यदि यह सच है, तो आपको उस सीधी रेखा से अर्ध-तल को छायांकित करने की आवश्यकता है जिसमें तथाकथित है। हे(0; 0)। सीधी रेखाओं के साथ भी ऐसा ही करें। मैं 2 और मैं 3. असमानताओं के समाधान का क्षेत्र (3) एक बहुभुज है एबीसीडी. समतल के प्रत्येक बिंदु के लिए फलन लीएक निश्चित मान लेता है ली=लीएक । सभी बिंदु धाराओं का सेट एक सीधी रेखा है ली=सी 1 एक्स 1 +सी 2 एक्स 2 (हमारे मामले में ली=2एक्स 1 +2एक्स 2) वेक्टर के लंबवत से(साथ 1 ;साथ 2) (से(2; 2)), मूल से उभर रहा है। यदि यह रेखा सदिश की धनात्मक दिशा में चलती है साथ, फिर उद्देश्य समारोह लीबढ़ेगा, नहीं तो घटेगा। इस प्रकार, हमारे मामले में, बहुभुज से बाहर निकलने पर सीधी रेखा एबीसीडीनिर्णय चलेंगे पर(3; 7.5), और इसलिए, सहित। परउद्देश्य फ़ंक्शन अधिकतम मान लेता है, अर्थात। लीअधिकतम =2ּ3+2ּ7,5=21। इसी तरह, यह निर्धारित किया जाता है कि फ़ंक्शन न्यूनतम मान लेता है, अर्थात, डी(1; 0) और लीन्यूनतम=2ּ1+2ּ0=2।

एक रैखिक प्रोग्रामिंग समस्या को हल करने के लिए सरल विधि का एल्गोरिथ्म इस प्रकार है।

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

2. लक्ष्य फलन को मूल और सहायक चरों के रूप में व्यक्त किया जाता है।

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

4. प्रत्येक सिम्प्लेक्स झांकी रैखिक प्रोग्रामिंग समस्या का समाधान देती है: मुक्त चर शून्य के बराबर होते हैं, मूल चर क्रमशः मुक्त सदस्यों के बराबर होते हैं।

5. इष्टतमता मानदंड अधिकतम के लिए समस्या को हल करने के लिए तालिका की अंतिम पंक्ति में नकारात्मक तत्वों की अनुपस्थिति और न्यूनतम के लिए सकारात्मक तत्व हैं।

6. समाधान को बेहतर बनाने के लिए एक सिंप्लेक्स की झांकी से दूसरी झांकी में जाना जरूरी है। ऐसा करने के लिए, पिछली तालिका में, अधिकतम समस्या में तालिका की अंतिम पंक्ति में सबसे छोटे नकारात्मक तत्व के अनुरूप कुंजी कॉलम और न्यूनतम समस्या में सबसे बड़ा सकारात्मक गुणांक खोजें। फिर कुंजी कॉलम के संबंधित सकारात्मक तत्वों के लिए मुक्त शर्तों के न्यूनतम अनुपात के अनुरूप कुंजी पंक्ति खोजें। कुंजी कॉलम और कुंजी पंक्ति के चौराहे पर कुंजी तत्व है।

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

8. एक इष्टतम योजना प्राप्त होने तक सिम्प्लेक्स टेबल रूपांतरित हो जाते हैं।

उदाहरण. किसी फ़ंक्शन का अधिकतम मान ज्ञात करें
यदि चर
प्रतिबंधों की प्रणाली को संतुष्ट करें:

समाधान। 1. नए चर पेश करना
, जिसकी मदद से हम सिस्टम की असमानताओं को समीकरणों में बदलते हैं:

हम उद्देश्य फलन के गुणांकों के चिह्न को बदलते हैं या इसे रूप में लिखते हैं
. हम पहली सिंप्लेक्स तालिका भरते हैं, शून्य रेखा में हम लिखते हैं एक्स 1 ,एक्स 2 और (मुक्त गुणांक)। कॉलम जीरो में एक्स 3 ,एक्स 4 ,एक्स 5 और एफ. हम इस तालिका को समीकरणों की प्राप्त प्रणाली और रूपांतरित उद्देश्य फ़ंक्शन के अनुसार भरते हैं।

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

2. हम पहली तालिका का हल करने वाला तत्व इस प्रकार पाते हैं। अंतिम पंक्ति के तत्वों में से, हम निरपेक्ष मान में सबसे बड़ा ऋणात्मक गुणांक चुनते हैं (यह -3 है) और दूसरा स्तंभ समाधान के रूप में स्वीकार किया जाता है। यदि किसी स्तंभ के सभी गुणांक धनात्मक नहीं हैं, तो
.

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

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

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

.

हम इन नियमों के अनुसार तालिकाओं को तब तक भरना जारी रखते हैं जब तक कि मानदंड पूरा नहीं हो जाता। हमारे पास हमारे कार्य के लिए दो और टेबल हैं।

	एक्स 1	एक्स 4					एक्स 3	एक्स 2
एक्स 3						एक्स 1
एक्स 2						एक्स 2
एक्स 5						एक्स 5

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

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

न्यूनतम के लिए एक रैखिक प्रोग्रामिंग समस्या को हल करते समय, अंतिम पंक्ति में सबसे बड़ा सकारात्मक गुणांक चुना जाता है, और निर्दिष्ट एल्गोरिदम तब तक किया जाता है जब तक कि अंतिम पंक्ति में कोई सकारात्मक गुणांक न हो।

एक्सेल का उपयोग करके रैखिक प्रोग्रामिंग समस्याओं का समाधान निम्नानुसार किया जाता है।

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

ऐसा करने के लिए, माइक्रोसॉफ्ट ऑफिस फाइल (2010) पर क्लिक करें, फिर एक्सेल विकल्प बटन पर क्लिक करें। दिखाई देने वाली एक्सेल विकल्प विंडो में, बाईं ओर ऐड-इन्स फ़ील्ड चुनें। विंडो के दाईं ओर, मैनेज फील्ड का मान एक्सेल ऐड-इन्स पर सेट किया जाना चाहिए, "गो" बटन पर क्लिक करें, जो इस फील्ड के बगल में स्थित है। ऐड-इन्स विंडो में, फाइंड सॉल्यूशन के आगे वाले चेक बॉक्स को चुनें और फिर ओके पर क्लिक करें। फिर आप इंस्टॉल किए गए ऐड-इन फाइंड सॉल्यूशंस के साथ काम कर सकते हैं।

सर्च सॉल्यूशंस को कॉल करने से पहले, वर्कशीट पर एक रैखिक प्रोग्रामिंग समस्या (गणितीय मॉडल से) को हल करने के लिए डेटा तैयार करना आवश्यक है:

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

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

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

1) "ऑब्जेक्टिव फंक्शन को ऑप्टिमाइज़ करें" फ़ील्ड में ऑब्जेक्टिव फंक्शन वाले सेल को निर्दिष्ट करें (इस सेल में ऑब्जेक्टिव फंक्शन के लिए फॉर्मूला होना चाहिए)। लक्ष्य सेल के मूल्य को अनुकूलित करने के लिए विकल्प का चयन करें (अधिकतम करें, छोटा करें):

2) "परिवर्तनशील कोशिकाओं को बदलना" फ़ील्ड में, चर कोशिकाओं को दर्ज करें। अगले क्षेत्र में "प्रतिबंधों के अनुसार" "जोड़ें" बटन का उपयोग करके निर्दिष्ट प्रतिबंध दर्ज करें। दिखाई देने वाली विंडो में, प्रतिबंधों की प्रणाली के लिए सूत्रों वाले कक्ष दर्ज करें, प्रतिबंध के संकेत और प्रतिबंध के मूल्य (मुक्त कारक) का चयन करें:

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

उदाहरण।सॉल्वर ऐड-इन का उपयोग करके हल करें एक्सेल कार्यरैखिक प्रोग्रामिंग: किसी फ़ंक्शन का अधिकतम मान ज्ञात करें
प्रतिबंधों के तहत

,

;

,
.

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

हम उद्देश्य समारोह और बाधाओं की प्रणाली के लिए निर्भरता का परिचय देते हैं। ऐसा करने के लिए, सेल C2 में, सूत्र दर्ज करें =SUMPRODUCT(A2:B2;A3:B3)। कोशिकाओं C4 और C5 में, क्रमशः, सूत्र हैं: =SUMPRODUCT(A2:B2;A4:B4) और =SUMPRODUCT(A2:B2;A5:B5)। परिणाम एक तालिका है।

हम "समाधान के लिए खोजें" कमांड लॉन्च करते हैं और दिखाई देने वाली विंडो में भरते हैं समाधान के लिए खोजें निम्नानुसार। "ऑब्जेक्टिव फंक्शन ऑप्टिमाइज़ करें" फ़ील्ड में, सेल C2 दर्ज करें। हम लक्ष्य सेल "अधिकतम" के मूल्य को अनुकूलित करना चुनते हैं।

"परिवर्तनशील कोशिकाओं को बदलना" फ़ील्ड में, चर कक्ष A2:B2 दर्ज करें। "प्रतिबंधों के अनुसार" फ़ील्ड में, "जोड़ें" बटन का उपयोग करके निर्दिष्ट प्रतिबंध दर्ज करें। सेल संदर्भ $C$4:$C$5 प्रतिबंध संदर्भ =$D$4:$D$5 उनके बीच का चिह्न<= затем кнопку «ОК».

"अप्रतिबंधित चर को गैर-ऋणात्मक बनाएं" बॉक्स को चेक करें। समाधान विधि का चयन करें "सिंप्लेक्स विधि द्वारा रैखिक समस्याओं के समाधान की खोज करें"।

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

संवाद बॉक्स में "समाधान की खोज के परिणाम" हम परिणाम को सहेजते हैं x1=0.75, x2=0.75 , F=1.5, जो उद्देश्य फ़ंक्शन के अधिकतम मूल्य के बराबर है।

स्वतंत्र कार्य के लिए कार्य

अभ्यास 1।फंक्शन का अधिकतम और न्यूनतम मान ज्ञात करने के लिए ग्राफिकल, सिम्प्लेक्स विधियाँ और एक्सेल उपकरण एफ(एक्स) बाधाओं की दी गई प्रणाली के लिए।

1. एफ(एक्स)=10एक्स 1 +5एक्स 2 2. एफ(एक्स)=3एक्स 1 -2एक्स 2

3. एफ(एक्स)=3एक्स 1 +5एक्स 2 4. एफ(एक्स)=3एक्स 1 +3एक्स 2

5. एफ(एक्स)=4एक्स 1 -3एक्स 2 6. एफ(एक्स)=2एक्स 1 -एक्स 2

7. एफ(एक्स)=-2एक्स 1 +4एक्स 2 8. एफ(एक्स)=4एक्स 1 -3एक्स 2

9. एफ(एक्स)=5एक्स 1 +10एक्स 2 10. एफ(एक्स)=2एक्स 1 +एक्स 2

11. एफ(एक्स)=एक्स 1 +एक्स 2 12. एफ(एक्स)=3एक्स 1 +एक्स 2

13. एफ(एक्स)=4एक्स 1 +5एक्स 2 14. एफ(एक्स)=3एक्स 1 +2एक्स 2

15. एफ(एक्स)=-एक्स 1 -एक्स 2 16. एफ(एक्स)=-3एक्स 1 -5एक्स 2

17. एफ(एक्स)=2एक्स 1 +3एक्स 2 18. एफ(एक्स)=4एक्स 1 +3एक्स 2

19. एफ(एक्स)=-3एक्स 1 -2एक्स 2 20. एफ(एक्स)=-3एक्स 1 +4एक्स 2

21. एफ(एक्स)=5एक्स 1 -2एक्स 2 22. एफ(एक्स)=-2एक्स 1 +3एक्स 3

23. एफ(एक्स)=2एक्स 1 +3एक्स 2 24. एफ(एक्स)=4एक्स 1 +3एक्स 2

25. एफ(एक्स)=-3एक्स 1 -2एक्स 2 26. एफ(एक्स)=-3एक्स 1 +4एक्स 2

27. एफ(एक्स)=-2एक्स 1 +4एक्स 2 28. एफ(एक्स)=4एक्स 1 -3एक्स 2

29. एफ(एक्स)=-एक्स 1 -एक्स 2 30. एफ(एक्स)=-3एक्स 1 -5एक्स 2

परीक्षण प्रश्न।

1. किन कार्यों को रैखिक प्रोग्रामिंग समस्याएँ कहते हैं?

2. रैखिक प्रोग्रामन समस्याओं के उदाहरण दीजिए।

3. रेखीय प्रोग्रामिंग की समस्या को आलेखीय विधि द्वारा कैसे हल किया जाता है?

4. रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए सरल विधि के एल्गोरिदम का वर्णन करें।

5. एक्सेल का उपयोग करके रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एल्गोरिदम का वर्णन करें।

विषय: रैखिक प्रोग्रामिंग

कार्य 2.ए. एक ग्राफिकल विधि द्वारा एक रैखिक प्रोग्रामिंग समस्या को हल करना

ध्यान!

यह कार्य संख्या 2073 का परिचय संस्करण है, मूल की कीमत 200 रूबल है। माइक्रोसॉफ्ट वर्ड में बनाया गया है।

भुगतान। संपर्क।

विकल्प 7. अधिकतम और न्यूनतम मान ज्ञात करेंरैखिक कार्य Ф \u003d 2x 1 - 2 x 2प्रतिबंधों के साथ: x 1 + x 2 4;

- एक्स 1 + 2 एक्स 2 ≤ 2;

एक्स 1 + 2 एक्स 2 ≤ 10;

एक्स मैं 0, मैं = 1.2।

समाधान:

सशर्त रूप से असमानताओं के संकेतों को समानता के संकेतों के साथ बदलकर, हम समीकरणों की एक प्रणाली प्राप्त करते हैं x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

हम इन समीकरणों के अनुसार सीधी रेखाएँ बनाते हैं, फिर, असमानताओं के संकेतों के अनुसार, हम अर्ध-तलों का चयन करते हैं और उनका सामान्य भाग प्राप्त करते हैं - ODE के स्वीकार्य समाधानों का क्षेत्र - चतुर्भुज MNPQ।

फ़ंक्शन का न्यूनतम मान

टीएसआई - बिंदु एम (2; 2) पर

मिनट = 2 2 - 2 2 = 0.

अधिकतम मान बिंदु N (10; 0) पर पहुँच जाता है,

अधिकतम \u003d 2 10 - 2 0 \u003d 20।

विकल्प 8. अधिकतम और न्यूनतम मान ज्ञात कीजिए

रैखिक कार्य Ф \u003d x 1 + x 2

प्रतिबंधों के साथ: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 0;

एक्स 1 + एक्स 2 - 4 ≥ 0;

एक्स मैं 0, मैं = 1.2।

समाधान:

सशर्त रूप से असमानताओं के संकेतों को समानता के संकेतों के साथ बदलकर, हम समीकरणों की एक प्रणाली प्राप्त करते हैं x1 - 4 x2 = 4;

3 x1 - x2 = 0;

हम इन समीकरणों के अनुसार सीधी रेखाएँ बनाते हैं, फिर, असमानताओं के संकेतों के अनुसार, हम अर्ध-तलों का चयन करते हैं और उनका सामान्य भाग प्राप्त करते हैं - ODE के स्वीकार्य समाधानों का क्षेत्र - एक असीम बहुभुज MNPQ।

फ़ंक्शन का न्यूनतम मान

tions - एक सीधी रेखा एनपी पर, उदाहरण के लिए

बिंदु Р(4; 0) पर

मिनट = 4 + 0 = 4।

ODE ऊपर से सीमित नहीं है, इसलिए Ф मैक्स = + ।

विकल्प 10. अधिकतम और न्यूनतम मान ज्ञात कीजिए

रैखिक कार्य \u003d 2 x 1 - 3 x 2

प्रतिबंधों के साथ: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 16;

एक्स 2 5;

एक्स मैं 0, मैं = 1.2।

सशर्त रूप से असमानताओं के संकेतों को समानता के संकेतों के साथ बदलकर, हम समीकरणों की एक प्रणाली प्राप्त करते हैं

एक्स 1 + 3 एक्स 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4)।

हम इन समीकरणों के अनुसार सीधी रेखाएँ बनाते हैं, फिर, असमानताओं के संकेतों के अनुसार, हम अर्ध-तलों का चयन करते हैं और उनका सामान्य भाग प्राप्त करते हैं - ODE के स्वीकार्य समाधानों का क्षेत्र - बहुभुज MNPQRS।

हम सदिश (2; -3) की रचना करते हैं और मूल बिन्दु से होकर खींचते हैं स्तर रेखा- सीधा।

हम समतल रेखा को दिशा में घुमाते हैं, जबकि F का मान बढ़ता है। बिंदु S(7; 0) पर, उद्देश्य फलन अपने अधिकतम Ф अधिकतम =2·7–3·0= 14 तक पहुँच जाता है। हम स्तर रेखा को दिशा में ले जाते हैं, जबकि का मान घटता है। फ़ंक्शन का न्यूनतम मान बिंदु N(0; 5) पर है

मिनट = 2 0 - 3 5 = -15।

कार्य 2.बी. एक रैखिक प्रोग्रामिंग समस्या का समाधान

विश्लेषणात्मक सिंप्लेक्स विधि

विकल्प 7. उद्देश्य फ़ंक्शन को छोटा करें Ф \u003d x 1 - x 2 + x 3 + x 4 + x 5 - x 6

प्रतिबंधों के तहत: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 - 4 x 3 + 2 x 6 \u003d 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6।

समाधान:

अज्ञात की संख्या n=6, समीकरणों की संख्या m=3। इसलिए, r = n-m = 3 अज्ञात को मुक्त माना जा सकता है। आइए x 1, x 3 और x 6 चुनें।

हम बुनियादी चर x 2 , x 4 और x 5 को मुक्त चर के रूप में व्यक्त करते हैं और प्रणाली को इकाई के आधार पर लाते हैं

x 2 \u003d 2 - 3 x 1 + 4 x 3 - 2 x 6

x 4 \u003d 9 - x 1 - 6 x 6 (*)

x 5 \u003d 6 - x 1 - 2 x 3 - 2 x 6

उद्देश्य समारोह इस तरह दिखेगा:

\u003d x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 - x 1 - 6 x 6 +6 - x 1 - 2 x 3 - 2 x 6 - x 6 =

13 + 2 x 1 - 5 x 3 - 7 x 6

आइए x 1 \u003d x 3 \u003d x 6 \u003d 0 डालते हैं, जबकि मूल चर मान x 2 \u003d 2 पर ले लेंगे; एक्स 4 \u003d 9; x 5 \u003d 6, यानी पहला संभव समाधान (0; 2; 0; 9; 6; 0), उद्देश्य फ़ंक्शन 1 \u003d 13।

चर x 3 और x 6 ऋणात्मक गुणांक वाले उद्देश्य फलन में शामिल हैं, इसलिए, उनके मूल्यों में वृद्धि के साथ, का मान घट जाएगा। उदाहरण के लिए, x 6 लें। सिस्टम के पहले समीकरण (*) से यह देखा जा सकता है कि x 6 के मान में वृद्धि x 6 \u003d 1 (जब तक x 2 0) तक संभव है। इस मामले में, x 1 और x 3 शून्य के बराबर मान बनाए रखते हैं। अब, मूल चर के रूप में, हम x 4, x 5, x 6 को निःशुल्क - x 1, x 2, x 3 के रूप में लेते हैं। आइए हम नए बुनियादी चरों को नए मुक्त चरों के रूप में व्यक्त करें। प्राप्त

x 6 \u003d 1 - 3/2 x 1 - 1/2 x 2 + 2 x 3

x 4 \u003d 3 + 8 x 1 + 3 x 2 - 12 x 3

x 5 \u003d 4 + 2 x 1 + x 2 - 6 x 3

\u003d 6 + 25/2 x 1 + 7/2 x 2 - 19 x 3

मुक्त चर के लिए शून्य मान निर्दिष्ट करें, अर्थात x 1 \u003d x 2 \u003d x 3 \u003d 0, जबकि x 6 \u003d 1, x 4 \u003d 3, x 5 \u003d 4, अर्थात तीसरा वैध समाधान (0; 0; 0; 3; 4; 1)। इस मामले में, 3 \u003d 6.

चर x 3 को ऋणात्मक गुणांक के साथ उद्देश्य फलन में शामिल किया गया है, इसलिए, शून्य के सापेक्ष x 3 में वृद्धि से F में कमी आएगी। दूसरे समीकरण से यह देखा जा सकता है कि x 3 1/ तक बढ़ सकता है। 4, तीसरे समीकरण से - 2/3 तक। दूसरा समीकरण अधिक महत्वपूर्ण है। हम चर x 3 को मूल की संख्या में, x 4 को मुक्त की संख्या में अनुवाद करते हैं।

अब हम x 1, x 2 और x 4 को नए मुक्त चर के रूप में लेते हैं। आइए नए बुनियादी चर x 3 , x 5 , x 6 को उनके पदों में व्यक्त करें। आइए सिस्टम प्राप्त करें

x 3 \u003d 1/4 + 2/3 x 1 + 1/4 x 2 - 1/12 x 4

x 5 \u003d 5/2 - 2 x 1 - 1/2 x 2 + 1/2 x 4

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

उद्देश्य समारोह रूप लेगा

\u003d 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

चर x 1 और x 2 ऋणात्मक गुणांक वाले उद्देश्य फलन में शामिल हैं, इसलिए, उनके मूल्यों में वृद्धि के साथ, का मान घट जाएगा। उदाहरण के लिए, x 2 लें। सिस्टम के दूसरे समीकरण से, यह देखा जा सकता है कि x 2 के मान में x 2 \u003d 5 (जब तक x 5 0) तक वृद्धि संभव है। इस स्थिति में, x 1 और x 4 शून्य मान बनाए रखते हैं, अन्य चर के मान x 3 = 3/2 के बराबर होते हैं; x 5 \u003d 0, x 6 \u003d 3/2, यानी चौथा वैध समाधान (0; 5; 3/2; 0; 0; 3/2)। इस मामले में, 4 \u003d 5/4।

अब हम x 1, x 4 और x 5 को नए मुक्त चर के रूप में लेते हैं। आइए नए बुनियादी चर x 2 , x 3 , x 6 को उनके पदों में व्यक्त करें। आइए सिस्टम प्राप्त करें

x 2 \u003d 5 - 4 x 1 + x 4 - 2 x 5

x 3 \u003d 3/2 - 1/3 x 1 + 1/6 x 4 - 1/2 x 5

x 6 \u003d 3/2 - 1/6 x 1 - 1/6 x 4

उद्देश्य समारोह रूप लेगा

एफ \u003d - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

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

अर्थात् min = - 5 का न्यूनतम मान, अंतिम व्यवहार्य हल (0; 5; 3/2; 0; 0; 3/2) इष्टतम है।

विकल्प 8. उद्देश्य फलन को अधिकतम कीजिए = 4 x 5 + 2 x 6

प्रतिबंधों के साथ: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 \u003d 30;

x 3 + x 5 - 2 x 6 \u003d 6;

2 x 4 + 3 x 5 - 2 x 6 \u003d 18;

समाधान:

समीकरणों की संख्या 4 है, अज्ञात की संख्या 6 है। इसलिए, r = n - m = 6 - 4 = 2 चर को मुक्त, 4 चर को मूल के रूप में चुना जा सकता है। हम x 5 और x 6 को फ्री वाले, x 1, x 2, x 3, x 4 को बेसिक वाले के रूप में चुनते हैं। हम मूल चरों को मुक्त चरों के रूप में व्यक्त करते हैं और समीकरणों के निकाय को इकाई के आधार पर घटाते हैं

एक्स 1 \u003d 12 - एक्स 5 - एक्स 6;

x 2 \u003d 30 - 5 x 5 + x 6;

x 3 \u003d 6 - x 5 + 2 x 6;

x 4 \u003d 9 - 3/2 x 5 + x 6;

हम उद्देश्य फलन को = 4 x 5 + 2 x 6 के रूप में लिखते हैं। मुक्त चर के लिए शून्य मान x 5 = x 6 = 0 असाइन करें। इस मामले में, मूल चर x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9 मानों पर ले जाएगा, अर्थात्, हम पहला संभव हल (12, 30, 6, 9, 0,) और 1 = 0 प्राप्त करेंगे।

दोनों मुक्त चर सकारात्मक गुणांक के साथ लक्ष्य फ़ंक्शन में प्रवेश करते हैं, अर्थात, F में और वृद्धि संभव है। आइए अनुवाद करें, उदाहरण के लिए, x 6 मूल की संख्या में। समीकरण (1) दर्शाता है कि x 1 = 0 x 5 = 12 पर, (2) ÷ (4) x 6 में धनात्मक गुणांक के साथ प्रवेश करता है। आइए एक नए आधार पर चलते हैं: मूल चर - x 6, x 2, x 3, x 4, मुक्त - x 1, x 5. आइए नए मूल चरों को नए मुक्त के माध्यम से व्यक्त करें।

एक्स 6 \u003d 12 - एक्स 1 - एक्स 5;

x 2 \u003d 42 - x 1 - 6 x 5;

x 3 \u003d 30 - 2 x 1 - 3 x 5;

x 4 \u003d 21 - x 1 - 5/2 x 5;

उद्देश्य फलन Ф = 24 - 2 x 1 + 2 x 5 का रूप लेगा;

मुक्त चर x 1 = x 5 = 0 के लिए शून्य मान निर्दिष्ट करें। इस मामले में, मूल चर x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21 मानों पर ले जाएगा, अर्थात्, हम दूसरा व्यवहार्य हल (0, 42, 30, 21, 0, 12) और 2 = 24 प्राप्त करेंगे।

लक्ष्य फ़ंक्शन x 5 एक सकारात्मक गुणांक के साथ प्रवेश करता है, अर्थात, F में और वृद्धि संभव है। आइए एक नए आधार पर चलते हैं: मूल चर - x 6, x 5, x 3, x 4, मुक्त वाले - x 1 , x 2. आइए नए मूल चरों को नए मुक्त के माध्यम से व्यक्त करें

x 6 \u003d 5 - 5/6 x 1 + 1/6 x 2;

x 5 \u003d 7 - 1/6 x 1 - 1/6 x 2;

x 3 \u003d 9 - 3/2 x 1 + 1/2 x 2;

x 4 \u003d 7/2 - 7/12 x 1 + 5/12 x 5;

उद्देश्य फलन = 38 - 7/2 x 1 - 1/3 x 2 का रूप लेगा;

मुक्त चर के लिए शून्य मान x 1 = x 2 = 0 असाइन करें। इस मामले में, मूल चर मान x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/ 2, अर्थात्, हमें तीसरा संभव हल X 3 = (0, 0, 9, 7/2, 7, 5) और 3 = 38 मिलेगा।

दोनों चर नकारात्मक गुणांक के साथ उद्देश्य फ़ंक्शन में प्रवेश करते हैं, अर्थात, Ф में और वृद्धि असंभव है।

इसलिए, अंतिम व्यवहार्य समाधान इष्टतम है, अर्थात ऑप्ट = (0, 0, 9, 7/2, 7, 5) और अधिकतम = 38।

विकल्प 10. उद्देश्य फ़ंक्शन को अधिकतम करें \u003d x 2 + x 3

प्रतिबंधों के तहत: x 1 - x 2 + x 3 \u003d 1,

x 2 - 2 x 3 + x 4 \u003d 2.

समाधान:

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

आइए x 2 और x 3 को मुक्त चर के रूप में लेते हैं। फिर चर x 1 और x 2 मूल चर होंगे, जिन्हें हम मुक्त के रूप में व्यक्त करेंगे।

एक्स 1 \u003d 1 + एक्स 2 - एक्स 3; (*)

एक्स 4 \u003d 2 - एक्स 2 + 2 एक्स 3;

लक्ष्य फलन पहले ही x 2 और x 3 के रूप में व्यक्त किया जा चुका है, अर्थात् = x 2 + x 3।

x 2 \u003d 0 और x 3 \u003d 0 पर, मूल चर x 1 \u003d 1, x 4 \u003d 2 के बराबर होंगे।

हमारे पास पहला संभव हल X 1 = (1, 0, 0, 2) है, जबकि 1 = 0 है।

वृद्धि के साथ Ф में वृद्धि संभव है, उदाहरण के लिए, x 3 के मान में, जो के लिए एक सकारात्मक गुणांक के साथ अभिव्यक्ति में शामिल है (x 2 शून्य के बराबर रहता है)। सिस्टम (*) के पहले समीकरण में यह देखा जा सकता है कि x 3 को 1 तक बढ़ाया जा सकता है (शर्त x 1 0 से), यानी यह समीकरण x 3 के मान को बढ़ाने पर प्रतिबंध लगाता है। सिस्टम का पहला समीकरण (*) हल कर रहा है। इस समीकरण के आधार पर, हम x 1 और x 3 स्थानों को बदलते हुए एक नए आधार पर जाते हैं। अब मूल चर x 3 और x 4, मुक्त - x 1 और x 2 होंगे। अब हम x 3 और x 4 को x 1 और x 2 के पदों में व्यक्त करते हैं।

हमें मिलता है: x 3 \u003d 1 - x 1 + x 2; (**)

x 4 \u003d 4 - 2 x 1 + x 2;

\u003d x 2 + 1 - x 1 + x 2 \u003d 1 - x 1 + 2 x 2

मुक्त चर को शून्य के बराबर करने पर, हमें दूसरा स्वीकार्य मूल समाधान X 2 = (0; 0; 1; 4) प्राप्त होता है, जिसमें 2 = 1 होता है।

F में वृद्धि x 2 में वृद्धि के साथ संभव है। समीकरणों की अंतिम प्रणाली (**) को देखते हुए x 2 में वृद्धि सीमित नहीं है। इसलिए, Ф सभी बड़े धनात्मक मानों को ग्रहण करेगा, अर्थात् अधिकतम = + ।

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

कार्य 2.डी. दिए गए प्रश्न का दोहरा प्रश्न लिखिए।

मूल कार्य।

विकल्प 7. उद्देश्य फलन को अधिकतम कीजिए = 2× एक्स 1 - एक्स 4

प्रतिबंधों के साथ: x 1 + x 2 \u003d 20,

एक्स 2 + 2× एक्स 4 5,

एक्स 1 + एक्स 2 + एक्स 3 ≤ 8,

x मैं 0 (i = 1, 2, 3, 4)

समाधान:

हम बाधाओं की प्रणाली को एक में लाते हैं, उदाहरण के लिए, दूसरे और तीसरे समीकरणों में अतिरिक्त चर पेश करके विहित रूप

एक्स 1 + एक्स 2 = 20,

एक्स 2 + 2 × एक्स 4 - एक्स 5 \u003d 5,

- एक्स 1 + एक्स 2 + एक्स 3 + एक्स 6 \u003d 8.

हमें दूसरे प्रकार की असममित समस्या मिली। दोहरी समस्या इस तरह दिखेगी:

उद्देश्य फलन कम से कम करें F = 20 × वाई 1 + 5 × वाई 2 + 8 × वाई 3

वाई 1 - वाई 3 . के लिए ≥ 2,

y1 + y2 + y3 ≥ 0,

वाई 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

वाई 3 ≥ 0.

विकल्प 8. उद्देश्य फ़ंक्शन को अधिकतम करें \u003d x 2 - x 4 - 3× एक्स 5

प्रतिबंधों के साथ: x 1 + 2× x 2 - x 4 + x 5 \u003d 1,

— 4 × एक्स 2 + एक्स 3 + 2× एक्स 4 - एक्स 5 = 2,

3 × एक्स 2 + एक्स 5 + एक्स 6 = 5,

एक्स मैं ≥ 0, (मैं = 1, 6)

समाधान:

समीकरणों के रूप में बाधाओं की एक प्रणाली के साथ हमारे पास मूल अधिकतमकरण समस्या है, यानी, दोहरी समस्याओं की एक जोड़ी में दूसरे प्रकार का असममित रूप होता है, जिसका गणितीय मॉडल मैट्रिक्स रूप में होता है:

प्रारंभिक समस्या: दोहरी समस्या:

एफ = सी × एक्स अधिकतम एफ = बी टी × यमिन

ए पर × एक्स \u003d बी और ए टी × वाई सी टी

मूल समस्या में, उद्देश्य फलन में चरों के गुणांकों की मैट्रिक्स-पंक्ति का रूप = (0; 1; 0; -1; -3; 0) है।

मुक्त शर्तों के स्तंभ मैट्रिक्स और बाधा प्रणाली में चर के लिए गुणांक के मैट्रिक्स का रूप है

बी \u003d 2, ए \u003d 0 - 4 1 2 -1 0

गुणांक के ट्रांसपोज़्ड मैट्रिक्स का पता लगाएं, उद्देश्य फ़ंक्शन में चर के लिए गुणांक की मैट्रिक्स-पंक्ति, और मुक्त सदस्यों के मैट्रिक्स-कॉलम का पता लगाएं

0 1 0 0 वी टी \u003d (1; 2; 5)

ए टी = -1 2 0 सी टी = -1

दोहरी समस्या को निम्नलिखित रूप में लिखा जा सकता है:

उद्देश्य फलन का न्यूनतम मान ज्ञात कीजिए F = y 1 + 2 × वाई 2 + 5 × वाई 3

प्रतिबंधों के तहत y 1 0,

2× वाई 1-4 × वाई 2 + 3 × वाई 3 1,

- वाई 1 + 2 × वाई 2 -1,

वाई 1 - वाई 2 + वाई 3 ≥ -3,

विकल्प 10. फलन को छोटा कीजिए = x 1 + x 2 + x 3

सीमित: 3× एक्स 1 + 9× एक्स 2 + 7× एक्स 3 2,

6 × एक्स 1 + 4 एक्स 2 + 5× एक्स 3 3,

8 × एक्स 1 + 2 एक्स 2 + 4× एक्स 3 4,

समाधान:

असमानताओं के रूप में बाधाओं की एक प्रणाली के साथ हमारे पास मूल न्यूनीकरण समस्या है, अर्थात, दोहरी समस्याओं की एक जोड़ी में तीसरे प्रकार का एक सममित रूप होता है, जिसका गणितीय मॉडल मैट्रिक्स रूप में होता है:

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

एफ = सी × एक्स मिनट एफ \u003d बी टी × यमैक्स

ए पर × एक्स ≥ ए टी पर बी × यू ≤ सी टी

एक्स 0 वाई ≥ 0

मूल समस्या में, उद्देश्य फ़ंक्शन में चर के लिए गुणांक की मैट्रिक्स-पंक्ति, मुक्त शर्तों के मैट्रिक्स-स्तंभ, और बाधा प्रणाली में चर के लिए गुणांक के मैट्रिक्स का रूप है

सी \u003d (1; 1; 1), बी \u003d 3, ए \u003d 6 4 5

आइए हम द्वैत समस्या के आव्यूह ज्ञात करें

बी टी = (2; 3; 4) सी टी = 3 ए टी = 9 4 2

दोहरी समस्या इस प्रकार तैयार की गई है:

उद्देश्य फलन को अधिकतम कीजिए F = 2y 1 + 3y 2 + 4y 3

प्रतिबंधों के तहत 3 × वाई 1 + 6 × वाई 2 + 8 × वाई 3 1,

9× वाई 1 + 4 × वाई 2 + 2 × वाई 3 1,

7× वाई 1 + 5 × वाई 2 + 4 × वाई 3 1,

वाई मैं ≥ 0 (i = 1, 2, 3)

कार्य 2.सी. सिंप्लेक्स टेबल का उपयोग करके एक रैखिक प्रोग्रामिंग समस्या को हल करना।

विकल्प 7. उद्देश्य फलन को अधिकतम कीजिए = 2 x 1 - x 2 + 3 x 3 + 2 x 4

प्रतिबंधों के तहत: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

समाधान:

हम बाधाओं की प्रणाली को विहित रूप में कम करते हैं

2 x 1 + 3 x 2 - x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

हमारे पास 7 अज्ञात के साथ 3 समीकरणों की एक प्रणाली है। हम x 1 , z 1 , z 3 को मूल 3 चर के रूप में चुनते हैं, x 2 , x 3 , x 4 , z 2 को मुक्त के रूप में चुनते हैं, हम उनके माध्यम से मूल चर व्यक्त करते हैं।

(2) से हमें प्राप्त होता है x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

(1) और (3) में प्रतिस्थापित करने पर, हमें प्राप्त होता है

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 \u003d 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

- 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 \u003d 2.

एक सिंप्लेक्स टेबल बनाएं

मैं पुनरावृति तालिका 1

बुनियादी एसी	स्वतंत्रता। एसी
एक्स 1	1	1	— 2	5	— 3	0	— 1	0		3/8
जेड 1	2	0	7	-11		1	2	0	1/ 4	1/8
जेड 3	4	0	18	-17	13	0	4	1	4/13	13/8
एफ	2	0	— 3	7	— 8	0	— 2	0		1

एक्स 1 \u003d (1; 0; 0; 0; 2; 0; 4) एफ 1 \u003d 2.

द्वितीय पुनरावृत्ति तालिका 2

एक्स 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
जेड 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
एफ	4	0	4	— 4	0	1	0	0		32/7

एक्स 2 \u003d (14/8; 0; 0; 1/4; 0; 0; 4) 2 \u003d 4.

III पुनरावृत्ति तालिका 3

एक्स 1	1	1	— 6	0	0		-1	— 1		1/2
x4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
एक्स 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
एफ	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

एक्स 3 \u003d (1; 0; 6/7; 10/7; 0; 0; 0) 3 \u003d 52/7।

चतुर्थ पुनरावृत्ति तालिका 4

जेड 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
एक्स 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
एफ	149/14	45/14	15	0	0	0	3/14	19/14

एक्स 4 \u003d (0; 0; 25/14; 37/14; 1/2; 0; 0) एफ 4 \u003d 149/14।

अंतिम तालिका की अनुक्रमणिका पंक्ति में कोई ऋणात्मक संख्या नहीं है, अर्थात उद्देश्य फलन के व्यंजक में, सभी i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

उत्तर: अधिकतम = 149/14,

इष्टतम समाधान (0; 0; 25/14; 37/14; 1/2; 0; 0)

विकल्प 8. उद्देश्य फलन को छोटा करें = 5 x 1 - x 3

प्रतिबंधों के तहत: x 1 + x 2 + 2 x 3 - x 4 \u003d 3,

एक्स 2 + 2 एक्स 4 \u003d 1,

समाधान:

चर की संख्या 4 है, मैट्रिक्स की रैंक 2 है, इसलिए मुक्त चर की संख्या r \u003d 4 - 2 \u003d 2 है, मूल चर की संख्या भी 2 है। हम x 3 लेते हैं, x 4 मुक्त चर के रूप में, हम मूल चर x 1, x 2 को मुफ्त में व्यक्त करेंगे और हम प्रणाली को इकाई के आधार पर लाएंगे:

एक्स 2 \u003d 1 - 2 एक्स 4,

x 1 \u003d 3 - x 2 - 2 x 3 + x 4 \u003d 3 - 1 + 2 x 4 - 2 x 3 + x 4 \u003d 2 - 2 x 3 + 3 x 4

\u003d 5 x 1 - x 3 \u003d 5 (2 - 2 x 3 + 3 x 4) - x 3 \u003d 10 - 10 x 3 + 15 x 4 - x 3 \u003d 10 - 11 x 3 + 15 x 4

हम समीकरणों के निकाय और उद्देश्य फलन को सरल सारणी के लिए सुविधाजनक रूप में लिखते हैं, अर्थात् x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

+ 11 x 3 - 15 x 4 \u003d 10

आइए एक टेबल बनाएं

मैं पुनरावृति तालिका 1

बुनियादी एसी	स्वतंत्रता। एसी
x1	2	1	0		— 3		1/2
x2	1	0	1	0	2
एफ	10	0	0	11	— 15		— 11/2

एक्स 1 \u003d (2; 1; 0; 0) एफ 1 \u003d 10.

द्वितीय पुनरावृत्ति तालिका 2

x3	1	1/2	0	1	-3/2		3/4
x2	1	0	1	0			1/2
एफ	— 1	— 11/2	0	0	3/2		— 3/4

एक्स 2 \u003d (0; 1; 1; 0) एफ 2 \u003d -1।

III पुनरावृत्ति तालिका 3

x3	7/4	1/2	3/4	1	0
x4	1/2	0	1/2	0	1
एफ	— 7/4	— 11/2	— 3/4	0	0

एक्स 3 \u003d (0; 0; 7/4; 1/2) एफ 3 \u003d -7/4।

अंतिम तालिका की अनुक्रमणिका पंक्ति में कोई धनात्मक संख्या नहीं है, अर्थात उद्देश्य फलन के व्यंजक में, सभी i > 0. हमारे पास केस I है, इसलिए, अंतिम मूल समाधान इष्टतम है।

उत्तर: मिनट = -7/4, इष्टतम समाधान (0; 0; 7/4; 1/2)

********************

विकल्प 10. उद्देश्य फ़ंक्शन को छोटा करें \u003d x 1 + x 2,

प्रतिबंधों के साथ: x 1 -2 x 3 + x 4 \u003d 2,

x 2 - x 3 + 2 x 4 \u003d 1,

समाधान:

चर की संख्या 5 है, मैट्रिक्स की रैंक 3 है, इसलिए मुक्त चर की संख्या r \u003d 6-3 \u003d 2 है। हम x 3 और x 4 को मुक्त चर के रूप में लेते हैं, x 1, x 2, x 5 मूल के रूप में। सिस्टम के सभी समीकरणों को पहले ही एक आधार पर कम कर दिया गया है (मूल चर मुक्त चर के रूप में व्यक्त किए जाते हैं), लेकिन वे एक ऐसे रूप में लिखे गए हैं जो सरल तालिकाओं का उपयोग करने के लिए सुविधाजनक नहीं है। हम समीकरणों की प्रणाली को रूप में लिखते हैं

एक्स 1 - 2 एक्स 3 + एक्स 4 \u003d 2

x 2 - x 3 +2 x 4 \u003d 1

एक्स 5 + एक्स 3 - एक्स 4। = 5

हम उद्देश्य फलन को मुक्त चरों के रूप में व्यक्त करते हैं और इसे - 3 x 3 +3 x 4 = 3 के रूप में लिखते हैं।

आइए एक टेबल बनाएं

मैं पुनरावृति तालिका 1

बुनियादी एसी	स्वतंत्रता। एसी
एक्स 1	2	1	0	-2	1	0	2	-1/2
एक्स 2	1	0	1	-1		0	1/2	1/2
एक्स 5	5	0	0	1	-1	1		1/2
एफ	3	0	0	-3	3	0		-3/2

एक्स 1 \u003d (2; 3; 0; 0; 5) एफ 1 \u003d 3.

तालिका 2

एक्स 1	3/2	1	-1/2	-3/2	0	0
एक्स 4	1/2	0	1/2	-1/2	1	0
एक्स 5	11/2	0	1/2	1/2	0	1
एफ	3/2	0	-3/2	-3/2	0	0

एक्स 2 \u003d (3/2; 0; 0; 1/2; 11/2) एफ 2 \u003d 3/2।

अंतिम तालिका की अनुक्रमणिका पंक्ति में कोई धनात्मक संख्या नहीं है, अर्थात, उद्देश्य फलन के व्यंजक में, सभी i > 0. हमारे पास केस 1 है, इसलिए, अंतिम मूल समाधान इष्टतम है।

उत्तर: मिनट = 3/2, इष्टतम समाधान है (3/2; 0; 0; 1/2; 11/2)।

परिचय

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

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

1. समस्या का विवरण

न्यूनतम उद्देश्य समारोह

कार्य के विकल्प संख्या 16 के अनुसार निर्णय बहुभुज द्वारा निर्दिष्ट बाधाओं की प्रणाली के लिए न्यूनतम उद्देश्य फ़ंक्शन खोजने की समस्या को हल करें। निर्णय बहुभुज चित्र 1 में दिखाया गया है:

चित्र 1 - समस्या समाधान का बहुभुज

बाधाओं की प्रणाली और समस्या का उद्देश्य कार्य नीचे प्रस्तुत किया गया है:

निम्नलिखित विधियों का उपयोग करके समस्या को हल करना आवश्यक है:

एलपी समस्याओं को हल करने के लिए ग्राफिकल विधि;

एलपी समस्याओं को हल करने के लिए बीजगणितीय विधि;

एलपी समस्याओं को हल करने के लिए सरल विधि;

एलपी समस्याओं का एक व्यवहार्य समाधान खोजने की विधि;

दोहरी एलपी समस्या का समाधान;

पूर्णांक एलपी समस्याओं को हल करने के लिए "शाखाओं और सीमाओं" की विधि;

पूर्णांक एलपी समस्याओं को हल करने के लिए गोमोरी की विधि;

बूलियन एलपी समस्याओं को हल करने के लिए बलाश विधि।

कार्य पर उपयुक्त निष्कर्ष निकालने के लिए विभिन्न विधियों द्वारा समाधान के परिणामों की तुलना करें।

2. ग्राफिक समाधानरैखिक प्रोग्रामिंग समस्याएं

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

चावल। 2 एलपी समस्या का चित्रमय समाधान

अंतिम बिंदू

दो बिंदुओं A1 और A2 से गुजरने वाली एक सीधी रेखा का समीकरण:

एबी: (0;1); (3;3)

सूर्य: (3;3); (4;1)

सीडी: (4;1); (3;0)

ईए: (1;0); (0;1)

सीएफ: (0;1); (5;2)

प्रतिबंधों के साथ:

बीजीय सिंप्लेक्स विधि द्वारा एक रैखिक प्रोग्रामिंग समस्या को हल करना

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

असमानताओं को इस तरह बदलें कि चर और मुक्त सदस्य बाईं ओर हों, और 0 दाईं ओर, अर्थात। कि बाईं ओर शून्य से बड़ा या उसके बराबर हो;

अतिरिक्त चर का परिचय दें, जिनकी संख्या प्रतिबंधों की प्रणाली में असमानताओं की संख्या के बराबर है;

जोड़े गए चरों की गैर-नकारात्मकता पर अतिरिक्त प्रतिबंधों का परिचय, असमानता के संकेतों को सख्त समान संकेतों से बदलें।

एलपी समस्या को हल करते समय बीजीय विधिएक शर्त जोड़ी जाती है: उद्देश्य फ़ंक्शन न्यूनतम होना चाहिए। यदि यह शर्त पूरी नहीं होती है, तो उद्देश्य फ़ंक्शन को उचित रूप से बदलना (-1 से गुणा करना) और न्यूनतम समस्या को हल करना आवश्यक है। समाधान मिलने के बाद, मूल फ़ंक्शन में चर के मूल्यों को प्रतिस्थापित करें और इसके मूल्य की गणना करें।

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

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

मुक्त चर

सेंट लेन - जोड़ें। किट

गैर-नकारात्मकता की स्थिति संतुष्ट है, इसलिए, इष्टतम समाधान पाया जाता है।

3. एक सिंप्लेक्स तालिका का उपयोग करके एक रैखिक प्रोग्रामिंग समस्या को हल करना

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

हम सिस्टम के सभी समीकरणों को फॉर्म में कम करते हैं:

हम एक सिंप्लेक्स टेबल बनाते हैं:

तालिका के प्रत्येक सेल के ऊपरी कोने में हम समीकरणों की प्रणाली से गुणांक दर्ज करते हैं;

हम पंक्ति एफ में अधिकतम सकारात्मक तत्व का चयन करते हैं, इसके अलावा सामान्य कॉलम होगा;

सामान्य तत्व को खोजने के लिए, हम सभी सकारात्मक लोगों के लिए संबंध बनाते हैं। 3/3; 9/1;- लाइन x3 में न्यूनतम अनुपात। इसलिए - सामान्य स्ट्रिंग और =3 - सामान्य तत्व।

हम पाते हैं = 1/=1/3। हम सेल के निचले कोने में लाते हैं, जहां सामान्य तत्व स्थित होता है;

सामान्य रेखा के सभी अधूरे निचले कोनों में, हम सेल के ऊपरी कोने में मूल्य के उत्पाद को दर्ज करते हैं;

सामान्य रेखा के ऊपरी कोनों का चयन करें;

सामान्य कॉलम के सभी निचले कोनों में हम ऊपरी कोने में मूल्य के उत्पाद को दर्ज करते हैं - और परिणामी मूल्यों का चयन करते हैं;

तालिका की शेष कोशिकाओं को संबंधित चयनित तत्वों के उत्पादों के रूप में भरा जाता है;

फिर हम एक नई तालिका बनाते हैं जिसमें सामान्य स्तंभ और पंक्ति के तत्वों की कोशिकाओं के पदनाम उलट जाते हैं (x2 और x3);

पूर्व सामान्य पंक्ति और स्तंभ के ऊपरी कोने में, जो मान पहले निचले कोने में थे, वे लिखे गए हैं;

पिछली तालिका में इन कोशिकाओं के ऊपरी और निचले कोनों के मूल्यों का योग शेष कोशिकाओं के ऊपरी कोने में लिखा गया है

4. एक व्यवहार्य समाधान ढूंढकर रैखिक प्रोग्रामिंग समस्या को हल करना

मान लीजिए कि रैखिक बीजीय समीकरणों की एक प्रणाली दी गई है:

हम मान सकते हैं कि सब कुछ, अन्यथा हम संबंधित समीकरण को -1 से गुणा करते हैं।

हम सहायक चर पेश करते हैं:

हम एक सहायक फ़ंक्शन भी पेश करते हैं

हम सिस्टम को बाधाओं (2) और शर्तों के तहत कम से कम करेंगे।

एक व्यवहार्य समाधान खोजने के लिए नियम: प्रणाली (1) के लिए एक व्यवहार्य समाधान खोजने के लिए, हम बाधाओं (2) के तहत फॉर्म (3) को कम करते हैं, मुक्त अज्ञात के रूप में हम xj को मूल के रूप में लेते हैं।

सरल विधि द्वारा किसी समस्या को हल करते समय, दो स्थितियाँ उत्पन्न हो सकती हैं:

न्यूनतम एफ = 0, तो सभी मैं शून्य के बराबर होना चाहिए। और परिणामी मान xj सिस्टम (1) के लिए एक व्यवहार्य समाधान होगा।

न्यूनतम एफ> 0, यानी। मूल प्रणाली में एक व्यवहार्य समाधान नहीं है।

स्रोत प्रणाली:

पिछले विषय की समस्या की स्थिति का उपयोग किया जाता है।

आइए अतिरिक्त चर जोड़ें:

मूल समस्या का एक स्वीकार्य समाधान पाया जाता है: x1 = 3, x2 = 3, F = -12। प्राप्त व्यवहार्य समाधान के आधार पर, हम सरल विधि का उपयोग करके मूल समस्या का इष्टतम समाधान ढूंढते हैं। ऐसा करने के लिए, हम सहायक कार्य के लक्ष्य फ़ंक्शन के साथ पंक्ति और पंक्ति को हटाकर ऊपर प्राप्त तालिका से एक नई सरल तालिका बनाएंगे:

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

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

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

प्रतिबंधों के साथ:

समाधान: हम प्रतिबंधों की प्रणाली को मानक रूप में लाते हैं:

इसके लिए दोहरा कार्य इस तरह दिखेगा:

सिम्प्लेक्स विधि से दोहरी समस्या का समाधान होगा।

आइए हम उद्देश्य फलन को रूपांतरित करें ताकि न्यूनीकरण की समस्या का समाधान हो और सिंप्लेक्स विधि द्वारा हल करने के लिए मानक रूप में बाधाओं की प्रणाली को लिखें।

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

= 0 - (3y1 + 9y2 + 3y3 + y4) ??मिनट

आइए हम दोहरी एलपी समस्या को हल करने के लिए प्रारंभिक सिम्प्लेक्स झांकी का निर्माण करें।

सिंप्लेक्स विधि का दूसरा चरण

तो, सिम्प्लेक्स विधि के तीसरे चरण में, निम्न परिणामों के साथ न्यूनतम समस्या का इष्टतम समाधान पाया गया: y2 = -7 / 8, y1 = -11/8, Ф = 12. का मान ज्ञात करने के लिए दोहरी समस्या का उद्देश्य कार्य, हम मूल और मुक्त चर के पाए गए मानों को अधिकतमकरण फ़ंक्शन में प्रतिस्थापित करते हैं:

अधिकतम = - Фमिनट = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

चूँकि प्रत्यक्ष और द्वैत समस्याओं के वस्तुनिष्ठ फलन का मान समान होता है, प्रत्यक्ष समस्या का समाधान मिल जाता है और 12 के बराबर होता है।

एफमिन \u003d एफएमएक्स \u003d -12

7. "शाखाओं और सीमा" विधि का उपयोग करके पूर्णांक रैखिक प्रोग्रामिंग की समस्या को हल करना

आइए हम मूल समस्या को इस तरह से रूपांतरित करें कि पारंपरिक तरीकों से हल करते समय पूर्णांक की स्थिति संतुष्ट न हो।

पूर्णांक प्रोग्रामिंग समस्या के समाधान का प्रारंभिक बहुभुज।

आइए हम रूपांतरित समाधान बहुभुज के लिए बाधाओं की एक नई प्रणाली का निर्माण करें।

बीजगणितीय विधि द्वारा हल करने के लिए हम बाधाओं की प्रणाली को समानता के रूप में लिखते हैं।

समाधान के परिणामस्वरूप, इष्टतम कार्य योजना मिली: x1 = 9/4, x2 = 5/2, F = -41/4। यह समाधान समस्या में निर्धारित समग्रता शर्त को पूरा नहीं करता है। हम मूल समाधान बहुभुज को दो क्षेत्रों में विभाजित करते हैं, इसमें से क्षेत्र 3 को छोड़कर

समस्या समाधान का परिवर्तित बहुभुज

आइए हम समाधान बहुभुज के गठित क्षेत्रों के लिए प्रतिबंधों की नई प्रणालियों की रचना करें। बायां क्षेत्र एक चतुर्भुज (ट्रेपेज़ॉइड) है। समाधान बहुभुज के बाएं क्षेत्र के लिए बाधा प्रणाली नीचे प्रस्तुत की गई है।

वाम क्षेत्र के लिए प्रतिबंध प्रणाली

दायां क्षेत्र बिंदु C को दर्शाता है।

सही निर्णय क्षेत्र के लिए बाधाओं की प्रणाली नीचे प्रस्तुत की गई है।

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

समाधान के परिणामस्वरूप, इष्टतम कार्य योजना मिली: x1 = 3, x2 = 3, F = -12। यह योजना समस्या में पूर्णांक चर की स्थिति को संतुष्ट करती है और इसे मूल पूर्णांक रैखिक प्रोग्रामिंग समस्या के लिए इष्टतम संदर्भ योजना के रूप में लिया जा सकता है। सही समाधान क्षेत्र के लिए समाधान निकालने का कोई मतलब नहीं है। नीचे दिया गया चित्र एक पूर्णांक रैखिक प्रोग्रामिंग समस्या को एक वृक्ष के रूप में हल करने की प्रगति को दर्शाता है।

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

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

सिस्टम (1) का एक पूर्णांक समाधान खोजना आवश्यक है जो उद्देश्य फ़ंक्शन F को कम करता है, और सभी गुणांक पूर्णांक होते हैं।

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

1) सिम्प्लेक्स विधि का उपयोग करके समस्या का समाधान (1), (2) निर्धारित किया जाता है, जिसके लिए समाधान के पूर्णांक होने की आवश्यकता को हटा दिया जाता है; यदि हल पूर्णांक हो जाता है, तो पूर्णांक समस्या का वांछित समाधान भी मिल जाएगा;

2) अन्यथा, यदि कुछ निर्देशांक एक पूर्णांक नहीं है, तो समस्या का प्राप्त समाधान एक पूर्णांक समाधान (एक स्वीकार्य पॉलीहेड्रॉन में पूर्णांक बिंदुओं की उपस्थिति) के अस्तित्व की संभावना के लिए जांचा जाता है:

यदि एक भिन्नात्मक मुक्त सदस्य के साथ किसी भी पंक्ति में, अन्य सभी गुणांक पूर्णांक बन जाते हैं, तो एक स्वीकार्य पॉलीहेड्रॉन में कोई पूर्णांक, अंक नहीं होते हैं, और पूर्णांक प्रोग्रामिंग की समस्या का कोई समाधान नहीं होता है;

अन्यथा, एक अतिरिक्त रैखिक बाधा पेश की जाती है, जो स्वीकार्य पॉलीहेड्रॉन से एक ऐसे हिस्से को काट देती है जो पूर्णांक प्रोग्रामिंग समस्या का समाधान खोजने के लिए अप्रमाणिक है;

3) एक अतिरिक्त रैखिक बाधा बनाने के लिए, एक भिन्नात्मक मुक्त सदस्य के साथ एल-वें पंक्ति का चयन करें और अतिरिक्त बाधा लिखें

जहां और हैं, क्रमशः, गुणांक के भिन्नात्मक भाग और मुक्त

सदस्य। आइए हम एक सहायक चर को बाधा (3) में पेश करें:

आइए हम गुणांक निर्धारित करें और बाधा (4) में शामिल करें:

जहां और क्रमशः और के लिए निकटतम निम्न पूर्णांक हैं।

गोमोरी ने साबित किया कि ऐसे चरणों की एक सीमित संख्या एक रैखिक प्रोग्रामिंग समस्या की ओर ले जाती है जिसका समाधान पूर्णांक है और इसलिए वांछित है।

समाधान: हम रैखिक बाधाओं की प्रणाली और लक्ष्य फ़ंक्शन को विहित रूप में कम करते हैं:

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

बलाश विधि द्वारा बूलियन एलपी समस्याओं को हल करना।

निम्नलिखित नियमों को ध्यान में रखते हुए, बूलियन चर के साथ पूर्णांक रैखिक प्रोग्रामिंग की समस्या के लिए स्वतंत्र रूप से एक संस्करण बनाएं: समस्या कम से कम 5 चर का उपयोग करती है, कम से कम 4 प्रतिबंध, प्रतिबंधों के गुणांक और उद्देश्य फ़ंक्शन को मनमाने ढंग से चुना जाता है, लेकिन ऐसे में एक तरीका है कि प्रतिबंधों की प्रणाली संगत है। कार्य बलाश एल्गोरिथम का उपयोग करके बूलियन चर के साथ ZCLP को हल करना और संपूर्ण खोज द्वारा समस्या को हल करने के संबंध में कम्प्यूटेशनल जटिलता में कमी का निर्धारण करना है।

प्रतिबंधों का निष्पादन

एफ मान

फ़िल्टर बाधा:

गणना कमी निर्धारण

संपूर्ण खोज विधि द्वारा समस्या का समाधान 6*25=192 परिकलित व्यंजक है। बालाश विधि द्वारा समस्या का समाधान 3*6+(25-3)=47 परिकलित व्यंजक है। संपूर्ण खोज विधि द्वारा समस्या को हल करने के संबंध में गणना की जटिलता में कुल कमी है।

निष्कर्ष

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

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

साहित्य:

1. ल्याशचेंको आई.एन. रैखिक और गैर-रेखीय प्रोग्रामिंग / I.N. Lyashchenko, E.A. करागोडोवा, N.V. चेर्निकोवा, N.Z. शोर। - के।: "हायर स्कूल", 1975, 372 पी।

2. शिक्षा के पूर्णकालिक और अंशकालिक रूपों के छात्रों के लिए "अनुप्रयुक्त गणित" अनुशासन में पाठ्यक्रम परियोजना के कार्यान्वयन के लिए दिशानिर्देश / द्वारा संकलित: I.A. Balakireva, A.V. Skatkov - सेवस्तोपोल: सेवएनटीयू पब्लिशिंग हाउस, 2003. - 15 पी।

3. अनुशासन "अनुप्रयुक्त गणित", खंड "वैश्विक खोज के तरीके और एक-आयामी न्यूनीकरण" / कॉम्प के अध्ययन के लिए दिशानिर्देश। ए.वी. स्काटकोव, आई.ए. बालाकिरेवा, एल.ए. लिटविनोवा - सेवस्तोपोल: सेवजीटीयू पब्लिशिंग हाउस, 2000. - 31 एस।

4. शिक्षा के पूर्णकालिक और पत्राचार रूपों के "कंप्यूटर सिस्टम और नेटवर्क" खंड "सॉल्विंग इंटीजर लीनियर प्रोग्रामिंग प्रॉब्लम्स" के छात्रों के लिए अनुशासन "एप्लाइड मैथमेटिक्स" के अध्ययन के लिए दिशानिर्देश / द्वारा संकलित: I.A. Balakireva, A.V. Skatkov - सेवस्तोपोल : सेवएनटीयू पब्लिशिंग हाउस, 2000. - 13 पी।

5. अकुलिच आई.एल. उदाहरणों और कार्यों में गणितीय प्रोग्रामिंग:

6. प्रक्रिया छात्र अर्थव्यवस्था के लिए भत्ता। विशेषज्ञ। विश्वविद्यालय।-एम .: उच्चतर। स्कूल, 1986.- 319s।, बीमार।

7. एंड्रोनोव एस.ए. इष्टतम डिजाइन विधियाँ: व्याख्यान पाठ / SPbGUAP। एसपीबी, 2001. 169 पी.: बीमार।

इसी तरह के दस्तावेज़

सरल विधि द्वारा रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एल्गोरिदम। एक रैखिक प्रोग्रामिंग समस्या के गणितीय मॉडल का निर्माण। एक्सेल में लीनियर प्रोग्रामिंग प्रॉब्लम सॉल्व करना। लाभ और इष्टतम उत्पादन योजना ढूँढना।

टर्म पेपर, जोड़ा गया 03/21/2012


ग्राफिकल समस्या समाधान। एक गणितीय मॉडल तैयार करना। उद्देश्य फ़ंक्शन का अधिकतम मूल्य निर्धारित करना। एक विहित रैखिक प्रोग्रामिंग समस्या के कृत्रिम आधार के साथ एक सरल विधि द्वारा समाधान। समाधान की इष्टतमता की जाँच करना।

परीक्षण, जोड़ा गया 04/05/2016


रैखिक प्रोग्रामिंग का सैद्धांतिक आधार। रैखिक प्रोग्रामिंग की समस्याएं, समाधान के तरीके। इष्टतम समाधान का विश्लेषण। एकल-सूचकांक रैखिक प्रोग्रामिंग समस्या का समाधान। समस्या का विवरण और डेटा प्रविष्टि। मॉडल निर्माण और समाधान कदम।

टर्म पेपर, जोड़ा गया 12/09/2008


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

टर्म पेपर, जोड़ा गया 10/31/2014


उद्यम के लाभ को अधिकतम करने के लिए गणितीय मॉडल का निर्माण, समस्या का एक चित्रमय समाधान। सॉल्वर ऐड-ऑन का उपयोग करके समस्या का समाधान। संसाधन भंडार में परिवर्तन का विश्लेषण। उद्देश्य फलन के गुणांकों में परिवर्तन की सीमा का निर्धारण।

टर्म पेपर, जोड़ा गया 12/17/2014


गणितीय प्रोग्रामिंग। रैखिक प्रोग्रामिंग। रैखिक प्रोग्रामिंग की समस्याएं। एक रैखिक प्रोग्रामिंग समस्या को हल करने के लिए चित्रमय विधि। रैखिक प्रोग्रामिंग की समस्या का आर्थिक सूत्रीकरण। गणितीय मॉडल का निर्माण।

टर्म पेपर, 10/13/2008 जोड़ा गया


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

परीक्षण, जोड़ा गया 05/02/2012


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

परीक्षण, जोड़ा गया 04/11/2012


नॉनलाइनियर प्रोग्रामिंग की समस्या का विवरण। स्थिर बिंदुओं का निर्धारण और उनके प्रकार। स्तर रेखाओं का निर्माण, उद्देश्य फ़ंक्शन और प्रतिबंधों का त्रि-आयामी ग्राफ। समस्या का चित्रमय और विश्लेषणात्मक समाधान। उपयोगकर्ता पुस्तिका और एल्गोरिथम योजना।

टर्म पेपर, जोड़ा गया 12/17/2012


एक रैखिक प्रोग्रामिंग समस्या के समाधान का विश्लेषण। सिंप्लेक्स तालिकाओं का उपयोग करते हुए सिंप्लेक्स विधि। कंप्यूटर पर एलपी समस्याओं का मॉडलिंग और समाधान। समस्या के इष्टतम समाधान की आर्थिक व्याख्या। परिवहन समस्या का गणितीय सूत्रीकरण।

अनुशासन पर नियंत्रण कार्य:

"इष्टतम समाधान के तरीके"

विकल्प संख्या 8

1. एक ग्राफिकल विधि का उपयोग करके एक रैखिक प्रोग्रामिंग समस्या को हल करें। दिए गए प्रतिबंधों के तहत फलन का अधिकतम और न्यूनतम ज्ञात कीजिए:

,

.

समाधान

प्रतिबंधों की प्रणाली के तहत, उद्देश्य फ़ंक्शन का न्यूनतम मूल्य और अधिकतम खोजना आवश्यक है:

9x1 +3x2 30, (1)

एक्स 1 + एक्स 2 ≤4, (2)

एक्स 1 + एक्स 2 ≤8, (3)

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

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

आइए फ़ंक्शन F = 0: F = 2x 1 +3x 2 = 0 के मान के अनुरूप एक सीधी रेखा का निर्माण करें। उद्देश्य फ़ंक्शन के गुणांकों से बना ग्रेडिएंट वेक्टर F(X) के न्यूनतमकरण की दिशा को इंगित करता है। वेक्टर की शुरुआत बिंदु (0; 0) है, अंत बिंदु (2; 3) है। आइए इस रेखा को समानांतर रूप से आगे बढ़ाते हैं। चूंकि हम न्यूनतम समाधान में रुचि रखते हैं, इसलिए, हम निर्दिष्ट क्षेत्र के पहले स्पर्श तक सीधी रेखा को आगे बढ़ाते हैं। ग्राफ पर, यह रेखा एक बिंदीदार रेखा द्वारा इंगित की जाती है।

सीधा
क्षेत्र को बिंदु C पर प्रतिच्छेद करता है। चूँकि बिंदु C रेखाओं (4) और (1) के प्रतिच्छेदन के परिणामस्वरूप प्राप्त होता है, तो इसके निर्देशांक इन रेखाओं के समीकरणों को संतुष्ट करते हैं:
.

समीकरणों की प्रणाली को हल करने के बाद, हम प्राप्त करते हैं: x 1 = 3.3333, x 2 = 0।

हम उद्देश्य फलन का न्यूनतम मान कहाँ प्राप्त कर सकते हैं: .

समस्या के उद्देश्य कार्य पर विचार करें।

आइए फ़ंक्शन F = 0: F = 2x 1 +3x 2 = 0 के मान के अनुरूप एक सीधी रेखा का निर्माण करें। उद्देश्य फ़ंक्शन के गुणांकों से बना ग्रेडिएंट वेक्टर F(X) के अधिकतमकरण की दिशा को इंगित करता है। वेक्टर की शुरुआत बिंदु (0; 0) है, अंत बिंदु (2; 3) है। आइए इस रेखा को समानांतर रूप से आगे बढ़ाते हैं। चूंकि हम अधिकतम समाधान में रुचि रखते हैं, हम निर्दिष्ट क्षेत्र के अंतिम स्पर्श तक सीधी रेखा को आगे बढ़ाते हैं। ग्राफ पर, यह रेखा एक बिंदीदार रेखा द्वारा इंगित की जाती है।

सीधा
क्षेत्र को बिंदु B पर प्रतिच्छेद करता है। चूँकि बिंदु B, रेखाओं (2) और (3) के प्रतिच्छेदन के परिणामस्वरूप प्राप्त होता है, तो इसके निर्देशांक इन रेखाओं के समीकरणों को संतुष्ट करते हैं:

.

हम उद्देश्य फलन का अधिकतम मान कहाँ प्राप्त कर सकते हैं: .

उत्तर:
तथा
.

2 . सिंप्लेक्स विधि का उपयोग करके एक रैखिक प्रोग्रामिंग समस्या को हल करें:

.

समाधान

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

आइए हम उद्देश्य फ़ंक्शन का न्यूनतम मान निर्धारित करें
निम्नलिखित शर्तों के तहत-प्रतिबंध:
.

पहली संदर्भ योजना के निर्माण के लिए, हम अतिरिक्त चरों को पेश करके समीकरणों की प्रणाली में असमानताओं की प्रणाली को कम करते हैं।

अर्थ की पहली असमानता (≥) में, हम मूल चर का परिचय देते हैं एक्स 3 माइनस साइन के साथ। अर्थ की दूसरी असमानता (≤) में, हम मूल चर का परिचय देते हैं एक्स 4 . तीसरे अर्थ असमानता (≤) में, हम मूल चर x 5 का परिचय देते हैं।

आइए पेश करते हैं कृत्रिम चर : पहली समानता में हम एक चर का परिचय देते हैं एक्स 6 ;

कार्य को न्यूनतम निर्धारित करने के लिए, हम उद्देश्य फलन को इस प्रकार लिखते हैं: .

उद्देश्य समारोह में पेश किए गए कृत्रिम चर के उपयोग के लिए, एम का एक तथाकथित दंड लगाया जाता है, एक बहुत बड़ी सकारात्मक संख्या, जिसे आमतौर पर निर्दिष्ट नहीं किया जाता है।

परिणामी आधार को कृत्रिम कहा जाता है, और समाधान विधि को कृत्रिम आधार विधि कहा जाता है।

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

समीकरणों से हम कृत्रिम चर व्यक्त करते हैं: x 6 \u003d 4-x 1 -x 2 +x 3, जिसे हम उद्देश्य फ़ंक्शन में प्रतिस्थापित करते हैं: या।

गुणांक मैट्रिक्स
समीकरणों की इस प्रणाली का रूप है:
.

आइए बुनियादी चर के संबंध में समीकरणों की प्रणाली को हल करें: एक्स 6 , एक्स 4 , एक्स 5.

यह मानते हुए कि मुक्त चर 0 हैं, हमें पहली आधार रेखा मिलती है:

X1 = (0,0,0,2,10,4)

एक मूल समाधान को स्वीकार्य कहा जाता है यदि यह गैर-ऋणात्मक है।

		एक्स 1	एक्स 2	एक्स 3	एक्स 4	एक्स 5	एक्स 6
एक्स 6
एक्स 4
एक्स 5

वर्तमान आधार रेखा इष्टतम नहीं है क्योंकि सूचकांक पंक्ति में सकारात्मक गुणांक हैं। हम चर x 2 के संगत स्तंभ को अग्रणी के रूप में चुनेंगे, क्योंकि यह सबसे बड़ा गुणांक है। मूल्यों की गणना करें डी मैं और उनमें से सबसे छोटा चुनें: min(4:1 , 2:2 , 10:2) = 1.

इसलिए, दूसरी पंक्ति अग्रणी है।

हल करने वाला तत्व (2) के बराबर है और प्रमुख स्तंभ और अग्रणी पंक्ति के चौराहे पर स्थित है।

		एक्स 1	एक्स 2	एक्स 3	एक्स 4	एक्स 5	एक्स 6
एक्स 6
एक्स 4
एक्स 5

हम सिंप्लेक्स टेबल का अगला भाग बनाते हैं। x 4 चर के बजाय, x 2 चर योजना 1 में प्रवेश करेगा।

योजना 1 में चर x 2 के अनुरूप रेखा योजना 0 की रेखा x 4 के सभी तत्वों को सक्षम करने वाले तत्व RE=2 से विभाजित करके प्राप्त की जाती है। हल करने वाले तत्व के स्थान पर हमें 1 प्राप्त होता है। x 2 कॉलम के शेष कक्षों में हम शून्य लिखते हैं।

इस प्रकार, नई योजना में 1 पंक्ति x 2 और स्तंभ x 2 भरे गए हैं। नई योजना 1 के अन्य सभी तत्व, सूचकांक पंक्ति के तत्वों सहित, आयत नियम द्वारा निर्धारित किए जाते हैं।

		एक्स 1	एक्स 2	एक्स 3	एक्स 4	एक्स 5	एक्स 6
एक्स 6
एक्स 2
एक्स 5
		1 1/2 +1 1/2 एम

वर्तमान आधार रेखा इष्टतम नहीं है क्योंकि सूचकांक पंक्ति में सकारात्मक गुणांक हैं। हम चर x 1 के संगत कॉलम को अग्रणी के रूप में चुनेंगे, क्योंकि यह सबसे बड़ा गुणांक है। मूल्यों की गणना करें डी मैंपंक्तियों द्वारा विभाजन के भागफल के रूप में: और उनमें से हम सबसे छोटा चुनते हैं: मिनट (3: 1 1/2, -, 8: 2) = 2.

इसलिए, पहली पंक्ति अग्रणी है।

हल करने वाला तत्व (1 1 / 2) के बराबर है और प्रमुख स्तंभ और अग्रणी पंक्ति के चौराहे पर स्थित है।

		एक्स 1	एक्स 2	एक्स 3	एक्स 4	एक्स 5	एक्स 6
एक्स 6		1 1 / 2
एक्स 2
एक्स 5
		-1 1 / 2 +1 1 / 2 एम

हम सिंप्लेक्स टेबल का अगला भाग बनाते हैं। चर x 6 के बजाय, चर x 1 को योजना 2 में शामिल किया जाएगा।

हमें एक नई सिंप्लेक्स तालिका मिलती है:

		एक्स 1	एक्स 2	एक्स 3	एक्स 4	एक्स 5	एक्स 6
एक्स 1
एक्स 2
एक्स 5

कोई भी अनुक्रमणिका पंक्ति मान धनात्मक नहीं है। इसलिए, यह तालिका इष्टतम कार्य योजना निर्धारित करती है।

सिंप्लेक्स तालिका का अंतिम संस्करण:

		एक्स 1	एक्स 2	एक्स 3	एक्स 4	एक्स 5	एक्स 6
एक्स 1
एक्स 2
एक्स 5

चूंकि इष्टतम समाधान में कोई कृत्रिम चर नहीं हैं (वे शून्य के बराबर हैं), यह समाधान संभव है।

इष्टतम योजना इस प्रकार लिखी जा सकती है: x 1 \u003d 2, x 2 \u003d 2:।

उत्तर:
,
.

3. कंपनी "थ्री फैट मेन" शहर के अलग-अलग हिस्सों में स्थित तीन गोदामों से तीन दुकानों तक डिब्बाबंद मांस की डिलीवरी में लगी हुई है। गोदामों में उपलब्ध डिब्बाबंद भोजन के स्टॉक, साथ ही दुकानों से ऑर्डर की मात्रा और वितरण दर (पारंपरिक मौद्रिक इकाइयों में) परिवहन तालिका में प्रस्तुत किए जाते हैं।

एक परिवहन योजना खोजें जो कम से कम नकद लागत प्रदान करे ("उत्तर-पश्चिम कोने" विधि का उपयोग करके मूल परिवहन योजना निष्पादित करें)।

समाधान

आइए समस्या की सॉल्वेबिलिटी के लिए आवश्यक और पर्याप्त स्थिति की जाँच करें:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

संतुलन की शर्त पूरी होती है। स्टॉक समान आवश्यकताएँ। इसलिए, परिवहन समस्या मॉडल बंद है।

आइए वितरण तालिका में प्रारंभिक डेटा दर्ज करें।

ज़रूरत

उत्तर-पश्चिम कोने की विधि का उपयोग करते हुए, हम परिवहन समस्या की पहली मूल योजना का निर्माण करेंगे।

ऊपरी बाएँ कोने से योजना को भरना शुरू होता है।

वांछित तत्व 4 है। इस तत्व के लिए स्टॉक 300 हैं, आवश्यकता 250 है। चूंकि न्यूनतम 250 है, हम इसे घटाते हैं:।

			300 - 250 = 50
250 - 250 = 0

वांछित तत्व 2 है। इस तत्व के लिए, स्टॉक 50 हैं, जरूरत 400 है। चूंकि न्यूनतम 50 है, हम इसे घटाते हैं:।

			50 - 50 = 0
	400 - 50 = 350

वांछित तत्व 5 है। इस तत्व के लिए, स्टॉक 300 हैं, जरूरतें 350 हैं। चूंकि न्यूनतम 300 है, हम इसे घटाते हैं:

			300 - 300 = 0
	350 - 300 = 50

वांछित तत्व 3 है। इस तत्व के लिए, स्टॉक 200 हैं, जरूरतें 50 हैं। चूंकि न्यूनतम 50 है, हम इसे घटाते हैं:

			200 - 50 = 150
	50 - 50 = 0

वांछित तत्व 6 है। इस तत्व के लिए, स्टॉक 150 हैं, जरूरतें 150 हैं। चूंकि न्यूनतम 150 है, हम इसे घटाते हैं:

			150 - 150 = 0
		150 - 150 = 0

ज़रूरत