对偶理论与灵敏度分析

关于对偶理论与灵敏度分析第一页，共四十二页，编辑于2023年，星期一

第一章例1中：美佳公司利用自身资源生产两种家电产品，其线形规划问题表示为：maxz=2x1+x2

5x2≤15

St.6x1+2x2≤24

x1

＋x2≤5

x1、x2≥0

现假定有某公司想把美佳公司的资源买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。设y1、y2和y3代表单位时间设备A、设备B和调试工序的出让代价，则6y2＋y3≥2、5y1+2y2+y3≥1；另外要求，minz=15y1+24y2+5y3，且y1、y2、y3≥0即minz=15y1+24y2+5y36y2＋y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.§2.1线性规划的对偶问题对偶问题的提出第二页，共四十二页，编辑于2023年，星期一maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.对称形式的对偶问题对称形式变量非负，求极大时约束条件取≤号、求极小时约束条件取≥号.Maxz=(2,1)x1x205211x1x2≤15245(x1x2)T≥0

minw=(15,24,5)y1y2y3061521y1y2y3≥21(y1y2y3)T≥0

第三页，共四十二页，编辑于2023年，星期一Maxz=CXAX≤bX≥0st.minw=YTbATY≥CTY≥0st.Maxz=c1

x1+c2

x2+…….+cnxna11x1+a12

x2+……..+a1n

xn≤b1

a21x1+a22

x2+……..+a2n

xn≤b2

…………………am1x1+am2

x2+……..+amnxn≤bmx1,x2,……xn≥0Minw=b1

y1+b2

y2+…….+bmyma11y1+a21

y2+……..+am1

ym≥c1

a12y1+a22

y2+……..+am2

ym≥c2…………………a1ny1+a2n

y2+……..+amn

ym≥cny1,y2,……ym≥0对称形式的对偶问题第四页，共四十二页，编辑于2023年，星期一1,若原问题目标是求极大化，则对偶问题的目标是极小化，反之亦然。2,原问题的约束系数矩阵与对偶问题的约束系数矩阵互为转置矩阵。3,极大化问题的每个约束对应于极小化问题的一个变量，其每个变量对应于对偶问题的一个约束。4,原问题与对偶问题互为对偶问题。对偶问题的特点Maxz=CXAX≤bX≥0St.Minz'=-CX-AX≥-bX≥0st.Maxw'=-YTb-ATY≤-CTY≥0st.minw=YTbATY≥CTY≥0st.求对偶标准化求对偶标准化第五页，共四十二页，编辑于2023年，星期一非对称形式的对偶问题maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.第六页，共四十二页，编辑于2023年，星期一原问题对偶问题目标函数maxmin目标函数约束条件≤≥=≥≤无约束变量变量≥≤无约束≥≤

=约束条件非对称形式的对偶问题第七页，共四十二页，编辑于2023年，星期一若互为对偶的线性规划分别有可行解则其相应的目标函数值满足性质1弱对偶性§2.2对偶问题的基本性质第八页，共四十二页，编辑于2023年，星期一推论1

极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。

推论2

极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推论推论3

若原始问题可行，则其目标函数无界的充要条件是对偶问题没有可行解。第九页，共四十二页，编辑于2023年，星期一若X和Y分别是互为对偶的线性规划的可行解，且使CX=Yb，则X和Y分别是相应线性规划问题的最优解。性质2：最优性准则若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相同。若原问题最优基为B，则其对偶问题最优解Y*=CBB-1性质3：强对偶性（对偶定理）第十页，共四十二页，编辑于2023年，星期一性质4：互补松弛性最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.最优解X*=(x1,x2,x3,x4,x5)

＝(7/2,3/2,15/2,0,0)minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.最优解y*=(y1,y2,y3,y4,y5)

＝(0,1/4,1/2,0,0)y1＝0y2＝1/4y3＝1/2x1＝7/2x2＝3/2第十一页，共四十二页，编辑于2023年，星期一§2.3影子价格maxz=2x1+x2

5x2≤156x1+2x2≤24

x1+x2≤5x1、x2≥0St.minz=15y1+24y2+5y36y2+y3≥25y1+2y2+y3≥1y1、y2、y3≥0St.最优解X*=(x1,x2,x3,x4,x5)＝(7/2,3/2,15/20,0)，最优值:Z*=17/2最终表21000CB

基bx1

x2x3x4x5021x3

x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj－zj000-1/4-1/2原问题对偶问题最终表-15-24-500CB

基by1

y2y3y4y5-24-5y2

y31/41/2-5/415/21001-1/41/21/4-3/2cj－zj-15/200-7/2-3/2最优解y*=(y1,y2,y3,y4,y5)＝(0,1/4,1/2,0,0)，最优值:Z*=17/2第十二页，共四十二页，编辑于2023年，星期一当线形规划原问题与对偶问题同时取得最优解时，其对偶最优解y＊i

代表在资源最优利用条件下对单位第i种资源的估价，这个估价称为这种资源的影子价格。其经济意义是：在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。第十三页，共四十二页，编辑于2023年，星期一原问题是利润最大化的生产计划问题Maxz=c1

x1+c2

x2+…….+cnxna11x1+a12

x2+……..+a1n

xn+xn+1=b1

a21x1+a22

x2+……..+a2n

xn+xn+2=b2

……………..……am1x1+am2

x2+……..+amnxn+xn+m=bmx1,x2,……xn+m≥0总利润（元）单位产品的利润（元/件）产品产量（件）消耗的资源（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）资源限量（吨）第十四页，共四十二页，编辑于2023年，星期一Minw=b1

y1+b2

y2+…….+bmyma11y1+a21

y2+……..+am1

ym–ym+1=c1

a12y1+a22

y2+……..+am2

ym–ym+2=c2…………….…a1ny1+a2n

y2+……..+amn

ym–ym+n=cny1,y2,……ym+n≥0资源价格（元/吨）资源限量（吨）总利润（元）对偶问题的最优解y1、y2、...、ym称为m种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，最大利润maxz=miny对偶问题是资源定价问题第十五页，共四十二页，编辑于2023年，星期一1、影子价格依赖于资源的利用情况，各企业不同。影子价格的经济解释2、影子价格表示的是资源的一种边际价格。影子价格越大，说明这种资源越是相对紧缺；影子价格越小，说明这种资源相对不紧缺若某种资源影子价格为零，则说明此资源未得到充分利用；若不为零，则表明该资源得到充分利用。第十六页，共四十二页，编辑于2023年，星期一y1y2ym增加单位资源可以增加的利润减少一件产品可以节省的资源3、影子价格代表一种机会成本机会成本a1jy1+a2jy2+……aijyi+……amjym表示减少一件产品所节省的资源可以增加的利润第十七页，共四十二页，编辑于2023年，星期一机会成本利润差额成本4、产品的差额成本（ReducedCost）差额成本=机会成本-利润第十八页，共四十二页，编辑于2023年，星期一在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产影子价格的经济含义第十九页，共四十二页，编辑于2023年，星期一在单纯形法中，原问题的最优解满足：

（1）是基本解；

（2）可行；

（3）检验数≤0（YA≥C），即对偶解可行。单纯形算法是从满足（1）、（2）的一个基可行解出发，转换到另一个基可行解，一直迭代到（3）得到满足，即对偶解可行为止。对偶单纯形法则是从满足（1）、（3）的一个对偶可行解出发，以基变量值是否全非负为检验数，连续迭代到（2）得到满足，即原问题的基解可行为止。两种算法结果是一样的，区别是对偶单纯形法的初始解不一定可行，只要求所有检验数都非正，在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基解可行，从而取得问题的最优解§2.4对偶单纯形法第二十页，共四十二页，编辑于2023年，星期一单纯形法与对偶单纯形法比较第二十一页，共四十二页，编辑于2023年，星期一单纯形法的步骤第二十二页，共四十二页，编辑于2023年，星期一对偶单纯形法的步骤第二十三页，共四十二页，编辑于2023年，星期一如何用？第二十四页，共四十二页，编辑于2023年，星期一例:cj-2-3-400CBXBbx1x2x3x4x50X4-3-1-2-1100x5-4-21-301σj-2-3-400θ14/3[]0x4-2x112-1/23/20-1/2-10-5/21/21-1/2σj0-2-10-1θ4/52-3x2-2x1[]12/50-1/5-2/51/511/5107/5-1/5-2/5σj00-9/5-8/5-1/5所以：X*=(x1,x2)T=(11/5,2/5)TZ*=28/5第二十五页，共四十二页，编辑于2023年，星期一如何用？第二十六页，共四十二页，编辑于2023年，星期一对应B的基解：存在检验数>0不可行单纯形法对偶单纯形法？××第二十七页，共四十二页，编辑于2023年，星期一用大M法求解或用两阶段法求解第二十八页，共四十二页，编辑于2023年，星期一灵敏度分析的两把尺子：σj=Cj-CBB-1pj≤0；

xB=B-1b≥0假设每次只有一种系数变化■价值系数C变化（单位产品利润变化）■右端常数b变化（资源拥有量变化）§2.5灵敏度分析（Lindo求解）当系数A，b，C发生改变时，目前最优基是否还最优？为保持目前最优基不变，系数A，b，C的允许变化范围是什么？第二十九页，共四十二页，编辑于2023年，星期一第一章例1中，若家电Ⅰ的利润降至1.5元/件，家电Ⅱ的利润增至2元/件，最优生产计划是否改变；原最终表1.52000CB

基bx1

x2x3x4x501.52x3

x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2cj－zj0001/8-9/41.52000CB

基bx1

x2x3x4x501.52x4

x1x26230100014/5-1/51/5100-610cj－zj00-1/100-3/2价值系数变化C第三十页，共四十二页，编辑于2023年，星期一右端常数变化b第一章例1中，若其它资源不变，而设备B的能力增加到32h，分析公司最优计划的变化；△b′=B-1△b=15/4-15/201/4-1/20-1/43/2080102-2=21000CB

基bx1

x2x3x4x5021x3

x1x215/2+107/2+23/2-20100011005/41/4-1/4-15/2-1/23/2cj－zj000-1/4-1/2020x3

x1x4155201051-410000101-6cj－zj0-100-2第三十一页，共四十二页，编辑于2023年，星期一灵敏度分析Lindo第一章例1，美佳公司生产状况如下表项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE

1)8.500000

VARIABLEVALUEREDUCEDCOSTX13.5000000.000000X21.5000000.000000

ROWSLACKORSURPLUSDUALPRICES2)7.5000000.0000003)0.0000000.2500004)0.0000000.500000

NO.ITERATIONS=2max2x1+x2st2)5x2<=153)6x1+2x2<=244)x1+x2<=5end第三十二页，共四十二页，编辑于2023年，星期一RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX12.0000001.0000001.000000X21.0000001.0000000.333333RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE215.000000INFINITY7.500000324.0000006.0000006.00000045.0000001.0000001.000000max2x1+x2st2)5x2<=153)6x1+2x2<=244)x1+x2<=5endTHETABLEAU

ROW(BASIS)X1X2SLK2SLK3SLK41ART0.0000.0000.0000.2500.5008.5002SLK20.0000.0001.0001.250-7.5007.5003X11.0000.0000.0000.250-0.5003.5004X20.0001.0000.000-0.2501.5001.500第三十三页，共四十二页，编辑于2023年，星期一DAKOTA家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？

每个书桌每个餐桌每个椅子资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20

用DESKS、TABLES和CHAIRS分别表示三种产品的生产量，建立LP模型，输入如下。MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十四页，共四十二页，编辑于2023年，星期一LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE

1)280.0000

VARIABLEVALUEREDUCEDCOSTDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000

ROWSLACKORSURPLUSDUALPRICES2)24.0000000.0000003)0.00000010.0000004)0.00000010.0000005)5.0000000.000000

NO.ITERATIONS=2MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十五页，共四十二页，编辑于2023年，星期一RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEDESKS60.00000020.0000004.000000TABLES30.0000005.000000INFINITYCHAIRS20.0000002.5000005.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE248.000000INFINITY24.000000320.0000004.0000004.00000048.0000002.0000001.33333355.000000INFINITY5.000000MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十六页，共四十二页，编辑于2023年，星期一THETABLEAU

ROW(BASIS)DESKSTABLESCHAIRSSLK2SLK3SLK4SLK51ART0.0005.0000.0000.00010.00010.0000.000280.0002SLK20.000-2.0000.0001.0002.000-8.0000.00024.0003CHAIRS0.000-2.0001.0000.0002.000-4.0000.0008.0004DESKS1.0001.2500.0000.000-0.5001.5000.0002.0005SLK50.0001.0000.0000.0000.0000.0001.0005.000MAX60DESKS+30TABLES+20CHAIRSST2)8DESKS+6TABLES+CHAIRS<=483)4DESKS+2TABLES+1.5CHAIRS<=204)2DESKS+1.5TABLES+0.5CHAIRS<=85)TABLES<=5END第三十七页，共四十二页，编辑于2023年，星期一

奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。

试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：

1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？

2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？

3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？

补充问题设用x1桶牛奶加工A1，用x2桶牛奶加工A2；maxz=72x1+64x2x1+x2≤5012x1+8x2≤4803x1≤100x1,x2≥0St.max72x1+64x2stmilk)x1+x2<=50time)12x1+8x2<=480shop)3x1<=100end第三十八页，共四十二页，编辑于2023年，星期一LPOPTIMUMFOUNDATSTEP2

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLE