运筹学习题集03

数学建模1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下：产品项目ABCD单位产值(元)1681401050406单位成本(元)4228350140单位纺纱用时(h)32104单位织带用时(h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h，列出线性规划模型。解：设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有线性规划模型如下：maxf(x)=(16842)x1+(14028)x2+(1050350)x3+(406140)x4=126x1+112x2+700x3+266x4s.t.4,3,2,1,012005.02720041023434321ixxxxxxxi2、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。解：设x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则问题的目标可描述为minz=1000x1+800x2x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥03、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）工厂1工厂2200万m3500万m3时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，……，x7星期日开始上班的人数。minx1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x7≥28x4+x5+x6+x7+x1≥15x5+x6+x7+x1+x2≥24x6+x7+x1+x2+x3≥25x7+x1+x2+x3+x4≥19x1+x2+x3+x4+x5≥31x2+x3+x4+x5+x6≥28x1、x2、x3、x4、x5、x6、x7≥04、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的最大重量为25kg，试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量kg55251023重要性系数201516148149解：引入0－1变量xiiiixxx不携带物品携带物品01（i＝1，…，7）则0－1规划模型为：maxz＝20x1＋15x2＋16x3＋14x4＋8x5＋14x6＋9x7s.t.5x1＋5x2＋2x3＋5x4＋10x5＋2x6＋3x7≤25xi＝0或1，i＝1，0，…，7标准化问题1、将下列线性规划化为标准形式不限321321321321321,0,019|1210|1573610..235)(minxxxxxxxxxxxxtsxxxxf0,,,,,,19121019121015773610..2'235)](max[654332163321533213321433213321xxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxf2、化下列线性规划为标准形maxz=2x1+2x2－4x3x1+3x2－3x3≥30x1+2x2－4x3≤80x1、x2≥0，x3无限制解：按照上述方法处理，得该线性规划问题的标准形为maxz=2x1+2x2－4x31+4x32x1+3x2－3x31+3x32－x4=30x1+2x2－4x31+4x32+x5=80x1、x2，x31，x32，x4，x5≥0图解法1、用图解法求解下面线性规划。maxz=2x1+2x2x1－x2≥1－x1+2x2≤0x1、x2≥0解：图1—3中阴影部分就是该问题的可行域，显然该问题的可行域是无界的。两条虚线为目标函数等值线，它们对应的目标值分别为2和4，可以看出，目标函数等值线向右移动，问题的目标值会增大。但由于可行域无界，目标函数可以增大到无穷。称这种情况为无界解或无最优解。2、用图解法求解下述LP问题。121212max2328416..4120,1,2jzxxxxxstxxj1－11z=42z=6OA图1—32x1x解：可知，目标函数在B(4,2)处取得最大值，故原问题的最优解为*(4,2)TX，目标函数最大值为*2*43*214z。3、用图解法求解以下线性规划问题：（1）maxz=x1+3x2s.t.x1+x2≤10-2x1+2x2≤12x1≤7x1,x2≥0x210(2,8)6x1-60710最优解为（x1,x2）=（2,8），maxz=26(2)minz=x1-3x2s.t.2x1-x24x1+x23x25x14x1,x20x253x10234最优解为（x1，x2）=（0，5），minz=-15（3）maxz=x1+2x2s.t.x1-x21x1+2x24x13x1,x20x22x101234多个最优解，两个最优极点为（x1，x2）=（2，1），和(x1，x2)=(0，2)，maxz=5（4）minz=x1+3x2s.t.x1+2x242x1+x24x1,x20x2x1=04x4=02x3=0x2=0x1024最优解为（x1，x2）=（4，0），minz=4单纯形法1、用单纯形法求解maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0解：首先将问题化为标准形式，然后将整个计算过程列在一个表中Cj50100000bCBXBx1↓x2↓x3x4x50x3111003000x421010400←0x50[1]001250－z501000000←0x31010-1500x42001-1150100x201001250－z50000-100－2500050x11010-1500x400-21150100x201001250－z00-500-50－27500由于σj≤0（j=1，…，5），故X*=（50，250，0，50，0）T，Z*=275002、用单纯形法求解maxz=2x1+x2－x1+x2≤52x1－5x2≤10x1、x2≥0解：用单纯形表实现如表1—10表1—10Cj2100bθCBXBx1↓x2x3x40x3-11105—←0x4[2]-5011010/4(min)－z210000x30-3/211/2102x11-5/201/25－z060-1－10σ2=60，且p2≤0，故该线性规划有无界解（无最优解）。3、用单纯形法（大M法）求解下列线性规划maxz=3x1－2x2－x3x1－2x2+x3≤11－4x1+x2+2x3≥3－2x1+x3=1x1、x2、x3≥0解：化为标准形式maxz=3x1－2x2－x3x1－2x2+x3+x4=11－4x1+x2+2x3－x5=3－2x1+x3=1x1、x2、x3、x4、x5≥0在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题maxz=3x1－2x2－x3－Mx6－Mx7x1－2x2+x3+x4=11－4x1+x2+2x3－x5+x6=3－2x1+x3+x7=1x1、x2、x3、x4、x5、x6、x7≥0用单纯形进行计算，计算过程见表Cj3-1-100-M-MbCBXBx1↓x2↓x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-20[1]00011－z3-6M-1+M-1+3M0-M004M0x43-20100-110-Mx60[1]00-11-21-1x3-20100011－z1-1+M00-M0-3M+1M+10x4[3]001-22-512-1x20100-11-21-1x3-20100011－z1000-1-M+1-M-123x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39－z000-1/3-1/3-M+1/3-M+2/3－2由于σj≤0（j=1，…，7），且基变量中不含人工变量，故X*=（4，1，9）T，z*=24、用单纯形法（大M法）求解下列线性规划maxz=3x1+2x22x1+x2≤23x1+4x2≥12x1、x2≥0解:化为标准形式后引入人工变量x5得到maxz=3x1+2x2－Mx52x1+x2+x3=23x1+4x2－x4+x5=12x1、…、x5≥0用单纯形法计算，过程列于表中。从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的人工变量x5=4，所以原问题无可行解。3200-MbCBxBx1x2x3x4x50-Mx3x523[1]4100-101212-z3+3M2+4M0-M012M2-Mx2x52-5101-40-10124-z-1-5M0-2-4M-M0-4+4M2、用单纯形法求解下述LP问题。121212max2328416..4120,1,2jzxxxxxstxxj解：首先将原问题转化为线性规划的标准型，引入松弛变量x3,x4,x5，可得：121231425max2328416..4120,1,2,,5jzxxxxxxxstxxxj构造单纯形表，计算如下：jc23000iBcBXb1x2x3x4x5x03x812100404x1640010－05x120[4]0013j2300003x2[1]010－1/2204x1640010432x301001/4－j2000－3/421x21010－1/2－04x800－41[2]432x301001/412j00－201/421x41001/4005x400－21/2132x2011/2－1/80j00－3/2－1/80原问题的最优解为*(4,2,0,0,4)TX，目标函数最大值为*2*43*214z。3、用单纯形法求解下述LP问题。12121212max34240..330,0zxxxxstxxxx解：首先将原问题转化为线性规划的标准型，引入松弛变量3x、4x，可得：121231241234maxz34240..330,,,0xxxxxstxxxxxxx构造单纯形表，计算如下：jc3400iBcBXb1x2x3x4x03x4021104004x301[3]0110j340003x30[5/3]01-1/31842x101/3101/330j5/300-4/331x18103/5-1/542x401-1/52/5j00-1-1由此可得，最优解为*(18,4,0,0)TX，目标函数值为*3*184*470z。4、用单纯形法求解下述LP问题。12121212max2.53515..5210,0zxxxxstxxxx解：引入松弛变量3x、4x，化为标准形式：121231241234max2.53515..5210,,,0zxxxxxstxxxxxxx构造单纯形表，计算如下：jc2.5100iBcBXb1x2x3x4x03x153510504x10[5]2012j2.5100