大连理工大学运筹学习题与答案

1、精品文档线性规划习题一1. 1试述LP模型的要素、组成部分及特征。判断下述模型是否LP模型并简述理由。（式中x,y为变量；B为参数；a,b,c,d,e 为常数。）（1）max z=2x 1-x 2-3x 3-X3 + +X13X1X2 5x3 - 8S.t.2xi - 4x2 +3x3 工5X0,X2 0, j =1,2,.n1.2试建立下列问题的数学模型：（1）设备配购问题某农场要购买一批拖拉机以完成每年三季的工作量：春种 择的拖拉机型号、单台投资额及工作能力如下表所示。330公顷，夏管130公顷，秋收470公顷。可供选拖拉机型号单台投资（元）单台工作能力（公顷）春种夏管秋收东方红50003

2、01741丰收4500291443跃进4400321642胜利5200311844问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小?（2）物资调运问题甲乙两煤矿供给a B, C三个城市的用煤。各矿产量和各市需求如下表所示:煤矿日产量（吨）城市日需求量（吨）甲乙200250ABC100150200各矿与各市之间的运输价格如下表示:城煤矿运价（元/吨）ABC甲9070100乙806580问应如何调运，才能既满足城市用煤需求，又使运输的总费用最少?（3 ）食谱问题某疗养院营养师要为某类病人拟订本周菜单。可供选择的蔬菜及其费用和所含营养成分的数量，以及这类病 人每周所需各种养分的最低数量

3、如下表所示：养分蔬菜每份所含养分数量（毫克）每份的费用（元）铁磷维生素A维生素C烟酸青豆0.451041580.30.15胡萝卜0.4528906530.350.15花菜1.05502550530.60.24卷心菜0.42575270.150.06甜菜0.5221550.250.18土豆0.57523580.80.10每周养分 最低需求量6.0325175002455.0另外为了 口味的需求，规定一周内所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人每周需14份蔬菜，问选用每种蔬菜各多少份？（4 ）下料问题某钢筋车间要用一批长度为10米的钢筋下料制作长度为三米的钢筋90根和长度为四米的钢筋

4、60根，问怎样下料最省？用图解法求解下列LP问题：（1）min z=6x 1+4x22xx2 -1s.t.3x1 4x2 -1.5x（ _ 0, x2 _ 0（2）max z=2.5x1+X23x1 5x2 空 15s.t.5x1 2x2 -10% _0,x2 -0(3) max z=2x 1+2x2f X| - X2 -1s.t. ；0.5捲 x2 辽 2Xi 亠 0, X2 丄 0(4) max z=x 1+X2X1 - x2 亠0s.t.丿3捲x2 兰-30 30, x2 启 0(5) min z=2x i-10x 2X| - X2 亠 0s.t. . X| - 5x2 -5X| 丄 0

5、, X2 丄 0(6) min z=-10x i-11x 23x14x2 _10+2x2 兰8x1 -2x2 _2为=0,x2亠01.4把1.3题的(3) - (6)化成标准形1.5把下列LP问题化成标准形。(1) min z=2x 1+3X2+5X3x _ X2 X3 2 5-6x1 +7x2 9x3 =15(2) min z=3x 1+4X2+2X3+X4一捲 一 x2 + x3 + & = -4凶1,x2兰01.6证明下述LP问题的可行域是一个空集:min z=x 1-2X2+2X3+X4s.t.x1x2 _x3 _x4 = 6X1,X2,X3,X4 一01.7已知LP问题如下：min

6、w=x 1+2x2-3x 3+4x45x2 +x3 +3x4 =5s.t. 丿论 +4x2 +x3 + x4 =7Xi,X2, X3M4 3 0判断下述各点：X=(8,2,7,-4)t,X2=(1,0,2,1)t,X3=(2,0,5,0) T 人=(0,0,-1,2)T,Xi=(3,1,0,0) T,Xi=(2,1/2,1,1/2)是不是该LP问题的可行解、基本解、基本可行解？试从中找出一个较优解。1.8设某线性规划问题的可行域如下:2为 + x2 -x3=25x, +3x2- x4=304Xi + 7x? X3 2x4 X5 = 85Xi,X2,X3,x4,X5 X0试判断下述各点：Xi=(

7、5,15,0,20,0)t,X2=(9,7,0,0,8)t,X 3=(15,5,10,0,0)是否为该可行域的极点并说明理由1.9设一标准形LP问题的系数阵为X0=(1,2,1) T是一可行解。试按性质 4证明中的方法，构造出另一个可行解。1.10试证明：若LP问题有两个不同的最优基本解，则必有无穷多个最优解。1.11设R,R2 U En为凸集，则(1) R 1+Rb=Z|Z=X+Y,X R ,Y R(2) R 1-R2=Z|Z=X-Y,X R ,Y R(3) 入 R=Z|Z=入 X, X R1,入 E1均为凸集。行2设R二En为凸集,i=1,2,则R=Rji也为凸集。1.13试举岀下述某一类

8、型的LP问题的实例：产品配比问题，配料问题，物资调运问题，食谱问题，下料问题及其它LP问题，然后建模并化标准形，再设法找岀一个基本可行解。1.14用枚举法求解下述 LP问题：(1) min w= x-i 4x2 X32x1 - 2x2 X3 =4s.t.X1一 x3 = 1占 0, x2 0, x3 色0(2) min w= x2x2 3x3I2xx2 3x3 = 2s.t. 2捲 +3x2 +4x3 =10X）KO, x2 兰0, x3 KO（3）1.3 题之（2）（4）1.3 题之（6）1.15某农户年初承包了 40亩土地，并备有生产专用资金 2500元。该户劳动力情况为：春夏季 4000

9、工时，秋冬季 3500工时。若有闲余工时则将为别的农户帮工，其收入为：春夏季0.5.元/工时，0.40元/工时。该户承包的地块只适宜种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养奶牛和鸡。每年每头奶牛需投资400元，每只鸡需投资3元。每头奶牛需用地1.5亩种植饲草，并占用劳动力：春夏季 0.3工时 和秋冬季0.6工时，每年净收入10元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作物一年需要的劳动力及收入情况如下表所示。问该农户应如何拟订经营方案才能使当年净收入最大？试建立该问题 的数学模型。大豆玉米小麦春夏季需工时/亩203510秋冬

10、季需工时/亩507540净收入（元/亩）5080401.16某罐头食品长用 A,B两个等级的西红柿加工成整番茄、番茄汁、番茄酱三种罐头。A,B原料质量评分分别为90, 50分。为保证产品质量，该厂规定三种罐头的品格（所用原料的质量平均分）如下表所示：罐头品名整番茄番茄汁番茄酱品格（分） 80 6050该厂现以0.5公斤6分的价格购进1500吨西红柿，其中可挑出 A等西红柿20%其余为B等。据市场预测，三 种罐头的最大需求量为：整番茄800万罐，番茄汁50万罐，番茄酱80万罐。原料耗量为：整番茄 0.75公斤/罐，番茄汁1.0公斤/罐，番茄酱1.25公斤/罐。三种罐头的价格及生产费用（其中不包括

11、西红柿原料费）如下 表所示。问该厂应如何拟订西红柿罐头的生产计划才能获利最大？试建立数学模型。（元/罐）整番茄番茄汁番茄酱价格0.860.900.76加工费0.2360.2640.108其它费用0.3510.3840.3171.17某厂生产甲、乙两种产品，每种产品都要在A,B两道工序加工。其中 B工序可由或B2完成，但乙产品不能用B加工。生产这两种产品都需要C,D,E三种原材料，有关数据如下表所示。又据市场预测，甲产品每天销售不超过30件。问应如何安排生产才能获利最大？试建立数学模型。产品单耗日供应量单位成本甲乙数量单位数量单位工A2180工时6元/工时B1360工时2元/工时序B21470工

12、时5元/工时原C312300米2元/米材D53100件1元/件料E41.5150公斤4元/公斤其他费用（元/件）2629单价（元/件）801001.18制造某机床需要 A,B,C三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机床，问最少要用多少根圆钢？试建立数学模型。轴件规格：长度（米）每台机床所需轴件数量A2.91B2.11C1.211.19某木材公司经营的木材储存在仓库中，最大贮存量为20万米3。由于木材价格随季节变化，该公司于每季初购进木材，一部分当季售出，一部分贮存以后出售。贮存费为a+bu,其中a=7元/米3，b=10元/米3 /季，u为贮存的

13、季度数。由于木材久贮易损，因此当年所有库存木材应于秋末售完。各季度木材单价及销量如下表所 示。为获全年最大利润，该公司各季应分别购销多少木材？试建立数学模型。季3购时价（元/米）3售出价（元/米）3最大销售量（万米）冬31032110春32533314夏34835220秋34034416单纯型法习题二2.1分别用图解法和单纯形法求解下述LP问题，并指出单纯形法迭代中每一基本可行解跟图解法可行域中哪一极点相互对应。（1）max z=10x 1+5x23x1 4x2 込9s.t.5x1 2x18x -0, x2 丄 0(2) max z=2x 汁X25x2 0, j =1,2,.,62.4用单纯形

14、法求解下述 LP问题:(1) max z=2x 1+2x2f X - X? _,1s.t.-0.5人+乂2 兰 2x, K 0, x2 兰 0 max z=10x 1+5x2-X1 X2 _ 1s.t. 捲-x2 _2x1 0, x2 亠 0(3) max z= 5x 1+3X2+2X3+4X45x x2 x3 8x4 =10 忌 +4x2 +3x3 +2x4 =10心2, X3N 30(4) min w= 2x 1+3X2+X3x14 x2 2x3 - 8s.t.3x1 2x2-6X1,X2,X3 0(5) min w=2 x 1+X2-X 3-x 42x1 x23x3 % = 6x1 x2

15、x3 x4 = 7X1,X2,X3,X4 启0(6) max z=10 x 1+15x2+12x35为 3x2x3 三 9-5为 +6x2 +15x3 乞 152% + x2 + x3 A 5公2，%兰0（7）min z= 3x i-4x 2+X3-2X 42x1 + x2 +2x3 + x4 =10x3 +2X4 兰10s.t.x x2& , ： 55 _ 2% 3x2 x3 & 一 20Xi,X2,X3 _ 02.5以2.1题之（1）为例，具体说明当目标函数中变量的系数怎样改变时，能够：（1）分别使每个极点成为最优点；（2）使该LP问题有多重最优解。2.6分别举出符合下述情况的LP问题之例

16、：（1）多重最优解；（2）最优解为退化的基本可行解；（3）最优解无界;（8）无可行解。2.7求解1.18题。2.8在一块地上种植某种农作物，据以往经验，在其生长过程中至少需要氮32公斤，磷恰以24公斤为宜，钾不得超过42公斤。现有四种肥料，其单价及氮磷钾含量（%如右表所示。问在该地块上施用这四种肥料各多少公斤，才能满足该农作物对氮磷钾的需要，又使施肥的总成本最低？成分含量成肥（%料甲乙丙丁氮330015磷502010钾14007单价（元/公斤）0.040.150.100.132.9试用矩阵形式的单纯形法解答下列问题：（1）已知用单纯形法求解某 LP问题所得到的初始单纯形表及最末单纯形表如下，试

17、将表中空白处填上适当字符。C325000基解XX2XX4X 5 X 6431211004630201042140001检验行1/20-2-1/4 01/2 01 1检验行已知用单纯形法求解某 LP问题，中间某两次迭代的单纯形表如下，试将表中空白处填上适当字符。C354000基解XX2XX4X 5 X 621 1 0 1 0 02-1 0 1 -1 1 010104001检验行X24/5-1/51/51/5-4/51/5检验行2.10试用改进单纯形法求解下述 LP问题：(1) max z=10 x 1+15x2+12x32为 + x2 + x3 兰 3x, +2x2 +3% 兰 52% 2x2x

18、3 乞 6X1,X2,X3 -0(2) max w=10 x 1+7X2+4X3+3X4+X52% +6x2 + x3 72为 +3x2 +4x3 +% +x5 兰8% +2x2 +3x3+為兰 5xj 0, j =1,2,3,4,5对偶原理习题三3.1试建立下述LP问题的对偶关系表，并写岀其对偶问题：(1) max z=4x 1+3X2+6X32x1 2x2 x3 三 6M _0,x2 _0,x3 _0(2) min w=60x 1+10x2+20x33% +x2 +x3 色2t N X2 +X3 色1M +2x2 x3 色1H 0,x2 0,x3 色0(3) min w=5x 1-3x 22% - x2 +4X3 A2N +x2 2% 兰13% x2 x3 兰 3xi 30,x2 3 0,x3 3 0(4) max z=4x 1+3X2+6X3x| 2x2 4x3 =10s.t.t 2Xr +5x2 +3x3 =150 30, x2 启 0, x3 3 03.2试写岀下述LP问题的对偶问题：(1) 1.1 ( 1)题 (2) 1.5 题 (3) 2.4 (5)题 (4) 2.4 ( 7)题(5) min w=2x 1+2X2+4X32捲 +3x2 +5x3 3 23捲 + x2 +7x3