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

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

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

${\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\}$ यानी वह क्षेत्र जिस पर भाजक धनात्मक है। वैकल्पिक रूप से, उद्देश्य फलन के भाजक को पूरे संभव क्षेत्र में सख्ती से नकारात्मक होना चाहिए।

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

रैखिक प्रोग्रामिंग और रैखिक-आंशिक प्रोग्रामिंग दोनों रैखिक समीकरणों और रैखिक असमानताओं का उपयोग करके अनुकूलन समस्याओं का प्रतिनिधित्व करते हैं, जो प्रत्येक समस्या-उदाहरण के लिए एक संभव सेट को परिभाषित करते हैं। आंशिक रैखिक कार्यक्रमों में उद्देश्य कार्यों का एक समृद्ध सेट होता है। अनौपचारिक रूप से, रैखिक प्रोग्रामिंग सर्वोत्तम परिणाम देने वाली नीति की गणना करती है, जैसे अधिकतम लाभ या न्यूनतम लागत। इसके विपरीत, लागत के परिणाम के उच्चतम अनुपात को प्राप्त करने के लिए एक रैखिक-आंशिक प्रोग्रामिंग का उपयोग किया जाता है, उच्चतम दक्षता का प्रतिनिधित्व करने वाला अनुपात। उदाहरण के लिए, एलपी के संदर्भ में हम उद्देश्य फलन 'लाभ = आय - लागत' को अधिकतम करते हैं और $100 का अधिकतम लाभ प्राप्त कर सकते हैं (= आय का $1100 - लागत का $1000)। इस प्रकार, एलपी में हमारे पास $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}}$

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

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

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

स्रोत

• 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 - जावा उत्तल अनुकूलन पुस्तकालय (ओपन सोर्स)

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