运筹学对偶理论习题.docVIP

第二章 线性规划的对偶理论2.1 写出下列线性规划问题的对偶问题 max z=2x1+2x24x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380x1、x2，x30解：其对偶问题为min w=30y1+ 80y2y1+ 4y2 23y1 + 2y2 23y1 + 4y2 4y1、y202.2 写出下列线性规划问题的对偶问题 min z=2x1+8x24x3x1 + 3x23x3 30x1 + 5x2 + 4x3 = 804x1 + 2x24x350x10、x20，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3 y1 y2 + 4 y3 23y1+5y2 + 2y3 83y1 + 4y24y3 =4y10，y2无限制，y302.3 已知线性规划问题 max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4202x1 + x2 + 3x3 +2x420x1、x2，x3，x40其对偶问题的最优解为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、y20将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 + 4x38x1、x2，x30解 将问题改写成如下形式 max（z）=4x12x26x32x1 4x2 8x3 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50显然，p4、p5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此p4、p5构成的就是初始正侧基。整个问题的计算过程列在表27中。 表27Cj42600bCBXBx1x2x3x4x50x4-2-4-810-240x5-4-1-401-8z-4-2-6000-4/-2-2/-4-6/-1000-2x21/212-1/4060x5-7/20-2-1/41-2z-30-2-1/20-120-3/(-7/2)0-2/-2(-1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/24z-1/200-1/4-1-32最后一个单纯形表中，已得到一个可行的正侧解，因而得到问题的最优解为 X*=（0，4，4）T最优值为z*=322.5 设某线性规划问题的初始单纯形表和最优单纯形表分别为 表29（初始单纯形表）Cj54300bCBXBx1x2x3x4x50x411110600x52140180z543000 表210（最优单纯形表）Cj54300bCBXBx1x2x3x4x54x201-22-1405x1103-1120z00-4-3-1-260现在要问：（1）c3在什么范围内变化，表中最优解不变？（2）c3从3变为8，求新的最优解解（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数3=4，因此当c33=4时，表中最优解不变。（2）当c3从3变为8时，则表中的检验数3从4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表211中所示的新的最优解。 表211Cj54800bCBXBx1x2x3x4x54x201-22-1405x1103-1120z001-3-1-2604x22/3104/3-1/3160/35x31/301-1/31/320/3z00-4-3-1-740/3即新的最优解为X*=（0，160/3，20/3）T。2.6 某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的A、B、C三种原材料的数量以及单位产品的利润如下表所示： 表212产品单位消耗原材料甲乙资源限量（kg）ABC121311908045单位产品利润（千元/件）54若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为： max z=5x1+4x2x1 +3x2 902x1+ x2 80x1+ x2 45x1、x2，x30用单纯形法求解该问题时，其初始单纯形表和最优单纯形表分别如表213和314所示，试分析使最优基不变的b3的变化范围。 表213（初始单纯形表）Cj54000bCBXBx1x2x3x4x50x313100900x421010800x51100145z540000 表214（最优单纯形表）Cj54000bCBXBx1x2x3x4x50x30012-5255x11001-1354x2010-1210z000-1-3-215解 由表213和表214可知，当B=（p3，p1，p2）时，有 当下式成立时，最优基不变。即 255b30，35b30，10+b30解不等式有 5b35此外，以B-1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出b3，即同样可得 5b35因此，不影响最优基的b3的变化范围是40，50。2.7 在例2.11的生产计划问题中：（1）若生产产品甲的工艺结构发生了改进，这时关于它的技术向量变为p1=（1，2，1/2）T，试分析对原最优计划有什么影响；（2）若该厂除了生产前两种产品外，拟开发新产品丙，已知产品丙每件消耗A、B、C原材料各为2、4、1kg，每件可获利润8千元。问该厂是否应该生产该产品和生产多少？解 （1）由于产品甲生产工艺的改进，这样原最优单纯形表中的第1列将会发生改变，具体为代入原最优单纯形表中得到 表215Cj54000bCBXBx1x2x3x4x50x35/4012-5255x15/4001-1354x2-1/210-1210将第1列化为单位向量，并用对偶单纯形法迭代一次得到如表216所示的新的最优生产计划。 表216Cj54000bCBXBx1x2x3x4x50x30011-4-105x11004/5-4/5284x2010-3/58/524z000-8/5-12/5(-12/5)/-4b0x500-1/4-1/415/25x110-1/53/50304x2012/5-1/5020z00-3/5-11/50-230即，工艺改进后新的最优生产计划为甲、乙各生产30件和20件，利润为230千元。（2）设新产品的产量为x3（件），其技术系数向量为p3=（2，4，1）T，由表214可求出3= c3CB B-1pj = 8（0，1，3）（2，4，1）T=10即安排生产产品丙是有利的。对应x3在最优单纯形表中的列向量为代入到最优表214中，并用单纯形法迭代一次得新的最优表217。 表217Cj540008bCBXBx1x2x3x4x5x30x30012-55255x11001-13354x2010-12210z000-1-31-2158x3001/52/5-1155x110-3/5-1/520204x2012/5-1/50020z00-1/5-7/5-20-220由表217，得最优解 X*=（20，20，5）T即该工厂生产产品甲、乙、丙分别为20，20，5件，可使工厂获得最大利润220千元。2.8 红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表218所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）表218时 间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，x7星期日开始上班的人数。我们的目标是要求售货人员的总数最少。因为每个售货员都工作五天，休息两天，所以我们只要计算出连续工作五天的售货人数，也就计算出了售货员的总数。我们把连续工作五天的售货员按照开始工作的时间分成7类，各类的人数分别为x1，x2，x7，即有目标函数： min x1+x2+x3+x4+x5+x6+x7.我们再按照每天所需售货员的人数写出约束条件，例如星期日需要28人，我们知道商场中的全休售货员中除了星期一开始上班和星期二开始上班的人外都应该上班，即有 x3+x4+x5