《运筹学》题库及答案

考试资料欢迎下载考试资料欢迎下载/考试资料欢迎下载运筹学习题库数学建模题（5）1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x1、x2，则x1、x2≥0，设z是产品售后的总利润，则maxz=70x1+120x2s.t.2、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量原材料（吨/件）工时（工时/件）零件（套/件）2252.513000吨4000工时500套产品利润（元/件）43建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x1、x2，设z为产品售后总利润，则maxz=4x1+3x2s.t.3、一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量100600300建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x3≥0，设z是产品售后的总利润，则maxz=10x1+6x2+4x3s.t.4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入0—1变量xi,xi=1表示应携带物品i，,xi=0表示不应携带物品I5、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：产产品资源ABC资源限量材料（kg）1.51.242500设备（台时）31.61.21400利润（元/件）101412根据市场需求，预测三种产品最低月需求量分别是150、260、120，最高需求量是250、310、130，试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产A、B、C数量为。6、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2小时，每单位产品B需要前道工序2小时和后道工序3小时。可供利用的前道工序有11小时，后道工序有17小时。每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售盈利，其余只能加以销毁。出售A、B、C的利润分别为3、7、2元，每单位产品C的销毁费用为1元。预测表明，产品C最多只能售出13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产A、B数量为销毁的产品C为。7、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500，在两个工厂之间有一条流量为200万的支流。第一化工厂每天排放有某种优化物质的工业污水2万，第二化工厂每天排放该污水1.4万。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净化。根据环保要求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万，第二化工厂的为800元/万。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。附图：¤工厂1¤工厂2500万200万解：设第一化工厂和第二化工厂的污水处理量分别为每天和x2万，st8、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分营养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为，则根据题意可得如下线性规划模型：9、某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铣钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别x1,x2,x3,x4单位则应满足的目标函数为：maxz=2x1+3x2+x3+x4满足的约束条件为：10、某航空公司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5，要求每天到D城有2个航次（往返），到A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划。客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d）大型A6000700080001000050007000100001800012510BCD中型A10002000400030004000600024820BCD小型A20003500600040005500800012619BCD解：设大型客机飞往A城的架次为x1A，中型客机飞往A城的架次为x2A，小型客机飞往A城的架次为x3A，其余依此类推。资源限制派出的大型客机架次不能超过10架，表示为同理班次约束飞往各城的班次要满足非负性约束且为整数；（i=1,2,3;j=A,B,C,D）目标函数为11、CRISP公司制造四种类型的小型飞机：AR1型（具有一个座位的飞机）、AR2型（具有两个座位的飞机）、AR4型（具有四个座位的飞机）以及AR6型（具有六个座位的飞机）。AR1和AR2一般由私人飞行员购买，而AR4和AR6一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（F.A.A）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了CRISP公司的有关飞机制造的重要信息。AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）建造飞机所需要的时间（天）每架飞机所需要的生产经理数目每架飞机的盈利贡献（千美元）84162177184119210315112125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按30天计算）。JonathanKuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设表示下个月生产AR1型飞机的数目，表示AR2型，表示AR4型，表示AR6型目标函数：约束条件：为整数12、永辉食品厂在第一车间用1单位原料N可加工3单位产品A及2单位产品B，产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加6元。原料N的单位购入价为2元，上述生产费用不包括工资在内。3个车间每月最多有20万工时，每工时工资0.5元，每加工1单位N需要1.5工时，若A继续加工，每单位需3工时，如B继续加工，每单位需2工时。原料N每月最多能得到10万单位。问如何安排生产，使工厂获利最大？解：设为产品A的售出量；为A在第二车间加工后的售出量；表示产品B的售出量；表示B在第三车间加工后的售出量；为第一车间所用原材料的数量，则目标函数为：约束条件：

化标准形式（5）1、将下列线性规划模型化为标准形式解：2、将下列线性规划模型化为标准形式解：3、将下列线性规划变为最大值标准形。解：

图解法（5）1、用图解法求解下面线性规划minz=－3x1+2x2解：可行解域为abcda，最优解为b点。由方程组解出x1=11，x2=0∴X*==（11，0）T∴minz=－3×11+2×0=－332、用图解法求解下面线性规划minz=2x1+x2解：从上图分析，可行解域为abcde，最优解为e点。由方程组解出x1=5，x2=3∴X*==（5，3）T∴minz=Z*=2×5+3=133、已知线性规划问题如下：MaxZ=用图解法求解，并写出解的情况解：x26Z’4x2=42 Z’ x1 0246810 5x1+10x2=50 x1+x2=1由图可知：解之得：则maxZ=2+3*4=144、用图解法求解下面线性规划问题解：

5、用图解法求解下面线性规划问题图解如下：可知，目标函数在B(4,2)处取得最大值，故原问题的最优解为，目标函数最大值为。二、单纯型法（15）1、用单纯型法求解下面线性规划问题的解maxz=3x1+3x2+4x3s.t.解：加入松弛变量x4，x5，得到等效的标准模型：maxz=3x1+3x2+4x3+0x4+0x5s.t.列表计算如下：

CBXBb33400θLx1x2x3x4x50x44034（5）1080x566643012200000334↑004x383/54/511/5040/30x542（21/5）8/50－3/511012/516/544/503/5↑－1/50－4/504x3204/712/7－1/73x11018/210－1/75/2138324/745/71/70－3/70－5/7－1/7∴X*=（10，0，2，0，0）T∴maxz=3×10+4×2=382、用单纯型法求解下面线性规划问题的解maxz=70x1+120x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.列表计算如下：CBXBb70120000θLx1x2x3x4x50x336094100900x420046010100/30x53003（10）001300000070120↑0000x324039/5010-2/5400/130x420（11/5）001-3/5100/11120x2303/101001/1010036120001234↑000－120x31860/11001－39/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/11－30/11∴X*=（，，，0，0）T∴maxz=70×+120×=3、用单纯型法求解下面线性规划问题的解maxz=4x1+3x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准形式：maxz=4x1+3x2+0x3+0x4+0x5s.t.用表解形式的单纯形法求解，列表计算如下：CBXBb43000θLx1x2x3x4x50x33000221003000/2=15000x4400052.50104000/5=8000x5500（1）0001500/1=500000004↑30000x320000210-22000/2=10000x415000（2.5）01-51500/2.5=6004x150010001——4000403↑00-40x3800001-0.8（2）800/2=4003x26000100.4-2——4x150010001500/1=5004301.2-2000-1.22↑0x5400000.5-0.413x21400011-0.404x110010-0.50.4046004310.4000-1-0.40据上表，X*=（100，1400，0，0，400）Tmaxz=4×100+3×1400=4604、用单纯型法求解下面线性规划问题的解maxz=10x1+6x2+4x3s.t.解：加入松弛变量x4，x5，x6，得到等效的标准模型：maxz=10x1+6x2+4x3+0x4+0x5+0x6s.t.列表计算如下：CBXBb1064000θLx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010↑640000x4400（3/5）1/21－1/100200/310x16012/51/201/1001500x618006/550－1/51150104501002↑－10－106x2200/3015/65/3－1/6010x1100/3101/6－2/31/600x6100004－20110620/310/32/3000－8/3－10/3－2/30∴X*=（，，0，0，0，100）T∴maxz=10×+6×=5、用单纯型法求解下面线性规划问题的解用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：=604-22000b060311100010[1]-120100402-220014-220004-22000b03004-51-304101-120100200[4]-60-2102-60-404-22000b0100011-1-1415101/201/21/4-2501-3/20-1/21/400-30-3-1/2所以X=（15，5，0，10，0，0）T为唯一最优解MaxZ=4*15-2*5=506、用单纯形法求解下述LP问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：2.510001535105010[5]20122.5100090[19/5]1－3/545/192.5212/501/55000－1/2145/19015/19－3/192.520/1910－2/195/19000－1/2由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。7、用单纯形法解线性规划问题解：化为标准型列出单纯形表Cj21000CBXBbx1x2x3x4x5000x3x4x5152450[6]152110001000145-Z021000020x3x1x5154101051/3[2/3]10001/6-1/60013123/2-Z-801/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2-Z-20000-1/4-1/2Z*=17/2,X*=(7/2,3/2,15/2,0,0)’8、用单纯型法求解下面线性规划问题的解解：Cj11000CBXBbx1x2x3x4x5000x3x4x5224[1]-2-112111000100012-Z011000100x1x4x5266100-2-3-1121010001-Z-203-100把表格还原为线性方程令x3=0此时，若让x2进基，则会和基变量x1同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解Cj24000CBXBbx1x2x3x4x5000x3x4x584311020[1]10001000143-Z024000004x3x4x2243[1]10001100010-20124-Z-122000-4204x1x4x22231000011-10010-221-Z-2000-200204x1x5x24121000010-1/21/211/2-1/2010-Z-2000-200Z*=20,X*=(2,3,0,2,0)’Z*=20,X*=(4,2,0,0,1)’10、用单纯型法求解下面线性规划问题的解解：列表如下Cj35000CBXBbx1x2x3x4x5000x3x4x5412181030[2]210001000169-Z035000050x3x2x546610[3]01010001/2-100143-Z-30300-5/20053x3x2x16220010101001/31/2-1/3-1/301/3-Z-20000-3/2-1X*=(2,6,6,0,0)’Z*=3611、用单纯型法求解下面线性规划问题的解解：化为标准型单纯型表如下：Cj21000CBXBbx1x2x3x4x5000x3x4x5152450[6]1521100010001–45Z021000020x3x1x5154101051/3[2/3]10001/6-1/60013123/2Z001/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2Z17/2000-1/4-1/2由些可得，问题的最优解为x1=7/2，x2=3/2，最优值maxz=17/212、用大M法求解如下线性规划模型：minz=5x1＋2x2＋4x3解：用大M法，先化为等效的标准模型：maxz/=－5x1－2x2－4x3s.t.增加人工变量x6、x7，得到：maxz/=－5x1－2x2－4x3－Mx6－Mx7s.t大M法单纯形表求解过程如下：CBXBb－5－2－400－M－MθLx1x2x3x4x5x6x7－Mx64（3）12－10104/3－Mx7106350－1015/3－9M－4M－7MMM－M－M9M－5↑4M－27M－4－M－M00－5x14/311/32/3－1/301/30——－Mx72011（2）－1－211－5-M－5/3-M－10/3-2M+5/3M2M－5/3-M0M－1/3M－2/32M－5/3↑－M－3M+5/30－5x15/311/25/60－1/601/610/30x410（1/2）1/21－1/2－11/22－5－5/2－25/605/60－5/601/2↑1/60－5/6－M－M+5/6－5－2x12/3101/3－11/31－1/3x220112－1－21－－5－2－11/311/3－1－1/300－1/3－1－1/3－M+1－M+1/3∴x*=（，2，0，0，0）T最优目标函数值minz=－maxz/=－（－）=13、用大M法求解如下线性规划模型：minz=540x1＋450x2＋720x3解：用大M法，先化为等效的标准模型：maxz/=－540x1－450x2－720x3s.t.增加人工变量x6、x7，得到：maxz/=－540x1－450x2－720x3－Mx6－Mx7s.t大M法单纯形表求解过程如下：CBXBb－540－450－72000－M－MθLx1x2x3x4x5x6x7－Mx670359－101070/3－Mx730（9）530－10130/9=10/3－12M－10M－12MMM－M－M12M－540↑10M－45012M－720－M－M00－Mx660010/3（8）－11/31－1/360/8=2.5－540x110/315/91/30－1/901/910/3/1/3=10-300+10/3M-8M－180－M－M/3+60－MM/3－600-150+10/3M8M-540↑MM/3－600－M/3+60－720x315/205/121－1/81/241/8－1/2415/2/5/12=18－540x15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450x320/3－1011/61/61/6－1/6x2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴该对偶问题的最优解是x*=（0，2，，0，0）T最优目标函数值minz=－（－5700）=570014、用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表Cj－30100－M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x74191-201[1]31-111000-10010001-Z10M-2M-34M10-M0000-Mx4x2x73163-2[6]0102-141001-13-11-3001-Z6M6M-304M+103M-4M000-3x4x2x103100101001/3[2/3]100-1/201/2-1/20-1/21/21/31/6-Z300303/2-M-3/2-M+1/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/41/21/4-3/4-1/21/41/4-Z-3/2-9/2000-3/4-M+3/4-M-1/4人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0)’Z*=3/215、用单纯形法求解线性规划问题解化为标准形式有列表计算Cj－3－200MCBXBbx1x2x3x4x50Mx3x521223[1]4100-10123-Z-12M3M+34M+20-M0-2Mx2x5242-5101-40-101-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4)’Z*=4M-4说明原问题无解写对偶问题（10）写出下列线性绘画问题的对偶问题 解： 2、写出下述线性规划的对偶问题解3、写出下列线性规划的对偶问题解：4、写出下列线性规划的对偶问题解

对偶性质1、已知线性规划问题如下：MaxZ=已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为： 将X=（2，4）T代入原问题可知：〉1为严格不等式，所以由对偶问题性质可知：解之得：所以Y=（1/5，0，1）TMinZ=142、已知线性规划问题 用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。答案：(对偶问题的最优解为；(依据z*=w*及互补松弛性，有x4=0,且 解得愿问题最优解X*=(7/5,0,1/5,0)。3、已知线性规划问题已知其对偶问题的最优解为，最优值为。试用对偶理论找出原问题的最优解。解先写出它的对偶问题s.t.① ②③④⑤将的值代入约束条件，得②，③，④为严格不等式；设原问题的最优解为，由互补松弛性得。因；原问题的两个约束条件应取等式，故有求解后得到；故原问题的最优解为；最优值为。4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。解：第一步，写出对偶问题第二步，将LP，DP都化为标准型第三步：将最优解代入标准型中，确定松弛变量取值第四步：利用互补松弛定理∴Y3*=0∴Y1S=0Y2S=0第五步：将Y3*=0Y1S=0Y2S=0代入约束条件则有∴对偶问题的最优解为Y*=(4/7,5/7,0)’5、已知线性规划问题：，试用对偶理论证明上述线性规划问题无最优解。证明：首先看到该问题存在可行解，例如，而上述问题的对偶问题为：由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。5、已知线性规划问题（1）写出其对偶问题；（2）用图解法求对偶问题的解；（3）利用（2）的结果及对偶性质求原问题解。解：（1）原线性规划问题可化为：其对偶问题为：（2）用图解法解得（3）由互补松弛性定理知道，又由解之，可得原问题最优解

对偶单纯形法（15）1、用对偶单纯形法解下列线性规划问题解：先化为标准型约束条件两边同乘(-1)列单纯形表Cj－15－24－500CBXBbx1x2x3x4x500x4x5－2－10－5[-6]-2-1-11001-15-24-50045-240x2x51/3-1/30-5101/6[-2/3]-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2)’Y*=(7/2,3/2)2、用对偶单纯形法解下列线性规划问题解：改写为标准形式列单纯形表如下：Cj－4－12－1800CBXBbx1x2x3x4x500x4x5－3－5－100[-2]-3-21001-4-12-1800690-12x4x2-35/2-1001[-3]1100-1/2-40-60-6421218-12x3x213/21/3-1/30110-1/31/30-1/2-200-2-6X*=(0,3/2,1)’Y*=(2,6)3、用对偶单纯形法求解下面的问题：解：令，则问题可以标准化为：取为初始基，则是非基可行解，但，是对偶可行解，建立单纯形表（见表4-1）计算结果如下：最优解。或最优解。本例如果用单纯形法计算，确定初始基可行解时，还需要引入两个人工变量，计算量要多于对欧单纯形法。表3-1：C备注-4-4L=2K=4-1-1L=1K=2-1/2-1/2L=2K=1或3灵敏度分析1、已知线性规划的标准形式为其最优单纯形表如下Cj－12100CBXBbx1x2x3x4x520x2x56101310111101-Z-12-30-1-20问：(1)当C1由－1变为4时，求新问题的最优解(2)讨论C2在什么范围内变化时，原有的最优解仍是最优解解：由表可知，C1是非基变量的价值系数，因此C1的改变只影响σ1可见最优性准则已不满足，继续迭代Cj42100CBXBbx1x2x3x4x520x2x56101[3]10111101610/3-Z-1220-1-2024x2x18/310/301102/31/32/31/3-1/31/3-Z-56/300-5/3-8/3-2/3(2)要使原最优解仍为最优解，只要在新的条件下满足σ≤0成立，因为x2是基变量，所以所有的σ值都将发生变化σ＝C-CBB-1A即则c2’≥1c2+△c2≥1△c2≥-1所以当x2的系数△c2≥-1时，原最优解仍能保持为最优解。2．已知线性规划问题及其最优单纯形表Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2若右端列向量，求新问题的最优解。解：因为－1小于0，因此继续迭代Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x3－152100-1/322/30011/301/3010[-2/3]11/3-Z-90-40-10-2σj/arj123004x6x5x33/27/23/2-3/23/21/21/23/21/2001-1/21/21/2010100-Z-6-3-30-200∴新问题的最优解为X*=(0,0,3/2,0,7/2,3/2)’Z*=63、已知线性规划问题及其最优单纯形表最优单纯形表如下：Cj23100CBXBbx1x2x3x4x523x1x2121001－124－1－11610/3-Z-800-3-5－1若p3由原来的，最优解将如何改变？解：计算∴继续迭代Cj23100CBXBbx1x2x3x4x523x1x21210011/15[7/30]4－1－111560/7-Z-8001/6-5－121x1x33/760/710-2/7-30/70130/7-30/7－9/7-30/71560/7-Z-66/70-5/70-30/7－12/7X*=(3/7,0,60/7,0,0)Z*=66/7(仍以例2为例)已知线性规划问题及其最优单纯形表Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2现增加一个新变量x7，且c7=3，p7=(3,1,-3)’，求新问题的最优解。解：由表知：∴∴继续迭代Cj－1－140003CBXBbx1x2x3x4x5x6x7－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3[3]-20-Z-170-40-10-26304x7x5x31/956/913/31/32/30-1/916/92/30011/92/91/3010-2/95/91/3100-Z-53/3-2-10/30-5/30-2/30∴X*=(0,0,13/3,0,56/9,0,1/9)’Z*=53/35．已知线性规划问题及其最优单纯形表Cj－1－14000CBXBbx1x2x3x4x5x6－104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2现增加新约束，求新问题的最优解。解：将原问题的最优解代入新增约束不满足新增加的约束条件，因此引入松弛变量x7后，新增约束变为，加进最优表得：Cj－1－140000CBXBbx1x2x3x4x5x6x7－1040x1x5x3x71/3613/317100-3-1/322/3100161/301/300100-2/311/30[3]-201-Z-170-40-10-20－1040x1x5x3x71/3613/3-81000-1/322/3-400161/301/3-10100-2/311/3[-4]0001-Z-170-40-10-20111/2－1040x1x5x3x65/3411/3210001/311/3100101/2-1/41/41/401000001-1/61/41/12-1/4-Z-130-20-1/200-1/2∴X*=(5/3,0,11/3,0,4,2,0)’Z*=135、线性规划问题用单纯形法求解得最终单纯形表如下表所示。x1x2x3x4x5x1611110X51003111cj-zj0-3-1-20试说明分别发生如下变化时，新的最优解是什么？（1）目标函数变为；（2）约束条件右端项由变为；（3）增添一个新的约束。解：（1）cj→23100θiCBxBbx1x2x3x4x52x161111020x5100[3]1110cj-zj01-1-202x18/3102/32/3-1/323X210/3011/31/31/30cj-zj00-4/3-7/3-1/3因为所有的检验数均小于等于零。故最优解为（2）因为。所以cj→2-1100θiCBxBbx1x2x3x4x52x13111100x5703111cj-zj0-3-1-20因为所有的检验数均小于等于零，故最优解为（3）由于，所以原问题的最优解不是该问题的最优解。在约束条件左右两端同时乘以“-1”，并加上松弛变量，得到cj→2-11000θiCBxBbx1x2x3x4x5x62x161111000x5100311100x6-210-2001cj-zj0-3-1-2002x161111000x5100311100x6-80-1[-3]-101cj-zj0-3-1-2002x110/312/302/301/30x522/308/302/311/31x38/301/311/30-1/3cj-zj0-8/30-5/30-1/3因为所有的检验数均小于等于零，故最优解为

第三章运输问题（15）1、安排一个使总运费最低的运输计划，并求出最低运费。运 销地价运价产产地产A1A2A3A4产量161110950210761470312881130需求量30405030要求：先用最小元素法求出一个初始方案，再用闭回路法，求检验数。如果不是最优，改进为最优。解：1）先用最小费用法（最小元素法）求此问题的初始基本可行解：地产地用费销地产地用费销A1A2A3A4Si16111095030××20210761470×2050×312881130×20×10dj30405030150150∴初始方案：Z=6×30+9×20+7×20+6×50+8×20+11×10=10702）用闭回路法，求检验数：地产用费地销地产用费地销A1A2A3A4Si1611－510－595030××20210－37614－470×2050×312－488－11130×20×10dj30405030150150从上表可看出，所有检验数≤0，已得最优解。∴该指派问题的最优方案就是上面用“最小费用法”求得的初始方案求出最小费用Z=6×30+9×20+7×20+6×50+8×20+11×10=10702、给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1B2B3B4siA1A2A312348765910119108015dj82212181）用最小费用法求初始运输方案，并写出相应的总运费；（5分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：地产用费地销地产用费地销B1B2B3B4SiA112341082××A2876520××218A391011930×2010×dj8221218606082B82B1B2A1218218B3B4A22010B2B3A3Z=1×8+2×2+6×2+5×18+10×20+11×10=4242）①用闭回路法，求检验数：地产用费地销地产用费地销B1B2B3B4SiA112304－21082××A28－47－26520××218A39010119130×2010×dj82212186060∵=1＞0，其余≤0∴选作为入基变量迭代调整。②用表上闭回路法进行迭代调整：地产用费地销地产用费地销B1B2B3B4SiA1123－14－31082××A28－37－16520××128A3901011－1930×20×10dj82212186060调整后，从上表可看出，所有检验数≤0，已得最优解。∴最优方案为：882B1B2A1128128B3B4A22010B2B4A3最小运费Z=1×8+2×2+6×12+5×8+10×20+9×10=4143、下列是将产品从三个产地运往四个销地的运输费用表。运 销运价地价产产产地A1A2A3A4产量19129650273776036591150需求量40406020要求：⑴用最小费用法建立运输计划的初始方案；⑵用位势法做最优解检验；⑶求最优解和最优方案的运费。解：⑴先用最小费用法（最小元素法）求此问题的初始基本可行解：地产用费地销地产用费地销A1A2A3A4Si19129650××30202737760×4020×3659115040×10×dj4040602016016030203020A3A41404010A1A334020A2A32初始方案总运费Z=9×30+6×20+3×40+7×20+6×40+9×10=980⑵按题目要求用位势法，作最优解检验：地产用费地销地产用费地销A1A2A3A4ui190120960××3020277377－2－9×4020×36509110－740×10×Vj9121618所有检验数如下：＝＝9－0－9＝0，＝＝12－0－12＝0，＝＝7－（－9）－9＝7，＝＝7－（－9）－18＝－2，＝＝5－（－7）－12＝0，＝＝11－（－7）－18＝0。⑶再用闭回路法求最优解和最优方案的运费，先检验：地产用费地销地产用费地销A1A2A3A4Si19－312－79650××302027－3377－360×4020×3650911－55040×10×Dj40406020160160∵所有检验数≤0，∴该方案已是最优方案，不需要再调整。30203020A3A414010A1A334020A2A32最优方案的运费Z=9×30+6×20+3×40+7×20+6×40+9×10=9804、给定下列运输问题：（表中数据为产地Ai到销地Bj的单位运费）B1B2B3B4siA1A2A32011

86

59

10

2

187

4

15

1015dj

33

12121）用最小费用法求初始运输方案，并写出相应的总运费；（4分）2）用1）得到的基本可行解，继续迭代求该问题的最优解。（10分）解：用“表上作业法”求解。1）先用最小费用法（最小元素法）求此问题的初始基本可行解：地产用费地销地产用费地销B1B2B3B4SiA1201186532××A25910210×××10A31874115×1122Dj331212303032B32B1B2A11212B1212B2B4A3B310A2B4Z=20×3+11×2+2×10+7×1+4×12+1×2=1592）①用闭回路法，求检验数：地产用费地销地产用费地销B1B2B3B4SiA12011806－1532××A25129－110－5210×××10A318－274115×1122Dj3312123030∵=12＞0，其余≤0∴选作为入基变量迭代调整。②用表上闭回路法进行迭代调整：地产用费地销地产用费地销B1B2B3B4SiA12011812611523××A259－1310－152101××9A318－147－124115××123Dj3312123030再选作为入基变量迭代调整。地产用费地销地产用费地销B1B2B3B4SiA120－121186－15×32×A259－110－52103××7A318－14704115××105Dj3312123030调整后，从上表可看出，所有检验数≤0，已得最优解。∴最优方案为：32B32B2B3A137B1B4A2105B3B4A3最小运费Z=11×3+8×2+5×3+2×7+4×10+1×5=1235、某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为A——1500套，B——2000套，C——3000套，D——3500套，有三个城市可供应上述规格服装，供应数量为Ⅰ——2500套，Ⅱ——2500套，Ⅲ——5000套。由于这些城市的服装质量、运价情况不一，运输成本（元/套）也不一样，详见下表：ABCDⅠ10567Ⅱ8276Ⅲ9348请帮助该公司确定一个成本最小的采购方案。(用伏格尔法)（12分）解：用伏格尔法确定初始调运方案为：ABCD供Ⅰ25002500Ⅱ20005002500Ⅲ150030005005000销150020003000350011=2；12=-2；13=3；21=1；23=5；32=-1（5分）有ij0,所以需要调整为：ABCD供Ⅰ25002500Ⅱ150010002500Ⅲ150050030005000销150020003000350011=1；12=2；13=2；21=0；23=4；34=1（5分）因为ij0，所以为最优方案。MinZ=2500*7+1500*2+1000*6+1500*9+500*3+3000*4=53500（2分）由于21=0所以在此闭回路上有无穷多最优解。6已知某运输问题如下（单位：百元/吨）：（12分）单位运价销地产地B1B2B3供应量（吨）A137218A2581012A394515需求量（吨）161217求：（1）、使总运费最小的调运方案和最小运费。(用伏格尔法)（10分）（2）、该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再求出一个最优调运方案来。（2分）解：1）用伏格尔法确定初始调运方案为：B1B2B3供A111718A21212A331215需16121712=9；22=0；23=6；33=-3（4分）有ij0,所以需要调整为：B1B2B3供A141418A21212A312315需16121712=6；22=5；23=6；31=3（4分）因为ij0，所以为最优方案。MinZ=3*4+2*14+12*5+12*4+3*5=163为唯一最优解。（2分）7已知运输问题的产销平衡表与单位运价表如下表所示。销地甲乙丙丁产量A327650B752360C254525销量60402015试用表上作业法求出最优解。解：本问题是产销平衡问题。根据最小元素法，初始可行解为：甲乙丙丁产量A104050B25201560C2525销量60402015135采用位势法，可得检验数如下表所示（为了区别，检验数用“括号里的数字”表示）甲乙丙丁产量UiA10（0）40（0）（9）（7）500B25(0)（-1）20(0)15(0)604C25(0)（4）（7）（7）25-1销量60402015135Vj32-2-1因为（B，乙）的检验数为-1，所以该初始可行解非最优解。从空格（B，乙）出发的闭回路为（B，乙）——（B，甲）——（A，甲）——（A，乙）——（B，乙）。该闭回路的偶数顶点位于格（B，甲）和（A，乙），由于所以可得如下可行解甲乙丙丁产量UiA35（0）15（0）（8）（6）500B(1)25（0）20(0)15(0)603C25(0)（4）（6）（6）25-1销量60402015135Vj32-10由于所有空格的检验数均大于零。所以得到唯一最优解。

匈牙利法（15）1、求解指派问题，并求出最小费用。Minz=（cij）4×4=解：用“匈牙利法”求解。效率矩阵表示为：行约简标号列约简行约简标号列约简至此已得最优解：∴最小费用W=8+17+16+19=602、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D四项不同的工作，每人做各项工作所消耗的时间如下表所示：ABCD甲21097乙154148丙13141611丁415139问：应该如何指派，才能使总的消耗时间为最少？解：用“匈牙利法”求解。效率矩阵表示为：行约简标号列约简行约简标号列约简√√√√至此已得最优解：∴使总消耗时间为最少的分配任务方案为：甲→C，乙→B，丙→D，丁→A。此时总消耗时间W=9+4+11+4=283、一个公司经理要分派4个推销员去4个地区推销某种商品。4个推销员各有不同的经验和能力，因而他们在每一地区能获得的利润不同，其估计值如下表所示：D1D2D3D4甲35272837乙28342940丙35243233丁24322528问：公司经理应怎样分派4个推销员才使总利润最大？解：用求极大值的“匈牙利法”求解。效率矩阵表示为：行约简M－C行约简M－CijM=40标号列约简所画（）0元素少于n（n＝4），未得到最优解，需要继续变换矩阵（求能覆盖所有0元素的最少数直线集合）：标号列约简√√√√√√标号未被直线覆盖的最小元素为cij=2,在未被直线覆盖处减去2，在直线交叉处加上2。标号∴得最优解：∴使总利润为最大的分配任务方案为：甲→D1，乙→D4，丙→D3，丁→D2。此时总利润W=35+40+32+32=1394、求解系数矩阵的指派问题解：先作等价变换如下现在已可看出，最优指派为5、用匈牙利法求解下列的指派问题，已知效率矩阵如下：。√√√解：→√√√由于得到了5个独立零元素，故可得最优指派方案。本题的最优解为：。这样可使目标函数最小，为3+2+4+3+9=21。6、某5×5指派问题效率矩阵如下，求解该指派问题。解：对C进行行、列变换，减去各行各列最小元素用圈0法对C1进行行列检验，得到对C2中所有不含圈0元素的行打√，如第5行对打√的行中，所有0元素所在列打√，如第1列对所有打√列中圈0元素所在行打√，如第3行重复上述(2),(3)步，直到不能进一步打√为止对未打√的每一行划一直线，如1，2，4行，对已打√的列划一纵线，如第1列，即得到覆盖当前0元素的最少直线数。见C3第5步：对矩阵C3作进一步变换，增加0元素在未被直线覆盖过的元素中找出最小元素，将打√行的各元素减去这个最小元素，将打√列的各元素加上这个最小元素(以避免打√行中出现负元素)，这样就增加了0元素的个数。对C3进行变换，最小元素为2，对打√的第3，5行各元素都减去2，对打√的第1列各元素都加上2，得到矩阵C4令决策变量矩阵中x12=x24=x35=x43=x51=1,其余xij=0

隐枚举法1、用隐枚举法求解规模0－1规划问题解：由于本题过滤条件不好选，所以开始不设过滤条件点过滤条件约束Z值(x2,x1,x4,x3)(4)(1)(2)(3)(0,0,0,0)×(0,0,0,1)√×(0,0,1,0)×(0,0,1,1)×(0,1,0,0)√×(0,1,0,1)√×(0,1,1,0)√×(0,1,1,1)√√√3(1,0,0,0)×(1,0,0,1)×(1,0,1,0)×(1,0,1,1)×(1,1,0,0)×(1,1,0,1)×(1,1,1,0)×(1,1,1,1)×此例的最优解X*=(0,1,1,1)’minz=3

割平面法1、用割平面法解整数规划问题将原整数规划问题称为原问题A0，不考虑整数条件的伴随规划称为问题B0，用单纯形法求解B0，得最优单纯形表Cj1100CBXBx1x2x3x411x2x17/43/401103/4-1/41/41/4-Z-5/200-1/2-1/2问：原问题的解是多少？解：x1=3/4,x2=7/4均不满足整数条件，选x1，则含x1的约束方程为：将所选的约束方程中非基变量的系数及常数项进行拆分处理。7/4=1+3/4-5/2=-3+1/21/4=0+1/4求割平面方程将割平面方程加到伴随规划的最终单纯形表中，用对偶单纯形法继续求解Cj11000CBXBx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4[-3/4]1/41/4-1/4001-Z-5/200-1/2-1/202/32110x2x1x311101010000101/31/31-1/3-4/3-Z-2000-1/3-2/3X*=(1,1)’Z*=22、

图和网络分析1、求下图中从v1到v3短路。解：令P(v1)=0，k=v1；T(vj)=+∞。当k=v1时，T(v2)=P(v1)+1=1,λ(v2)=v1;T(v4=P(v1)+2=2,λ(v4=v1;所有T标号中T(v2)最小，故P(v2)=T(v2)=1，k=v2。当k=v2时，T(v3)=P(v2)+7=8,λ(v3)=v2;T(v6)=P(v2)+3=4,λ(v6)=v2;T(v4)<P(v2)+3，故v4的T标号不变;所有T标号中T(v4)最小，故P(v4)=T(v4)=2，k=v4。当k=v4时，T(v6)==P(v3)+2，可不变;T(v5)=P(v3)+2=4,λ(v5)=v4;所有T标号中T(v6)最小，故P(v6)=T(v6)=4，k=v6。当k=v6时，T(v3)=P(v6)+3=7,λ(v3)=v6所有T标号中T(v5)最小，故P(v5)=T(v5)=4，k=v5。当k=v5时，T(v3)<P(v5)+6，故v3的T标号不变;所有T标号中T(v3)最小，故P(v3)=T(v3)=7。所有的点都具有P标号，算法结束。从v1至v3的最短路为：v1→v2→v6→v3。2、电信公司要在15个城市之间铺设光缆，这些城市的位置及相互之间的铺设光缆的费用如下图所示。试求出一个连接在15个城市的铺设方案，使得总费用最小。解：费用最小的铺设方案对应于光缆图的最小支撑树。求得最小支撑树为：最小费用为28。3、求出从vs到vt的最大流，弧旁的数字是弧的容量。解：以零流作为初始流，计算增广链并调整流量，过程如下：可知，最大流量为5，最小截集为，其中，。

决策分析1、设三个备选投资方案的决策益损如下表：销售状态收益值(万元)可行方案销路好销路一般销路差销路极差A5025–25–45B7030–40–80C3015–5–10问题：(1)试用最大最大决策标准选择方案；(2)当α取何值时，用现实主义决策标准和用最大最大决策标准选择的方案相同?解：2、已知某企业有下表所示的情况，请选择所用策略。表中效益值的单位为万元。效益自然状态Sj及值aij概率P(Sj)策略diS1（产品销路好）P(S1)=0.3S2（产品销路一般）P(S2)=0.5S3（产品销路差）P(S3)=0.2d1（按甲方案生产）402615d2（按乙方案生产）353020d3（按丙方案生产）302420请用决策树来进行决策。解：来说明单级决策树的画法和最优期望益损值准则的决策方法。步骤如下：销路好P(S1)=0.3△40d1=28销路一般P(S2)=0.5△26销路差P(S3)=0.2△1529.5\\d2=29.5销路好P(S1)=0.3△35决选乙方案销路一般P(S2)=0.5△30策销路差P(S3)=0.2△20\\d3=25销路好P(S1)=0.3△30销路一般P(S2)=0.5△24销路差P(S3)=0.2△203、公司有50000元多余资金，如用于某项投资，估计成功率为96%，成功时可获利12%，若失败，将丧失全部资金。如果把资金存入银行，则可稳得利息6%。为获取更多情报，该公司可求助于咨询服务，咨询费用为500元，但咨询意见只能提供参考。该咨询公司过去类似的200例咨询意见实施结果如下表所示。实施结果咨询意见投资成功投资失败合计可以投资154次2次156次不宜投资2次6次44次合计192次8次200次问：该公司是否值得求助于咨询服务？应如何安排多余资金？解：根据以上分析，可以完成决策树的全部内容。见下图：P（E1）=0.9637606000投资P（E2）=0.043760-50000不咨询存银行30004272P（E1∣T1）=0.9875272P（E2∣T1）=0.0136000咨询5272投资-500004772T1存银行3000