Lineární-zlomkové programování - Linear-fractional programming

v matematická optimalizace, lineární-zlomkové programování (LFP) je zobecněním lineární programování (LP). Zatímco objektivní funkce v lineárním programu je a lineární funkce, objektivní funkce v lineárně-zlomkovém programu je poměr dvou lineárních funkcí. Lineární program lze považovat za zvláštní případ lineárně-zlomkového programu, ve kterém je jmenovatelem konstantní funkce.

Vztah k lineárnímu programování

Lineární programování i lineární frakční programování představují optimalizační problémy pomocí lineárních rovnic a lineárních nerovností, které pro každou instanci problému definují proveditelná sada. Frakční lineární programy mají bohatší sadu objektivních funkcí. Lineární programování neformálně počítá politiku, která přináší nejlepší výsledek, například maximální zisk nebo nejnižší náklady. Naproti tomu lineární-zlomkové programování se používá k dosažení nejvyššího poměr výsledku k nákladům, poměr představující nejvyšší účinnost. Například v kontextu LP maximalizujeme objektivní funkci zisk = příjem - náklady a může získat maximální zisk 100 $ (= 1100 $ z příjmu - 1000 $ z nákladů). V LP tedy máme účinnost 100 $ / 1000 $ = 0,1. Pomocí LFP bychom mohli dosáhnout efektivity 10 $ / 50 $ = 0,2 se ziskem pouze 10 $, ale pouze s investicí 50 $.

Definice

Formálně je lineárně-zlomkový program definován jako problém maximalizace (nebo minimalizace) poměru afinní funkce přes mnohostěn,

${displaystyle {egin {aligned} {ext {maximize}} quad & {frac {mathbf {c} ^ {T} mathbf {x} + alpha} {mathbf {d} ^ {T} mathbf {x} + eta}} {ext {subject to}} quad & Amathbf {x} leq mathbf {b}, end {aligned}}}$

kde ${displaystyle mathbf {x} v mathbb {R} ^ {n}}$ představuje vektor proměnných, které mají být stanoveny, ${displaystyle mathbf {c}, mathbf {d} v mathbb {R} ^ {n}}$ a ${displaystyle mathbf {b} v mathbb {R} ^ {m}}$ jsou vektory (známých) koeficientů, ${displaystyle Ain mathbb {R} ^ {m imes n}}$ je (známá) matice koeficientů a ${displaystyle alpha, eta in mathbb {R}}$ jsou konstanty. Omezení musí omezovat proveditelný region na ${displaystyle {mathbf {x} | mathbf {d} ^ {T} mathbf {x} + eta> 0}}$, tj. oblast, ve které je jmenovatel kladný.^[1][2] Alternativně musí být jmenovatel objektivní funkce přísně negativní v celé proveditelné oblasti.

Transformace na lineární program

Za předpokladu, že proveditelná oblast je neprázdná a ohraničená, Charnes-Cooperova transformace^[1]

${displaystyle mathbf {y} = {frac {1} {mathbf {d} ^ {T} mathbf {x} + eta}} cdot mathbf {x} ;;;; t = {frac {1} {mathbf {d} ^ {T} mathbf {x} + eta}}}$

převede výše uvedený lineární frakční program na ekvivalentní lineární program:

${displaystyle {egin {aligned} {ext {maximize}} quad & mathbf {c} ^ {T} mathbf {y} + alpha t {ext {subject}} quad & Amathbf {y} leq mathbf {b} t & mathbf {d} ^ {T} mathbf {y} + eta t = 1 & tgeq 0.end {zarovnáno}}}$

Pak řešení pro ${displaystyle mathbf {y}}$ a ${displaystyle t}$ přináší řešení původního problému jako

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

Dualita

Nech duální proměnné spojené s omezeními ${displaystyle Amathbf {y} -mathbf {b} tleq mathbf {0}}$ a ${displaystyle mathbf {d} ^ {T} mathbf {y} + eta t-1 = 0}$ být označen ${displaystyle mathbf {u}}$ a ${displaystyle lambda}$, resp. Pak je duální LFP výše ^[3][4]

${displaystyle {egin {aligned} {ext {minimal}} quad & lambda {ext {subject to}} quad & A ^ {T} mathbf {u} + lambda mathbf {d} = mathbf {c} & - mathbf {b } ^ {T} mathbf {u} + lambda eta geq alpha & mathbf {u} v mathbb {R} _ {+} ^ {m}, lambda v mathbb {R}, konec {zarovnáno}}}$

který je LP a který se shoduje s duálem ekvivalentního lineárního programu vyplývajícího z Charnes-Cooperovy transformace.

Vlastnosti a algoritmy

Objektivní funkce v lineárně-zlomkovém problému je jak kvazikonkávní, tak i kvazikonvexní (tedy kvazilineární) s a monotónní vlastnictví, pseudokonvexnost, což je silnější vlastnost než kvazikonvexnost. Lineární frakční objektivní funkce je tedy pseudokonvexní i pseudokonkávní pseudolinear. Vzhledem k tomu, že LFP lze transformovat na LP, lze jej vyřešit pomocí jakékoli metody řešení LP, například simplexní algoritmus (z George B. Dantzig ),^[5][6][7][8] the křížový algoritmus,^[9] nebo metody vnitřních bodů.

Poznámky

Reference

• Craven, B. D. (1988). Frakční programování. Série Sigma v aplikované matematice. 4. Berlín: Heldermann Verlag. p. 145. ISBN  978-3-88538-404-5. PAN  0949209.
• Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "Metoda konečného křížení pro hyperbolické programování". Evropský žurnál operačního výzkumu. 114 (1): 198–214. CiteSeerX  10.1.1.36.7090. doi:10.1016 / S0377-2217 (98) 00049-6. Zbl  0953.90055. Postprintový předtisk.CS1 maint: ref = harv (odkaz)
• Kruk, Serge; Wolkowicz, Henry (1999). "Pseudolinear programování". Recenze SIAM. 41 (4): 795–805. doi:10.1137 / S0036144598335259. JSTOR  2653207. PAN  1723002.
• Mathis, Frank H .; Mathis, Lenora Jane (1995). "Nelineární programovací algoritmus pro správu nemocnice". Recenze SIAM. 37 (2): 230–234. doi:10.1137/1037046. JSTOR  2132826. PAN  1343214.
• Murty, Katta G. (1983). „3.10 Částečné programování (str. 160–164)“. Lineární programování. New York: John Wiley & Sons, Inc., str. Xix + 482. ISBN  978-0-471-09725-9. PAN  0720547.CS1 maint: ref = harv (odkaz)

Další čtení

• Bajalinov, E. B. (2003). Lineární frakční programování: teorie, metody, aplikace a software. Boston: Kluwer Academic Publishers.
• Barros, Ana Isabel (1998). Techniky diskrétního a částečného programování pro modely umístění. Kombinatorická optimalizace. 3. Dordrecht: Kluwer Academic Publishers. str. xviii + 178. ISBN  978-0-7923-5002-6. PAN  1626973.
• Martos, Béla (1975). Nelineární programování: Teorie a metody. Amsterdam-Oxford: North-Holland Publishing Co. str. 279. ISBN  978-0-7204-2817-9. PAN  0496692.
• Schaible, S. (1995). "Částečné programování". In Reiner Horst a Panos M. Pardalos (ed.). Příručka globální optimalizace. Nekonvexní optimalizace a její aplikace. 2. Dordrecht: Kluwer Academic Publishers. str. 495–608. ISBN  978-0-7923-3120-9. PAN  1377091.
• Stancu-Minasian, I. M. (1997). Frakční programování: Teorie, metody a aplikace. Matematika a její aplikace. 409. Přeložil Victor Giurgiutiu z rumunského jazyka z roku 1992. Dordrecht: Kluwer Academic Publishers Group. str. viii + 418. ISBN  978-0-7923-4580-0. PAN  1472981.

Software

• WinGULF - vzdělávací interaktivní lineární a lineárně-frakční programovací řešič se spoustou speciálních možností (otočení, tvorba cen, větvení proměnných atd.)
• JOptimizer - konvexní knihovna optimalizace Java (open source)