线性规划

爱编程的小明

发布于 2022-09-06 14:22:13

2K0

线性规划最先在第二次世界大战时被提出，用于最大化资源的利用效率。其中的“规划”也是一个军事词汇，指按照既定的时刻表去执行任务或者用最佳方式做人员部署。线性规划问题的研究很快得到了大家的关注。

基本形式

线性规划的一般形式为：

\begin{array}{cl} \min _{x \in \mathbb{R}^{n}} & Z=CX=\sum\limits_{j=1}^n c^{\mathrm{T}} x, \\ \text { s.t. } & A x=b, \\ & G x \leqslant e, \end{array}

这样的线性规划问题可以通过一些方法转化为一下标准形线性规划问题(等式约束和决策变量非负)

\begin{array}{cl} \min _{x \in \mathbb{R}^{n}} & {Z=CX} , \\ \text { s.t. } & A x=b, \\ & x \geqslant 0, \\ &b_i\geqslant 0 \end{array}

A是m\times n型矩阵，m是约束方程的个数，n是决策变量的个数（一般来说

具体的转化方法包括:

目标函数是求最大值的问题，可以通过将目标函数的系数乘以“-1”来找最小值，即

对应同一个解。

不等式约束条件可以通过引入松弛变量化为等式约束条件，例如对于不等式约束:

x_1+x_2+x_3\le 8

可以通过引入x_4=8-x_1-x_2-x_3\ge 0 来实现，即通过引入松弛变量x_4 ，将原来的约束问题转化为:

对于取值无约束的变量x_k ，可以通过引入两个有约束的变量来表示，如可令x_k=x_k^{'}-x_k^{''} ,其中x_k=x_k^{'}-x_k^{''}\ge 0

解的概念和基本定理

考虑标准形线性规划的约束条件:

AX=b, X\ge 0

这里矩阵A为m\times n 矩阵，从矩阵A

中抽取m列组成新矩阵，若得到的新的矩阵可逆，则认为该矩阵为对应线性规划问题的一个基，记为, 称的列向量的为基向量，记为P_j(j=1, 2, \dots , m) 。

与基向量对应的变量

称为基变量,记为X_B=[x_1, x_2, \dots, x_m]^T , 其余的变量称为非基变量,记为X_N 。接着令n-m个非基变量为0，可以解得约束方程组的解，这里叫做约束方程组的基本解/基解：

其中满足非负约束条件X\ge 0 A的基解称为基本可行解/基可行解。

基可行解都是可行域的顶点

若最优解在基解中，那么该最优解也叫做基本最优解。 基可行解对应的基称为可行基。基本最优解对应的基称为可行基。

当最优解唯一时，最优解亦是基本最优解，当最优解不唯一时，则最优解不一定是基本最优解。

凸集、凸组合、极点

线性规划的解的基本定理:

若可行域有界，则线性规划问题的目标函数一定可以在可行域的顶点上达到最优。

若线性规划有最优解, 则最优值一定可以在可行解集合的某个极点上到达, 最优解就是极点的坐标向量.

线性规划的可行解集合K的点X是极点的充要条件为X是基本可行解.

定理2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点（退化基本可行解时）。

若线性规划可行解K非空,则K是凸集.

迭代算法

图解法

。。。

单纯形法

单纯形法的基本思路是从某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），直到目标函数达到最优，对应的基可行解即为最优解。单纯形法中可行解的变换是通过对增广矩阵的行变换实现的，无论是对约束条件还是目标函数进行行变换，都不会改变最优解的取值。为了计算方便，一般通过构造单纯形表进行计算，每迭代一步构造一个新的单纯形表。接下来根据老师ppt的一个例子进行说明:

为了计算方便，一般取好求逆的矩阵作为基:

进而解得初始基本可行解:

作出对应的单纯形表:

\begin{array}{|c|c|c|c|c|c|c|} \hline X_{B} & x_{1} & x_{2} & x_{3} & x_{4} & b & \theta_{i} \\ \hline x_{3} & 2 & 1 & 1 & 0 & 40 & 40\\ \hline x_{4} & 1 & 3 & 0 & 1 & 30 & 10\\ \hline \lambda_{j} & 3 & 4 & 0 & 0 & & \\ \hline \end{array}

这里需要注意的是，我们要保证x_3, x_4 有一个要大于零（仍然作为基变量）的情况下最大化x_2 ，因此我们其实要比较的就是 x_3, x_4哪一个退出基变量可以获得更大的x_2 ，其实比较的也就是\displaystyle\frac{b_i}{a_{i2}} 的值，即写在\theta 位置的值。(如果取较大的范围，那么就会出现不满足约束条件的情况)

在比较\displaystyle\frac{b_i}{a_{i2}} 的值的时候，需要注意的是只对a_{ij} 大于0的值进行考虑，小于零的值不作为出基变量的参考依据，或者说

对应的基变量不会出基。

接着为了能够利用同样的方法进行比较，我们需要对原来的单纯形表通过行变换获得新的单纯形表，新的单纯形表应该以 x_2, x_3作为基变量，具体进行的行变换是将原来的单纯形表中第三行的值乘以\frac{1}{3} , 然后通过行变换将第一个行x_2

列的值化为0，并将\lambda 行x_2 列的值化为0，这个时候再看\lambda 是否存在大于零的值，如果仍存在大于零的值，则需要进一步进行调整基变量:

\begin{array}{|c|c|c|c|c|c|c|} \hline X_{B} & x_{1} & x_{2} & x_{3} & x_{4} & b & \theta_{i} \\ \hline x_{3} & 5 / 3 & 0 & 1 & -1 / 3 & 30 & 18 \\ \hline x_{2} & 1 / 3 & 1 & 0 & 1 / 3 & 10 & 30 \\ \hline \lambda_{j} & 5 / 3 & 0 & 0 & -4 / 3 & & \\ \hline \end{array}

再继续进行:

\begin{array}{|c|c|c|c|c|c|c|} \hline X_{B} & x_{1} & x_{2} & x_{3} & x_{4} & b & \theta_{i} \\ \hline x_{1} & 1 & 0 & 3 / 5 & -1 / 5 & 18 & \\ \hline x_{2} & 0 & 1 & -1 / 5 & -2 / 5 & 4 & \\ \hline \lambda_{j} & 0 & 0 & -1 & -1 & & \\ \hline \end{array}