运筹学对偶问题

运筹学对偶问题第1页，课件共47页，创作于2023年2月4.1对偶问题(1)对偶问题的提出例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024第2页，课件共47页，创作于2023年2月Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的使用价格？第3页，课件共47页，创作于2023年2月Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件两个原则所得不得低于生产的获利要使对方能够接受设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y240

2y1+2y2+2y350第4页，课件共47页，创作于2023年2月通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3称为影子价格第5页，课件共47页，创作于2023年2月(2)对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)第6页，课件共47页，创作于2023年2月原始问题MaxZ=CXs.t.AX≤b X≥0bAC≤Maxnm对偶问题MinW=Ybs.t. YAT≥C Y≥0≥MinCTATbTnm第7页，课件共47页，创作于2023年2月例2：求线性规划问题的对偶规划解：由原问题的结构可知为对称型对偶问题第8页，课件共47页，创作于2023年2月例3：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。第9页，课件共47页，创作于2023年2月例4：求线性规划问题的对偶规划解：由原问题的结构可知不是对称型对偶问题，可先化为对称型，再求其对偶规划。第10页，课件共47页，创作于2023年2月上式已为对称型对偶问题，故可写出它的对偶规划令则上式化为第11页，课件共47页，创作于2023年2月对偶关系对应表原问题对偶问题目标函数类型MaxMin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与

0

对偶问题约束类型变量

0约束

的对应关系无限制＝原问题约束类型与

0对偶问题变量类型约束

变量

0的对应关系＝无限制第12页，课件共47页，创作于2023年2月4.2对偶问题的基本性质定理1对偶问题的对偶就是原问题MaxW’=-Ybs.t.-YA≤-C Y≥0MinZ’=-CXs.t.-AX≥-b X≥0MaxZ=CXs.t.AX≤b X≥0MinW=Ybs.t.YA≥C Y≥0对偶的定义对偶的定义第13页，课件共47页，创作于2023年2月定理2(弱对偶定理)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb第14页，课件共47页，创作于2023年2月推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理3、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)的最优解。证明：对任X，有CXby=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。第15页，课件共47页，创作于2023年2月定理4(主对偶定理)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明：(1)当X*和Y*为原问题和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。第16页，课件共47页，创作于2023年2月(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型令令所以Y*是对偶问题的可行解，对偶问题的目标函数值为X*是原问题的最优解，原问题的目标函数值为第17页，课件共47页，创作于2023年2月推论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。第18页，课件共47页，创作于2023年2月定理5若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是同时成立证:(必要性）原问题对偶问题第19页，课件共47页，创作于2023年2月MaxZ=CXs.t. AX+XS=b X,XS≥0MinW=Ybs.t.ATY-YS=C W,WS

≥0XTYS=0YTXS=0mn=YYSAT-ICn=AXSIbnmmX原始问题和对偶问题变量、松弛变量的维数第20页，课件共47页，创作于2023年2月y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0第21页，课件共47页，创作于2023年2月4.3对偶问题的解令设原问题为为原问题的一最优解则为对偶问题的一最优解CCBCN0CBXBbXBXNXSCBXBB-1bIB-1NB-1ZCBB-1b0CN-CBB-1N-CBB-1第22页，课件共47页，创作于2023年2月例1MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.ty1y2y3MinW=30y1+60y2+24y3

y1+3y2+0y3

402y1+2y2+2y3

50

y1,y2,y30s.tMaxW’=-30y1-60y2-24y3

y1+3y2+0y3–y4

=402y1+2y2+2y3

–y5

=50y1,y2,y3,y4,y50s.t第23页，课件共47页，创作于2023年2月MaxW’=-30y1-60y2-24y3+0(y4+

y5)-M(y6+

y7)

y1+3y2+0y3–y4+

y6

=402y1+2y2+2y3

–y5

+

y7

=50y1,y2,y3,y4,y50s.tC-30-60-2400-M-MθCByBby1y2y3y4y5y6y7-My640130-101040/3-My7502220-10125Z-90M-30+3M-60+5M-24+2MMM00

第24页，课件共47页，创作于2023年2月C-30-60-2400-M-MθCByBby1y2y3y4y5y6y7-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

第25页，课件共47页，创作于2023年2月例1、MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.tX1+2X2+X3=303X1+2X2+X4=602X2+X5=24

X1–X50s.tCBXBBX1X2X3X4X5θ40X115101/2-1/20

0X59003/2-1/21

50X215/297501-3/41/40

Z

0

0

-35/2-15/2

0

第26页，课件共47页，创作于2023年2月第27页，课件共47页，创作于2023年2月y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0第28页，课件共47页，创作于2023年2月第29页，课件共47页，创作于2023年2月C23-5-M0-MθCBXBbX1X2X3X4X5X6-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

第30页，课件共47页，创作于2023年2月(P)第31页，课件共47页，创作于2023年2月第32页，课件共47页，创作于2023年2月4.4影子价格(1)原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第33页，课件共47页，创作于2023年2月(2)对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润MaxZ=MinW第34页，课件共47页，创作于2023年2月(3)资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0第35页，课件共47页，创作于2023年2月y1y2ym(4)产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源第36页，课件共47页，创作于2023年2月机会成本利润差额成本(5)产品的差额成本（ReducedCost）差额成本=机会成本-利润第37页，课件共47页，创作于2023年2月(6)互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产第38页，课件共47页，创作于2023年2月4.5对偶单纯形法定义：设A=(BN)，其中B是一个非奇异的m×m阶方阵，对应地C=(CBCN)，则YB=CB的解Y*=CBB-1称为对偶问题(D)的一个基本解；若Y*还满足Y*N≧CN，则称Y*为(D)的一个基可行解；若有Y*N>CN，则称Y*为非退化的基可行解，否则称为退化的基可行解。(1)对偶单纯形法的基本原理定义：如果原问题(P)的一个基本解X与对偶问题(D)的基可行解Y对应的检验数向量满足条件则称X为原问题(P)的一个正则解。原问题(P)的正则解X与对偶问题(D)的基可行解Y一一对应第39页，课件共47页，创作于2023年2月对偶单纯形法的基本思想从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。第40页，课件共47页，创作于2023年2月(2)对偶单纯形法的迭代步骤建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；若b’≥0,则得到最优解,停止;否则,若有bk<0则选k行的基变量为出基变量,转3若所有akj’≥0(j=1,2,…,n)，则原问题无可行解,停止;否则,若有akj’<0则选=min{j’/akj’┃akj’<0}=r’/akr’那么x