Chapter 12 Linear Programming

Notes

अध्याय 12 – रैखिक प्रोग्रामन (Linear Programming)

1. रैखिक प्रोग्रामन समस्या (Linear Programming Problem – LPP)

रैखिक प्रोग्रामन समस्या एक ऐसी गणितीय समस्या है, जिसमें दिए गए रैखिक व्यवरोधों (Linear Constraints) के अंतर्गत किसी रैखिक उद्देश्य फलन (Linear Objective Function) का अधिकतम या न्यूनतम मान ज्ञात किया जाता है।

रैखिक प्रोग्रामन में चर तथा दी गई शर्तें रैखिक रूप में होती हैं।

1.1 उद्देश्य फलन (Objective Function)

जिस रैखिक फलन का अधिकतम या न्यूनतम मान ज्ञात करना होता है, उसे उद्देश्य फलन कहते हैं।

इसे सामान्यतः निम्नलिखित रूप में लिखा जाता है:

Z = ax + by

यहाँ x तथा y चर हैं, जबकि a तथा b अचर हैं।

इसका उद्देश्य Z का अधिकतम या न्यूनतम मान ज्ञात करना है।

1.2 व्यवरोध (Constraints)

रैखिक असमिकाओं (Linear Inequalities) के रूप में दी गई शर्तों को व्यवरोध कहते हैं।

उदाहरण:

• x + y ≤ 4
• x + 2y ≤ 8
• 2x + y ≥ 3

x तथा y के मानों को दिए गए सभी व्यवरोधों को संतुष्ट करना चाहिए।

1.3 अनऋणात्मक व्यवरोध (Non-Negativity Constraints)

निम्नलिखित शर्तें:

x ≥ 0 तथा y ≥ 0

अनऋणात्मक व्यवरोध कहलाती हैं।

इन शर्तों के कारण सुसंगत क्षेत्र प्रथम चतुर्थांश तथा उसकी सीमा बनाने वाले निर्देशांक अक्षों तक सीमित रहता है।

1.4 सुसंगत क्षेत्र (Feasible Region)

वह उभयनिष्ठ क्षेत्र जो दिए गए सभी व्यवरोधों तथा अनऋणात्मक शर्तों को संतुष्ट करता है, सुसंगत क्षेत्र कहलाता है।

ग्राफ में इसे उभयनिष्ठ छायांकित क्षेत्र द्वारा दर्शाया जाता है।

1.5 आलेखीय विधि (Graphical Method)

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

हल करने के चरण:

1. उद्देश्य फलन तथा सभी व्यवरोधों को लिखिए।
2. प्रत्येक रैखिक असमिका को समानता में बदलकर उसकी सीमा रेखा प्राप्त कीजिए।
3. प्रत्येक रेखा पर दो उपयुक्त बिंदु ज्ञात कीजिए। सामान्यतः अक्षों पर उसके अंतःखंड लिए जाते हैं।
4. निर्देशांक तल पर सभी रेखाएँ खींचिए।
5. जहाँ उपयुक्त हो, वहाँ परीक्षण बिंदु जैसे (0, 0) की सहायता से सही अर्धतल ज्ञात कीजिए।
6. सभी व्यवरोधों को संतुष्ट करने वाला उभयनिष्ठ सुसंगत क्षेत्र ज्ञात कीजिए।
7. सुसंगत क्षेत्र के शीर्ष बिंदु (Corner Points) ज्ञात कीजिए।
8. प्रत्येक शीर्ष बिंदु के निर्देशांक उद्देश्य फलन Z में रखिए।
9. प्राप्त मानों की तुलना करके आवश्यक अधिकतम या न्यूनतम मान ज्ञात कीजिए।

2. हल किया हुआ उदाहरण 1 – अधिकतमकरण (Maximisation)

प्रश्न: निम्नलिखित उद्देश्य फलन का अधिकतम मान ज्ञात कीजिए:

Z = 3x + 4y

निम्नलिखित व्यवरोधों के अंतर्गत:

x + y ≤ 4

x ≥ 0, y ≥ 0

हल

दिया गया उद्देश्य फलन है:

Z = 3x + 4y

व्यवरोध है:

x + y ≤ 4 ...(A)

असमिका को समानता में बदलने पर:

x + y = 4 ...(1)

समीकरण (1) से निम्नलिखित मान प्राप्त होते हैं:

रेखा x + y = 4 बिंदुओं (0, 4) तथा (4, 0) से होकर गुजरती है।

व्यवरोध (A) में (0, 0) रखने पर:

0 + 0 ≤ 4

0 ≤ 4 (संतुष्ट)

अतः हम उस क्षेत्र का चयन करेंगे जिसमें मूलबिंदु (0, 0) स्थित है।

अनऋणात्मक व्यवरोधों के अनुसार आवश्यक सुसंगत क्षेत्र त्रिभुज OAB है।

शीर्ष बिंदु हैं:

• O(0, 0)
• A(4, 0)
• B(0, 4)

उद्देश्य फलन के मान

बिंदु O(0, 0) पर:

Z = 3(0) + 4(0) = 0

बिंदु A(4, 0) पर:

Z = 3(4) + 4(0) = 12

बिंदु B(0, 4) पर:

Z = 3(0) + 4(4) = 16

उत्तर:

Z का अधिकतम मान = 16, जो B(0, 4) पर प्राप्त होता है।

3. हल किया हुआ उदाहरण 2 – न्यूनतमकरण (Minimisation)

प्रश्न: निम्नलिखित उद्देश्य फलन का न्यूनतम मान ज्ञात कीजिए:

Z = −3x + 4y

निम्नलिखित व्यवरोधों के अंतर्गत:

x + 2y ≤ 8

−3x + 2y ≤ 12

x ≥ 0, y ≥ 0

हल

उद्देश्य फलन है:

Z = −3x + 4y

दिए गए व्यवरोध:

x + 2y ≤ 8 ...(A)

−3x + 2y ≤ 12 ...(B)

असमिकाओं को समानताओं में बदलने पर:

x + 2y = 8 ...(1)

−3x + 2y = 12 ...(2)

समीकरण (1) के लिए

x + 2y = 8

यह रेखा बिंदुओं (0, 4) तथा (8, 0) से होकर गुजरती है।

समीकरण (2) के लिए

−3x + 2y = 12

यह रेखा बिंदुओं (0, 6) तथा (−4, 0) से होकर गुजरती है।

व्यवरोधों की जाँच

व्यवरोध (A) में (0, 0) रखने पर:

0 ≤ 8 (संतुष्ट)

व्यवरोध (B) में (0, 0) रखने पर:

0 ≤ 12 (संतुष्ट)

अतः आवश्यक सुसंगत क्षेत्र प्रथम चतुर्थांश में दोनों असमिकाओं को संतुष्ट करने वाला उभयनिष्ठ क्षेत्र होगा।

यहाँ दूसरा व्यवरोध, पहले व्यवरोध से बने त्रिभुजाकार क्षेत्र को और सीमित नहीं करता है।

सुसंगत क्षेत्र त्रिभुज OCD है, जिसके शीर्ष बिंदु हैं:

• O(0, 0)
• C(8, 0)
• D(0, 4)

उद्देश्य फलन के मान

बिंदु O(0, 0) पर:

Z = −3(0) + 4(0) = 0

बिंदु C(8, 0) पर:

Z = −3(8) + 4(0) = −24

बिंदु D(0, 4) पर:

Z = −3(0) + 4(4) = 16

उत्तर:

Z का न्यूनतम मान = −24, जो C(8, 0) पर प्राप्त होता है।

4. हल किया हुआ उदाहरण 3 – अधिकतमकरण (Maximisation)

प्रश्न: निम्नलिखित उद्देश्य फलन का अधिकतम मान ज्ञात कीजिए:

Z = 5x + 3y

निम्नलिखित व्यवरोधों के अंतर्गत:

3x + 5y ≤ 15

5x + 2y ≤ 10

x ≥ 0, y ≥ 0

हल

उद्देश्य फलन है:

Z = 5x + 3y

व्यवरोध:

3x + 5y ≤ 15 ...(A)

5x + 2y ≤ 10 ...(B)

असमिकाओं को समानताओं में बदलने पर:

3x + 5y = 15 ...(1)

5x + 2y = 10 ...(2)

समीकरण (1) के लिए

3x + 5y = 15

यह रेखा बिंदुओं (0, 3) तथा (5, 0) से होकर गुजरती है।

समीकरण (2) के लिए

5x + 2y = 10

यह रेखा बिंदुओं (0, 5) तथा (2, 0) से होकर गुजरती है।

व्यवरोधों की जाँच

व्यवरोध (A) में (0, 0) रखने पर:

0 ≤ 15 (संतुष्ट)

व्यवरोध (B) में (0, 0) रखने पर:

0 ≤ 10 (संतुष्ट)

अतः सुसंगत क्षेत्र वह उभयनिष्ठ क्षेत्र होगा जिसमें मूलबिंदु स्थित है।

प्रतिच्छेद बिंदु ज्ञात करना

समीकरण (1) तथा (2) को हल करने पर:

3x + 5y = 15

5x + 2y = 10

पहले समीकरण में 2 से गुणा करने पर:

6x + 10y = 30

दूसरे समीकरण में 5 से गुणा करने पर:

25x + 10y = 50

दोनों समीकरणों को घटाने पर:

19x = 20

x = 20/19

अब 5x + 2y = 10 में मान रखने पर:

5(20/19) + 2y = 10

100/19 + 2y = 190/19

2y = 90/19

y = 45/19

अतः प्रतिच्छेद बिंदु है:

E(20/19, 45/19)

सुसंगत क्षेत्र के शीर्ष बिंदु हैं:

• O(0, 0)
• B(0, 3)
• E(20/19, 45/19)
• C(2, 0)

उद्देश्य फलन के मान

बिंदु O(0, 0) पर:

Z = 5(0) + 3(0) = 0

बिंदु B(0, 3) पर:

Z = 5(0) + 3(3) = 9

बिंदु C(2, 0) पर:

Z = 5(2) + 3(0) = 10

बिंदु E(20/19, 45/19) पर:

Z = 5(20/19) + 3(45/19)

Z = (100 + 135)/19

Z = 235/19

उत्तर:

Z का अधिकतम मान = 235/19, जो E(20/19, 45/19) पर प्राप्त होता है।

5. हल किया हुआ उदाहरण 4 – न्यूनतमकरण (Minimisation)

प्रश्न: निम्नलिखित उद्देश्य फलन का न्यूनतम मान ज्ञात कीजिए:

Z = x + 2y

निम्नलिखित व्यवरोधों के अंतर्गत:

2x + y ≥ 3

x + 2y ≥ 6

x ≥ 0, y ≥ 0

हल

उद्देश्य फलन है:

Z = x + 2y

व्यवरोध:

2x + y ≥ 3 ...(A)

x + 2y ≥ 6 ...(B)

असमिकाओं को समानताओं में बदलने पर:

2x + y = 3 ...(1)

x + 2y = 6 ...(2)

समीकरण (1) के लिए

2x + y = 3

समीकरण (2) के लिए

x + 2y = 6

व्यवरोधों की जाँच

व्यवरोध (A) में (0, 0) रखने पर:

0 ≥ 3 (संतुष्ट नहीं)

व्यवरोध (B) में (0, 0) रखने पर:

0 ≥ 6 (संतुष्ट नहीं)

अतः सुसंगत क्षेत्र मूलबिंदु से दूर उस ओर स्थित होगा जहाँ दोनों असमिकाएँ संतुष्ट होती हैं।

यह सुसंगत क्षेत्र अपरिबद्ध (Unbounded) है।

शीर्ष बिंदु

शीर्ष बिंदु हैं:

• B(0, 3)
• C(6, 0)

उद्देश्य फलन के मान

बिंदु B(0, 3) पर:

Z = 0 + 2(3) = 6

बिंदु C(6, 0) पर:

Z = 6 + 2(0) = 6

उत्तर:

Z का न्यूनतम मान = 6 है।

यह न्यूनतम मान B(0, 3), C(6, 0) तथा इन दोनों बिंदुओं को मिलाने वाले रेखाखंड के प्रत्येक बिंदु पर प्राप्त होता है।

6. हल किया हुआ उदाहरण 5 – अधिकतमकरण एवं न्यूनतमकरण

प्रश्न: निम्नलिखित उद्देश्य फलन का अधिकतम तथा न्यूनतम मान ज्ञात कीजिए:

Z = 5x + 10y

निम्नलिखित व्यवरोधों के अंतर्गत:

x + 2y ≤ 120

x + y ≥ 60

x − 2y ≥ 0

x ≥ 0, y ≥ 0

हल

उद्देश्य फलन है:

Z = 5x + 10y

दिए गए व्यवरोध:

x + 2y ≤ 120 ...(A)

x + y ≥ 60 ...(B)

x − 2y ≥ 0 ...(C)

असमिकाओं को समानताओं में बदलने पर:

x + 2y = 120 ...(1)

x + y = 60 ...(2)

x − 2y = 0 ...(3)

समीकरण (1) के लिए

x + 2y = 120

समीकरण (2) के लिए

x + y = 60

समीकरण (3) के लिए

x − 2y = 0

x = 2y

प्रतिच्छेद बिंदु ज्ञात करना

समीकरण (2) तथा (3) का प्रतिच्छेद:

x + y = 60

x = 2y

मान रखने पर:

2y + y = 60

3y = 60

y = 20

x = 40

अतः:

D(40, 20)

समीकरण (1) तथा (3) का प्रतिच्छेद:

x + 2y = 120

x = 2y

मान रखने पर:

2y + 2y = 120

4y = 120

y = 30

x = 60

अतः:

E(60, 30)

व्यवरोधों की जाँच

व्यवरोध (A) में (0, 0) रखने पर:

0 ≤ 120 (संतुष्ट)

व्यवरोध (B) में (0, 0) रखने पर:

0 ≥ 60 (संतुष्ट नहीं)

व्यवरोध (C) के लिए:

x − 2y ≥ 0

अतः आवश्यक क्षेत्र रेखा x = 2y पर या उसके नीचे स्थित होगा।

उभयनिष्ठ सुसंगत क्षेत्र चतुर्भुज CAED है।

शीर्ष बिंदु हैं:

• C(60, 0)
• A(120, 0)
• E(60, 30)
• D(40, 20)