The mathematical experience of the student is incomplete if he never had the opportunity to solve a problem invented by himself. - G POLYA

12.1 भूमिका (Introduction)

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

एक फर्नीचर व्यापारी दो वस्तुओं जैसे मेज़ और कुर्सियों का व्यवसाय करता है। निवेश के लिए उसके पास Rs 50,000 और रखने के लिए केवल 60 वस्तुओं के लिए स्थान है। एक मेज़ पर Rs 2500 और एक कुर्सी पर Rs 500 की लागत आती है। वह

L.Kantorovich

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

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

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

12.2 रैखिक प्रोग्रामन समस्या और उसका गणितीय सूत्रीकरण (Linear Programming Problem and its Mathematical Formulation)

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

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

(ii) कुछ अधिक महत्त्वपूर्ण स्थितियाँ या व्यवरोधों का भी समावेश है जैसे उसका निवेश अधिकतम Rs 50,000 तक सीमित है तथा उसके पास अधिकतम 60 वस्तुओं को रखने के लिए स्थान उपलब्ध है।

मान लीजिए कि वह कोई कुर्सी नहीं खरीदता केवल मेज़ों के खरीदने का निश्चय करता है, इसलिए वह $50,000 \div 2500$, या 20 मेज़ों को खरीद सकता है। इस स्थिति में उसका सकल लाभ Rs $(250 \times 20)$ या Rs 5000 होगा।

मान लीजिए कि वह कोई मेज़ न खरीदकर केवल कुर्सियाँ ही खरीदने का चयन करता है। तब वह अपनी उपलब्ध Rs 50,000 की राशि में $50,000 \div 500$, अर्थात् 100 कुर्सियाँ ही खरीद सकता है। परंतु वह केवल 60 नगों को ही रख सकता है। अतः वह 60 कुर्सियाँ मात्र खरीदने के लिए बाध्य होगा। जिससे उसे सकल लाभ Rs $60 \times 75$ अर्थात् Rs 4500 ही होगा।

ऐसी और भी बहुत सारी संभावनाएँ हैं। उदाहरण के लिए वह 10 मेज़ों और 50 कुर्सियाँ खरीदने का चयन कर सकता है, क्योंकि उसके पास 60 वस्तुओं को रखने का स्थान उपलब्ध है। इस स्थिति में उसका सकल लाभ Rs $(10 \times 250+50 \times 75)$, अर्थात् Rs 6250 इत्यादि।

अतः हम ज्ञात करते हैं कि फर्नीचर व्यापारी विभिन्न चयन विधियों के द्वारा अपनी धन राशि का निवेश कर सकता है और विभिन्न निवेश योजनाओं को अपनाकर विभिन्न लाभ कमा सकेगा।

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

12.2.1 समस्या का गणितीय सूत्रीकरण (Mathematical Formulation of the Problem)

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

$$ \begin{align*} & x \geq 0 \tag{1}\\ & y \geq 0 \tag{2} \end{align*} \text { (ऋणेतर व्यवरोध) } $$

क्योंकि मेज़ों और कुर्सियों की संख्या ऋणात्मक नहीं हो सकती है।

व्यापारी (व्यवसायी) पर अधिकतम धन राशि (यहाँ यह Rs 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} $$

$$ \text { या } $$

और

व्यवसायी इस प्रकार से निवेश करना चाहता है उसका लाभ $\mathrm{Z}$ (माना) अधिकतम हो और जिसे $x$ और $y$ के फलन के रूप में निम्नलिखित प्रकार से व्यक्त किया जा सकता है:

$\mathrm{Z}=250 x+75 y$ (उद्देशीय फलन कहलाता है)

प्रदत्त समस्या का अब गणितीय रूप में परिवर्तित हो जाती है:

$\mathrm{Z}=250 x+75 y$ का अधिकतमीकरण कीजिए

जहाँ व्यवरोध निम्नलिखित है

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

इसलिए हमें रैखिक फलन $\mathrm{Z}$ का अधिकतमीकरण करना है जबकि ॠणेतर चरों वाली रैखिक असमिकाओं के रूप कुछ विशेष स्थितियों के व्यवरोध व्यक्त किए गए हैं। कुछ अन्य समस्याएँ भी हैं जिनमें रैखिक फलन का न्यूनतमीकरण किया जाता है जबकि ऋणेतर चर वाली रैखिक असमिकाओं के रूप में कुछ विशेष स्थितियों के व्यवरोध व्यक्त किए जाते है। ऐसी समस्याओं को रैखिक प्रोग्रामन समस्या कहते हैं।

अतः एक रैखिक प्रोग्रामन समस्या वह समस्या है जो कि $x$ और $y$ जैसे कुछ अनेक चरों के एक रैखिक फलन $\mathrm{Z}$ (जो कि उद्देश्य फलन कहलाता है) का इष्टतम सुसंगत/अनुकूलतम सुसंगत मान (अधिकतम या न्यूनतम मान) ज्ञात करने से संबंधित है। प्रतिबंध यह है कि चर ऋणेतर पूर्णांक हैं और ये रैखिक असमिकाओं के समुच्चय रैखिक व्यवरोधों को संतुष्ट करते हैं। रैखिक पद से तात्पर्य है कि समस्या में सभी गणितीय संबंध रैखिक हैं जबकि प्रोग्रामन से तात्पर्य है कि विशेष प्रोग्राम या विशेष क्रिया योजना ज्ञात करना।

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

उद्देश्य फलन रैखिक फलन $\mathrm{Z}=a x+b y$, जबकि $a, b$ अचर है जिनका अधिकतमीकरण या न्यूनतमीकरण होना है एक रैखिक उद्देश्य फलन कहलाता है।

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

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

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

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

12.2.2 रैखिक प्रोग्रामन समस्याओं को हल करने की आलेखीय विधि (Graphical Method of Solving Linear Programming Problems)

कक्षा 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)। इस क्षेत्र का प्रत्येक बिंदु समस्या का सुसंगत हल कहलाता है।

अतः हम निम्न को परिभाषित करते हैं:

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

सुसंगत हल समूह सुसंगत क्षेत्र के अंतः भाग तथा सीमा के सभी बिंदु व्यवरोधों के सुसंगत हल कहलाते हैं। आकृति 12.1 में सुसंगत क्षेत्र $\mathrm{OABC}$ के अंतः भाग तथा सीमा के सभी बिंदु समस्या के सुसंगत हल प्रदर्शित कहते हैं। उदाहरण के लिए बिंदु $(10,50)$ समस्या का एक सुसंगत हल है और इसी प्रकार बिंदु $(0,60),(20,0)$ इत्यादि भी हल हैं।

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

इष्टतम/अनुकूलतम ( सुसंगत) हलः सुसंगत क्षेत्र में कोई बिंदु जो उद्देश्य फलन का इष्टतम मान (अधिकतम या न्यूनतम) दे, एक इष्टतम हल कहलाता है।

अब हम देखते हैं कि सुसंगत क्षेत्र $\mathrm{OABC}$ में प्रत्येक बिंदु (1) से (4) तक में प्रदत्त सभी व्यवरोधों को संतुष्ट करता है और ऐसे अनंत बिंदु हैं। यह स्पष्ट नहीं है कि हम उद्देश्य फलन $\mathrm{Z}=250 x+75 y$ के अधिकतम मान वाले बिंदु को किस प्रकार ज्ञात करने का प्रयास करें। इस स्थिति को हल करने के लिए हम निम्न प्रमेयों का उपयोग करेंगे जो कि रैखिक प्रोग्रामन समस्याओं को हल करने में मूल सिद्धांत (आधारभूत) है। इन प्रमेयों की उपपति इस पुस्तक के विषय-वस्तु से बाहर है। प्रमेय 1 माना कि एक रैखिक प्रोग्रामन समस्या के लिए $\mathrm{R}$ सुसंगत क्षेत्र* (उत्तल बहुभुज) है और माना कि $\mathrm{Z}=a x+b y$ उद्देश्य फलन है। जब $\mathrm{Z}$ का एक इष्टतम मान (अधिकतम या न्यूनतम) हो जहाँ व्यवरोधों से संबंधित चर $x$ और $y$ रैखिक असमीकरणों द्वारा व्यक्त हो तब यह इष्टतम मान सुसंगत क्षेत्र के कोने (शीर्ष) पर अवस्थित होने चाहिए।

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

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

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

वह इस प्रकार है:

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

इस विधि में निम्न पदों का समाविष्ट हैं:

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

2. उद्देश्य फलन $\mathrm{Z}=a x+b y$ का मान प्रत्येक कोनीय बिंदु पर ज्ञात कीजिए। माना कि $\mathrm{M}$ और $m$, क्रमशः इन बिंदुओं पर अधिकतम तथा न्यूनतम मान प्रदर्शित करते हैं।

3. (i) जब सुसंगत क्षेत्र परिबद्ध है, $\mathrm{M}$ और $m, \mathrm{Z}$ के अधिकतम और न्यूनतम मान हैं।

(ii) ऐसी स्थिति में जब सुसंगत क्षेत्र अपरिबद्ध हो तो हम निम्नलिखित विधि का उपयोग करते हैं।

4. (a) $\mathrm{M}$ को $\mathrm{Z}$ का अधिकतम मान लेते हैं यदि $a x+b y>\mathrm{M}$ द्वारा प्राप्त अर्ध-तल का कोई बिंदु सुसंगत क्षेत्र में न पड़े अन्यथा $\mathrm{Z}$ कोई अधिकतम मान नहीं है।

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

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

प्रश्नावली 12.1

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

1. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=3 x+4 y$ का अधिकतमीकरण कीजिए:

$$ x+y \leq 4, x \geq 0, y \geq 0 $$

2. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=-3 x+4 y$ का न्यूनतमीकरण कीजिए:

$$ x+2 y \leq 8,3 x+2 y \leq 12, x \geq 0, y \geq 0 $$

3. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=5 x+3 y$ का अधिकतमीकरण कीजिए:

$$ 3 x+5 y \leq 15,5 x+2 y \leq 10, x \geq 0, y \geq 0 $$

4. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=3 x+5 y$ का न्यूनतमीकरण कीजिए;

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

5. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=3 x+2 y$ का न्यूनतमीकरण कीजिए:

$$ x+2 y \leq 10,3 x+y \leq 15, x, y \geq 0 $$

6. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=x+2 y$ का न्यूनतमीकरण कीजिए:

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

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

7. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=5 x+10 y$ का न्यूनतमीकरण तथा अधिकतमीकरण कीजिए :

$$ x+2 y \leq 120, x+y \geq 60, x-2 y \geq 0, x, y \geq 0 $$

8. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=x+2 y$ का न्यूनतमीकरण तथा अधिकतमीकरण कीजिए:

$$ x+2 y \geq 100,2 x-y \leq 0,2 x+y \leq 200 ; x, y \geq 0 $$

9. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=-x+2 y$ का अधिकतमीकरण कीजिए:

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

10. निम्न अवरोधों के अंतर्गत $\mathrm{Z}=x+y$ का अधिकतमीकरण कीजिए:

$x-y \leq-1,-x+y \leq 0, x, y \geq 0$

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

द्वितीय विश्व युद्ध में, जब युद्ध संचालन की योजना बनी, जिससे कि शत्रुओं को न्यूनतम व्यय पर अधिकतम हानि पहुँचे, रैखिक प्रोग्रामन विधि अस्तित्व में आई। रैखिक प्रोग्रामन के क्षेत्र में प्रथम प्रोग्रामन का सूत्रपात रूसी गणितज्ञ L.Kantoro Vich तथा अमेरिकी अर्थशास्त्री F.L.Hitch Cock ने 1941 में किए। दोनों ने स्वतंत्र रूप से कार्य किया।

इस प्रोग्रामन को परिवहन-समस्या के नाम से जाना गया। सन् 1945 में अंग्रेज अर्थशास्त्री G.Stigler ने रैखिक प्रोग्रामन समस्या, के अंतर्गत इष्टतम आहार संबंधी समस्या का वर्णन किया। सन् 1947 में G.B. Dantzig ने एक दक्षता पूर्ण विधि जो सिंपलेक्स विधि के नाम से प्रसिद्ध है, का सुझाव दिया जो रैखिक प्रोग्रामन समस्याओं को सीमित प्रक्रमों में हल करने की सशक्त विधि है।

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