1. 分式规划例子

在数学规划问题中，若目标函数为分式函数，且约束条件中的函数是线性的，则称线性规划分式规划，简称分式规划。
分式规划通常可表示为如下形式：
$$\begin{gathered} \min \frac{{\mathbf{p}}^{\text{T}}\mathbf{x}+\alpha }{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta } \\ \text{s.t.}\{\begin{array}{l}\mathbf{A}\mathbf{x}\le \mathbf{b},\\ \mathbf{x}\ge 0.\end{array} \end{gathered}$$
其中，$\alpha$，$\beta$ 为常数；$\mathbf{p}$，$\mathbf{q}$ 为 $n$ 维列向量；$\mathbf{A}$ 为 $m\times 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} 是有界闭集，且对 $\forall \mathbf{x}\in S$，有 ${\mathbf{q}}^{\text{T}}\mathbf{x}+\beta >0$。引入新变量 $z$，令 $z=\frac{1}{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta }$，$\mathbf{y}=z\mathbf{x}$，则以上模型可转化为线性规划模型：
$$\begin{gathered} \min {\mathbf{p}}^{\text{T}}\mathbf{y}+\alpha z \\ \text{s.t.}\{\begin{array}{l}\mathbf{A}\mathbf{y}-\mathbf{b}z\le 0,\\ {\mathbf{q}}^{\text{T}}\mathbf{y}+\beta z=1,\\ \mathbf{y}\ge 0,z\ge 0.\end{array} \end{gathered}$$
至此，可用单纯形法来求解此规划，并最终得到原分式规划的最优解。

原分式 $\frac{{\mathbf{p}}^{\text{T}}\mathbf{x}+\alpha }{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta }$ 转化为
$$\begin{array}{rl}\frac{{\mathbf{p}}^{\text{T}}\mathbf{x}+\alpha }{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta }& =\frac{{\mathbf{p}}^{\text{T}}\mathbf{x}}{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta }+\frac{\alpha }{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta }\\ & ={\mathbf{p}}^{\text{T}}\mathbf{x}z+\alpha z\\ & ={\mathbf{p}}^{\text{T}}\mathbf{y}+\alpha z.\end{array}$$

原约束 $\mathbf{A}\mathbf{x}\le \mathbf{b}$ 转化为：
$$\begin{array}{rl}\mathbf{A}\mathbf{x}& \le \mathbf{b}\\ \mathbf{A}\frac{\mathbf{y}}{z}& \le \mathbf{b}\\ \mathbf{A}\mathbf{y}& \le \mathbf{b}z\\ \mathbf{A}\mathbf{y}-\mathbf{b}z& \le 0\end{array}$$

$z=\frac{1}{{\mathbf{q}}^{\text{T}}\mathbf{x}+\beta }$ 转化为：
$$\begin{array}{rl}z({\mathbf{q}}^{\text{T}}\mathbf{x}+\beta )& =1\\ {\mathbf{q}}^{\text{T}}z\mathbf{x}+\beta z& =1\\ {\mathbf{q}}^{\text{T}}\mathbf{y}+\beta z& =1\end{array}$$

2. 分式规划例题

例 求解下列分式规划：
$$\begin{gathered} \min \frac{-2x_1+x_2+2}{x_1+3x_2+4} \\ \text{s.t.}\{\begin{array}{l}-x_1+x_2\le 4,\\ 2x_1+x_2\le 14,\\ x_2\le 6,\\ x_1\ge 0,x_2\ge 0.\end{array} \end{gathered}$$

解 令 $z=\frac{1}{x_1+3x_2+4}$，$\mathbf{y}=z\mathbf{x}$，则原分式规划问题可转化为如下等价的线性规划模型：

$$\begin{gathered} \mathbf{A}=\left[\begin{array}{cc}-1& 1\\ 2& 1\\ 0& 1\end{array}\right],\mathbf{b}=\left[\begin{array}{c}4\\ 14\\ 6\end{array}\right],\mathbf{y}=\left[\begin{array}{c}{y}_1\\ y_2\end{array}\right],\mathbf{p}=\left[\begin{array}{c}-2\\ 1\end{array}\right],\mathbf{q}=\left[\begin{array}{c}1\\ 3\end{array}\right], \\ \alpha =2,\beta =4. \end{gathered}$$

$$\begin{gathered} {\mathbf{p}}^{\text{T}}\mathbf{y}+\alpha z=-2y_1+y_2+2z \\ \mathbf{A}\mathbf{y}-\mathbf{b}z\le 0\to \\ -y_1+y_2-4z\le 0 \\ 2y_1+y_2-14z\le 0 \\ {y}_2-6z\le 0 \\ {\mathbf{q}}^{\text{T}}\mathbf{y}+\beta z=1\to \\ {y}_1+3y_2+4z=1 \end{gathered}$$

$$\begin{gathered} \min -2y_1+y_2+2z \\ \text{s.t.}\{\begin{array}{l}-y_1+y_2-4z\le 0\\ 2y_1+y_2-14z\le 0\\ y_2-6z\le 0\\ y_1+3y_2+4z=1\\ y_1\ge 0,y_2\ge 0,z\ge 0.\end{array} \end{gathered}$$

首先化成标准型：
$$\begin{gathered} \min w=-2y_1+y_2+2z \\ \max (-w)=2y_1-y_2-2z-M{y}_6 \\ \text{s.t.}\{\begin{array}{l}-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\ge 0,z\ge 0.\end{array} \end{gathered}$$

初始单纯形表：

.	$y_1$	$y_2$	$y_3$	$y_4$	$y_5$	$y_6$	z	右边
.	-2-M	1-3M	0	0	0	0	2-4M	-M
$y_3$	-1	1	1	0	0	0	-4	0
$y_4$	2	1	0	1	0	0	-14	0
$y_5$	0	1	0	0	1	0	-6	0
$y_6$	1	3	0	0	0	1	4	1

最优单纯形表：

.	$y_1$	$y_2$	$y_3$	$y_4$	$y_5$	$y_6$	z	右边
.	0	$\frac{52}{11}$	0	$\frac{5}{11}$	0	$M+\frac{12}{11}$	0	$\frac{12}{11}$
$y_3$	0	4	1	0	0	1	0	1
$y_1$	1	$\frac{23}{11}$	0	$\frac{2}{11}$	0	$\frac{7}{11}$	0	$\frac{7}{11}$
$y_5$	0	$\frac{15}{11}$	0	$-\frac{3}{11}$	1	$\frac{6}{11}$	0	$\frac{6}{11}$
$z$	0	$\frac{5}{22}$	0	$\frac{1}{22}$	0	$\frac{1}{11}$	1	$\frac{1}{11}$

故：$y_1=\frac{7}{11}$，$y_2=0$，$z=\frac{1}{11}$ 是以上线性规划模型的最优解。
故原分式规划的最优解为 $x_1=\frac{y_1}{z}=7$，$x_2=\frac{y_2}{z}=0$。