說(shuō)到分?jǐn)?shù)規(guī)劃，其實(shí)這只是一個(gè)用來(lái)轉(zhuǎn)換問(wèn)題模型的一個(gè)套路，并沒(méi)有固定的模板什么的，下面我們看看分?jǐn)?shù)規(guī)劃的形式和特性。

分?jǐn)?shù)規(guī)劃(fractional programming) 的一般形式：

對(duì)于解空間 S 、連續(xù)的實(shí)值函數(shù) a(x)，b(x) ，滿(mǎn)足 ?x∈S , b(x)>0，求

解決分?jǐn)?shù)規(guī)劃問(wèn)題的一般方法是分析其對(duì)偶問(wèn)題，但更加實(shí)用的方法是對(duì)其進(jìn)行 參數(shù)搜索(parametric search)，即對(duì)答案進(jìn)行猜測(cè)，再驗(yàn)證該猜測(cè)值的最優(yōu)性，將優(yōu)化問(wèn)題轉(zhuǎn)化為判定性問(wèn)題或其他的優(yōu)化問(wèn)題。由于分?jǐn)?shù)規(guī)劃模型的特殊性，使得能夠構(gòu)造另外一個(gè)由猜測(cè)值 λ \lambdaλ 作為自變量的相關(guān)問(wèn)題，且該問(wèn)題的解滿(mǎn)足一定的單調(diào)性，或其他的可以減小參數(shù)搜索范圍的性質(zhì)①，從而逼近答案。

① 比如 Dinkelbach算法，每次直接把上次子問(wèn)題的解向量代入原問(wèn)題的表達(dá)式，算出下一個(gè)迭代式的猜測(cè)值。

假設(shè)是最優(yōu)解，根據(jù)定義有

由上面的形式構(gòu)造一個(gè)新函數(shù)

這個(gè)新函數(shù)是一個(gè)非分式的規(guī)劃。先來(lái)挖掘函數(shù) g(λ) 本身的性質(zhì)。

（1）單調(diào)性

g(λ) 是一個(gè)嚴(yán)格遞減函數(shù)，即， 

只需要注意到，在中原有的 x 代入會(huì)得到更小的結(jié)果即可。

（2）Dinkelbach定理

若為原問(wèn)題的答案，則

1. 必要性

先證明

設(shè)，根據(jù)定義有

而恰好取到這個(gè)下界 0 ，所以最小值就是 0 ，證畢。

2. 充分性

再證明

反證法。反設(shè)存在一個(gè)解 λ′= f(x′) 是更優(yōu)的解，根據(jù)定義有

那么，將 x′代入，可以發(fā)現(xiàn) g(λ) 一定是小于零的，與題設(shè)矛盾。

（3）二分查找

仍然設(shè)為答案，則

此時(shí)便可以進(jìn)行二分查找了。