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

12.1 परिचय

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

एक फर्नीचर डीलर केवल दो वस्तुओं - टेबल और चेयर में व्यापार करता है। वह 50,000 रुपये निवेश करने के लिए तैयार है और अधिकतम 60 टुकड़ों के लिए भंडारण स्थान रखता है। एक टेबल की कीमत 2500 रुपये है और एक चेयर की कीमत 500 रुपये है। वह अनुमानित करता है कि एक टेबल की बिक्री से, वह 250 रुपये का लाभ कमा सकता है और एक चेयर की बिक्री से 75 रुपये का लाभ कमा सकता है। वह यह जानना चाहता है कि उपलब्ध धन से वह कितने टेबल और चेयर खरीदना चाहता है ताकि वह अपना कुल लाभ अधिकतम कर सके, अनुमानित करते हुए कि वह उस सभी वस्तुओं को बेच सकता है जिन्हें वह खरीदता है।

ऐसी प्रकार की समस्याएं जो लाभ (या लागत) को अधिकतम (या न्यूनतम) करने की कोशिश करती हैं, एक सामान्य प्रकार की समस्याओं के रूप में कल्पना की जाती है जिन्हें अनुकूलनीय समस्याएं कहते हैं। अतः, एक अनुकूलनीय समस्या में अधिकतम लाभ, न्यूनतम लागत या न्यूनतम संसाधनों का उपयोग आदि जैसे कुछ चीजों को खोजना शामिल हो सकता है।

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

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

12.2 रैखिक प्रोग्रामिंग समस्या और उसका गणितीय रूपांतरण

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

(एक) डीलर अपने धन को टेबल, चेयर या उनके संयोजन में निवेश कर सकता है। इसके अतिरिक्त, वह विभिन्न निवेश रणनीतियों का पालन करके विभिन्न लाभ कमा सकता है।

(दो) कुछ अतिरिक्त शर्तें या प्रतिबंध हैं, जैसे, उसका निवेश अधिकतम 50,000 रुपये तक सीमित है और उसका भंडारण स्थान भी अधिकतम 60 टुकड़ों तक है।

मान लीजिए वह केवल टेबल खरीदने का निर्णय लेता है और कोई चेयर नहीं, तो वह 13, अर्थात् 20 टेबल खरीद सकता है। इस मामले में उसका लाभ 14, अर्थात् 15 रुपये होगा।

मान लीजिए वह केवल चेयर खरीदने का चुनौती लेता है और कोई टेबल नहीं। अपने 50,000 रुपये के पूंजी के साथ, वह 16, अर्थात् 100 चेयर खरीद सकता है। लेकिन वह केवल 60 टुकड़े भंडारण कर सकता है। इस प्रकार, वह केवल 60 चेयर खरीदने को मजबूर होता है जो उसे कुल 4500 रुपये का लाभ देगा।

कई अन्य संभावनाएं हैं, उदाहरण के लिए, वह 60 टुकड़ों के लिए भंडारण कर सकता है, इसलिए वह 10 टेबल और 50 चेयर चुन सकता है। इस मामले में कुल लाभ 18, अर्थात् 19 रुपये होगा और इसी तरह।

हम इस प्रकार पाते हैं कि डीलर अपने धन को विभिन्न तरीकों से निवेश कर सकता है और विभिन्न निवेश रणनीतियों का पालन करके विभिन्न लाभ कमा सकता है।

अब समस्या यह है: वह अपने धन को कैसे निवेश करना चाहिए ताकि वह अधिकतम लाभ प्राप्त कर सके? इस प्रश्न का उत्तर देने के लिए, आइए समस्या को गणितीय रूप में रूपांतरित करने का प्रयास करें।

12.2.1 समस्या का गणितीय रूपांतरण

मान लीजिए $x$ डीलर द्वारा खरीदे जाने वाले टेबलों की संख्या और $y$ चेयरों की संख्या है। स्पष्ट रूप से, $x$ और $y$ गैर-नकारात्मक होने चाहिए, अर्थात्,

$$ \begin{align*} & x \geq 0 \tag{1}\\ & y \geq 0 \tag{2} \end{align*} \text { (Non-negative constraints) } $$

डीलर उस अधिकतम राशि और उस अधिकतम सामान की सीमा से प्रतिबंधित है जिसे वह निवेश कर सकता है (यहां यह 50,000 रुपये है) और जिसे वह भंडारण कर सकता है (यहां यह 60 है)।

गणितीय रूप में कहा जाता है,

या $$ \begin{array}{rlrl} 2500 x+500 y & \leq 50,000 & \text { (investment constraint ) } \\ 5 x+y & \leq 100 & & \\ x+y & \leq 60 & & \text { (storage constraint) } \tag{4} \end{array} $$

डीलर ऐसी भागीदारी करना चाहता है ताकि उसका लाभ अधिकतम हो, अगर उसका लाभ $Z$ है, जो $x$ और $y$ के अनुक्रम में एक फलन के रूप में दिया गया है

$Z=250 x+75 y$ (लक्षित फलन कहलाता है)

गणितीय रूप में, दी गई समस्याएं अब इस प्रकार घटित हो गई हैं:

$Z=250 x+75 y$ को अधिकतम करें

शर्तों के अधीन:

$$ \begin{aligned} 5 x+y & \leq 100 \\ x+y & \leq 60 \\ x \geq 0, y & \geq 0 \end{aligned} $$

इस प्रकार, हमें $Z$ को अधिकतम करना है जो कि कुछ शर्तों द्वारा निर्धारित एक समूह के रैखिक असमानताओं के साथ चरों के गैर-नकारात्मक होने के बावजूद एक रैखिक फलन है। कुछ अन्य समस्याओं में हमें एक रैखिक फलन को न्यूनतम करना होता है जो कि चरों के गैर-नकारात्मक होने और एक समूह के रैखिक असमानताओं द्वारा निर्धारित कुछ शर्तों के अधीन है। ऐसी समस्याएं रैखिक प्रोग्रामिंग समस्याओं कहलाती हैं।

अतः, एक रैखिक प्रोग्रामिंग समस्या ऐसी समस्या है जो कई चरों (जैसे $x$ और $y$) के एक रैखिक फलन (जिसे लक्षित फलन कहते हैं) के अभिप्रेत अभिकल्पित मान (अधिकतम या न्यूनतम मान) को खोजने से संबंधित है, चरों की शर्त गैर-नकारात्मक होनी चाहिए और एक समूह के रैखिक असमानताओं (जिन्हें रैखिक प्रतिबंध कहते हैं) को पूरा करना चाहिए। शब्द रैखिक अर्थात् समस्या में उपयोग किए गए सभी गणितीय संबंध रैखिक संबंध हैं, जबकि शब्द प्रोग्रामिंग किसी विशेष कार्यक्रम या कार्य योजना को निर्धारित करने की विधि को संदर्भित करता है।

हम आगे बढ़ने से पहले, हम अब उन शब्दों (जो ऊपर उपयोग किए गए हैं) की आधिकारिक परिभाषा पर चर्चा करेंगे जिन्हें हम रैखिक प्रोग्रामिंग समस्याओं में उपयोग करेंगे:

लक्षित फलन $Z=a x+b y$ का एक रैखिक फलन, जहां $a, b$ फिर एक फलन है जिसे अधिकतम या न्यूनतम करना होता है, को एक रैखिक लक्षित फलन कहते हैं।

उपरोक्त उदाहरण में, $Z=250 x+75 y$ एक रैखिक लक्षित फलन है। चर $x$ और $y$ निर्णय चर कहलाते हैं।

प्रतिबंध रैखिक प्रोग्रामिंग समस्या में चरों पर प्रयुक्त रैखिक असमानताओं या समीकरणों या प्रतिबंधों को प्रतिबंध कहते हैं। शर्त $x \geq 0, y \geq 0$ गैर-नकारात्मक प्रतिबंध कहलाती हैं। उपरोक्त उदाहरण में, असमानताओं (1) से (4) का समूह प्रतिबंध हैं।

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

अब हम रैखिक प्रोग्रामिंग समस्याओं के समाधान कैसे प्राप्त करेंगे इस पर चर्चा करेंगे। इस अध्याय में, हम केवल आलेखी विधि पर चर्चा करेंगे।

12.2.2 रैखिक प्रोग्रामिंग समस्याओं को हल करने की आलेखी विधि

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

$$ \begin{align*} 5 x+y & \leq 100 \tag{1} \\ x+y & \leq 60 \tag{2} \\ x & \geq 0 \tag{3} \\ y & \geq 0 \tag{4} \end{align*} $$

इस प्रणाली (सादे क्षेत्र में) का आलेख इन असमानताओं (1) से (4) द्वारा निर्धारित सभी अर्ध आकृतियों के लिए एक ही क्षेत्र का आलेख है (आकृति 12.1)। इस क्षेत्र के प्रत्येक बिंदु टेबल और चेयर में निवेश के लिए डीलर के लिए एक उपयुक्त विकल्प का प्रतिनिधित्व करता है। इस प्रकार, यह क्षेत्र समस्या के लिए उपयुक्त क्षेत्र कहलाता है। इस क्षेत्र का प्रत्येक बिंदु समस्या का एक उपयुक्त समाधान कहलाता है। इस प्रकार, हमें मिलता है,

आकृति 12.1

उपयुक्त क्षेत्र एक रैखिक प्रोग्रामिंग समस्या के सभी प्रतिबंधों जिसमें गैर-नकारात्मक प्रतिबंध $x, y \geq 0$ शामिल हैं, द्वारा निर्धारित सामान्य क्षेत्र (या समाधान क्षेत्र) को उपयुक्त क्षेत्र कहते हैं। आकृति 12.1 में, क्षेत्र OABC (सादा) समस्या के लिए उपयुक्त क्षेत्र है। उपयुक्त क्षेत्र के अलावा कोई भी क्षेत्र अनुपयुक्त क्षेत्र कहलाता है।

उपयुक्त समाधान उपयुक्त क्षेत्र के भीतर और उसकी सीमा पर बिंदुओं को प्रतिबंधों के उपयुक्त समाधान का प्रतिनिधित्व करते हैं। आकृति 12.1 में, उपयुक्त क्षेत्र $OABC$ के भीतर और उसकी सीमा पर प्रत्येक बिंदु समस्या के लिए उपयुक्त समाधान का प्रतिनिधित्व करती है। उदाहरण के लिए, $(10,50)$ समस्या का एक उपयुक्त समाधान है और इसी तरह $(0,60),(20,0)$ आदि भी।

उपयुक्त क्षेत्र के बाहर कोई भी बिंदु अनुपयुक्त समाधान कहलाता है। उदाहरण के लिए, $(25,40)$ समस्या का एक अनुपयुक्त समाधान है।

अभिकल्पित (उपयुक्त) समाधान: लक्षित फलन के अभिकल्पित मान (अधिकतम या न्यूनतम) को देने वाला उपयुक्त क्षेत्र का कोई भी बिंदु अभिकल्पित (उपयुक्त) समाधान कहलाता है।

अब, हम देखते हैं कि $OABC$ के उपयुक्त क्षेत्र के प्रत्येक बिंदु प्रदान किए गए (1) से (4) में सभी प्रतिबंधों को पूरा करता है, और क्योंकि अनंत संख्या में बिंदुओं हैं, इसलिए यह स्पष्ट नहीं है कि हम उस बिंदु को कैसे प्राप्त करना चाहिए जो लक्षित फलन $Z=250 x+75 y$ के अधिकतम मान को देता है। इस स्थिति को संभालने के लिए, हम निम्नलिखित प्रमाणों का उपयोग करते हैं जो रैखिक प्रोग्रामिंग समस्याओं को हल करने में मौलिक रूप से सहायता करते हैं। इन प्रमाणों के दोहराव पुस्तक के परिदृश्य के पार हैं।

प्रमाण 1 मान लीजिए $R$ एक रैखिक प्रोग्रामिंग समस्या के लिए उपयुक्त क्षेत्र (उत्तल बहुभुज) है और $Z=a x+b y$ लक्षित फलन है। जब $Z$ के पास एक अभिकल्पित मान (अधिकतम या न्यूनतम) होता है, जहां $x$ और $y$ चर रैखिक असमानताओं द्वारा वर्णित प्रतिबंधों के अधीन हैं, तो यह अभिकल्पित मान उपयुक्त क्षेत्र के एक कोने बिंदु (शीर्ष) पर होना चाहिए।

प्रमाण 2 मान लीजिए $R$ एक रैखिक प्रोग्रामिंग समस्या के लिए उपयुक्त क्षेत्र है, और $Z=a x+b y$ लक्षित फलन है। यदि $R$ सीमित है**, तो लक्षित फलन $Z$ पर $R$ पर दोनों अधिकतम और न्यूनतम मान प्राप्त होते हैं और इनमें से प्रत्येक कोने बिंदु (शीर्ष) पर $R$ पर होता है।

टिप्पणी यदि $R$ असीमित है, तो लक्षित फलन के अधिकतम या न्यूनतम मान के लिए एक मान मौजूद नहीं हो सकता। हालांकि, यदि यह मौजूद होता है, तो यह उपयुक्त क्षेत्र के एक कोने बिंदु पर होना चाहिए। (प्रमाण 1 द्वारा)।

उपरोक्त उदाहरण में, सीमित (उपयुक्त) क्षेत्र के कोने बिंदुओं (शीर्ष) $O, A, B$ और $C$ हैं और उनके 좌표 $(0,0),(20,0),(10,50)$ और $(0,60)$ को आसानी से प्राप्त किया जा सकता है। अब हम $Z$ के इन बिंदुओं पर मूल्यांकन करेंगे।

हमें मिलता है

• उपयुक्त क्षेत्र का एक कोना बिंदु उस क्षेत्र का एक बिंदु है जो दो सीमा रेखाओं के प्रवेश बिंदु है।

• एक रैखिक असमानताओं के प्रणाली का एक उपयुक्त क्षेत्र तब सीमित कहा जाता है जब उसे एक वृत्त के भीतर घेरा जा सकता है। अन्यथा, यह असीमित कहलाता है। असीमित का अर्थ है कि उपयुक्त क्षेत्र किसी भी दिशा में अनंत रूप से बढ़ता रहता है।

हम देखते हैं कि डीलर का अधिकतम लाभ निवेश रणनीति $(10,50)$ से प्राप्त होता है, अर्थात् 10 टेबल और 50 चेयर खरीदना।

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

1. रैखिक प्रोग्रामिंग समस्या के उपयुक्त क्षेत्र को प्राप्त करें और उसके कोने बिंदुओं (शीर्ष) को देखकर या उस बिंदु पर प्रवेश करने वाली दो रेखाओं के समीकरणों को हल करके निर्धारित करें।

2. प्रत्येक कोने बिंदु पर लक्षित फलन $Z=a x+b y$ का मूल्यांकन करें। $\mathbf{M}$ और $m$, इन बिंदुओं के इन मानों के सबसे बड़ा और सबसे छोटा मान को संदर्भित करें।

3. (एक) जब उपयुक्त क्षेत्र सीमित हो, तो $M$ और $m$ $Z$ के अधिकतम और न्यूनतम मान होते हैं।

(दो) अगर, उपयुक्त क्षेत्र असीमित है, तो हमें मिलता है:

4. (एक) $M$ $Z$ का अधिकतम मान है, अगर $a x+b y>M$ द्वारा निर्धारित खुला अर्ध आकृति उपयुक्त क्षेत्र के साथ कोई बिंदु साझा नहीं करता है। अन्यथा, $Z$ का कोई अधिकतम मान नहीं है।

(बी) इसी प्रकार, $m$ $Z$ का न्यूनतम मान है, अगर $a x+b y<m$ द्वारा निर्धारित खुला अर्ध आकृति उपयुक्त क्षेत्र के साथ कोई बिंदु साझा नहीं करता है। अन्यथा, $Z$ का कोई न्यूनतम मान नहीं है।

हम अब इन कोने बिंदु विधि के इन चरणों को कुछ उदाहरणों के साथ स्पष्ट करेंगे:

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

$Z=4 x+y$ को अधिकतम करें शर्तों के अधीन:

$$ \begin{aligned} x+y & \leq 50 \\ 3 x+y & \leq 90 \\ x \geq 0, y & \geq 0 \end{aligned} $$

समाधान आकृति 12.2 में सादा क्षेत्र प्रतिबंधों (2) से (4) द्वारा निर्धारित प्रणाली के लिए उपयुक्त क्षेत्र है। हम देखते हैं कि उपयुक्त क्षेत्र OABC सीमित है। इसलिए, अब हम $Z$ के अधिकतम मान को निर्धारित करने के लिए कोने बिंदु विधि का उपयोग करते हैं।

कोने बिंदुओं $O, A, B$ और $C$ के 좌표 $(0,0),(30,0),(20,30)$ और $(0,50)$ हैं। अब हम प्रत्येक कोने बिंदु पर $Z$ का मूल्यांकन करते हैं।

आकृति 12.2

इस प्रकार, $Z$ का अधिकतम मान $(30,0)$ बिंदु पर 120 है।

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

$Z=200 x+500 y$ को न्यूनतम करें

शर्तों के अधीन:

$$ \begin{align*} x+2 y & \geq 10 \tag{1}\\ 3 x+4 y & \leq 24 \tag{2}\\ x \geq 0, y & \geq 0 \tag{3} \end{align*} $$

समाधान आकृति 12.3 में सादा क्षेत्र प्रतिबंधों (2) से (4) द्वारा निर्धारित प्रणाली के लिए उपयुक्त क्षेत्र ABC है, जो सीमित है। कोने बिंदुओं A, B और $C$ के 좌표 $(0,5),(4,3)$ और $(0,6)$ हैं। अब हम $Z=200 x+500 y$ का इन बिंदुओं पर मूल्यांकन करते हैं।

आकृति 12.3

इस प्रकार, $Z$ का न्यूनतम मान $(4,3)$ बिंदु पर 2300 प्राप्त होता है।

उदाहरण 3 आलेखी विधि द्वारा निम्नलिखित समस्या को हल करें:

$Z=3 x+9 y$ को न्यूनतम और अधिकतम करें

शर्तों के अधीन: $\quad x+3 y \leq 60$

$$ \begin{align*} x+3 y & \leq 60 \tag{1}\\ x+y & \geq 10 \tag{2}\\ x & \leq y \tag{3}\\ x \geq 0, y & \geq 0 \tag{4} \end{align*} $$

समाधान सबसे पहले, आइए रैखिक असमानताओं (2) से (5) के प्रणाली के उपयुक्त क्षेत्र को आलेखित करें। उपयुक्त क्षेत्र $ABCD$ आकृति 12.4 में दिखाया गया है। ध्यान दें कि क्षेत्र सीमित है। कोने बिंदुओं A, B, C और D के 좌표 $(0,10),(5,5),(15,15)$ और $(0,20)$ हैं।

आकृति 12.4

अब हम $Z$ के न्यूनतम और अधिकतम मान जानते हैं। तालिका से हमें पता चलता है कि $Z$ का न्यूनतम मान $B(5,5)$ बिंदु पर उपयुक्त क्षेत्र में 60 है।

उपयुक्त क्षेत्र पर $Z$ का अधिकतम मान दो कोने बिंदुओं $C(15,15)$ और $D(0,20)$ पर प्राप्त होता है और यह दोनों मामलों में 180 है।

टिप्पणी देखें कि उपरोक्त उदाहरण में, समस्या में $C$ और $D$ कोने बिंदुओं पर बहु-अभिकल्पित समाधान हैं, अर्थात् दोनों बिंदुओं एक समान अधिकतम मान 180 प्रदान करते हैं। ऐसे मामलों में, आप देख सकते हैं कि $C$ और $D$ को जोड़ने वाली रेखा स्तरीय खंड CD के प्रत्येक बिंदु भी एक समान अधिकतम मान प्रदान करता है। यह भी उसी प्रकार सत्य है अगर दो बिंदुओं एक समान न्यूनतम मान प्रदान करते हैं।

उदाहरण 4 आलेखी विधि द्वारा लक्षित फलन के न्यूनतम मान को निर्धारित करें

$$ Z=-50 x+20 y $$

शर्तों के अधीन:

$$ \begin{aligned} & 2 x-y \geq-5 \\ & 3 x+y \geq 3 \\ & 2 x-3 y \leq 12 \\ & x \geq 0, y \geq 0 \end{aligned} $$

समाधान सबसे पहले, आइए असमानताओं (2) से (5) के प्रणाली के उपयुक्त क्षेत्र को आलेखित करें। उपयुक्त क्षेत्र (सादा) आकृति 12.5 में दिखाया गया है। देखिए कि उपयुक्त क्षेत्र असीमित है।

अब हम $Z$ का कोने बिंदुओं पर मूल्यांकन करते हैं।

आकृति 12.5

इस तालिका से, हमें पता चलता है कि -300 $Z$ के कोने बिंदु $(6,0)$ पर $Z$ का सबसे छोटा मान है। क्या हम कह सकते हैं कि $Z$ का न्यूनतम मान -300 है? ध्यान दें कि अगर क्षेत्र सीमित होता, तो $Z$ का यह सबसे छोटा मान $Z$ का न्यूनतम मान होता (प्रमाण 2)। लेकिन यहां हम देखते हैं कि उपयुक्त क्षेत्र असीमित है। इसलिए, -300 $Z$ का न्यूनतम मान हो सकता है या नहीं। इस विषय को निर्धारित करने के लिए, हम असमानता को आलेखित करते हैं

$$ -50 x+20 y<-300 \text{ (see Step 3(ii) of corner Point Method.) } $$

अर्थात्, $$ -5 x+2 y<-30 $$

और जाँचते हैं कि परिणामी खुला अर्ध आकृति उपयुक्त क्षेत्र के साथ कोई बिंदु साझा करता है या नहीं। अगर यह कोई बिंदु साझा करता है, तो -300 $Z$ का न्यूनतम मान नहीं होगा। अन्यथा, -300 $Z=-50 x+20 y$ का न्यूनतम मान होगा।

जैसा कि आकृति 12.5 में दिखाया गया है, यह कोई बिंदु साझा करता है। इसलिए, $z=-50 x+20 y$ के दिए गए प्रतिबंधों के अधीन 100 का कोई न्यूनतम मान नहीं है।

उपरोक्त उदाहरण में, क्या आप कह सकते हैं कि $(0,5)$ पर $-50 x+20 y>100$ का अधिकतम मान 100 है? इसके लिए, जाँचें कि $-50 x+20 y>100$ का आलेख उपयुक्त क्षेत्र के साथ कोई बिंदु साझा करता है या नहीं। (क्यों?)

उदाहरण 5 $Z=3 x+2 y$ को न्यूनतम करें

शर्तों के अधीन:

$$ \begin{align*} x+y & \geq 8 \tag{1}\\ 3 x+5 y & \leq 15 \tag{2}\\ x \geq 0, y & \geq 0 \tag{3} \end{align*} $$

समाधान आइए असमानताओं (1) से (3) को आलेखित करें (आकृति 12.6)। क्या कोई उपयुक्त क्षेत्र है? क्यों यह ऐसा है?

आकृति 12.6 से आप देख सकते हैं कि सभी प्रतिबंधों को एक साथ पूरा करने वाला कोई भी बिंदु नहीं है। इस प्रकार, समस्या में कोई भी उपयुक्त क्षेत्र नहीं है और इसलिए कोई भी उपयुक्त समाधान नहीं है।

टिप्पणियाँ इन सभी उदाहरणों से हम रैखिक प्रोग्रामिंग समस्याओं के कुछ सामान्य विशेषताओं को देख सकते हैं:

(एक) उपयुक्त क्षेत्र हमेशा एक उत्तल क्षेत्र होता है।

(दो) लक्षित फलन का अधिकतम (या न्यूनतम)

आकृति 12.6 समाधान उपयुक्त क्षेत्र के कोने (कोर्नर) पर प्राप्त होता है। अगर दो कोने बिंदुओं लक्षित फलन के अधिकतम (या न्यूनतम) मान को प्रदान करते हैं, तो इन बिंदुओं को जोड़ने वाली रेखा स्तरीय खंड के प्रत्येक बिंदु भी एक समान अधिकतम (या न्यूनतम) मान प्रदान करेगा।

सारांश

एक रैखिक प्रोग्रामिंग समस्या ऐसी समस्या है जो कई चरों (जिन्हें लक्षित फलन कहते हैं) के एक रैखिक फलन के अभिकल्पित मान (अधिकतम या न्यूनतम) को खोजने से संबंधित है जिसकी शर्त है कि चर गैर-नकारात्मक हों और एक समूह के रैखिक असमानताओं (जिन्हें रैखिक प्रतिबंध कहते हैं) को पूरा करें। कभी-कभी चरों को निर्णय चर कहा जाता है और ये गैर-नकारात्मक होते हैं।

ऐतिहासिक टिप्पणी

दुनिया युद्ध II के दौरान, जब खर्चे को आर्थिक रूप से कम करने की योजनाएं बनाई जाती थीं, शत्रु को अधिक क्षति पहुंचाने के लिए, रैखिक प्रोग्रामिंग समस्याएं प्रमुख स्थान पर आ गईं।

रैखिक प्रोग्रामिंग में पहली समस्या 1941 में भारतीय गणितज्ञ, एल। कैंटोरोविच और अमेरिकी अर्थशास्त्री, एफ। एल। हिट्कॉक द्वारा रूपांतरित की गई थी, जो एक-दूसरे के साथ अलग-अलग काम कर रहे थे। यह बेहद ज्ञानवर्धक परिवहन समस्या थी। 1945 में, अंग्रेजी अर्थशास्त्री, जी। स्टाइगलर ने एक और रैखिक प्रोग्रामिंग समस्या का वर्णन किया - एक अभिकल्पित आहार की निर्धारण की समस्या।

1947 में, अमेरिकी अर्थशास्त्री, जी। बी। डैंट्जिग ने एक कुशल विधि की सिफारिश की जिसे सीम्प्लेक्स विधि कहा जाता है, जो कि किसी भी रैखिक प्रोग्रामिंग समस्या को एक पारित संख्या में चरणों में हल करने की एक पुनरावृत्ति प्रक्रिया है।

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