समाधान: निम्नलिखित बाधाओं के तहत फ़ंक्शन \(f (x, y)\) का अधिकतम और न्यूनतम मान ज्ञात करें $$ f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow अधिकतम, न्यूनतम \ \ \begin(मामलों) 2x+3y\geq 6 \\ 3x-2y\leq 18\\ -x+2y\leq 8\\ x,y\geq0\end(मामलों) $$
ग्राफिकल तरीकासमस्या के समाधान का उपयोग दो चर के साथ समस्याओं के समाधान के लिए किया जाता है जो एक सममित रूप में लिखे गए हैं, साथ ही साथ कई चर के साथ समस्याओं के लिए, बशर्ते कि उनके विहित संकेतन में दो से अधिक मुक्त चर न हों।

इस मामले में, दो चर के साथ एक कार्य।

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

1. आइए xOy तल पर स्वीकार्य विलयनों के प्रांत की रचना करें।
2. गैर-ऋणात्मक समाधानों के क्षेत्र का चयन करें।

4. आइए वस्तुनिष्ठ फलनों के एक परिवार की रचना करें।
5. अधिकतम (न्यूनतम) मान ज्ञात करें वस्तुनिष्ठ कार्य.

1. हम समस्या के स्वीकार्य समाधान \(D\) के डोमेन की रचना करते हैं।

व्यवहार्य समाधान के क्षेत्र का निर्माण करने के लिए:
1) हम सीमा रेखाएँ बनाते हैं:
हम असमानताओं को समानता में बदलते हैं, और फिर \(\frac(x)(a)+\frac(y)(b) = 1\) के रूप के अक्षों पर खंडों में एक सीधी रेखा के समीकरण में बदलते हैं, फिर \ (x=a\) ऑक्स अक्ष पर कटा हुआ एक खंड है, \(y=b\) - ओए अक्ष पर $$ \begin(cases) 2x+3y = 6 \\ 3x-2y = 18\\ - x+2y = 8 \end(केस) => \begin(cases) \frac(x)(3)+\frac(y)(2) = 1 \\ \frac(x)(8)-\frac( y)(9) = 1 \\ -\frac (x)(6)+ \frac(y)(4) = 1 \end(cases) $$ प्रत्येक पंक्ति के लिए, अक्षों पर खंडों को अलग रखें और उन्हें कनेक्ट करें। हमें सही लाइनें मिलीं।

2) हम अर्ध-तल पाते हैं जो दी गई असमानताओं को संतुष्ट करते हैं:
असमानता के लिए \(2x+3y\geq 6\) आधा तल है जो रेखा \(2x+3y = 6\) के ऊपर स्थित है। डायरेक्ट एसी
असमानता के लिए \(3x-2y\leq 18 => -3x+2y \geq -18\) एक अर्ध-तल है जो रेखा \(3x-2y = 18\) के ऊपर स्थित है। प्रत्यक्ष सीबी
असमानता के लिए \(-x+2y\leq 8\) आधा तल है जो रेखा \(-x+2y = 8\) के नीचे स्थित है। डायरेक्ट एबी

व्यवहार्य समाधानों के क्षेत्र को दी गई असमानताओं के अनुरूप तीन अर्ध-तलों के सामान्य भाग के रूप में परिभाषित किया गया है। यह क्षेत्र एक त्रिभुज है \(ABC\)

क्षेत्र \(D\) त्रिभुज है \(ABC\) अंजीर देखें।

2. गैर-ऋणात्मक समाधानों के क्षेत्र का चयन करें।

गैर-नकारात्मक समाधानों का क्षेत्र पहली तिमाही में स्थित है और सभी पांच अर्ध-तलों का एक सामान्य हिस्सा है, जिनमें से तीन क्षेत्र \(D\) हैं, जो असमानताओं से प्राप्त होते हैं, और इसके अतिरिक्त दो असमानताएं \(x \geq 0\) - ऊपरी आधा-तल (I और II क्वार्टर) और \(y \geq 0\) - दायां आधा-तल (I और IV क्वार्टर), जो चर की गैर-नकारात्मकता की स्थिति को व्यक्त करते हैं \( एक्स; वाई \)। गैर-नकारात्मक समाधानों का वांछित क्षेत्र प्राप्त किया \(DEBFG\)

3. क्षेत्र के शीर्षों के निर्देशांक ज्ञात कीजिए।
चार शीर्षों के निर्देशांक पहले से ही ज्ञात हैं (ये अक्षों के साथ रेखाओं के प्रतिच्छेदन बिंदु हैं)।
आइए इन निर्देशांकों को लिखें:
\(D(0;2)\), \(E(0;4)\), \(F(6;0)\), \(G(3;0)\)
बिंदु \(B\) के निर्देशांकों को \(-x+2y = 8\) और \(3x-2y = 18\) रेखाओं के प्रतिच्छेदन बिंदुओं के रूप में खोजें। समीकरणों की प्रणाली को हल करें और इस बिंदु के निर्देशांक खोजें $$\begin(cases) -x+2y = 8\\ 3x-2y = 18\end(cases)=> \begin(cases) 2x = 26\\ 3x -2y = 18 \end(मामलों)=> \begin(मामलों) x = 13\\ y = 10.5\end(मामलों)$$
हमें बिंदु के निर्देशांक मिले \(B(13;10.5)\)

4. हम वस्तुनिष्ठ कार्यों का एक परिवार बनाते हैं।
समीकरण \(f(x,y)=(x-4)^2 + (y-3)^2 \rightarrow max,min\) xOy तल पर निर्देशांक के साथ बिंदु पर केंद्रित संकेंद्रित वृत्तों के परिवार को परिभाषित करता है \ (Q(4;3)\), जिनमें से प्रत्येक पैरामीटर \(f\) के एक निश्चित मान से मेल खाता है। जैसा कि आप जानते हैं, एक वृत्त के समीकरण के लिए पैरामीटर \(f=R^2\)।

आइए हम एक ही समन्वय प्रणाली में संकेंद्रित वृत्तों के एक परिवार \(f\) और रेखाओं के एक परिवार का प्रतिनिधित्व करते हैं। बिंदु \(f\) के अधिकतम (न्यूनतम) बिंदु को निर्धारित करने की समस्या स्वीकार्य क्षेत्र में उस बिंदु को खोजने के लिए कम हो जाएगी जिसके माध्यम से परिवार का चक्र \(f=const\) गुजरता है, जो इसके लिए जिम्मेदार है पैरामीटर \(f\) का सबसे बड़ा (सबसे छोटा) मान।

5. उद्देश्य फलन का अधिकतम (न्यूनतम) मान ज्ञात कीजिए।

न्यूनतम उद्देश्य फ़ंक्शन मान: वृत्त की त्रिज्या को धीरे-धीरे बढ़ाते हुए, हमने प्राप्त किया है कि वृत्त जिस प्रथम शीर्ष से होकर गुजरता है वह बिंदु \(G(3;0)\) है। इस बिंदु पर उद्देश्य कार्य न्यूनतम और बराबर होगा \(f(3,0)=(3-4)^2 + (0-3)^2 = 10\)

उद्देश्य समारोह का अधिकतम मूल्य: वृत्त की त्रिज्या को और बढ़ाकर, हमने प्राप्त किया है कि वृत्त जिस अंतिम शीर्ष से होकर गुजरेगा वह बिंदु \(B(13;10.5)\) है। इस बिंदु पर उद्देश्य फलन अधिकतम और बराबर होगा \(f(13,10.5)=(13-4)^2 + (10.5-3)^2 = 137.25\)

आप उद्देश्य फलन समीकरण में शेष शीर्षों के निर्देशांकों को प्रतिस्थापित करके समाधान की शुद्धता को सत्यापित कर सकते हैं:
शीर्ष पर \(D(0;2)\) उद्देश्य फलन का मान \(f(0,2)=(0-4)^2 + (2-3)^2 = 17\) के बराबर है
शीर्ष पर \(E(0;4)\) उद्देश्य फलन का मान \(f(0,4)=(0-4)^2 + (4-3)^2 = 17\) के बराबर है
शीर्ष पर \(F(6;0)\) उद्देश्य फलन का मान है \(f(6,4)=(6-4)^2 + (0-3)^2 = 13\)
मिला क्या

उत्तर:
उद्देश्य फलन का न्यूनतम मान \(f_(min) = 10\)
उद्देश्य फलन का अधिकतम मान \(f_(अधिकतम) = 137.25\)

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

उदाहरण

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

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

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

ध्यान!

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

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

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

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

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

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

समाधान:

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

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

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

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

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

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

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

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

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

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

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

3 x 1 - x 2 0;

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

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

समाधान:

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

3 x1 - x2 = 0;

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

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

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

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

मिनट = 4 + 0 = 4।

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

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

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

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

2 x 1 + x 2 16;

एक्स 2 5;

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

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

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

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

3 x 1 = 21 (4)।

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

मूल कार्य।

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

y1 + y2 + y3 ≥ 0,

वाई 3 ≥ 0,

2× y2 ≥ 1,

Y2 ≥ 0,

वाई 3 ≥ 0.

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

एक्स 0 वाई ≥ 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

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

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

+ 11 x 3 - 15 x 4 \u003d 10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

समाधान:

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

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

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

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

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

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

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

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

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

तालिका 2

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

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

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

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

हम तीसरी पंक्ति को 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 पर पहुंच जाती है);

संघीय संस्थाशिक्षा का

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

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

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

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

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

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

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

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

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

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

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

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