运筹学习题集03.docx

数学建模1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目ABCD单位产值 (元)1681401050406单位成本 (元)4228350140单位纺纱用时 (h)32104单位织带用时 (h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h，列出线性规划模型。解：设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有线性规划模型如下：max f(x)=(168-42)x1 +(140-28)x2 +(1050-350)x3 +(406-140)x4=126 x1 +112 x2 +700 x3 +266 x4s.t. 工厂1工厂2200万m3500万m32、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。解：设x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则问题的目标可描述为min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x203、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）时 间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，x7星期日开始上班的人数。 min x1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x728x4+x5+x6+x7+x115x5+x6+x7+x1+x224x6+x7+x1+x2+x325x7+x1+x2+x3+ x419x1+x2+x3+x4+x531x2+x3+x4+x5+x628x1、x2、x3、x4、x5、x6、x704、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的最大重量为25 kg，试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量kg55251023重要性系数201516148149解：引入01变量xi （i1，7）则01规划模型为：max z20x115x216x314x48x514x69x7s.t. 5x15x22x35x410x52x63x725xi0或1，i1，0，7标准化问题1、将下列线性规划化为标准形式 2、化下列线性规划为标准形max z=2x1+2x24x3x1 + 3x23x3 30x1 + 2x24x380x1、x20，x3无限制解：按照上述方法处理，得该线性规划问题的标准形为 max z=2x1+2x24x31+4x32x1 + 3x23x31 + 3x32x4 = 30x1 + 2x24x31 + 4x32 + x5 = 80x1、x2，x31，x32，x4，x5 0图解法111z=42z=6OA图131、用图解法求解下面线性规划。 max z=2x1+2x2x1x2 1x1 + 2x2 0x1、x2 0解：图13中阴影部分就是该问题的可行域，显然该问题的可行域是无界的。两条虚线为目标函数等值线，它们对应的目标值分别为2和4，可以看出，目标函数等值线向右移动，问题的目标值会增大。但由于可行域无界，目标函数可以增大到无穷。称这种情况为无界解或无最优解。2、用图解法求解下述LP问题。解： 可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为，目标函数最大值为。3、 用图解法求解以下线性规划问题：（1）maxz=x1+3x2s.t.x1+x210-2x1+2x212x1 7x1,x20 x2 10 (2,8) 6 x1 -6 0 7 10最优解为（x1,x2）=（2,8），max z=26(2)minz=x1-3x2s.t.2x1-x24x1+x23x25x14x1,x20 x2 5 3 x1 0 2 3 4最优解为 （x1，x2）=（0，5），min z=-15（3）maxz=x1+2x2s.t.x1-x21x1+2x24x13x1,x20 x2 2 x1 0 1 2 3 4多个最优解，两个最优极点为（x1，x2）=（2，1），和(x1，x2)=(0，2)，max z=5（4）minz=x1+3x2s.t.x1+2x242x1+x24x1,x20 x2 x1=0 4 x4=0 2 x3=0 x2=0 x1 0 2 4 最优解为（x1，x2）=（4，0），min z=4单纯形法1、用单纯形法求解max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20解：首先将问题化为标准形式，然后将整个计算过程列在一个表中Cj50100000b CBXB x1 x2x3x4x5 0x311100300 0x421010400 0x501001250z501000000 0x31010-150 0x42001-1150 100x201001250z50000-10025000 50x11010-150 0x400-21150 100x201001250z00-500-5027500由于j0（j=1，5），故X*=（50，250，0，50，0）T， Z*=275002、用单纯形法求解max z=2x1+x2x1 + x252x15x210x1、x20解：用单纯形表实现如表110 表110Cj2100b CBXB x1x2x3x4 0x3-11105 0x42-5011010/4(min)z21000 0x30-3/211/210 2x11-5/201/25z060-1102=6 0，且p20，故该线性规划有无界解（无最优解）。3、用单纯形法（大M法）求解下列线性规划max z=3x12x2x3x12x2 + x3 114x1 + x2 + 2x3 32x1 + x3 = 1x1、x2、x30解：化为标准形式 max z=3x12x2x3x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 = 32x1 +x3 = 1x1、x2、x3 、x4、x50在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题max z=3x12x2x3Mx6Mx7x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 + x6 = 32x1 + x3 +x7 = 1x1、x2、x3、x4、x5、x6、x70用单纯形进行计算，计算过程见表Cj3-1-100-M-Mb CBXB x1 x2x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-20100011z3-6M-1+M-1+3M0-M004M0x43-20100-110-Mx60100-11-21-1x3-20100011z1-1+M00-M0-3M+1M+10x43001-22-512-1x20100-11-21-1x3-20100011z1000-1-M+1-M-123x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39z000-1/3-1/3-M+1/3-M+2/32由于j0（j=1，7），且基变量中不含人工变量，故X*=（4，1，9）T， z*=24、用单纯形法（大M法）求解下列线性规划max z=3x1+2x22x1+ x2 23x1 +4 x2 12x1、x20解: 化为标准形式后引入人工变量x5得到 max z=3x1+2x2Mx52x1+ x2 +x3 = 23x1 +4 x2 x4+x5 =12x1、x50用单纯形法计算，过程列于表中。从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量x5=4，所以原问题无可行解。 3200-MbCBxBx1x2x3x4x50-Mx3x52314100-101212-z3+3M2+4M0-M012M2-Mx2x52-5101-40-10124-z-1-5M0-2-4M-M0-4+4M2、用单纯形法求解下述LP问题。解：首先将原问题转化为线性规划的标准型，引入松弛变量x3, x4,x5，可得：构造单纯形表，计算如下：230000812100401640010012040013230000210101/220164001043301001/420003/42210101/2080041243301001/41200201/4241001/40040021/2132011/21/80003/21/80原问题的最优解为，目标函数最大值为。3、用单纯形法求解下述LP问题。解：首先将原问题转化为线性规划的标准型，引入松弛变量、，可得：构造单纯形表，计算如下：340004021104003013011034000305/301-1/3184101/3101/3305/300-4/3318103/5-1/54401-1/52/500-1-1由此可得，最优解为，目标函数值为。4、用单纯形法求解下述LP问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：2.510001535105010520122.510009019/513/545/192.5212/501/550001/2145/19015/193/192.520/19102/195/190001/2由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。5、用单纯形法求解下述线性规划解：引入松弛变量、和，列单纯形表计算如下：1230000821810010413100101/308114001123000024/5-14/517/501-4/5032/51/10-3/10101/1004048/57/5-11/5002/5148/77/10-11/1000-3/1000160-528120141-3100100402-140-1101-70-1002600-71-1/25/211010-110-1/23/22201-70-1/21/20000-1/2-1/2故，原问题的最优解为， ，其中。7、用单纯形法求解下述LP问题。解：构造单纯形表计算如下：340004021104003013011034000305/3011/3184101/3101/3305/3004/3318103/51/544011/52/50011故，最优解为，目标函数值为。8、用大M法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得：构造单纯形表计算如下：2350MMM71110107M1025110153M+23-4M2M-5-M00M207/21/21/211/24/72515/21/21/201/207M/2+8M/2-6M/2+10-3M/2-134/7011/71/72/7-1/7245/7106/7-1/75/71/700-50/7-1/7-M-16/7-M+1/7由此得，原问题的最优解为，目标函数最优值为102/7。9、用两阶段法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得第一阶段的模型为：构造单纯形表，计算如下：00001117111010711025110153421001207/21/21/211/24/70515/21/21/201/207/21/21/203/234/7011/71/72/7-1/7245/7106/7-1/75/71/7000011由此可得第一阶段的最优解，转入第二阶段，单纯形表如下：235034/7011/71/7245/7106/7-1/700-50/7-1/7由此得，原问题的最优解为，目标函数最优值为102/7。10、求解下述LP问题 解：用大M法求解。将原问题化为标准型，可得：在第三个等式约束中引入一个人工变量，可得：用单纯形表求解，可得：101512000M0953110009/501556150100-M521100-115/22M+10M+15M+1200-M0109/513/51/51/50009024091611003/2M7/50-1/53/5-2/50-117/309-M/53M/5+10-2M/5-20-M0103/2139/8003/16-1/8000123/209/1611/161/1600-M1/20-43/800-7/16-3/80-11027/8-43M/800-21/8-7M/16-5/8-3M/8-M0所有变量的检验数均为负数或零，单纯形表计算完毕，但人工变量仍在基变量中，故原问题无可行解。写对偶问题1、写出下列线性规划问题的对偶问题 max z=2x1+2x24x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380x1、x2，x30解：其对偶问题为min w=30y1+ 80y2y1+ 4y2 23y1 + 2y2 23y1 + 4y2 4y1、y202、写出下列线性规划问题的对偶问题 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无限制，y30对偶的性质1、已知线性规划问题 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、已知线性规划的最优解为，试利用互补松弛定理，求对偶问题的最优解。解：原问题的对偶问题为：將代入原问题的约束条件，可得： （1）又由 （2）将结论（1）和（2）结合起来，可解得。3、已知线性规划问题其对偶问题的最优解为、，试用对偶理论求解原问题的最优解。解：原问题的对偶问题为：将对偶问题的最优解代入约束条件，可得： （1）又由 （2）将结论（1）和（2）结合起来，可得： ，解得 即原问题的最优解为。对偶单纯形法1、用对偶单纯形法求下面问题解：Cj 4600min( zj - cj)/ai*jCBXBbx1x2x3x4ai*j022 =c22（u2+v2）=4（1+1）= 2023 =c23（u2+v3）=3（1+6）= 2034 =c34（u3+v4）=9（2+4）= 30由于23 =20，故表中基可行解不是最优解，并以x23为第一个顶点作闭回路，如下销 地产地B1B2B3B4产量A120525503764A220x23202433A32010308389销量40201525该闭回路上，偶数顶点上的基变量最小值为5，以该调整量进行调整得到如表销 地产地B1B2B3B4产量A12525503764A2155202433A32010308389销量402015254、用最小元素法给出运输问题的初始可行解，检验解的最优性，如果不是最优解，改进成最优解。甲乙丙丁产量A1067124B1610599C5410104销量5246解： 用最小元素法求得初始解：甲乙丙丁产量A314B459C224销量5246用位势法计算u和v：甲乙丙丁uiA(10)(12)0B(5)(9)-3C(5)(4)-5vj109812计算非基本变量的检验数：甲乙丙丁uiA-3(6)-1(7)0B9(16)4(10)-3C7(10)3(10)-5vj109812以(A乙)作为调入格，用闭回路调整法计算(A乙)的新运量：甲乙丙丁产量A1214B459C44销量5246用位势法计算非基变量的检验数：甲乙丙丁uiA(10)(6)-1(7)(12)0B9(