線形分数計画法

数理最適化において、線形分数計画法（LFP ）は線形計画法（LP）の一般化です。線形計画法の目的関数は線形関数ですが、線形分数計画法の目的関数は2つの線形関数の比です。線形計画法は、分母が定数関数1である線形分数計画法の特殊なケースとみなすことができます。

正式には、線形分数計画問題は、多面体上のアフィン関数の比を最大化（または最小化）する問題として定義される。

${\displaystyle {\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}}}$

どこ$\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$は決定すべき変数のベクトルを表します。${\displaystyle \mathbf {c} ,\mathbf {d} \in \mathbb {R} ^{n}}$そして$\displaystyle \mathbf {b} \in \mathbb {R} ^{m}}$は（既知の）係数のベクトルであり、$\displaystyle A\in \mathbb {R} ^{m\times n}}$は係数の（既知の）行列であり、${\displaystyle \alpha ,\beta \in \mathbb {R} }$は定数です。制約条件は実行可能領域を制限しなければなりません。${\displaystyle \{\mathbf {x} |\mathbf {d} ^{T}\mathbf {x} +\beta >0\}}$つまり、分母が正となる領域です。^{[ 1 ] [ 2 ]}あるいは、目的関数の分母は実行可能領域全体で厳密に負でなければなりません。

線形計画法と線形分数計画法はどちらも、線形方程式と線形不等式を用いて最適化問題を表現します。これらの式は、問題の各インスタンスに対して実行可能集合を定義します。分数線形計画法は、より豊富な目的関数セットを持ちます。非公式には、線形計画法は、最大利益や最小コストなど、最良の結果をもたらす方策を計算します。対照的に、線形分数計画法は、結果とコストの比率を最大化するために使用されます。この比率は、最高の効率を表します。たとえば、LP の文脈では、目的関数profit  =  income − cost  を最大化し、最大利益 $100 (=  $1100 の 収入− $1000 のコスト) を得ることができます。したがって、LP では、効率は $100/$1000 = 0.1 となります。LFP を使用すると、投資額が $50 だけで、利益は $10 に過ぎず、効率は $10/$50 = 0.2 となります。      

実行可能領域が空でなく有界であると仮定すれば、任意の線形分数計画問題は、Charnes–Cooper変換を用いて線形計画問題に変換できる。^{[ 1 ]}主なアイデアは、新しい非負変数を導入することである。${\displaystyle t}$プログラムに含まれる定数を再スケーリングするために使用されるプログラムへ（${\displaystyle \alpha ,\beta ,\mathbf {b} }$これにより、目的関数の分母が${\displaystyle \mathbf {d} ^{T}\mathbf {x} +\beta }$) は 1 に等しい。(変換を理解するために、より単純な特殊なケースを考察すると有益である。${\displaystyle \alpha =\beta =0}$）

形式的には、チャーンズ・クーパー変換によって得られる線形計画法は、変換された変数を使用する。$\displaystyle \mathbf {y} \in \mathbb {R} ^{n}}$そして$t ≥ 0$:

${\displaystyle {\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}}}$

解決策${\displaystyle \mathbf {x} }$元の線形分数計画は、等式を介して変換された線形計画の解に変換できます。

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

逆に、${\displaystyle \mathbf {y} }$そして${\displaystyle t}$変換された線形計画の解は、次の方法で元の線形分数計画の解に変換できます。

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

制約に関連付けられた双対変数を${\displaystyle A\mathbf {y} -\mathbf {b} t\leq \mathbf {0} }$そして${\displaystyle \mathbf {d} ^{T}\mathbf {y} +\beta t-1=0}$で表す${\displaystyle \mathbf {u} }$そして${\displaystyle \lambda }$それぞれ。すると、上記の LFP の双対は^{[ 3 ] [ 4 ]となります。}

${\displaystyle {\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}}}$

これは線形計画問題であり、チャーンズ・クーパー変換によって得られる同等の線形計画問題の双対問題と一致する。

線形分数問題の目的関数は、準凹関数かつ準凸関数（したがって準線形）であり、単調性、擬凸性を持ちます。擬凸性は、準凸性よりも強い性質です。線形分数目的関数は、擬凸関数かつ擬凹関数であるため、擬線形です。LFP は LP に変換できるため、シンプレックス法（George B. Dantzigによる）^{[ 5 ] [ 6 ] [ 7 ] [ 8 ]} 、クロス法^{[ 9 ]} 、内点法など、任意のLP解法を使用して解くことができます。

• Murty, Katta  G. (1983). "3.10 分数計画法（pp. 160–164）".線形計画法. ニューヨーク：John Wiley & Sons, Inc. pp.  xix+482. ISBN 978-0-471-09725-9. MR 0720547 . 

• Bajalinov, EB (2003).線形分数計画法：理論、方法、応用、ソフトウェア. ボストン：Kluwer Academic Publishers.
• Barros, Ana Isabel (1998).位置モデルのための離散および分数計画法. 組合せ最適化. 第 3巻. ドルドレヒト: Kluwer Academic Publishers. pp.  xviii+178. ISBN 978-0-7923-5002-6MR 1626973 .​ 
• マルトス、ベラ（1975）。非線形計画法：理論と方法。アムステルダム＝オックスフォード：ノースホランド出版。p.  279。ISBN 978-0-7204-2817-9. MR 0496692 . 
• Schaible, S. (1995). 「分数計画法」. Reiner Horst および Panos M. Pardalos (編)『グローバル最適化ハンドブック』非凸最適化とその応用. 第 2 巻. ドルドレヒト: Kluwer Academic Publishers. pp. 495–608 . ISBN  978-0-7923-3120-9MR 1377091 .​ 
• Stancu-Minasian, IM (1997).分数計画法：理論、方法、応用. 数学とその応用. 第 409巻. Victor Giurgiutiuによる1992年ルーマニア語からの翻訳. ドルドレヒト：Kluwer Academic Publishers Group. pp.  viii+418. ISBN 978-0-7923-4580-0. MR 1472981 .