版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第三章线性规划的对偶理论与灵敏度分析
线性规划的对偶问题
对偶问题的基本性质影子价格对偶单纯形法灵敏度分析第二节对偶问题的基本性质为了便于讨论,下面不妨总是假设:原线性规划问题的矩阵表达式加上松弛变量后为:
一、单纯形法的矩阵描述上式中Xs为松弛变量,,I为m×m单位矩阵。
Cj
c1c2
cn00
0CBXBbx1x2
xnxn+1xn+2
xn+m0xn+1b1a11a12
a1n10
00xn+2b2a21a22
a2n01
0
0xn+mbmam1am2
amn00
1cj-zjc1c2
cn00
0非基变量基变量XBXNXS0XSbBNICj-zjCBCN0
单纯形法计算时,总选取I为初始基,对应基变量为Xs。设迭代若干步后,基变量为XB,在初始单纯形表中的系数矩阵为B。B将在初始单纯形表中单独列出,而A中去掉若干列后剩下的列组成矩阵N,这样初始单纯形表可列成如下形式。非基变量基变量XBXNXS0XSbBNICj-zjCBCN0
当迭代若干步后,基变量为XB时,则该步的单纯形表中由XB系数组成的矩阵为I。又因单纯形法的迭代是对约束增广矩阵进行的行的初等变换,对应XS的系数矩阵在新表中应为B-1。故当基变量为XB时,新的单纯形表具有如下形式。基变量非基变量XBXNXSCBXBB-1bIB-1NB-1
Cj-zj0CN-CBB-1N-CBB-1
当迭代后基变量为XB时,其在初始单纯形表中的系数矩阵为B,则有:(1)对应初始单纯形表中的单位矩阵I,迭代后的单纯形表中为B-1
(2)初始单纯形表中基变量Xs=b,迭代后的表中
XB=B-1
b(3)初始单纯形表中约束系数矩阵为
,迭代后的表中约束系数矩阵为(B-1左乘):非基变量基变量XBXNXS0XSbBNICj-zjCBCN0基变量非基变量XBXNXSCBXBB-1bIB-1NB-1
Cj-zj0CN-CBB-1N-CBB-1
(4)若初始矩阵中变量Xj的系数向量为Pj,迭代后为,则有:(5)当B为最优基时,应有:
这时从检验数行看出,若取其相反数恰好是其对偶问题的一个可行解。将这个解代入对偶问题的目标函数值,有:
因XB的检验数可写为:
则有称为单纯形乘子,若令基变量非基变量XBXNXSCBXBB-1bIB-1NB-1
Cj-zj0CN-CBB-1N-CBB-1
XN的检验数
XS的检验数
XB的检验数
所以XA的检验数
例1
两个互为对偶的线性规划问题,两者分别加上松弛和剩余变量后为:二、原规划与对偶规划问题的变量及解之间的对应关系两个问题的最终单纯形表见下页:
原问题变量松弛变量
x1x2x3x4x5x315/20015/4-15/2x17/21001/4-1/2x23/2010-1/43/2000-1/4-1/2
对偶问题的剩余变量对偶问题变量y4y5y1y2y3
对偶问题变量对偶问题的剩余变量
y1y2y3y4y5y21/4-5/410-1/41/4y31/215/2011/2-3/215/2007/23/2
原问题松弛变量x3x4x5原问题变量x1x2二、原规划与对偶规划问题的变量及解之间的对应关系●对偶(min型)变量的最优解等于原问题松弛变量检验数的绝对值●对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值●由于原问题和对偶问题是相互对偶的,因此对偶问题的检验数与原问题的解也有类似上述关系。●更一般地讲,不管原问题是否标准,在最优解的单纯型表中,都有原问题虚变量(松弛或剩余)的检验数对应其对偶问题实变量
(对偶变量)的最优解,原问题实变量(决策变量)的检验数对应其对偶问题虚变量
(松弛或剩余变量)的最优解。因此,原问题或对偶问题只需求解其中之一就可以了。三、线性规划的对偶定理弱对偶性(弱对偶定理)证明:弱对偶定理推论:●max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限;min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限。●如果原问题(对偶问题)为无界解,则其对偶问题(原问题)无可行解。●如果原问题(对偶问题)有可行解,其对偶问题(原问题)无可行解,则原问题(对偶问题)为无界解。注意:如果原问题(对偶问题)无可行解,对偶问题(原问题)具有无界解或无可行解。2.最优性(最优解判别定理)证明:设xj*是原问题的最优解,yi*是对偶问题的最优解3.强对偶性(对偶定理)定理如果原问题和对偶问题都有可行解,则它们都有最优解,且它们的最优解的目标函数值相等。证:第一步,证明都有最优解。原问题和对偶问题都有可行解,由弱对偶定理推论1可知,原问题目标函数有上界,对偶问题的目标函数有下界,故一定存在最优解。
第二步,证明最优解的目标函数值相等。根据单纯
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 43913-2024钢制异径短节
- 奶茶促销策划方案(2篇)
- 2024年湿法混合颗粒机项目资金筹措计划书代可行性研究报告
- 环境化学-知到答案、智慧树答案
- 果树栽培学基础-知到答案、智慧树答案
- 2023年注射剂类药品资金需求报告
- 2023年原子灰资金申请报告
- 2023年片式电感资金申请报告
- 2023年镭矿资金需求报告
- 2023年熏香资金申请报告
- fluent炉膛仿真教程
- 北师大版小学数学一年级下册第六单元分析及教学建议
- 七年级学生特点分析及建议
- 统编教材小学语文《十万个为什么》读中推进课活动设计
- 临时钢管立柱计算
- 中医跟师心得体会范文
- 博世力士乐运动控制器常用编程指令手册
- 对蜡烛及其燃烧的探究》教学设计
- 旋回破碎机操作规程
- 中医美容科临床技术操作规范.
- 眩晕中医临床路径标准住院表单
评论
0/150
提交评论