标题~
- 本系列文章主要用于笔者期末复习，行文混乱，请见谅
- 备考补充及零碎知识点
- 弱对偶定理
- 推论
- 最优性
- 强对偶定理
- 互补松弛性✨
- 证明过程(推荐看一看)
- 换言之:对偶变量和松弛变量的乘积为0
- 例子
- 应用
- 影子价格
- 定义
- 内涵
- 注意
- 问题
- 检验数的意义
- 问题
- 问题：什么是退化的最优解
- 对偶问题的引入
- 从另一个角度思考
- 总结
- 对偶问题的一般形式
- 原问题
- 对偶问题
- ✨以矩阵描述(更加直观)
- 多做题,就知道什么是对偶了
- 对称形式
- 非对称形式✨✨✨【一定要掌握】
- 规律
- 推导过程
- 复习单纯形法计算过程
- 举例说明
- 对偶单纯形法
- 单纯形法基本思路
- ❓问题：怎么（什么时候）添加人工变量
- ❓问题：有非零人工变量怎么办
- 对偶单纯形法基本思路
- 确定初始基解
- 问题 为什么对偶问题的最优性一直都是满足的
- 跟单纯形法的区别与联系✨✨
- 例题讲解✨✨🙌
- 注意看，对偶单纯形法的条件是min还是max【我看到的是min配合大于等于】
- 注意：对偶问题不需要用对偶表，看视频就好⚠️⚠️⚠️⚠️
- 下面的例题做法非考试正规做法！！但是求单纯形法规则是一样的
- 运输问题建模
- 产销平衡问题
- 建立模型
- 求解模型【表上作业法】
- 确定可行解方法①：左上角填充法
- 确定可行解方法②：最小元素法
- 确定可行解方法③：沃格尔法
- 迭代方法①：闭回路法
- 入基变量选择
- 出基变量选择
- 产销不平衡问题
- 产量大于销量
- 有转运的问题
- 产销不确定
听说运筹学这门课挺好的，有值得一听的必要；此篇用作课堂总结、期末复习及记录。
或许与教材内容会有很大程度重复。
本系列文章主要用于笔者期末复习，行文混乱，请见谅
本章开始会适当结合一些B站网课【运筹学】应试向基础教程
备考补充及零碎知识点
- 对偶问题的对偶问题就是原问题
- 矩阵表达
- 要弄清楚矩阵
A
A
A和
C
C
C分别是什么
- 最好记住这几个矩阵,进而记住弱对偶定理,松弛定理
弱对偶定理
结合着矩阵形式表述
推论
- 原问题最优解目标函数值是对偶问题目标函数值的下界，对偶问题最优解目标函数值是原问题目标函数值的上界。
对偶问题的解一定大于原问题的解
- 原问题有无界解→对偶问题无可行解，对偶问题有无界解→原问题无可行解，但逆不成立（对偶问题无可行解时，原问题也可能无可行解)
- 原问题有可行解而对偶问题无可行解→原问题为无界解，反之(对调"原问题"和"对偶问题")亦然
最优性
强对偶定理
互补松弛性✨
互补松弛性😦双最优解情况下）若原问题中某一约束条件对应的对偶变量( y i y_i yi)值为非零，则该约束条件取严格等式;若约束条件取严格不等式，则其对应的对偶变量一定为0，即:
- 若 y i > 0 y_{i}>\mathbf{0} yi>0 ，则有 ∑ j = 1 n a i j x j = b i \sum_{j=1}^{n} a_{i j} x_{j}=b_{i} ∑j=1naijxj=bi ， 即松弛变量值为 0
- 若
∑
j
=
1
n
a
i
j
x
j
<
b
i
\sum_{j=1}^{n} a_{i j} x_{j}
换言之:对偶变量和松弛变量的乘积为0
例子
本题中, y 1 y_1 y1为0,对应第一个松弛变量 x 3 x_3 x3不为0
y 2 , y 3 y_2,y_3 y2,y3不为0,对应第二第三个松弛变量 x 4 , x 5 x_4,x_5 x4,x5不为0
应用
知道了对偶表的最终表,就知道了飞机变量,从而知道了基变量.
影子价格
定义
单位第 i i i种资源在最优方案中做出贡献的估价
做法:通过求导得到每一种资源带来的利润的提升是多少
内涵
资源的影子价格有赖于资源的利用情况，即当目前一组基变量用于获得原问题最优解时，对偶变量 y i y_i yi每单位对利润的贡献。（需要区别于资源的市场价格)
根据互补松弛性质,有如下结论:
- 第i种资源未充分利用→其边际价格为0
- 第i种资源的边际价格不为0→其已耗尽
注意
当出现退化的最优解时，会出现第i种资源恰好耗尽，而非稀缺，但其影子价格 y i y_i yi仍大于0的情况(对应 y i y_i yi的第i个约束条件的松弛变量取值为0)，此时 b i b_i bi值的任何增加只会带来该种资源的剩余，而不增加利润值。
比如 这种值正好耗尽,同时其他值也耗尽了,这时候只增加这个值,没有用!
问题
什么叫退化的最优解
检验数的意义
问题
为什么 y i = C B B − 1 y_i=C_BB^{-1} yi=CBB−1
附上课件的解答,这个我也不知道为什么
问题：什么是退化的最优解
对偶问题的引入
所有问题一定能找到对偶问题，但是其对偶问题不一定有意义.
从另一个角度思考
假设公司A想要收购这家公司的全部资源A、B、C自己生产
从公司A的角度思考：
公司A的获利最大化——目标（以最小代价收购）
这家公司愿意出让这些资源——约束（出让所得不小于原有盈利）
以 y 1 , y 2 , y 3 y_1,y_2,y_3 y1,y2,y3表示A、B与C三种资源的出让代价，
总结
原问题 对偶问题 收益最大化 代价最小化 方程的个数,即种类的个数 决策变量数 价值系数 对偶问题右端的项向量,即 约束 资源的 约束 价值系数 对偶问题的一般形式
原问题
对偶问题
用 y i ( i = 1 , 2... m ) y_i(i=1,2...m) yi(i=1,2...m)表示第 i i i种资源的估价
✨以矩阵描述(更加直观)
多做题,就知道什么是对偶了
对称形式
与前面内容有所重复,即 B , C B,C B,C互换, A A A转置
上面讲的都是对称形式
非对称形式✨✨✨【一定要掌握】
转化有一定的规律,下面是详细的推导过程
规律
类似对称形式的,约束条件的符号决定了变量,变量的符号决定了约束条件
⚠️注意我们说的是max向min转化的问题
⚠️如果反过来,那么最后两行的"变号" "不变号"也要对调.
推导过程
复习单纯形法计算过程
为了防止这个地方听不懂,做一点说明:
检验数: σ j = c j − z j = c j − C B B − 1 P j \sigma_{\mathrm{j}}=\mathrm{c}_{{j}}-z_{j} =c_j - {C}_{\mathrm{B}}B^{-1}P_j \quad σj=cj−zj=cj−CBB−1Pj
其中P是第 j j j列变量前的系数(参考第一章)
- 考虑所有基变量的列:前m列所有
P
j
P_j
Pj合起来就变成了矩阵
B
B
B
所以检验数: C B − C B B − 1 P j = C B − C B B − 1 B = 0 {C}_{\mathrm{B}} - {C}_{\mathrm{B}}B^{-1}P_j={C}_{\mathrm{B}} - {C}_{\mathrm{B}}B^{-1}B=0 CB−CBB−1Pj=CB−CBB−1B=0
- 考虑所有飞机变量中的
X
N
X_N
XN列:这些列合起来变成了矩阵
N
N
N
所以同理,检验数: C N − C B B − 1 N {C}_{\mathrm{N}} - {C}_{\mathrm{B}}B^{-1}N CN−CBB−1N
- 考虑松弛变量
X
S
X_S
XS,松弛变量的价值系数为0,则有
检验数: 0 − C B B − 1 E = − C B B − 1 0- {C}_{\mathrm{B}}B^{-1}E=- {C}_{\mathrm{B}}B^{-1} 0−CBB−1E=−CBB−1
剩下的,见小字部分:推导出了②③式,然后换元
举例说明
对偶单纯形法
单纯形法基本思路
先寻找到初始基可行解，判断所有检验数是否小于等于0。若是，查看基变量中是否有人工变量，若无非零人工变量，即找到了最优解;若为否，再找出相邻目标函数值更大的基可行解，并继续判别，直到找出最优解。
❓问题：怎么（什么时候）添加人工变量
❓问题：有非零人工变量怎么办
对偶单纯形法基本思路
同样的，先找对偶问题的可行解再找对偶问题最优解
- 最优性看检验数 σ j \sigma_j σj
- 可行性看右端项
b
i
b_i
bi
确定初始基解
与单纯形法不同，并不要求资源限量 b i b_i bi为正
但是，当所有 b i b_i bi为正，意味着原问题取到可行解，那么此时原问题和对偶问题得到的都是最优解
- 先确定出基，是b里最小的
问题 为什么对偶问题的最优性一直都是满足的
跟单纯形法的区别与联系✨✨
-
单纯形法先确定入基变量，是最大的检验数(检验数：基变量一定为0,一部分小于零一部分大于零)，对偶先确定出基变量，是最小的 b ( b < 0 ) b(b<0) b(b<0)【单纯形法先列后行，对偶单纯形法先行后列】
✨✨🙌检验数 σ \sigma σ非正，代表对偶问题有可行解；左边的b非负，代表原问题有可行解。
-
单纯形法随后确定出基变量，是检验数 θ i = b i j a i \theta_i=\frac{b_{ij}}{a_i} θi=aibij 中最小的，【零和负数忽略！】；对偶单纯形法确定入基变量，选择 θ = min { c j − z j a r j ∣ a r j < 0 } = c s − z s a r s \theta=\min \left\{\frac{c_{j}-z_{j}}{a_{r j}} \mid a_{r j}<0\right\}=\frac{c_{s}-z_{s}}{a_{r s}} θ=min{arjcj−zj∣arj<0}=arscs−zs最小的【零和正数忽略！】【先算出 σ \sigma σ再算出 θ \theta θ的】【 z s z_s zs就是每一行 C B i ∗ a i s C_{Bi}*a_{is} CBi∗ais求和的值】
【对偶单纯形法中的 σ \sigma σ和 b b b跟原单纯形法是相反的，所以事实上是一样的】
-
单纯形法中最后判断的方式是检验数 σ \sigma σ全部小于等于零，而始终保证 b i b_i bi全部大于等于零；而对偶单纯形法相反，最后判断的是 b i b_i bi是否全部大于等于零，始终保证检验数 σ \sigma σ全部小于等于零。⚠️⚠️⚠️⚠️
-
【在后面做题时发现，上面这些条件需要原问题为{min，大于等于}，并且最后转换为max的问题】
例题讲解✨✨🙌
注意看，对偶单纯形法的条件是min还是max【我看到的是min配合大于等于】
注意：对偶问题不需要用对偶表，看视频就好⚠️⚠️⚠️⚠️
https://www.bilibili.com/video/BV12Z4y1W7aU
https://www.bilibili.com/video/BV1ut4y1T7K2
下面的例题做法非考试正规做法！！但是求单纯形法规则是一样的
对偶问题为：
运输问题建模
【考试一般不考原理，要考原理考的也是单纯形法】
【运输问题的思路其实也是单纯形法，但是针对这类问题进行了优化】
产销平衡问题
建立模型
这还是线性规划问题，可以用单纯形法求解，但是变量太多了，有另外的求解方法。
这种方法本质上和单纯形法一样，也是先找可行解在迭代出最优解。
- 模型特点
- 解有上下界
- 产销平衡（有一个多余约束条件）
- 约束条件比较特殊
- 运输表
本题有 3 + 4 − 1 = 6 3+4-1=6 3+4−1=6个这个表应该有 m + n − 1 m+n-1 m+n−1个基变量，剩下的是非基变量
求解模型【表上作业法】
确定可行解方法①：左上角填充法
尽可能使左上角取得最大值
确定可行解方法②：最小元素法
每一步优先考虑单位运价最小的业务【范围是在整个表里找最小运费】
确定可行解方法③：沃格尔法
找运价最小与次小，二者之差称为罚数，优先选择最大的罚数
迭代方法①：闭回路法
入基变量选择
选择检验数最小【负数绝对值中最大的那个】
- 核心：从非基变量开始，构造回路
- 原理：令起始的非基变量为1，（按照顺时针或者逆时针都可以）为了保证产销平衡的约束条件，下一个基变量减1，再下一个基变量加1，该格子检验数为这一变化带来的运费变化
- 即：遇到空格保持直走，遇到基变量可以选择 90°拐弯，最后计算这一个非基变量对运费带来的变化。所有的非基变量都要算出来，取最小的入基
出基变量选择
画出入基变量的回路，如图所示，回路中偶数点最小的基变量最先变成0
【思路是让某个基变量变成0，如题，此时 θ \theta θ取2】
产销不平衡问题
产量大于销量
对于这类问题，可以假想一个销地 B 5 B_5 B5，对于产量大于销量的这部分，统一运往 B 5 B_5 B5。
由于 B 5 B_5 B5是个假想地，实际上就是就地存储在A;的物品数量，因此其运价为0，新的单位运价表如下:
有转运的问题
产地同时也是销地
产销不确定
分析：
- 首先， a 3 a_3 a3是有上限的
- 将产量分为最小产量和冗余产量，分别放在 A i A_i Ai和 A i ′ A_i^{'} Ai′【必须到/可到可不到】
- 假定一个不能被运输的销地，销量由产量减已有销量得到。【
A
i
′
A_i^{'}
Ai′这种可到可不到的放到B5相当于原地储存】
- 核心：从非基变量开始，构造回路
- 模型特点
-
- 先确定出基，是b里最小的
- 考虑所有基变量的列:前m列所有
P
j
P_j
Pj合起来就变成了矩阵
B
B
B
- 原问题最优解目标函数值是对偶问题目标函数值的下界，对偶问题最优解目标函数值是原问题目标函数值的上界。
猜你喜欢
网友评论
- 搜索
- 最新文章
- 热门文章