1、运运 筹筹 学学Operations Research* 1第三章第三章 对偶理论与灵敏度分析对偶理论与灵敏度分析内容提要内容提要3.1 线性规划的对偶问题3.2 线性规划的对偶理论3.3 影子价格3.4 对偶单纯形方法3.5 灵敏度分析* 2从 经济意义 上研究线性规划的对偶问题，通过对对偶问题的研究，从不同的角度对线性规划问题进行分析，从而利用有限的数据，得出更广泛的结果，间接地获得更多的有用信息，为企业经营决策提供更多的科学依据。3.1 线性规划的对偶问题线性规划的对偶问题1. 对偶问题的提出2. 如何将原问题转化为对偶问题3. 原问题与对偶问题的对应关系* 3例例 ： 某工厂拥有 A、
2、 B、 C三种类型的原料，生产甲、乙两种产品。每件产品在生产中消耗的原料数量，每件产品的价格以及三种原料可利用的数量如下表所示：产品原料 甲 乙原料数量（吨）A 1 1 300B 2 1 400C 0 2 250价格（元 /件） 50 100* 41. 对偶问题的提出问题 ：工厂应如何安排生产可获得最大的总收益？解解 ： 设变量 xi为第 i种（甲、乙）产品的生产件数（ i 1， 2）。则有目标函数 Max z = 50x1 + 100x2 s.t. x1 + x2 3002x1 + x2 4002x2 250 x1 ,x2 0* 5现在考虑若三种原料都用于转让，试问：三种原料各如何收费才能
3、既 保证本厂的利益，又能最有竞争力？设 y1 ， y2 ， y3 分别为每设备工时（或原料）每单位的收取费用，则有Min f = 300y1+ 400y2 + 250y3s.t. y1+2y2 50（不少于甲产品的利润）y1+ y2+2y3 100（不少于乙产品的利润）y1,y2 ,y3 0* 6Min f = 300y1+ 400y2 + 250y3s.t. y1+2y2 50y1+ y2+ 2y3 100y1, y2 , y3 0Max z = 50x1 + 100x2 s.t. x1 + x2 3002x1 + x2 4002x2 250 x1 , x2 0对偶问题对偶问题租赁者模型租赁
4、者模型原问题原问题管理者模型管理者模型一对互为对偶的模型* 7问题的提出问题的提出线线性性规规划划对对偶偶问问题题线性规划有一个有趣的特性，就是对于任何一个求 极大值 的线性规划问题都存在一个与其对应的 极小值 线性规划问题，而且二者之间联系紧密，可以 互相转化。 对偶性 从例子中可以看出： （ 1）原规划问题为 生产计划 问题，而其对偶问题为赋予该生产计划可行性的 潜在价值 问题 （ 2）原规划的目标函数是从资源拥有者的角度得出 利润最大化 ，而其对偶规划的目标函数是从想获得该资源方的角度得出 成本最小化 （ 3）两个问题共用一套参数，但组合方式不同 对偶问题的定义： （对称形式 Dual
5、Program） （ LP ） max Z=c1 x1 + c2 x2 + . + cn xns.t. a11x1 + a12 x2 + . + a1nxn b1 . . . . . . am1x1 + am2x2 + .+ amn xn bm x1 , x2 , . , xn 0（ DP） min W=b1 y1+ b2 y2+ . + bm yms.t. a11y1+ a21 y2+ . + am1 ym c1 . . . . . . a1ny1+ a2n y2+ . + amnym cn y1 , y2 , . , ym 0* 9对称对偶线性规划的特点是： 全部约束条件均为不等式，对极大化问题为 ，对极小化问题为 。 全部变量均为非负。(LP) Max z = c x (DP) Min f = bT ys.t. Ax b s.t. AT y cTx 0 y 0 则（ DP）称为（ LP）的对称形式对偶问题设：* 10
