1、第二章 线性规划对偶理论第一节 线性规划对偶理论第二 节 对偶问题基本性质第三 节 影子价格第四 节 对偶单纯形法第五 节 灵敏度分析1/66第一节 线性规划对偶理论一、对偶问题的提出例 2/66设备台时 /件产品 可用台时（千小时）产 品 1 产 品 2下料 设备 A 1 0 4机加工 设备 B 0 2 12焊 接 设备 C 3 2 18产 品 单 价 3元 /件 5元 /件3/66n生产是为赢利（取得收入）。还有 别的 办法 赢利（取得收入） 。例如，卖出或出租设备 。n问，三种设备卖价 或租价各 应是 多少，进项才不 低于自己生产时的销售收入？n原来的问题： 两种产品各生产多少，利润总额
2、最大？4/66n用 y1、 y2和 y3分别表示 A、 B和 C三种设备单位台时卖价 或 租价，则，总进项 w可表示 成w=4y1 +12y2+18y3 生产两种产品消耗的设备台时的价值（或称出售或出租两种产品所用设备 台时的进项）分别 是 1y1 +0y2+3y3 和 0y1 +2y2+2y3 两种产品售价分别是 3和 5。出售或 出租产品 所用设备台时的 进项不能低于售价。所以，应有1y1 +0y2+3y3 3和 0y1 +2y2+2y3 5从另一个角度看 ， w=4y1 +12y2+18y3是总 消耗。5/66n回答 y1、 y2和 y3各是多少的问题，可表示如下：Min w=4y1 +
3、12y2+18y3 s.t. y1 +3y3 3 2y2 +2y3 5 y1, y2, y3 0 该问题 叫做 原问题 (P)的对偶问题 (D)。可看出，Max z=CX Min w=bTY(P) s.t. AX b (D) s.t. ATY CTX 0 Y 06/66cj 3 5 0 0 0icB xB B-1b x1 x2 x3 x4 x50 x3 2 0 0 1 1/3 -1/35 x2 6 0 1 0 1/2 03 x1 2 1 0 0 -1/3 1/3z 36 0 0 0 -3/2 -1 j若要问对偶问题的解是什么，可以看 解 (P)时得到的 最终 单纯形表 。最终单纯形表7/66从
4、该表松弛变量的检验数行得到：3 =0， 4 = -3/2， 5 = -1，y1 =0， y2 = 3/2， y3 = 1，将其代入 (D):w=40 +123/2+181=36 (1)0 +31 =3 (2)23/2+21 =5 (3)y1, y2, y3 0 (4)这是对偶问题有趣的一个方面。8/66二、对称的 对偶 问题一般形式上面的例子叫做对称的对偶问题。三、非对称的 对偶问题请见教科书第三版第 52页或 第四版 第 53页的表。9/66事项 原问题（对偶问题） 对偶问题（原问题）AbC目 标 函数n个 决策 变 量xj 0xj 0xj无 约 束m个 决策 变 量yi 0yi 0yi无 约 束第二节 对偶理论基本性质一、对称 形式单纯形法矩阵 表达Max z=CX s.t. AX bX 0化成标准形式 Max z=CX+0Xs s.t. AX+IXs=bX， Xs 0Xs =(xs1, xs2, , xsm)T 是 松 弛变量10/66
