运筹学对偶理论习题

《运筹学对偶理论习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划的对偶理论2.1写出下列线性规划问题的对偶问题maxz=2x1+2x2－4x3x1+3x2+3x3≤304x1+2x2+4x3≤80x1、x2，x3≥0解：其对偶问题为minw=30y1+80y2y1+4y2≥23y1+2y2≥23y1+4y2≥－4y1、y2≥02.2写出下列线性规划问题的对偶问题minz=2x1+8x2－4x3x1+3x2－3x3≥30－x1+5x2+4x3=804x1+2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为maxw=30y1+80y2+50y3y1－y2+4y3≥23

2、y1+5y2+2y3≤8－3y1+4y2－4y3=－4y1≥0，y2无限制，y3≤02.3已知线性规划问题maxz=x1+2x2+3x3+4x4x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。解：其对偶问题为minw=20y1+20y2y1+2y2≥1（1）2y1+y2≥2（2）2y1+3y2≥3（3）3y1+2y2≥4（4）y1、y2≥0将y1*=6/5，y2*=1/5代入上述约束条件，得（

3、1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以2x3*+3x4*=203x3*+2x4*=20解得x3*=x4*=4。故原问题的最优解为X*=（0，0，4，4）T2.4用对偶单纯形法求解下列线性规划minz=4x1+2x2+6x32x1+4x2+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0解将问题改写成如下形式max（－z）=－4x1－2x2－6x3－2x1－4x2－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2

4、，x3，x4，x5≥0显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表2—7中。表2—7Cj－4－2－600bCBXBx1x2x3x4x50x4-2[-4]-810-240x5-4-1-401-8－z-4-2-6000θ-4/-2-2/-4-6/-1000-2x21/212-1/4060x5-7/20[-2]-1/41-2－z-30-2-1/20-120θ-3/(-7/2)0-2/-2(-1/2)/(-1/4)0-2x2-310-1/214

5、-6x37/4011/8-1/24－z-1/200-1/4-1-32最后一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为X*=（0，4，4）T最优值为z*=322.5设某线性规划问题的初始单纯形表和最优单纯形表分别为表2—9（初始单纯形表）Cj54300bCBXBx1x2x3x4x50x411110600x52140180－z543000表2—10（最优单纯形表）Cj54300bCBXBx1x2x3x4x54x201-22-1405x1103-1120－z00-4-3-1-260现在要问：（1）c3在什么范围内变化，

6、表中最优解不变？（2）c3从3变为8，求新的最优解解（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数σ3=－4，因此当Δc3≤－σ3=4时，表中最优解不变。（2）当c3从3变为8时，则表中的检验数σ3从—4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表2—11中所示的新的最优解。表2—11Cj54800bCBXBx1x2x3x4x54x201-22-1405x110[3]-1120－z001-3-1-2604x22/3104/3-1/3160/35x31/301-1/31/320/3－z0

7、0-4-3-1-740/3即新的最优解为X*=（0，160/3，20/3）T。2.6某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的A、B、C三种原材料的数量以及单位产品的利润如下表所示：表2—12产品单位消耗原材料甲乙资源限量（kg）ABC121311908045单位产品利润（千元/件）54若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为：maxz=5x1+4x2  x1+3x2≤902x1  +x2≤80  x1  +x2≤45x1、x2，x3≥0用单纯形法求解该问题时，其初

8、始单纯形表和最优单纯形表分别如表2—13和3—14所示，试分析使最优基不变的b3的变化范围。表2—13（初始单纯形表）Cj54000bCBXBx1x2x3x4x50x313100900x421010800x51100145－z540000表2—14