【课堂笔记】运筹学第二章：对偶问题

标题~

• 本系列文章主要用于笔者期末复习，行文混乱，请见谅
• 备考补充及零碎知识点
• • 弱对偶定理
  • • 推论
  • 最优性
  • 强对偶定理
  • 互补松弛性✨
  • • 证明过程(推荐看一看)
    • • 换言之:对偶变量和松弛变量的乘积为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=1n​aij​xj​=bi​ ， 即松弛变量值为 0

• 若

  ∑

  j

  =

  1

  n

  a

  i

  j

  x

  j

  <

  b

  i

  \sum_{j=1}^{n} a_{i j} x_{j}<b_{i}

  ∑j=1n​aij​xj​<bi​ ， 即松弛变量值不为 0 ，则有

  y

  i

  =

  0

  y_{i}=0

  yi​=0

证明过程(推荐看一看)

换言之:对偶变量和松弛变量的乘积为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​=CB​B−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​−CB​B−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​−CB​B−1Pj​=CB​−CB​B−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​−CB​B−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−CB​B−1E=−CB​B−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​=ai​bij​​ 中最小的，【零和负数忽略！】；对偶单纯形法确定入基变量，选择

  θ

  =

  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{arj​cj​−zj​​∣arj​<0}=ars​cs​−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

下面的例题做法非考试正规做法！！但是求单纯形法规则是一样的

对偶问题为：

运输问题建模

【考试一般不考原理，要考原理考的也是单纯形法】

【运输问题的思路其实也是单纯形法，但是针对这类问题进行了优化】

产销平衡问题

建立模型

这还是线性规划问题，可以用单纯形法求解，但是变量太多了，有另外的求解方法。

这种方法本质上和单纯形法一样，也是先找可行解在迭代出最优解。

• 模型特点

1. 解有上下界
2. 产销平衡（有一个多余约束条件）
3. 约束条件比较特殊

• 运输表

  

  本题有

  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相当于原地储存】