王树尧老师运筹学课程笔记 05 线性规划与单纯形法（概念、建模、标准型）

第5讲 线性规划与单纯形法（概念、建模、标准型）

线性规划问题及其数学模型

线性规划问题

定义：在线性约束条件下，寻找线性目标函数的最优化问题。

线性规划问题的共同特征

• 每一个问题都用一组决策变量$\left(x_1,x_2,\cdots ,x_n\right)$表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的。（如果实际要求变量不是连续的，那么先把变量当做连续的去求解，最后再进行讨论。）
• 要有建模的有关数据，如资源拥有量、消耗资源定额、创造新价值量等，并构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
• 都有一个要求达到的目标，它可用决策变量及其有关的价值系数构成的线性函数(称为目标函数)来表示。按问题的不同，要求目标函数实现最大化或最小化。

线性规划模型的标准型

之所以要将问题化为标准型，主要是为了便于之后使用单纯形等方法进行求解。

线性规划数学模型一般有如下形式：

目标函数 $\max (\min )z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$
满足约束条件 $\left\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n⩽(=,⩾)b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n⩽(=,⩾)b_2\\ ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n⩽(=,⩾)b_m\\ x_1,x_2,\cdots ,x_n⩾0\end{array}\right\}$

标准化的步骤：

1. 目标函数需要化为$max$。若原本的目标函数是$min$，则令$z^{{}^{\prime }}=-z$，然后求$max{z}^{{}^{\prime }}$。
2. 约束条件需要化为$=$。若原本的约束条件是$\le$，则约束条件变为原本的约束条件减去一个新的非负变量。若原本的约束条件是$\ge$，则约束条件变为原本的约束条件加上一个新的非负变量。
3. 变量需要化为$\ge 0$。若原本的变量是$=0$，则直接改为$\ge 0$，但实际上这种情况并不会出现，因为如果变量$=0$，那么改变量就不会在目标函数和约束条件中出现。若原本的变量是$\le 0$，则令$x_i^{{}^{\prime }}=-x_i$，并令$x_i^{{}^{\prime }}\ge 0$，同时目标函数和约束条件中进行替换。若原本的变量没有约束（$\in$R），则令$x_i=x_i^{{}^{\prime }}-x_i^{{}^{\prime \prime }}$，并令$x_i^{{}^{\prime }}\ge 0x_i^{{}^{\prime \prime }}\ge 0$，同时目标函数和约束条件中进行替换。

线性规划问题的处理流程

1. 数学建模。得到目标函数和约束条件。
2. 化标准型（详解上述标准化的3个步骤）。
3. 单纯形法求解。
4. 对于解的讨论。

补充说明

线性规划数学模型一般有如下形式：

目标函数 $\max (\min )z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$
满足约束条件 $\left\{\begin{array}{c}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n⩽(=,⩾)b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n⩽(=,⩾)b_2\\ ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n⩽(=,⩾)b_m\\ x_1,x_2,\cdots ,x_n⩾0\end{array}\right\}$

其中$c_i$为价值系数，$b_i$为限额系数，$a_{ij}$为技术系数。这些名称来源于生产问题，可以结合实际的生产问题加以理解。

一般情况下$m<n$，即方程个数$<$未知数个数。（也就是说求出的解是无穷多个的，KKT定理可能会失效。）

总结

线性规划问题是指，在线性约束条件下，寻找线性目标函数的最优化问题。

对于线性规划问题，可以按照KKT方法进行处理，更推荐的是先化为标准型然后再用单纯形法求解。