运筹学题库第一章

1、1求解下述线性规划问题min z = -3 x + 4 x4 x + 2 x 5s.t. 0、122设某种动物每天至少需要700g蛋白质、30g矿物质、100mg维生素，现有五种饲料可供 选择，每种饲料每公斤营养成分的含量及单价如表所示。试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。饲料蛋白质/g矿物质/g维生素/mg价格/ （元/kg）1310.50.2220.510.7310.20.20.446220.35180.50.80.83某医院昼夜24h各时段内需要的护士数量如下：2： 006： 00 10人，6： 0010： 00 15 人，10： 0014： 00 25

2、人，14： 0018： 00 20 人，18： 0022： 00 18 人，22： 002： 00 12 人。护士分别于 2： 00，6： 00，10： 00，14： 00，18： 00，22： 00 分 6 批上班，并连续 工作8小时。试建立模型，要求既满足值班需要，又使护士人数最少。4某人有一笔30万元的资金，在今后三年内有以下投资项目：（1）三年内的每年年初均可投资，每年获利为投资额的20%，其本利可以起用于下一年 投资；（2）只允许第一年年初投入，第二年年末可收回，本利合计为投资额的150%，但此类投 资限额不超过15万元；（3）于三年内第二年初允许投资，可于第三年末收回，本利合计为投

3、资额的160%，这类 投资限额20万元。（4）于三年内的第三年初允许投资，一年回收，可获利40%，投资限额为10万元。试为该人确定一个使第三年末本利和为最大的投资计划。网上下载部分：1某厂准备生产A、B、C三种产品，它们都消耗劳动力和材料，如下表：产品名称耗用设备（台时/件）耗用材料（kg/件）利润（元/件）A633B341C554资源量45 （台时）30 （kg）试建立能获得最大利润的产品生产计划的线性规划模型，并列出初始单纯形表。某航空公司为满足客运量日益增长的需要，正考虑购置一批新的远程、中程、短程的喷 气式客机。每架远程的喷气式客机价格670万元，每架中程的喷气式客机价格500万元，每

4、 架短程的喷气式客机价格350万元。该公司现有资金15000万元可以用于购买飞机。根据估 计年净利润每架远程客机42万元，每架中程客机30万元，每架短程客机23万元。设该公 司现有熟练驾驶员可用来配备30架新的飞机。维修设备足以维修新增加40架短程的喷气式 客机，每架中程客机的维修量相当于4/3架短程客机，每架远程客机的维修量相当于5/3 架短程客机。为获得最大利润，该公司应购买各类飞机各多少架？（建立模型，不需求解）卜表1是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a ,a ,a ,d,c ,c为待定常数，d0。试说明这些常数分别取何值时，以下结论成立。12312（1）表中解

5、为惟一最优解；（2）表中解为最优解，但存在无穷多最优解；（4）（3）该线性规划问题具有无界解；（4）表中解非最优，为对解改进，换入变量为气，换出变量为气基bXXXXXX123456Xd4a10a0X2-1-301-1063a3-500-41z,c00-30根据以下条件建立线性规划数学模型某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资 源的限量，单位产品的利润如下表所示：单位 产4消耗、资源ABC资源限量原材料1.01.54.02000机械台时2.01.21.01000单位利润101412根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销

6、售量分 别为250，280和120件。月销售分别为250，280和120件，问如何安排生产计划，使总利 润最大？解：设乂注2%分别设代表三种产品的产量，则线性规划模型为maxZ=10X1+14X2 +12X3s t | X1 +1.5X2+4X3W20002X+1.2X2+X3W1000 200WXW250250WX；W280E，%，X330把下列线性规划问题化成标准形式：1. minZ = 5xj 一 2x2ixt + -|-x24一 Xi + X2 - 2 2x2 .r, - - *2.=工一工广，化为赫罹更为 jnizjrZ = 2jci/ + x3 = 2工/ +工】 * h. +力/

7、 - 了广=45 . 工】+ JE* 了/ + M】* 十 n = 6工广，七1居j.工丁彳工溺A 05.根据所给条件建立线性规划模型。某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根， 长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省？ 答：将10米长的钢筋截为3米和4米长，共有以下几种下料方式：长度-种-类-一IIIm3米0124米210设xx2，x3分别表示采用i、ii、m种下料方式的钢筋数，则线性规划模型可写成： minZ= X1 +X2 +X32X2+3X3A90 2X1+X260X1，X2，X3301.下表为用单纯形法计算时某一步的表格。已知

8、该线性规划的目标函数为maxZ=5x1+3x2，约X1X2X3X,10b-1gX32CO11 / 5xiade01.3, 4束形式为“w”，x , x为松驰变量，表中解代入目标函数后得z=10 求表中.3, 4 求表中ag的值(2)表中给出的解是否为最优解?解：(1) a=2 b=0 c=0 d=1 e=4/5 f=0 g= 5表中给出的解为最优解2.用单纯形法求解下列线性规划问题：maxZ=3x +5x尸户15s t2x2W123x1+2x2W 18 X, x20 解：化为标准形式12maxZ =3xi + 5x2+x3 + 0 x4+0 x5 s t x+ x3=152x2 +x5=12*

9、 3x1+2x2+x5=18巳30(j=1,，5)c.35000C Bx Bbx1x2x3xx50 x315000 x4120(2)0100 xs.1832001c z35000JJ0 x315101000 x460101/200 x6(3)0011c z300 5/20JJ0 x3130011/3 1/35x260101/203x2100 1/31/2c. z.000 3/21最优解 X* = (2, 6, 13, 0, 0) t Z*=363.用大M法求解下列线性规划问题maxZ = I 十 t 3x3 X| + 2 + 3xj = 152xj + xj； + 5xj = 20 s. tB

10、0(j = 1- ,4)解：化为标准形式maxZ=x1+2x2+3x3 x4mx5mx6 s t * x1+2x2+3x3 +x5=152x1+x2+5x3+x6=20 x +2x +x +x4=10123*x 30 (j=1,6)c j-J123-1-M-MC Bx Bbx 1x 2x 3x 4x 5xMx515123010Mx202150011x 101(2)1100c z4M+15M+29M+3000Mx5。5002-110Mx 615(3/2)04/2-1/2012x51/211/21/200c. z.3 -M201313 M+223八-M+2200Mx5500(2)-1101x110

11、103-1/302/32x200112/30-1/3c z002M+2-M-20-M3x15/2001-1/21/201x15/21007/6-3/22/32x25/201011/2-1/3c. z.000-7/2-M-1-Mx*= ( 5 , 5, , 0, 0, 0) t, z*=15222用单纯形法求解线性规划问题minZ=2X+x2+x3s t3X+ x2+x360X X2 +2x3 10V xi+x2x320、x；0 (j=1,2, 3) 解：化为标准形式maxZ =2xi x2+x3s t V 3xi+ x2+x3+x4=60 xi x2 +2x3+x5=10V x1+x2x3+x

12、6=20巳30(j=1,6)-.c211000jCxbxxxxxxBB1234560 x6031110040 x10(1)1201050 x20111001c z211000jj0 x3004513040 x1011201010 x100(2) 30 161c z013020jj0 x1000111242x115101/201/21x251/201 3/20 1/21/2c z00 5/201/2jj1/2最优解 X* = (15, 5, 0, 10, 0, 0) t Z*= 25福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售 货人员充分休息，售货人员每周工作

13、五天，休息两天，并要求休息的两天是连续的，问该如 何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。时间所需售货人员数时间所需售货人员数星期一28星期五19星期二15星期六31星期三24星期日28星期四25.加入人工变量，化原问题为标准形maxz = 3xi +5x2 +0 x3 +0 x4 -Mx5 PXi+ X3 = 42x2 +X4 =123xi +2x2 +X5 =18最优单纯形表如下？ 1,2,3,4,5XX】X2X3X4X5bC3500- MX】3100-1/31/32X300011/3-1/32X250101/206Zjqc003/2

14、M +1所以最优解为X = (2,6,2,0,0), Z* = 3626.解：设疝为从星期i（i=l,2,3,7）开始休息的人数。7则 minz = xi5l=l6i=27Ei=3i=l5l=l6i=27Ei=3x*8为N 24X4 + X5 + 乂6 + x? + X N 25 x5+ x6+x7+xj+x2 19 X6+X7+xi+X2+X3 N31 x7 + Xi + X2 + X3 + X4 + 为 N 28% N0Ji=l,2,7）三、（15分）某厂生产甲、乙两种产品，这两种产品均需要人、B、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表

15、所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设z是产设甲、乙产品的生产数量应为x1、x2，则x1、x2N0设z是产max z =70 x1+120 x2s.t.9x + 4x 3604x：+ 6x： 2003 x +10 x 02）用单纯形法求最优解：加入松弛变量x3, x4, x5,得到等效的标准模型: max z =70 x1+120 x2+0 x3+0 x4+0 x5s.t.9 x + 4 x + x = 3604 x1 + 6 x2+ x

16、 = 2003 x +10 x+ x = 300 x 0, j = 1,2,.,55列表计算如下:111111.max z =70X 也 +120X 迎=些111111用大M法或对偶单纯形法求解如下线性规划模型:min z =5x1 + 2x2+4x33 x + x + 2 x 4 10 x , x , x 0V 123解：用大M法，先化为等效的标准模型:max z/ =5x 2x 4x3s.t.3 x + x + 2 x - xx = 100,j = 1,2,.,5i j增加人工变量x6、x7，得到:max Z =5x 2x 4x Mx Mx7s.t3 x + x + 2 x - x=10

17、0, j = 1,2,.,7 =10大M法单纯形表求解过程如下:CBXBb-5-2-400-M-MX1X2X3X4X5X6X70l-M-MX6:(3)12-10106350-1014/35/3-9M-4M-7MMM-M-M9M-5 t4M-27M-4-M-M00-5-MX14/311/32/3-1/301/30011(2)-1-211-5-M-5/3-M-10/3 -2M+5/3 M2M-5/3-M0M-1/3 M-2/3 2M-5/3 t-M-3M+5/30-5X15/311/25/60-1/601/60(1/2)1/21-1/2-11/210/3-5-5/2-25/605/60-5/601

18、/2 t1/60-5/6-M-m+5/6-5X12/3101/3-11/31-1/30112-1-21_ 22-5-2-11/311/3-1-1/3001/311/3m+1-m+1/32.x*= (3, 2, 0, 0, 0) t最优目标函数值min z =max z =（-号）=22 一家工厂制造甲、乙、丙三种产品，需要三种资源一一技术服务、劳 动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得 的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型

19、；（5分）2）用单纯形法求该问题的最优解。（10分）解：1）建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为xx2、X3,则xx2、X3N0,设z是产品售后的总利润，贝Umax z =10 xi+6x2+4x3s.t.X + X + X 100 TOC o 1-5 h z 12310 x + 4x + 5 x 6001232x1 + 2X2 + 6X3 0v 1232）用单纯形法求最优解：加入松弛变量x4, x5, x6，得到等效的标准模型：max z =10 x1+6x2+4x3+0 x4+0 x5+0 x6s.t.100100=600300X + X + X + X TOC o 1

20、-5 h z 1234 HYPERLINK l bookmark82 o Current Document 10 x + 4 x + 5 x+ xJ 12352 x + 2 x + 6 x+ x1236X. 0, j = 1,2,.,6列表计算如下：CBXBb10640000l0 x41001111001000 x5600(10)45010600X630022600115000000010 f640000X4400(3/5)1/21-1/100200/310X16012/51/201/1001500X618006/550-1/51150104501002 f-10-106X2200/3015/

21、65/3-1/6010X1100/3101/6-2/31/600X6100004-201220010620/310/32/30300-8/3-10/3-2/30.*(旨,* 0 0 0 100)T.max z =10 X.max z =10 X100+6X3200 22003寸i.化为标准型min Z =2X+x2-2x3J1+x2+x3 =4+x -x W6x3无约束W0,，x2x3无约束-消21产品原料J甲乙丙原料量A63545B34530单件利润415求使该厂获利最大的生产计划。目标函数为max Z =28x4+x5+2x6，约束形式为“W”，且x1, x2, x3为松弛变量， 表中的解

22、代入目标函数中得Z=14,求出ag的值，并判断是否最优解。C0002812CbXBbxx2x3%x5x6a310-14/30056d205/202800ef100c-zbc00-1g一、分别用人工变量法和两阶段法求解下列线性规划问题max z=-2x1-3x2-x3x1+4x2+2x3=8J 3x1+2x2=6j x1,x2,x3=0三、某文教用品厂利用原材料白坯纸生产原稿纸、日记本和练习本三 种产品。该厂现有工人100人，每天白坯纸的供应量为30000千克。 如单独生产各种产品时，每个工人每天可生产原稿纸30捆，或日记 本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸 10/3

23、千克，每打日记本用白坯纸40/3千克，每箱练习本用白坯纸80/3 千克。已知生产各种产品的盈利为:每捆原稿纸1元，每打日记本两 元，每箱练习本3元。试决定：（1）在现有生产技术条件下，使该厂 盈利最大的方案。（2）如白坯纸供应量不变，而工人的数量不足时可 从市场上招收临时工，临时工费用为每人每天15元。问该厂应否招收临时工及招收多少人为宜。3、某饲养场需饲养动物，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现 有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1-8所示。表1-8饲料蛋白质庖矿物质向维生素fmg价格/元奖131050222051J00.731020

24、2044622035180$0J80J8要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。列解模型（40分）1、某灌区的开发，涉及三种主要的限制资源，可能安排的作物有三种，种植各种作物每亩所需要的资源及其净收益见表1。资源 名称单位可利用资源数各种作物所需资源数玉米水稻棉花土地亩100111肥料100公斤50000.5水100 m380120各种作物每亩净收益3040121）试列出使灌区的总收益最大的线性规划模型。2）应用单纯形法求解该模型。4. （15分）某农场生产四种农作物，每种农作物的成本和利润如下:农作物肥料（公斤/亩）杀虫剂（公斤/亩）利润（元）萝卜4250包心菜294

25、0洋葱5210土豆0320目前农场有400公斤肥料和500公斤杀虫剂，问每种农作物种植多少亩才使 利润最大？）某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下:甲乙原材料（吨/件）22工时（工时/件）52.5可用量3000 吨4000工时用表解形式的单纯形法求解;求最大利润。解：设甲、乙两种产品的生产数量为x、x2,设z为产品售后总利润，则max z =气+3七s.t.2工 + 2x 30005x + 2.5x 400012x 0加入松弛变量x3，x4, x5,得到等效的标准形式:max z= 4x +3x +0 x +0 x,+0 x.2345s.t.2x + 2x + x

26、 = 30005x + 2.5x + x = 4000124x + x = 500 x, 0 , j = 1,2,.,500000 x20000210-22000/2=10000X415000(2.5)01-51500/2.5 =6004x500100014000403f00-40 x800001-0.8(2)800/2=4003x6000100.4-24x50010001500/1=5004301.2-2000-1.22t0 x5400000.5-0.413x1400011-0.404x10010-0.50.40460043-10.4-0.40据上表，X*=(100, 1400, 0, 0,

27、400) t最大利润 max z =4 X 100+3 X 1400=4600 (元)33.一家昼夜服务的饭店，24小时中需要的服务员数如题33表: 题33表起迄时间服务员的最少人数2 : 006 : 0046 : 0010 : 00810 : 0014 : 001014 : 0018 : 00718 : 0022 : 001222 : 002 : 004每个服务员每天连续工作8小时，且在时段时上班。问题的目标是求满足以上要求的最少上班人数，试对这个问题建立线性规划模型。34.求出线性规划问题：max Z = X + 3Xs.t. 5X1 + 10X2 50 1的最优解。X2 01、消费者购买

28、某一时期需要的营养物（如大米、猪肉、牛奶等）希望获得其中的营养成分 （如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分 数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物 营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用 计算。解：设购买甲、乙、丙三种营养物的数量分别为气、七和七则根据题意可得如下线性规划模型：min z = 25x + 20 x + 45x4x + 6x

29、 + 20 x 80 x + x + 2x 65 TOC o 1-5 h z 123s.t 7021x + 7x +35x 450123x , x , x 0v123将下列线性规划化为标准形式 max Z = x + 4x 一 x2x + x + 3x 310 x + 3x + 6x -5 1 2 3 x 0,x 0,x无限制 123用单纯形法求解下列线性规划max Z = 3x + 4 x + x2x + 3x + x 1 x + 2 x + 2 x 0, j = 1,2,3/6某投资人现有下列四种投资机会，三年内每年年初都有3万元（不计利息）可供投资： 方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20%,下一年可 继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50%,下一年可 继续将本息投入获利，这种投资最多不超过2万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60%，这种投资 最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资，一年