运筹学04对偶问题课件.ppt

1、4.1 对偶问题(1) (1) 对偶问题的提出对偶问题的提出例例1 1、生产组织与计划问题、生产组织与计划问题A, BA, B各生产多少各生产多少, , 可获最大利润可获最大利润? ?可用资源可用资源煤煤劳动力劳动力仓库仓库A B1 23 20 2单位利润单位利润40 50306024Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件如果因为某种原因，不愿意自己生产，而希望通如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应过将现有资源承接对外加工来获得收

2、益，那么应如何确定各资源的如何确定各资源的使用价格使用价格？Max Z= 40 x1 +50 x2 x1 + 2x2 30 3x1 + 2x2 60 2x2 24 x1，x2 0s.t目标函数目标函数约束条件约束条件两个原则两个原则1. 所得不得低于生产所得不得低于生产的获利的获利2. 要使对方能够接受要使对方能够接受设三种资源的使用单价分别为设三种资源的使用单价分别为 y1 , y2 , y3y1 y2 y3生产单位产品生产单位产品A A的资源消耗所得不少于单位产品的资源消耗所得不少于单位产品A A的获利的获利生产单位产品生产单位产品B B的资源消耗所得不少于单位产品的资源消耗所得不少于单位

3、产品B B的获利的获利y1 +3 y2 40 2y1 + 2 y2 + 2y3 50 50通过使用所有资源对外加工所获得的收益通过使用所有资源对外加工所获得的收益W = 30y1 + 60 y2 + 24y3根据原则根据原则2 ，对方能够接受的价格显然是越低越好，因此，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：此问题可归结为以下数学模型：Min W = 30y1 + 60 y2 + 24y3 y1 + 3y2 402y1 + 2 y2 + 2y3 50y1 , y2 , y3 0s.t目标函数目标函数约束条件约束条件原线性规划问题称为原线性规划问题称为原问题原问题，此问

4、题为此问题为对偶问题对偶问题，y1 , y2 , y3 称为称为影子价格影子价格(2) (2) 对偶问题的形式对偶问题的形式njxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxjmnmnmmnnnnnn, 2 , 10.221122222121112121112211定义定义 设原线性规划问题为设原线性规划问题为 则称下列线性规划问题则称下列线性规划问题miycyayayacyayayacyayayatsybybybWMininmmnnnmmmmmm, 2 , 10.221122222112112211112211为其对偶问题，其中为其对偶问题，其中yi (i=1,2,m)

5、 称为称为对偶变量对偶变量。上述对偶问题称为上述对偶问题称为对称型对偶问题对称型对偶问题。原问题简记为原问题简记为(P)，对偶问题简记为，对偶问题简记为(D)原始问题原始问题Max Z=CXs.t. AXbX 0bACMaxnm对偶问题对偶问题Min W=Ybs.t.YATCY 0MinCTATbTnm0,94723.6521212121xxxxxxtsxxZMax例例2：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知为对称型对偶问题解：由原问题的结构可知为对称型对偶问题0,62543.9721212121yyyyyytsyyWMin0,94723.652121212

6、1xxxxxxtsxxZMax例例3：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知不是对称型对偶问题，解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。可先化为对称型，再求其对偶规划。0,62543.9721212121yyyyyytsyyWMin0,94723.6521212121xxxxxxtsxxZMax0,94723.6521212121xxxxxxtsxxZMax例例4：求线性规划问：求线性规划问题的对偶规划题的对偶规划解：由原问题的结构可知不是对称型对偶问题，解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划

7、。可先化为对称型，再求其对偶规划。0,94723723.652121212121xxxxxxxxtsxxZMax0,94723723.652121212121xxxxxxxxtsxxZMax上式已为对称型对偶问题，故可写出它的对偶规划上式已为对称型对偶问题，故可写出它的对偶规划 0,6225433.977211211211211yyyyyyyyytsyyyZMin令令111yyy 则上式化为则上式化为0,62543.9721212121yyyyyytsyyZMin无限制0,94723.6521212121xxxxxxtsxxZMax对偶关系对应表对偶关系对应表 原问题原问题 对偶问题对偶问题目

8、标函数类型目标函数类型 Max Min目标函数系数目标函数系数 目标函数系数目标函数系数 右边项系数右边项系数与右边项的对应关系与右边项的对应关系 右边项系数右边项系数 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m 变量数变量数m原问题变量类型与原问题变量类型与 0 对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束 的对应关系的对应关系 无限制无限制 原问题约束类型与原问题约束类型与 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 无限制无限制4.2 对偶问题的基本性质定理

9、定理1 1 对偶问题的对偶就是原问题对偶问题的对偶就是原问题Max W=-Ybs.t. -YA-CY0Min Z=-CXs.t. -AX-bX 0Max Z=CXs.t. AX bX 0Min W=Ybs.t. YA C Y0对偶的定义对偶的定义对偶的定义对偶的定义定理定理2 2 ( (弱对偶定理弱对偶定理) )分别为分别为(P), (D)的可行解，则有的可行解，则有C bX， yX y证明：由证明：由AX b, y 0 有有 yAX b y 由由 Ay C, X 0 有有 y A X C X所以所以C X y A X yb推论推论2、(P)有可行解有可行解, 但无有限最优解，则但无有限最优解

10、，则(D)无可无可行解。行解。定理定理3、 yX,分别为分别为(P), (D)的可行解，且的可行解，且X yC=b, 则它们是则它们是(P), (D) 的最优解。的最优解。证明：对任证明：对任X，有，有CX b y =CXX最优最优推论推论1、(P), (D)都有可行解，则必都有最优解。都有可行解，则必都有最优解。定理定理4 4( (主对偶定理主对偶定理) )若一对对偶问题若一对对偶问题(P)(P)和和(D)(D)都有可行解，则它们都都有可行解，则它们都有最优解，且目标函数的最优值必相等。有最优解，且目标函数的最优值必相等。证明：证明： (1) 当当X*和和Y*为原问题和对偶问题的一个可行解为

11、原问题和对偶问题的一个可行解有有bAX CYAYbYAX CXYAX YbYAXCX原问题目标函数值原问题目标函数值对偶问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。最优解；对偶问题有下界，也存在有限最优解。(2) 当当X*为原问题的一个最优解，为原问题的一个最优解，B为相应的最优基为相应的最优基,通通过引入松弛变量过引入松弛变量Xs,将问题将问题(P)转化为标准型转化为标准型0,.0sssXXbIXAXtsXCXZMax令令sXXX*00111BCABCCIABCCBBB0011A

12、BCCBCBB01BCB令令01BCYB0AYCCAY所以所以Y*是对偶问题的可行解，是对偶问题的可行解，对偶问题的目标函数值为对偶问题的目标函数值为bBCbYWB1X*是原问题的最优解，原是原问题的最优解，原问题的目标函数值为问题的目标函数值为bBCCXZB1WZ推论：推论：若一对对偶问题中的任意一个有最优解，则另一个若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：一对对偶问题的关系，有且仅有下列三种：1.1. 都有最优解，且目标函数最优值相等；都有最优解，且目标函数最优值相等；2.2. 两

13、个都无可行解；两个都无可行解；3.3. 一个问题无界，则另一问题无可行解。一个问题无界，则另一问题无可行解。定理定理5 若若 X , Y分别为分别为(P) , (D)的可行解，则的可行解，则X , Y为为最优解的充要条件是最优解的充要条件是00XCYAAXbY同时同时成立成立证证: (: (必要性）必要性）原问题原问题 对偶问题对偶问题0,.ssXXbXAXtsCXZMax0,.ssYYcYYAtsYbWMinbXAXsCYYAsAXbXsCYAYsYbYXYAXsCXXYYAXs0XYYXssMax Z=CXs.t.AX+XS=bX, XS 0Min W=Ybs.t. ATY-YS=CW,

14、WS 0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数原始问题和对偶问题变量、松弛变量的维数 y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 04.3 对偶问题的解0,.0sssXXbIXAXts

15、XCXZMax令令sXXX*设原问题为设原问题为为原问为原问题的一题的一最优解最优解则则1BCYB为对偶问题为对偶问题0.YCYAtsYbWMin的一最优解的一最优解CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN-CBB-1N-CBB-1例例1 Max Z=40X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.ty1y2y3Min W = 30y1+ 60y2 + 24y3 y1+3y2 + 0y3 402y1+2y2 + 2y3 50 y1 , y2 , y3 0 0s.tMax W = -30y1- 6

16、0y2 - 24y3 y1+3y2 + 0y3 y4 = = 402y1+2y2 + 2y3 y5 = = 50 y1 , y2 , y3 , y4 , y5 0 0s.tMax W = -30y1- 60y2 - 24y3 +0(y4 + y5 )-M (y6 + y7 ) y1+3y2 + 0y3 y4 + y6 = = 402y1+2y2 + 2y3 y5 + y7 = = 50 y1 , y2 , y3 , y4 , y5 0 0s.tC-30-60-2400-M-MCByBby1y2y3y4y5y6y7-My640130-101040/3-My7502220-10125Z-90M-3

17、0+3M-60+5M-24+2MMM00 C-30-60-2400-M-MCByBby1y2y3y4y5y6y7-60y240/31/310-1/301/30 -My770/34/3022/3-1-2/31 Z-800-70M/3-10+4M/30-24+2M2M/3-M 0 -60y240/31/310-1/301/3040-24y335/32/3011/3-1/2-1/31/235/2Z-1080600-12-12 -60y215/201-1/2-1/21/41/6-1/4 -30y135/2103/21/2-3/4-1/23/4 Z-97500-9-15-15/2 例例1、Max Z=4

18、0X1+ 50X2 X1+2X2 303X1+2X2 60 2X2 24 X1 , X2 0 0s.t X1+2X2 +X3 = 303X1+2X2 +X4 =60 2X2 +X5 = 24 X1 X5 0 0s.tCBXBBX1X2X3X4X540X115101/2-1/20 0X59003/2-1/21 50X215/297501-3/41/40 Z 0 0 -35/2-15/2 0 ,0,02 21515, ,2 23535y y, ,y y, ,y yY Y3 32 21 11B21515900000215235900215150215235005432154321yyyyyyxxxx

19、xxssCY y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量xjym+j=0yixn+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0 0，另一个一定等于，另一个一定等于0 00,10527.532321321321321XXXXXXXXXtsXXXZMax010527.)(5326165321432164321XXXXXXXXXXXtsXXMXXXZMaxC23-

20、5-M0-MCBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115Z-17M2+3M3-4M2M-50-M0 -MX4207/21/211/2-1/24/72X151-5/21/20-1/21/2 Z2M-1003M/2+8M/2-60M/2+1-3M/2-1 3X24/7011/72/71/7-1/7 2X145/7106/75/7-1/71/7 Z102/700-50/7-M-16/7-1/7-M+1/7 0,10527.532321321321321XXXXXXXXXtsXXXZMax(P)0,53522.1072121212121yyyyyyyytsy

21、yWMin无限制0, 0,53522.1075432152142132121yyyyyyyyyyyyyytsyyWMin无限制750007171600007474571717167500054321654321yyyyyyxxxxxxxMMssCY4.4 影子价格(1) (1) 原始问题是利润最大化的生产计划问题原始问题是利润最大化的生产计划问题0. .21212211222222121111212111222211mnnnnmmnnmnmmnnnnnnxxxxxxbxxaxaxabxxaxaxabxxaxaxat sxcxcxcZMax单位产品的利润（元单位产品的利润（元/ /件）件）产品产

22、量（件）产品产量（件）总利润（元）总利润（元）资源限量（吨）资源限量（吨）单位产品消耗的资源（吨单位产品消耗的资源（吨/ /件）件）剩余的资源（吨）剩余的资源（吨）消耗的资源（吨）消耗的资源（吨）(2) 对偶问题对偶问题0. .212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayat sybybybWMin资源限量（吨）资源限量（吨）资源价格（元资源价格（元/吨）吨）总利润（元）总利润（元）对偶问题是资源定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、y

23、m称为称为m种资源的种资源的影子价格（影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润原始和对偶问题都取得最优解时，最大利润 Max Z=Min W(3) (3) 资源影子价格的性质资源影子价格的性质 影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0 0种资源的边际利润第种资源的增量第最大利润的增量iibzyiooimmiiybybybybWZ2

24、211mmiiiybybbybybZZ)(2211iiybZy1y2ym(4) (4) 产品的机会成本产品的机会成本机会成本机会成本表示减少一件产品所节省的资源可以增加的利润表示减少一件产品所节省的资源可以增加的利润mmjiijjjyayayaya2211增加单位资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源减少一件产品可以节省的资源0 xxxxbxaxaxaxabxaxaxaxabxaxaxaxas.t.xcxcxcxczmaxnj21mnmnjmj2m21m12n2nj2j2221211n1nj1j212111nnjj2211机会成本机会成本利润利润差额成本差额成本

25、0. .212122112222221121112211112211nmmmmnnmmmnnnmmmmmmmmyyyyyycyyayayacyyayayacyyayayat sybybybWMin(5) 产品的差额成本（产品的差额成本（Reduced Cost）差额成本差额成本=机会成本机会成本 - 利润利润jjTjmjmjjjmcaycayayayy)(2211(6) 互补松弛关系的经济解释互补松弛关系的经济解释0000000000jjmjmjjmjiininiinixyyxyxyxxyxy在利润最大化的生产计划中在利润最大化的生产计划中（1）边际利润大于）边际利润大于0的资源没有剩余的资源

26、没有剩余（2）有剩余的资源边际利润等于）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产）机会成本大于利润的产品不安排生产4.5 对偶单纯形法n定义：设定义：设A=(B N)，其中，其中B是一个非奇异的是一个非奇异的m m阶阶方阵，对应地方阵，对应地C=(CB CN)，则，则YB=CB的解的解Y*=CBB-1称称为对偶问题为对偶问题(D)的一个基本解；若的一个基本解；若Y*还满足还满足Y*NCN，则称则称Y*为为(D)的一个基可行解；若有的一个基可行解；若有Y*NCN，则称，则称Y*为非退化的基可行解，否则称为

27、退化的基可行解。为非退化的基可行解，否则称为退化的基可行解。(1) (1) 对偶单纯形法的基本原理对偶单纯形法的基本原理l定义：如果原问题定义：如果原问题(P)的一个基本解的一个基本解X与对偶问题与对偶问题(D)的基的基可行解可行解Y对应的检验数向量满足条件对应的检验数向量满足条件l则称则称X为原问题为原问题(P)的一个正则解。的一个正则解。001NBCCBNNB原问题原问题(P)的正则解的正则解X与对偶问题与对偶问题(D)的基可行解的基可行解Y一一对应一一对应对偶单纯形法的基本思想对偶单纯形法的基本思想v 从原规划的一个基本解出发，此基本解不一定可行从原规划的一个基本解出发，此基本解不一定可

28、行( (正则正则解解) )，但它对应着一个对偶基可行解（检验数非正），所，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。应着另一个对偶基可行解（检验数非正）。v 如果得到的正则解的分量皆非负则该正则解为最优解。如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯

29、形法在迭代过程中始终保持对偶解也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。解时，便得到原规划的最优解。(2) (2) 对偶单纯形法的迭代步骤对偶单纯形法的迭代步骤1. 建立初始对偶单纯形表建立初始对偶单纯形表,对应一个基本解对应一个基本解,所有检验数所有检验数均非正均非正,转转2；2. 若若b0,则得到最优解则得到最优解,停止停止;否则否则,若有若有bk0则选则选k行的行的

30、基变量为出基变量基变量为出基变量,转转33. 若所有若所有akj0( j = 1,2,n )，则原问题无可行解，则原问题无可行解,停止停止;否则否则,若有若有akj0 则选则选 =min j / akjakj0= r/akr 那么那么xr为进基变量为进基变量,转转4；4. 以以akr为转轴元为转轴元,作矩阵行变换使其变为作矩阵行变换使其变为1,该列其他元该列其他元变为变为0,转转2。例例0,4232.432321321321321xxxxxxxxxtsxxxfMin解：将上式标准化解：将上式标准化0,4232.4325432153214321321xxxxxxxxxxxxxtsxxxfMaxC

31、-2-3-400CBXBbX1X2X3X4X50X4-3-1-2-1100X5-4-21-301-f0-2-3-4000X4-10-5/21/21-1/2-2X121-1/23/20-1/2-f-40-4-10-1-3X22/501-1/5-2/51/5-2X111/5101/5-1/5-2/5-f-28/500-9/5-8/5-1/50,10527.532321321321321XXXXXXXXXtsXXXZMax0,10527.532321532143214321XXXXXXXXXXXtsMXXXXZMaxC23-5-M0CBXBbX1X2X3X4X5-MX47111100X5-10-25

32、-101Z-7M2+M3+M-5+M003X27111100X5-45-70-6-51Z21-10-8-M-303X24/7011/72/71/72X145/7106/75/7-1/7Z102/700-50/7-M-16/7-1/7是是是是是是是是否否否否否否否否所有所有所有所有得到得到最优解最优解计算计算计算计算典式对应原规划的典式对应原规划的基本解是可行的基本解是可行的典式对应原规划的基典式对应原规划的基本解的检验数本解的检验数所有所有所有所有计算计算计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代停停没没有有最最优优解解没没有有最最优优解解单纯形法单纯形法对偶单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min精品课件精品课件！精品课件精品课件！n第四章作业第四章作业n1（选（选2）、）、2、4、6、8、9（选（选2）