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

संकल्पना:

• संभव क्षेत्र के छोर बिंदु ऐसे बिंदु होते हैं जिसके लिए हमें उद्देश्य फलन के मान के जाँच करने की आवश्यकता है। 
• संभव क्षेत्र के इन छोर बिंदुओं के लिए उद्देश्य फलन का अधिकतम मान इष्टतम संभव बिंदु होगा। 
• इस स्थिति में यदि उद्देश्य फलन  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 \leq 40 \)
  2. \( 3x_1 + x_2 \leq 24 \)
  3. \( x_1 + x_2 \leq 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 \not\leq 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 \leq 40 \) → सुसंगत

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

   \( x_1 = 0\) पर

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

   \( x_2 = 0\) पर

   (3) से: \( x_1 = 10 \) → (2) की जाँच करें: \( 30 \not\leq 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 \leq 24 \) → सुसंगत

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

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

1. \( 0 + 30 = 30 \leq 40 \)
2. \( 0 + 10 = 10 \leq 24 \)
3. \( 0 + 10 = 10 \leq 10 \)

उत्तर:

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

व्याख्या:

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

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

निहितार्थ:

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

घटना:

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

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

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

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

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

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

व्याख्या:

वोगेल की सन्निकटन विधि (VAM):

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

वोगेल की सन्निकटन विधि में चरण:

1. जुर्माना लागत की गणना करें: प्रत्येक पंक्ति और स्तंभ के लिए, जुर्माना लागत की गणना करें, जो उस पंक्ति या स्तंभ में सबसे छोटी और दूसरी सबसे छोटी लागत के बीच का अंतर है।
2. सबसे अधिक जुर्माना लागत की पहचान करें: सबसे अधिक जुर्माना लागत वाली पंक्ति या स्तंभ की पहचान करें। इस पंक्ति या स्तंभ को आवंटन के लिए प्राथमिकता दी जाती है क्योंकि यह चयन न करने पर परिवहन लागत में सबसे अधिक वृद्धि की क्षमता का प्रतिनिधित्व करता है।
3. जितना संभव हो आवंटित करें: पहचानी गई पंक्ति या स्तंभ में, सबसे कम लागत वाली सेल को जितना संभव हो आवंटित करें। यह आवंटन आपूर्ति और मांग सीमाओं द्वारा बाधित है।
4. आपूर्ति और मांग को समायोजित करें: आवंटन के बाद, संबंधित पंक्ति और स्तंभ के लिए आपूर्ति और मांग को समायोजित करें। यदि आपूर्ति या मांग पूरी हो जाती है, तो संबंधित पंक्ति या स्तंभ को पार कर दें।
5. दोहराएँ: जब तक सभी आपूर्ति और मांग पूरी नहीं हो जाती, तब तक प्रक्रिया को दोहराएँ, यह सुनिश्चित करते हुए कि परिवहन आव्यूह को तदनुसार अद्यतन किया गया है।

लाभ:

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

हानि:

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

अनुप्रयोग:

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

सही विकल्प विश्लेषण:

सही विकल्प है:

विकल्प 3: प्रत्येक पंक्ति या स्तंभ में दो सबसे छोटी लागतों के बीच का अंतर।

यह विकल्प प्रारंभिक आवंटनों को प्रभावित करने के लिए VAM में उपयोग किए जाने वाले प्राथमिक मानदंड की सही पहचान करता है। विधि जुर्माना लागत पर केंद्रित है, जो प्रत्येक पंक्ति या स्तंभ में दो सबसे छोटी लागतों के बीच का अंतर है। यह दृष्टिकोण सुनिश्चित करता है कि आवंटन इस तरह से किए जाते हैं कि परिवहन लागत में संभावित वृद्धि कम हो।

अवधारणा:

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

अवरोधों की संख्या = 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 ⇒ {5_C}_2\)

∴ \(\frac{5!}{2!\;\times\;(5-2)!}\Rightarrow10\)

वर्णन:

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

निम्न के आधार पर \(Z = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{c_{ij}}} } {x_{ij}}\) को कम करने पर:

\(\begin{array}{l} \sum\limits_{i = 1}^m {{x_{ij}}} \le {b_i}\,\,(demand)\\ \sum\limits_{j = 1}^n {{x_{ij}}} \le {a_i}\,\,(\sup ply) \end{array}\)

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

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

वर्णन:

द्विविधता

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

स्पष्टीकरण:

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

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

X1 + 2X2 ≤ 40

\(\frac{X_1}{40}\;+\;\frac{X_2}{20}\leq1\)

3X1 + 2X2 ≤ 60

\(\frac{X_1}{20}\;+\;\frac{X_2}{40}\leq1\)

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 में अद्वितीय इष्टतम समाधान है।

स्पष्टीकरण

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

स्पष्टीकरण:  

रैखिक प्रोग्रामिंग संसाधनों के इष्टतम आवंटन को ज्ञात करने के लिए एक गणितीय तकनीक है। 

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

रैखिक प्रोग्रामिंग की आवश्यकता

• उद्देश्य फलन: यह मुख्य फलन है; मात्रा में स्पष्ट रूप से पहचाने जाने योग्य और मापने योग्य है।
• प्रतिबंध: ये सीमित संसाधन हैं जिनके भीतर हमें उद्देश्य प्राप्त करना होता है।

व्याख्या:

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

निम्नलिखित सिम्पलेक्स विधि में चरों के समूह हैं। 

• कृत्रिम चर
  • इस चर को गैर-ऋणात्मकता बाधा का उल्लंघन नहीं करने के लिए बाधा के प्रकार से बड़े या बराबर होने की स्थिति में पेश किया जाता है। 
• मूल चर 
  • उन्हें उस चर के रूप में परिभाषित किया जा सकता है जो शून्य के अलावा किसी भी मान को ले सकते हैं। 
• गैर-मूल चर
  • यह चर मूल हल में नहीं है और इसमें शून्य मान है। 
• शिथिल चर 
  • इस चर को, से कम (<) बाधा को हटाने के लिए सिम्पलेक्स विधि में पेश किया जाता है।
• अधिशेष चर
  • इस चर को, से बड़े (>) बाधा को हटाने के लिए सिम्पलेक्स विधि में पेश किया जाता है। 

दिए गए उद्देश्य फलन और बाधाओं के उदाहरण के लिए एक सिंप्लेक्स तालिका नीचे दिखाई गई है

अधिकतम Z = 4 x1 + 6 x2 + x3

2 x1 - x2 + 3 x3 ≤ 5 के अधीन

x2 ≤ 2

x1, x2, x3 ≥ 0

सिंप्लेक्स विधि के विशेष मामले निम्नलिखित हैं:

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

इष्टतम समाधान: यदि (Cj- Zj) में कम से कम एक गैर-मूल चर है) अंतिम सिंप्लेक्स तालिका की पंक्ति का मान शून्य है, यह इंगित करता है कि एक से अधिक इष्टतम समाधान हैं।

असीमित समाधान: यदि सभी प्रतिस्थापन राशन, bi/ai (ai - कुंजी स्तम्भ या पिवट स्तम्भ गुणांक ऋणात्मक हैं) तो यह समाधान असीमित है।

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

पतित समाधान: यदि स्थिर स्तम्भ (bi) में कुछ मान शून्य हैं, तो समाधान पतित हो जाता है।

वर्णन:-

उद्देश्य फलन

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

व्यवरोध:

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

Additional Information

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

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

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

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

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