线性规划

                     

贡献者： 零穹

　　 1939 年，苏联数学家 Kantorovich 出版了《生产组织与计划中的线性规划模型》一书，为列宁格勒胶合板厂的计划任务建立了一个线性规划的数学模型，为用数学方法解决管理并使二者结合做出了开创性的工作。后来，由于战争的需要，美国经济学家 Koopmans 重新独立地研究运输问题，并很快看到了线性规划在经济学中应用的意义。此后线性规划也被广泛应用于军事、经济等各方面。鉴于他们在线性规划方面的突出贡献，1975 年的诺贝尔经济学奖授予了他们。1947 年美国数学家 Dantzig 提出了求解一般线性规划问题的方法——单纯性法，之后线性规划问题在理论上日益成熟，并在实际中日益广泛应用。

　　 线性规划研究的是在线性不等式或等式限制下，使得某一线性目标取得最大（或最小）的问题。

1. 线性规划

　　 由线性规划的定义，线性规划模型式 1 具有很多形式，但是我们总可以将其转化为某一种特定的形式，并只需要对这种形式进行研究。

2. 线性规划的标准形式

　　 通常称下面定义的形式为线性规划模型的标准形式。

　　 任何线性规划模型式 1 都可以化为标准型式 2 ：若约束条件为 $\sum _j^n{a}_{ij}{x}_i\le b_i$，则引入 $y_i$，从而约束条件等价于

此时 $y_i$ 称为松弛变量。

　　 若约束条件为 $\sum _j^n{a}_{ij}{x}_i\ge 0$，则引入 $y_i$，从而约束条件等价于

此时 $y_i$ 称为剩余变量。

　　 若目标函数为 $maxz$，则定义 $z^{\prime }=-z$，于是目标函数等价于 $min{z}^{\prime }$。

　　 若某个变量 $x_i$ 无限制，则引入两个变量 $x_i^{\prime },x_i^{″}$，从而 $x_i$ 无限制等价于

在标准形式下，使得目标函数最小的变量 $x_1,\cdots ,x_n$ 在以变量为的坐标的坐标系下将只能在 “第一象限”。

3. 单纯形法

　　 首先介绍求解线性规划常用的术语。由于任一的线性规划都可化为标准型，我们讨论标准型。

　　 证明：将式 2 写为矩阵形式：

其中 $x=(x_1,\cdots ,x_n{)}^T,A=(a_{ij}),b=(b_1,\cdots ,b_n{)}^T,c=(c_1,\cdots ,c_m{)}^T$。设 $A$ 的秩总为 $m$（否则可将某些约束条件去掉变成这一情形，或者由约束可知问题无解，于是不用讨论），总可以调换式 2 中 $x_i$ 之间的顺序，使得 $A$ 中 $m$ 个线性无关的列在前 $m$ 列。因此，总可以认为矩阵 $A$ 的前 $m$ 列是线性无关的。

　　 设 $B$ 是 $A$ 的前 $m$ 列构成的矩阵，$N$ 是后 $n-m$ 列构成的矩阵，$x_B=(x_1,\cdots ,x_m{)}^T,x_N=(x_{m+1},\cdots ,x_n{)}^T$。那么有

即 $B{x}_B+N{x}_N=b$，从而 $x_B=B^{-1}b-B^{-1}N{x}_N$。于是 式 7 等价于

　　 证毕！

　　 注意，基本解只是式 6 的约束条件的解，而不一定是可行解，除非对应的 $x_B=B^{-1}b$ 大于 0。

　　 证明：充分性：设 $x$ 是任一可行解。那么把它带入标准式和典则式中，即得

而可行解意味着 $x_i\ge 0$，因此所有的 ${\lambda }_i\ge 0$ 意味着 $z(x)\ge z_0$，因而基本可行解是最优解。

　　 必要性：设基本解 $x\ast$ 是最优解，即 $z(x^{\ast })=z_0$。若 ${\lambda }_i>0$，则一定存在可行解 $x$，使得 $x$ 中仅 $x_i$ 分量不为 0，而其它分量为 0，并且 $x_i>0$（暂略）。把它带入式 6 ，则得 $z(x)=-{\lambda }_i{x}_i+z_0<z_0$。这与 $z_0$ 最小矛盾。

　　 证毕！