运筹学1至6章习题参考答案.doc

80运筹学(第3版) 习题答案运筹学1至6章习题参考答案第1章 线性规划1.1 工厂每月生产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.2 建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架两种窗架所需材料规格及数量如表124所示：表124 窗架所需材料规格及数量型号A型号B每套窗架需要材料长度（m）数量(根)长度(m)数量(根)A1：22B1：2.52A2：1.53B2：23需要量（套）300400问怎样下料使得（1）用料最少；（2）余料最少【解】 第一步：求下料方案，见下表。方案一二三四五六七八九十需要量B12.52111000000800B2201002110001200A120010010210600A21.50001002023900余料(m)00.50.51110100.5第二步：建立线性规划数学模型设xj（j=1,2,，10）为第j种方案使用原材料的根数，则（1）用料最少数学模型为（2）余料最少数学模型为1.3某企业需要制定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.4 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60，这种投资最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30，这种投资最多不超过1万元投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.【解】是设xij为第i年投入第j项目的资金数，变量表如下项目一项目二项目三项目四第1年第2年第3年x11x21x31x12x23x34数学模型为最优解X=(30000，0，66000，0，109200，0)；Z847201.5 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于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.6 图解下列线性规划并指出解的形式：(1) 【解】最优解X（3，2）；最优值Z=19 (2) 【解】有多重解。最优解X（1）（0，5/4）；X（2）（3，1/2）最优值Z=5(3) 【解】最优解X（4，1）；最优值Z=10，有唯一最优解(4) 【解】最优解X（2，3）；最优值Z=26，有唯一最优解(5) 【解】无界解。 (6)【解】无可行解。1.7 将下列线性规划化为标准形式 (1) 【解】（1）令为松驰变量 ，则标准形式为 (2) 【解】（2）将绝对值化为两个不等式，则标准形式为 (3) 【解】方法1：方法2：令则标准型为(4) 【解】令，线性规划模型变为标准型为1.8 设线性规划取基分别指出对应的基变量和非基变量，求出基本解，并说明是不是可行基【解】B1：x1、x3为基变量，x2、x4为非基变量,基本解为X=（15，0，10，0）T，B1是可行基。B2：x2、x4是基变量，x1、x3为非基变量，基本解X=（0，20，0，100）T，B2是可行基。1.9分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点 (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.10用单纯形法求解下列线性规划(1)【解】单纯形表：C(j)34100R. H. S.RatioBasisC(i)X1X2X3X4X5X402311044/3X501220133/2C(j)-Z(j)341000X242/311/31/30 4/32X50-1/304/3-2/311/3MC(j)-Z(j)1/30-1/3-4/3016/3X1313/21/21/202X5001/23/2-1/211C(j)-Z(j)0-1/2-1/2-3/20-6最优解：X=（2，0，0，0，1）；最优值Z6 (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.12 在第1.9题中，对于基求所有变量的检验数,并判断B是不是最优基【解】, B不是最优基，可以证明B是可行基。1.13已知线性规划的最优基为，试用矩阵公式求（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.14 已知某线性规划的单纯形表128, 求价值系数向量C及目标函数值Z表128Cjc1c2c3c4c5c6c7bCBXBx1x2x3x4x5x6x73x4012130244x1101020100x601404123/2j0110102【解】由有c21（31400（1）2c31（324（1）04）1c51（3（3）420（4）0c7-2（324(1)02）0则C(4,2,1,3,0,0,0,)，Z=CBXB=12 1.15 已知线性规划的最优单纯形表如表129所示，求原线性规划矩阵C、A、及b，最优基B及表129Cjc1c2c3c4c5bCBXBx1x2x3x4x5c1x11041/61/156c2x201301/52j00123【解】由c4c50，由公式得由 得 由 得 1.16思考与简答（1）在例1.2中，如果设xj(j=1，2，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化。（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路。（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1，模型如何变化。（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化。(5)在单纯形法中，为什么说当时线性规划具有无界解。(6)选择出基变量为什么要遵循最小比值规则，如果不遵循最小比值规则会是什么结果。（7）简述大M法计算的基本思路，说明在什么情形下线性规划无可行解。（8）设X(1)、X(2)、X(3)是线性规划的3个最优解，试说明也是线性规划的最优解。（9）什么是基本解、可行解、基本可行解、基本最优解，这四个解之间有何关系。（10）简述线性规划问题检验数的定义及其经济含义。返回顶部第2章 线性规划的对偶理论2.1某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位，C不少于180单位此人准备每天从六种食物中摄取这三种营养成分已知六种食物每百克的营养成分含量及食物价格如表2-22所示（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A，B，C三种营养成分试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型表2-22含量 食物营养成分一二三四五六需要量A1325144081180B24930251215150C1872134100180食物单价（元/100g）0.50.40.80.90.30.2【解】（1）设xj为每天第j种食物的用量，数学模型为（2）设yi为第i种单位营养的价格，则数学模型为2.2写出下列线性规划的对偶问题（1） 【解】（2） 【解】（3） 【解】（4） 【解】对偶问题为： 2.3考虑线性规划(1)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解；(3)利用公式CBB1求原问题的最优解；(4)利用互补松弛条件求原问题的最优解【解】(1)原问题的对偶问题为容易看出原问题和对偶问题都有可行解，如X(2，1)、Y(1，0，1)，由定理2.4知都有最优解。(2)对偶问题最优单纯形表为C(j)42700R. H. S.BasisC(i)y1y2y3y4y5y370-1/514/5-1/528/5y1417/50-3/52/54/5C(j)-Z(j)0-11/50-16/5-1/5w=42.4对偶问题的最优解Y(4/5,0,28/5)，由定理2.6，原问题的最优解为X=(16/5，1/5)，Z42.4（3）CB=(7,4), (4)由y1、y3不等于零知原问题第一、三个约束是紧的，解等式得到原问题的最优解为X=(16/5，1/5)。2.4证明下列线性规划问题无最优解证明：首先看到该问题存在可行解，例如x=(2,1,1)，而上述问题的对偶问题为由约束条件知y10，由约束条件当y20知y11，对偶问题无可行解，因此原问题也无最优解(无界解)。2.5已知线性规划的最优解，求对偶问题的最优解【解】其对偶问题是：由原问题的最优解知，原问题约束的松弛变量不等于零()，x1、x3不等于零，则对偶问题的约束、约束为等式，又由于知y30；解方程得到对偶问题的最优解Y=(5/2,5/2,0)；w55/227.52.6用对偶单纯形法求解下列线性规划 【解】将模型化为对偶单纯形表：cj34600CBXBX1X2X3X4X5b00X4X512223110011012C(j)-Z(j)34600003X4X101115/21/2101/21/246C(j)-Z(j)019/203/21853X2X101105/22111/2142C(j)-Z(j)0021122b列全为非负，最优解为x(2，4，0)；Z22 【解】将模型化为5400 b XB CB X1 X2 X3 X4 X30-1-110-6 X4021012CjZj3400 X1311-106 X400-121-10CjZj0130 X131011-4 X2401-2-110CjZj0051出基行系数全部非负，最小比值失效，原问题无可行解。【解】将模型化为 cj240