Which statements are true?

the feasible region of every linear programme is convex

if a linear programme in standard form has an optimal solution, some extreme point of its feasible region is optimal

every basic feasible solution is an extreme point of the feasible region

the feasible region of every linear programme is convex

if a linear programme in standard form has an optimal solution, some extreme point of its feasible region is optimal

the set {(x, y) : x² + y² = 1} is convex

every basic feasible solution is an extreme point of the feasible region

An optimal simplex tableau has a non-basic variable whose reduced cost is zero. This indicates

alternate optimal solutions (if the pivot is non-degenerate)

that the tableau is not optimal

Which statements about the two-phase and Big-M methods are true?

Phase I minimises the sum of the artificial variables

if the optimal value of Phase I is positive, the original problem is infeasible

the Big-M and two-phase methods are two ways of handling artificial variables

Phase I minimises the sum of the artificial variables

if the optimal value of Phase I is positive, the original problem is infeasible

Phase I is needed only when the problem is unbounded

the Big-M and two-phase methods are two ways of handling artificial variables

For a primal max cᵀx, Ax ≤ b, x ≥ 0 and its dual min bᵀy, Aᵀy ≥ c, y ≥ 0, which statements are true?

cᵀx ≤ bᵀy for every primal-feasible x and dual-feasible y

if the primal is unbounded, the dual is infeasible

at optimality, a primal constraint that is not tight has dual value zero

cᵀx ≤ bᵀy for every primal-feasible x and dual-feasible y

if the primal is unbounded, the dual is infeasible

if the primal is infeasible, the dual must be unbounded

at optimality, a primal constraint that is not tight has dual value zero

The dual of min 3x₁ + 2x₂ subject to x₁ + x₂ ≥ 4, x₁ + 3x₂ ≥ 6, x₁, x₂ ≥ 0 is

max 4y₁ + 6y₂ subject to y₁ + y₂ ≤ 3, y₁ + 3y₂ ≤ 2, y₁, y₂ ≥ 0

max 3y₁ + 2y₂ subject to y₁ + y₂ ≤ 4, y₁ + 3y₂ ≤ 6, y₁, y₂ ≥ 0

min 4y₁ + 6y₂ subject to y₁ + y₂ ≥ 3, y₁ + 3y₂ ≥ 2, y₁, y₂ ≥ 0

max 4y₁ + 6y₂ subject to y₁ + 3y₂ ≤ 3, y₁ + y₂ ≤ 2, y₁, y₂ ≥ 0

Which statements about transportation problems are true?

a balanced transportation problem always has a feasible solution

an unbalanced problem is balanced by adding a dummy source or destination with zero unit costs

for minimisation, a BFS is optimal when cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell

a balanced transportation problem always has a feasible solution

an unbalanced problem is balanced by adding a dummy source or destination with zero unit costs

Vogel’s approximation method always gives an optimal solution

for minimisation, a BFS is optimal when cᵢⱼ − uᵢ − vⱼ ≥ 0 for every non-basic cell

रैखिक प्रोग्रामन: सिंप्लेक्स, द्वैतता, परिवहन व नियतन

रैखिक प्रोग्रामन GATE गणित (MA) पेपर का खंड 11 है, अंतिम, और सबसे एल्गोरिथ्मीय। यह ज्यामिति से आरंभ होता है — रैखिक प्रोग्राम का सुसंगत क्षेत्र एक उत्तल बहुफलकीय समुच्चय है, और यदि इष्टतम हो तो वह किसी चरम बिंदु पर प्राप्त होता है, जो ठीक एक आधारी सुसंगत हल है — और सिंप्लेक्स विधि वही तथ्य है जो एक चरम बिंदु से बेहतर पड़ोसी तक चलने वाले एल्गोरिथ्म में बदला गया। अध्याय पाठ्यक्रम का अनुसरण करता है: मॉडल, उत्तल समुच्चय व चरम बिंदु; आधारी सुसंगत हल व आलेखीय विधि; असुसंगत व अपरिबद्ध समस्याओं तथा वैकल्पिक इष्टतम के संकेतों सहित सिंप्लेक्स, द्वि-चरणीय व संशोधित सिंप्लेक्स विधियाँ; दुर्बल व प्रबल द्वैतता प्रमेयों तथा पूरक शिथिलता सहित द्वैतता; उत्तर-पश्चिम कोना, न्यूनतम लागत व वोगेल आरंभिक हलों तथा संशोधित वितरण (MODI) परीक्षण सहित संतुलित व असंतुलित परिवहन समस्याएँ; तथा हंगेरियन विधि सहित नियतन समस्या। यहाँ का प्रत्येक आंकिक उत्तर पूर्ण-खोज से जाँचा गया है।

1. मॉडल, उत्तल समुच्चय व चरम बिंदु

रैखिक प्रोग्राम रैखिक प्रतिबंधों से परिभाषित समुच्चय पर रैखिक उद्देश्य cᵀx का इष्टतमीकरण करता है; प्रत्येक LP को शिथिल (≤) या अधिशेष (≥) चर जोड़कर तथा मुक्त चरों को विभाजित कर मानक रूप max cᵀx, Ax = b, x ≥ 0 में लिखा जा सकता है। समुच्चय S उत्तल है यदि वह अपने बिंदुओं के बीच प्रत्येक खंड को समाविष्ट करे; अर्ध-समष्टियों के प्रतिच्छेद उत्तल हैं, अतः प्रत्येक सुसंगत क्षेत्र उत्तल है (वृत्त x² + y² = 1 नहीं)। S का चरम बिंदु वह है जो S के दो अन्य बिंदुओं का निश्चित उत्तल संयोजन न हो।

मूल प्रमेय। यदि मानक रूप LP का सुसंगत क्षेत्र अरिक्त हो तो उसका एक चरम बिंदु है, और यदि LP का इष्टतम हल हो तो कोई चरम बिंदु इष्टतम है। चरम बिंदु ठीक आधारी सुसंगत हल (BFS) हैं: m × n आव्यूह A के m रैखिकतः स्वतंत्र स्तंभ चुनें (आधार B), शेष n − m चर 0 रखें, Bx_B = b हल करें, और x_B ≥ 0 माँगें। अधिकतम C(n, m) आधारी हल हैं; जिस BFS में कोई आधारी चर 0 हो वह अपभ्रष्ट है।

आलेखीय विधि। x ≤ 4, 2y ≤ 12, 3x + 2y ≤ 18, x, y ≥ 0 के अंतर्गत max z = 3x + 5y: शीर्ष (0, 0), (4, 0), (4, 3), (2, 6), (0, 6) हैं, z = 0, 12, 27, 36, 30 सहित, अतः इष्टतम (2, 6) पर z = 36 है। उद्देश्य रेखा 3x + 5y = k को बाहर खिसकाने पर (2, 6) अंत में पहुँचता है।

2. सिंप्लेक्स, द्वि-चरणीय व संशोधित सिंप्लेक्स विधियाँ

BFS व आधार B सहित max cᵀx, Ax = b, x ≥ 0 हेतु अनाधारी xⱼ की समानीत लागत c̄ⱼ = cⱼ − c_BᵀB⁻¹aⱼ है। यदि प्रत्येक c̄ⱼ ≤ 0 तो BFS इष्टतम है। अन्यथा c̄ⱼ > 0 वाला चर लाएँ और निर्गामी चर चुनने हेतु न्यूनतम अनुपात परीक्षण min{(B⁻¹b)ᵢ/(B⁻¹aⱼ)ᵢ : (B⁻¹aⱼ)ᵢ > 0} लगाएँ; उद्देश्य घटता नहीं, और अपभ्रष्ट चरण के अतिरिक्त निश्चित रूप से बढ़ता है।

अंतिम सारणी पढ़ना
संकेत	निष्कर्ष
बिना धनात्मक प्रविष्टि का प्रवेशी स्तंभ	LP अपरिबद्ध है: चर असीम बढ़ सकता है
इष्टतम पर, समानीत लागत 0 वाला अनाधारी चर	वैकल्पिक इष्टतम: उसे लाने से एक और इष्टतम BFS, और बीच का खंड इष्टतम
चरण I कृत्रिम चरों के धनात्मक योग पर समाप्त	LP असुसंगत है
0 के बराबर आधारी चर	अपभ्रष्टता; चक्रण सैद्धांतिक रूप से संभव, ब्लैंड नियम से रोका जाता है

द्वि-चरणीय विधि। जब कोई स्पष्ट आरंभिक BFS न हो (≥ या = प्रतिबंध), कृत्रिम चर जोड़ें; चरण I उनका योग न्यूनतम करता है। न्यूनतम 0 मूल समस्या का BFS देता है, जिससे चरण II वास्तविक उद्देश्य इष्टतम करता है; धनात्मक न्यूनतम असुसंगतता सिद्ध करता है। बिग-M विधि उद्देश्य में बड़े M से कृत्रिमों को दंडित कर यही एक चरण में करती है।
संशोधित सिंप्लेक्स। केवल B⁻¹ (या B का गुणनखंडन) रखें: सिंप्लेक्स गुणक πᵀ = c_BᵀB⁻¹ निकालें, c̄ⱼ = cⱼ − πᵀaⱼ का मूल्यांकन करें, केवल प्रवेशी स्तंभ B⁻¹aⱼ बनाएँ, और एक प्रारंभिक आव्यूह से B⁻¹ अद्यतन करें। n ≫ m होने पर यह बहुत कम श्रम से वही पिवोट करती है।

3. द्वैतता

प्राथमिक max cᵀx, Ax ≤ b, x ≥ 0 का द्वैत min bᵀy, Aᵀy ≥ c, y ≥ 0 है: प्रत्येक प्राथमिक प्रतिबंध हेतु एक द्वैत चर, दाएँ पक्ष व लागतें भूमिकाएँ बदलते हैं, और द्वैत का द्वैत प्राथमिक है। ≥ प्रतिबंधों वाले min प्राथमिक हेतु द्वैत ≤ प्रतिबंधों वाला max है; समता प्रतिबंध मुक्त द्वैत चर देता है।

दुर्बल द्वैतता: किसी भी प्राथमिक-सुसंगत x व द्वैत-सुसंगत y हेतु cᵀx ≤ bᵀy। अतः अपरिबद्ध प्राथमिक का द्वैत असुसंगत है, और समान उद्देश्य-मान प्रमाणित करते हैं कि दोनों इष्टतम हैं।
प्रबल द्वैतता: यदि किसी एक समस्या का परिमित इष्टतम हो, तो दूसरी का भी है और इष्टतम मान बराबर हैं। दोनों असुसंगत हो सकती हैं (उदा. x₁ − x₂ ≤ −1, −x₁ + x₂ ≤ −1 सहित max x₁)।
पूरक शिथिलता: सुसंगत x, y इष्टतम हैं यदि और केवल यदि प्रत्येक i हेतु yᵢ(b − Ax)ᵢ = 0 तथा प्रत्येक j हेतु xⱼ(Aᵀy − c)ⱼ = 0: शिथिल प्रतिबंध का द्वैत मूल्य शून्य है, और धनात्मक चर का द्वैत प्रतिबंध कसा हुआ।

🧠 इष्टतम शीर्ष से द्वैत मूल्य

x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0 सहित max 2x + 3y, (3, 1) पर z = 9 सहित इष्टतम है। दोनों चर धनात्मक हैं, अतः दोनों द्वैत प्रतिबंध कसे हैं: u + v = 2 तथा u + 3v = 3, जिससे v = 1/2, u = 3/2। प्रबल द्वैतता जाँचें: 4u + 6v = 6 + 3 = 9। द्वैत मान u = 1.5 वह दर है जिससे पहले दाएँ पक्ष की प्रति इकाई वृद्धि पर z बढ़ता है (छाया मूल्य)।

4. परिवहन समस्याएँ

आपूर्ति aᵢ वाले m स्रोतों से माँग bⱼ वाले n गंतव्यों तक इकाई लागत cᵢⱼ पर भेजें, Σcᵢⱼxᵢⱼ न्यूनतम करते हुए। समस्या संतुलित है यदि Σaᵢ = Σbⱼ, और तब वह सदा सुसंगत है; असंतुलित समस्या शून्य लागतों वाले कृत्रिम स्रोत या गंतव्य से संतुलित की जाती है। m + n समता प्रतिबंधों में से एक अतिरेकी है, अतः BFS में m + n − 1 आधारी कोष्ठ हैं; कम धनात्मक आवंटन अपभ्रष्ट BFS दर्शाते हैं, जिसे ε आवंटन रखकर सँभाला जाता है।

हल की गई समस्या: आपूर्ति 30, 40; माँग 20, 30, 20; लागत पंक्ति 1 (2, 3, 1), पंक्ति 2 (5, 4, 8)
विधि	आवंटन	लागत
उत्तर-पश्चिम कोना	x₁₁ = 20, x₁₂ = 10, x₂₂ = 20, x₂₃ = 20	40 + 30 + 80 + 160 = 310
न्यूनतम लागत	x₁₃ = 20, x₁₁ = 10, x₂₂ = 30, x₂₁ = 10	20 + 20 + 120 + 50 = 210
न्यूनतम-लागत BFS की MODI जाँच	u₁ = 0, v₁ = 2, v₃ = 1, u₂ = 3, v₂ = 1; Δ₁₂ = 3 − 0 − 1 = 2, Δ₂₃ = 8 − 3 − 1 = 4	सभी Δ ≥ 0: इष्टतम, 210

वोगेल सन्निकटन विधि प्रत्येक पंक्ति व स्तंभ हेतु उसकी दो सबसे छोटी लागतों का अंतर (सबसे सस्ते कोष्ठ का उपयोग न करने का दंड) निकालती है, सबसे बड़े दंड वाली रेखा के सबसे सस्ते कोष्ठ में यथासंभव अधिक आवंटित करती है, और दोहराती है; यह प्रायः अन्य दो से इष्टतम के अधिक निकट आरंभ करती है परंतु इष्टतम होने की गारंटी नहीं। MODI (u–v) विधि: आधारी कोष्ठों हेतु एक uᵢ = 0 सहित uᵢ + vⱼ = cᵢⱼ हल करें; BFS (न्यूनीकरण हेतु) इष्टतम है यदि और केवल यदि प्रत्येक अनाधारी कोष्ठ हेतु Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ ≥ 0; अन्यथा बंद पाश के परितः सबसे ऋणात्मक Δ लाएँ।

5. नियतन समस्या व हंगेरियन विधि

n कर्मचारियों को n कार्यों पर, एक-एक, कुल लागत न्यूनतम करते हुए नियत करें: सभी आपूर्ति व माँग 1 वाली परिवहन समस्या, अतः अत्यधिक अपभ्रष्ट (2n − 1 आधारी कोष्ठों के विरुद्ध n धनात्मक आवंटन)। n! सुसंगत नियतन हैं। हंगेरियन विधि: प्रत्येक पंक्ति का न्यूनतम घटाएँ, फिर प्रत्येक स्तंभ का; सभी शून्यों को न्यूनतम रेखाओं से ढँकें; यदि n रेखाएँ चाहिए तो शून्यों में इष्टतम नियतन है; अन्यथा सबसे छोटी अनावृत प्रविष्टि सभी अनावृत प्रविष्टियों से घटाएँ, प्रतिच्छेदों पर जोड़ें, और दोहराएँ। किसी पंक्ति या स्तंभ से अचर घटाने पर प्रत्येक नियतन की लागत समान मात्रा से बदलती है, इसीलिए विधि सही है। अधिकतमीकरण समस्या प्रत्येक प्रविष्टि को सबसे बड़ी से घटाकर बदली जाती है।

उदाहरण। लागतें [[10, 3, 8], [7, 5, 4], [6, 9, 2]]। पंक्ति-ह्रास [[7, 0, 5], [3, 1, 0], [4, 7, 0]] देता है; स्तंभ-ह्रास (स्तंभ न्यूनतम 3, 0, 0) [[4, 0, 5], [0, 1, 0], [1, 7, 0]] देता है, जिसके शून्य (1, 2), (2, 1), (3, 3) एक नियतन बनाते हैं। इसकी लागत 3 + 7 + 2 = 12 है, और कुल ह्रास 3 + 4 + 2 + 3 = 12 इष्टतमता पुष्ट करता है।

मुख्य बिंदु

सुसंगत क्षेत्र उत्तल हैं; इष्टतम, यदि हो, चरम बिंदु पर प्राप्त होता है, और चरम बिंदु आधारी सुसंगत हल हैं (अधिकतम C(n, m))।
सिंप्लेक्स: इष्टतम जब कोई समानीत लागत सुधार न कर सके; अपरिबद्ध जब प्रवेशी स्तंभ में धनात्मक प्रविष्टि न हो; वैकल्पिक इष्टतम जब अनाधारी समानीत लागत 0 हो; चरण I > 0 अर्थात् असुसंगत।
दुर्बल द्वैतता cᵀx ≤ bᵀy; प्रबल द्वैतता समान इष्टतम देती है; पूरक शिथिलता शिथिल प्रतिबंधों को शून्य द्वैत मूल्यों से जोड़ती है।
संतुलित परिवहन में m + n − 1 आधारी कोष्ठ; उत्तर-पश्चिम कोना, न्यूनतम लागत व वोगेल आरंभिक हल देते हैं और MODI, Δᵢⱼ = cᵢⱼ − uᵢ − vⱼ ≥ 0 जाँचता है।
नियतन n! सुसंगत हलों वाली अपभ्रष्ट परिवहन समस्या है; हंगेरियन विधि पंक्तियाँ व स्तंभ घटाती है और शून्यों को n रेखाओं से ढँकती है।

अभ्यास प्रश्न (16)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

x ≤ 4, 2y ≤ 12, 3x + 2y ≤ 18, x ≥ 0, y ≥ 0 के अंतर्गत z = 3x + 5y का अधिकतम मान ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 36
शीर्ष (0, 0), (4, 0), (4, 3), (2, 6) व (0, 6) हैं, जहाँ z = 0, 12, 27, 36, 30। इष्टतम 36, (2, 6) पर है, जहाँ y = 6 तथा 3x + 2y = 18 कसे हैं। (4, 3) जाल है: यह तीनों प्रतिबंधों का कोना दिखता है परंतु केवल 27 देता है।
एक निकाय Ax = b में 4 अज्ञातों में 2 समीकरण हैं, A की कोटि 2। आधारी हलों की अधिकतम संभव संख्या ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 6
आधारी हल 4 में से 2 स्तंभों को आधार चुनता है और शेष 2 चर 0 रखता है; C(4, 2) = 6 विकल्प हैं, प्रत्येक अधिकतम एक आधारी हल देता है (दोनों स्तंभ आश्रित हों तो कोई नहीं)। सभी का सुसंगत होना आवश्यक नहीं।
कौन-से कथन सत्य हैं?
1. प्रत्येक रैखिक प्रोग्राम का सुसंगत क्षेत्र उत्तल है
2. यदि मानक रूप रैखिक प्रोग्राम का इष्टतम हल हो, तो उसके सुसंगत क्षेत्र का कोई चरम बिंदु इष्टतम है
3. समुच्चय {(x, y) : x² + y² = 1} उत्तल है
4. प्रत्येक आधारी सुसंगत हल सुसंगत क्षेत्र का चरम बिंदु है
उत्तर देखें
उत्तर: A — प्रत्येक रैखिक प्रोग्राम का सुसंगत क्षेत्र उत्तल है; B — यदि मानक रूप रैखिक प्रोग्राम का इष्टतम हल हो, तो उसके सुसंगत क्षेत्र का कोई चरम बिंदु इष्टतम है; D — प्रत्येक आधारी सुसंगत हल सुसंगत क्षेत्र का चरम बिंदु है
(1) अर्ध-समष्टियों व अतिसमतलों का प्रतिच्छेद उत्तल है। (2) LP का मूल प्रमेय है। (4) मानक रूप में BFS व चरम बिंदु एक ही हैं। (3) असत्य: (1, 0) व (−1, 0) वृत्त पर हैं परंतु उनका मध्यबिंदु (0, 0) नहीं।
अधिकतमीकरण समस्या की सिंप्लेक्स पुनरावृत्ति में प्रवेशी चर के स्तंभ में कोई धनात्मक प्रविष्टि नहीं। तब समस्या
1. अपरिबद्ध है
2. असुसंगत है
3. के वैकल्पिक इष्टतम हैं
4. अपभ्रष्ट है
उत्तर देखें
उत्तर: A — अपरिबद्ध है
धनात्मक प्रविष्टि न होने पर अनुपात परीक्षण का कोई उम्मीदवार नहीं: प्रवेशी चर बढ़ाने से कोई आधारी चर कभी ऋणात्मक नहीं होता, अतः वह असीम बढ़ सकता है और धनात्मक समानीत लागत वाला उद्देश्य भी बढ़ता है। असुसंगतता चरण I संकेतित करता है, वैकल्पिक इष्टतम इष्टतम पर शून्य समानीत लागतें।
एक इष्टतम सिंप्लेक्स सारणी में एक अनाधारी चर की समानीत लागत शून्य है। यह दर्शाता है
1. वैकल्पिक इष्टतम हल (यदि पिवोट अपभ्रष्ट न हो)
2. अपरिबद्ध समस्या
3. असुसंगत समस्या
4. कि सारणी इष्टतम नहीं
उत्तर देखें
उत्तर: A — वैकल्पिक इष्टतम हल (यदि पिवोट अपभ्रष्ट न हो)
उस चर को लाने से उद्देश्य (समानीत लागत) × (चरण) = 0 से बदलता है, अतः वह समान इष्टतम मान वाले भिन्न BFS तक पहुँचता है, और उनके बीच खंड का प्रत्येक बिंदु इष्टतम है। यदि अनुपात-परीक्षण चरण 0 हो तो BFS वही रहता है, जो अपभ्रष्ट अपवाद है।
द्वि-चरणीय व बिग-M विधियों के विषय में कौन-से कथन सत्य हैं?
1. चरण I कृत्रिम चरों का योग न्यूनतम करता है
2. यदि चरण I का इष्टतम मान धनात्मक हो, तो मूल समस्या असुसंगत है
3. चरण I की आवश्यकता केवल अपरिबद्ध समस्या में है
4. बिग-M व द्वि-चरणीय विधियाँ कृत्रिम चरों को सँभालने के दो ढंग हैं
उत्तर देखें
उत्तर: A — चरण I कृत्रिम चरों का योग न्यूनतम करता है; B — यदि चरण I का इष्टतम मान धनात्मक हो, तो मूल समस्या असुसंगत है; D — बिग-M व द्वि-चरणीय विधियाँ कृत्रिम चरों को सँभालने के दो ढंग हैं
(1) चरण I की परिभाषा है। (2) मूल समस्या का सुसंगत x चरण I मान 0 देता, अतः धनात्मक न्यूनतम उसे नकारता है। (4) बिग-M एक उद्देश्य में कृत्रिमों को दंडित करती है; द्वि-चरणीय दंड को अपने चरण में अलग करती है। (3) असत्य: चरण I आरंभिक BFS खोजने हेतु है, जो परिबद्धता से निरपेक्ष ≥ या = प्रतिबंधों हेतु आवश्यक है।
x + y ≤ 4, x + 3y ≤ 6, x ≥ 0, y ≥ 0 के अंतर्गत 2x + 3y का अधिकतम ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 9
शीर्ष: (0, 0) → 0, (4, 0) → 8, (0, 2) → 6, तथा x + y = 4 व x + 3y = 6 का प्रतिच्छेद, अर्थात् y = 1, x = 3 → 9। अधिकतम 9, (3, 1) पर है।
LP max 2x + 3y, x + y ≤ 4, x + 3y ≤ 6, x, y ≥ 0 हेतु प्रतिबंध x + y ≤ 4 से संबद्ध द्वैत चर का इष्टतम मान ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 1.5
प्राथमिक इष्टतम (3, 1) है, x, y > 0 दोनों, अतः पूरक शिथिलता से दोनों द्वैत प्रतिबंध कसे हैं: u + v = 2 तथा u + 3v = 3। अतः v = 1/2 तथा u = 3/2। जाँच: द्वैत उद्देश्य 4u + 6v = 6 + 3 = 9, प्राथमिक इष्टतम के बराबर।
प्राथमिक max cᵀx, Ax ≤ b, x ≥ 0 तथा उसके द्वैत min bᵀy, Aᵀy ≥ c, y ≥ 0 हेतु कौन-से कथन सत्य हैं?
1. प्रत्येक प्राथमिक-सुसंगत x व द्वैत-सुसंगत y हेतु cᵀx ≤ bᵀy
2. यदि प्राथमिक अपरिबद्ध हो, तो द्वैत असुसंगत है
3. यदि प्राथमिक असुसंगत हो, तो द्वैत अवश्य अपरिबद्ध है
4. इष्टतम पर, जो प्राथमिक प्रतिबंध कसा न हो उसका द्वैत मान शून्य है
उत्तर देखें
उत्तर: A — प्रत्येक प्राथमिक-सुसंगत x व द्वैत-सुसंगत y हेतु cᵀx ≤ bᵀy; B — यदि प्राथमिक अपरिबद्ध हो, तो द्वैत असुसंगत है; D — इष्टतम पर, जो प्राथमिक प्रतिबंध कसा न हो उसका द्वैत मान शून्य है
(1) x, y ≥ 0 का उपयोग कर cᵀx ≤ (Aᵀy)ᵀx = yᵀAx ≤ yᵀb। (2) कोई भी द्वैत-सुसंगत y प्राथमिक को परिबद्ध करता। (4) पूरक शिथिलता है। (3) असत्य: दोनों समस्याएँ असुसंगत हो सकती हैं, उदा. x₁ − x₂ ≤ −1 तथा −x₁ + x₂ ≤ −1 सहित max x₁।
x₁ + x₂ ≥ 4, x₁ + 3x₂ ≥ 6, x₁, x₂ ≥ 0 के अंतर्गत min 3x₁ + 2x₂ का द्वैत है
1. y₁ + y₂ ≤ 3, y₁ + 3y₂ ≤ 2, y₁, y₂ ≥ 0 के अंतर्गत max 4y₁ + 6y₂
2. y₁ + y₂ ≤ 4, y₁ + 3y₂ ≤ 6, y₁, y₂ ≥ 0 के अंतर्गत max 3y₁ + 2y₂
3. y₁ + y₂ ≥ 3, y₁ + 3y₂ ≥ 2, y₁, y₂ ≥ 0 के अंतर्गत min 4y₁ + 6y₂
4. y₁ + 3y₂ ≤ 3, y₁ + y₂ ≤ 2, y₁, y₂ ≥ 0 के अंतर्गत max 4y₁ + 6y₂
उत्तर देखें
उत्तर: A — y₁ + y₂ ≤ 3, y₁ + 3y₂ ≤ 2, y₁, y₂ ≥ 0 के अंतर्गत max 4y₁ + 6y₂
≥ प्रतिबंधों व x ≥ 0 सहित min का द्वैत max bᵀy, Aᵀy ≤ c, y ≥ 0 है। यहाँ b = (4, 6), c = (3, 2) तथा A = [[1, 1], [1, 3]], अतः Aᵀ = [[1, 1], [1, 3]] भी, जिससे y₁ + y₂ ≤ 3 (x₁ का स्तंभ) तथा y₁ + 3y₂ ≤ 2 (x₂ का स्तंभ)। अंतिम विकल्प गलत ढंग से पक्षांतरित करता है।
3 स्रोतों व 4 गंतव्यों वाली संतुलित परिवहन समस्या के आधारी सुसंगत हल में आधारी चरों की संख्या ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 6
3 + 4 = 7 समता प्रतिबंध हैं, परंतु स्रोतों पर उनका योग गंतव्यों पर योग के बराबर है, अतः एक अतिरेकी है और कोटि m + n − 1 = 6 है। 6 से कम धनात्मक आवंटनों वाला BFS अपभ्रष्ट है।
आपूर्ति 30 व 40, माँग 20, 30 व 20 हैं, तथा इकाई लागतें स्रोत 1 से (2, 3, 1) व स्रोत 2 से (5, 4, 8) हैं। उत्तर-पश्चिम कोना आरंभिक हल की कुल लागत ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 310
कोष्ठ (1, 1) से आरंभ: x₁₁ = min(30, 20) = 20; स्तंभ 1 पूर्ण, दाएँ जाएँ: x₁₂ = 10 स्रोत 1 समाप्त करता है; नीचे जाएँ: x₂₂ = 20 स्तंभ 2 पूर्ण करता है; x₂₃ = 20। लागत 20·2 + 10·3 + 20·4 + 20·8 = 40 + 30 + 80 + 160 = 310। विधि लागतों की उपेक्षा करती है, इसीलिए प्रायः दुर्बल है।
उन्हीं आँकड़ों हेतु (आपूर्ति 30, 40; माँग 20, 30, 20; लागतें (2, 3, 1) व (5, 4, 8)) न्यूनतम कुल परिवहन लागत ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 210
न्यूनतम लागत x₁₃ = 20, x₁₁ = 10, x₂₂ = 30, x₂₁ = 10 देती है, लागत 20 + 20 + 120 + 50 = 210। MODI: u₁ = 0 से v₁ = 2, v₃ = 1; फिर u₂ = 3 तथा v₂ = 1। अनाधारी Δ₁₂ = 3 − 0 − 1 = 2 तथा Δ₂₃ = 8 − 3 − 1 = 4 अऋणात्मक हैं, अतः 210 इष्टतम है (पूर्ण खोज सहमत है)।
परिवहन समस्याओं के विषय में कौन-से कथन सत्य हैं?
1. संतुलित परिवहन समस्या का सदा सुसंगत हल होता है
2. असंतुलित समस्या शून्य इकाई लागतों वाले कृत्रिम स्रोत या गंतव्य को जोड़कर संतुलित की जाती है
3. वोगेल सन्निकटन विधि सदा इष्टतम हल देती है
4. न्यूनीकरण हेतु, BFS इष्टतम है जब प्रत्येक अनाधारी कोष्ठ हेतु cᵢⱼ − uᵢ − vⱼ ≥ 0
उत्तर देखें
उत्तर: A — संतुलित परिवहन समस्या का सदा सुसंगत हल होता है; B — असंतुलित समस्या शून्य इकाई लागतों वाले कृत्रिम स्रोत या गंतव्य को जोड़कर संतुलित की जाती है; D — न्यूनीकरण हेतु, BFS इष्टतम है जब प्रत्येक अनाधारी कोष्ठ हेतु cᵢⱼ − uᵢ − vⱼ ≥ 0
(1) xᵢⱼ = aᵢbⱼ/Σa सुसंगत है। (2) कृत्रिम इकाई अधिशेष को बिना लागत सोख लेती है। (4) cᵢⱼ − uᵢ − vⱼ समानीत लागतें हैं, (uᵢ, vⱼ) द्वैत चर। (3) असत्य: वोगेल अच्छे आरंभिक BFS हेतु अनुमानी विधि है, और इष्टतम चूक सकती है।
तीन कार्य तीन कर्मचारियों को, एक-एक, नियत किए जाते हैं, लागत आव्यूह की पंक्तियाँ (10, 3, 8), (7, 5, 4), (6, 9, 2)। न्यूनतम कुल लागत ____ है।
संख्यात्मक उत्तर — मान टाइप करें।
उत्तर देखें
उत्तर: 12
पंक्ति न्यूनतम 3, 4, 2 से [[7, 0, 5], [3, 1, 0], [4, 7, 0]]; स्तंभ न्यूनतम 3, 0, 0 से [[4, 0, 5], [0, 1, 0], [1, 7, 0]]। (1, 2), (2, 1), (3, 3) पर शून्य एक नियतन बनाते हैं: 3 + 7 + 2 = 12, कुल घटाए के बराबर, अतः इष्टतम। शेष पाँच क्रमचयों की लागत 13, 17, 19, 23, 24 है।
n × n नियतन समस्या के सुसंगत हलों की संख्या है
1. n!
2. n²
3. 2ⁿ
4. 2n − 1
उत्तर देखें
उत्तर: A — n!
सुसंगत नियतन प्रत्येक कर्मचारी को भिन्न कार्य देता है, अर्थात् n कार्यों का क्रमचय, और n! क्रमचय हैं। 2n − 1, समस्या को परिवहन समस्या मानने पर आधारी कोष्ठों की संख्या है, जिनमें केवल n धनात्मक हैं, अतः प्रत्येक BFS अपभ्रष्ट है।

यह अध्याय निःशुल्क है। परीक्षा का अभ्यास ₹1 प्रतिदिन से भी कम में।

निःशुल्क खाता इन 16 प्रश्नों को उत्तर देते ही अंकित करता है, प्रगति हर डिवाइस पर सहेजता है, और आज़माने हेतु 1 पूर्ण मॉक टेस्ट व 20 विगत वर्ष प्रश्न देता है। GATE Basic ₹29 प्रति माह — हर माह 4 मॉक टेस्ट व 150 विगत वर्ष प्रश्न, कभी भी रद्द करें। Premium में AI मेंटर व असीमित अभ्यास।