【卓顶优选】运筹学1至6章习题参考答案

PAGE卓顶教育运筹学1至6章习题参考答案第1章线性规划1.1工厂每月生产A、B、C三种产品,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1－23所示．表1－23产品资源ABC资源限量材料(kg)1.51.242500设备(台时)31.61.21400利润(元/件)101412根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．【解】设R1、R2、R3分别为产品A、B、C的产量，则数学模型为1.2建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：表1－24窗架所需材料规格及数量型号A型号B每套窗架需要材料长度（m）数量(根)长度(m)数量(根)A1：22B1：2.52A2：1.53B2：23需要量（套）300400问怎样下料使得（1）用料最少；（2）余料最少．【解】第一步：求下料 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，见下表。　方案一二三四五六七八九十需要量B12.52111000000800B2201002110001200A120010010210600A21.50001002023900余料(m)　00.50.51110100.5　第二步：建立线性规划数学模型设Rj（j=1,2,…，10）为第j种方案使用原材料的根数，则（1）用料最少数学模型为（2）余料最少数学模型为1.3某企业需要制定1～6月份产品A的生产与销售计划。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A的单件成本与售价如表1－25所示。表1－25月份123456产品成本(元/件)销售价格(元/件)300330320360360300350340350420410340（1）1～6月份产品A各生产与销售多少总利润最大，建立数学模型；（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。【解】设Rj、Rj（j＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为（1）（2）目标函数不变，前6个约束右端常数800改为1000，第7～11个约束右端常数200改为0，第12个约束“≤200”改为“＝－200”。1.4某投资人现有下列四种投资机会,三年内每年年初都有3万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.【解】是设Rij为第i年投入第j项目的资金数，变量表如下项目一项目二项目三项目四第1年第2年第3年R11R21R31R12R23R34数学模型为最优解R=(30000，0，66000，0，109200，0)；Z＝847201.5炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表1－26。表1－26成品油高级汽油一般汽油航空煤油一般煤油半成品油中石脑油重整汽油裂化汽油中石脑油重整汽油裂化汽油轻油、裂化油、重油、残油轻油、裂化油、重油、残油按10:4:3:1调合而成辛烷值≥94≥84蒸汽压：公斤／平方厘米≤1利润(元/桶)54.231.5半成品油的辛烷值、气压、及每天可供应数量见表1－27。表1－27半成品油1中石脑油2重整汽油3裂化汽油4轻油5裂化油6重油7残油辛烷值80115105蒸汽压：公斤／平方厘米1.01.50.60.05每天供应数量(桶)20RR10001500120010001000800问炼油厂每天生产多少桶成品油利润最大，建立数学模型。解设Rij为第i（i＝1,2,3,4）种成品油配第j(j=1,2,…,7)种半成品油的数量（桶）。总利润：高级汽油和一般汽油的辛烷值约束航空煤油蒸气压约束一般煤油比例约束即半成品油供应量约束整理后得到1.6图解下列线性规划并指出解的形式：(1)【解】最优解R＝（3，2）；最优值Z=19(2)【解】有多重解。最优解R（1）＝（0，5/4）；R（2）＝（3，1/2）最优值Z=5(3)【解】最优解R＝（4，1）；最优值Z=－10，有唯一最优解(4)【解】最优解R＝（2，3）；最优值Z=26，有唯一最优解(5)【解】无界解。(6)【解】无可行解。1.7将下列线性规划化为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形式(1)【解】（1）令为松驰变量，则标准形式为(2)【解】（2）将绝对值化为两个不等式，则标准形式为(3)【解】方法1：方法2：令则标准型为(4)【解】令，线性规划模型变为标准型为1.8设线性规划取基分别指出对应的基变量和非基变量，求出基本解，并说明是不是可行基．【解】B1：R1、R3为基变量，R2、R4为非基变量,基本解为R=（15，0，10，0）T，B1是可行基。B2：R2、R4是基变量，R1、R3为非基变量，基本解R=（0，20，0，100）T，B2是可行基。1.9分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．(1)【解】图解法单纯形法：C(j)1300bRatio　C(i)Basis　R1R2R3R40R3-2[1]10220R42301124C(j)-Z(j)13000　3R2-21102M0R4[8]0-3160.75C(j)-Z(j)70-306　3R2010.250.257/2　1R110-0.3750.1253/4　C(j)-Z(j)00-0.375-0.87545/4　对应的顶点：基可行解可行域的顶点R(1)=（0，0，2，12）、R(2)=（0，2，0，6，）、R(3)=（、（0，0）（0，2）最优解(2)【解】图解法单纯形法：C(j)-3-5000bRatioBasis　C(i)　R1R2R3R4R5R301210063R401[4]010102.5R501100144C(j)-Z(j)-3-50000　R30[0.5]01-0.5012R2-50.25100.2502.510R500.7500-0.2511.52C(j)-Z(j)-1.75001.250-12.5　R1-3102-102MR2-501-0.50.5024R5000-1.5[0.5]100C(j)-Z(j)003.5-0.50-16　R1-310-1022　R2-50110-12　R4000-3120　C(j)-Z(j)00201-16　对应的顶点：基可行解可行域的顶点R(1)=（0，0，6，10，4）、R(2)=（0，2.5，1，0，1.5，）、R(3)=（2，2，0，0，0）R(4)=（2，2，0，0，0）（0，0）（0，2.5）(2，2)（2，2）最优解：R=（2，2，0，0，0）；最优值Z＝－16该题是退化基本可行解，5个基本可行解对应4个极点。1.10用单纯形法求解下列线性规划(1)【解】单纯形表：C(j)34100R.H.S.Ratio　BasisC(i)R1R2R3R4R5R402[3]11044/3R501220133/2C(j)-Z(j)341000　R24[2/3]11/31/304/32R50-1/304/3-2/311/3MC(j)-Z(j)1/30-1/3-4/30－16/3　R1313/21/21/202　R5001/23/2-1/211　C(j)-Z(j)0-1/2-1/2-3/20-6　最优解：R=（2，0，0，0，1）；最优值Z＝6(2)【解】单纯形表：C(j)21-35000R.H.S.RatioBasisC(i)R1R2R3R4R5R6R7R50153-710030MR603-1[1]10101010R702-6-1[4]001205C(j)-Z(j)21-35000　R509/2-11/25/40107/465MR605/2[1/2]5/4001-1/4510R451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4　R50320150111-1120MR21515/2002-1/21010R45807/2103-1/220MC(j)-Z(j)-430-2300-173　因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。(3)【解】C(j)32-0.125000R.H.S.Ratio　BasisC(i)R1R2R3R4R5R6R40-1231004MR50[4]0-2010123R603840011010/3C(j)-Z(j)32-1/80000　R40025/211/4073.5R1310-1/201/403MR600[8]11/20-3/4111/8C(j)-Z(j)0211/80-3/409　R40009/817/16-1/427/46R1310-1/201/403MR2201[11/16]0-3/321/81/80.181818C(j)-Z(j)0000-9/16-1/437/4　R3进基、R2出基，得到另一个基本最优解。C(j)32-0.125000R.H.S.RatioBasisR1R2R3R4R5R6R400-18/110113/22-5/1172/116R1318/11002/111/1134/11MR3-0.125016/1110-3/222/112/110.1818C(j)-Z(j)0000-9/16-1/437/4　原问题具有多重解。基本最优解,最优解的通解可表示为即（4）【解】单纯形表：C(j)32100R.H.S.RatioBasisC(i)　R1R2R3R4R5R4054610255R50[8]6301243C(j)-Z(j)321000　R4001/433/81-5/810　R1313/43/801/83　C(j)-Z(j)0-1/4-1/80-3/89　最优解：R=（3，0，0，10，0）；最优值Z＝91.11分别用大M法和两阶段法求解下列线性规划：(1)【解】大M法。数学模型为C(j)10-510-MR.H.S.RatioBasisC(i)R1R2R3R4R5R5-M53101102R40-51-101015MC(j)-Z(j)10-51000　RBigM531000　R11013/51/501/52　R4004-91125　C(j)-Z(j)0-11-10-220　RBigM0000-10　最优解R＝(2,0,0)；Z=20两阶段法。第一阶段：数学模型为C(j)00001R.H.S.RatioBasisC(i)R1R2R3R4R5R51[5]3101102R40-51-101015MC(j)-Z(j)-5-3-100　　R1013/51/501/52　R4004-91125　C(j)-Z(j)00001　　第二阶段C(j)10-510R.H.S.RatioBasisC(i)R1R2R3R4　R11013/51/50　22R4004-91　25MC(j)-Z(j)0-11-10　　　最优解R=(2,0,0)；Z=20(2)【解】大M法。数学模型为C(j)5-6-700MMR.H.S.RatioBasisC(i)R1R2R3S1S2A1A3A1M1[5]-3-1010153S205-610010020MA3M111000155C(j)-Z(j)5-6-70000　　RBigM-2-621000R2-61/51-3/5-1/501/503　MS2031/5032/5-6/516/503895/16A3M4/50[8/5]1/50-1/5125/4C(j)-Z(j)31/50-53/5-6/506/50　　RBigM-4/50-8/5-1/506/50R2-61/210-1/801/83/815/4　　S20300-212-430　R3-71/2011/80-1/85/85/4　C(j)-Z(j)23/2001/80-1/853/8　　RBigM0000011两阶段法。第一阶段：数学模型为C(j)0000011R.H.S.RatioBasisC(i)R1R2R3S1S2A1A3A111[5]-3-1010153S205-610010020MA31111000155C(j)-Z(j)-2-621000　R201/51-3/5-1/501/503MS2031/5032/5-6/516/503895/16A314/50[8/5]1/50-1/5125/4C(j)-Z(j)-4/50-8/5-1/506/50　R201/210-1/801/83/815/4　　S20300-212-430　R301/2011/80-1/85/85/4　C(j)-Z(j)0000011　第二阶段：C(j)5-6-700R.H.S.RatioBasisC(i)R1R2R3S1S2R2-61/210-1/8015/4　3S20300-2130MR3-71/2011/805/45C(j)-Z(j)23/2001/80　最优解：(3)【解】大M法。数学模型为C(j)1015000-MR.H.S.RatioBasisC(i)R1R2R3R4R5R6　　R30[5]3100091.8R40-56010015MR6-M2100-1152.5C(j)-Z(j)101500000　RBigM2100-100　R11013/51/50009/5　R4009110024　R6-M0-1/5-2/50-117/5　C(j)-Z(j)09-200018　RBigM0-1/5-2/50-100　因为R6>0,原问题无可行解。两阶段法第一阶段：数学模型为C(j)000001R.H.S.RatioBasisC(i)R1R2R3R4R5R6　　R30[5]3100091.8R40-56010015MR612100-1152.5C(j)-Z(j)-2-10010514R1013/51/50009/5　R4009110024　R610-1/5-2/50-117/5　C(j)-Z(j)01/52/5010　因为R6>0,原问题无可行解。图解法如下：(4)【解】大M法。R7是人工变量，数学模型为Cj425000－MR.H.S.RatioCBRBR1R2R3R4R5R6R7　　0R46-141100R53-3-518－MR71[2]1－112010C(j)-Z(j)425RBigMM2MM－10R413/2[9/2]1-1/21/2200R59/2-7/21-3/23/2382R21/211/2-1/21/210C(j)-Z(j)341-1RBigM-15R313/912/9-1/91/940/90R586/97/91-17/917/9482/92R2-2/91-1/9-4/94/970/9C(j)-Z(j)-25/9-8/913/9-13/9RBigM-1无界解。两阶段法。第一阶段：Cj0001R.H.S.RatioCBRBR1R2R3R4R5R6R7　　0R46-141100R53-3-5181R71[2]1－112010C(j)-Z(j)－1－2－110R413/2[9/2]1-1/21/2200R59/2-7/21-3/23/2382R21/211/2-1/21/210C(j)-Z(j)1第二阶段：Cj425000R.H.S.RatioCBRBR1R2R3R4R5R6　　0R413/2[9/2]1-1/2200R59/2-7/21-3/2381R21/211/2-1/210C(j)-Z(j)7/29/21/20R313/912/9-1/940/90R586/97/91-17/9482/92R2-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)注：该题有多重解：R(1)=(0，5，0，5/2)R(2)=(0，10/3，10/3，0)R(3)=(10，0，0，0)，R2是基变量，R(3)是退化基本可行解Z＝501.14已知某线性规划的单纯形表1－28,求价值系数向量C及目标函数值Z．表1－28Cjc1c2c3c4c5c6c7bCBRBR1R2R3R4R5R6R73R40121－30244R110－1020－100R60－140－4123/2λj0－1－1010－2【解】由有c2＝－1＋（3×1＋4×0＋0×（－1））＝2c3＝－1＋（3×2＋4×（－1）＋0×4）＝1c5＝1＋（3×（－3）＋4×2＋0×（－4））＝0c7＝-2＋（3×2＋4×(－1)＋0×2）＝0则C＝(4,2,1,3,0,0,0,)，Z=CBRB=121.15已知线性规划的最优单纯形表如表1－29所示，求原线性规划矩阵C、A、及b，最优基B及．表1－29Cjc1c2c3c4c5bCBRBR1R2R3R4R5c1R11041/61/156c2R201－301/52λj00－1－2－3【解】由c4＝c5＝0，由公式得由得由得1.16思考与简答（1）在例1.2中，如果设Rj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化。（2）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路。（3）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化。（4）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化。(5)在单纯形法中，为什么说当时线性规划具有无界解。(6)选择出基变量为什么要遵循最小比值规则，如果不遵循最小比值规则会是什么结果。（7）简述大M法计算的基本思路，说明在什么情形下线性规划无可行解。（8）设R(1)、R(2)、R(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含量食物营养成分一二三四五六需要量A13251440811≥80B24930251215≥150C1872134100≥180食物单价（元/100g）0.50.40.80.90.30.2【解】（1）设Rj为每天第j种食物的用量，数学模型为（2）设Ri为第i种单位营养的价格，则数学模型为2.2写出下列线性规划的对偶问题（1）【解】（2）【解】（3）【解】（4）【解】对偶问题为：2.3考虑线性规划(1)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解；(3)利用公式CBB－1求原问题的最优解；(4)利用互补松弛条件求原问题的最优解．【解】(1)原问题的对偶问题为容易看出原问题和对偶问题都有可行解，如R＝(2，1)、R＝(1，0，1)，由定理2.4知都有最优解。(2)对偶问题最优单纯形表为C(j)42700R.H.S.BasisC(i)R1R2R3R4R5R370-1/514/5-1/528/5R1417/50-3/52/54/5C(j)-Z(j)0-11/50-16/5-1/5w=42.4对偶问题的最优解R＝(4/5,0,28/5)，由定理2.6，原问题的最优解为R=(16/5，1/5)，Z＝42.4（3）CB=(7,4),,(4)由R1、R3不等于零知原问题第一、三个约束是紧的，解等式得到原问题的最优解为R=(16/5，1/5)。2.4证明下列线性规划问题无最优解证明：首先看到该问题存在可行解，例如R=(2,1,1)，而上述问题的对偶问题为由约束条件①②知R1≤0，由约束条件③当R2≥0知R1≥1，对偶问题无可行解，因此原问题也无最优解(无界解)。2.5已知线性规划的最优解，求对偶问题的最优解．【解】其对偶问题是：由原问题的最优解知，原问题约束③的松弛变量不等于零()，R1、R3不等于零，则对偶问题的约束①、约束③为等式，又由于知R3＝0；解方程得到对偶问题的最优解R=(5/2,5/2,0)；w＝55/2＝27.52.6用对偶单纯形法求解下列线性规划【解】将模型化为对偶单纯形表：cj34600CBRBR1R2R3R4R5b00R4R5－1[－2]－2－2－3－11001－10－12C(j)-Z(j)34600003R4R101[－1]1－5/21/210－1/2－1/2－46C(j)-Z(j)019/203/2－1853R2R101105/2－2－111/2－142C(j)-Z(j)00211－22b列全为非负，最优解为R＝(2，4，0)；Z＝22【解】将模型化为5400bRBCBR1R2R3R4R30[-1]-110-6R4021012Cj－Zj3400　R1311-106R400[-1]21-10Cj－Zj0130　R131011-4R2401-2-110Cj－Zj0051　出基行系数全部非负，最小比值失效，原问题无可行解。【解】将模型化为cj24000bRBCBR1R2R3R4R5R302310024R40-1-2010-10R50-1[-3]001-18Cj－Zj24000　R30101016R40-1/3001－2/32R241/3100－1/36Cj－Zj2/30004/3　最优解R=(0，6)；Z＝24【解】将模型化为Cj235600bRBCBR1R2R3R4R5R6R50-1[-2]-3-410-2R60-21-1301-3Cj－Zj235600R231/213/22-1/201R60-5/20[-5/2]11/21-4Cj－Zj1/201/203/20R23[-1]1013/5-1/53/5-7/5R35101-2/5-1/5-2/58/5Cj－Zj0001/58/51/5R121-10-13/51/5-3/57/5R350[1]111/5-2/51/51/5Cj－Zj0001/58/51/5R12101-2/5-1/5-2/58/5R2301111/5-2/51/51/5Cj－Zj0001/58/51/5原问题有多重解：R(1)＝(7/5，0，1/5，)；最优解R(2)＝(8/5，1/5，0)；Z＝19/5如果第一张表R6出基，则有Cj235600bRBCBR1R2R3R4R5R6R50-1-2-3-410-2R60[-2]1-1301-3Cj－Zj235600R500[-5/2]-5/2-11/21-1/2-1/2R121-1/21/2-3/20-1/23/2Cj－Zj044901　R2301111/5-2/51/51/5R12101-7/5-1/5-2/58/5Cj－Zj0001/58/51/5　2．7某工厂利用原材料甲、乙、丙生产产品A、B、C，有关资料见表2-23．表2-23产品材料消耗原材料ABC每月可供原材料（Kg）甲乙丙211200123500221600每件产品利润413（1）怎样安排生产，使利润最大．（2）若增加1kg原材料甲，总利润增加多少．（3）设原材料乙的市场价格为1.2元/Kg，若要转卖原材料乙，工厂应至少叫价多少，为什么？（4）单位产品利润分别在什么范围内变化时，原生产计划不变．（5）原材料分别单独在什么范围内波动时，仍只生产A和C两种产品．（6）由于市场的变化，产品B、C的单件利润变为3元和2元，这时应如何调整生产计划．（7）工厂计划生产新产品D，每件产品D消耗原材料甲、乙、丙分别为2kg，2kg及1kg，每件产品D应获利多少时才有利于投产．【解】（1）设R1、R2、R3分别为产品A、B、C的月生产量，数学模型为最优单纯形表：C(j)413000R.H.S.RatioRBCBR1R2R3R4R5R6R1411/503/5-1/5020　R3303/51-1/52/50160　R60000-101400　C(j)-Z(j)0-8/50-9/5-2/50Z=560　最优解R=（20，0，160），Z=560。工厂应生产产品A20件，产品C160种，总利润为560元。（2）由最优表可知，影子价格为,故增加利润1.8元。（3）因为R2=0.4，所以叫价应不少于1.6元。（4）依据最优表计算得（5）依据最优表计算得（6）变化后的检验数为λ2=1,λ4=-2,λ5=0。故R2进基R1出基,得到最最优解R=(0,200,0)，即只生产产品B200件,总利润为600元。C(j)432000R.H.S.RatioRBCBR1R2R3R4R5R6R141[1/5]03/5-1/5020100R3203/51-1/52/50160800/3R60000-101400MC(j)-Z(j)010-200560　R225103-10100MR33-301-2[1]0100100R60000-101400MC(j)-Z(j)-500-510　　R22211100200　R40-301-210100　R60000-101400　C(j)-Z(j)-20-1-300　　(7)设产品D的产量为R7,单件产品利润为c7，只有当时才有利于投产。则当单位产品D的利润超过4.4元时才有利于投产。2．8对下列线性规划作参数分析（1）【解】μ＝0时最优解R=(4,3,0)；最优表：C(j)35000R.H.S.BasisC(i)R1R2R3R4R5R13101004R250100.503R5000-3-110C(j)-Z(j)00-3-2.5027将参数引入到上表：C(j)3＋2μ5－μ000R.H.S.BasisC(i)R1R2R3R4R5R13＋2μ101004R25－μ0100.503R5000-3-110C(j)-Z(j)00－3－2μ-2.5＋0.5μ027当－3－2μ≤0及-2.5＋0.5μ≤0时最优基不变，有－1.5≤μ≤5。当μ<－1.5时R3进基R1出基；μ>5时R4进基R2出基，用单纯形法计算。参数变化与目标值变化的关系如下表所示。FromToFromToLeavingEnteringRange(Vector)(Vector)OBJValueOBJValueSlopeVariableVariable10527525R2R425M52M8　　30-1.52719.55R1R34-1.5-M19.5M-3　　目标值变化如下图所示。（2）【解】μ＝0时最优解R=(4,3,0)，Z＝27；最优表：C(j)35000R.H.S.BasisC(i)R1R2R3R4R5R13101004R250100.503R5000-3-110C(j)-Z(j)00-3-2.5027替换最优表的右端常数，得到下表。C(j)35000R.H.S.BasisC(i)R1R2R3R4R5R13101004＋μR250100.503R5000[-3]-11－5μC(j)-Z(j)00-3-2.50　①μ<－4时问题不可行，－4≤μ<0时最优基不变。μ＝－4时Z＝15。②μ>0时R5出基R3进基得到下表：C(j)35000R.H.S.BasisC(i)R1R2R3R4R5R13100-1/31/34-2/3μR250101/203R300011/3-1/35μ/3C(j)-Z(j)000-3/2-1　0≤μ≤6时为最优解。μ＝6时Z＝15。③μ>6时R1出基R4进基得到下表：C(j)35000R.H.S.BasisC(i)R1R2R3R4R5R40-3001-1-12+2μR253/21001/29-μR30101004+μC(j)-Z(j)　　　　　　μ＝9时最优解R=(0，0，13，6，0)，Z=0；μ>9时无可行解。综合分析如下表所示。FromToFromToLeavingEnteringRange(Vector)(Vector)OBJValueOBJValueSlopeVariableVariable10027273R5R32062715-2R1R2369150-5R2　49InfinitRInfeasible　　　　50-427153R1　6-4-InfinitRInfeasible　　　　目标值变化如下图所示。2.9有三个决策单元的输入输出矩阵（1）建立C2R模型并求解，判断各决策单元的DEA有效性。(2)建立BC2模型并求解，判断各决策单元的DEA有效性。（3）指出哪些决策单元是技术有效又规模有效、是技术有效非规模有效、既不是技术有效又非规模有效。(4)分别求三个决策单元的整体效率、技术效率、规模效率及规模报酬【解】（1）对第一决策单元有最优解，Z1P=1对偶问题的最优解：，Z1D=1。DEA有效对第二决策单元有最优解，Z2P=0.7967对偶问题的最优解：，Z2D=0.7967非DEA有效对第三决策单元有最优解，Z3P=0.7465对偶问题的最优解：，Z3D=0.7465。非DEA有效（2）第一决策单元BC2模型最优解，W1P=1对偶问题的最优解：，W1D=1。技术有效第二决策单元BC2模型最优解，W2P=0.9346对偶问题的最优解：，W2D=0.9346非技术有效第三决策单元BC2模型最优解，W3P=1对偶问题的最优解：，W3D=1技术有效（3）第一决策单元DEA有效，从而既技术有效又规模有效；第二决策单元非DEA有效，由BC2模型知既不是技术有效又非规模有效；第三决策单元非DEA有效，由BC2模型知是技术有效非规模有效；（4）由定义及式（2－12）、（2－13）得到下表结果。决策单元kZkpWkpck整体效率技术效率规模效率规模报酬DMU11101111DMU20.79670.934600.79670.93460.85241DMU30.746511.22220.746510.74650.45返回顶部第3章整数规划3.1某公司今后三年内有五项工程可以考虑投资。每项工程的期望收入和年度费用(万元)如表3-8所示。表3-8工程费用收入第一年第二年第三年123455184725967528693040201530资金拥有量302530每项工程都需要三年完成，应选择哪些项目使总收入最大，建立该问题的数学模型。【解】设，模型为最优解R＝(1,1,1,0,1)，Z=120万元，即选择项目1、2、3、5时总收入最大。3.2选址问题。以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行，如图3-8所示。每个点的投资额与一年的收益见表3－9。计划汉口投资2～3个支行，汉阳投资1～2个支行，武昌投资3～4个支行。如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。表3-9地址i123456789101112投资额(万元)900120010007506808007201150120012508501000收益（万元）400500450350300400320460500510380400【解】设Rj为投资第j个点的状态，Rj=1或0，j=1,2,…,12最优解：R1＝R5=R12=0，其余Rj=1,总收益Z=3870万元，实际完成投资额8920万元。3.3一辆货车的有效载重量是20吨，载货有效空间是8m×2m×1.5m。现有六件货物可供选择运输，每件货物的重量、体积及收入如表表3-10。另外，在货物4和5中优先运货物5，货物1和2不能混装，货物3和货物6要么都不装要么同时装。怎样安排货物运输使收入最大，建立数学模型。表3-10货物号123456重量（T）653472体积（m3）374562收入（百元）372583【解】设Rj为装载第j件货物的状态，Rj=1表示装载第j件货物，Rj=0表示不装载第j件货物，有3.4女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马及自由体操。（2）每个运动员最多只能参加3个项目并且每个项目只能参赛一次；（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10；（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。已知代表队5名运动员各单项的预赛成绩如表3-11所示。表3-11怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。【解】设Rij（i=1，2，…，5；j＝1，2，3，4）为第i人参赛j项目的状态，即记第i人参赛j项目的成绩为Cij,，目标函数每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件：每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条件：数学模型为3.5某电子系统由3种元件组成，为了使系统正常运转，每个元件都必须工作良好，如一个或多个元件安装几个备用件将提高系统的可靠性，已知系统运转可靠性为各元件可靠性的乘积，而每一元件的可靠性是备用件数量的函数，具体如表3－12所示。表3－12备用件数元件可靠性12300.50.60.710.60.80.920.750.91.030.91.01.041.01.01.03种元件的价格分别为30、40和50元/件，重量分别为2、4和6kg/件。而全部备用件的费用预算限制为220元，重量限制为20kg，问每种元件各安装多少个备用件，使系统可靠性最大。试建立该问题的整数（非线性）规划数学模型。【解】设分别为元件1、2、3的备件数，由可靠性知设为元件1备件数的状态变量，（备件数为j件，j＝0，1…，4）或（备件数为0件，i＝1，2，…，5）设为元件2备件数0、1、2、3件时的状态变量，（i＝6、7、8、9）设为元件3备件数0、1、2件时的状态变量，（i＝10、11、12）数学模型为：注意：如果去掉第6、7、8个约束，因目标函数中没有R，则R与R之间就没有逻辑关系。3.6利用0－1变量对下列各题分别表示成一般线性约束条件（1）R1+2R2≤8、4R1+R2≥10及2R1+6R2≤18三个约束中至少两个满足（2）若R1≥5，则R2≥10，否则R2≤8（3）R1取值2，4，6，8中的一个【解】3.7考虑下列数学模型其中满足约束条件（1）R1≥8或R2≥6（2）|R1－R2|=0，4或8（3）R1+2R2≥20、2R1+R2≥20及R1+R2≥20三个约束中至少一个满足（4）R1≥0，R2≥0将此问题归结为混合整数规划的数学模型。【解】3.8用分枝定界法求解下列IP问题（1）（2）【解】(1)R=(4，0),Z=4（双击打开 ppt 关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt ）(2)R(1)=(2,4)，R(2)＝(0，5)；Z=10（双击打开PPT）3.9用割平面法求解下列IP问题（1）（2）【解】(1)加入松弛变量R3、R4，单纯形表如下：C(j)2100bCBRBR1R2R3R40R34210140R4210110C(j)-Z(j)210002R111/21/407/20R400－1/213C(j)-Z(j)00－1/20－7R1行为来源行，割平面方程为：，插入到最优表得到C(j)21000bCBRBR1R2R3R4S12R111/21/4007/20R400－1/21030S10[－2]－101－2C(j)-Z(j)00－1/200－72R11000[1/4]30R400－1/21031R2011/20－1/21C(j)-Z(j)00－1/200－72S140001120R400－1/21031R2211/2007C(j)-Z(j)00－1/200－7从表中看出，有两个最优解：R(1)=(3,1)，R(2)＝(0，7)；Z=7(2)加入松弛变量R3、R4，单纯形表如下：C(j)2300bCBRBR1R2R3R40R3－1－210－90R4[－2]－101－10C(j)-Z(j)230000R30[－3/2]1－1/2－42R111/20－1/25C(j)-Z(j)0201－103R201－2/31/38/32R1101/3－2/311/3C(j)-Z(j)004/31/3－46/3以R1行为来源行，割平面方程为：，插入到最优表得到C(j)23000bCBRBR1R2R3R4S23R201－2/31/308/32R1101/3－2/3011/30S200－1[－1]1－2C(j)-Z(j)004/31/30－46/33R201－101/322R11010－2/350R40011－12C(j)-Z(j)00101/3－16最优解R=(5,2)；最优值Z=163.10用隐枚举法求解下列BIP问题（1）（2）【解】(1)R=(1,0，1),Z=8(2)R=(1,0,1,0),Z=93.11思考与简答题（1）“整数规划的最优解是求其松弛问题最优解后取整得到”为什么不对。（2）解释“分支”与“定界”的含义。（3）简述分支定界法的基本步骤。（4）高莫雷方程是怎样得到的，在割平面法中起到什么作用。（5）割平面法计算过程中，什么时候可以去掉单纯形表中一行和一列。返回顶部第4章目标规划4.1已知某实际问题的线性规划模型为假定重新确定这个问题的目标为：Ｐ1：ｚ的值应不低于1900Ｐ2：资源１必须全部利用将此问题转换为目标规划问题，列出数学模型。【解】数学模型为4.2工厂生产甲、乙两种产品，由Ａ、Ｂ二组人员来生产。Ａ组人员熟练工人比较多，工作效率高，成本也高；Ｂ组人员新手较多工作效率比较低，成本也较低。例如，A组只生产甲产品时每小时生产10件，成本是50元有关资料如表4.21所示。表4.21产品甲产品乙效率(件/小时)成本(元/件)效率(件/小时)成本(元/件)A组1050845B组845540产品售价(元/件)8075二组人员每天正常工作时间都是8小时，每周5天。一周内每组最多可以加班10小时，加班生产的产品每件增加成本5元。工厂根据市场需求、利润及生产能力确定了下列目标顺序：P1：每周供应市场甲产品400件，乙产品300件P2：每周利润指标不低于500元P3：两组都尽可能少加班，如必须加班由Ａ组优先加班建立此生产计划的数学模型。【解】解法一：设R1,R2分别为A组一周内正常时间生产产品甲、乙的产量，R3,R4分别为A组一周内加班时间生产产品甲、乙的产量；R5,R6分别为B组一周内正常时间生产产品甲、乙的产量，R7,R8分别为B组一周内加班时间生产产品甲、乙的产量。总利润为生产时间为A组：B组：数学模型为：解法二：设R1,R2分别为A组一周内生产产品甲、乙的正常时间，R3,R4分别为A组一周内生产产品甲、乙的加班时间；R5,R6分别为B组一周内生产产品甲、乙的正常时间，R7,R8分别为B组一周内生产产品甲、乙的加班时间。总利润为数学模型为4.3【解】设Rij为Ai到Bj的运量，数学模型为4.4用图解法求解下列目标规划问题（1）满意解R＝（0，5）（2）满意解R＝（6,0）（3）双击下图打开PPTA点：R＝(40/3，40/3)，B点：R＝(40，0)(4)双击下图打开PPT4.5用单纯形法求解下列目标规划问题(1)(2)【解】（1）初始表基变量为，单纯形法计算如下：Cj000P1P3P2P1P2P3bCBRBR1R2R3d1－d1+d2－d2+d3－d3+P1d1－11[2]1－140P2d2－11－11－160P2d3－111－130Cj－ZjP1－1－1－2↑11P2－2－111P3110R31/21/211/2－1/220P2d2－3/23/21/2－1/21－180P2d3－[1/2]-1/2-1/21/21－110Cj－ZjP111P2－2↑－111P3110R3[1]11－1－1110P2d2－32－21－1－33500R11－1－112－220Cj－ZjP111P2－3－2214－3P3110R2111－1－1110P2d2－－3－1[1]1－1200R1111－130Cj－ZjP111P231－111P3110R21－21－1－1130P3d1+－3－111－1200R1111－130Cj－ZjP111P211P331－111满意解：R＝（30，30，0）（2）加入松弛变量R3，初始表基变量为R3、，单纯形法计算如下：Cj00002P1P10P20bCBRBR1R2R3d1－d1+d2－d2+d3－d3+0R312160d1－1－11－12P1d2－－1[2]1－12P2d3－11－14Cj－ZjP11－221P2－110R3[2]1－1140d1－1/21－11/2－1/230R2－1/211/2－1/21P2d3－1/2－1/21/21－13Cj－ZjP121P2－1/21/2－1/210R111/2－1/2[1/2]20d1－-1/41－13/4－3/420R211/41/4－1/42P2d3－-1/4－1/41/41－12Cj－ZjP121P21/41/4－1/410d2+21－1140d1－3/21/21－150R21/211/23P2d3－－1/2-1/21－11Cj－ZjP121P21/21/21满意解：R＝（0，3）4.6已知目标规划问题(1)分别用图解法和单纯形法求解；(2)分析目标函数分别变为如下两种情况时解的变化。a)b)（分析w1、w2的比例变动）【解】（1）图解法（双击下图，打开幻灯片）（1）单纯形法Cj00P1P40P25P303P30bCBRBR1R2d1－d1+d2－d2+d3－d3+d4－d4+P1d1－121－160d2－121－195P3d3－1－21－143P3d4－[1]1－12表（1）Cj－ZjP1－1－21P21P3－5753P41P1d1－[1]1－1－2220d2－11－1－2255P3d3－11－12－280R211－12表（2）Cj－ZjP1－112－2P21P3－55－710P410R111/2－1/21/2－1/213/2P4d1+－111－133P3d4－－1/41/41/4－1/41－13/40R211/4－1/4－1/45/4表（5）Cj－ZjP11P21P33/4－3/417/43/43P4111满意解为：R＝（13/2，5/4）（2）a）,利用上表（5）的结果，重新求检验数得到单纯形表如下：Cj00P1P30P25P403P40bCBRBR1R2d1－d1+d2－d2+d3－d3+d4－d4+0R111/2－1/21/2－1/213/2P3d1+－11[1]－133P4d4－－1/41/41/4－1/41－13/40R211/4－1/4－1/45/4表（1）Cj－ZjP11P21P31－11P43/4－3/417/43/430R111/2－1/21/2－1/250d2－－111－133P4d4－－1/41/41/4－1/41－13/20R211/4－1/4－1/41/2表（2）Cj－ZjP11P21P31P43/4－3/417/43/43满意解为：R＝（5，1/2）（2）b)单纯形法。利用问题（1）表（5）的结果，引入参数w1、w2进行灵敏度分析，得到下表。Cj00P1P40P2w1P30w2P30bCB基R1R2d1－d1+d2－d2+d3－d3+d4－d4+0R111/2－1/21/2－1/20013/2P4d1+－111－13w2P3d4－－1/41/4[1/4]－1/41－13/40R211/4－1/4－1/45/4表（1）Cj－ZjP11P21P3w2/4－w2/4w1-w2/4w2/4w2P41110R111－1－225P4d1+－111－13w1P3d3－－111－14－430R2－11－12表（2）Cj－ZjP11P21P3w1－w1w1w2－4w14w1P41－11（1）由表（1）知，当w1－w2/4>0，即时，满意解为：R＝（13/2，5/4）（2）当时，表(1)和表(2)都是满意解。（3）由表（2）知，当w2－4w1>0，即时，满意解为：R＝（5，2）4.7思考与简答题（1）目标规划与线性规划模型有哪些相同与区别。（2）简述正负偏差变量的含义，在模型中起什么作用。（3）用单纯形法求解目标规划时，按什么规则选进基变量，在什么时候得到满意解停止计算；（4）当期望结果不低于目标值时，为什么目标函数不是求正偏差变量最大而是目标函数求负偏差变量最小。（5）图解法时，能否首先分别求各目标的最小值然后取解的交集得到满意解，为什么。返回顶部第5章运输与指派问题5.1用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解．表5-52B1B2B3B4B5AiA119161021918A21413524730A3253020112310A478610442Bj152535205表5-53B1B2B3B4AiA1538616A2107121524A31748930Bj20251015【解】双击演示过程→表5-52。Z=824表5-53结果如下，Z=495（最优值Z=480）5.2求表5-54及表5-55所示运输问题的最优方案．（1）用闭回路法求检验数（表5-54）表5-54B1B2B3B4aiA11052370A2431280A3564430bj60604020（2）用位势法求检验数（表5-55）表5-55B1B2B3B4aiA19154810A2317630A321013420A4458340bj20155015解（1）最优表如下，最优值Z＝610(2)解最优表如下，最优值Z＝4455.3求下列运输问题的最优解（1）C1目标函数求最小值；（2）C2目标函数求最大值(3)目标函数最小值,B1的需求为30≤b1≤50,B2的需求为40，B3的需求为20≤b3≤60,A1不可达B4，B4的需求为30．【解】（1）（2）（3）先化为平衡表　B11B12B2B31B32B4aiA144977M70A266533220A3884991050A4M0MM0M40bj302040204030180最优解如下表，最优值Z＝6405.4（1）建立数学模型设Rij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则(2)写平衡运价表将第一、二等式两边同除以40，加入松驰变量R13,R23和R33将不等式化为等式，则平衡表为：B1B2B3ai甲乙丙80605065504000051015bj10155为了平衡表简单，故表中运价没有乘以40，最优解不变（3）最优调度方案：即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为Z=40（5×80+5×60+5×50+10×40）=54000（元）5.5（1）设Rij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。12345ai12341MMM1.151.25MM1.31.40.87M1.451.551.020.98000065656565bj5040608030(3)用表上作业法，最优生产方案如下表：12345ai123450152560105653065656565Bi5040608030上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产