रैखिक-आंशिक प्रोग्रामिंग

गणितीय अनुकूलन में रैखिक-आंशिक प्रोग्रामिंग (LFP) रैखिक प्रोग्रामिंग (LP) का एक सामान्यीकरण है, जबकि रैखिक प्रोग्राम में वस्तुनिष्ठ फलन एक रैखिक फंक्शन है, एक रैखिक-आंशिक प्रोग्राम में वस्तुनिष्ठ फलन दो रैखिक कार्यों का अनुपात है। रेखीय प्रोग्राम को रेखीय-आंशिक प्रोग्राम के एक विशेष स्थिति के रूप में माना जा सकता है जिसमें भाजक स्थिर फंक्शन 1 है।

औपचारिक रूप से रेखीय-आंशिक प्रोग्रामिंग को बहुफलक पर एफिन फंक्शन के अनुपात को अधिकतम करने (या कम करने) की समस्या के रूप में परिभाषित किया गया है,

${\begin{aligned}{\text{maximize}}\quad &{\frac {\mathbf {c} ^{T}\mathbf {x} +\alpha }{\mathbf {d} ^{T}\mathbf {x} +\beta }}\\{\text{subject to}}\quad &A\mathbf {x} \leq \mathbf {b} ,\end{aligned}}$

जहाँ $\mathbf {x} \in \mathbb {R} ^{n}$ निर्धारित किए जाने वाले चर के सदिश का प्रतिनिधित्व करता है $\mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}$ और $\mathbf {b} \in \mathbb {R} ^{m}$ (ज्ञात) गुणांक के सदिश हैं $A\in \mathbb {R} ^{m\times n}$ गुणांक का (ज्ञात) आव्यूह है और $\alpha ,\beta \in \mathbb {R}$ स्थिरांक हैं। बाधाओं के संभव क्षेत्र $\{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\beta >0\}$ यानी वह क्षेत्र जिस पर भाजक धनात्मक है। वैकल्पिक रूप से वस्तुनिष्ठ फलन के भाजक को पूर्ण संभव क्षेत्र में सख्ती से नकारात्मक होना चाहिए।

रैखिक प्रोग्रामिंग की तुलना में प्रेरणा

रैखिक प्रोग्रामिंग और रैखिक-आंशिक प्रोग्रामिंग दोनों रैखिक समीकरणों और रैखिक असमानताओं का उपयोग करके अनुकूलन समस्याओं का प्रतिनिधित्व करते हैं, जो प्रत्येक समस्या-उदाहरण के लिए एक संभव सेट को परिभाषित करते हैं, आंशिक रैखिक प्रोग्राम में वस्तुनिष्ठ फलन का एक समृद्ध सेट होता है। अनौपचारिक रूप से रैखिक प्रोग्रामिंग सर्वोत्तम परिणाम देने वाली नीति की गणना करती है, जैसे अधिकतम लाभ या न्यूनतम लागत। इसके विपरीत, लागत के परिणाम के उच्चतम अनुपात को प्राप्त करने के लिए एक रैखिक- आंशिक प्रोग्रामिंग का उपयोग किया जाता है, उच्चतम दक्षता का प्रतिनिधित्व करने वाला अनुपात। उदाहरण के लिए, LP के संदर्भ में वस्तुनिष्ठ फलन 'लाभ = आय - लागत' को अधिकतम करते हैं और $100 का अधिकतम लाभ प्राप्त कर सकते हैं (= आय का $1100 - लागत का $1000) इस प्रकार LP में हमारे पास $100/$1000 = 0.1 की दक्षता है, LFP का उपयोग करके हम केवल $10 के लाभ के साथ $10/$50 = 0.2 की दक्षता प्राप्त कर सकते हैं, लेकिन इसके लिए केवल $50 के निवेश की आवश्यकता होती है।

रैखिक प्रोग्राम में परिवर्तन

किसी भी रेखीय-आंशिक प्रोग्राम को एक रेखीय प्रोग्राम में परिवर्तित किया जा सकता है यह मानते हुए कि चार्न्स-कूपर परिवर्तन का उपयोग करते हुए संभव क्षेत्र खाली नहीं है और परिबद्ध है।मुख्य विचार प्रोग्राम के लिए एक नया गैर-नकारात्मक चर $t$ प्रस्तुत करना है, जिसका उपयोग प्रोग्राम में सम्मिलित स्थिरांक ($\alpha ,\beta ,\mathbf {b}$) को पुनर्विक्रय करने के लिए उपयोग किया जाएगा, इससे हमें यह अपेक्षा करने की अनुमति मिलती है कि वस्तुनिष्ठ फलन का भाजक ($\mathbf {d} ^{T}\mathbf {x} +\beta$) 1 के बराबर है (परिवर्तन को समझने के लिए $\alpha =\beta =0$ के साथ सरल विशेष स्थिति पर विचार करना शिक्षाप्रद है।)

औपचारिक रूप से, चार्न्स-कूपर परिवर्तन के माध्यम से प्राप्त रैखिक प्रोग्राम रूपांतरित चर $\mathbf {y} \in \mathbb {R} ^{n}$ और $t\geq 0$ का उपयोग करता है

${\begin{aligned}{\text{maximize}}\quad &\mathbf {c} ^{T}\mathbf {y} +\alpha t\\{\text{subject to}}\quad &A\mathbf {y} \leq \mathbf {b} t\\&\mathbf {d} ^{T}\mathbf {y} +\beta t=1\\&t\geq 0.\end{aligned}}$

एक समाधान $\mathbf {x}$ मूल रेखीय-आंशिक प्रोग्राम को समानता के माध्यम से परिवर्तित रैखिक प्रोग्राम के समाधान में अनुवादित किया जा सकता है

$\mathbf {y} ={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}\cdot \mathbf {x} \quad {\text{and}}\quad t={\frac {1}{\mathbf {d} ^{T}\mathbf {x} +\beta }}.$

इसके विपरीत, रूपांतरित रैखिक प्रोग्राम $\mathbf {y}$ और $t$ के लिए एक समाधान को मूल रैखिक-आंशिक प्रोग्राम के समाधान में अनुवादित किया जा सकता है

$\mathbf {x} ={\frac {1}{t}}\mathbf {y} .$

द्वैत

बाधाओं से जुड़े दोहरे चरों $A\mathbf {y} -\mathbf {b} t\leq \mathbf {0}$ और $\mathbf {d} ^{T}\mathbf {y} +\beta t-1=0$ को क्रमशः $\mathbf {u}$ और $\lambda$ द्वारा दर्शाया जाता है फिर उपरोक्त LFP का द्वैत है

${\begin{aligned}{\text{minimize}}\quad &\lambda \\{\text{subject to}}\quad &A^{T}\mathbf {u} +\lambda \mathbf {d} =\mathbf {c} \\&-\mathbf {b} ^{T}\mathbf {u} +\lambda \beta \geq \alpha \\&\mathbf {u} \in \mathbb {R} _{+}^{m},\lambda \in \mathbb {R} ,\end{aligned}}$

जो LP है और चार्नेस-कूपर परिवर्तन से उत्पन्न समकक्ष रैखिक प्रोग्राम के द्वैत के साथ मेल खाता है।

गुण और एल्गोरिदम

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

स्रोत

• Murty, Katta G. (1983). "3.10 Fractional programming (pp. 160–164)". रैखिक प्रोग्रामिंग. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547.

अग्रिम पठन

• Bajalinov, E. B. (2003). Linear-Fractional Programming: Theory, Methods, Applications and Software. Boston: Kluwer Academic Publishers.
• Barros, Ana Isabel (1998). Discrete and fractional programming techniques for location models. Combinatorial Optimization. Vol. 3. Dordrecht: Kluwer Academic Publishers. pp. xviii+178. ISBN 978-0-7923-5002-6. MR 1626973.
• Martos, Béla (1975). Nonlinear programming: Theory and methods. Amsterdam-Oxford: North-Holland Publishing Co. p. 279. ISBN 978-0-7204-2817-9. MR 0496692.
• Schaible, S. (1995). "Fractional programming". In Reiner Horst and Panos M. Pardalos (ed.). Handbook of global optimization. Nonconvex optimization and its applications. Vol. 2. Dordrecht: Kluwer Academic Publishers. pp. 495–608. ISBN 978-0-7923-3120-9. MR 1377091.
• Stancu-Minasian, I. M. (1997). Fractional programming: Theory, methods and applications. Mathematics and its applications. Vol. 409. Translated by Victor Giurgiutiu from the 1992 Romanian. Dordrecht: Kluwer Academic Publishers Group. pp. viii+418. ISBN 978-0-7923-4580-0. MR 1472981.

सॉफ्टवेयर

• WinGULF - बहुत सारे विशेष विकल्पों (पिवोटिंग, मूल्य निर्धारण, ब्रांचिंग चर, आदि) के साथ शैक्षिक इंटरैक्टिव रैखिक और रैखिक- आंशिक प्रोग्रामिंग सॉल्वर।
• JOptimizer - जावा उत्तल अनुकूलन पुस्तकालय (ओपन सोर्स)

श्रेणी:अनुकूलन एल्गोरिद्म और विधियां श्रेणी:रैखिक प्रोग्रामिंग श्रेणी:सामान्य उत्तलता