非线性规划之分式规划

朴灿烈づ我的快乐病毒、 2021-09-25 04:36 488阅读 0赞

### 文章目录 ###

*  1. 分式规划例子
 *  2. 分式规划例题

# 1. 分式规划例子 #

在数学规划问题中，若目标函数为分式函数，且约束条件中的函数是线性的，则称线性规划分式规划，简称分式规划。  
分式规划通常可表示为如下形式：  
 min ⁡ p T x + α q T x + β s.t. \{ A x ≤ b , x ≥ 0 . \\min \\frac\{\\bm\{p\}^\\text\{T\}\\bm\{x\} + \\alpha\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} \\\\ \\text\{s.t.\} \\begin\{cases\} \\bm\{Ax\} \\leq \\bm\{b\}, \\\\ \\bm\{x\} \\geq \\bm\{0\}. \\\\ \\end\{cases\} minqTx\+βpTx\+αs.t.\{ Ax≤b,x≥0.  
其中， α \\alpha α， β \\beta β 为常数； p \\bm\{p\} p， q \\bm\{q\} q 为  n n n 维列向量； A \\bm\{A\} A 为  m × n m \\times n m×n 阶矩阵。

这一类问题有类似于线性规划问题的极好的性质。

1.  若分式规划问题存在最优解，则最优解可在可行域顶点上达到。
2.  任一局部极小值即全局极小值。

由 Charnes 和 Cooper 于 1962 年提出的用单纯刑法求解分式规划问题的方法：  
设集合上  S = \{ x ∈ R n ∣ A x ≤ b , b ≥ 0 \} S = \\\{ x \\in \\mathbb\{R\}^n \\mid \\bm\{Ax\} \\leq \\bm\{b\}, \\bm\{b\} \\geq \\bm\{0\} \\\} S=\{ x∈Rn∣Ax≤b,b≥0\} 是有界闭集，且对  ∀ x ∈ S \\forall \\bm\{x\} \\in S ∀x∈S，有  q T x + β > 0 \\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta > 0 qTx\+β>0。引入新变量  z z z，令  z = 1 q T x + β z = \\frac\{1\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} z=qTx\+β1， y = z x \\bm\{y\} = z \\bm\{x\} y=zx，则以上模型可转化为线性规划模型：  
 min ⁡ p T y + α z s.t. \{ A y − b z ≤ 0 , q T y + β z = 1 , y ≥ 0 , z ≥ 0. \\min \\bm\{p\}^\\text\{T\}\\bm\{y\} + \\alpha z \\\\ \\text\{s.t.\} \\begin\{cases\} \\bm\{Ay\} - \\bm\{b\}z \\leq 0, \\\\ \\bm\{q\}^\\text\{T\}\\bm\{y\} + \\beta z = 1, \\\\ \\bm\{y\} \\geq 0, z \\geq 0. \\\\ \\end\{cases\} minpTy\+αzs.t.⎩⎪⎨⎪⎧Ay−bz≤0,qTy\+βz=1,y≥0,z≥0.  
至此，可用单纯形法来求解此规划，并最终得到原分式规划的最优解。

原分式  p T x + α q T x + β \\frac\{\\bm\{p\}^\\text\{T\}\\bm\{x\} + \\alpha\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} qTx\+βpTx\+α 转化为  
 p T x + α q T x + β = p T x q T x + β + α q T x + β = p T x z + α z = p T y + α z . \\begin\{aligned\} \\frac\{\\bm\{p\}^\\text\{T\}\\bm\{x\} + \\alpha\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} &= \\frac\{\\bm\{p\}^\\text\{T\}\\bm\{x\}\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} + \\frac\{\\alpha\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} \\\\ & = \\bm\{p\}^\\text\{T\} \\bm\{x\} z + \\alpha z \\\\ & = \\bm\{p\}^\\text\{T\} \\bm\{y\} + \\alpha z. \\\\ \\end\{aligned\} qTx\+βpTx\+α=qTx\+βpTx\+qTx\+βα=pTxz\+αz=pTy\+αz.

原约束  A x ≤ b \\bm\{Ax\} \\leq \\bm\{b\} Ax≤b 转化为：  
 A x ≤ b A y z ≤ b A y ≤ b z A y − b z ≤ 0 \\begin\{aligned\} \\bm\{Ax\} & \\leq \\bm\{b\} \\\\ \\bm\{A\}\\frac\{\\bm\{y\}\}\{z\} & \\leq \\bm\{b\} \\\\ \\bm\{Ay\} &\\leq \\bm\{b\} z \\\\ \\bm\{Ay\} - \\bm\{b\}z & \\leq 0 \\\\ \\end\{aligned\} AxAzyAyAy−bz≤b≤b≤bz≤0

z = 1 q T x + β z = \\frac\{1\}\{\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta\} z=qTx\+β1 转化为：  
 z ( q T x + β ) = 1 q T z x + β z = 1 q T y + β z = 1 \\begin\{aligned\} z (\\bm\{q\}^\\text\{T\}\\bm\{x\} + \\beta) & = 1 \\\\ \\bm\{q\}^\\text\{T\} z \\bm\{x\} + \\beta z & = 1 \\\\ \\bm\{q\}^\\text\{T\} \\bm\{y\} + \\beta z & = 1 \\\\ \\end\{aligned\} z(qTx\+β)qTzx\+βzqTy\+βz=1=1=1

# 2. 分式规划例题 #

**例** 求解下列分式规划：  
 min ⁡ − 2 x 1 + x 2 + 2 x 1 + 3 x 2 + 4 s.t. \{ − x 1 + x 2 ≤ 4 , 2 x 1 + x 2 ≤ 14 , x 2 ≤ 6 , x 1 ≥ 0 , x 2 ≥ 0. \\min \\frac\{-2x\_1 + x\_2 + 2\}\{x\_1 + 3x\_2 + 4\} \\\\ \\text\{s.t.\} \\begin\{cases\} -x\_1 + x\_2 \\leq 4, \\\\ 2x\_1 + x\_2 \\leq 14, \\\\ x\_2 \\leq 6, \\\\ x\_1 \\geq 0, x\_2 \\geq 0. \\\\ \\end\{cases\} minx1\+3x2\+4−2x1\+x2\+2s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧−x1\+x2≤4,2x1\+x2≤14,x2≤6,x1≥0,x2≥0.

**解** 令  z = 1 x 1 + 3 x 2 + 4 z = \\frac\{1\}\{x\_1 + 3x\_2 + 4\} z=x1\+3x2\+41， y = z x \\bm\{y\} = z\\bm\{x\} y=zx，则原分式规划问题可转化为如下等价的线性规划模型：

A = \[ − 1 1 2 1 0 1 \] , b = \[ 4 14 6 \] , y = \[ y 1 y 2 \] , p = \[ − 2 1 \] , q = \[ 1 3 \] , α = 2 , β = 4. \\bm\{A\} = \\begin\{bmatrix\} -1 & 1 \\\\ 2 & 1 \\\\ 0 & 1 \\\\ \\end\{bmatrix\}, \\bm\{b\} = \\begin\{bmatrix\} 4 \\\\ 14 \\\\ 6 \\\\ \\end\{bmatrix\}, \\bm\{y\} = \\begin\{bmatrix\} y\_1 \\\\ y\_2 \\\\ \\end\{bmatrix\}, \\bm\{p\} = \\begin\{bmatrix\} -2 \\\\ 1 \\\\ \\end\{bmatrix\}, \\bm\{q\} = \\begin\{bmatrix\} 1 \\\\ 3 \\\\ \\end\{bmatrix\}, \\\\ \\alpha = 2, \\beta = 4. A=⎣⎡−120111⎦⎤,b=⎣⎡4146⎦⎤,y=\[y1y2\],p=\[−21\],q=\[13\],α=2,β=4.

p T y + α z = − 2 y 1 + y 2 + 2 z A y − b z ≤ 0 → − y 1 + y 2 − 4 z ≤ 0 2 y 1 + y 2 − 14 z ≤ 0 y 2 − 6 z ≤ 0 q T y + β z = 1 → y 1 + 3 y 2 + 4 z = 1 \\bm\{p\}^\\text\{T\} \\bm\{y\} + \\alpha z = -2 y\_1 + y\_2 + 2z \\\\ \\bm\{Ay\} - \\bm\{b\} z \\leq 0 \\rightarrow \\\\ -y\_1 + y\_2 - 4 z \\leq 0 \\\\ 2y\_1 + y\_2 - 14 z \\leq 0 \\\\ y\_2 - 6 z \\leq 0 \\\\ \\bm\{q\}^\\text\{T\} \\bm\{y\} + \\beta z = 1 \\rightarrow \\\\ y\_1 + 3y\_2 + 4z = 1 \\\\ pTy\+αz=−2y1\+y2\+2zAy−bz≤0→−y1\+y2−4z≤02y1\+y2−14z≤0y2−6z≤0qTy\+βz=1→y1\+3y2\+4z=1

min ⁡ − 2 y 1 + y 2 + 2 z s.t. \{ − y 1 + y 2 − 4 z ≤ 0 2 y 1 + y 2 − 14 z ≤ 0 y 2 − 6 z ≤ 0 y 1 + 3 y 2 + 4 z = 1 y 1 ≥ 0 , y 2 ≥ 0 , z ≥ 0. \\min -2y\_1 + y\_2 + 2z \\\\ \\text\{s.t.\} \\begin\{cases\} -y\_1 + y\_2 - 4z \\leq 0 \\\\ 2y\_1 + y\_2- 14z \\leq 0 \\\\ y\_2 - 6z \\leq 0 \\\\ y\_1 + 3y\_2 + 4z = 1 \\\\ y\_1 \\geq 0, y\_2 \\geq 0, z \\geq 0. \\\\ \\end\{cases\} min−2y1\+y2\+2zs.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧−y1\+y2−4z≤02y1\+y2−14z≤0y2−6z≤0y1\+3y2\+4z=1y1≥0,y2≥0,z≥0.

首先化成标准型：  
 min ⁡ w = − 2 y 1 + y 2 + 2 z max ⁡ ( − w ) = 2 y 1 − y 2 − 2 z − M y 6 s.t. \{ − y 1 + y 2 − 4 z + y 3 = 0 , 2 y 1 + y 2 − 14 z + y 4 = 0 , y 2 − 6 z + y 5 = 0 , y 1 + 3 y 2 + 4 z + y 6 = 1 , y j ≥ 0 , z ≥ 0. \\min w = -2y\_1 + y\_2 + 2z \\\\ \\max (-w) = 2y\_1 - y\_2 - 2z - M y\_6 \\\\ \\text\{s.t.\} \\begin\{cases\} -y\_1 + y\_2 - 4z + y\_3 = 0, \\\\ 2y\_1 + y\_2 - 14z + y\_4 = 0, \\\\ y\_2 - 6z + y\_5 = 0, \\\\ y\_1 + 3y\_2 + 4z + y\_6 = 1, \\\\ y\_j \\geq 0, z \\geq 0. \\\\ \\end\{cases\} minw=−2y1\+y2\+2zmax(−w)=2y1−y2−2z−My6s.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧−y1\+y2−4z\+y3=0,2y1\+y2−14z\+y4=0,y2−6z\+y5=0,y1\+3y2\+4z\+y6=1,yj≥0,z≥0.

初始单纯形表：

最优单纯形表：

故： y 1 = 7 11 y\_1 = \\frac\{7\}\{11\} y1=117， y 2 = 0 y\_2 = 0 y2=0， z = 1 11 z = \\frac\{1\}\{11\} z=111 是以上线性规划模型的最优解。  
故原分式规划的最优解为  x 1 = y 1 z = 7 x\_1 = \\frac\{y\_1\}\{z\} = 7 x1=zy1=7， x 2 = y 2 z = 0 x\_2 = \\frac\{y\_2\}\{z\} = 0 x2=zy2=0。