↓Skip to main content
  1. Posts/

线性规划

·2 mins·
Table of Contents

#线性规划

定义 #

线性规划指目标函数和约束条件均为线性的优化问题.

数学模型 #

模型特点:包含决策变量,目标函数以及约束条件.

  • 决策变量:$(x_1,…,x_n)$,是决策人要考虑和控制的因素;
  • 目标函数:$z=f(x_1,…,x_n)$,线性形式，通常求$z$的极大或极小值.
  • 约束条件:线性等式或不等式 线性规划数学模型的一般形式: $$ max(或min)\ z=c_1x_1+c_2x_2+…+c_nx_n\ s.t. \begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\leq(=,\geq)b_1\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\leq(=,\geq)b_2\ \qquad\qquad\qquad……\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\leq(=,\geq)b_m\ \end{cases} $$ 亦即: $$ max(或min)\ z= \sum_{i=1}^{n} c_ix_i\ s.t. \begin{cases} \sum_{j=1}^{n} a_{ij}x_i\leq(=,\geq)b_i,i=1,2,…,m\ x_j\geq 0,j=1,2,…,n \end{cases} $$

数学模型隐含的假设:

  • 比例性： 决策变量变化引起目标的改变量与决策变量改变量成正比.
  • 可加性： 每个决策变量对目标和约束的影响独立于其它变量.
  • 连续性： 每个决策变量取连续值.
  • 确定性： 线性规划中的参数$a_{ij}$,$b_i$,$c_i$为确定值.

建模步骤 #

三步走:

  • 需要做哪些决策?$\longrightarrow$确定决策变量
  • 问题的目标是什么?$\longrightarrow$写出目标函数
  • 资源和需求之间的情况如何?$\longrightarrow$确定约束条件

线性规划的标准型 #

$$ max\ z=c_1x_1+c_2x_2+…+c_nx_n\ s.t. \begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n=b_1\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n=b_2\ \qquad\qquad\qquad……\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n=b_m\ \end{cases} $$ 亦即: $$ max\ z=CX\ s.t. \begin{cases} AX=b\ X\geq0 \end{cases} $$

对一般的线性规划模型,我们通过添加松弛变量让其变为标准型.

线性规划求解:图解法 #

对于决策变量$x_1$,$x_2$,以$x_1$,$x_2$为坐标轴建立平面直角坐标系,依靠约束条件画出可行域,寻找$z=CX$所构成的直线族中满足题意的直线.

  • 优点:简单、直观，便于了解线性规划基本原理和几何意义;
  • 缺点:只能用来求解两个决策变量的问题.

线性规划的启示:

  • 可行域： 由约束平面围起来的凸多边形区域，可行域内每一个点代表一个可行解 如果可行域非空，那么它一定是一个凸集。
  • 最优解： 总是在可行域的边界上，一般由可行域的极点（顶点）表示。 积极(紧)与非积极(非紧)约束： 在最优解处满足等式的约束为积极(紧)约束； 在最优解处满足严格不等式的约束为非积极(非紧)约束。
  • 特殊情形： 如果可行域为空集，线性规划问题无可行解； 如果目标函数等值线可以无限地在可行域内向改善的方向移动，线性规划问题无界； 线性规划问题可能存在无穷多个最优解。

线性规划求解:单纯形法 #

在单纯形法之前:一些基本概念与定理 #

考虑线性规划问题: $$ max\ z=CX\ s.t. \begin{cases} AX=b\ X\geq0 \end{cases} $$

  • 基,基向量,基变量: $B$是矩阵$A$中的一个$m×m$阶的满秩子矩阵，称为线性规划问题的一个基. $B$中的每一个列向量$P_j$为基向量: $$ \begin{cases} A=(P_1\ …\ P_m\ \ P_{m+1}\ …\ P_n)=(B,N)\ \quad\quad\quad基向量\quad非基向量\quad\quad \end{cases} $$ 对应的$x_j$为基变量: $$ \begin{cases} X=(x_1\ …\ x_m\ \ x_{m+1}\ …\ x_n)^T=(X_B,X_N)^T\ \quad\quad\quad基变量\quad非基变量\quad\quad\quad\quad \end{cases} $$
  • 基解,基可行解,可行基
    求解$AX=b$可得:$X_B=B^{-1}b-B^{-1}NX_N$. 对应于基$B$,$X=(B^{-1}b,0)^{T}$为$AX=b$的一个基解. 满足变量非负约束(即$B^{-1}b\geq0$)的基解称为基可行解,对应的基$B$称为可行基.

注意:

  • 基解中最多有$m$个非零分量
  • 基解的数目不超过$C_n^m$
  • 凸集: 如果集合$D$中任意两点$X_1$和$X_2$,其连线上的所有点也都是集合$D$中的点，称$D$为凸集.(即对任何$X_1,X_2\in D$和$0\leq a\leq 1$,有$X=aX_1 +(1-a)X_2\in D$)
  • 凸组合: $X_1,X_2,…,X_k$是$n$维欧氏空间中的$k$个点,若有一组数$\mu_1,\mu_2,…,\mu_k$ 满足 $0\leq\mu_i\leq 1$ ($i=1,…,k $),且 $\sum_{i=1}^{k}\mu_i=1$ ,那么 $X=\sum_{i=1}^k\mu_iX_i$ 是点$X_1,X_2,…,X_k$ 的凸组合
  • 顶点: 凸集 $D$ ,点 $X\in D$ ,若找不到两个不同的点 $X_1,X_2\in D$ ,使得 $X=aX_1+(1-a)X_2,0<a<1$ ,则称$X$为$D$的顶点.
  • 定理1: 如果LP问题存在可行解,那么其可行域一定是凸集.
  • 引理1: $D$为有界凸多面集,$X\in D$,$X$必可表示为$D$的顶点的凸组合.
  • 定理2: 如果LP问题的可行域有界,则其最优值必可在顶点处获得.
  • 引理2: LP问题的可行解$X$是基可行解的充分必要条件是:$X$的非$0$分量对应的系数列向量线性无关.
  • 定理3: LP问题的基可行解$X$对应可行域的顶点.

单纯形法 #

基本思路:先找出一个基可行解，判断是否为最优，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，直到找到最优解为止. 考虑线性规划问题: $$ max\ z=CX\ s.t. \begin{cases} AX=b\ X\geq0 \end{cases} $$ 设 $A=(I,N)$ ,令 $B=I$ ,则有 $$ x_i=b_i-\sum_{j=m+1}^na_{ij}x_j,i=1,2,…,m $$ 带入$z=CX$中,有 $$ z=\sum_{i=1}^{m}c_ib_i+\sum_{j=m+1}^n(c_j-\sum_{i=1}^mc_ia_{ij})x_j $$ 当 $x_j=0,j=m+1,…,n$ 时, $$ \begin{cases} X^{(1)}=(b_1,…,b_m,0,…,0)^{T}(初始基可行解)\ z^{(1)}= \sum_{i=1}^mc_ib_i(对应目标函数值) \end{cases} $$ 记 $\lambda_j = c_j-\sum_{i=1}^mc_ia_{ij},j=m+1,…,n$ ,称 $\lambda_j$ 为检验数.

  • 定理4: 对解 $X^{(1)}$ ,若检验数 $\lambda _j,j=m+1,…,n$全部$\leq0$ ,则 $X^{(1)}$ 为最优解.
  • 定理5: 对解 $X^{(1)}$ ,若有某个非基变量 $x_{m+k}$ 对应的 $\lambda_{m+k}>0$ ,而且相应的 $P_{m+k} = (a_{1(m+k)},…,a_{m(m+k)})^{T}\leq0$ ,则原问题无有界最优解. 若不符合上两种情况,则需要进行换基迭代. ①决定换入变量: 若 $max_{\lambda_j>0}\lambda_j=\lambda_{m+k}$ ,则 $x_{m+k}$ 为换入变量. ②决定换出变量: 若 $\theta =min{\frac{b_i}{a_{i(m+k)}}|a_{i(m+k)}>0} = \frac{b_r}{a_{r(m+k)}}$ ,则 $x_r$ 为换出变量.
  • 定理6 经单纯形法换基迭代获得的新解 $$ X^{(2)}=(b_1-\theta a_{1(m+k)},…,b_m-\theta a_{m(m+k)},0,…,\theta,…,0)^{T}$$ 是基可行解,且满足$z^{(2)}>z^{(1)}$.

单纯形法基础步骤: ①确定初始基,初始基可行解; ②检查非基变量检验数 $\lambda_j$是否全部 $\leq0$,若是,则已求得最优解;否则继续下一步; ③若有 $\lambda_k>0$, $P_k$全部 $\leq0$,则停止,该问题没有有界最优解;否则继续下一步; ④根据最大非负检验书 $\lambda_j$确定换入变量$x_{m+k}$,根据最小 $\theta$值确定换出变量 $x_r$; ⑤以$a_{r(m+k)}$为中心进行换基迭代,之后转第②步. 单纯形法的求解过程可以在单纯形表上进行.

单纯形法进阶 #

有时标准形式无法直接找到一组初始基可行解,这时候运用单纯形法需要引进人工变量.

  • 大M法 引进人工变量 $x_p$,…,$x_q$,同时修改 $z^{*}=z-\sum_{i=p}^{q}Mx_i$,其中$M$为很大的数,这样做使得取最优解时人工变量值必须为$0$.
  • 两阶段法 一阶段:引进人工变量$x_p$,…,$x_q$,同时修改 $z^{*}=-\sum_{i=p}^{q}x_i$.解决一阶段优化问题后,$x_p$,…,$x_q$取值均为$0$; 二阶段:在一阶段的最终单纯形表中,修改$z$为初始标准型问题的目标函数,在新的单纯形表中解决原问题.

    人工变量不能完全出基时,原问题无可行解.

↑