线性规划和单纯形法

文章发布时间:

2023-05-15

最后更新时间:

2023-06-03

1.线性规划问题及数学模型

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

一些概念

CPF:corner-point feasible 角点可行解
可行解、非可行解
目标函数、约束函数
松弛变量（slack variables）

问题形式

一般形式

\[\begin{array}{c} \max (\min ) z=\sum_{j=1}^{\mathrm{n}} c_{\mathrm{j}} x_{j} \\ \text { s.t. }\left\{\begin{array}{l} \sum_{j=1}^{\mathrm{n}} \mathrm{a}_{\mathrm{ij}} \mathrm{x}_{\mathrm{j}} \leq(=, \geq) b_{i}(i=1,2, \ldots, m) \\ x_{\mathrm{j}} \geq 0 \qquad(j=1,2, \ldots, n) \end{array} \right. \end{array}\] ### 矩阵形式 \[\begin{array}{r} m \alpha x(\min ) z=C X \\ \text { s.t. }\left\{\begin{array}{l} A X \leq(=, \geq) b \\ X \geq 0 \end{array}\right. \end{array}\] ## 线性规划的标准化原因:在求解模型时，需要将数学语言转化为机器语言（任意一条语句都有明确且唯一的意义)，这涉及到一个转化的过程，即标准化。 ### 线性规划模型的标准形式 \[\begin{array}{c} \max z=\sum_{j=1}^{\mathrm{n}} c_{\mathrm{j}} x_{j} \\ \text { s.t. }\left\{\begin{array}{l} \sum_{j=1}^{\mathrm{n}} \mathrm{a}_{\mathrm{ij}} \mathrm{x}_{\mathrm{j}} = b_{i}\ (i=1,2, \ldots, m) \\ x_{\mathrm{j}} \geq 0 \qquad\qquad(j=1,2, \ldots, n) \end{array} \right. \end{array}\]

目标函数最大(max)
约束条件为等式
资源限量非负
决策向量非负

非标准形式可以转化为标准形式: - min ---> max :取相反数 - 不等式 ---> 等式:加减非负变量 - 决策变量无约束: 转化成两非负向量的差

有关线性规划的假设

比例性

假设针对对象:目标函数和约束函数
内容:一个活动的贡献值与这个活动级别成比例,或者说方程中不会出现二次及其以上次数的项

可加性

对象:模型中的每一个函数
内容:就是假设每个函数中不会出现交叉项,或者说不同活动做的贡献不是简单的相加关系

可分性

对象:决策变量
内容:感觉就是说假设决策变量是实数域上的连续函数

确定性

对象:模型参数
内容:模型中的参数假设为已知常量
注意:实际应用中,确定性假设很少完全满足,使用的参数值可能是将来条件的一种预期,不可避免地带有一定程度的不确定性。出于这一原因,在假设的参数下确定的最优解被找到后,通常要进行灵敏度分析(sensitivity analysis)。目的之一是识别灵敏度参数(该参数的改变必然导致最优解的变化),因为灵敏度参数值的变化需要立即去改变正在使用的解。

正确地假设(assumption in perspective)

感觉中文译本中这个标题（‘前景假设’）翻译的不好. 这一节是想告诉读者假设有时候并不会全都满足,但是我们可以通过其他的方式进行弥补.如:不满足确定性假设时,我们为此对灵敏度参数进行了灵敏度分析,这就是对不满足假设时的弥补.

当四个假设中某个不满足时,要怎么处理问题.

图解法

图解法可以解决具有两个变量的任何线性规划问题。在增加一些难度的情况下,可以对它进行扩展来解决三个变量但不能多于三个变量的问题(下一章我们将研究用单纯形法解决较大规模的问题)。

运筹学求解软件包

lingo/lindo
excel solver
mpl cplex

2.线性规划几何意义

图解法

(画个表格) 图解法难以解决高维问题。

解的情况

唯一
无穷多
无界解（可行域不封闭、无界）
无解（没有可行域）

出现后两者就有可能是数学建模出现了问题，如缺乏必要的约束条件、出现矛盾的约束条件。

3.解的概念

4.单纯形法原理

基本概念

凸集（通俗版本）集合中任意两点的连线仍在集合中。

（严格定义）设n维度欧式空间中点集\(\mathbb{K}\)，\(X_1,X_2\)为集合中任意两点，若对任意实数\(\alpha\in [0,1]\)，满足： \[ \alpha X_1+(1-\alpha)X_2\in\mathbb{K} \] 则称该集合\(\mathbb{K}\)为凸集。

凸组合 设n维度欧式空间中点集\(\mathbb{K}\)，\(X_1,\cdots,X_k\)为集合中任意\(k\)个点，若存在\(k\)个实数\(0\leq\alpha_i\leq 1,i=1,\cdots,k\)并且\(\sum_{i=1}^{k}\alpha_i =1\)，满足： \[ X=\sum_{i=1}^{k}\alpha_i X_i \] 则称\(X\)为\(X_1,\cdots,X_k\)的凸组合。\(0 <\alpha_i< 1,i=1\)，称为严格凸组合。

顶点设\(\mathbb{K}\)凸集，\(X\in\mathbb{K}\),如果\(X\)不能用\(\mathbb{K}\)中不同两点的严格凸组合表示，则称\(X\)为\(\mathbb{K}\)的一个顶点。

也即，对\(0 <\alpha< 1\)有， \[ X\neq \alpha X_1+(1-\alpha)X_2,\forall X_1,X_2\in\mathbb{K},X_1\neq X_2 \] ## 前置定理

定理1（线性规划问题的可行域为凸集）若线性规划问题存在可行域， \[ D=\{\textbf{X}\vert \sum_{i=1}^{n}\textbf{P}_ix_i=\textbf{b},x_i\geq 0\} \] 是凸集。（小写的x代表\(X\)的分量）

proof 设\(X_1,X_2\)为\(D\)中任意两个相异的点，\(A\)是以\(P_i\)为行向量的矩阵。则有， \[ AX_1=b,AX_2=b \] 于是，两点连线上任意一点\(X\)满足， \[ \begin{align*} AX=& A(\alpha X_1+(1-\alpha)X_2)\\ =&\alpha AX_1+AX_2-\alpha AX_2\in\mathbb{K}\\ =& \alpha b+b-\alpha b\\ =& b \end{align*} \] 故\(X\in D\)，\(D\)凸集。

定理2 若\(\mathbb{K}\)为有界凸集，则集合内任意一点可以表示为\(\mathbb{K}\)的顶点的凸组合。

proof 对于二维的情况比较形象。已知三角形为有界凸集。任何有界凸集可以用凸多边形逼近，而任意凸多边形可以划分成可数个三角形。承认上诉逻辑，我们只需要证明：三角形的任意一点可以用顶点的凸组合表出。

设\(X_1,X_2,X_3\)为三角形的三个顶点。\(X\)为三角形内任意一点。若\(X\)在三条边上（即落在任意两个顶点的连线上），由凸集定义显然有顶点的凸组合表示。若不在三条边上，做过\(X\)与\(X_1\)的射线交另外两点的连线于\(X'\)，于是有， \[ X'=\alpha X_2+(1-\alpha)X_3 \] \[ X=\lambda X'+(1-\lambda)X_1 \] \[ \lambda,\alpha\in(0,1) \] 代入即得， \[ X=(1-\lambda)X_1+\lambda\alpha X_2+\lambda(1-\alpha)X_3 \] 将三个系数相加不难发现和为\(1\)。至此，我们得到了\(X\)用顶点的凸组合的表示。

但是对于二维以上的情形，就没有这么直观了，我们需要将三角形换成所谓的“单纯形”。

单纯形是二维的三角形，三维的四面体，在任意维度的推广。n-维单纯形是一个有 n+1 个顶点，n+1 个面 (facet) 的多面体。这个词译自英语 simplex，「单纯」其实意味着基本，因为他是组成更复杂结构（复形 complex）的基本构件。

迭代定理

整个迭代过程的基本思想是:先寻找到初始基可行解，然后判断其是否最优、非最优，寻找到单位变动能创造更大收益的非基变量作为入基变量，然后确定入基变量变动后最先因资源受限而降为0的基变量作为出基变量，通过换基得到一个更接近最优值的解，不断重复，直到目标函数取到最优。 # 5.单纯形法的计算步骤 ## 单纯形法的计算步骤 ### 寻找初始基可行解

最优性检验&入基变量选取

由迭代原理可知，基变量对应的检验数必为0，非基变量则存在如下几种情况: 1. 所有非基变量的检验数均小于0，代表达到最优，任何变动都会使得目标值往更小的方向变化。 2. 部分非基变量的检验数小于0，其余非基变量的检验数等于0。代表已经达到最优，但存在部分约束，它们的变动并不会导致目标函数值发生变化，即模型存在无穷多最优解。 3. 部分非基变量的检验数大于0，代表现有的生产组合并没有达到最优，存在部分约束，它们的变动能使目标函数值往更大的方向变化，根据单纯形法，选择单位变动使目标函数值变化量最大的变量作为入基变量。

出基变量选取

emmm

### 换基&更新单纯形表

单纯形法的变形

大M法(人工变量法)

考虑如下线性规划问题: \[ \begin{array}{c} \max z=-3 x_{1}+x_{3} \\ \text { s.t. }\left\{\begin{array}{r} x_{1}+x_{2}+x_{3} \leq 4 \\ -2 x_{1}+x_{2}-x_{3} \geq 1 \\ 3 x_{2}+x_{3}=9 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array}\right. \end{array} \] 化为标准形式: \[ \max z=-3 x_{1}+0 x_{2}+x_{3}+0 x_{4}+0 x_{5} \] \[ \text { s.t. }\left\{\begin{array}{r} x_{1}+x_{2}+x_{3}+x_{4}=4 \\ -2 x_{1}+x_{2}-x_{3}-x_{5}=1 \\ 3 x_{2}+x_{3}=9 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0 \end{array}\right. \] 有时我们并不能很方便地找出一组基来，为了更好地找到初始基，我们需要引入人工变量来构造一组基。 \[ \mathbf{A}=\left(\begin{array}{ccccc} 1 & 1 & 1 & 1 & 0 \\ -2 & 1 & -1 & 0 & -1 \\ 0 & 3 & 1 & 0 & 0 \end{array}\right), \quad \mathbf{b}=\left(\begin{array}{l} 4 \\ 1 \\ 9 \end{array}\right) \] 人工变量法的目的是为了构造一组基，原模型中只有一个单位列向量，但基的秩为 3 ，即应找到三个单位列向量，由此我们引入人工变量 \(x_{6}\) 和 \(x_{7}\) 。由于这是我们人工引入 (实际上并不存在的产品)，我们需要控制它最终的值只能为 0 ，所以在目标函数中，它的价值系数为 \(-M\) (其中 \(M\) 是个足够大的数，并假设其能参与运算)，代表它每生产一件，都会导致目标函数变得足够小，由此，新的模型标准式为: \[ \begin{array}{c} \max z=-3 x_{1}+0 x_{2}+x_{3}+0 x_{4}+0 x_{5}-M x_{6}-M x_{7} \\ \text { s.t. }\left\{\begin{array}{c} x_{1}+x_{2}+x_{3}+x_{4}=4 \\ -2 x_{1}+x_{2}-x_{3}-x_{5}+x_{6}=1 \\ 3 x_{2}+x_{3}+x_{7}=9 \\ x_{j} \geq 0(j=1,2, \ldots, 7) \end{array}\right. \end{array} \]

由于人工变量是我们构建的，实际并不存在，所以要求它最终取值为0，若是单纯形表迭代到所有非基变量检验数均小于0，但基变量中含非0的人工变量时，说明该线性规划问题无解。

两阶段法

模型求解的过程一般都靠计算机完成，需要将数学语言转化为含义明确唯一的程序语言，使用人工变量法虽然可以帮助寻找初始基，但M这个足够大的数含义并非明确，在不同问题中，“足够”有不同的衡量标准，为此我们引入两阶段法。其基本思路是将添加人工变量后的线性规划问题拆分成两个阶段:

第一阶段:求解一个目标函数只包含人工变量的线性规划问题，在决策变量非负的约束条件下，人工变量只有取0才能取到最小值，此时的最优解即原问题的一个基可行解。
第二阶段:回归原问题，并用第一阶段最后的基为初始基，对原问题用单纯形法迭代。

还是以上一道题为例 \[ \max z=-3 x_{1}+0 x_{2}+x_{3}+0 x_{4}+0 x_{5} \] \[ \text { s.t. }\left\{\begin{array}{r} x_{1}+x_{2}+x_{3}+x_{4}=4 \\ -2 x_{1}+x_{2}-x_{3}-x_{5}=1 \\ 3 x_{2}+x_{3}=9 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0 \end{array}\right. \] 第一阶段：加入人工变量 \(x_{6}\) 和 \(x_{7}\) ，构建目标函数只包含人工变量的模型: \[ \max z= 0 x_{1}+0 x_{2}+0 x_{3}+0 x_{4}+0 x_{5}-x_{6}-x_{7} \] \[ \text { s.t. }\left\{\begin{array}{r} x_{1}+x_{2}+x_{3}+x_{4}=4 \\ -2 x_{1}+x_{2}-x_{3}-x_{5}=1 \\ 3 x_{2}+x_{3}=9 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} \geq 0 \end{array}\right. \]

第二阶段：第一阶段最后的基为初始基，对原问题用单纯形法迭代。

若第一阶段迭代最终结果中的基变量仍含有非0的人工变量，即目标函数值不为0，则说明问题无解。

单纯形法的其他讨论

一些可能出现的情况

目标函数极小值时解的最优性判别根据单纯形法的迭代原理，在目标函数取极小值时，只需确保所有检验数大于0即可保证最优。
退化按最大检验数和最小比值\(\theta\)确定入基变量和出基变量时，有时会存在两个及以上相同的最大或最小值，从而使得下个表中的基可行解中出现一个或多个基变量等于0的退化解(模型中存在多余约束，使得多个基可行解对应同一顶点)，进而可能导致迭代计算陷入循环，为避免重复的运算，规定:存在多个检验数大于0取得相同最大值时，始终取下标值最小(或最大)的变量作为入基变量;存在多个\(\theta\)出现相同最小比值，始终取下标值最小(或最大)的变量作为出基变量。
无可行解的判别从人工变量法和两阶段法的计算步骤中可以看出，当求解结果出现所有检验数均小于等于0，但基变量中仍存在非零的人工变量(两阶段法第一阶段目标函数值不为0)时，表明问题无可行解，即人工变量最终求解结果必须为0.

修正单纯形法 (求解过程的优化)

单纯形法的矩阵描述

主要是对换基过程的优化，把求逆过程优化，直接在单纯形表上操作。不严格地说，其实就是把求逆换成初等行变换。 emmm

≡