运筹学 第02章 对偶线性规划与灵敏度分析

《运筹学 第02章 对偶线性规划与灵敏度分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学第二章对偶线性规划与灵敏度分析本章重点对偶问题的求解对偶定理对偶单纯形法灵敏度分析对偶线性规划问题的导出(1)（前面讲过的生产计划问题）某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的日生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354对偶线性规划问题的导出(2)设每天生产三种产品的数量分别为x1、x2、x3现在三种产品销路不畅，可以将所有的原料外卖，现在要谈判，我们的价格底线是

2、什么？对偶线性规划问题的导出(3)解决这一问题应考虑外卖原料获利应不少于生产产品的获利，即出卖能够制造一个单位产品的原料的获利应该不少于生产一个单位该产品的获利价格应该尽可能低，这样才有竞争力价格应该是非负的设出租或外卖三种原料的价格分别为y1、y2、y3对偶线性规划问题的导出(4)上述两个线性规划模型是在同一工厂的资源状况和生产状况条件下产生的，是同一问题从不同角度来观察所产生的，因此两者密切相关，我们称这两个线性规划问题互为对偶问题，其中一个问题是另一问题的对偶问题。对偶问题的定义(1)对于线性规划问题（1）对偶问题的定义(

3、2)和（2）对偶问题的定义(2)称（1）是（2）的对偶问题；也称（2）是（1）的对偶问题这种对偶关系称为对称形式的对偶，用矩阵表示为对偶问题的定义(3)还有一种非对称形式的对偶，用矩阵表示为求对偶问题原问题（或对偶问题）对偶问题（或原问题）目标函数MaxZ目标函数MinW约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量约束条件数：n个第j个约束条件类型为“≥”第j个

4、约束条件类型为“≤”第j个约束条件类型为“=”示例(2.1-1)写出下面线性规划的对偶规划示例(2.1-2)结果为作业(6)书上99页的2-1对偶定理(1)对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的一系列定理定理1对称性定理对偶问题的对偶问题是原问题定理2弱对偶定理极大化原问题的任一可行解的目标函数值，不大于其对偶问题的任一可行解的目标函数值对偶定理(2)均有可行解，分别为和，则证明：由(L)，左乘，得由(D)，右乘，得设（L）和（D）对偶定理(3)推论1极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目

5、标函数值的一个下界推论2极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界推论3若原问题可行，则其目标函数无界的充要条件是对偶问题没有可行解对偶定理(4)推论4若对偶问题可行，则其目标函数无界的充要条件是原问题没有可行解定理3最优性准则定理若、分别为互为对偶问题的线性规划的可行解，且，则和分别是相应线性规划问题的最优解对偶定理(5)CX≤bTYT弱对偶定理已知结论最优解定义X=Y=特别取证明CX≤C对偶定理(6)定理4主对偶定理若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同证

6、明：第一部分——证明两者均有最优解由于原始问题和对偶问题均可行，根据弱对偶定理知两者均有界，于是均有最优解。第二部分——证明在达到最优时，两个问题的目标函数值相等利用单纯形法的特征，就非对称形式的对偶问题给出对偶定理(7)第一步：给出原问题和对偶问题(L)设原问题有对应于最优基B的最优基本可行解X=(XB,0)T,则有XB=B-1b(D)对偶定理(8)第二步：利用单纯形法的矩阵描述，由单纯形法最优性判别定理得出重要结论,并引出“单纯形乘子”的定义；定义（最优单纯形乘子）令A=（B,N），所以对应于最优基B的检验数满足对偶定理(9

7、)第三步：证明最优单纯形乘子就是对偶问题的可行解所以，是对偶问题的可行解对偶定理(10)第四步：进一步证明是对偶问题的最优解，并验证两个问题的目标函数值相等。又根据最优性准则定理，这时的正是对偶问题的最优解。由原问题最优单纯形表求对偶问题最优解由检验数的计算方法可知设B是原线性规划问题的最优基，则是其对偶问题的最优解若A中有单位子矩阵，该子矩阵对应的列为第i1,i2,…,im(i1

8、1-11-170000-1-5-10示例(2.2-2)得即对偶问题的最优解为y1*=5，y2*=10什麽是对偶单纯形法对偶单纯形法是应用对偶原理求解原始线性规划的一种方法。注意：不是解对偶问题的单纯形法对偶单纯形法的基本思想(1)对偶可行基的概念若cBB-1是对