चित्रमय विधि द्वारा किसी फलन का एक्स्ट्रेमा ज्ञात कीजिए। उद्देश्य फलन का इष्टतम मान कहलाता है

के लिए परीक्षण वर्तमान नियंत्रणज्ञान

1. समस्या का कोई भी आर्थिक-गणितीय मॉडल रैखिक प्रोग्रामिंगशामिल हैं:

ए उद्देश्य समारोह और बाधा प्रणाली

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

सी. चर की गैर-नकारात्मकता के लिए बाधाओं और शर्तों की प्रणाली

डी. चर के गैर-नकारात्मकता के लिए उद्देश्य कार्य और शर्तें

ए।वस्तुनिष्ठ कार्य

बी समीकरणों की प्रणाली

C. असमानताओं की प्रणाली

डी. चर की गैर-नकारात्मकता की स्थिति

3. गणितीय प्रोग्रामिंग की समस्या का इष्टतम समाधान है

ए बाधा प्रणाली का स्वीकार्य समाधान

बी बाधा प्रणाली का कोई समाधान

सी।उद्देश्य समारोह के अधिकतम या न्यूनतम के लिए बाधा प्रणाली का स्वीकार्य समाधान

डी. बाधा प्रणाली का अधिकतम या न्यूनतम समाधान

4. बाधाओं की एक प्रणाली को मानक कहा जाता है यदि इसमें शामिल है

ए सभी संकेत

बी।सभी संकेत

सी. सभी निशान

D. सभी निशान

5. रैखिक प्रोग्रामिंग की समस्या हल हो गई है रेखांकन, अगर कार्य में

ए एक चर

बी।दो चर

सी. तीन चर

D. चार चर

6. फॉर्म की असमानता का वर्णन करता है

बी परिधि

सी।आधा विमान

डी. विमान

7. उद्देश्य फलन का अधिकतम या न्यूनतम पाया जाता है

ए मूल में

B. उत्तल विलयन बहुभुज की भुजाओं पर

C. एक उत्तल विलयन बहुभुज के अंदर

डी।उत्तल समाधान बहुभुज के शीर्षों पर

8. एलएलपी का विहित रूप एक ऐसा रूप है जिसमें प्रतिबंधों की प्रणाली में संकेत होते हैं

ए सभी संकेत

बी सभी संकेत

सी।सभी संकेत

D. सभी निशान

9. यदि बाधा को ">=" चिह्न के साथ निर्दिष्ट किया जाता है, तो एक अतिरिक्त चर इस बाधा में एक गुणांक के साथ पेश किया जाता है

बी।-1

10. अतिरिक्त चर को गुणांक के साथ उद्देश्य फ़ंक्शन में पेश किया जाता है

सी।0

ए।j-वें प्रकार के उत्पाद की 1 इकाई के निर्माण के लिए आवश्यक संख्या के साथ संसाधन की मात्रा

B. i-th प्रकार के अप्रयुक्त संसाधन

C. j -th प्रकार . के उत्पादन की 1 इकाई की बिक्री से लाभ

D. j-वें प्रकार के उत्पादों की मात्रा

12. अधिकतम उद्देश्य फ़ंक्शन के लिए एलएलपी को हल करते समय समाधान कॉलम का चयन शर्त के आधार पर किया जाता है

ए।महानतम सकारात्मक मूल्यउद्देश्य फलन का गुणांक Cj

B. उद्देश्य फलन के गुणांक Cj का सबसे छोटा धनात्मक मान

सी. महानतम नकारात्मक अर्थउद्देश्य फलन का गुणांक Cj

D. अज्ञात के लिए गुणांकों का कोई स्तंभ

13. इष्टतम योजना वाली तालिका में उद्देश्य फलन का मान है

ए। x1 . पर गुणांक के कॉलम के साथ उद्देश्य फ़ंक्शन के गुणांक की पंक्ति के चौराहे पर

बी।स्तंभ b . के साथ उद्देश्य फलन के गुणांकों की पंक्ति के प्रतिच्छेदन पर

C. गुणांकों के स्तंभ में xn . पर

डी। मूल आधार के कॉलम के साथ उद्देश्य फ़ंक्शन के गुणांक की पंक्ति के चौराहे पर

14. कृत्रिम चर को गुणांक के साथ विहित रूप में बाधाओं की प्रणाली में पेश किया जाता है

ए।1

15. सिंप्लेक्स तालिका में योजना की इष्टतमता किसके द्वारा निर्धारित की जाती है

A. कॉलम b . द्वारा

बी।उद्देश्य फ़ंक्शन मानों की स्ट्रिंग द्वारा

सी अनुमति लाइन

D. अनुमति कॉलम द्वारा

16. एक रैखिक प्रोग्रामन समस्या को देखते हुए

बी।1

17. एक रैखिक प्रोग्रामन समस्या को देखते हुए

इस समस्या के लिए कृत्रिम चरों की संख्या है

सी।2

18. यदि मूल एलएलपी का फॉर्म है

फिर दोहरी समस्या की बाधाएं

ए। फॉर्म है

बी।हमशक्ल

सी. जैसा दिखता है

डी. जैसा दिखता है

19. यदि मूल एलएलपी का फॉर्म है

ए। फॉर्म है

बी। फॉर्म है

सी. जैसा दिखता है

डी।हमशक्ल

20. दोहरी समस्या के अज्ञात उद्देश्य कार्यों के गुणांक हैं:

ए मूल समस्या के अज्ञात उद्देश्य कार्यों के लिए गुणांक

बी।मूल समस्या की बाधा प्रणाली के मुक्त सदस्य

C. मूल समस्या से अनजान

D. गुणांक अज्ञात प्रणालीमूल समस्या की बाधाएं

21. यदि मूल एलएलपी अधिकतम उद्देश्य फलन पर था, तो दोहरा कार्य होगा

ए. अधिकतम तक भी

बी या तो अधिकतम या न्यूनतम

C. अधिकतम और न्यूनतम दोनों

डी।कम से कम

22. मूल और दोहरी समस्याओं के बीच संबंध यह है कि

ए। दोनों कार्यों को हल किया जाना चाहिए

बी।उनमें से एक का समाधान दूसरे के समाधान से प्राप्त होता है

C. दोहरी समस्या के समाधान से मूल समस्या का समाधान प्राप्त करना असंभव है

D. दोनों का एक ही हल है

23. यदि मूल एलएलपी का फॉर्म है

फिर दोहरी समस्या का उद्देश्य कार्य

ए। फॉर्म है

बी। फॉर्म है

सी।हमशक्ल

डी. जैसा दिखता है

24. यदि मूल एलएलपी का फॉर्म है

तो द्वैत समस्या में चरों की संख्या है

बी।2

25. परिवहन कार्य का मॉडल बंद है,

ए।यदि

26. परिवहन समस्या का चक्र है

ए। एक बंद आयताकार पॉलीलाइन, जिसके सभी कोने कब्जे वाली कोशिकाओं में हैं

B. एक बंद आयताकार पॉलीलाइन, जिसके सभी शीर्ष मुक्त कोशिकाओं में हैं

C. एक बंद आयताकार पॉलीलाइन, जिसमें से एक शीर्ष एक कब्जे वाले सेल में है, बाकी मुक्त कोशिकाओं में हैं

डी।एक बंद आयताकार पॉलीलाइन, जिसमें से एक शीर्ष एक मुक्त सेल में है, और शेष कब्जे वाली कोशिकाओं में है

27. आयाम (m * n) की परिवहन समस्या की संभावनाएं m + n संख्या ui और vj हैं, जिसके लिए शर्तें हैं

ए।ui+vj=cij कब्जे वाली कोशिकाओं के लिए

B. ui+vj=cij मुक्त कोशिकाओं के लिए

सी. ui+vj=cij वितरण तालिका के पहले दो स्तंभों के लिए

डी. ui+vj=cij आवंटन तालिका की पहली दो पंक्तियों के लिए

28. आयाम (एम + एन) की परिवहन समस्या का अनुमान संख्याएं हैं

yij=cij-ui-vj जिनकी गणना की जाती है

A. व्यस्त कोशिकाओं के लिए

बी।मुक्त कोशिकाओं के लिए

C. वितरण तालिका की पहली दो पंक्तियों के लिए

D. वितरण तालिका के पहले दो स्तंभों के लिए

29. परिवहन समस्या को हल करते समय, उद्देश्य फ़ंक्शन का मान पुनरावृत्ति से पुनरावृत्ति तक होना चाहिए

ए वृद्धि

बी वृद्धि या परिवर्तन नहीं

सी. किसी भी अंक के मूल्य से वृद्धि

डी।घटाना या अपरिवर्तित रहना

30. परिवहन समस्या की गैर-पतित योजना के कब्जे वाले कक्षों की संख्या बराबर होनी चाहिए

सी।एम+एन-1

31. आर्थिक भावनापरिवहन कार्य का उद्देश्य कार्य

ए कुल यातायात

बी।परिवहन की कुल लागत

सी. कुल प्रसव

डी. कुल जरूरतें

आइए हम विमान पर सिस्टम के स्वीकार्य समाधानों के सेट का निर्माण करें रैखिक असमानताएंऔर ज्यामितीय रूप से उद्देश्य फ़ंक्शन का न्यूनतम मान ज्ञात करें।

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

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

.

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

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. एक्सेल का उपयोग करके रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एल्गोरिदम का वर्णन करें।

राज्य बजट शिक्षण संस्थान

उच्च व्यावसायिक शिक्षा

"ओम्स्क राज्य तकनीकी विश्वविद्यालय"

गणना और ग्राफिक कार्य

अनुशासन से "इष्टतम नियंत्रण सिद्धांत »

विषय पर "अनुकूलन के तरीके और संचालन अनुसंधान »

विकल्प 7

पूरा हुआ:

पत्राचार छात्र

चौथा वर्ष समूह ZA-419

नाम: कुज़ेलेव एस.ए.

चेक किया गया:

देव्यातेरिकोवा एम.वी.

ओम्स्क - 2012
^

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

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

मॉडल की पहली बाधा है . इसमें चिह्न को चिह्न = से बदलने पर, हम समीकरण प्राप्त करते हैं . अंजीर पर। 1.1 यह एक रेखा (1) को परिभाषित करता है जो विमान को दो अर्ध-तलों में विभाजित करती है, इस स्थिति में रेखा के ऊपर और नीचे। यह चुनने के लिए कि कौन असमानता को संतुष्ट करता है , हम इसमें किसी भी बिंदु के निर्देशांक प्रतिस्थापित करते हैं जो दी गई रेखा पर स्थित नहीं है (उदाहरण के लिए, मूल बिंदु एक्स 1 = 0, एक्स 2 = 0)। चूँकि हमें सही व्यंजक (20 0 + 6 0 = 0 15) प्राप्त होता है, इसलिए अर्ध-समतल मूल बिन्दु (एक तीर से चिह्नित) से असमिका को संतुष्ट करता है। अन्यथा, एक और आधा विमान।

हम समस्या की शेष बाधाओं के साथ इसी तरह आगे बढ़ते हैं। पहले चतुर्थांश रूपों के साथ सभी निर्मित अर्ध-विमानों का प्रतिच्छेदन ए बी सी डी(अंजीर देखें। 1)। यह कार्य का वैध दायरा है।

चरण 2। एक स्तर रेखा का निर्माण स्तर रेखा ऑब्जेक्टिव फंक्शन समतल में बिंदुओं का एक समूह होता है, जिस पर ऑब्जेक्टिव फंक्शन एक स्थिर मान लेता है। ऐसा समुच्चय समीकरण द्वारा दिया गया है एफ ( एक्स) = स्थिरांक. आइए डालते हैं, उदाहरण के लिए, स्थिरांक = 0 और स्तर पर एक रेखा खींचना एफ ( एक्स) = 0, यानी हमारे मामले में, प्रत्यक्ष 7 एक्स 1 + 6एक्स 2 = 0.

यह रेखा मूल बिंदु से होकर गुजरती है और सदिश के लंबवत है। यह वेक्टर (0,0) पर ऑब्जेक्टिव फंक्शन ग्रेडिएंट है। किसी फ़ंक्शन का ग्रेडिएंट प्रश्न के बिंदु पर दिए गए फ़ंक्शन के आंशिक डेरिवेटिव के मूल्यों का एक वेक्टर है। एलपी समस्या के मामले में, उद्देश्य फ़ंक्शन के आंशिक व्युत्पन्न गुणांक के बराबर होते हैं सीमैं, जे = 1 , ..., एन.

ग्रेडिएंट फ़ंक्शन के सबसे तेज़ विकास की दिशा दिखाता है। ऑब्जेक्टिव फंक्शन लेवल लाइन को मूव करना एफ ( एक्स) = स्थिरांक. ढाल की दिशा के लंबवत, वह अंतिम बिंदु ज्ञात करें जहां यह क्षेत्र के साथ प्रतिच्छेद करता है। हमारे मामले में, यह बिंदु D है, जो उद्देश्य फलन का अधिकतम बिंदु होगा (चित्र 2 देखें)।

यह रेखाओं (2) और (3) के प्रतिच्छेदन पर स्थित है (चित्र 1 देखें) और इष्टतम समाधान निर्धारित करता है।

^ ध्यान दें कि यदि उद्देश्य फ़ंक्शन का न्यूनतम मान ज्ञात करना आवश्यक है, तो स्तर रेखा को ढाल की दिशा के विपरीत दिशा में ले जाया जाता है।

^ चरण 3. अधिकतम (न्यूनतम) बिंदु के निर्देशांक और उद्देश्य फ़ंक्शन के इष्टतम मूल्य का निर्धारण

बिंदु सी के निर्देशांक खोजने के लिए, संबंधित प्रत्यक्ष समीकरणों से युक्त एक प्रणाली को हल करना आवश्यक है (इस मामले में, समीकरण 2 और 3 से):

16एक्स 1 − 2एक्स 2 ≤ 18

8एक्स 1 + 4एक्स 2 ≤ 20

हमें इष्टतम समाधान = 1.33 मिलता है।

^ उद्देश्य समारोह का इष्टतम मूल्य एफ * = एफ (एक्स*) = 7 * 0 + 6 * 1,33 = 7,8