छात्र के गणितीय अनुभव की पूर्णता तभी होती है जब वह कभी अपने द्वारा बनाए गए समस्या को हल न करे। - जी. पॉल्या

12.1 परिचय

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

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

एल. कांटोरोविच

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

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

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

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

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

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

(ii) कुछ प्रमुख शर्तें या सीमाएं हैं, जैसे कि उसका निवेश अधिकतम 50,000 रुपये तक हो सकता है और उसकी भंडारण क्षमता भी अधिकतम 60 इकाई तक हो सकती है।

मान लीजिए वह केवल मेज खरीदने का निर्णय लेता है और कुर्सी नहीं, तो वह $50000 \div 2500$, अर्थात 20 मेज खरीद सकता है। इस स्थिति में उसका लाभ 250 × 20, अर्थात 5000 रुपये होगा।

मान लीजिए वह केवल कुर्सी खरीदने का निर्णय लेता है और मेज नहीं। अपने 50,000 रुपये के कैपिटल के साथ, वह $50000 \div 500$, अर्थात 100 कुर्सियां खरीद सकता है। लेकिन वह केवल 60 इकाई भंडारण कर सकता है। इसलिए, वह केवल 60 कुर्सियां खरीदने के बाध्य हो जाता है जो उसे 60 × 75, अर्थात 4500 रुपये का कुल लाभ देगा।

कई अन्य संभावनाएं हैं, उदाहरण के लिए, वह 10 मेज और 50 कुर्सियां खरीद सकता है, क्योंकि वह केवल 60 इकाई भंडारण कर सकता है। इस स्थिति में कुल लाभ 10 × 250 + 50 × 75, अर्थात 6250 रुपये होगा आदि।

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

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

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

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

$ x \geq 0 \hspace{4cm} \ldots(1)$

$y \geq 0 \hspace{4cm} \ldots(2) \text { (गैर-ऋणात्मक सीमाएं) } $

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

गणितीय रूप में,

या $ \qquad 2500 x+500 y \leq 50,000 \text { (निवेश सीमा ) }$

$\qquad 5 x+y \leq 100\hspace{5cm} \ldots(3)$

$\qquad x+y \leq 60 \text { (संग्रहण सीमा) } \hspace{2cm} \ldots(4)$

व्यापारी अपने लाभ को अधिकतम करने के लिए निवेश करना चाहता है, मान लीजिए, $Z$ जो $x$ और $y$ के फलन के रूप में दिया गया है, निम्नलिखित है:

$Z=250 x+75 y$ (उद्देश्य फलन कहलाता है) $\hspace{3cm} \ldots(5)$

गणितीय रूप में, दिया गया समस्या अब निम्नलिखित रूप में घट जाती है:

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

प्रतिबंधों के अधीन:

$\qquad 5 x+y \leq 100$

$\qquad x+y \leq 60$

$\qquad x \geq 0, y \geq 0$

इसलिए, हमें एक रैखिक फलन $Z$ को अधिकतम करना होता है, जो कुछ चरों (मान लीजिए $x$ और $y$) के रूप में दिया गया है और जो चर गैर-ऋणात्मक हों और एक समूह रैखिक असमिकाओं के अधीन हों। कुछ अन्य समस्याओं में हमें एक रैखिक फलन को न्यूनतम करना होता है, जो कुछ चरों के रूप में दिया गया है और जो चर गैर-ऋणात्मक हों और एक समूह रैखिक असमिकाओं के अधीन हों। ऐसी समस्याओं को रैखिक प्रोग्रामिंग समस्याएं कहा जाता है।

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

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

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

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

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

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

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

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

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

$\qquad 5 x+y \leq 100 \hspace{3cm} \ldots(1) $

$\qquad x+y \leq 60 \hspace{3cm} \ldots(2) $

$\qquad x \geq 0 \hspace{4cm} \ldots(3) $

$\qquad y \geq 0 \hspace{4cm} \ldots(4) $

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

चित्र 12.1

संभाव्य क्षेत्र एक रैखिक प्रोग्रामिंग समस्या के सभी संकर्षणों (समान रूप से गैर-ऋणात्मक संकर्षण $x, y \geq 0$ शामिल) द्वारा निर्धारित सामान्य क्षेत्र को संभाव्य क्षेत्र (या समाधान क्षेत्र) कहते हैं। चित्र 12.1 में, क्षेत्र OABC (छायांकित) समस्या के संभाव्य क्षेत्र है। संभाव्य क्षेत्र के बाहर क्षेत्र को असंभाव्य क्षेत्र कहते हैं।

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

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

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

अब, हम देखते हैं कि संभाव्य क्षेत्र $OABC$ में कोई भी बिंदु सभी संकर्षणों को संतुष्ट करता है जैसा कि (1) से (4) में दिया गया है, और क्योंकि यहां अपार बिंदुओं की संख्या है, हमें स्पष्ट रूप से बताना कठिन हो गया है कि कौन सा बिंदु उद्देश्य फ़ंक्शन $Z=250 x+70 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,5,0)$ और $(0,60)$ क्रमशः। अब हम इन बिंदुओं पर $Z$ के मान की गणना करेंगे।

हमारे पास है:

$ \begin{array}{|l|l|} \hline \text{संभव क्षेत्र के शीर्ष} & \text{संगत } Z , (\text{रुपये में}) \ \hline O(0,0) & 0 \ C(0,60) & 4500 \ B(10,50) & \mathbf{6250} \longleftarrow \text{अधिकतम} \ A(20,0) & 5000 \ \hline \end{array} $

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

• एक रैखिक असमानताओं के निर्णय तंत्र के संभव क्षेत्र को वृत्त के भीतर बंद किया जा सके तो इसे बंद कहा जाता है। अन्यथा, इसे असीमित कहा जाता है। असीमित का अर्थ है कि संभव क्षेत्र कोई दिशा में अनंत तक फैला हो सकता है।

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

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

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

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

3. (i) जब संभव क्षेत्र बंद होता है, तो $M$ और $m$ क्रमशः $Z$ के अधिकतम और न्यूनतम मान होते हैं।

(ii) जब संभव क्षेत्र असीमित होता है, तो हमारे पास है:

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

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

अब हम शीर्ष बिंदु विधि के इन चरणों को समझने के लिए कुछ उदाहरणों के माध्यम से दिखाएंगे:

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

अधिकतम करें $Z=4 x+y \hspace{2cm} \ldots(1) $

के अंतर्गत संरोचन शर्तों:

$ \qquad x+y \leq 50 \hspace{3cm} \ldots(2) $

$ \qquad 3 x+y \leq 90 \hspace{3cm} \ldots(3) $

$ \qquad x \geq 0, y \geq 0 \hspace{3cm} \ldots(4) $

हल चित्र 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 \hspace{2cm} \ldots(1) $

के अंतर्गत संरोचन शर्तों:

$\qquad x+2 y \geq 10 \hspace{3cm} \ldots(2) $

$\qquad 3 x+4 y \leq 24 \hspace{3cm} \ldots(3) $

$\qquad x \geq 0, y \geq 0 \hspace{3cm} \ldots(4) $

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

चित्र 12.3

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

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

$Z=3 x+9 y\hspace{4.5cm} \ldots(1) $

के अंतर्गत बंधन: $\qquad x+3 y \leq 60 \hspace{3.8cm} \ldots(2) $

$\qquad\qquad\qquad\qquad\qquad\qquad x+y \geq 10 \hspace{4cm} \ldots(3) $

$\qquad\qquad\qquad\qquad\qquad\qquad x \leq y \hspace{5cm} \ldots(4) $

$\qquad\qquad\qquad\qquad\qquad\qquad x \geq 0, y \geq 0 \hspace{4cm} \ldots(5) $

हल सबसे पहले, हम रैखिक असमिकाओं के प्रणाली (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 \hspace{3cm} \ldots(1) $

के अंतर्गत बंधन:

$\qquad 2 x-y \geq-5 \hspace{3cm} \ldots(2) $

$\qquad 3 x+y \geq 3 \hspace{3cm} \ldots(3) $

$\qquad 2 x-3 y \leq 12 \hspace{3cm} \ldots(4) $

$\qquad x \geq 0, y \geq 0 \hspace{3cm} \ldots(5) $

हल पहले असमानताओं (2) से (5) के योग्य क्षेत्र को आलेखित करें। योग्य क्षेत्र (छायांकित) चित्र 12.5 में दिखाया गया है। ध्यान दें कि योग्य क्षेत्र असीमित है।

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

चित्र 12.5

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

$ \qquad -50 x+20 y<-300 \text{ (शीर्ष बिंदु विधि के चरण 3(ii) को देखें।) $

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

के लिए आलेख बनाएं और जाँच करें कि इस खुले अर्ध-तल के बिंदु योग्य क्षेत्र के साथ उभयनिष्ठ हैं या नहीं। यदि यह उभयनिष्ठ है, तो $-300$ $Z$ का न्यूनतम मूल्य नहीं होगा। अन्यथा, $-300$ $Z$ का न्यूनतम मूल्य होगा।

चित्र 12.5 में दिखाए गए अनुसार, यह उभयनिष्ठ बिंदु हैं। अतः $Z=-50 x+20 y$ के दिए गए संरेखण के अंतर्गत कोई न्यूनतम मूल्य नहीं है।

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

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

जो कि निम्नलिखित संरेखण के अंतर्गत है:

$\qquad x+y \geq 8 \hspace{3.5cm} \ldots(1) $

$\qquad 3 x+5 y \leq 15 \hspace{3cm} \ldots(2) $

$\qquad x \geq 0, y \geq 0 \hspace{3cm} \ldots(3) $

हल असमानताओं (1) से (3) को आलेखित करें (चित्र 12.6)। क्या कोई योग्य क्षेत्र है? क्यों ऐसा है?

चित्र 12.6 से आप देख सकते हैं कि कोई भी बिंदु सभी संरेखण के अंतर्गत नहीं है। अतः समस्या में कोई योग्य क्षेत्र नहीं है और अतः कोई योग्य समाधान नहीं है।

संग्रहण से चर्चा किए गए उदाहरणों से हम लीनियर प्रोग्रामिंग समस्याओं के कुछ सामान्य विशेषताओं को ध्यान में रखते हैं:

(i) संभव क्षेत्र हमेशा एक उत्तल क्षेत्र होता है।

(ii) उद्देश्य फंक्शन का अधिकतम (या न्यूनतम)

चित्र 12.6

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

अभ्यास 12.1

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

1. $Z=3 x+4 y$ को अधिकतम कीजिए

प्रतिबंधों के अंतरगत : $x+y \leq 4, x \geq 0, y \geq 0$.

उत्तर दिखाएं

हल

प्रतिबंधों $x+y \leq 4, x \geq 0, y \geq 0$ द्वारा निर्धारित संभाव्य क्षेत्र निम्नलिखित है।

संभाव्य क्षेत्र के कोने बिंदु $O(0,0), A(4,0)$, और $B(0,4)$ हैं। इन बिंदुओं पर $Z$ के मान निम्नलिखित हैं।

कोने बिंदु	$\mathbf{Z}=\mathbf{3 x}+\mathbf{4} \boldsymbol{{}y}$
$O(0,0)$	0
$A(4,0)$	12
$B(0,4)$	16	$arrow$ अधिकतम

इसलिए, $Z$ का अधिकतम मान 16 बिंदु $B(0,4)$ पर है।

2. $Z=-3 x+4 y$ को न्यूनतम कीजिए

प्रतिबंधों के अंतरगत : $x+2 y \leq 8,3 x+2 y \leq 12, x \geq 0, y \geq 0$.

उत्तर दिखाएं

हल

प्रतिबंधों के तंत्र $x+2 y \leq 8,3 x+2 y \leq 12, x \geq$ 0 , और $y \geq 0$ द्वारा निर्धारित संभाव्य क्षेत्र निम्नलिखित है।

संभाव्य क्षेत्र के कोने बिंदु $O(0,0), A(4,0), B(2,3)$, और $C(0,4)$ हैं। इन कोने बिंदुओं पर $Z$ के मान निम्नलिखित हैं।

कोने बिंदु	$\mathbf{Z}=\mathbf{- 3 x + 4 y}$
$0(0,0)$	0
$A(4,0)$	-12	$arrow$ न्यूनतम
$B(2,3)$	6
$C(0,4)$	16

इसलिए, $Z$ का न्यूनतम मान -12 बिंदु $(4,0)$ पर है।

3. $Z=5 x+3 y$ को अधिकतम करें

जो कि $3 x+5 y \leq 15,5 x+2 y \leq 10, x \geq 0, y \geq 0$ के अंतर्गत हो।

उत्तर दिखाएं

हल

संरचना के तहत निर्धारित क्षेत्र, $3 x+5 y \leq 15$, $5 x+2 y \leq 10, x \geq 0$, और $y \geq 0$ के निम्नलिखित हैं।

संभाव्य क्षेत्र के कोने बिंदु $O(0,0), A(2,0), B(0,3)$, और $C(\frac{20}{19}, \frac{45}{19})$ हैं। इन कोने बिंदुओं पर $Z$ के मान निम्नलिखित हैं।

कोने बिंदु	$\mathbf{Z}=\mathbf{5} \boldsymbol{{}x}+\mathbf{3} \boldsymbol{{}y}$
$O(0,0)$	0
$A(2,0)$	10
$B(0,3)$	9
$C(\frac{20}{19}, \frac{45}{19})$	$\frac{235}{19}$	$arrow$ अधिकतम

4. $Z=3 x+5 y$ को न्यूनतम करें

जो कि $x+3 y \geq 3, x+y \geq 2, x, y \geq 0$ के अंतर्गत हो।

उत्तर दिखाएं

हल

संरचना के तहत निर्धारित क्षेत्र, $x+3 y \geq 3, x+y \geq 2$, और $x$, $y \geq 0$ के निम्नलिखित हैं।

यह देखा जा सकता है कि संभाव्य क्षेत्र असीमित है।

संभाव्य क्षेत्र के कोने बिंदु $A(3,0), B(\frac{3}{2}, \frac{1}{2})$, और $C(0,2)$ हैं।

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

कोने बिंदु	$\mathbf{Z}=\mathbf{3} \boldsymbol{{}x}+\mathbf{5} \boldsymbol{{}y}$
$A(3,0)$	9
$B(\frac{3}{2}, \frac{1}{2})$	7	$arrow$ न्यूनतम
$C(0,2)$	10

क्योंकि संभव क्षेत्र असीमित है, इसलिए, 7 $Z$ का न्यूनतम मान हो सकता है या नहीं।

इसके लिए, हम असमिका $3 x+5 y<7$ के ग्राफ को खींचते हैं और जाँच करते हैं कि परिणामी अर्ध-तल संभव क्षेत्र के साथ कोई बिंदु आम नहीं है या नहीं।

देखा जा सकता है कि संभव क्षेत्र $3 x+5 y<7$ के कोई आम बिंदु नहीं है। इसलिए,

$Z$ का न्यूनतम मान 7 है बिंदु $(\frac{3}{2}, \frac{1}{2})$ पर।

5. $Z=3 x+2 y$ को अधिकतम करें

$ x+2 y \leq 10,3 x+y \leq 15, x, y \geq 0 $ के अंतर्गत।

उत्तर दिखाएं

हल

अंतर्गत शर्तों $x+2 y \leq 10,3 x+y \leq 15, x \geq 0$, और $y \geq 0$ द्वारा निर्धारित संभव क्षेत्र निम्नलिखित है।

संभव क्षेत्र के कोने बिंदु $A(5,0), B(4,3)$, और $C(0,5)$ हैं।

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

कोने बिंदु	$\mathbf{Z}=\mathbf{3 x}+\mathbf{2} \boldsymbol{{}y}$
$A(5,0)$	15
$B(4,3)$	18	$arrow$ अधिकतम
$C(0,5)$	10

इसलिए, $Z$ का अधिकतम मान 18 है बिंदु $(4,3)$ पर।

6. $Z=x+2 y$ को न्यूनतम करें

$2 x+y \geq 3, x+2 y \geq 6, x, y \geq 0$ के अंतर्गत।

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

उत्तर दिखाएं

हल

अंतर्गत शर्तों $2 x+y \geq 3, x+2 y \geq 6, x \geq 0$, और $y$ $\geq 0$ द्वारा निर्धारित संभव क्षेत्र निम्नलिखित है।

संभव क्षेत्र के कोने बिंदु $A(6,0)$ और $B(0,3)$ हैं।

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

कोने बिंदु	$Z=x+2 y$
$A(6,0)$	6
$B(0,3)$	6

देखा जा सकता है कि बिंदुओं $A$ और $B$ पर $Z$ का मूल्य समान है। यदि हम किसी अन्य बिंदु जैसे $(2,2)$ पर रेखा $x+2 y=6$ पर जाएं, तो $Z=6$ होगा।

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

इसलिए, रेखा $x+2 y=6$ पर किसी भी बिंदु पर $Z$ का मूल्य न्यूनतम होता है।

7. $Z=5 x+10 y$ को न्यूनतम और अधिकतम करें

$ x+2 y \leq 120, x+y \geq 60, x-2 y \geq 0, x, y \geq 0 $ के अंतर्गत।

उत्तर दिखाएं

हल

संरचनाओं $x+2 y \leq 120, x+y \geq 60, x-2 y \geq$ $0, x \geq 0$, और $y \geq 0$ द्वारा निर्धारित योग्य क्षेत्र निम्नलिखित है।

योग्य क्षेत्र के कोने बिंदु $A(60,0), B(120,0), C(60,30)$, और $D(40$, 20) हैं।

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

कोने बिंदु	$\mathbf{Z}=\mathbf{5} \boldsymbol{{}x}+\mathbf{1 0} \boldsymbol{{}y}$
$A(60,0)$	300	$arrow$ न्यूनतम
$B(120,0)$	600	$arrow$ अधिकतम
$C(60,30)$	600	$arrow$ अधिकतम
$D(40,20)$	400

$Z$ का न्यूनतम मूल्य $(60,0)$ पर 300 है और $Z$ का अधिकतम मूल्य $(120,0)$ और $(60,30)$ के बीच जुड़ी रेखा पर सभी बिंदुओं पर 600 है।

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

$ x+2 y \geq 100,2 x-y \leq 0,2 x+y \leq$ $200, x \geq 0$, और $y \geq 0$ के अंतर्गत।

उत्तर दिखाएं

हल

संरचनाओं $x+2 y \geq 100,2 x-y \leq 0,2 x+y \leq$ $200, x \geq 0$, और $y \geq 0$ द्वारा निर्धारित योग्य क्षेत्र निम्नलिखित है।

कोड़े बिंदुओं के योग्य क्षेत्र के कोने बिंदु $A(0,50), B(20,40), C(50,100)$, और $D(0$, 200) हैं।

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

कोने बिंदु	$\mathbf{Z}=\boldsymbol{{}x}+\mathbf{2} \boldsymbol{{}y}$
$A(0,50)$	100	$arrow$ न्यूनतम
$B(20,40)$	100	$arrow$ न्यूनतम
$C(50,100)$	250
$D(0,200)$	400	$arrow$ अधिकतम

$Z$ का अधिकतम मान 400 है, जो $(0,200)$ पर है और $Z$ का न्यूनतम मान 100 है, जो बिंदुओं $(0,50)$ और $(20,40)$ को जोड़ने वाले रेखाखंड पर सभी बिंदुओं पर है।

9. अधिकतम करें $Z=-x+2 y$, बाधा के अंतर्गत:

$$x \geq 3, x+y \geq 5, x+2 y \geq 6, y \geq 0$$

उत्तर दिखाएं

हल

बाधा द्वारा निर्धारित योग्य क्षेत्र, $x \geq 3, x+y \geq 5, x+2 y \geq 6$, और $y \geq 0$, निम्नलिखित है।

देखा जा सकता है कि योग्य क्षेत्र असीमित है।

कोने बिंदुओं $A(6,0), B(4,1)$, और $C(3,2)$ पर $Z$ के मान निम्नलिखित हैं।

कोने बिंदु	$Z=-\boldsymbol{{}x}+\mathbf{2} \boldsymbol{{}y}$
$A(6,0)$	$Z=-6$
$B(4,1)$	$Z=-2$
$C(3,2)$	$Z=1$

क्योंकि योग्य क्षेत्र असीमित है, इसलिए $Z=1$ अधिकतम मान हो सकता है या नहीं।

इसके लिए हम असमिका, $-x+2 y>1$ को आलेखित करते हैं और जांच करते हैं कि निर्मित अर्ध-तल योग्य क्षेत्र के साथ कोई बिंदु आम नहीं है या नहीं।

निर्मित योग्य क्षेत्र योग्य क्षेत्र के साथ कोई बिंदु आम है।

इसलिए, $Z=1$ अधिकतम मान नहीं है। $Z$ का कोई अधिकतम मान नहीं है।

10. अधिकतम करें $Z=x+y$, बाधा के अंतर्गत $x-y \leq-1,-x+y \leq 0, x, y \geq 0$.

उत्तर दिखाएं

हल

बाधा द्वारा निर्धारित क्षेत्र, $x-y \leq-1,-x+y \leq 0, x, y \geq 0$, निम्नलिखित है।

कोई उपयोगी क्षेत्र नहीं है और इसलिए, $Z$ के कोई अधिकतम मान नहीं है।

सारांश

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

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

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

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

1947 में, अमेरिकी अर्थशास्त्री जी. बी. डांटिग ने एक दक्ष विधि का प्रस्ताव रखा जो लीनियर प्रोग्रामिंग समस्याओं को एक सीमित संख्या में कदमों में हल करने के लिए एक पुनरावर्ती प्रक्रिया है, जिसे सिंप्लेक्स विधि कहते हैं।

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