ग्राफ़ से बीजगणित तक: सिंप्लेक्स क्यों?
आलेखीय विधि में रैखिक उद्देश्य का सबसे अच्छा मान हमेशा संभव क्षेत्र के किसी कोने (शीर्ष) पर मिलता है। 3 या ज़्यादा चरों में क्षेत्र बन नहीं सकता, इसलिए कोने से कोने चलने का बीजगणितीय तरीक़ा चाहिए।
सिंप्लेक्स विधि एक कोने (आम तौर पर मूल बिंदु) से शुरू होकर किनारे के साथ ऐसे पड़ोसी कोने पर जाती है जहाँ उद्देश्य बेहतर हो। जब कोई पड़ोसी बेहतर न हो, रुक जाती है।
स्लैक चर और पहली तालिका
स्लैक चर किसी संसाधन का बचा हुआ हिस्सा नापता है। x + y ≤ 4 को लिखो x + y + r = 4, जहाँ r ≥ 0।
उदाहरण: P = 3x + 2y अधिकतम करो, शर्तें x + y ≤ 4, x + 3y ≤ 9, x ≤ 3, x, y ≥ 0। उद्देश्य को लिखो P − 3x − 2y = 0।
| आधारी | x | y | r | s | t | मान |
|---|---|---|---|---|---|---|
| r | 1 | 1 | 1 | 0 | 0 | 4 |
| s | 1 | 3 | 0 | 1 | 0 | 9 |
| t | 1 | 0 | 0 | 0 | 1 | 3 |
| P | −3 | −2 | 0 | 0 | 0 | 0 |
आधारी चर (r, s, t) के स्तंभ में एक 1 और बाक़ी शून्य हैं। अनाधारी चर (x, y) = 0। यानी यह तालिका कोना (0, 0) और P = 0 बताती है।
पिवट: स्तंभ, अनुपात परीक्षण, पंक्ति संक्रियाएँ
- पिवट स्तंभ: उद्देश्य पंक्ति की सबसे ऋणात्मक प्रविष्टि (यहाँ x, −3)। x बढ़ाने से P प्रति इकाई सबसे तेज़ बढ़ता है।
- अनुपात परीक्षण: उस स्तंभ में धनात्मक प्रविष्टि वाली हर पंक्ति के लिए मान ÷ प्रविष्टि: 4/1, 9/1, 3/1। सबसे छोटा (3, पंक्ति t) पिवट पंक्ति है — यही शर्त सबसे पहले ख़त्म होती है।
- पिवट को 1 बनाओ: पिवट पंक्ति को पिवट अवयव से भाग दो।
- स्तंभ साफ़ करो: पिवट पंक्ति के गुणज जोड़/घटाकर स्तंभ की बाक़ी प्रविष्टियाँ 0 करो।
- प्रवेश करने वाला चर (x) निकलने वाले (t) की जगह आधारी सूची में आता है।
पिवट 1 के बाद: x = 3, r = 1, s = 6, P = 9 (कोना (3, 0))। P पंक्ति: 0, −2, 0, 0, 3 | 9। अब भी −2 है, तो y पर पिवट: अनुपात 1/1 = 1 और 6/3 = 2, यानी पंक्ति r। पिवट 2 के बाद P पंक्ति 0, 0, 2, 0, 1 | 11।
सिंप्लेक्स तालिका पढ़ना
- इष्टतम? अधिकतम करते समय जब उद्देश्य पंक्ति में कोई ऋणात्मक प्रविष्टि न हो।
- मान: हर आधारी चर अपनी पंक्ति के मान के बराबर; सारे अनाधारी चर 0। अंतिम: y = 1, s = 3, x = 3, r = t = 0, P = 11।
- स्लैक का अर्थ: s = 3 यानी दूसरे संसाधन की 3 इकाई बची; r = t = 0 यानी वे संसाधन पूरे इस्तेमाल हुए (बंधनकारी)।
- स्लैक स्तंभों के नीचे P पंक्ति की संख्याएँ (r के लिए 2, t के लिए 1) बताती हैं कि उस संसाधन की एक और इकाई से P कितना बढ़ेगा (छाया मूल्य)।
- अंतिम P पंक्ति में किसी अनाधारी चर के नीचे 0 हो तो और भी इष्टतम हल हैं; पिवट स्तंभ में कोई धनात्मक प्रविष्टि न हो तो P असीमित है।
सिंप्लेक्स से न्यूनतम करना, और ≥ शर्तें
C न्यूनतम करना हो तो P = −C अधिकतम करो, वही चरण अपनाओ; अंत में C = −P।
उदाहरण: C = x − 2y न्यूनतम करो, x + y ≤ 6, y ≤ 4। P = −x + 2y अधिकतम करो: P पंक्ति 1, −2। y पर पिवट (अनुपात 6 और 4 → पंक्ति 2): y = 4, P = 8, तो न्यूनतम C = −8, बिंदु (0, 4) पर।
अगर शर्त ≥ हो, तो मूल बिंदु संभव नहीं। तब एक अधिशेष (surplus) चर घटाओ और एक कृत्रिम (artificial) चर जोड़ो, और दो-चरण विधि (पहले कृत्रिम चर हटाओ) या बिग-M विधि (कृत्रिम चरों पर बहुत बड़ा दंड M) अपनाओ।
खुद करो: कोनों से जाँचो
उदाहरण के संभव क्षेत्र के सारे कोने लिखो: (0, 0), (3, 0), (3, 1), (1.5, 2.5), (0, 3)। हर एक पर P = 3x + 2y निकालो। क्या सबसे बड़ा मान सिंप्लेक्स के 11 से मिलता है? अब उद्देश्य P = x + 2y करके सिंप्लेक्स फिर चलाओ। कौन-सा कोना जीतता है? (3D के स्लाइडर से जाँचो।)
मुख्य सूत्र और परिभाषाएँ
- स्लैक: a·x + b·y ≤ c → a·x + b·y + s = c, s ≥ 0
- उद्देश्य पंक्ति: P − 3x − 2y = 0
- पिवट स्तंभ = P पंक्ति की सबसे ऋणात्मक प्रविष्टि
- अनुपात परीक्षण: मान ÷ धनात्मक प्रविष्टि; सबसे छोटा चुनो
- इष्टतम (अधिकतम) जब P पंक्ति में कोई ऋणात्मक न हो
- C न्यूनतम ⇔ P = −C अधिकतम
हल किए गए उदाहरण
1. शर्तें x + 2y ≤ 10 और 3x + y ≤ 15 को स्लैक चरों के साथ लिखो।
x + 2y + s₁ = 10 और 3x + y + s₂ = 15, जहाँ s₁, s₂ ≥ 0।
2. P = 5x + 4y अधिकतम करो, 2x + y ≤ 8, x + 2y ≤ 7, x, y ≥ 0। पहला पिवट करो।
P पंक्ति: −5, −4। पिवट स्तंभ x (−5)। अनुपात 8/2 = 4, 7/1 = 7 → पंक्ति 1, पिवट 2। पंक्ति 1 को 2 से भाग: x + 0.5y + 0.5r = 4। पंक्ति 2 − पंक्ति 1: 1.5y − 0.5r + s = 3। P पंक्ति + 5×पंक्ति 1: −1.5y + 2.5r = 20। यानी x = 4, s = 3, P = 20।
3. उदाहरण 2 पूरा करो।
y के नीचे अब भी −1.5 है। अनुपात 4/0.5 = 8, 3/1.5 = 2 → पंक्ति 2, पिवट 1.5। भाग: y − r/3 + 2s/3 = 2। पंक्ति 1 − 0.5×नई पंक्ति: x + 2r/3 − s/3 = 3। P पंक्ति + 1.5×नई पंक्ति: 2r + s = 23। कोई ऋणात्मक नहीं, तो इष्टतम: x = 3, y = 2, P = 23।
4. C = x − 2y न्यूनतम करो, x + y ≤ 6, y ≤ 4, x, y ≥ 0।
P = −x + 2y अधिकतम, यानी P + x − 2y = 0। पिवट स्तंभ y (−2)। अनुपात 6/1 = 6, 4/1 = 4 → पंक्ति 2। फिर y = 4, पहला स्लैक = 2, P पंक्ति 1, 0, 0, 2 | 8। इष्टतम: P = 8, तो C = −8, x = 0, y = 4 पर।
5. अंतिम तालिका की पंक्तियाँ: x | 1 0 0.5 −0.5 | 6; y | 0 1 −0.25 0.75 | 2; P | 0 0 1.5 0.5 | 42 (स्तंभ x, y, s₁, s₂)। हल पढ़ो।
P पंक्ति में ऋणात्मक नहीं → इष्टतम। आधारी: x = 6, y = 2। अनाधारी: s₁ = s₂ = 0 (दोनों संसाधन पूरे इस्तेमाल)। P = 42। संसाधन 1 की हर अतिरिक्त इकाई P में 1.5 जोड़ेगी।
6. P = 3x + 2y + 4z अधिकतम करो, x + y + 2z ≤ 4, 2x + y + 3z ≤ 5, x, y, z ≥ 0।
पिवट 1: z (−4); अनुपात 4/2 = 2, 5/3 ≈ 1.67 → पंक्ति 2। P = 20/3, P पंक्ति में −1/3 (x), −2/3 (y)। पिवट 2: y; अनुपात 2 (पंक्ति 1) और 5 → पंक्ति 1। P = 8, पर x पर अब भी −1। पिवट 3: x; सिर्फ़ z पंक्ति में धनात्मक (अनुपात 1)। अंतिम: x = 1, y = 3, z = 0, P = 9। जाँच: 1 + 3 = 4 ✓, 2 + 3 = 5 ✓।
आम गलतियाँ
- अधिकतम करते समय P पंक्ति की सबसे बड़ी धनात्मक संख्या को पिवट स्तंभ चुनना। सबसे ऋणात्मक चुनो।
- अनुपात परीक्षण में शून्य या ऋणात्मक प्रविष्टि वाली पंक्तियाँ लेना। सिर्फ़ धनात्मक गिनो।
- पिवट के समय P पंक्ति या "आधारी चर" का नाम बदलना भूल जाना।
- अनाधारी चर का कोई मान पढ़ना। अनाधारी चर हमेशा 0 होते हैं।