परिचय

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

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

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


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

हम तीसरी पंक्ति को 5 के बराबर प्रमुख तत्व से विभाजित करते हैं, हमें नई तालिका की तीसरी पंक्ति मिलती है।

बेस कॉलम सिंगल कॉलम के अनुरूप हैं।

शेष तालिका मानों की गणना:

"बीपी - मूल योजना":

; ;

"X1": ; ;

"एक्स5": ; .

सूचकांक पंक्ति के मान गैर-ऋणात्मक हैं, इसलिए हम इष्टतम समाधान प्राप्त करते हैं: , ; .

जवाब:निर्मित उत्पादों की बिक्री से अधिकतम लाभ, 160/3 इकाइयों के बराबर, 80/9 इकाइयों की मात्रा में केवल दूसरे प्रकार के उत्पादों की रिहाई से सुनिश्चित होता है।

टास्क नंबर 2

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

क्योंकि सिफर का अंतिम अंक 8 है, तो A=2; बी = 5।

क्योंकि सिफर का अंतिम अंक 1 है, तो आपको कार्य संख्या 1 चुनना चाहिए।

फेसला:

1) आइए उस क्षेत्र को बनाएं जिसे असमानताओं की प्रणाली परिभाषित करती है।

यह क्षेत्र एक त्रिभुज ABC है जिसके शीर्षों के निर्देशांक हैं: A(0; 2); बी(4; 6) और सी(16/3; 14/3)।

उद्देश्य फ़ंक्शन स्तर बिंदु (2; 5) पर केंद्रित वृत्त हैं। त्रिज्या के वर्ग वस्तुनिष्ठ फलन के मान होंगे। तब आकृति दर्शाती है कि उद्देश्य फलन का न्यूनतम मान बिंदु H पर पहुंच जाता है, अधिकतम मान या तो बिंदु A पर या बिंदु C पर होता है।

बिंदु A पर उद्देश्य फलन का मान:;

बिंदु C पर उद्देश्य फलन का मान:;

इसका मतलब है कि फ़ंक्शन का अधिकतम मान बिंदु A(0; 2) पर पहुंच गया है और 13 के बराबर है।

आइए बिंदु H के निर्देशांक ज्ञात करें।

ऐसा करने के लिए, सिस्टम पर विचार करें:

ó

ó

एक रेखा वृत्त की स्पर्श रेखा होती है यदि समीकरण का एक अद्वितीय हल है। एक द्विघात समीकरण का एक अद्वितीय हल होता है यदि विभेदक 0 है।

फिर ; ; - समारोह का न्यूनतम मूल्य।

2) न्यूनतम समाधान खोजने के लिए लैग्रेंज फ़ंक्शन लिखें:

पर एक्स 1 =2.5; एक्स 2 =4.5 हम पाते हैं:

ó

प्रणाली के लिए एक समाधान है, अर्थात्। पर्याप्त चरम स्थितियां संतुष्ट हैं।

हम अधिकतम समाधान खोजने के लिए लैग्रेंज फ़ंक्शन की रचना करते हैं:

एक चरम के लिए पर्याप्त शर्तें:

पर एक्स 1 =0; एक्स 2 =2 हम पाते हैं:

ó ó

सिस्टम का एक समाधान भी है, अर्थात। पर्याप्त चरम स्थितियां संतुष्ट हैं।

जवाब:उद्देश्य समारोह के न्यूनतम पर पहुंच गया है ; ; अधिकतम उद्देश्य फलन तब प्राप्त होता है जब ; .

टास्क नंबर 3

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

मैं = 8, के = 1।

ए = 2200; कश्मीर 1 =6; के2 = 1; एन = 0.2; एम = 0.5।

फेसला:

4 वर्षों की पूरी अवधि को 4 चरणों में विभाजित किया गया है, जिनमें से प्रत्येक एक वर्ष के बराबर है। आइए पहले वर्ष से शुरू होने वाले चरणों की संख्या दें। मान लीजिए कि के-वें चरण में उद्यम ए और बी को क्रमशः एक्स के और वाई के आवंटित धन हैं। फिर योग X k + Y k =a k k - उस चरण में उपयोग की गई धनराशि की कुल राशि है और पिछले चरण k - 1 से शेष है। पहले चरण में सभी आवंटित धन का उपयोग किया जाता है और 1 = 2200 इकाइयाँ। k पर प्राप्त होने वाली आय - वह अवस्था, जब X k और Y k इकाइयाँ आवंटित की जाती हैं, 6X k + 1Y k होगी। बता दें कि k से शुरू होने वाले अंतिम चरणों में प्राप्त अधिकतम आय - वह चरण f k (a k) इकाइयाँ हैं। आइए इष्टतमता के सिद्धांत को व्यक्त करते हुए बेलमैन कार्यात्मक समीकरण लिखें: प्रारंभिक स्थिति और प्रारंभिक समाधान जो भी हो, प्रारंभिक अवस्था के परिणामस्वरूप प्राप्त राज्य के संबंध में बाद का समाधान इष्टतम होना चाहिए:

प्रत्येक चरण के लिए, आपको X k मान और मान . चुनना होगा वाई को=एक- एक्सक. इसे ध्यान में रखते हुए, हम k-वें चरण में आय पाएंगे:

कार्यात्मक बेलमैन समीकरण इस तरह दिखेगा:

आखिरी से शुरू करते हुए, सभी चरणों पर विचार करें।

(चूंकि रेखीय फलन की अधिकतम सीमा खंड के अंत में x 4 = a 4 पर पहुंच जाती है);

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

उदाहरण

सुचारू कार्य और समीकरणों की प्रणाली

समीकरणों की किसी भी प्रणाली को हल करने की समस्या

(एफ 1 (एक्स 1, एक्स 2, …, एक्स एम) = 0 एफ 2 (एक्स 1, एक्स 2, …, एक्स एम) = 0 … एफ एन (एक्स 1, एक्स 2, …, एक्स एम) = 0 ( \displaystyle \left\((\begin(matrix)F_(1)(x_(1),x_(2),\ldots ,x_(M))=0\\F_(2)(x_(1),x_ (2),\ldots ,x_(M))=0\\\ldots \\F_(N)(x_(1),x_(2),\ldots ,x_(M))=0\end(matrix) )\सही।)

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

S = ∑ j = 1 N F j 2 (x 1, x 2 , … , x M) (1) (\displaystyle S=\sum _(j=1)^(N)F_(j)^(2)( x_(1),x_(2),\ldots ,x_(M))\qquad(1))

यदि कार्य सुचारू हैं, तो न्यूनतम समस्या को ढाल विधियों द्वारा हल किया जा सकता है।

किसी भी सुचारू उद्देश्य फ़ंक्शन के लिए, सभी चर के संबंध में 0 (\displaystyle 0) आंशिक व्युत्पन्न के बराबर हो सकता है। इष्टतम उद्देश्य फ़ंक्शन समीकरणों की ऐसी प्रणाली के समाधानों में से एक होगा। फ़ंक्शन (1) (\displaystyle (1)) के मामले में यह कम से कम वर्ग (एलएसएम) समीकरणों की एक प्रणाली होगी। मूल प्रणाली का कोई भी समाधान कम से कम वर्ग प्रणाली का समाधान है। यदि मूल प्रणाली असंगत है, तो एलएसएम प्रणाली, जिसमें हमेशा एक समाधान होता है, मूल प्रणाली का अनुमानित समाधान प्राप्त करना संभव बनाता है। एलएसएम प्रणाली के समीकरणों की संख्या अज्ञात की संख्या के साथ मेल खाती है, जो कभी-कभी संयुक्त प्रारंभिक प्रणालियों के समाधान की सुविधा प्रदान करती है।

रैखिक प्रोग्रामिंग

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

संयुक्त अनुकूलन

कॉम्बीनेटरियल ऑब्जेक्टिव फंक्शन का एक विशिष्ट उदाहरण ट्रैवलिंग सेल्समैन समस्या का ऑब्जेक्टिव फंक्शन है। यह फलन ग्राफ पर हैमिल्टनियन चक्र की लंबाई के बराबर है। यह ग्राफ़ के शीर्षों के क्रमपरिवर्तन सेट n - 1 (\displaystyle n-1) पर दिया गया है और यह ग्राफ़ के किनारे की लंबाई मैट्रिक्स द्वारा निर्धारित किया जाता है। ऐसी समस्याओं का सटीक समाधान अक्सर विकल्पों की गणना में ही आता है।

अध्याय 1. रैखिक प्रोग्रामिंग की मुख्य समस्या का विवरण

1. रैखिक प्रोग्रामिंग

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

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

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

उत्पादन योजना में संसाधनों के इष्टतम उपयोग की समस्या;

मिश्रण की समस्या (उत्पादों की संरचना की योजना बनाना);

गोदामों (इन्वेंट्री प्रबंधन या) में भंडारण के लिए विभिन्न प्रकार के उत्पादों का इष्टतम संयोजन खोजने की समस्या;

परिवहन कार्य (उद्यम के स्थान का विश्लेषण, माल की आवाजाही)।

रैखिक प्रोग्रामिंग गणितीय प्रोग्रामिंग का सबसे विकसित और व्यापक रूप से उपयोग किया जाने वाला खंड है (इसके अलावा, इसमें शामिल हैं: पूर्णांक, गतिशील, गैर-रेखीय, पैरामीट्रिक प्रोग्रामिंग)। इसे इस प्रकार समझाया गया है:

बड़ी संख्या में आर्थिक समस्याओं के गणितीय मॉडल आवश्यक चरों के संबंध में रैखिक हैं;

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

रैखिक प्रोग्रामिंग की कई समस्याओं को हल किया जा रहा है, व्यापक आवेदन मिला है;

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

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

सामान्य तौर पर, मॉडल निम्नानुसार लिखा जाता है:

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

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

(1.2) गैर-नकारात्मकता आवश्यकताएं

(1.3) जहां एक्स जे- चर (अज्ञात);

- रैखिक प्रोग्रामिंग समस्या के गुणांक।

समस्या यह है कि बाधाओं (1.2) और (1.3) के अधीन फ़ंक्शन (1.1) का इष्टतम मान ज्ञात करें।

बाधाओं की प्रणाली (1.2) को समस्या की कार्यात्मक बाधा कहा जाता है, और बाधाओं (1.3) को प्रत्यक्ष बाधा कहा जाता है।

एक वेक्टर जो बाधाओं (1.2) और (1.3) को संतुष्ट करता है उसे रैखिक प्रोग्रामिंग समस्या का व्यवहार्य समाधान (योजना) कहा जाता है। वह योजना जिसके लिए फलन (1.1) अपने अधिकतम (न्यूनतम) मान तक पहुँचता है, इष्टतम कहलाता है।

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

सिंप्लेक्स विधि विकसित की गई थी और पहली बार 1947 में अमेरिकी गणितज्ञ जे। डेंट्ज़िग द्वारा समस्याओं को हल करने के लिए लागू की गई थी।

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

मानक रूप में दी गई एलपी समस्या का एक स्वीकार्य समाधान (एक स्वीकार्य योजना) संख्याओं का एक आदेशित सेट (x1, x2, ..., xn) है जो बाधाओं को पूरा करता है; n-आयामी अंतरिक्ष में एक बिंदु है।

स्वीकार्य समाधानों का सेट एलपी समस्या के स्वीकार्य समाधान (एसडीआर) का क्षेत्र बनाता है। ODR एक उत्तल बहुफलक (बहुभुज) है।

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

एक समाधान को मूल कहा जाता है यदि सभी मुक्त चर शून्य के बराबर हों।

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

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

जब चरों की संख्या 3 से अधिक हो तो इन समस्याओं को आलेखीय रूप से हल करना बहुत कठिन होता है। रैखिक प्रोग्रामिंग समस्याओं को हल करने का एक सार्वभौमिक तरीका है, जिसे सरल विधि कहा जाता है।

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

इसका उपयोग किसी भी रैखिक प्रोग्रामिंग समस्या को हल करने के लिए किया जा सकता है।

सिंप्लेक्स विधि परिणामी समाधान के क्रमिक सुधार के विचार पर आधारित है।

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

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

सिंप्लेक्स पद्धति को लागू करने की प्रक्रिया में इसके तीन मुख्य तत्वों का कार्यान्वयन शामिल है:

समस्या के कुछ प्रारंभिक व्यवहार्य बुनियादी समाधान निर्धारित करने की एक विधि;

सर्वोत्तम (अधिक सटीक, सबसे खराब नहीं) समाधान के लिए संक्रमण का नियम;

पाए गए समाधान की इष्टतमता की जाँच के लिए मानदंड।

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

6.1 परिचय

अनुकूलन। भाग 1

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

6.2. अनुकूलन सिद्धांत के मूल सिद्धांत

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

अज्ञात के साथ एम समीकरणों द्वारा वर्णित कुछ मनमानी प्रणाली को ध्यान में रखते हुए, हम तीन मुख्य प्रकार की समस्याओं को अलग कर सकते हैं। यदि m=n , तो समस्या को बीजीय कहा जाता है। ऐसी समस्या का आमतौर पर एक ही समाधान होता है। यदि m>n, तो समस्या को फिर से परिभाषित किया जाता है और, एक नियम के रूप में, इसका कोई समाधान नहीं है। अंत में, एम . के लिए

अनुकूलन मुद्दों की चर्चा के लिए आगे बढ़ने से पहले, हम कई परिभाषाओं का परिचय देते हैं।

डिजाइन के पैमाने

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

एक्स1, एक्स2, एक्स3,...,एक्सएन।

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

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

एम = एम (एक्स 1, एक्स 2, ..., एक्स एन)।

इंजीनियरिंग अभ्यास में अक्सर सामना किए जाने वाले उद्देश्य समारोह के उदाहरण लागत, वजन, ताकत, आयाम, दक्षता हैं। यदि केवल एक डिज़ाइन पैरामीटर है, तो उद्देश्य फ़ंक्शन को एक समतल पर एक वक्र द्वारा दर्शाया जा सकता है (चित्र 6.1)। यदि दो डिज़ाइन पैरामीटर हैं, तो लक्ष्य फ़ंक्शन को तीन आयामों (चित्र। 6.2) के स्थान में एक सतह द्वारा दर्शाया जाएगा। तीन या अधिक डिज़ाइन मापदंडों के साथ, उद्देश्य फ़ंक्शन द्वारा निर्दिष्ट सतहों को हाइपरसर्फेस कहा जाता है और इन्हें चित्रित नहीं किया जा सकता है।

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

कुछ मामलों में उद्देश्य कार्य सबसे अप्रत्याशित रूप ले सकता है। उदाहरण के लिए, इसे हमेशा व्यक्त करना संभव नहीं है

अंजीर। 1. एक आयामी उद्देश्य समारोह।

Fig.6.2.द्वि-आयामी उद्देश्य समारोह।

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

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

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

न्यूनतम और अधिकतम ढूँढना

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

डिजाइन स्थान

यह सभी n डिज़ाइन मापदंडों द्वारा परिभाषित क्षेत्र का नाम है। डिज़ाइन स्थान उतना बड़ा नहीं है जितना यह लग सकता है, क्योंकि यह आमतौर पर कई तक सीमित होता है

समस्या के भौतिक सार से जुड़ी स्थितियां। बाधाएं इतनी मजबूत हो सकती हैं कि कार्य में कोई कमी नहीं होगी

चित्र 6.3. उद्देश्य फलन के चिह्न को विपरीत में बदलना

अधिकतम कार्य न्यूनतम कार्य बन जाता है।

संतोषजनक समाधान। बाधाओं को दो समूहों में बांटा गया है: बाधाएं - समानताएं और बाधाएं - असमानताएं।

बाधाएं - समानता

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

सी 1 (एक्स 1 , एक्स 2 ,..., एक्स एन) = 0,

सी 2 (एक्स 1 , एक्स 2 ,..., एक्स एन) = 0,

..................

सी जे (एक्स 1 , एक्स 2 ,..., एक्स एन) = 0।

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

बाधाएं - असमानताएं

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

जेड 1 आर 1 (एक्स 1, एक्स 2, ..., एक्स एन) जेड 1

जेड 2 आर 2 (एक्स 1, एक्स 2, ..., एक्स एन) जेड 2

.......................

जेड के आर के (एक्स 1, एक्स 2, ..., एक्स एन) जेड के

यह ध्यान दिया जाना चाहिए कि बहुत बार, सीमाओं के कारण, उद्देश्य फ़ंक्शन का इष्टतम मूल्य प्राप्त नहीं होता है जहां इसकी सतह में शून्य ढाल होता है। अक्सर सबसे अच्छा समाधान डिज़ाइन डोमेन की सीमाओं में से एक पर होता है।

स्थानीय इष्टतम

यह डिज़ाइन स्थान में उस बिंदु का नाम है जिस पर अपने निकटतम पड़ोस में अन्य सभी बिंदुओं पर इसके मूल्यों की तुलना में उद्देश्य फ़ंक्शन का सबसे बड़ा मूल्य है।

चित्र 6.4. एक मनमाना उद्देश्य फलन में कई हो सकते हैं

स्थानीय ऑप्टिमा।

अंजीर पर। चित्र 6.4 एक-आयामी उद्देश्य फ़ंक्शन दिखाता है जिसमें दो स्थानीय ऑप्टिमा हैं। अक्सर डिज़ाइन स्पेस में कई स्थानीय ऑप्टिमा होते हैं और इस बात का ध्यान रखा जाना चाहिए कि समस्या के इष्टतम समाधान के लिए पहले वाले को गलती न करें।

वैश्विक इष्टतम

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

उदाहरण 6.1

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

आइए हम इस समस्या को अनुकूलन एल्गोरिथम को लागू करने के लिए सुविधाजनक रूप में तैयार करें।

डिज़ाइन पैरामीटर: x 1 , x 2 , x 3 ।

उद्देश्य फ़ंक्शन (जिसे कम से कम करने की आवश्यकता है) कंटेनर की साइड सतह का क्षेत्र है:

ए = 2 (एक्स 1 एक्स 2 + एक्स 2 एक्स 3 + एक्स 1 एक्स 3), एम 2।

बाधा - समानता:

वॉल्यूम \u003d x 1 x 2 x 3 \u003d 1m3।

बाधा - असमानता:

रैखिक प्रोग्रामिंग समस्याएं

रैखिक प्रोग्रामिंग (एलपी)गणितीय प्रोग्रामिंग के वर्गों में से एक है - एक अनुशासन जो चरम (अनुकूलन) समस्याओं का अध्ययन करता है और उन्हें हल करने के तरीकों को विकसित करता है।

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

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

गणितीय प्रोग्रामिंग के कार्यों और समस्याओं के प्रकार के आधार पर कई वर्गों (रैखिक, गैर-रैखिक, उत्तल, पूर्णांक, स्टोकेस्टिक, गतिशील प्रोग्रामिंग, आदि) में विभाजित किया जाता है।

पर सामान्य दृष्टि सेएलपी समस्या का निम्न रूप है:

, (5.1)

, , (5.2)

, , (5.3)

जहां , , स्थिरांक दिए गए हैं।

फलन (5.1) को उद्देश्य फलन कहा जाता है; सिस्टम (5.2), (5.3) - बाधाओं की एक प्रणाली द्वारा; कंडीशन (5.4) डिजाइन मापदंडों की गैर-नकारात्मकता की स्थिति है।

बाधाओं (5.2), (5.3) और (5.4) को संतुष्ट करने वाले डिजाइन मापदंडों के सेट को कहा जाता है स्वीकार्य समाधानया योजना.

इष्टतम समाधानया इष्टतम योजनाएलपी समस्या को एक व्यवहार्य समाधान कहा जाता है, जिसमें उद्देश्य कार्य (5.1) इष्टतम (अधिकतम या न्यूनतम) मान लेता है।

मानक कार्यएलपी को स्थिति (5.2) और (5.4) के तहत उद्देश्य फ़ंक्शन (5.1) के अधिकतम (न्यूनतम) मान को खोजने की समस्या कहा जाता है, जहां, यानी। वे। केवल असमानताओं (5.2) के रूप में प्रतिबंध और सभी डिज़ाइन पैरामीटर गैर-नकारात्मकता की स्थिति को संतुष्ट करते हैं, और समानता के रूप में कोई शर्तें नहीं हैं:

,

, , (5.5)

.

विहित (मुख्य) कार्यएलपी को शर्त (5.3) और (5.4) के तहत उद्देश्य फ़ंक्शन (5.1) के अधिकतम (न्यूनतम) मान को खोजने की समस्या कहा जाता है, जहां वे। केवल समानता (5.3) के रूप में प्रतिबंध और सभी डिज़ाइन पैरामीटर गैर-नकारात्मकता की स्थिति को संतुष्ट करते हैं, और असमानताओं के रूप में कोई शर्तें नहीं हैं:

,

.

विहित एलपी समस्या को मैट्रिक्स और वेक्टर रूप में भी लिखा जा सकता है।

विहित एलपी समस्या के मैट्रिक्स रूप में निम्नलिखित रूप हैं:

विहित LP समस्या का सदिश रूप।

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

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

नोट डाउनलोड करें , प्रारूप में चित्र

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

शायद गणितीय मॉडल का निर्माण रैखिक प्रोग्रामिंग का सबसे कठिन हिस्सा है, जिसके लिए विचाराधीन समस्या को चर, समीकरणों और असमानताओं की एक प्रणाली में अनुवाद की आवश्यकता होती है - एक प्रक्रिया जो अंततः कौशल, अनुभव, क्षमताओं और अंतर्ज्ञान पर निर्भर करती है। मॉडल का कंपाइलर।

रैखिक प्रोग्रामिंग के गणितीय मॉडल के निर्माण के एक उदाहरण पर विचार करें

निकोलाई कुज़नेत्सोव एक छोटा यांत्रिक संयंत्र चलाता है। अगले महीने, वह दो उत्पादों (ए और बी) का उत्पादन करने की योजना बना रहा है, जिसके लिए विशिष्ट सीमांत लाभ क्रमशः 2,500 और 3,500 रूबल का अनुमान है।

दोनों उत्पादों के निर्माण के लिए मशीनिंग, कच्चे माल और श्रम की लागत की आवश्यकता होती है (चित्र 1)। उत्पाद ए की प्रत्येक इकाई के निर्माण के लिए 3 घंटे मशीन प्रसंस्करण, 16 यूनिट कच्चा माल और 6 यूनिट श्रम आवंटित किया जाता है। यूनिट बी के लिए संबंधित आवश्यकताएं 10, 4 और 6 हैं। निकोलाई ने भविष्यवाणी की है कि अगले महीने वह 330 घंटे मशीनिंग, 400 यूनिट कच्चे माल और 240 यूनिट श्रम प्रदान कर सकता है। उत्पादन प्रक्रिया की तकनीक ऐसी है कि किसी भी महीने में उत्पाद बी की कम से कम 12 इकाइयों का उत्पादन किया जाना चाहिए।

चावल। 1. संसाधनों का उपयोग और प्रावधान

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

रैखिक मॉडल चार चरणों में बनाया जा सकता है।

चरण 1. चर की परिभाषा

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

Z = उत्पादों ए और बी के उत्पादन के परिणामस्वरूप अगले महीने में प्राप्त कुल सीमांत लाभ (रूबल में)।

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

x 1 = अगले महीने में उत्पादित उत्पाद A की इकाइयों की संख्या।

x 2 = अगले महीने में उत्पादित उत्पाद B की इकाइयों की संख्या।

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

मंच। 2. उद्देश्य समारोह का निर्माण

एक उद्देश्य फ़ंक्शन एक रैखिक समीकरण है जिसे या तो अधिकतम या न्यूनतम किया जाना चाहिए। इसमें वांछित चर के रूप में व्यक्त लक्ष्य चर शामिल है, अर्थात Z को x 1 , x 2 ... के रूप में एक रैखिक समीकरण के रूप में व्यक्त किया जाता है।

हमारे उदाहरण में, प्रत्येक निर्मित उत्पाद ए 2500 रूबल लाता है। सीमांत लाभ, और उत्पाद ए की x 1 इकाइयों के निर्माण में, सीमांत लाभ 2500 * x 1 होगा। इसी तरह, उत्पाद बी की x 2 इकाइयों के निर्माण से सीमांत लाभ 3500 * x 2 होगा। इस प्रकार, उत्पाद A की x 1 इकाइयों और उत्पाद B की x 2 इकाइयों के उत्पादन के कारण अगले महीने में प्राप्त कुल सीमांत लाभ, यानी लक्ष्य चर Z होगा:

जेड = 2500 * x 1 + 3500 * x 2

निकोले इस सूचक को अधिकतम करना चाहता है। इस प्रकार, हमारे मॉडल में उद्देश्य कार्य है:

अधिकतम Z = 2500 * x 1 + 3500 * x 2

मंच। 3. प्रतिबंधों की परिभाषा

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

हमारे उदाहरण में, उत्पादों ए और बी को उत्पादन के लिए प्रसंस्करण समय, कच्चे माल और श्रम की आवश्यकता होती है, और इन संसाधनों की उपलब्धता सीमित है। इन दो उत्पादों के उत्पादन की मात्रा (अर्थात 2 का x 1 मान) इस प्रकार इस तथ्य से सीमित होगी कि उत्पादन प्रक्रिया में आवश्यक संसाधनों की मात्रा उपलब्ध से अधिक नहीं हो सकती है। मशीन प्रसंस्करण समय के साथ स्थिति पर विचार करें। उत्पाद ए की प्रत्येक इकाई के उत्पादन के लिए तीन घंटे की मशीन प्रसंस्करण की आवश्यकता होती है, और यदि x 1 इकाइयों का उत्पादन किया जाता है, तो इस संसाधन के 3 * x 1 घंटे खर्च किए जाएंगे। उत्पाद B की प्रत्येक इकाई के उत्पादन के लिए 10 घंटे की आवश्यकता होती है और इसलिए, यदि x 2 उत्पादों का उत्पादन किया जाता है, तो 10 * x 2 घंटे की आवश्यकता होगी। इस प्रकार, उत्पाद A की x 1 इकाइयों और उत्पाद B की x 2 इकाइयों के उत्पादन के लिए आवश्यक मशीन समय की कुल मात्रा 3 * x 1 + 10 * x 2 है। यह कुल मशीन समय 330 घंटे से अधिक नहीं हो सकता। गणितीय रूप से, यह इस प्रकार लिखा गया है:

3 * x 1 + 10 * x 2 330

इसी तरह के विचार कच्चे माल और श्रम पर लागू होते हैं, जिससे दो और प्रतिबंधों को लिखा जा सकता है:

16 * x 1 + 4 * x 2 400

6 * x 1 + 6 * x 2 240

अंत में, यह ध्यान दिया जाना चाहिए कि एक शर्त है जिसके अनुसार उत्पाद बी की कम से कम 12 इकाइयों का निर्माण किया जाना चाहिए:

चरण 4. गैर-नकारात्मकता की शर्तें लिखना

आवश्यक चर ऋणात्मक संख्या नहीं हो सकते हैं, जिन्हें असमानताओं x 1 0 और x 2 0 के रूप में लिखा जाना चाहिए। हमारे उदाहरण में, दूसरी शर्त बेमानी है, क्योंकि यह ऊपर निर्धारित किया गया था कि x 2 12 से कम नहीं हो सकता।

निकोलाई की उत्पादन समस्या के लिए पूर्ण रैखिक प्रोग्रामिंग मॉडल को इस प्रकार लिखा जा सकता है:

अधिकतम करें: Z = 2500 * x 1 + 3500 * x 2

बशर्ते कि: 3 * x 1 + 10 * x 2 330

16 * x 1 + 4 * x 2 400

6 * x 1 + 6 * x 2 240

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

यह विधि केवल दो आवश्यक चर वाली समस्याओं के लिए उपयुक्त है। विधि को प्रदर्शित करने के लिए ऊपर निर्मित मॉडल का उपयोग किया जाएगा।

ग्राफ पर कुल्हाड़ियां दो अज्ञात चरों को दर्शाती हैं (चित्र 2)। इससे कोई फर्क नहीं पड़ता कि किस चर को किस अक्ष के साथ प्लॉट करना है। एक पैमाना चुनना महत्वपूर्ण है जो अंततः आपको एक दृश्य आरेख बनाने की अनुमति देगा। चूंकि दोनों चर गैर-ऋणात्मक होने चाहिए, केवल पहला चतुर्थांश खींचा जाता है।

चावल। 2. रैखिक प्रोग्रामिंग ग्राफ अक्ष

उदाहरण के लिए, पहली बाधा पर विचार करें: 3 * x 1 + 10 * x 2 330। यह असमानता रेखा के नीचे के क्षेत्र का वर्णन करती है: 3 * x 1 + 10 * x 2 = 330। यह रेखा x-अक्ष 1 को काटती है। x 2 \u003d 0 पर, अर्थात्, समीकरण इस तरह दिखता है: 3 * x 1 + 10 * 0 \u003d 330, और इसका समाधान: x 1 \u003d 330 / 3 \u003d 110

इसी तरह, हम सभी बाधा स्थितियों के लिए x 1 और x 2 अक्षों के साथ प्रतिच्छेदन बिंदुओं की गणना करते हैं:

स्वीकार्य सीमा	अनुमत मानों की सीमा	x-अक्ष के साथ प्रतिच्छेदन 1	x-अक्ष के साथ प्रतिच्छेदन 2
3 * x 1 + 10 * x 2 330	3 * x 1 + 10 * x 2 = 330	एक्स 1 = 110; एक्स 2 = 0	एक्स 1 = 0; एक्स 2 = 33
16 * x 1 + 4 * x 2 400	16 * x 1 + 4 * x 2 = 400	एक्स 1 = 25; एक्स 2 = 0	एक्स 1 = 0; एक्स 2 = 100
6 * x 1 + 6 * x 2 240	6 * x 1 + 6 * x 2 = 240	एक्स 1 = 40; एक्स 2 = 0	एक्स 1 = 0; एक्स 2 = 40
एक्स 2 12	एक्स 2 = 12	पार नहीं करता; x-अक्ष के समानांतर चलता है 1	एक्स 1 = 0; एक्स 2 = 12

ग्राफिक रूप से, पहली सीमा अंजीर में दिखाई गई है। 3.

चावल। 3. पहली बाधा के लिए व्यवहार्य समाधान के क्षेत्र का निर्माण

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

इसी तरह, हम चार्ट पर बाकी प्रतिबंधों को दर्शाते हैं (चित्र 4)। मान x 1 और x 2 छायांकित क्षेत्र पर या उसके अंदर ABCDE सभी मॉडल बाधाओं का अनुपालन करेगा। ऐसे क्षेत्र को स्वीकार्य समाधानों का क्षेत्र कहा जाता है।

चावल। 4. समग्र रूप से मॉडल के लिए व्यवहार्य समाधान का क्षेत्र

अब, व्यवहार्य समाधान के क्षेत्र में, x 1 और x 2 के मानों को निर्धारित करना आवश्यक है जो Z को अधिकतम करते हैं। ऐसा करने के लिए, उद्देश्य फ़ंक्शन समीकरण में:

जेड = 2500 * x 1 + 3500 * x 2

हम x 1 और x 2 से पहले के गुणांकों को समान संख्या से विभाजित (या गुणा) करते हैं, ताकि परिणामी मान ग्राफ़ पर दिखाई गई सीमा में आ जाएं; हमारे मामले में, ऐसी सीमा 0 से 120 तक है; इसलिए गुणांकों को 100 (या 50) से विभाजित किया जा सकता है:

जेड = 25x 1 + 35x 2

फिर Z को x 1 और x 2 (25 * 35 = 875) से पहले गुणांक के गुणनफल के बराबर मान दें:

875 = 25x 1 + 35x 2

और, अंत में, अक्ष x 1 और x 2 के साथ रेखा के प्रतिच्छेदन बिंदु खोजें:

आइए इस लक्ष्य समीकरण को ग्राफ़ पर उसी तरह से प्लॉट करें जैसे कि बाधाएं (चित्र 5):

चावल। 5. व्यावहारिक समाधान के क्षेत्र में उद्देश्य फ़ंक्शन (काली बिंदीदार रेखा) का अनुप्रयोग

Z मान पूरे ऑब्जेक्टिव फंक्शन लाइन में स्थिर रहता है। Z को अधिकतम करने वाले मान x 1 और x 2 को खोजने के लिए, आपको स्वीकार्य समाधान के क्षेत्र की सीमाओं के भीतर उद्देश्य फ़ंक्शन की रेखा को समानांतर रूप से ऐसे बिंदु पर स्थानांतरित करने की आवश्यकता है, जो अधिकतम पर स्थित है उद्देश्य फ़ंक्शन की मूल रेखा से ऊपर और दाईं ओर, यानी बिंदु C (चित्र 6) से दूरी।

चावल। 6. उद्देश्य फलन की रेखा व्यवहार्य समाधानों के क्षेत्र में अपने अधिकतम स्तर पर पहुंच गई है (बिंदु C पर)

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

आइए, उदाहरण के लिए, बिंदु C पर x 1 और x 2 के मान निर्धारित करें। ध्यान दें कि बिंदु C, रेखाओं के प्रतिच्छेदन पर है: 3x 1 + 10x 2 = 330 और 6x 1 + 6x 2 = 240। समीकरणों की इस प्रणाली का समाधान देता है: x 1 = 10, x 2 = 30। व्यवहार्य समाधान के क्षेत्र के सभी शीर्षों के लिए गणना परिणाम तालिका में दिए गए हैं:

दूरसंचार विभाग	मान x 1	मान x 2	जेड \u003d 2500x 1 + 3500x 2
लेकिन	22	12	97 000
पर	20	20	120 000
साथ में	10	30	130 000
डी	0	33	115 500
इ	0	12	42 000

इस प्रकार, निकोलाई कुज़नेत्सोम को अगले महीने के लिए 10 आइटम ए और 30 आइटम बी के उत्पादन की योजना बनानी चाहिए, जिससे उसे 130 हजार रूबल का मामूली लाभ प्राप्त होगा।

संक्षेप में, रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए चित्रमय पद्धति का सार संक्षेप में प्रस्तुत किया जा सकता है:

1. दो निर्णय मापदंडों का प्रतिनिधित्व करने वाले ग्राफ़ पर दो अक्ष बनाएं; केवल पहला चतुर्थांश ड्रा करें।
2. कुल्हाड़ियों के साथ सभी सीमा स्थितियों के चौराहे के बिंदुओं के निर्देशांक निर्धारित करें, मूल्यों को x 1 = 0 और x 2 = 0 को बदले में सीमा स्थितियों के समीकरणों में प्रतिस्थापित करें।
3. चार्ट पर मॉडल बाधा रेखाएं बनाएं।
4. ग्राफ पर उस क्षेत्र का निर्धारण करें (जिसे स्वीकार्य निर्णय क्षेत्र कहा जाता है) जो सभी बाधाओं को पूरा करता है। यदि ऐसा कोई क्षेत्र नहीं है, तो मॉडल का कोई समाधान नहीं है।
5. निर्णय क्षेत्र के चरम बिंदुओं पर वांछित चर के मूल्यों को निर्धारित करें, और प्रत्येक मामले में लक्ष्य चर Z के संबंधित मान की गणना करें।
6. अधिकतमकरण समस्याओं के लिए, समाधान वह बिंदु है जिस पर Z अधिकतम है; न्यूनीकरण समस्याओं के लिए, समाधान वह बिंदु है जिस पर Z न्यूनतम है।

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

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

विकल्प संख्या 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

ज़रूरत