对偶线性规划.ppt

第二章对偶线性规划 对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系 互补松弛关系最优解的Kuhn Tucher条件对偶可行基对偶单纯形法对偶的经济解释 DUAL 一 对偶的定义 原始问题minz CTXs t AX bX 0 对偶问题maxy bTWs t ATW CW 0 min b A CT C AT bT max m n m n 二 对偶问题的性质 1 对偶的对偶就是原始问题 2 其他形式问题的对偶 三 原始对偶关系 1 可行解的目标函数值之间的关系设XF WF分别是原始问题和对偶问题的可行解z CTXF WTAXF WTb y2 最优解的目标函数值之间的关系设Xo Wo分别是原始问题和对偶问题的最优解z CTXo WoTAXo WoTb y 3 原始问题和对偶问题最优解之间的互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 互补松弛关系 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 XTWS 0WTXS 0 m n W WS AT I C n A XS I b n m m X 原始问题和对偶问题变量 松弛变量的维数 w1wiwmwm 1wm jwn m x1xjxnxn 1xn ixn m 对偶问题的变量对偶问题的松弛变量 原始问题的变量原始问题的松弛变量 xjwm j 0wixn i 0 i 1 2 m j 1 2 n 在一对变量中 其中一个大于0 另一个一定等于0 Kuhn Tucher条件 3 原始问题和对偶问题最优解的充分必要条件 1 原始可行条件 PFC AX XS bX XS 0 2 对偶可行条件 DFC ATW WS CW WS 0 3 互补松弛条件 CSC XTWS 0WTXS 0 四 对偶单纯形法 1 用单纯形表求解原始问题的四种形式 minz CTXs t AX bX 0 minz CTXs t AX bX 0 maxz CTXs t AX bX 0 maxz CTXs t AX bX 0 2 3 4 1 单纯形表和对偶 1 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 对偶问题 原始问题 引进松弛变量 引进松弛变量 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 WT CBTB 1WST CT WTA minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 minz CTXs t AX bX 0 maxy bTWs t ATW CW 0 单纯形表和对偶 2 对偶问题 原始问题 引进松弛变量 引进松弛变量 minz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 WT CBTB 1WST CT WTA maxz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW 0 WS 0 maxz CTXs t AX bX 0 miny bTWs t ATW CW 0 单纯形表和对偶 3 对偶问题 原始问题 引进松弛变量 引进松弛变量 maxz CTXs t AX XS bX XS 0 miny bTWs t ATW WS CW 0 WS 0 WT CBTB 1WST WTA CT maxz CTXs t AX XS bX XS 0 maxy bTWs t ATW WS CW WS 0 maxz CTXs t AX bX 0 miny bTWs t ATW CW 0 单纯形表和对偶 4 对偶问题 原始问题 引进松弛变量 引进松弛变量 maxz CTXs t AX XS bX XS 0 miny bTWs t ATW WS CW WS 0 WT CBTB 1WST WTA CT 2 对偶单纯形法 初始解原始不可行的问题 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 35对偶问题的最优解为 w1 w2 w3 w4 w5 w6 1 5 7 0 0 0 maxy 35 3 初始解原始 对偶都不可行的问题 解法1 先解决原始可行性 在得到原始可行解时同时得到对偶可行解 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 17对偶问题的最优解为 w1 w2 w3 w4 w5 w6 7 5 10 0 0 0 maxy 17 解法2 先解决对偶可行性 已得到对偶可行解 再用对偶单纯形法求解 得到原始可行解 已获得最优解 x1 x2 x3 x4 x5 x6 5 7 6 0 0 0 minz 17对偶问题的最优解为 w1 w2 w3 w4 w5 w6 7 5 10 0 0 0 maxy 17 五 对偶的经济解释 1 原始问题是利润最大化的生产计划问题 单位产品的利润 元 件 产品产量 件 总利润 元 资源限量 吨 单位产品消耗的资源 吨 件 剩余的资源 吨 消耗的资源 吨 2 对偶问题 资源限量 吨 资源价格 元 吨 总利润 元 对偶问题是资源定价问题 对偶问题的最优解w1 w2 wm称为m种资源的影子价格 ShadowPrice 原始和对偶问题都取得最优解时 最大利润maxz miny 3 资源影子价格的性质 影子价格越大 说明这种资源越是相对紧缺影子价格越小 说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余 这种资源的影子价格一定等于0 w1w2wm 4 产品的机会成本 机会成本表示减少一件产品所节省的资源可以增加的利润 增加单位资源可以增加的利润 减少一件产品可以节省的资源 机会成本 利润 差额成本