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

12.1 परिचय

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

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

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

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

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

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

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

(i) विक्रेता अपना धन मेजें या कुर्सियाँ या दोनों के संयोजन में लगा सकता है। इसके अतिरिक्त विभिन्न निवेश रणनीतियों अपनाकर वह भिन्न-भिन्न लाभ कमाएगा।

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

मान लीजिए वह केवल मेजें खरीदने का निर्णय लेता है और कोई कुर्सी नहीं, तो वह $50000 \div 2500$, अर्थात् 20 मेजें खरीद सकता है। इस स्थिति में उसका लाभ ₹$(250 \times 20)$, अर्थात् ₹$\mathbf{5 0 0 0}$ होगा।

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

और भी कई संभावनाएँ हैं, उदाहरण के लिए, वह 10 मेज़ें और 50 कुर्सियाँ खरीद सकता है, क्योंकि वह केवल 60 टुकड़े ही संग्रहीत कर सकता है। इस स्थिति में कुल लाभ रुपये $(10 \times 250+50 \times 75)$, यानी रुपये $\mathbf{6 2 5 0}$ होगा और इसी तरह।

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

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

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

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

$$ \begin{align*} & x \geq 0 \tag{1}\\ & y \geq 0 \tag{2} \end{align*} \text { (अ-ऋणात्मक बाध्यताएँ) } $$

व्यापारी अधिकतम राशि जो वह निवेश कर सकता है (यहाँ यह 50,000 रुपये है) और अधिकतम वस्तुओं की संख्या जो वह संग्रहीत कर सकता है (यहाँ यह 60 है) से बाध्य है।

गणितीय रूप से कहा गया है,

या

$$ \begin{array}{rlrl} 2500 x+500 y & \leq 50,000 & \text { (निवेश सीमा) } \ 5 x+y & \leq 100 & & \ x+y & \leq 60 & & \text { (भंडारण सीमा) } \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$ असीमित है, तो उद्देश्य फलन का अधिकतम या न्यूनतम मान मौजूद नहीं भी हो सकता है। यदि यह मौजूद है, तो यह $R$ के एक कोनीय बिंदु पर होना चाहिए। (प्रमेय 1 द्वारा)

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

हमारे पास

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

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

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

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

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

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

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

(ii) यदि सुसाध्य क्षेत्र असीमित हो, तो:

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

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

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

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

Z = 4x + y को अधिकतम करें, निमलिखित बाधाओं के अधीन:

[ \begin{aligned} x + y & \leq 50 \ 3x + 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$ का अधिकतम मान 120 बिंदु $(30,0)$ पर है।

उदाहरण 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 में छायांकित क्षेत्र ABC विकरणों (2) से (4) द्वारा निर्धारित सुसंगत क्षेत्र है, जो परिबद्ध है। कोने के बिंदुओं 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$

विकरणों के अधीन: $\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$ का न्यूनतम मान 60 सुविधाजनक क्षेत्र के बिंदु $B(5,5)$ पर है।

सुविधाजनक क्षेत्र पर $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

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

$$ -50 x+20 y<-300 \text{ (कोने के बिंदु विधि का चरण 3(ii) देखें।) } $$

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

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

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

उपरोक्त उदाहरण में, क्या आप बता सकते हैं कि क्या $z=-50 x+20 y$ का अधिकतम मान $(0,5)$ पर 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 से आप देख सकते हैं कि कोई भी बिंदु सभी बंधनों को एक साथ संतुष्ट नहीं करता। इस प्रकार, इस समस्या का कोई सुसंगत क्षेत्र नहीं है और इसलिए कोई सुसंगत हल नहीं है।

टिप्पणियाँ अब तक जिन उदाहरणों पर हमने चर्चा की है, उनसे हम रैखिक प्रोग्रामन समस्याओं की कुछ सामान्य विशेषताएँ देखते हैं:

(i) सुसंगत क्षेत्र सदैव एक अवतल (convex) क्षेत्र होता है।

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

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

सारांश

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

ऐतिहासिक नोट

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

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

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

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