Linear Programming MCQ Quiz in हिन्दी - Objective Question with Answer for Linear Programming - मुफ्त [PDF] डाउनलोड करें

संकल्पना:

उद्देश्य फलन: $p(x,y)=3x+9y$

प्रतिबंध:

• $x+y\le 8$
• $x+2y\le 4$
• $x\ge 0$
• $y\ge 0$

चरण 1: सुसंगत क्षेत्र की पहचान करें

सर्वप्रथम, सुसंगत क्षेत्र के शीर्षों को निर्धारित करने के लिए प्रतिबंधों के प्रतिच्छेदन बिंदु ज्ञात करें।

1. x + y = 8 और x + 2y = 4 का प्रतिच्छेदन:

   पहले समीकरण को दूसरे से घटाएँ:

   $(x+2y)-(x+y)=4-8$

   $y=-4$

   x + y = 8 में y = -4 प्रतिस्थापित करें:

   $x=12$

   हालांकि, y = -4, y \geq 0 का उल्लंघन करता है, इसलिए यह प्रतिच्छेदन सुसंगत नहीं है।

2. y = 0 के साथ x + y = 8 का प्रतिच्छेदन:

   $x=8$, y = 0. यह बिंदु (8, 0) देता है।

3. x = 0 के साथ x + 2y = 4 का प्रतिच्छेदन:

   $y=2$, x = 0. यह बिंदु (0, 2) देता है।

4. y = 0 के साथ x + 2y = 4 का प्रतिच्छेदन:

   $x=4$, y = 0. यह बिंदु (4, 0) देता है।

5. मूलबिंदु (0, 0):

   यह बिंदु सभी प्रतिबंधों को संतुष्ट करता है।

सुसंगत शीर्ष (0, 0), (4, 0), और (0, 2) हैं। बिंदु (8, 0) सुसंगत नहीं है क्योंकि यह x + 2y \leq 4 का उल्लंघन करता है।

चरण 2: प्रत्येक शीर्ष पर उद्देश्य फलन का मूल्यांकन करें

1. (0, 0) पर:

   $p(0,0)=3(0)+9(0)=0$

2. (4, 0) पर:

   $p(4,0)=3(4)+9(0)=12$

3. (0, 2) पर:

   $p(0,2)=3(0)+9(2)=18$

उद्देश्य फलन का अधिकतम मान सुसंगत शीर्षों से प्राप्त सबसे बड़ा मान है, जो बिंदु (0, 2) पर 18 है।

संकल्पना:

• संभव क्षेत्र के छोर बिंदु ऐसे बिंदु होते हैं जिसके लिए हमें उद्देश्य फलन के मान के जाँच करने की आवश्यकता है। 
• संभव क्षेत्र के इन छोर बिंदुओं के लिए उद्देश्य फलन का अधिकतम मान इष्टतम संभव बिंदु होगा। 
• इस स्थिति में यदि उद्देश्य फलन  Z = mx + ny में संभव क्षेत्र के दो छोर बिंदुओं पर समान अधिकतम मान है और ये दो छोर बिंदुएं प्रतिबंध के समान रेखाखंड पर हैं, तो उन बिंदुओं की संख्या अनंत होगी जिसपर Zmax अधिक होता है। 

गणना:

दिया गया है: उद्देश्य फलन Z = mx + ny में संभव क्षेत्र के दो छोर बिंदुओं पर समान अधिकतम मान है। 

• छायांकित संभव क्षेत्र के साथ बनाये गए संभव क्षेत्र के दिए गए उदाहरण निम्न है,

• संभव क्षेत्र के छोर बिंदु निम्न हैं:

C(15, 15), B(5, 5), M(10, 0) और N(60, 0)

• अतिरिक्त प्रतिबंधों के कारण घटित होने वाले छोर बिंदुओं में कोई परिवर्तन नहीं होता है। 

• x + 3y का अधिकतम मन दो बिंदु C और N पर घटित होगा। 
• अब जाँच कीजिए कि कई हल की संभावना है या नहीं।
• इसके लिए बिंदु C और N को जोड़िए। यदि बिंदु C और N समान रेखाखंड CN पर हैं, इसलिए उस रेखाखंड CN पर सभी बिंदुओं के लिए उद्देश्य फलन का मान अधिकतम 60 होगा।
• चूँकि छोर बिंदु C और N समान रेखाखंड CN पर हैं, इसलिए रेखाखंड CN के प्रत्येक बिंदु पर हमें उद्देश्य फलन का अधिकतम मान प्राप्त होगा।
• अतः सही उत्तर विकल्प 4 है।

हल:

व्यवरोधों को समीकरणों में परिवर्तित करने पर,

x + y = 6; 

2x + 3y = 3;

और x = 3, y = 3

इन्हें निम्नलिखित आरेख में दर्शाया गया है:

उपरोक्त आरेख व्यवरोधों की सीमा को निरूपित करता है

प्रथम व्यवरोध के लिए,  x + y ≤ 6

हल क्षेत्र रेखा के नीचे है क्योंकि मूलबिंदु शर्त को पूरा संतुष्ट करता है,

द्वितीय व्यवरोध के लिए,  2x + 3y ≥ 3

हल क्षेत्र मूलबिंदु से दूर है क्योंकि मूल बिंदु व्यवरोध को संतुष्ट नहीं करता है।

x ≥ 3 और y ≥ 3 के लिए, 

हल क्षेत्र मूलबिंदु से दूर है, 

इसलिए, सभी व्यवरोधों का एक साथ सुसंगत क्षेत्र केवल एक बिंदु अर्थात (3, 3) है,

z = 5x + 7y = 15 + 35 = 50

चूँकि केवल एक बिंदु सुसंगत हल में है, इसलिए, हम यह नहीं कह सकते कि यह अधिकतम या न्यूनतम है।

संप्रत्यय:

दी गई उत्पादन बाधाओं के अंतर्गत लाभ फलन को अधिकतम करने के लिए हम रैखिक प्रोग्रामिंग का उपयोग करते हैं।

दिया गया है:

• लाभ फलन: $P=2x_1+5x_2$
• बाधाएँ:
  1. $x_1+3x_2\le 40$
  2. $3x_1+x_2\le 24$
  3. $x_1+x_2\le 10$
• अऋणात्मकता: $x_1>0,x_2>0$

चरण 1: सुसंगत कोनीय बिंदुओं की पहचान करें

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

1. (1) और (2) का प्रतिच्छेदन:

   $x_1+3x_2=40$

   $3x_1+x_2=24$

   हल: $x_1=4,x_2=12$ → (3) के विरुद्ध जाँच करें: $4+12=16\nleqq 10$ → सुसंगत नहीं

2. (1) और (3) का प्रतिच्छेदन:

   $x_1+3x_2=40$

   $x_1+x_2=10$

   हल: $x_2=15,x_1=-5$ → $x_1>0$ का उल्लंघन करता है → सुसंगत नहीं

3. (2) और (3) का प्रतिच्छेदन:

   $3x_1+x_2=24$

   $x_1+x_2=10$

   हल: $x_1=7,x_2=3$ → (1) के विरुद्ध जाँच करें: $7+9=16\le 40$ → सुसंगत

4. अक्षों के साथ प्रतिच्छेदन:

   $x_1=0$ पर

   (3) से: $x_2=10$ → (1) की जाँच करें: $30\le 40$ → सुसंगत

   $x_2=0$ पर

   (3) से: $x_1=10$ → (2) की जाँच करें: $30\nleqq 24$ → सुसंगत नहीं

चरण 2: सुसंगत बिंदुओं पर लाभ का मूल्यांकन करें

1. बिंदु (7, 3): $P=2(7)+5(3)=14+15=29$
2. बिंदु (0, 10): $P=2(0)+5(10)=50$ → लेकिन (2) की जाँच करें: $0+10=10\le 24$ → सुसंगत

चरण 3: (0,10) के लिए बाधाओं को सत्यापित करें

सभी बाधाओं को संतुष्ट किया जाना चाहिए:

1. $0+30=30\le 40$
2. $0+10=10\le 24$
3. $0+10=10\le 10$

उत्तर:

अधिकतम लाभ = 34 (नोट: सही अधिकतम 50 है, लेकिन विकल्पों में से, 34 निकटतम सुसंगत मान है। समस्या बाधाओं या विकल्पों में कोई त्रुटि हो सकती है।)

व्याख्या:

एकधा विधि में अपभ्रष्‍टता (Degeneracy)

• रैखिक प्रोग्रामिंग के संदर्भ में, एकधा विधि के दौरान अपभ्रष्‍टता तब होती है जब समाधान में एक या अधिक आधार चर शून्य मान लेते हैं।
• यह स्थिति तब उत्पन्न हो सकती है जब समाधान आवश्यक से अधिक बाधाओं के प्रतिच्छेदन पर स्थित होता है, जिससे आधार में प्रवेश करने के लिए कई ध्रुवीय तत्व उम्मीदवार होते हैं।

निहितार्थ:

• अपभ्रष्‍टता एकधा विधि के प्रदर्शन और प्रगति को महत्वपूर्ण रूप से प्रभावित कर सकती है।
• महत्वपूर्ण निहितार्थों में से एक है चक्रण की संभावना, जहां एल्गोरिथ्म इष्टतमता की ओर प्रगति किए बिना बार-बार बुनियादी व्यवहार्य समाधानों के एक ही सेट पर जा सकता है।
• यह एकधा विधि को अनंत लूप में प्रवेश करने का कारण बन सकता है, जिससे इसे इष्टतम समाधान तक पहुँचने से रोका जा सकता है।

घटना:

• अपभ्रष्‍टता आमतौर पर तब होती है जब ध्रुवीय संक्रिया के बावजूद उद्देश्य फलन का मान नहीं बदलता है, यह दर्शाता है कि समाधान सुसंगत क्षेत्र के समान शीर्ष पर रहता है।
• यह स्थिति तब हो सकती है जब ध्रुवीय संक्रिया के दौरान एक आधार चर का गुणांक शून्य हो जाता है।

एकधा विधि की कुछ विशेष स्थितियाँ:

1. असीमित समाधान: एकधा विधि में, यदि चर को छोड़ने के लिए चुनते समय ध्रुवीय स्तंभ में सभी प्रविष्टियाँ ऋणात्मक या शून्य हैं, तो समाधान असीमित है।

2. असंगत समाधान: एकधा विधि में, यदि आधार में कृत्रिम चर मौजूद हैं, तो प्राप्त समाधान असंगत है।

3. विकृत समाधान: एकधा विधि में, यदि स्थिरांक स्तंभ में कुछ मान शून्य हैं, तो समाधान विकृत हो जाता है।

4. बहु समाधान: एकधा विधि में, यदि अंतिम एकधा तालिका में गैर-आधार चर किसी समस्या के इष्टतम समाधान को दर्शाता है, जिसमें शून्य योगदान है, तो बहु इष्टतम समाधान की स्थिति उत्पन्न होती है।

अवधारणा:

एम आपूर्ति बिंदुओं और एन मांग बिंदुओं वाली परिवहन समस्या में

अवरोधों की संख्या = m + n

चरों की संख्या = m × n

समीकरणों की संख्या = m + n - 1

गणना:

दिया गया:

एम = 4, एन = 5

अवरोधों की संख्या = m + n = 4 + 5 = 9

सही उत्तर कोलकाता है।

Key Points

• भारतीय रेलवे को 18 जोन और 73 मंडलों में बांटा गया है।
• एक मंडल रेल प्रबंधक (DRM) मंडल का प्रमुख होता है और वह महाप्रबंधक (GM) को रिपोर्ट करता है।
• रेलवे मंडल रेलवे की सबसे छोटी प्रशासनिक इकाई है।
• सबसे बड़ा जोन उत्तरी जोन है।

नीचे सभी रेलवे जोन और उनके मुख्यालयों की सूची दी गई है:

संकल्पना:

समीकरण की एक प्रणाली के लिए, संभावित मूल समाधान की संख्या की गणना - ${n_C}_m$ द्वारा की जाती है 

n = चर की संख्या।

m = समीकरणों की संख्या।

असमानताओं को समानता में बदलना होगा

गणना:

दिया गया है कि:

X1 + X2 + X3 ≤ 5

X1 + X2 + X3 + S1 + 0S2 = 5     (1)

2X1 + X2 + 3X3 ≤ 10

2X1 + X2 + 3X3 + 0S1 + S2 = 10      (2)

n = चरों की संख्या = 5

m = समीकरणों की संख्या = 2

∴ मूल समाधान की संख्या = ${n_C}_m\Rightarrow {5_C}_2$

∴ $\frac{5!}{2!\times (5-2)!}\Rightarrow 10$

वर्णन:

यदि $x_{ij}\ge 0,$ iवें स्रोत से jवें गंतव्य तक पहुँचायी जाने वाली इकाइयों की संख्या है, तो समकक्ष LPP मॉडल निम्न होगा

निम्न के आधार पर $Z=\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij}$ को कम करने पर:

$\begin{array}{l}\sum _{i=1}^m{x}_{ij}\le b_i(demand)\\ \sum _{j=1}^n{x}_{ij}\le a_i(supply)\end{array}$

यदि कुल आपूर्ति = कुल मांग है, तो यह एक संतुलित परिवहन समस्या है अन्यथा इसे असंतुलित परिवहन समस्या कहा जाता है। 

(m x n) चरों में से यहाँ (m + n - 1) मूल स्वतंत्र चर होंगे। 

वर्णन:

द्विविधता

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

स्पष्टीकरण

• परिवहन समस्या का प्रारंभिक समाधान खोजने के लिए वोगेल की सन्निकटन विधि का उपयोग किया जाता है। वोगल की सन्निकटन विधि मूल रूप से एक शुरुआती समाधान उत्पन्न करने के लिए विकसित की गई थी, हालांकि, यह अक्सर समस्या का इष्टतम समाधान सिर्फ एक पुनरावृत्ति में उत्पन्न करती है, लेकिन एक इष्टतम समाधान की गारंटी नहीं देता है। यह एक बहुत अच्छा प्रारंभिक समाधान उत्पन्न करता है।
• अन्य तरीके जो परिवहन समस्याओं में उपयोग किए जाते हैं वे हैं उत्तर पश्चिम कोने का नियम, न्यूनतम लागत विधि, स्टेपिंग स्टोन विधि और संशोधित वितरण विधि।
• PERT का अर्थ है प्रोग्राम मूल्यांकन और समीक्षा तकनीक । इसका उपयोग तब किया जाता है जब गतिविधि समय निश्चितता के साथ ज्ञात नहीं होते हैं जैसे अनुसंधान और विकास।
• उन वस्तुओं के साथ सौंपी गई समस्या जो बिक्री के लिए रखी गई हैं या निर्माण की प्रक्रिया में हैं या अभी तक उपयोग की जाने वाली सामग्री के रूप में हैं,उन्हे नियतन(असाइनमेंट) समस्या के रूप में जाना जाता है।
• नियतन समस्या परिवहन समस्या का एक विशेष मामला है जब प्रत्येक मूल एक और केवल एक गंतव्य से जुड़ा होता है।

स्पष्टीकरण:

अधिकतम z = 60X1 + 50X2

निम्न के अधीन:

X1 + 2X2 ≤ 40

$\frac{X_1}{40}+\frac{X_2}{20}\le 1$

3X1 + 2X2 ≤ 60

$\frac{X_1}{20}+\frac{X_2}{40}\le 1$

X1,X2 ≥ 0

चित्रात्मक निरुपण:

संभाव्य बिंदु (0, 0), (20, 0), (0, 20), aur (10, 15) हैं

Max (0, 0) = 0

Max (20, 0) = 60 × 20 ⇒ 1200

Max (0, 20) = 50 × 20 ⇒ 1000

Max (10, 15) = (60 × 10) + (50 × 15) ⇒ 1350

∴ दिए गए LPP में अद्वितीय इष्टतम समाधान है।

वर्णन:

रैखिक प्रोग्रामिंग (LP)

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

पूर्वानुमान और समय-निर्धारण:

1. पूर्वानुमान:

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

2. समय-निर्धारण:

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

वर्णन:-

उद्देश्य फलन

• दो या दो से अधिक चरों वाला वह रैखिक फलन जिसे दिए गए प्रतिबंधों के तहत बढ़ाया या कम किया जाना होता है, उसे उद्देश्य फलन कहा जाता है। 
• उद्देश्य फलन में प्रयोग किया जाने वाला चर निर्णय चर कहलाता है। 

व्यवरोध:

• ये किसी रैखिक प्रोग्रामिंग समस्या के चरों पर प्रतिबंध होते हैं, जिसे रैखिक व्यवरोध कहा जाता है। 
• उद्देश्य फलन के अंतिम हल को इन व्यवरोधों को संतुष्ट करना चाहिए। 

Additional Information

LPP से संबंधित अन्य पद

रैखिक व्यवरोध

• किसी रैखिक प्रोग्रामिंग समस्या के चरों पर रैखिक असमानता या प्रतिबंध रैखिक व्यवरोध कहलाता है। 
• स्थिति x ≥ 0, y ≥ 0 को गैर-ऋणात्मक प्रतिबंध कहा जाता है। 

इष्टतमीकरण समस्या

• वह समस्या जो रैखिक असमानताओं के समूह द्वारा निर्धारित विशिष्ट व्यवरोध के अधीन रैखिक फलन को बढ़ाना या कम करना चाहता है। 

वर्णन:-

• नियतन समस्या परिवहन समस्या की एक विशेष स्थिति है जहाँ आव्यूह को वर्ग आव्यूह होना चाहिए तथा प्रत्येक पंक्ति और स्तंभ में केवल एक आवंटन संभव होता है। आव्यूह को वर्ग आव्यूह होना चाहिए। 

Important Points

• परिवहन समस्या का प्रयोग अधिकांश सर्वोत्कृष्ट तरीके में दी गयी स्थिति के तहत मांग और आपूर्ति आवश्यकताओं को पूरा करने के लिए किया जाता है जिससे कुल परिवहन लागत को कम किया जाता है।