运筹学课件--第三章 对偶规划.ppt

1、经营运营研究-管理科学方法，李准，桂林电子科技大学管理学院，SubTitle，Or3360SM，第三章双重计划内容摘要第一节双重计划的数学模式双重问题的性质第二节双重计划的经济解释影子价值的内涵影子价值的说明应用节目第三节资源价钱决策案例，第二节Or3333 OR3360SM 对称性定理弱对偶定理，对偶定理互补松弛定理对偶问题解决的经济意义极限贡献，OR3360SM，OR我想借用你的机械设备。 怎么样？价格呢，钱，但是现在手机生意这么好，还不如把我的机器设备借给他，收租金，学生也可以。肯定不会让你弟弟吃亏的。价格呢。上衣做得好，上衣也做得好。只是.王老板做家电赚了大钱，可惜我们老李有高科技产品

2、，但机器设备不足，怎么办？只有租赁。高：王老板，听说最近家用电器生意太惨了，请兄弟也帮帮我们吧！4，王经理，董事长，OR:SM，OR:SM，厂方在协商时要心里有数，以便测量对方的出价，选择是否租赁，要掌握设备台市成本的最低价格。在牙齿问题上，厂长面临两种茄子选择：自行生产或租赁设备。首先要明确两个茄子问题：合理安排生产能获得多少利润？为了不降低利润水平，资源转让的最低价格是多少？问题的最佳解决方案：x1=4，x2=5，Z*=37。5，或：sm，或：sm，第一节双计划的数学模型1，双问题的建议转让价钱家庭销售A，B，C设备收益利润分别是y1，y2，y3原始用于生产A产品的设备台。转让不能低于自产

3、的利益。因此，与2y1 0y2 3y3一样，在乙产品的情况下，0y1 2y2 4y3 5设备台时销售的收益(最小收益额)min 16y1 10y2 32y3显然有y1、y2、y30，6、Or :SM和2x1牙齿。第一节大邱规划的数学模型1，对偶问题的毽子范例1的对偶问题的数学模型，Maxz=3x 15x 2 16 2x 2 10s . t . 3x 1 4x 2 32x 1，x20，Min=16 y1 10 y2 32y 3 2 y1 0 y2 3y 3s . t . 0 y1 2 y2 4y 3 5 y1，7，或：sm，或：sm，第一部分对偶计划的数学模型，表3-1，对偶关系，原始问题(或对

4、偶问题)目标函数最大目标函数系数(资源限制)约束系数矩阵A(AT) n变量对偶问题(或原始第j个约束j 8，第I个约束=，第I个变量不受约束，OR:SM，1，1，or 3360 sm minzx 1 5x 2 4x 3 9x 4 7x1 2x 2 x2 8x3 x4 18 6x 2 5x 4 10 2x1 8x2 x3 14x 1无限制，or 3360 sm min z=2 x1-x2 2x 3-x1 x2x 3=4-x1x 2-x3 6x 10，x20，X3无限制max w18y 1 10 y2 14 y3 7 y1 2 y3=1 2 y6 y2 8 y3 5 y3 4 y5 9 y10mi

5、n z=2 x1-x2 2x 3-x1x2x 3=4-x1x 2-x3 6x 10，x20，x3无限制2，请写以下问题的对偶问题：max w=5x1 4x2 6x3，x1 -x1 x2 x3 -5 x1-x2 x3=1 x10，x20，x3不受约束，10，or 3360 sm，*，OR:SM，第一个2，最优化定理将X，Y分别设定为原始问题和对偶问题的可行解，C X b T Y分别设定为X，Y各自的最优解。3.双导性定理对原问题有最优解的话，对偶问题也有最优解，两个茄子目标函数值相同。4.互补松弛最佳解的充分条件是Y * X s 0，ys x 0，11，or :sm，Xi，j，or :sm，第一

6、节对偶规划的数学模型。把互补条件写如下。m I 1 n J1，要使求和等于0，每个分量必须为0，因此(1) yi*0，S 0，相反，xSi 0点yi *=0；(2) yS j 0点x* 0，相反，如果使用x* 0点yS j 0牙齿上的关系为对偶问题(或原始问题)建立约束线性方程组，则方程的解是最优解。12，or 3360 sm，j，or 3360 sm，第一个双计划的数学模型示例3已知线性计划，max z3x 1 4x2x3x 1 2x2x 3 10st2x 12x 3 16x 0，J1也就是说，如果求解y1 2y 2 3 2 y1 2y 2 4，牙齿线性方程，则y1=1牙齿，13，或：sm，

7、*，2，或：sm，试试看？已知线性计划问题min 2 x1 3x 2 5x 3 2x 4 3x 5 x2 2x 3 3x 4 3x 5 4 2x 1 x2 3x 4 X5 3x j 0，J1，2，5，知道对偶问题的最佳解决方法，y1 4/5，y* 3/5 z=5，14，or :sm，*，*，*，*，*，*，2，2 3，or 3360 sm，解决方案：首先是双重问题maxz4 y1 3y2，y1 2y因为y1，Y20原始问题的两个约束x1 3 X5 4必须得到等式，所以求解2 x1 X5 3就得到X11，X51。因此，原始问题的最佳解是X *=(1，0，0，0，1) T。*=5，15，或：sm，

8、或：sm，第二部分双重计划的经济解释1，阴影值的含义，n m Z c j x j bi yi j 1 I 1，Z bi，yi，左侧是资源bi每次向目标函数Z添加1个单位时的贡献。对偶变量yi在经济上表示原始问题的第一类资源的极限值。双变量的值yi*表示第I个资源的极限值，称为阴影值。原始问题价值系数如果Cj表示单位产值，则yi称为影子价格。原始问题值系数如果Cj表示单位收益，则yi称为阴影收益。阴影价钱=资源成本阴影收益，16，OR:SM，OR:SM，第二部分双重计划的经济说明1，阴影价值的嵌套阴影价格反映了目标函数的增加，而不是资源的实际价格，而是资源配置结构，其他数据的固定，一个资源的一个

9、单位的增加。资源I的总库存评价：购买或销售资源I的当前配额评价：增加或减少第一，影子利润说明增加什么资源对经济利益最有利，影子价格告诉我们什么代价可以得到不足的资源。第三名，影子价格是机会成本。资源租赁/转让的基本价格第4位，利用影子价格分析新产品的资源效果：利用价钱决定第5位影子价格分析现有产品价钱波动的资源紧缩第6位，有助于分析过程变更后节约资源的收益第7位，预测哪些资源是稀缺资源，哪些资源不不足。17，OR:SM，OR:SM，第3节确定资源价钱方案示例：在一家工厂生产甲方产品，(1)；a、b、资源成本、资源所有权、原材料(kg)、9，4，20，360、设备功率、(工作时间) (度)、4

10、3，5 10，50 1，200第一、最佳生产决策maxz7x1 12x2、原材料的单位转让收益为y1，设备劳动时间单位转让收益为y2，电力的单位转让收益为y3。销售决策的线性计划模型：min w360 y1 200 y2 300 y3 9 y1 4 y2 3 y3 7s . t . 4 y1 5 y2 10 y3 12 y1，y2，y3 0，19，y * 0y * 1.36 y * 0.52，z资源市场原材料的价格为千克/企业需要购买资源吗？分析：原材料的资源费用为千克/20韩元，设备工作费用为50韩元，电力资源费用为度/1韩元，因此影子价格分别为千克/千克、时间/51.36韩元和度/1.52韩元。企业经营决策者可以将本企业资源的影子价格与市场价格进行比较后做出决定。电力资源影子价格高于市场价格，企业可以考虑购买资源，增加拥有量。设备工作时间的影子价格低于市场价格，企业暂时不能购买。虽然原材料市场价格低于影子价格，但由于它是非短缺资源，企业增加资源不仅没有利润，还会增加库存成本。20、或：sm、或：sm，牙齿章节概括了双重问题与原始问题对称的线性规划问题。对偶理论主要有对称、最优化、互补性等几个茄子基本定理，对分析和判断线性规划问题的解决具有重要作用。大邱变量的经济解释是对资源最佳利用情况的客观评价，不是实际价格，而是虚拟价钱(或价值