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

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

हम x 1 x 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 एम2 तक बोर्ड और 2,000 डॉलर मूल्य की सहायक सामग्री प्राप्त कर सकती है। प्रत्येक कैबिनेट को 7 घंटे मशीन संचालन की आवश्यकता होती है, और टेबल को 3 घंटे की आवश्यकता होती है। प्रति माह कुल 840 मशीन संचालन घंटे का उपयोग किया जा सकता है।

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

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

आइए हम कैबिनेट के उत्पादन की मात्रा को x 1 और तालिकाओं के उत्पादन की मात्रा को x 2 से निरूपित करें। आइए प्रतिबंधों की एक प्रणाली और एक लक्ष्य फ़ंक्शन बनाएं:

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

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

तालिका नंबर एक

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

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

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

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

1. तय करना चित्रमय विधिरैखिक प्रोग्रामिंग समस्या. दिए गए प्रतिबंधों के साथ फ़ंक्शन का अधिकतम और न्यूनतम ज्ञात करें:

,

.

समाधान

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

9x 1 +3x 2 ≥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 = 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 के अनुरूप कॉलम चुनेंगे, क्योंकि यह सबसे बड़ा गुणांक है। आइए मानों की गणना करें डी मैं और उनमें से हम सबसे छोटा चुनते हैं: न्यूनतम(4:1, 2:2, 10:2) = 1।

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

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

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

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

योजना 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 के बजाय, प्लान 2 में वेरिएबल x 1 शामिल होगा।

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

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

सूचकांक स्ट्रिंग मानों के बीच कोई सकारात्मक मान नहीं हैं। इसलिए, यह तालिका समस्या के लिए इष्टतम योजना निर्धारित करती है।

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

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

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

इष्टतम योजना इस प्रकार लिखी जा सकती है: x 1 = 2, x 2 = 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

ज़रूरत

प्रयोगशाला कार्य संख्या 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 एक्स 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 के लिए, टूल्स देखें)। यदि समाधान खोजें आदेश या विश्लेषण समूह अनुपलब्ध है, तो आपको यह ऐड-इन डाउनलोड करना होगा।

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

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

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

7) 7एक्स 1 + 6एक्स 2 → अधिकतम 20एक्स 1 + 6एक्स 2 ≤ 15 16एक्स 1 − 2एक्स 2 ≤ 18 8एक्स 1 + 4एक्स 2 ≤ 20 13एक्स 1 + 3एक्स 2 ≤ 4 एक्स 1 , एक्स 2 ≥ 0.

चरण 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. अधिकतम (न्यूनतम) बिंदु के निर्देशांक और उद्देश्य फ़ंक्शन का इष्टतम मान निर्धारित करना

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

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

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

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

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