1 / 51
文档名称:

线性规划的对偶理论(2)ppt演示文稿.ppt

格式:ppt   大小:1,265KB   页数:51页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

线性规划的对偶理论(2)ppt演示文稿.ppt

上传人:精品小课件 2021/2/22 文件大小:1.24 MB

下载得到文件列表

线性规划的对偶理论(2)ppt演示文稿.ppt

文档介绍

文档介绍:第三章 线性规划的对偶理论
组合优化理论
Combinatorial
Optimization Theory
1
§1 对偶问题的提出
一、对偶问题的实例
产品 资源
资源 甲 乙 限制
A 3 2 65
B 2 1 40
C 0 3 75
单件利润 1500 2500
max z =1500x1+2500x2
. 3x1+2x2 ≤65
2x1 +x2 ≤40 (1)
3x2 ≤75
x1 , x2 ≥ 0
最优解为: x1* =5 , x2* =25 zmax =70000
设 y1, y2, y3 分别为 A, B, C 三种资源出售的价格
3y1 +2y2 ≥ 1500
2y1 + y2 +3y3 ≥ 2500
w= 65y1 +40y2 +75y3
min w = 65y1 +40y2 +75y3
. 3y1 +2y2 ≥ 1500 (2)
2y1 + y2 +3y3 ≥ 2500
y1, y2, y3≥ 0
最优解为: y1*= 500
y2*= 0 , y3* = 500,
wmin = 70000
如果称(1)为LP 问题的
原问题,则称(2)为(1)
的对偶问题。
2
第三章 线性规划的对偶理论
二、对偶问题的形式
1、对称型对偶问题
max z = c1x1 + c2x2 + … + cnxn
. a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn ≤ b2
(3) … …
am1x1 + am2x2 + … + amnxn ≤ bm
xj ≥ 0 (j = 1,2,…,n)
min w = b1 y1 + b2 y2 + … +bm ym
. a11y1 + a21 y2 + … + am1ym ≥ c1
a12y1 + a22y2 + … + am2 ym ≥ c2
(4) … …
a1ny1 + a2ny2 + … + amnym ≥ cn
yi≥ 0 (i = 1,2,…,m)
定义1 设原 LP 问题为
则称下列 LP 问题
为其对偶问题,其中 yi ≥ 0 (i = 1,2,…,m)称为对偶变量,
并称(3)、(4)为一对对称型对偶问题
max z=cx
(P) . Ax ≤b
x ≥ 0
min w= yb
(D) . yA ≥ c
y ≥ 0
3
§1 对偶问题的提出
2、非对称型对偶问题
max z = cx
(P) . Ax = b
x ≥ 0
max z = cx
. Ax ≤ b
-Ax ≤ -b
x ≥ 0
引入对偶变量(u,v),其中 u = (u1,u2,…,um)
为对应于第一组不等式约束 Ax ≤b 的对偶变
量,v = (v1,v2,…,vm) 为对应于第二组不等式约
束 -Ax ≤-b 的对偶变量,按对称型的结论:
min w = (u-v) b
. (u-v) A ≥ c
u,v ≥ 0
令 y=u-v
min w= yb
(D) . yA ≥ c
y ≥ 0
min w = yb
(D) . yA ≥c
y 无符号限制
4
第三章 线性规划的对偶理论
3、混

最近更新

2024年节约用电倡议书600字左右范文7篇 10页

2024年自我鉴定护士毕业模板6篇 13页

2024年自我介绍大学生0字篇 11页

三种食用菌的抗烟草花叶病毒(TMV)活性研究的.. 2页

最新部编人教版小学三年级道德与法治下册期末.. 13页

2024年职业学校鉴定表自我鉴定参考5篇 8页

纺织行业的人工智能应用案例分享 24页

2024年美术青花瓷教案8篇 23页

纺织材料的表面处理与功能化 24页

2024年网络教育毕业生自我鉴定简短9篇 13页

一维碳纳米材料的可控制备及其生长机理的研究.. 2页

一粒小麦抗白粉病新基因的鉴定和标记辅助转移.. 2页

一类李代数的结构及表示的中期报告 2页

2024年精选教师个人述职报告模板7篇 20页

2024年精选关于资金补助申请书参考范文3篇 5页

管理学StephenPRobb 30页

管理学-02管理思想的发展 24页

管理咨询的基本介绍 32页

一种基于离散小波变换的图像数字水印算法的任.. 2页

2023年监理工程师之土木建筑目标控制强化训练.. 17页

2023年特岗教师《专业基础知识》考试全真模拟.. 14页

变压器火灾及预防 23页

2024年石景山区高三理科数学统一测试(一模)-完.. 11页

养牛日常饲养工作日记记录表 1页

饲养牛记录表 7页

〖精选文档〗销售话术900句 13页

光伏电站电池板清洗合同模板 5页

自考公共关系学重点笔记 41页

台达楼宇管理和控制产品销售培训 30页

自考公共关系学重点笔记 47页