运筹学答案熊伟上汇总.doc

教材习题答案部分有图形的答案附在各章PPT 文档的后面，请留意。第1章 线性规划第2章 线性规划的对偶理论 第3章 整数规划 第4章 目标规划第5章 运输与指派问题 第6章 网络模型 第7章 网络计划 第8章 动态规划 第9章 排队论 第10章 存储论 第11章 决策论 第12章 对策论习题一1.1 讨论下列问题：（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A 有5台，利用率为0.8, 设备B 有7台，利用率为0.85, 其它条件不变，数学模型怎样变化（2）在例1.2中，如果设x j (j=1，2，7 为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1，模型如何变化（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化1.2 工厂每月生产A 、B 、C 三种产品 , 单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表122所示 310和130. 试建立该问题的数学模型, 使每月利润最大【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为max Z =10x 1+14x 2+12x 31.5x 1+1.2x 2+4x 325003x +1.6x +1.2x 1400231 150x 1250260x 2310120x 3130x 1, x 2, x 301.3 建筑公司需要用6m 长的塑钢材料制作A 、B 两种型号的窗架两种窗架所需材料规格及数量如表123所示： 【解】 设x j （j =1,2,，14）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为min Z =x jj =1142x 1+x 2+x 3+x 4300x 2+3x 5+2x 6+2x 7+x 8+x 9+x 10450x 3+x 6+2x 8+x 9+3x 11+2x 12+x 13400x +x +2x +x +x +3x +2x +3x +4x 6004791012131423x j 0, j =1, 2, ,14用单纯形法求解得到两个基本最优解X (1=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 ;Z=534 X (2=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 ;Z=534 （2）余料最少数学模型为min Z =0.6x 1+0.3x 3+0.7x 4+ +0.4x 13+0.8x 142x 1+x 2+x 3+x 4300x 2+3x 5+2x 6+2x 7+x 8+x 9+x 10450 x 3+x 6+2x 8+x 9+3x 11+2x 12+x 13400x +x +2x +x +x +3x +2x +3x +4x 6004791012131423x j 0, j =1,2, ,14用单纯形法求解得到两个基本最优解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 A、B 两种产品，都需要经过前后两道工序加工，每一个单位产品A 需要前道工序1小时和后道工序2小时，每一个单位产品B 需要前道工序2小时和后道工序3小时可供利用的前道工序有11小时，后道工序有17小时每加工一个单位产品B 的同时，会产生两个单位的副产品C ，且不需要任何费用，产品C 一部分可出售赢利，其余的只能加以销毁出售单位产品A 、B 、C 的利润分别为3、7、2元，每单位产品C 的销毁费为1元预测表明，产品C 最多只能售出13个单位试建立总利润最大的生产计划数学模型【解】设x 1, x 2分别为产品A 、B 的产量，x 3为副产品C 的销售量, x 4为副产品C 的销毁量，有x 3+x 4=2x 2,Z 为总利润，则数学模型为maxZ=3x 1+7x 2+2x 3-x 4x 1+2x 2112x +3x 1712-2x 2+x 3+x 4=0x 133x j 0, j =1, 2, , 41.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资： 方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60，这种投资最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30，这种投资最多不超过1万元投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型. 【解】是设x 为第i 年投入第j 项目的资金数，变量表如下数学模型为max Z =0.2x 11+0.2x 21+0.2x 31+0.5x 12+0.6x 23+0.3x 34x 11+x 1230000-1.2x 11+x 21+x 2330000-1.5x 12-1.2x 21+x 31+x 3430000x 1220000x 1500023x 3410000x ij 0, i =1, ,3; j =1, 4最优解X=(30000，0，66000，0，109200，0 ；Z 847201.6 IV发展公司是商务房地产开发项目的投资商公司有机会在三个建设项目中投资：高层办公楼、宾馆及购物中心，各项目不同年份所需资金和净现值见表124三个项目的投资方案是：投资公司现在预付项目所需资金的百分比数，那么以后三年每年必须按此比例追加项目所需资金，也获得同样比例的净现值例如，公司按10投资项目1，现在必须支付400万，今后三年分别投入600万、900万和100万，获得净现值450万公司目前和预计今后三年可用于三个项目的投资金额是：现有2500万，一年后2000万，两年后2000万，三年后1500万当年没有用完的资金可以转入下一年继续使用IV 公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分比，使其投资获得的净现值最大 【解】以1为单位，计算累计投资比例和可用累计投资额，见表（2）。表（2） 设x j 为j 项目投资比例，则数学模型：max Z =45x 1+70x 2+50x 340x 1+80x 2+900x 32500100x 1+160x 2+140x 34500 190x 1+240x 2+160x 36500200x +310x +220x 8000123x j 0, j =1,2,3最优解X （0，16.5049，13.1067）；Z=1810.68万元 1.7 图解下列线性规划并指出解的形式：max Z =-2x 1+x 2x 1+x 21 (1 x 1-3x 2-1x , x 012【解】最优解X （1/2，1/2）；最优值Z=1/2min Z =-x 1-3x 2(2 2x 1-x 2-22x 1+3x 212x 0, x 021【解】最优解X （3/4，7/2）；最优值Z=45/4 min Z =-3x 1+2x 2x 1+2x 211-x +4x 1012 (32x 1-x 27x -3x 121x 1, x 20【解】最优解X （4，1）；最优值Z= 10max Z =x 1+x 23x 1+8x 212(4 x 1+x 22 2x 13x 1, x 20【解】最优解X （3/2，1/4）；最优值Z=7/4 min Z =x 1+2x 2x 1-x 22(5 x 13x 26x 1, x 20【解】最优解X （3，0）；最优值Z=3 max Z =x 1+2x 2x 1-x 22(6 x 13x 26x 1, x 20【解】无界解。 min Z =2x 1-5x 2x 1+2x 26 (7x 1+x 22x , x 012【解】无可行解。max Z =2.5x 1+2x 22x 1+x 28(8 0.5x 11.5x 1+2x 210x 1, x 20【解】最优解X （2，4）；最优值 Z=13 1.8 将下列线性规划化为标准形式 max Z =x 1+4x 2-x 32x 1+x 2+3x 320 (1 5x 1-7x 2+4x 3310x 1+3x 2+6x 3-5x 10, x 20, x 3无限制 【解】（1）令x 3=x 3-x 3, x 4, x 5, x 6为松驰变量 ，则标准形式为 max Z =x 1-4x 2-x 3+x 3 2x 1+x 2+3x 3-3x 3+x 4=20 5x 1-7x 2+4x 3-4x 3-x 5=3 -10x 1-3x 2-6x 3+6x 3+x 6=5 x 1, x 2, x 3, x 3, x 4, x 5, x 60min Z =9x 1-3x 2+5x 3|6x 1+7x 2-4x 3|20 (2 x 15 x 1+8x 2=-8x 10, x 20, x 30【解】（2）将绝对值化为两个不等式，则标准形式为max Z =-9x 1+3x 2-5x 36x 1+7x 2-4x 3+x 4=20-6x -7x +4x +x =201235 x -x =516-x -8x =821x 1, x 2, x 3, x 4, x 5, x 60max Z =2x 1+3x 21x 15(3-x 1+x 2=-1x 0, x 021【解】方法1：max Z =2x 1+3x 2x 1-x 3=1x +x =514x 1-x 2=1x 1, x 2, x 3, x 40=x 1-1, 有x 1x 1+1, x 15-1=4 方法2：令x 1+1 +3x 2max Z =2(x 14x 1+1 +x 2=-1-(x 1x , x 012则标准型为+3x 2max Z =2+2x 1+x 3=4x 1+x 2=0-x 1x , x , x 0123max Z =min(3x 1+4x 2, x 1+x 2+x 3x 1+2x 2+x 330(4 4x 1-x 2+2x 3159x 1+x 2+6x 3-5x 1无约束, x 2、x 30【解】令y 3x 1+4x 2, y x 1+x 2+x 3, x 1=x 1-x 1，线性规划模型变为max Z =y-x 1 +4x 2y 3(x 1y x -x +x +x1123-x 1+2x 2+x 330 x 1-x 1 -x 2+2x 3154(x 19(x 1-x 1 +x 2+6x 3-5, x 1, x 2、x 30x 1标准型为max Z =y+3x 1-4x 2+x 4=0y -3x 1y -x +x -x -x +x =011235-x 1+2x 2+x 3+x 6=30 x 1-4x 1-x 2+2x 3-x 7=154x 1-9x 1+9x 1-x 2-6x 3+x 8=5, x 1, x 2, x 3, x 4, x 5, x 6, x 7, x 80x 11.9 设线性规划max Z =5x 1+2x 22x 1+3x 2+x 3=504x -2x +x =60124x 0, j =1, , 4j2120取基B 1=(P1，P3 =分别指出B 1和B 2对应的基变量和非基变量，、B 241，40求出基本解，并说明B 1、B 2是不是可行基【解】B 1：x 1，x 3为基变量，x 2，x 4为非基变量, 基本解为X=（15，0，20，0）T ，B 1是可行基。B 2：x 1, x 4是基变量，x 2, x 3为非基变量，基本解X =（25，0，0，40）T ，B 2不是可行基。 1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点max Z =x 1+3x 2-2x 1+x 22 (12x +3x 1212x , x 012【解】图解法 最优解X =(, , Z =424min Z =-3x 1-5x 2x 1+2x 26 (2 x 1+4x 210x 1+x 24x 10, x 20【解】图解法 该题是退化基本可行解，5个基本可行解对应4个极点。1.11用单纯形法求解下列线性规划max Z =3x 1+4x 2+x 32x 1+3x 2+x 31(1x 1+2x 2+2x 33x 0, j =1, 2,3j max Z =2x 1+x 2-3x 3+5x 4x 1+5x 2+3x 3-7x 430(2 3x 1-x 2+x 3+x 4102x 1-6x 2-x 3+4x 420x j 0, j =1, , 4【解】单纯形表： 因为730并且a i 70(i =1,2,3，故原问题具有无界解，即无最优解。max Z =3x 1+2x 2-18x 3-x 1+2x 2+3x 34 (34x 1-2x 3123x 1+8x 2+4x 310x 1, x 2, x 30 原问题具有多重解。 基本最优解X(11273427237=(3,0, ,0 及X (2=(,0, , ,0 T ; Z =, 最优解的通解可表841111114示为X =aX (1 +(1-a X (2 即X =(3411227272-a , a , -a , -a ,0 T ,(0a 1 1111811111111min Z =-2x 1-x 2-4x 3+x 4x 1+2x 2+x 3-3x 48(4 -x 2+x 3+2x 410 2x 1+7x 2-5x 3-10x 420x j 0, j =1, , 4 max Z =3x 1+2x 2+x 35x 1+4x 2+6x 325（5）8x +6x +3x 24123x 0, j =1, 2,3j max Z =5x 1+6x 2+8x 3(6x 1+3x 2+2x 350x 1+4x 2+3x 380x 0, x 0, x 0231【解】单纯形表： 1.12 分别用大M 法和两阶段法求解下列线性规划：max Z =10x 1-5x 2+x 3(1 5x 1+3x 2+x 3=10-5x 1+x 2-10x 315x 0, j =1, 2,3j【解】大M 法。数学模型为max Z =10x 1-5x 2+x 3-Mx 55x 1+3x 2+x 3+x 5=10-5x 1+x 2-10x 3+x 4=15x 0, j =1, 2, ,5j 两阶段法。第一阶段：数学模型为min w =x 55x 1+3x 2+x 3+x 5=10-5x +x -10x +x =151234x 0, j = 1, 2, ,5j最优解X=(2,0,0；Z=20 min Z =5x 1-6x 2-7x 3x 1+5x 2-3x 3 15(2 5x 1-6x 2+10x 320x 1+x 2+x 3=5x j 0, j =1, 2,3【解】大M 法。数学模型为min Z =5x 1-6x 2-7x 3+MA 1+MA 3x 1+5x 2-3x 3-S 1+A 1=155x -6x +10x +S =201232x 1+x 2+x 3+A 3=5所有变量非负 第一阶段：数学模型为min w =A 1+A 3x 1+5x 2-3x 3-S 1+A 1=155x -6x +10x +S =201232x 1+x 2+x 3+A 3=5 所有变量非负 最优解：X=(0，3.75，1.25 ；Z=31.25 即 X =(0,155T 125, , Z =- 444max Z =10x 1+15x 25x 1+3x 29(3-5x 1+6x 2152x 1+x 25x 1、x 2、x 30【解】大M 法。数学模型为max Z =10x 1+15x 2-Mx 75x 1+3x 2+x 4=9-5x +6x +x =151252x 1+x 2-x 6+x 7=5x j 0, j = 1, 2, ,7 因为两阶段法第一阶段：数学模型为min Z =x 75x 1+3x 2+x 4=9-5x +6x +x =151252x 1+x 2-x 6+x 7=5x j 0, j =1,2, ,7 因为max Z =2x 1+3x 2-x