रैखिक प्रोग्रामन क्या है?
आपको सबसे अच्छा नतीजा चाहिए (सबसे ज़्यादा लाभ, सबसे कम खर्च), पर सीमाएँ भी हैं (समय, पैसा, सामान)। यह सबसे अच्छा नतीजा निकालने का तरीका रैखिक प्रोग्रामन है।
निर्णायक चर (decision variables)
जो चीज़ें हम तय करते हैं, जैसे x = केक की संख्या, y = ब्रेड की संख्या। ये ऋणात्मक नहीं हो सकते, इसलिए हमेशा x ≥ 0, y ≥ 0 लिखते हैं (ऋणेतर व्यवरोध)।
व्यवरोध (constraints)
एक नियम जो रैखिक असमिका में लिखा हो, जैसे 2x + y ≤ 10 (ओवन के घंटे)। "रैखिक" का मतलब x और y की घात सिर्फ़ 1 है, xy या x² नहीं।
उद्देश्य फलन (objective function)
जिस राशि को सबसे अच्छा बनाना है, जैसे Z = 50x + 30y (₹ में लाभ), उसे उद्देश्य फलन कहते हैं।
इष्टतमीकरण (optimisation)
Z को सबसे बड़ा (अधिकतम) या सबसे छोटा (न्यूनतम) बनाना इष्टतमीकरण है। इस रूप में लिखी समस्या रैखिक प्रोग्रामन समस्या (LPP) कहलाती है।
शब्द-समस्या से LPP कैसे बनाएँ
- चर का नाम रखो: "माना x = …, y = …"।
- छोटी तालिका बनाओ: हर वस्तु कितना संसाधन लेती है और कितना लाभ या खर्च देती है।
- हर संसाधन का एक व्यवरोध: (एक वस्तु का उपयोग × संख्या) ≤ (उपलब्ध)। "कम से कम" के लिए ≥ लिखो।
- x ≥ 0, y ≥ 0 जोड़ो।
- Z लिखो और बताओ "अधिकतम करो" या "न्यूनतम करो"।
परीक्षा में आम प्रकार: उत्पादन (लाभ), आहार (खर्च), परिवहन (खर्च) और आवंटन समस्याएँ।
दो चरों में आलेखीय विधि
दो चर हों तो ग्राफ़ पेपर का हर बिंदु (x, y) एक योजना है।
चरण 1: हर रेखा खींचो
≤ या ≥ को = कर दो। दो आसान बिंदु निकालो: x = 0 रखकर y, और y = 0 रखकर x। दोनों को मिला दो।
चरण 2: सही तरफ़ रंगो
रेखा से बाहर का कोई बिंदु, आमतौर पर (0, 0), असमिका में रखो। सही निकले तो उसकी तरफ़ रंगो, गलत निकले तो दूसरी तरफ़।
चरण 3: साझा क्षेत्र
पहले चतुर्थांश में जो भाग हर व्यवरोध से रंगा है, वही सुसंगत क्षेत्र है।
चरण 4: कोनीय बिंदु विधि
क्षेत्र के सारे कोने (शीर्ष) निकालो। जहाँ दो रेखाएँ कटती हैं, वह कोना दोनों समीकरण साथ हल करके मिलता है। हर कोने को Z में रखो। सबसे बड़ा मान = अधिकतम, सबसे छोटा = न्यूनतम।
कोने ही क्यों?
सारी रेखाएँ Z = k आपस में समांतर हैं। ऐसी रेखा को बाहर खिसकाओ तो बहुभुज को छोड़ते समय आख़िरी बिंदु कोई कोना (या पूरी भुजा) होता है। यही कोनीय बिंदु प्रमेय है। 3D के चौथे चरण में यही समलाभ रेखा (iso-profit line) दिखती है।
सुसंगत और असुसंगत क्षेत्र, परिबद्ध या अपरिबद्ध
सुसंगत क्षेत्र और सुसंगत हल
सारे व्यवरोधों (x ≥ 0, y ≥ 0 सहित) का साझा क्षेत्र सुसंगत क्षेत्र है। इसका हर बिंदु (किनारे भी) एक सुसंगत हल है। बाहर के बिंदु असुसंगत हल हैं।
परिबद्ध क्षेत्र
अगर क्षेत्र किसी वृत्त के अंदर बंद हो सके तो वह परिबद्ध है। तब Z का अधिकतम और न्यूनतम दोनों होते हैं, और दोनों कोनों पर मिलते हैं।
अपरिबद्ध क्षेत्र
अगर क्षेत्र किसी दिशा में अनंत तक फैला हो तो वह अपरिबद्ध है। तब अधिकतम या न्यूनतम न भी हो। नियम: सबसे अच्छा कोनीय मान M निकालो। अधिकतम के लिए खुला अर्ध-तल ax + by > M खींचो। अगर इसका क्षेत्र से कोई साझा बिंदु नहीं, तो M ही अधिकतम है; वरना अधिकतम नहीं है। न्यूनतम के लिए ax + by < m से ऐसे ही जाँचो।
असुसंगत समस्या
अगर कोई भी बिंदु सारे व्यवरोध न माने (जैसे x + y ≤ 2 और x + y ≥ 5), तो सुसंगत क्षेत्र खाली है और LPP का कोई हल नहीं।
इष्टतम हल (तीन व्यवरोधों तक)
सुसंगत क्षेत्र का जो बिंदु Z का सबसे अच्छा मान दे, वह इष्टतम हल है और वह Z इष्टतम मान है।
- एक ही इष्टतम: सिर्फ़ एक कोना जीतता है।
- अनेक इष्टतम: दो पड़ोसी कोने बराबर सबसे अच्छा मान दें, तो उन्हें जोड़ने वाली भुजा का हर बिंदु भी इष्टतम है, क्योंकि Z की रेखा उस भुजा के समांतर है।
- कोई इष्टतम नहीं: गलत दिशा में अपरिबद्ध, या असुसंगत।
तीन व्यवरोध (और x, y ≥ 0) हों तो क्षेत्र के ज़्यादा से ज़्यादा पाँच कोने होते हैं, इसलिए कोनों और Z की एक साफ़ तालिका ही पूरा उत्तर है। बोर्ड परीक्षा में LPP का प्रश्न अक्सर 5 अंक का होता है: लगभग 1 अंक समस्या बनाने का, 2 ग्राफ़ और क्षेत्र के, 2 कोने, Z और निष्कर्ष के।
करके देखो: कागज़ और स्केल वाला प्रयोग
वर्गांकित कागज़ पर x + y = 4 और x + 2y = 6 खींचो। क्षेत्र रंगो। अब स्केल को 3x + 4y = 0 पर रखो ((0,0) और (4, −3) से होकर)। उसे समांतर रखते हुए मूल बिंदु से दूर खिसकाओ। हरे क्षेत्र का आख़िरी छुआ बिंदु निशान लगाओ। क्या (2, 2) आया? अब 3D के खुले खेल वाले चरण में जाँचो।
मुख्य सूत्र और परिभाषाएँ
- LPP: Z = ax + by को अधिकतम या न्यूनतम करो, रैखिक व्यवरोधों और x ≥ 0, y ≥ 0 के साथ
- सुसंगत क्षेत्र = सारे व्यवरोधों का साझा क्षेत्र
- कोनीय बिंदु प्रमेय: इष्टतम मान (यदि है) सुसंगत क्षेत्र के किसी कोने पर होता है
- परिबद्ध क्षेत्र → अधिकतम और न्यूनतम दोनों होते हैं
- अपरिबद्ध: M अधिकतम तभी है जब ax + by > M का क्षेत्र से कोई साझा बिंदु न हो (न्यूनतम: ax + by < m)
- दो कोनों पर बराबर सबसे अच्छा Z → उन्हें जोड़ने वाली भुजा का हर बिंदु इष्टतम
हल किए गए उदाहरण
1. Z = 3x + 4y को अधिकतम करो, जबकि x + y ≤ 4, x + 2y ≤ 6, x ≥ 0, y ≥ 0।
चरण 1: x + y = 4 बिंदु (4, 0) और (0, 4) से जाती है। x + 2y = 6 बिंदु (6, 0) और (0, 3) से। चरण 2: (0, 0) दोनों को मानता है, तो मूल बिंदु की ओर रंगो। चरण 3: कोने: (0, 0), (4, 0), (0, 3) और कटान बिंदु। समीकरण घटाओ: y = 2, तो x = 2, यानी (2, 2)। चरण 4: Z(0,0) = 0, Z(4,0) = 12, Z(2,2) = 6 + 8 = 14, Z(0,3) = 12। चरण 5: क्षेत्र परिबद्ध है, इसलिए अधिकतम Z = 14, x = 2, y = 2 पर।
2. Z = 4x + y को अधिकतम करो, जबकि x + y ≤ 5, 2x + y ≤ 8, x, y ≥ 0।
चरण 1: x + y = 5 अक्षों को (5, 0), (0, 5) पर; 2x + y = 8 को (4, 0), (0, 8) पर काटती है। चरण 2: दोनों ≤ हैं, मूल बिंदु की ओर रंगो। चरण 3: कटान: दूसरे में से पहला घटाओ: x = 3, y = 2। कोने: (0, 0), (4, 0), (3, 2), (0, 5)। चरण 4: Z = 0, 16, 14, 5। चरण 5: अधिकतम Z = 16, (4, 0) पर।
3. एक बेकरी केक और ब्रेड बनाती है। केक को 2 घंटे ओवन और 1 kg आटा; ब्रेड को 1 घंटा ओवन और 1 kg आटा चाहिए। रोज़ 10 घंटे ओवन और 7 kg आटा है। लाभ: केक ₹50, ब्रेड ₹30। किसके कितने बनाएँ कि लाभ सबसे ज़्यादा हो?
चरण 1: माना x = केक, y = ब्रेड। चरण 2: ओवन: 2x + y ≤ 10। आटा: x + y ≤ 7। x, y ≥ 0। Z = 50x + 30y अधिकतम करना है। चरण 3: 2x + y = 10 → (5, 0), (0, 10); x + y = 7 → (7, 0), (0, 7)। कटान: घटाने पर x = 3, y = 4। चरण 4: कोने (0, 0), (5, 0), (3, 4), (0, 7)। Z = 0, 250, 150 + 120 = 270, 210। चरण 5: 3 केक और 4 ब्रेड बनाओ, सबसे ज़्यादा लाभ ₹270।
4. Z = 2x + 3y को न्यूनतम करो, जबकि x + y ≥ 3, x + 2y ≥ 4, x, y ≥ 0।
चरण 1: x + y = 3 → (3, 0), (0, 3); x + 2y = 4 → (4, 0), (0, 2)। चरण 2: (0, 0) रखने पर 0 ≥ 3 गलत, तो मूल बिंदु से दूर वाली तरफ़ रंगो। क्षेत्र ऊपर खुला है: अपरिबद्ध। चरण 3: कोने: (0, 3), (4, 0) और कटान: घटाने पर y = 1, x = 2 → (2, 1)। चरण 4: Z = 9, 8, 7। सबसे छोटा कोनीय मान m = 7। चरण 5: खुला अर्ध-तल 2x + 3y < 7 क्षेत्र के नीचे है, कोई साझा बिंदु नहीं। तो न्यूनतम Z = 7, (2, 1) पर।
5. आहार समस्या: भोजन A ₹4 प्रति इकाई, इसमें 2 इकाई विटामिन और 1 इकाई खनिज। भोजन B ₹5 प्रति इकाई, इसमें 1 इकाई विटामिन और 2 इकाई खनिज। कम से कम 8 इकाई विटामिन और 10 इकाई खनिज चाहिए। सबसे सस्ता मेल निकालो।
चरण 1: x = A की इकाइयाँ, y = B की इकाइयाँ। C = 4x + 5y न्यूनतम करना है। चरण 2: विटामिन: 2x + y ≥ 8। खनिज: x + 2y ≥ 10। x, y ≥ 0। चरण 3: 2x + y = 8 → (4, 0), (0, 8); x + 2y = 10 → (10, 0), (0, 5)। कटान: y = 8 − 2x रखो; x + 16 − 4x = 10 → x = 2, y = 4। चरण 4: कोने (0, 8), (2, 4), (10, 0)। C = 40, 28, 40। चरण 5: क्षेत्र अपरिबद्ध है, 4x + 5y < 28 जाँचो: क्षेत्र से कोई साझा बिंदु नहीं। सबसे सस्ता: A की 2 और B की 4 इकाइयाँ, ₹28।
6. Z = x + 2y को अधिकतम करो, जबकि x + y ≤ 6, x ≤ 4, y ≤ 5, x, y ≥ 0 (तीन व्यवरोध)।
चरण 1: रेखाएँ: x + y = 6, x = 4 (खड़ी), y = 5 (आड़ी)। चरण 2: सब ≤ हैं, मूल बिंदु की ओर रंगो। चरण 3: कोने: (0, 0), (4, 0), x = 4 और x + y = 6 का मिलन (4, 2), y = 5 और x + y = 6 का मिलन (1, 5), और (0, 5)। चरण 4: Z = 0, 4, 8, 11, 10। चरण 5: अधिकतम Z = 11, (1, 5) पर।
7. Z = 2x + 2y को अधिकतम करो, जबकि x + y ≤ 4, x + 2y ≤ 6, x, y ≥ 0।
चरण 1: क्षेत्र उदाहरण 1 जैसा, कोने (0, 0), (4, 0), (2, 2), (0, 3)। चरण 2: Z = 0, 8, 8, 6। चरण 3: दो पड़ोसी कोने (4, 0) और (2, 2) दोनों 8 देते हैं। चरण 4: तो इन्हें जोड़ने वाले रेखाखंड का हर बिंदु Z = 8 देता है। अनंत इष्टतम हल हैं; अधिकतम Z = 8।
8. दिखाओ कि x + y ≥ 3, x + 2y ≥ 4, x, y ≥ 0 पर Z = x + y का अधिकतम नहीं है। और अगर नियम x + y ≤ 2 और x + y ≥ 5 हों तो क्या होगा?
भाग 1: कोने (0, 3), (2, 1), (4, 0), Z = 3, 3, 4। सबसे बड़ा कोनीय मान 4 है। अर्ध-तल x + y > 4 जाँचो: बिंदु (10, 10) इसमें भी है और सुसंगत क्षेत्र में भी। तो Z बढ़ता ही जाता है: अधिकतम नहीं। भाग 2: कोई संख्या एक साथ 2 से छोटी-बराबर और 5 से बड़ी-बराबर नहीं हो सकती। रंगे भाग कभी नहीं मिलते, सुसंगत क्षेत्र खाली है, LPP असुसंगत है, कोई हल नहीं।
आम गलतियाँ
- x ≥ 0 और y ≥ 0 भूल जाना। तब क्षेत्र गलती से ऋणात्मक मानों में फैल जाता है।
- गलत तरफ़ रंगना। हमेशा (0, 0) से जाँचो (अगर रेखा मूल बिंदु से जाए तो कोई और बिंदु लो)।
- अपरिबद्ध क्षेत्र में खुले अर्ध-तल ax + by > M की जाँच किए बिना अधिकतम बता देना।
- कोई कोना छूट जाना, ख़ासकर दो रेखाओं का कटान बिंदु। उसे दोनों समीकरण हल करके सही निकालो, ग्राफ़ से अंदाज़े से नहीं।