《运筹学 ( 对偶问题及性质)（经典实用）.ppt》由会员分享，可在线阅读，更多相关《运筹学 ( 对偶问题及性质)（经典实用）.ppt（27页珍藏版）》请在三一文库上搜索。
1、运筹学 ( 对偶问题及性质),Chapter2 对偶理论 ( Duality Theory ),线性规划的对偶模型 对偶性质 对偶问题的经济解释影子价格 对偶单纯形法 灵敏性分析,本章主要内容：,运筹学 ( 对偶问题及性质),线性规划的对偶模型,设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 ：,产品数据表,问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？,1. 对偶问题的现实来源,运筹学 ( 对偶问题及性质),解：设甲、乙型产品各生产x1及x2件，则数学模型为：,反过来问：
2、若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？,运筹学 ( 对偶问题及性质),在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：,运筹学 ( 对偶问题及性质),2. 原问题与对偶问题的对应关系,原问题 （对偶问题）,对偶问题 （原问题）,运筹学 ( 对偶问题及
3、性质),线性规划的对偶模型,（1）对称形式,特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.,已知 (LP)，写出 (DP),运筹学 ( 对偶问题及性质),单纯形法计算的矩阵描述(nm),运筹学 ( 对偶问题及性质),若初始矩阵中变量 xj的系数向量为Pj, 迭代后为Pj, 则有 Pj=B-1 Pj 当B为最优基时，应有 令Y=CBB-1, 则,运筹学 ( 对偶问题及性质),运筹学 ( 对偶问题及性质),例2.1 写出线性规划问题的对偶问题,解：首先将原问题变形为对称形式,运筹学 ( 对偶问题及性质),(2) 非对称形式的对偶规划 一般称不
4、具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；,运筹学 ( 对偶问题及性质),（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。,1.线性规划对偶问题,运筹学 ( 对偶问题及性质),线性规划的对偶模型,运筹学 ( 对偶问题及性质),例2.2 写出下列线性规划问题的对偶问题.,解：原问题的
5、对偶问题为,运筹学 ( 对偶问题及性质),对偶性质,例2.3 分别求解下列2个互为对偶关系的线性规划问题,分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：,运筹学 ( 对偶问题及性质),对偶性质,原问题最优表,对偶问题最优表,运筹学 ( 对偶问题及性质),对偶性质,原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。,运筹学 ( 对偶问题及性质),对偶问题的基本性质,(1) 对称性：对偶问题的对偶是原问题 ; (2)弱对偶性：若X是原问题的可行解，Y是对偶问题的可行解。则存在CXYb; (3) 无界性：若原
6、问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解; (4) 可行解是最优解时的性质 ; (5) 对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相等; (6) 互补松弛性 ; (7) 原问题检验数与对偶问题解的关系。,运筹学 ( 对偶问题及性质),对偶性质,性质1 (对称性)：对偶问题的对偶是原问题,运筹学 ( 对偶问题及性质),对偶性质,性质2 (弱对偶性) 设 和 分别是问题(LP)和(DP)的可行解，则必有,推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。,性质3 (无界性): 在
7、一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。,运筹学 ( 对偶问题及性质),从两图对比可明显看到原问题无界，其对偶问题无可行解,运筹学 ( 对偶问题及性质),对偶性质,性质4 (最优性定理) 如果 是原问题的可行解， 是其对偶问题的可行解，并且:,则 是原问题的最优解， 是其对偶问题的最优解。,运筹学 ( 对偶问题及性质),对偶性质,性质5 (强对偶性)：若原问题具有最优解，则对偶问题也具有最优解，且它们最优解的目标函数值相等。,性质6 (互补松弛性)：在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零
8、，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零. 即Y*XS=0，YSX*=0,运筹学 ( 对偶问题及性质),对偶性质,例2.4 已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,解：写出原问题的对偶问题，即,标准化,运筹学 ( 对偶问题及性质),设对偶问题最优解为Y(y1，y2),因为X10，X20，所以由互补松弛性定理可知， 对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为： Y=(1,1)，最优值w=26。,运筹学 ( 对偶问题及性质),作业:第88-89页: 3.3(1),(2) 3.8 思考题：3.2 3.4,此课件下载可自行编辑修改，供参考！ 感谢你的支持，我们会努力做得更好！,