运筹学对偶理论习题.doc

第二章 线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x2－4x3x1 + 3x2 + 3x3 ≤304x1 + 2x2 + 4x3≤80x1、x2，x3≥0解：其对偶问题为min w=30y1+ 80y2y1+ 4y2 ≥23y1 + 2y2 ≥23y1 + 4y2 ≥－4y1、y2≥02.2 写出下列线性规划问题的对偶问题 min z=2x1+8x2－4x3x1 + 3x2－3x3 ≥30－x1 + 5x2 + 4x3 = 804x1 + 2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3 y1－ y2 + 4 y3 ≥23y1+5y2 + 2y3 ≤8－3y1 + 4y2－4y3 =－4y1≥0，y2无限制，y3≤02.3 已知线性规划问题 max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4≤202x1 + x2 + 3x3 +2x4≤20x1、x2，x3，x4≥0其对偶问题的最优解为y1*=6/5，y2*=1/5试用互补松弛定理求该线性规划问题的最优解。

解：其对偶问题为min w=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代入上述约束条件，得（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 用对偶单纯形法求解下列线性规划 min z=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，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-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在什么范围内变化，表中最优解不变？（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－z00-4-3-1-740/3即新的最优解为X*=（0，160/3，20/3）T2.6 某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的A、B、C三种原材料的数量以及单位产品的利润如下表所示： 表2—12产品单位消耗原材料甲乙资源限量（kg）ABC121311908045单位产品利润（千元/件）54若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为： max z=5x1+4x2  x1 +3x2 ≤902x1  + x2 ≤80  x1  + x2 ≤45x1、x2，x3≥0用单纯形法求解该问题时，其初始单纯形表和最优单纯形表分别如表2—13和3—14所示，试分析使最优基不变的b3的变化范围。

表2—13（初始单纯形表）Cj54000bCBXBx1x2x3x4x50x313100900x421010800x51100145－z540000 表2—14（最优单纯形表）Cj54000bCBXBx1x2x3x4x50x30012-5255x11001-1354x2010-1210－z000-1-3-215解 由表2—13和表2—14可知，当B=（p3，p1，p2）时，有 当下式成立时，最优基不变即 25－5Δb3≥0，35－Δb3≥0，10+Δb3≥0解不等式有 －5≤Δb3≤5此外，以B-1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出Δb3，即同样可得 －5≤Δb3≤5因此，不影响最优基的b3的变化范围是[40，50]2.7 在例2.11的生产计划问题中：（1）若生产产品甲的工艺结构发生了改进，这时关于它的技术向量变为p1‘=（1，2，1/2）T，试分析对原最优计划有什么影响；（2）若该厂除了生产前两种产品外，拟开发新产品丙，已知产品丙每件消耗A、B、C原材料各为2、4、1kg，每件可获利润8千元。

问该厂是否应该生产该产品和生产多少？解 （1）由于产品甲生产工艺的改进，这样原最优单纯形表中的第1列将会发生改变，具体为代入原最优单纯形表中得到 表2—15Cj54000bCBXBx1x2x3x4x50x35/4012-5255x15/4001-1354x2-1/210-1210将第1列化为单位向量，并用对偶单纯形法迭代一次得到如表2—16所示的新的最优生产计划 表2—16Cj54000bCBXBx1x2x3x4x50x30011[-4]-105x11004/5-4/5284x2010-3/58/524－z000-8/5-12/5——θ————————(-12/5)/-4b0x500-1/4-1/415/25x110-1/53/50304x2012/5-1/5020－z00-3/5-11/50-230即，工艺改进后新的最优生产计划为甲、乙各生产30件和20件，利润为230千元2）设新产品的产量为x3‘（件），其技术系数向量为p3‘=（2，4，1）T，由表2—14可求出σ3‘= c3’－CB B-1pj‘ = 8－（0，1，3）（2，4，1）T=1>0即安排生产产品丙是有利的。

对应x3‘在最优单纯形表中的列向量为代入到最优表2—14中，并用单纯形法迭代一次得新的最优表2—17 表2—17Cj540008bCBXBx1x2x3x4x5x3‘0x30012-5[5]255x11001-13354x2010-12210－z000-1-31-2158x3‘001/52/5-1155x110-3/5-1/520204x2012/5-1/50020－z00-1/5-7/5-20-220由表2—17，得最优解 X*=（20，20，5）T即该工厂生产产品甲、乙、丙分别为20，20，5件，可使工厂获得最大利润220千元2.8 红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表2—18所示为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建。