运筹学习题答案一.doc

习题一1.1 讨论下列问题：（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化（2）在例1.2中，如果设xj(j=1，2，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1，模型如何变化（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表123所示表123产品资源ABC资源限量材料(kg)1.51.242500设备(台时)31.61.21400利润(元/件)101412 根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为1.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架两种窗架所需材料规格及数量如表124所示：表124 窗架所需材料规格及数量型号A型号B每套窗架需要材料长度（m）数量(根)长度(m)数量(根)A1：1.72B1：2.72A2：1.33B2：2.03需要量（套）200150问怎样下料使得（1）用料最少；（2）余料最少【解】 第一步：求下料方案，见下表。方案一二三四五六七八九十十一十二十三十四需要量B1:2.7m21110000000000300B2:2m01003221110000450A1:1.7m00100102103210400A2:1.3m01120010130234600余料0.600.30.700.30.70.610.10.900.40.8第二步：建立线性规划数学模型设xj（j=1,2,，14）为第j种方案使用原材料的根数，则（1）用料最少数学模型为用单纯形法求解得到两个基本最优解X(1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534X(2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534（2）余料最少数学模型为用单纯形法求解得到两个基本最优解X(1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根显然用料最少的方案最优。1.4某企业需要制定16月份产品A的生产与销售计划。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。16月份产品A的单件成本与售价如表125所示。表125月份1 2 3 4 5 6产品成本(元/件)销售价格(元/件)300 330 320 360 360 300350 340 350 420 410 340（1）16月份产品A各生产与销售多少总利润最大，建立数学模型；（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。【解】设xj、yj（j1，2，6）分别为16月份的生产量和销售量，则数学模型为（1）（2）目标函数不变，前6个约束右端常数800改为1000，第711个约束右端常数200改为0，第12个约束“200”改为“200”。1.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60，这种投资最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30，这种投资最多不超过1万元投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.【解】是设xij为第i年投入第j项目的资金数，变量表如下项目一项目二项目三项目四第1年第2年第3年x11x21x31x12x23x34数学模型为最优解X=(30000，0，66000，0，109200，0)；Z847201.6 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表126。表126成品油高级汽油一般汽油航空煤油一般煤油半成品油中石脑油重整汽油裂化汽油中石脑油重整汽油裂化汽油轻油、裂化油、重油、残油轻油、裂化油、重油、残油按10:4:3:1调合而成辛烷值9484蒸汽压：公斤平方厘米1利润(元/桶)54.231.5半成品油的辛烷值、气压、及每天可供应数量见表127。表127半成品油1中石脑油2重整汽油3裂化汽油4轻油5裂化油6重油7残油辛烷值80115105蒸汽压：公斤平方厘米1.01.50.60.05每天供应数量(桶)200010001500120010001000800问炼油厂每天生产多少桶成品油利润最大，建立数学模型。解 设xij为第i（i1,2,3,4）种成品油配第j(j=1,2,7)种半成品油的数量（桶）。总利润：高级汽油和一般汽油的辛烷值约束航空煤油蒸气压约束一般煤油比例约束即半成品油供应量约束整理后得到1.7 图解下列线性规划并指出解的形式：(1) 【解】最优解X（2，4）；最优值Z=13(2) 【解】有多重解。最优解X（1）（3/2，1/2）；X（2）（4/5，6/5）最优值Z=2(3) 【解】最优解X（4，1）；最优值Z=10，有唯一最优解(4) 【解】最优解X（2，3）；最优值Z=26，有唯一最优解(5) 【解】无界解。 (6)【解】无可行解。1.8 将下列线性规划化为标准形式 (1)【解】（1）令为松驰变量 ，则标准形式为 (2) 【解】（2）将绝对值化为两个不等式，则标准形式为 (3) 【解】方法1：方法2：令则标准型为(4) 【解】令，线性规划模型变为标准型为1.9 设线性规划取基分别指出对应的基变量和非基变量，求出基本解，并说明是不是可行基【解】B1：x1，x3为基变量，x2，x4为非基变量,基本解为X=（15，0，20，0）T，B1是可行基。B2：x1,x4是基变量，x2,x3为非基变量，基本解X=（25，0，0，40）T，B2不是可行基。1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点 (1)【解】图解法单纯形法：C(j)1300bRatioC(i)BasisX1X2X3X40X3-2110220X42301124C(j)-Z(j)130003X2-21102M0X480-3160.75C(j)-Z(j)70-3063X2010.250.257/21X110-0.3750.1253/4C(j)-Z(j)00-0.375-0.87545/4对应的顶点：基可行解可行域的顶点X(1)=（0，0，2，12）、X(2)=（0，2，0，6，）、X(3)=（、（0，0）（0，2）最优解 (2) 【解】图解法单纯形法：C(j)-3-5000bRatioBasisC(i)X1X2X3X4X5X301210063X4014010102.5X501100144C(j)-Z(j)-3-50000X300.501-0.5012X2-50.25100.2502.510X500.7500-0.2511.52C(j)-Z(j)-1.75001.250-12.5X1-3102-102MX2-501-0.50.5024X5000-1.50.5100C(j)-Z(j)003.5-0.50-16X1-310-1022X2-50110-12X4000-3120C(j)-Z(j)00201-16对应的顶点：基可行解可行域的顶点X(1)=（0，0，6，10，4）、X(2)=（0，2.5，1，0，1.5，）、X(3)=（2，2，0，0，0）X(4)=（2，2，0，0，0）（0，0）（0，2.5）(2，2)（2，2）最优解：X=（2，2，0，0，0）；最优值Z16该题是退化基本可行解，5个基本可行解对应4个极点。1.11用单纯形法求解下列线性规划(1)【解】单纯形表：C(j)34100R. H. S.RatioBasisC(i)X1X2X3X4X5X402311011/3X501220133/2C(j)-Z(j)341000X242/311/31/301/31/2X50-1/304/3-2/317/3MC(j)-Z(j)1/30-1/3-4/30-4/3X1313/21/21/201/2X5001/23/2-1/215/2C(j)-Z(j)0-1/2-1/2-3/20-3/2最优解：X=（1/2，0，0，0，5/2）；最优值Z3/2 (2) 【解】单纯形表：C(j)21-35000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1110101010X702-6-14001205C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/21/25/4001-1/4510X451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4X50320150111-1120MX21515/2002-1/21010X45807/2103-1/220MC(j)-Z(j)-430-2300-173因为730并且ai70,原问题无可行解。两阶段法第一阶段：数学模型为C(j)000001R. H. S.RatioBasisC(i)X1X2X3X4X5X6X3053100091.8X40-56010015MX612100-1152.5C(j)-Z(j)-2-10010514X1013/51/50009/5X4009110024X610-1/5-2/50-117/5C(j)-Z(j)01/52/5010因为X60,原问题无可行解。图解法如下： (4) 【解】大M法。X7是人工变量，数学模型为Cj425000MR.H.S.RatioCBXBX1X2X3X4X5X6X70X46-141100X53-3-518MX7121112010C(j)-Z(j)425* Big MM2MM10X413/29/21-1/21/2200X59/2-7/21-3/23/2382X21/211/2-1/21/210C(j)-Z(j)341-1* Big M-15X313/912/9-1/91/940/90X586/97/91-17/917/9482/92X2-2/91-1/9-4/94/970/9C(j)-Z(j)-25/9-8/913/9-13/9* Big M-1无界解。两阶段法。第一阶段：Cj0001R.H.S.RatioCBXBX1X2X3X4X5X6X70X46-141100X53-3-5181X7121112010C(j)-Z(j)12110X413/29/21-1/21/2200X59/2-7/21-3/23/2382X21/211/2-1/21/210C(j)-Z(j)1第二阶段：Cj425000R.H.S.RatioCBXBX1X2X3X4X5X60X413/29/21-1/2200X59/2-7/21-3/2381X21/211/2-1/210C(j)-Z(j)7/29/21/20X313/912/9-1/940/90X586/97/91-17/9482/92X2-2/91-1/9-4/970/9C(j)-Z(j)-3-11原问题无界解。1.13 在第1.9题中，对于基求所有变量的检验数,并判断B是不是最优基【解】, B不是最优基，可以证明B是可行基。1.14已知线性规划的最优基为，试用矩阵公式求（1）最优解；(2)单纯形乘子；(3)(4)【解】则(1)(2)(3)(4)注：该题有多重解：X(1)=(0，5，0，5/2)X(2)=(0，10/3，10/3，0)X(3)=(10，0，0，0)，x2是基变量，X(3)是退化基本可行解Z501.15 已知某线性规划的单纯形表128, 求价值系数向量C及目标函数值Z表128Cjc1c2c3c4c5c6c7bCBXBx1x2x3x4x5x6x73x4012130244x1101020100x601404123/2j0110102【解】由有c21（31400（1）2c31（324（1）04）1c51（3（3）420（4）0则(4,2,1,3,0,0,0,)，Z=CBXB=12 1.16 已知线性规划的最优单纯形表如表129所示，求原线性