स्नातकोत्तर → अनुकूलन → समाजनीति अनुकूलन ↓
पूर्णांक प्रोग्रामिंग
पूर्णांक प्रोग्रामिंग गणितीय अनुकूलन या गणितीय प्रोग्रामिंग की एक शाखा है। इस संदर्भ में, "अनुकूलन" का अर्थ उपलब्ध विकल्पों के एक दिए गए सेट से किसी मानदंड के संबंध में सबसे अच्छा तत्व चुनना है। पूर्णांक प्रोग्रामिंग विशेष रूप से उन अनुकूलन समस्याओं से संबंधित है जहां कुछ या सभी चर पूर्णांक तक सीमित होते हैं।
पूर्णांक प्रोग्रामिंग के प्रकार
- शुद्ध पूर्णांक प्रोग्रामिंग (पीआईपी): सभी निर्णय चर पूर्णांक मान लेने के लिए आवश्यक हैं।
- मिश्रित पूर्णांक प्रोग्रामिंग (एमआईपी): केवल कुछ चर को पूर्णांक होने की आवश्यकता होती है, जबकि अन्य गैर-पूर्णांक हो सकते हैं।
- बाइनरी पूर्णांक प्रोग्रामिंग: पूर्णांक प्रोग्रामिंग का विशेष मामला जिसमें चर को 0 या 1 तक सीमित किया जाता है। यह अक्सर हां/ना निर्णयों के लिए उपयोग किया जाता है।
सांयोजनात्मक अनुकूलन में महत्व
सांयोजनात्मक अनुकूलन की कई समस्याओं को पूर्णांक प्रोग्रामिंग समस्याओं के रूप में तैयार किया जा सकता है। सांयोजनात्मक अनुकूलन उन वस्तुओं पर ध्यान केंद्रित करता है जो विविक्त हैं या जिन्हें गिना जा सकता है। चूंकि पूर्णांक मान विविक्त हैं, इसलिए इस तरह की समस्याओं को हल करने के लिए पूर्णांक प्रोग्रामिंग सबसे अच्छा तरीका है और इसे हल करने में महत्वपूर्ण हो जाता है।
पूर्णांक प्रोग्रामिंग समस्या का सूत्रीकरण
पूर्णांक प्रोग्रामिंग समस्या आमतौर पर इस प्रकार तैयार की जाती है:
धिकतम (या न्यूनतम) करें: c 1 x 1 + c 2 x 2 + ... + c n x n
इसके अधीन:
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2
...
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m
जहां: x 1 , x 2 , ..., x n पूर्णांक हैं
यहां, c i उद्देश्य फ़ंक्शन के गुणांक को दर्शाता है जिसे आप अधिकतम या न्यूनतम करना चाहते हैं, a ij बाधाओं के गुणांक को दर्शाता है, और b i बाधाओं की सीमाओं को दर्शाता है।
उदाहरण: झोला समस्या
आइए पूर्णांक प्रोग्रामिंग के एक क्लासिक उदाहरण पर विचार करें: झोला समस्या। उद्देश्य झोले में रखी गई वस्तुओं के कुल मूल्य को अधिकतम बनाना है, बिना उसकी ले जाने की क्षमता से अधिक किए।
झोला समस्या का उदाहरण:
- वस्त्र: 4 वस्त्र वजन
w = [2, 3, 4, 5]और मूल्यv = [3, 4, 5, 6]के साथ हैं। - क्षमता: यह बैग अधिकतम 5 लोगों का वजन ले सकता है।
झोला समस्या को पूर्णांक प्रोग्रामिंग का उपयोग करके तैयार करें:
धिकतम करें: 3x 1 + 4x 2 + 5x 3 + 6x 4
इसके अधीन: 2x 1 + 3x 2 + 4x 3 + 5x 4 ≤ 5
जहां: x 1 , x 2 , x 3 , x 4 ∈ {0, 1}
प्रतिबंध x i ∈ {0, 1} सुनिश्चित करता है कि प्रत्येक वस्तु को बैग में या नहीं शामिल किया जा सकता है।
दृश्य प्रतिनिधित्व
यह दृश्य बैग के एक सरलीकृत मॉडल को दर्शाता है जिसमें वजन घटते क्रम में पैक किया गया है।
पूर्णांक प्रोग्रामिंग समस्याओं का समाधान
पूर्णांक प्रोग्रामिंग समस्याएं सामान्यतः एनपी-कठिन होती हैं, जिसका अर्थ है कि सभी ऐसी समस्याओं को कुशलतापूर्वक (बहुपद समय में) हल करने वाले कोई ज्ञात एल्गोरिदम नहीं हैं। हालांकि, विशिष्ट समस्याओं को हल करने के लिए कई दृष्टिकोण अपनाए जा सकते हैं।
1. शाखा और सीमा
यह पूर्णांक प्रोग्रामिंग समस्याओं को हल करने के लिए एक व्यापक रूप से इस्तेमाल की जाने वाली विधि है। मूल विचार समस्या को छोटे उप-समस्याओं (शाखाओं) में विभाजित करना है और उप-समस्याओं की सीमाओं का मूल्यांकन करके इष्टतम समाधान ढूंढना है जबकि उप-समस्याओं को व्यवस्थित रूप से समाप्त किया जाता है यदि उनकी सीमाएं संकेत देती हैं कि वे एक बेहतर समाधान नहीं कर सकती (सीमा)।
2. काटने का प्लेन मैथड
यह विधि समस्या में क्रमशः रैखिक बाधाओं (काटने के प्लेन) को सम्मिलित करके पूर्णांक प्रोग्रामिंग समस्या की रैखिक शिथिलीकरण को बेहतर बनाती है, जिसका उद्देश्य समाधान स्थान के उन क्षेत्रों को छानना होता है जिनके पास पूर्णांक समाधान नहीं होते हैं।
पूर्णांक प्रोग्रामिंग के व्यावहारिक अनुप्रयोग
- संसाधन आवंटन: सीमित संसाधनों का प्रतिस्पर्धात्मक गतिविधियों के बीच आवंटन।
- अनुसूची निर्धारण: कार्यों को समय सीमाओं में आवंटित करना, जैसे कार्य अनुसूचियां, परिवहन अनुसूचियां, आदि।
- नेटवर्क डिज़ाइन: नेटवर्क पथों का डिज़ाइन, बैंडविड्थ निर्दिष्ट करना, आदि।
- उत्पादन योजना: उत्पादन गतिविधियों की योजना बनाना, जैसे उत्पादों की मात्रा का उत्पादन करना।
उदाहरण समस्या: कार्य अनुसूची निर्धारण
कई कार्यों के एक समूह पर विचार करें, जिनमें से प्रत्येक का विशिष्ट प्रसंस्करण समय और समयसीमा होती है। उद्देश्य कार्यों को इस प्रकार से निर्धारित करना है कि कुल विलंबता को न्यूनतम किया जा सके, जो कि कार्यों के विलंबित होने की मात्रा होती है ताकि वे पूरी हो सकें और समय सीमा से अधिक ले सकें।
उदाहरण:
- कार्य: कार्य 1, कार्य 2, कार्य 3, प्रसंस्करण समय 2, 4, 3 और समय सीमाएं 2, 6, 5 क्रमशः।
इस अनुसूची समस्या को पूर्णांक प्रोग्रामिंग का उपयोग करके तैयार करें:
न्यूनतम करें: T 1 + T 2 + T 3
इसके अधीन:
x 1,1 + x 1,2 + x 1,3 = 1
x 2,1 + x 2,2 + x 2,3 = 1
x 3,1 + x 3,2 + x 3,3 = 1
पूर्णता प्रतिबंध:
C 1 = 2x 1,1 + 4x 2,1 + 3x 3,1
C 2 = C 1 + 2x 1,2 + 4x 2,2 + 3x 3,2
C 3 = C 2 + 2x 1,3 + 4x 2,3 + 3x 3,3
जहां:
T i = max(0, C i - समय सीमा i )
x i,j ∈ {0, 1}
पूर्णांक प्रोग्रामिंग के लाभ
पूर्णांक प्रोग्रामिंग कई जटिल निर्णय लेने की समस्याओं को हल करने के लिए एक शक्तिशाली ढांचा प्रदान करता है, क्योंकि इसका उपयोग अनुकूलन समस्याओं के भीतर तार्किक आवश्यकताओं को मॉडल करने की क्षमता है। यह विशेष रूप से तब लाभप्रद होता है जब:
- निर्णय को स्वाभाविक रूप से चालू/बंद शर्तों में दर्शाया जा सकता है (जैसे, निवेश करना है या नहीं)।
- आपका समाधान कड़ाई से तार्किक बाधाओं का पालन करना चाहिए।
- आपको ऐसी समस्याओं को हल करना है जहां कुछ चर को विभिन्न मानों की आवश्यकता होती है।
निष्कर्ष
पूर्णांक प्रोग्रामिंग न केवल अनुकूलन के व्यापक क्षेत्र में बल्कि उद्योगों में कई व्यावहारिक अनुप्रयोगों में भी महत्वपूर्ण भूमिका निभाता है। इसकी जटिलता और कम्प्यूटेशनल तीव्रता के बावजूद, ऐसे प्रभावी रणनीति और ह्यूरिस्टिक्स हैं जिनका उपयोग वास्तविक दुनिया की समस्याओं के लिए व्यावहारिक समाधान प्राप्त करने के लिए किया जा सकता है। जैसे-जैसे कम्प्यूटेशनल शक्ति में वृद्धि होती जा रही है, पूर्णांक प्रोग्रामिंग जटिल निर्णय लेने की चुनौतियों से निपटने में अधिक सहायक और व्यापक हो रही है।
टिप्पणियाँ