习运筹学题1

习题11用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。0xx42x4x66x4x3x2xminz)a(21212121，0x,x124x3x2x2x2x3xmaxz)b(212121218x310x512010x6xxxmaxz)c(2121210x,x23x2x2x2x6x5xmaxz)d(21212121答案：(a)唯一解3*,)5.0,75.0(*zXT);(b)唯一解4*,)2,0(*zXT);(c)唯一解16*,)6,10(*zXT);(d)无界解）2用单纯形法求解下列线性规划问题。0x,x82x5x94x3x5x10xmaxz)a(212121210x,x5xx242x6x155xx2xmaxz)b(212121221答案：(a)唯一解5.17*,)5.1,1(*zXT)，对偶问题5.17*,)786.1,357.0(*wYT;(b)唯一解5.8*,)5.1,5.3(*zXT），5.8*,)5.0,25.0,0(*wYT3用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。0xxx0x2x2x2x6xxx2xx2xmaxz)a(3,2,132313213210x,x,x62x3x82x4xxx3x2xminz)b(32121321321答案：(a)无界解；(b)唯一解8*,)0,8.1,8.0(*zXT)，对偶问题8*,)0,1(*wYT4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a～l的值。表1-54初始单纯形表bx1x2x3x4x5x46(b)(c)(d)10x51-13(e)01cj-zj(a)-1200表1-55单纯形法迭代后的表bx1x2x3x4x5x1(f)(g)2-11/20x54(h)(i)11/21cj-zj0-7(j)(k)(l)表1-55基变量x1列向量01'1p，所以g=1,h=0（2）初始表,,jpb某步表jpBbB11,有已知表查出12/102/11B,341612/102/141fffbB201112/102/10111bbpB5,42312/102/1221icicipB2,21112/102/11131ededpB（3）初始表主元行×（-主元检验数/主元）加到检验数行得下一步表的检验数行。表1-54第一行系数×（-a/b）+表1-54检验数行=表1-54检验数行即：0,21,2,712lakjaa故：0,23,5,3lkja。5某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据见下表1-56，试安排最优生产计划，使该厂获利最大。表1-56产品的有关数据表设备产品设备有效台时设备加工费（元/小时）ⅠⅡⅢA1A2B1B2B357647109812116000100004000700040000.050.030.060.110.05原料费（元/件）售价（元/件）0.251.250.352.000.502.806一家糖果商店出售三种不同品牌的果仁糖，每个品牌含有不同比例的杏仁、核桃仁、胡桃仁。为了维护商店的质量信誉，每个品牌中所含有的果仁的最大、最小比例是必须满足的，如下表1-57所示：表1-57每个品牌中所含有的果仁的比例表品牌含量需求每磅售价（美元）普通腰果仁不超过20%胡桃仁不低于40%核桃仁不超过25%杏仁没有限制0.89豪华腰果仁不超过35%杏仁不低于40%核桃仁、胡桃仁没有限制1.10蓝带腰果仁含量位于30%~50%之间杏仁不低于30%核桃仁、胡桃仁没有限制1.80表1-58列出了商店从供应商每周能够得到的每类果仁的最大数量和每磅的价格：表1-58每类果仁的最大数量和每磅的价表果仁类型每磅价格（美元）每周最大供应量（磅）杏仁0.452000核桃仁0.554000腰果仁0.705000胡桃仁0.503000商店希望确定每周购进杏仁、核桃仁、腰果仁、胡桃仁的数量，使周利润最大。建立数学模型，帮助该商店管理人员解决果仁混合的问题。7写出下列线性规划问题的对偶问题。无约束321321321321321x0,x,x53x4xx33xx2x24x3xx4x2x2xminz)a()n,,1nj(x)nn,,1j(0x)m,,1mi(bxa)mm,,1i(bxaxcmaxz)b(1j1j1in1jjij1in1jjijn1jjj无约束答案：（a）无约束321321321321321x0,x,x43x3y4y24yy3y2y2yy5y3y2ymax（b）)m,,1i(v)n,,1i(0u)n,...,1nj(cvaua)nn,,1j(cvauavbubmin1i1i1jm1im1miiijiij1jm1im1miiijiijm1miiim1iii111111mm无约束8已知线性规划问题：0xxx1xx2x2xxxxxmaxz32132132121，，试应用对偶理论证明上述线性规划问题最优解为无界。答案：显然T(0,0,0)X为该问题的可行解，其对偶问题为：0yy0yy1yy12yyyy2min2121212121，显然第一个约束与变量非负要求矛盾，故对偶问题无可行解。由无界性该问题最优解为无界。9已知线性规划问题：)4,,1j(0x)4(9xxx)3(6xxx)2(6x2x)1(8x3xxxx4x2xmaxzj321432214214321要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)T，试根据对偶理论求出对偶问题最优解。答案：对偶问题)4,,1j(0y(4)1yy(3)1yy(2)4yyy3y(1)2y2yy9yy66y8yminj314343214214321设对偶问题的最优解为),,,(*4*3*2*1*yyyyY将X*=(2,2,4,0)T代入原问题，约束（4）为严格不等式（即x*S1，x*S2，x*S3）0），由互补松弛性，y*4=0。又因为x*1=2,x*2=2,x*3=4都大于0，由互补松弛性，对偶问题对应（1）--（3）约束为等式，（即y*S1=y*S2=y*S3=0）故有(3)1y(2)4yy3y(1)22yy****1*2*3321，解得对偶问题的最优解为)0,1,5/3,5/4(*yY。10已知线性规划问题：0x,x,x42xx6xxxxx2xmaxz32121321321先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。（1）目标函数变为321x3x2xmaxz；（2）约束右端项由46变为43；（3）增添一个新的约束条件：22xx31。答案：最终表cj2-1100bCBXBx1x2x3x4x52x10x51111003111610j0-3-1-20该问题的最优解TX)10,0,0,0,6(*，最优值1262*z对偶问题的最优解)2,1,3,0,2(*Y，最优值1226*（1）目标函数中非基变量2x的系数2c由-1变为3重新计算2x的检验数20131)02(3'22jBpCc最优解发生变化，将2x的检验数12，系数3c2代入最终表，用单纯形法求解之，见下表cj23100bCBXBx1x2x3x4x52x10x5111100[3]111610*j0（1）-1-202x13x2102/32/3-1/3011/31/31/38/310/3j00-4/3-7/3-1/3该问题的最优解TX)0,0,0,3/10,3/8(*，最优值3463103382*z对偶问题的最优解)3/4,0,0,3/1,3/7(*Y,最优值346314376*（2）037324331313132'1bB，故最优基不变最优解为TX)0,0,0,3/7,3/2(*，最优值325373322*z（3）最优解TX)10,0,0,0,6(*不满足新加的约束将约束化为等式，选松弛变量作为基变量得-2x2xx631将其添加到最终表得过渡表，然后将第一行乘-1加到第三行将基变量x1的系数列向量化为单位向量cj2-11000bCBXBx1x2x3x4x5x62x10x50x611110003111010-2001610-22x10x50x61111000311100-1[-3]-101610（-8）j0-3-1*-2002x10x51x312/302/301/308/302/311/301/311/30-1/310/322/38/3j0-8/30-5/30-1/3新的最优解TX)3/22,0,3/8,0,3/10(*，最优值328383102*z11用分支定界法求解下列整数规划问题：(1)，且为整数，0xx369x4x357x5x3x2xmaxz21212121(2)且为整数,0x,x305x6x165x2xxxmaxz2121212112用隐枚举法求解下列0-1规划问题：)5,,1j(10x35x3x6x11x83x4x-3x7x4x2xxxx3x2x5x2x3xmaxzj542154315432154321或xj=0或1，j=1，2，3，4，513某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表1-59。假定各条航线使用相同型号的船只，又各城市之间的航程天数见表1-60。又知每条船只每次装卸货物的时间各需1天，则该航运公司至少应配备多少条船,才能满足所有航线的运货需求?建立模型并用软件求解。表1-59各条航线的起点、终点城市及每天航班数表航线起点终点每天航班1234EBADDCFB3211表1-60各城市之间的航程天数表终点起点ABCDEFABCDEF012147710313882301555141315017207851703785203014设某公司有五个人可以完成五项工作，每人做每项工作的用时如表1-61所示。每人仅做一项工作，每项工作仅一人做。如何安排是用时最少？建立数学模型并用软件求解表1-61每人完成任务的用时表单位：天工作人员ABCDE人员甲1279