大家好，欢迎来到IT知识分享网。

前言

因为管理运筹学老师，一看就不太好惹的样子，感觉期末考试要是不按她的要求来肯定分不高。记录一下吧

模型建立要求

线性规划问题数学模型的一般表达形式

解的情况

线性规划问题的可行解的集合（可行域）是凸集。
凸集的极点（顶点）的个数是有限的。
最优解如果存在只可能再凸集的顶点上取得，而不可能发生再凸集得内部。
线性规划问题的解得可能是：唯一解、无穷多最优解、无界解和无可行解。

约束条件中常数项的灵敏度分析

影子价格

约束条件的常数项中每增加一个单位使得最优目标函数值增加的数量称之为约束条件的影子价格。

对偶价格

约束条件的常数项中每增加一个单位而使最优目标函数值得到改进的数量称之为这个约束条件的对偶价格。

松约束

当目标函数取到最优解时，对应资源使用量<对应资源约束量。
简单来说就是资源有的多，用不完。

紧约束

当目标函数取到最优解时，对应资源使用量=对应资源的约束量
简单来说就是，这个资源用的刚刚好，可以理解为最优解由短板来决定。

小结

当目标函数求最大时，增加的数量就是改进的数量，所以影子价格=对偶价格。
当目标函数求最小时，影子价格= – 对偶价格。
当约束条件常数项增加一个单位时，有：
1.如果对偶价格大于0，则齐最有目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时，最优目标函数值变得更小。
2.如果对偶价格小于0，则其最优目标函数数值变坏，即求最大值时，最优目标函数值变更小了，求最小值时，最优目标函数值变得更大了。
3.如果对偶价格=0，则其最目标函数不变。

线性规划模型的标准形式

1.约束条件右端常数项非负。
2.约束条件全部为等号约束。
3.所有变量全都是非负的。

单纯形法

基本思路和原理

引例

基

基向量

非基向量

因此基向量和非基向量并不是绝对的，而是相对的。

基变量

非基变量

基本解

基本可行解、可行基

基本最优解、最优基

使目标函数达到最优的基本可行解称为基本最优解，其对应的基称为最优基。

退化的基本解、退化的基本可行解、退化的基本最优解

基中的某些基变量为0

小结

表格求解法

看一道例题：
max z = 10x₁ + 5x₂
s.t.: 3x₁ + 4x₂ <= 9
5x₁ + 2x₂ <= 8
x_i(i=1,2) >= 0

化成标准型

首先要化成标准型如下：
max z = 10x₁ + 5x₂ + 0x₃ + 0x₄
s.t.: 3x₁ + 4x₂ + x₃ = 9
5x₁ + 2x₂ + x₄ = 8
x_i(i=1,2,3,4)>=0

列出初始表

由于基本可行解中，非基变量都为0，那么我们当选择对角线矩阵作为基变量时，就能够轻而易举地得出可行解了。这里，我们可以选择x₃ 、x₄的列作为基变量，因为是对角线矩阵，因此出初始表格：

其中C代表价值系数、X代表产品类、b代表约条件右边的值（资源拥有量）、Cb、Xb表示选择为基向量的对应变量的名称。

这样我们能够轻易求的基可行解为X1=0，X2=0、X3=9、X4=8（非基变量都为0，基变量就为b）

选择换入基

因为单纯型法是通过类似枚举获得最优解，但是单纯的枚举变量多了运算量增长太快，因此，单纯形法采用逐步逼近的思路进行搜索，选择当前解的“临近解”来继续搜索，如果“临近解”优于当前解，则继续搜索，如果没有，说明当前解就是为最优解。

“临近解”的定义：基可行解中换一组基变量所得出的基可行解。

那么我们就需要先选择换出基，再选择换入基，最后进行对换，然后迭代，就能得到最优解了。

选择换成基就是看检验数σj的值，其计算方法为Cj – Cb b^T

例如σ1 = 10 – 03 – 08 = 10
以此类推，得出检验数：

基变量的检验数肯定是为0的，检验数可以理解为生产某产品的所获得的单位价值，检验数越大，说明这个产品越优先生产就越好。

从表中看出X1产品检验数最高，为10故选择X1为换入基。

选择换出基

因为基向量和非基向量是相对的，有想换入的，那么就得选择一个换出基来进行对换，因为基向量的个数是固定的。

因此使用θi来进行换出基的选择。

θi = b / 换入基对应的值
例如θ1 = 9 / 3 = 3
以此类推，那么我们得到：

因为基可行解都是>=0的，因此我们这里应该选择θ最小的作为换出基，这样可以保证解都>=0。
值得注意的是，只有θ>0的时候才允许进行对换

这样我们就选择X4作为换出基。

对换基

选择好了换入基和换出基，我们就能够进行基的对换，从而得到接近最优解的解。
值得注意的是，我们同时需要满足换入的基能够和原来的基向量组成对角线矩阵（这里即为X1:01、X3:10），这样才能方便我们求出基可行解。

将X1右边一行同除以5（矩阵的初等变化可以得到）：

然后同样，X3 – 3*X1得到：

（这里-3/5因为是负的所有可以直接不用写，肯定不会选他）
化成了我们需要的形式。

迭代

那我们可以继续计算σj和θ
得：

需要继续，选择X2和X3对换。
最后计算得到：

计算到这，就可以停止了，因为此时σ都小于等于0，说明没有基换入会改善当前的解，因此当前的解就是最优解了。

单纯形法解情况的判断

唯一最优解

（1）当所有非基变量的检验数都<0时
（2）当所有非基变量的检验数都<=0时且存在某个非基变量Xj的检验数为0，而他它所对应的系数Pj全部<=0
满足以上任意之一都算。

无界解

当存在某个非0变量的检验数>0且它所对应的系数Pj全部<=0

无穷多最优解

当所有非基变量的检验数都<=0且存在某个非基变量的Xj的检验数位0，而它所对应的系数Pj不全<=0(即存在>0系数)

无可行解

当我们遇到约束条件列表不能直接抽取出单位矩阵的时候，我们就需要引入人工变量来帮助我们制造出单位矩阵，辅助求解。

大M法

使用大M法，我们可以构造出加入人工变量后的目标函数，即原函数上 -M*每个人工变量，这里M取无穷大，说明如果人工变量不为0，就是无解的情况，换句话说，当单纯形法计算到最后结果的时候，发现人工变量并未被换出，并且其基变量不为0，那么说明此问题无解。
例题如下：

因为所有非基变量都<=0了，无法继续迭代了，说明到最后一步了，但是人工变量仍在里面，说明此问题无可行解。

二阶段法

顾名思义，分两个阶段来计算。第一阶段用来判断是否有可行解。
如果没有直接结束。
如果有则进入第二阶段。
第二阶段就是继续求解。
二阶段法第一阶段，需要自己设定人工变量的目标函数，然后进行正常的单纯形法求解，如果最后发现人工变量未被换出，说明无可行解，求解就结束了。
人工变量目标函数= -（各个人工变量）

例题:

这里求解当所有非基变量都小于0的时候，求解结束，发现有人工变量未被换出，说明此问题无解。

如果全部被换出，那么进入第二阶段，值得注意的是，进入第二阶段时，关于人工变量的列都可以划去，不进行计算（好不容易换出来了，就别让它进去了）。

当人工变量作为基变量，但是基变量为0的话，原方程仍然有解且说明此约束条件是与其他约束条件线性相关的，简单来说就是这个约束条件被包括在了别的约束条件里，直接去掉这个约束条件能够得出一模一样的解。

对偶单纯形法

当我们在约束条件中无法直接找到一个单位矩阵，但是通过某几个约束条件符号的变换，能够找到单位矩阵，并且原问题是求最小值，我们可以尝试使用对偶单纯形法来求解。

例如上图，我们通过符号的变化，得出了有单位矩阵的不那么标准（等号右边允许存在小于0）的标准型

接下来我们类似的列单纯形法表格：

对偶单纯形法，需要先找进基变量再找离基变量（和单纯形法想法），我们可以看到b的那列存在负值，对偶单纯型法就是需要将这列搞成正的，就说明原问题有最优解了。

这里首先寻找b最小的作为离基变量，这里-5最小，说明x₄是离基变量。

然后寻找进基变量，首先计算检验数σ_j
注意，开局只有当所有非基变量检验数全都<=0才能够继续使用对偶单纯形法，否则就只能使用大M或者二阶段法来求解了。

然后算比值θ：σ_j的各个元素（x₁到x₅对应的列）除以x₄的对应的各个元素。
找出比值最小的（但是要大于0的）作为进基变量，比值相同选择下标最小的就行了

然后进行对换，接下来的操作和单纯形法一样。

无可行解的情况

简单来说，就是不能整成b都大于0的时候，就是无可行解了。

最后一步发现所有的b都大于等于0了，说明已经找到最优解了。

小结

对偶单纯形法适用于以下表达式类型

单纯形法和对偶单纯形法的对比

单纯形法最优解判断标准及实例练习

b都大于等于0，存在非基变量大于0且其P_j全都小于等于0

人工变量还在里面，所有是无可行解

b都>=0且没人工变量，其非基变量<0所有有唯一最优解。

所有非基变量都<=0，说明有最优解，因为b都>=0,存在一个非基变量=0，且P_j存在>0的，说明还可以进行换基，得到一个新的最优解，因此说明有无穷多最优解。

有人工变量，但是基变量为0，不影响，所以是最优解。

b都大于等于0，所有非基变量都小于0，有唯一最优解。

看得出来，b=-6换不出来，所以无可行解。

灵敏度分析

需要进行灵敏度的分析之前需要先了解一下单纯形法表格的一些性质：

可以简单理解为，最终单纯性表格和最初的单纯性表格就差了个B的逆矩阵

我们可以看个例子检验一下：

其中:
b = (8，12，36)^T
I =
0 0 1
0 1 0
1 0 0

B(最终基变量的原始值) =
1 0 1
0 2 0
0 4 3

X_S = X₃ X₄ X₅
B^-1(原始基变量对应终表中的值)=
1 2/3 -1/3
0 1/2 0
0 -2/3 1/3

X_B = X₃ X₂ X₁
C_B=(0, 3, 5)

B^-1b = (4，6，4）^T
BB^-1 =
1 0 0
0 1 0
0 0 1 = I

-C^BB^-1 = (0, -1/2, -1)

值得注意的是X_S是初始单纯形表的基变量（注意顺序）
X_B是最终单纯形表的基变量
X_N是未在初始表和终表为充当过基变量的非基变量。

单纯形表的灵敏度分析

灵敏度分析所研究的问题是，当某一规划的最优解已知的情况下，某数据发生变化后对最优解产生的影响。

原数据发生变化的主要原因可能有原数据不可靠或准确度不高，实际问题的条件模糊不清或被忽略，最优解执行一段时间后环境发生变化等。

因此，我们有必要研究一下问题：
1.当某些系数变化时，最优解改变多少？
2.当增加或减少变量时，最优解改变多少?
3.当增加或减少约束条件时，问题的最优解改变多少？
4.最优解不改变时，某些系数的允许变化范围又有多大？

系数包括：
目标函数中的价值系数c_j、约束条件中的常数项b_i、约束条件中的技术系数a_ij

灵敏度分析的基本步骤

1.将参数的改变直接通过计算反映到最终单纯形表上来
2.检查第三列（b列）是否全部>=0
3.检查检验数行是否全部<=0
4.按下标所列情况得出结论或决定继续计算的步骤

单纯形表灵敏度分析的主要内容

目标函数系数的灵敏度分析（价值系数）

从上图可知，当c改变时，直接带入计算检验数σ即可，根据计算结果来进一步判断即可。

约束条件的常数项的灵敏度分析（资源拥有量）

从上图可知，当b改变时，可以根据B^-1计算出终表新的b，然后进一步计算和判断即可。

增加或减少决策变量的灵敏度分析（增加或减少产品）

若增加决策变量x_k，当x_k没有出现在终表的基变量时，则p_k表示其资源消耗量（x_k那一列）
那么p_k^’ = B^-1p_k然后进一步计算判断即可。

若移除某个决策变量，如果是基变量，则任取一个符合条件的非基变量作为基变量进入替换，如果没有符合条件的，则引入人工变量，使用大M法。

稀疏矩阵的灵敏度分析（工艺系数或技术系数）

若改变决策变量x_k的资源消耗量，并且x_k在终表的基变量中，则一般进行重新计算。

增加或减少约束条件的灵敏度分析（增加或减少资源）

增加约束条件，可以将此约束条件放入终表，然后经过初等变换后变成符合条件的基变量，然后进行后续的运算和判断。

对偶问题

首先给出一个对偶问题的例子，可以先稍微观察一下区别和联系。

对称型线性规划问题

下面给出对称性线性规划问题的定义

结合开始的例子可以看一下，给的例子是对称性形式的。

那么如果不符合上述定义，就成为非对称性线性规划问题。

因此，如果有以下结论：
一个对称性线性规划问题的对偶问题也一定是对称性线性规划问题，反之，一个非对称线性规划问题的对偶问题也一定是非对称线性规划问题。

已知线性规划问题，写出其对偶问题

对称型线性规划问题

如果看出问题是对称性的线性规划问题，那么其对偶问题是比较好写的。
可以举个例子：

还是挺简单的。

非对称型线性规划问题

约束条件相反时

可见约束条件相反时，对应对偶变量的符号取反即可。

举个小例子：

约束条件取=号

可见，约束条件取=，那么对应的对偶变量正负不限。

举个例子：

决策变量符号取反或=（非对称）

可以看到，原问题决策变量的符号影响对偶问题约束条件的符号。

可以进一步看例子：

小结

其实只需要记住下面的话就行了。

从对称性线性规划出发，那个地方非对称，其对偶问题的地方就非对称，然后原问题的决策变量的符号影响对偶问题约束条件的符号，原问题的约束条件的符号，影响对偶问题约束条件的符号。

弱对偶性定理

就是说，min的问题是>=其对偶问题（max问题）反之max的问题是<=其对偶问题（min问题）。
看下面的图应该就能比较好理解了。

例题：

无界解情况

强对偶定理

互补松弛定理

例1

这样我们就能轻松算的y1^* = 1、y2^* = 1，其余都为0，求解完毕了。

例2

从最优解单纯性表中得到对偶问题的最优解

我们直接看例子：

可见检验数的相反数就是对偶问题的解。

判断原问题和对偶问题解的情况

影子价格在经营管理中的应用

（1）影子价格说明增加哪一种资源对增加经济效益最有力，三种资源的影子价格为（0，1，3），说明首先应考虑增加资源C，因为相比之下它能给收益带来的增加最大。
（2）影子价格与某一约束条件相对应
（3）影子价格又是一种机会成本，企业经营决策者可以把本企业资源的影子价格与当时资源的市场价格进行对比，当某种资源的影子价格高于市场价时，企业可以买进该种资源，因为资源带来的收益大于购买资源的费用。

求min型的单纯形法

就是检验数这块和max型单纯形法反过来。max是检验数都小于0才结束，min就是检验数都>0才结束。

平衡运输问题

找初始可行基

西北角法

最小元素法

最优的判别和计算方法

（）表示非基变量，没有运输，因此运输量为0

再看一个例子：

闭合回路调整就是选最小的检验数的格子为换出为起点然后四个角，+1，-1编号，取出-1里的格子里最小值，然后沿着回路*符号进行更新，更新完之后重新计算检验数，通过即可得到最优解。

产销不平衡的问题及其转化

课堂示例

整数规划模型的类型

指派问题及匈牙利法

标准形式的指派问题

直接求解即可。

例题2：



划去没打√的行以及打了勾的列，然后剩下的元素中选择出最小的，进行变换

非标准形式的指派问题

最大化的指派问题

人数与事数不等的指派问题

一个人可以做几件事的指派问题

copy这个人就行

某些事一定不难由某人做的指派问题

分支界限法

0-1规划的隐枚举法

动态规划

资源分配问题

例题：

背包问题

例题：

最短路问题

最小生成树

最大流问题

给出初始可行流

总结

最短路问题就是先从起点（起始标记点）找到周围未标记点的最短的路，然后将最短路的点标记，之后再从标记的点继续找最短路，一直标记到没了，得到的结果就是最短路径。

最小生成树的破圈法就是找个圈，去掉最大的边即可，直到没圈了就完成了。

最大流问题就是先确定初始0流，然后从弧最少的路径调整流量即可

最小费用最大流，先使用最短路径法找出费用最小的路径，然后调整流量计算出费用，然后循环往复即可。

知识点回顾

1.运筹学的英文名称是Operations Research或者Operational Research直译为作业研究
2.运筹学数学规划模型分为线性模型和非线性模型，其模型的建立包含三要素：决策变量、目标函数、约束条件
3.线性规划是运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较为成熟和应用上极为广泛的一个分支。
4.线性规划问题就是求一个线性目标函数在一组线性的约束条件下的极值问题。
5.求解线性规划问题最有效的方法是单纯形法。
6.满足所有约束条件的点的集合称为线性规划问题的可行域。
7.可行域中的每一点称为线性规划问题的可行解。
8.使目标函数达到最优的可行解称为线性规划问题的最优解
9.最优解的目标函数称为原问题的最优值。
10.线性规划问题的类型具有四种：唯一最优值、无穷多最优解、无界解和无可行解。
11.当目标函数的斜率和某个约束条件的斜率相等时，原问题可能具有无穷多最优解。
12.一个实际问题如果出现无界解说明建立的模型中可能某个约束条件没有考虑到。
13.一个实际问题中如果出现无可行解说明建立的模型中可能出现相互矛盾的约束条件。
14.运筹学就是求解满足所有约束条件使得目标函数达到最优的决策变量的值。
15.线性规划数学莫具有如下四种表示方式：一般形式、和式、矩阵形式、向量形式
16.最大化的目标函数种资源的影子价格等于它的对偶价格，最小化的目标函数中资源的影子价格就等于他的对偶价格的相反数。

参考

管理运筹学老师的课件
管理运筹学——韩伯棠