文档介绍：该【对偶问题公开课获奖课件赛课一等奖课件 】是由【书犹药也】上传分享，文档一共【89】页，该文档可以免费在线阅读，需要了解更多关于【对偶问题公开课获奖课件赛课一等奖课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2025/5/7
--第2章 对偶问题--
--1--
第 二 章 线性规划的对偶理论
Duality 对偶
Dual Problem 对偶问题
Dual Linear Programming
对偶线性规划
Dual Theory 对偶理论
2025/5/7
2
例 甲方生产计划问题：
Ⅰ Ⅱ 能力
设备A 2 2 12
设备B 4 0 16
设备C 0 5 15
利润 2 3
Ⅰ，Ⅱ各生产多少, 可获最大利润?
乙方租借设备：
甲方以何种价格将设备A、B、
C租借给乙方比较合理？ 请为
其定价。
问题的提出
--第2章 对偶问题--
2025/5/7
3
而就乙方而言，但愿甲方的租金收入在满足约束的条件下越小越好，
这样双方才也许达到协议。
于是得到下述 的线性规划模型：
解：假设A、B、C的单位租金分别为 ，因此生产产品Ⅰ的资源用于出租时，租金收入应满足：
类似的，生产产品Ⅱ的资源用于出租时，租金收入应满足：
总的租金收入：
--第2章 对偶问题--
思绪： 就甲方而言， 租金收入应不低于将设备用于自已生产时的利润。
原问题的对偶问题
2025/5/7
--第2章 对偶问题--
--4--
例：某企业计划生产甲、乙两种产品，该两种产品均需经 A、B、C、D 四种不一样设备加工，按工艺资料规定，在多种不一样设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：怎样安排产品的生产计划，才能使企业获利最大?
2025/5/7
--第2章 对偶问题--
--5--
设 企业生产甲产品为X1件，
乙产品为X2件，则
max z= 2 X1 +3 X2
2 X1 +2 X2 12
X1 +2 X2 8
4 X1 16
4 X2 12
X1 0 , X2 0
(原问题) <========> ( 对偶问题)
设第i种资源价格为yi,（ i=1, 2, 3, 4,） 则有
min w= 12y1 + 8y2 + 16y3 +12 y4
2y1 + y2 + 4y3 +0 y4 2
2y1 +2y2 + 0y3 +4 y4 3
yi 0, (i=1, 2, 3, 4 )
y1
y2
y3
y4
2025/5/7
--第2章 对偶问题--
--6--
原问题与对偶问题的关系
一般表达式：
原问题： max z = c1 X1 + c2 X2 + ┈ + cn Xn
a11 X1 + a12 X2 + ┈ + a1n Xn b1
a21 X1 + a22 X2 + ┈ + a2n Xn b2
·······················
am1 X1 + am2 X2 + ┈ + amn Xn bm
xj 0，j=1,2,┈,n
对偶问题： min w = b1 y1 + b2 y2 + ┈ + bm ym
a11 y1 + a21 y2 + ┈ + am1 ym c1
a12 y1 + a22 y2 + ┈ + am2 ym c2
·························
a1n y1 + a2n y2 + ┈ + amn ym cn
yi 0，(i=1,2,···,m )
2025/5/7
--第2章 对偶问题--
--7--
典式模型对应对偶构造矩阵表达
（1） max z = C X
AX b
X 0
min w = Y b
YA C
Y 0
对偶问题
原问题
这是规范形式 的原问题，由此写出其对偶问题如右方所示，那么，当原问题
不是规范形式时，应怎样写出其对偶问题？可以先将原问题化成规范的
原问题，再写出对偶问题。
2025/5/7
--第2章 对偶问题--
--8--
对偶模型其他构造关系
（2）若模型为 max z = C X
AX b X 0
max z = C X
- AX -b
X 0
变形
min w = Y b
YA C
Y 0
Min w=Y ´(-b)
st. Y ´(-A) C Y ´ 0
令 Y= -Y ´
对偶问题
对偶变量Y
2025/5/7
--第2章 对偶问题--
--9--
（3）max z = C X
AX b X 0
变形
设X= -X´
max = -CX ´
st. -AX´ b X´ 0
min w = Y b
YA C
Y 0
则有
min w = Y b
-YA - C
Y 0
2025/5/7
--第2章 对偶问题--
--10--
对偶问题典式：
用矩阵形式表达：
（1） max z = C X min w = Y b
AX b <========> YA C
X 0 Y 0
（2） max z = C X min w = Y b
AX b <========> YA C
X 0 Y 0
（3）max z = C X min w = Y b
AX b <========> YA C
X 0 Y 0