管理运筹学整理答案

第二章2.5表2-3为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为12max53zxx，约束形式为，34,xx为松弛变量，表中解代入目标函数后得10z。表2-3x1x2x3x4x32c011/5x1ade01jb-1fg(1)求a~g的值；(2)表中给出的解是否为最优解。解：a=2,b=0,c=0,d=1,e=4/5,f=0,g=5；表中给出的解为最优解。2.6表2-4中给出某求最大化线性规划问题的初始单纯形表及迭代后的表，45,xx为松弛变量，求表中a~l的值及各变量下标m~t的值。表2-4x1x2x3x4x5xm6bcd10xn1-13e01ja1-200xsfg2-11/20xt4hi11/21j07jkl解：a=-3,b=2,c=4,d=-2,e=2,f=3,g=1,h=0,i=5,j=-5,k=3/2,l=0；变量的下标为m—4,n—5,s—1,t—62.10下述线性规划问题：要求根据以上信息确定三种资源各自的影子价格。解：由以上信息可以求得该问题的对偶问题的最优解11131148(6,8,9)693,1,27332310TBYCB所以三种资源的影子价格分别为48,1,33。2.11某单位加工制作100套工架，每套工架需用长为2.9m、2.1m和1.5m的圆钢各一根。已知原材料长7.4m。问如何下料使得所用的原材料最省？解：简单分析可知，在每一根原材料上各截取一根2.9m,2.lm和1.5m的圆钢做成一套工架，每根原材料剩下料头0.9m，要完成100套工架，就需要用100根原材料，共剩余90m料头。若采用套截方案，则可以节省原材料，下面给出了几种可能的套截方案，如表2-5所示。表2-5可能的下料方案方案长度/mABCDE2.9120102.1002211.531203合计/m7.47.37.27.16.6料头/m00.10.20.30.8实际中，为了保证完成这100套工架，使所用原材料最省，可以混合使用各种下料方案。设按方案A,B,C,D,E下料的原材料数分别为x1,x2,x3,x4,x5，根据表2-5可以得到下面的线性规划模型123451243451235min00.10.20.30.8210022100..3231000,1,2,3,4,5izxxxxxxxxxxxstxxxxxi用大M法求解此模型的过程如表2-6所示，最优解为：x*=(0,40,30,20,0)T，最优值为z*=16。表2-6cj0-0.1-0.2-0.3-0.8-M-M-MθiCBXBbx1x2x3x4x5x6x7x8-Mx610012010100100-Mx710000221010—-Mx8100[3]1203001100/3j4M-0.1+3M-0.2+4M-0.3+3M-0.8+4M000-Mx6200/305/3-2/31-110-1/3200/3-Mx7100002[2]1010100/20x1100/311/32/301001/3—j0-0.1+5M/3-0.2+4M/3-0.3+3M-0.800-4M/3-Mx650/30[5/3]-5/30-3/21-1/2-1/3150/15-0.3x45000111/201/20—0x1100/311/32/301001/3100/1j0-0.1+5M/30.1-5M/30-0.65-3M/200.153M/2-4M/3-0.1x21001-10-9/103/5-3/10-1/5-0.3x45000111/201/200x130101013/10-1/51/102/5j0000-0.74-M+0.06-M+0.12-M-0.02求解该问题的LINGO程序如下：model:sets:row/1..3/:b;arrange/1..5/:x,c;link(row,arrange):a;endsetsdata:b=100,100,100;c=1,0.1,0.2,0.3,0.8;a=1,2,0,1,0,0,0,2,2,1,3,1,2,0,3;enddatamin=@sum(arrange(j):c(j)*x(j));@for(row(i):@sum(arrange(j):a(i,j)*x(j))=b(i););end运行该程序后，也立即可以得到最优解为：x*=(0,40,30,20,0)T，最优值为z*=16。即按方案B下料40根，方案C下料30根，方案D下料20根，共需原材料90根就可以制作完成100套工架，剩余料头最少为16m。2.13某昼夜服务公交公司的公交线路每天各时段内所需要司机和乘务人员如表2-9所示。表2-9班次时间所需人数班次时间所需人数16:00-10:0060418:00-22:0050210:00-14:0070522:00-2:0020314:00-18:006062:00-6：0030设司机和乘务人员分别在各时段开始时上班并连续工作8小时。问该公司公交线路应如何安排司机和乘务人员，使得既能满足工作需要，又使配备的总人数最少？（本科生仅需建立问题的数学模型）解：设xi为安排从第i班次开始时上班的人数，则该问题的数学模型为61611223344556min607060..5020300,1,2,...,6iiizxxxxxxxstxxxxxxxi求解此模型得到最优解：**(40,30,30,20,0,30),150Txz。2.18现有线性规划问题123123123123max5513320..1241090,,0zxxxxxxstxxxxxx先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1）约束条件①的右端项系数由20变为30；（2）约束条件②的右端项系数由90变为70；（3）目标函数中3x的系数由13变为8；解：在上述LP问题的第①、②个约束条件中分别加入松弛变量x4,x5得123451234123512345max551300320..1241090,,,,0zxxxxxxxxxstxxxxxxxxx①②列出此问题的初始单纯形表并进行迭代运算，过程如表2-12所示。表2-12cj-551300θiCBXBbx1x2x3x4x50x420-11[3]1020/30x59012410019j-55130013x320/3-1/3[1/3]11/30200x570/346/32/30-10/3135j-2/32/30-13/305x220-113100x510160-2-41j00-2-50由表2-12中的计算结果可知，LP问题的最优解X*=(0,20,0,0,10)T，z*=5*20=100。（1）约束条件①的右端项系数由20变为30，则有1103030419030Bb列出单纯形表，并利用对偶单纯形法求解，过程如表2-13所示。表2-13cj-551300CBXBbx1x2x3x4x55x230-113100X5-30160[-2]-41j00-2-505x2-152310[-5]3/213x315-8012-1/2j-1600-1-10x43-23/5-1/501-3/1013x396/52/5101/10j-103/5-1/500-13/10由表2-13中计算结果可知，LP问题的最优解变为**(0,0,9,3,0),139117TXz。（2）约束条件②的右端常数由90变为70，则有1102020417010Bb列出单纯形表，并利用对偶单纯形法求解，结果如表2-14所示。由表2-14结果知，LP问题的最优解变为**(0,5,5,0,0),5513590TXz。（3）目标函数中x3的系数由13变为8，由于x3是非基变量，其检验数变为38530(2)70所以LP问题的最优解不变。第三章3.5某服装厂可生产三种服装，生产不同类型的服装要租用不同的设备，设备租金和其他经济数据见表3-4。假定市场需求不成问题，服装厂每月可用人工2000小时，该厂如何安排生产可使每月的利润最大？试建立此问题的数学模型。表3-4服装种类设备租金(元)生产成本(元/件)销售价格(元/件)人工工时(小时/件)设备工时(小时/件)设备可用工时(小时)西服500028040053300衬衫2000304010.5480羽绒服300020030042600解：设ix为第i类服装的月产量，10iiy生产第类服装否则123123max12010100500020003000zxxxyyys.t.12311223354200033000.548026000,01iixxxxyxyxyxyor且为整数3.6某部队现有5种武器装备储存管理，存放量分别为ai(i=1,…,5)。为了安全起见，拟分为8个仓库存放，各仓库的最大允许存放量分别为bj(j=1,…,8),且有5811ijijab。一种武器装备可以分多个仓库存放，但每个仓库只能存放一种，也只能整件存放。已知第i种武器装备每单位在第j个仓库存放一年的费用为cij。第j个仓库固定费用为每年dj元，但若仓库不存放则没有费用。要求设计一个使总费用最小的存储方案，试建立相应的优化模型。解：设xij为第i种武器装备在仓库j中存放的数量，1,0,ijijy第种武器装备存放在第个仓库中其他min*(*),,,..1,01,ijijjijjiijijijjijijiijijcxdyxaixbyijstyjxyij为整数，且为或，3.7某地准备投资D元建民用住宅。可以建住宅的地点有n处：A1、A2、……、An。Aj处每幢住宅的造价为dj，最多可造aj幢。问应当在哪几处建住宅，分别建几幢，才能使建造的住宅总数最多，试建立问题的数学模型。解：在Aj地所建住宅的数量为xj，1,0,jjAy在地建住宅否则则该问题的数学模型为11max,01,njjjjjnjjjjjzxxaydxDxyorj为整数3.9某部门有3个生产同类产品的工厂(产地)，生产的产品由4个销售点(销地)出售，各工厂的生产量、各销售点的销售量(假定单位均为吨)以及各工厂到各销售点的单位运价(元/吨)如表3-5所示，要求研究产品如何调运才能使得总运费最小。试建立该问题的数学模型，并采用表上作业法求出最佳的调运方案（要求用最小元素法找到初始调运方案）。表3-5销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214解：数学模型：111213142122232431323334111213142122232431323334112131122232132333142434min412411210398511616102281412140,,ijzxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxij利用最小元素法，求得的初始解表3-6销地产地B1B2B3B4产量A110616A28210A314822销量8141214非基变量的检验数：表3-7销地产地B1B2B3B4产量A112A21-1A31012销量由于非基变量x24的检验数为负，所以初始解不是最优解，x24进基，在闭回路{x24,x23,x13,x14}中进行运量调整，得到新的调运方案：表3-8销地产地B1B2B3B4产量A112416A28210A314822销量8141214重新计算检验数：表3-9销