अनुकूलन — रैखिक प्रोग्रामन, पूर्णांक प्रोग्रामन, परिवहन, नियतन व PERT-CPM

संक्रिया अनुसंधान इकाई 1 का वह एकमात्र बड़ा उप-प्रकरण है जिसका GATE CS में कोई समतुल्य नहीं — GATE के अभियांत्रिकी-गणित व विविक्त-गणित अध्याय इससे बहुत पहले रुक जाते हैं। यह अध्याय इसका सम्पूर्ण भाग ढकता है: दो चरों हेतु रैखिक-प्रोग्रामन प्रतिरूप व उसका आलेखीय हल, सिम्प्लेक्स विधि व द्वैतता सहित द्वि-सिम्प्लेक्स विधि, संवेदनशीलता विश्लेषण, पूर्णांक प्रोग्रामन, विशेष-संरचना वाले LP के रूप में परिवहन व नियतन प्रतिरूप जो अपनी समर्पित विधियों से हल होते हैं, तथा क्रांतिक-पथ गणना, संसाधन समतलन व लागत व्यापार सहित परियोजना अनुसूचन हेतु PERT-CPM।

LP प्रतिरूप व आलेखीय विधि

रैखिक प्रोग्रामन समस्या रैखिक उद्देश्य फलन c₁x₁ + c₂x₂ + ... को रैखिक प्रतिबंधों (समताएँ या असमिकाएँ) व अऋणात्मकता xᵢ ≥ 0 के अधीन अधिकतम या न्यूनतम करती है। दो चरों हेतु यह आलेखीय रूप से हल होती है: प्रत्येक प्रतिबंध को अर्ध-तल के रूप में आलेखित करें, उन्हें प्रतिच्छेदित कर सुसंगत क्षेत्र पाएँ (एक उन्नतोदर बहुभुज, संभवतः असीमित), और ध्यान दें कि इष्टतम हल सदा इस क्षेत्र के किसी कोने (चरम) बिंदु पर होता है — कभी कड़ाई से भीतर नहीं, क्योंकि किसी रेखीय फलन का मान किसी भी सीधी रेखा के अनुदिश एकदिष्ट रूप से बदलता है, अतः किसी आंतरिक बिंदु से उद्देश्य को सुधारने वाली दिशा में सीमा की ओर बढ़ना उसे तब तक कभी बुरा नहीं बनाता जब तक कोई कोना न पहुँच जाए। उद्देश्य का मूल्यांकन प्रत्येक कोने पर करें और सर्वश्रेष्ठ चुनें।

⚠️ असीमित सुसंगत क्षेत्र का अर्थ असीमित इष्टतम नहीं
न्यूनीकरण समस्या का सान्त इष्टतम तब भी हो सकता है जब सुसंगत क्षेत्र अनंत तक फैला हो, क्योंकि उद्देश्य उस क्षेत्र पर नीचे से परिबद्ध रह सकता है (उदा० दूर जाने पर वह बढ़ता ही जाए)। इष्टतम केवल तब असीमित है जब सुसंगत रहते हुए उद्देश्य को बिना सीमा सुधारा जा सके — इसे क्षेत्र के आकार से अनुमान लगाने के बजाय स्पष्ट रूप से जाँचें।

सिम्प्लेक्स विधि, द्वैतता व संवेदनशीलता विश्लेषण

  • सिम्प्लेक्स विधि: असमिकाओं को शिथिल/अतिरिक्त चरों से समताओं में बदलती है, किसी आधारभूत सुसंगत हल (प्रायः मूल बिंदु) से आरंभ होती है, और सुसंगत क्षेत्र के कोरों के अनुदिश कोने-दर-कोने चलती है, प्रत्येक चाल उद्देश्य सुधारती है, जब तक कोई सन्निहित कोना उसे और न सुधारे — वही इष्टतम है। कलनविधि ठीक वही कोना-जाँच व्यवस्थित रूप से करती है जो आलेखीय विधि करती है, पर किसी भी संख्या के आयामों में।
  • द्वैतता: प्रत्येक LP (आद्य) का एक संबद्ध द्वैत LP होता है — अधिकतमीकरण आद्य न्यूनतमीकरण द्वैत से युग्मित होता है, आद्य के प्रतिबंध-गुणांक द्वैत के बनते हैं, और आद्य के उद्देश्य-गुणांक द्वैत की प्रतिबंध दायीं-भुजाएँ बनते हैं तथा उल्टा भी। दुर्बल द्वैतता प्रमेय कहता है कि द्वैत का उद्देश्य-मान सदा आद्य का परिबद्ध करता है (किसी भी सुसंगत युग्म पर द्वैत न्यूनतम ≥ आद्य अधिकतम), और सबल द्वैतता कहता है कि जब दोनों समस्याओं का सुसंगत इष्टतम हल हो तो उनके इष्टतम मान बराबर होते हैं।
  • द्वि-सिम्प्लेक्स विधि: तब प्रयुक्त जब कोई हल द्वैत-सुसंगत हो (इष्टतम-सी दिखती गुणांक) पर आद्य-असंगत (ऋणात्मक दायीं-भुजा) — नए सिरे से आरंभ करने के बजाय, यह द्वैत-सुसंगति बनाए रखते हुए आद्य-सुसंगति पुनर्स्थापित करती है, जो प्रतिबंध बदलने के बाद (उदा० संवेदनशीलता विश्लेषण या प्रतिबंध जोड़ने के बाद पुनः-अनुकूलन में) शून्य से पुनः हल करने से तेज़ है।
  • संवेदनशीलता विश्लेषण पूछता है कि इष्टतम आधार (कौन चर आधारभूत हैं) बदलने से पहले उद्देश्य-गुणांक या प्रतिबंध की दायीं-भुजा कितनी बदल सकती है — गुणांक की परास, तथा प्रतिबंध की छाया-कीमत (उस प्रतिबंध में प्रति इकाई शिथिलन पर इष्टतम कितना सुधरता है, जो संगत द्वैत-चर के मान के बराबर होती है)।

पूर्णांक प्रोग्रामन, परिवहन व नियतन

LP-कुल की तीन विशेष समस्याएँ
समस्याक्या भिन्न हैमानक विधि
पूर्णांक प्रोग्रामनकुछ या सभी चर पूर्णांक होने चाहिए; LP-शिथिलन के हल को पूर्णांकित करना सुसंगत या इष्टतम होने की गारंटी नहीं देता।शाखा व परिबंध (LP-शिथिलन हल करें, भिन्नात्मक चर पर शाखा करें) या काट-तल।
परिवहन समस्याm आपूर्ति स्रोतों से n माँग गंतव्यों तक भेजन-लागत न्यूनतम करें; संतुलित समस्या में कुल आपूर्ति = कुल माँग।आरंभिक सुसंगत हल हेतु उत्तर-पश्चिम कोना या वोगेल सन्निकटन विधि, फिर इष्टतमता जाँचने व सुधारने हेतु MODI (या स्टेपिंग-स्टोन)।
नियतन समस्याएक विशेष (अपकर्षित) परिवहन समस्या: n श्रमिकों से n कार्य, एक-एक करके, कुल लागत न्यूनतम करते हुए।हंगेरियन विधि — पंक्ति व स्तंभ न्यूनीकरण, फिर सभी शून्यों को न्यूनतम रेखाओं से ढकना व समायोजन।
🎯 पूर्णांक प्रोग्राम के LP-शिथिलन को पूर्णांकित करना बुरी तरह क्यों विफल हो सकता है
LP-शिथिलन (पूर्णांकता-प्रतिबंध हटाना) अधिकतमीकरण पूर्णांक प्रोग्राम के वास्तविक इष्टतम की ऊर्ध्व सीमा देता है, पर शिथिल इष्टतम के भिन्नात्मक मान, निकटतम पूर्णांक तक पूर्णांकित होने पर, सुसंगत भी न हों (पूर्णांकित हल किसी ऐसे प्रतिबंध का उल्लंघन कर सकता है जिसे भिन्नात्मक हल ठीक-ठीक संतुष्ट करता था), और सुसंगत होने पर भी इष्टतम से दूर हो सकता है। शाखा व परिबंध इसके बजाय व्यवस्थित रूप से पूर्णांक-बाध्य शाखाएँ खोजता है, अब तक मिले सर्वश्रेष्ठ पूर्णांक हल को न हरा सकने वाली शाखाओं को छाँटने हेतु LP-सीमा का प्रयोग करते हुए।

PERT-CPM: क्रांतिक पथ, संसाधन समतलन व लागत

परियोजना को एक गतिविधि-नेटवर्क (दिष्ट अचक्रीय ग्राफ) के रूप में प्रतिरूपित किया जाता है: शीर्ष घटना/पड़ाव हैं और कोर अवधि वाली गतिविधियाँ (CPM, निश्चयात्मक) या तीन समय आकलन — आशावादी, सर्वाधिक संभाव्य, निराशावादी — जो PERT के सूत्र (o + 4m + p)/6 से प्रत्याशित समय में संयोजित होते हैं। क्रांतिक पथ आरंभ से अंत तक का सबसे लंबा पथ है; उसकी कुल लंबाई न्यूनतम संभव परियोजना-अवधि है, और किसी क्रांतिक गतिविधि में कोई विलंब पूरी परियोजना को विलंबित करता है। प्रत्येक गतिविधि का एक सबसे शीघ्र आरंभ/समापन (अग्र-यात्रा) व सबसे विलंबित आरंभ/समापन (पश्च-यात्रा) होता है; उसका कुल फ्लोट = विलंबित आरंभ − शीघ्र आरंभ (समतुल्यतः, विलंबित समापन − शीघ्र समापन) मापता है कि वह परियोजना विलंबित किए बिना कितना खिसक सकती है। क्रांतिक गतिविधि की परिभाषा से शून्य कुल फ्लोट होता है — फ्लोट व क्रांतिकता एक ही गणना के दो दृष्टिकोण हैं।

  • संसाधन समतलन समय के साथ संसाधन-माँग को सहज करने (उदा० कार्यबल-शिखर से बचने) हेतु अक्रांतिक गतिविधियों को उनके फ्लोट के भीतर खिसकाता है, परियोजना बढ़ाए बिना — यह उस अवशिष्टता का उपयोग करता है जिसे संसाधन-अंध अनुसूचन नज़रअंदाज़ करता है।
  • लागत-विचार (क्रैशिंग): गतिविधि की एक सामान्य अवधि/लागत व एक क्रैश (न्यूनतम) अवधि/लागत होती है; क्रैशिंग प्रति इकाई बचाए समय की अतिरिक्त लागत पर अवधि छोटी करती है, और परियोजना सबसे सस्ते ढंग से क्रांतिक-पथ गतिविधियों को उनकी प्रति-दिन-बचत-लागत के बढ़ते क्रम में क्रैश करके छोटी की जाती है, प्रत्येक क्रैश के बाद क्रांतिक पथ पुनः जाँचते हुए क्योंकि वह गतिविधियों की भिन्न शृंखला पर खिसक सकता है।

मुख्य बिंदु

  • LP का इष्टतम सदा सुसंगत क्षेत्र के किसी कोने (चरम बिंदु) पर होता है — उद्देश्य का मूल्यांकन वहीं करें, कभी भीतर नहीं।
  • सिम्प्लेक्स उद्देश्य सुधारते हुए कोना-दर-कोना चलता है; सबल द्वैतता आद्य व द्वैत के इष्टतम मान बराबर कर देती है जब दोनों सुसंगत हों; द्वि-सिम्प्लेक्स प्रतिबंध-परिवर्तन के बाद बिना पुनः-आरंभ आद्य-सुसंगति पुनर्स्थापित करती है।
  • पूर्णांक प्रोग्राम के LP-शिथिलन को पूर्णांकित करना सुसंगत या इष्टतम होने की गारंटी नहीं — शाखा व परिबंध ही सुदृढ़ विधि है।
  • परिवहन समस्या आरंभिक-हल विधि (उत्तर-पश्चिम कोना या वोगेल) व इष्टतमता हेतु MODI से हल होती है; नियतन समस्या इसकी एक-एक विशेष स्थिति है, जो हंगेरियन विधि से हल होती है।
  • क्रांतिक पथ आरंभ-से-अंत तक का सबसे लंबा पथ है और उसके अनुदिश हर गतिविधि का कुल फ्लोट शून्य होता है; संसाधन समतलन व क्रैशिंग दोनों फ्लोट/लागत व्यापार का उपयोग करते हैं, परियोजना बढ़ाए बिना (समतलन) या बढ़ाकर (क्रैशिंग)।

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

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

  1. सीमित सुसंगत क्षेत्र वाली रैखिक प्रोग्रामन समस्या में, इष्टतम हल:

    1. सदा सुसंगत क्षेत्र के किसी कोने (चरम) बिंदु पर होता है
    2. सदा सुसंगत क्षेत्र के कड़ाई से भीतर होता है
    3. सुसंगत क्षेत्र के केंद्रक पर होता है
    4. कलन के बिना निर्धारित नहीं किया जा सकता
    उत्तर देखें

    उत्तर: A — सदा सुसंगत क्षेत्र के किसी कोने (चरम) बिंदु पर होता है

    रैखिक उद्देश्य किसी भी दिशा में एकदिष्ट रूप से बदलता है, अतः किसी आंतरिक बिंदु से उसे सुधारना तब तक नहीं रुकता जब तक सीमा का कोई कोना न आ जाए — इसी कारण सिम्प्लेक्स को केवल कोनों की जाँच करनी होती है।

  2. रैखिक प्रोग्रामन में सबल द्वैतता कहती है कि:

    1. जब दोनों का सुसंगत इष्टतम हल हो, तो आद्य व द्वैत के इष्टतम उद्देश्य-मान बराबर होते हैं
    2. द्वैत समस्या के सदा आद्य से अधिक चर होते हैं
    3. केवल आद्य समस्या को हल करने की आवश्यकता है
    4. द्वैत केवल तभी सुसंगत है जब आद्य असुसंगत हो
    उत्तर देखें

    उत्तर: A — जब दोनों का सुसंगत इष्टतम हल हो, तो आद्य व द्वैत के इष्टतम उद्देश्य-मान बराबर होते हैं

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

  3. द्वि-सिम्प्लेक्स विधि सामान्यतः तब लागू होती है जब सारणी हो:

    1. द्वैत-सुसंगत पर आद्य-असंगत
    2. आद्य-सुसंगत पर द्वैत-असंगत
    3. आद्य व द्वैत दोनों असंगत
    4. पहले से ही इष्टतम हल पर
    उत्तर देखें

    उत्तर: A — द्वैत-सुसंगत पर आद्य-असंगत

    द्वि-सिम्प्लेक्स इष्टतम-सी दिखती (द्वैत-सुसंगत) गुणांकों से असुसंगत (ऋणात्मक) दायीं-भुजा सहित आरंभ होती है और आद्य-सुसंगति पुनर्स्थापित करती है, जो ठीक वही स्थिति है जो इष्टतमता के पश्चात् किसी प्रतिबंध की दायीं-भुजा कसने पर बनती है।

  4. पूर्णांक प्रोग्राम के LP-शिथिलन के इष्टतम हल को निकटतम पूर्णांकों तक पूर्णांकित करना:

    1. ऐसा हल दे सकता है जो असुसंगत हो या इष्टतम से दूर हो
    2. सदा वास्तविक पूर्णांक इष्टतम देता है
    3. शाखा व परिबंध विधि की परिभाषा है
    4. केवल नियतन समस्याओं हेतु वैध है
    उत्तर देखें

    उत्तर: A — ऐसा हल दे सकता है जो असुसंगत हो या इष्टतम से दूर हो

    पूर्णांकित भिन्नात्मक हल किसी ऐसे प्रतिबंध का उल्लंघन कर सकता है जो भिन्नात्मक बिंदु पर ठीक-ठीक संतुष्ट था, और सुसंगत रह जाने पर भी वह सर्वश्रेष्ठ पूर्णांक हल न हो — शाखा व परिबंध ही वह विधि है जो इष्टतमता की गारंटी देती है।

  5. नियतन समस्या का सर्वोत्तम वर्णन है:

    1. परिवहन समस्या की एक विशेष (अपकर्षित) स्थिति जिसमें सभी आपूर्ति व माँग 1 के बराबर हों
    2. एक अरैखिक अनुकूलन समस्या
    3. परिवहन समस्या से असंबद्ध
    4. केवल सिम्प्लेक्स से हल करने योग्य, किसी समर्पित विधि से कभी नहीं
    उत्तर देखें

    उत्तर: A — परिवहन समस्या की एक विशेष (अपकर्षित) स्थिति जिसमें सभी आपूर्ति व माँग 1 के बराबर हों

    n श्रमिकों से n कार्य, एक-एक करके, वह परिवहन समस्या है जहाँ प्रत्येक स्रोत ठीक 1 आपूर्ति करता है और प्रत्येक गंतव्य ठीक 1 माँगता है — इसकी उच्च अपकर्षिता ही वह कारण है कि सामान्य परिवहन विधियों के बजाय समर्पित हंगेरियन विधि प्रयुक्त होती है।

  6. परियोजना नेटवर्क में, किसी गतिविधि का कुल फ्लोट है:

    1. विलंबित आरंभ शून्य शीघ्र आरंभ (समतुल्यतः विलंबित समापन शून्य शीघ्र समापन)
    2. शीघ्र आरंभ शून्य विलंबित आरंभ
    3. नेटवर्क की हर गतिविधि हेतु सदा शून्य
    4. गतिविधि की अपनी अवधि
    उत्तर देखें

    उत्तर: A — विलंबित आरंभ शून्य शीघ्र आरंभ (समतुल्यतः विलंबित समापन शून्य शीघ्र समापन)

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

  7. PERT में, आशावादी समय o, सर्वाधिक संभाव्य समय m व निराशावादी समय p वाली गतिविधि की प्रत्याशित अवधि की गणना इस प्रकार होती है:

    1. (o + 4m + p) / 6
    2. (o + m + p) / 3
    3. (o + p) / 2
    4. केवल m, o व p को नज़रअंदाज़ करते हुए
    उत्तर देखें

    उत्तर: A — (o + 4m + p) / 6

    PERT का भारित औसत गतिविधि-अवधि को सन्निकटतः बीटा-बंटित मानते हुए सर्वाधिक-संभाव्य आकलन को किसी भी चरम की तुलना में चार गुना भार देता है।

  8. परियोजना की अवधि घटाने हेतु उसे क्रैश करने के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. परियोजना छोटी करने हेतु केवल क्रांतिक-पथ गतिविधियों को क्रैश करने की आवश्यकता है
    2. क्रैश के बाद क्रांतिक पथ गतिविधियों की भिन्न शृंखला पर खिसक सकता है
    3. क्रैशिंग सदा बिना अतिरिक्त लागत के होती है
    4. गतिविधियों को प्रति इकाई बचाए समय की लागत के बढ़ते क्रम में क्रैश करना चाहिए
    उत्तर देखें

    उत्तर: A — परियोजना छोटी करने हेतु केवल क्रांतिक-पथ गतिविधियों को क्रैश करने की आवश्यकता है; B — क्रैश के बाद क्रांतिक पथ गतिविधियों की भिन्न शृंखला पर खिसक सकता है; D — गतिविधियों को प्रति इकाई बचाए समय की लागत के बढ़ते क्रम में क्रैश करना चाहिए

    अक्रांतिक गतिविधि को क्रैश करना परियोजना को तनिक भी छोटा नहीं करता, क्योंकि क्रांतिक पथ की लंबाई अप्रभावित रहती है; क्रांतिक पथ स्वयं खिसक सकता है एक बार क्रैश पूर्व अवरोध हटा दे; और क्रैशिंग सदा प्रति इकाई बचाए समय अतिरिक्त लागत लेती है, इसीलिए सबसे सस्ती क्रांतिक गतिविधियाँ पहले क्रैश की जाती हैं।

  9. संतुलित परिवहन समस्या में, यदि स्रोतों में फैली कुल आपूर्ति 100 इकाई है और गंतव्यों में फैली कुल माँग D इकाई है, तो D बराबर होना ही चाहिए _____।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: 100

    परिवहन समस्या ठीक तब 'संतुलित' है जब कुल आपूर्ति कुल माँग के बराबर हो; असंतुलित समस्या को मानक विधियाँ लागू करने से पहले शून्य-लागत वाला डमी स्रोत या गंतव्य जोड़कर पहले संतुलित बनाया जाता है।