1、线性规划习 题 一11 试述 LP 模型的要素、组成部分及特征。判断下述模型是否 LP 模型并简述理由。 （式中 x,y 为变量；为参数；a,b,c,d,e 为常数。 ）（1）max z=2x 1-x2-3x3s.t. 1235840,x(2)min z= 1nkxs.t. 1,2.,0nikiabmx(3)min z= 11nnijys.t. ,2,.ijjiixcmydne(4)max z= 1njcxs.t. 1,12,.0,.nijiijabdmxn1.2 试建立下列问题的数学模型：（1）设备配购问题某农场要购买一批拖拉机以完成每年三季的工作量：春种 330 公顷，夏管 130 公顷，
2、秋收 470 公顷。可供选择的拖拉机型号、单台投资额及工作能力如下表所示。问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小？（2）物资调运问题单台工作能力（公顷）拖拉机型号 单台投资（元） 春种 夏管 秋收东方红丰收跃进胜利5000450044005200302932311714161841434244甲乙两煤矿供给 A，B，C 三个城市的用煤。各矿产量和各市需求如下表所示：煤矿 日产量（吨） 城市 日需求量（吨）甲乙200250ABC100150200各矿与各市之间的运输价格如下表示：问应如何调运，才能既满足城市用煤需求，又使运输的总费用最少？（3）食谱问题某疗养院营养师要为某
3、类病人拟订本周菜单。可供选择的蔬菜及其费用和所含营养成分的数量，以及这类病人每周所需各种养分的最低数量如下表所示：每 份 所 含 养 分 数 量（毫克） 养分蔬菜 铁 磷 维生素 A 维生素 C 烟酸每份的费用（元）青豆胡萝卜花菜卷心菜甜菜土豆0.45 10 415 8 0.30.45 28 9065 3 0.351.05 50 2550 53 0.60.4 25 75 27 0.150.5 22 15 5 0.250.5 75 235 8 0.80.150.150.240.060.180.10每周养分最低需求量6.0 325 17500 245 5.0 另外为了口味的需求，规定一周内所用的卷
4、心菜不多于 2 份，其它蔬菜不多于 4 份。若病人每周需 14 份蔬菜，问选用每种蔬菜各多少份？（4）下料问题某钢筋车间要用一批长度为 10 米的钢筋下料制作长度为三米的钢筋 90 根和长度为四米的钢筋 60 根，问怎样下料最省？用图解法求解下列 LP 问题：（1）min z=6x 1+4x2s.t. 1234.50,x(2) max z=2.5x1+x2s.t. 1250,x城 市煤矿运价（元/吨）A B C甲乙90 70 10080 65 80(3) max z=2x1+2x2s.t. 120.5,x(4) max z=x1+x2s.t. 1230,x(5) min z=2x1-10x2s
5、.t. 1250,x(6) min z=-10x1-11x2s.t. 1234580,x1.4 把 1.3 题的（3）-（6）化成标准形.1.5 把下列 LP 问题化成标准形。(1) min z=2x1+3x2+5x3s.t. 12356790,x(2) min z=3x1+4x2+2x3+x4s.t. 1234746,0xx1.6 证明下述 LP 问题的可行域是一个空集：min z=x1-2x2+2x3+x4s.t. 12346,0xx1.7 已知 LP 问题如下：min w=x1+2x2-3x3+4x4s.t. 2341557,0x判断下述各点：X 1=(8,2,7,-4)T,X2=(1,
6、0,2,1)T,X3=(2,0,5,0)T X4=(0,0,-1,2)T,X1=(3,1,0,0)T,X1=(2,1/2,1,1/2)T是不是该 LP 问题的可行解、基本解、基本可行解？试从中找出一个较优解。1.8 设某线性规划问题的可行域如下：123451234523078,xx试判断下述各点：X1=(5,15,0,20,0)T,X2=(9,7,0,0,8)T,X3=(15,5,10,0,0)T是否为该可行域的极点并说明理由。1.9 设一标准形 LP 问题的系数阵为A= 0316X0=(1,2,1)T是一可行解。试按性质 4 证明中的方法，构造出另一个可行解。1.10 试证明：若 LP 问题
7、有两个不同的最优基本解，则必有无穷多个最优解。1.11 设 R1,R2 为凸集，则nE(1) R1+R2=Z|Z=X+Y,XR 1 ,YR 2(2) R1-R2=Z|Z=X-Y,XR 1 ,YR 2(3) R 1=Z|Z=X, XR 1,E 1均为凸集。1.12 设 Ri 为凸集,i=1,2,则 R=nEiR也为凸集。1.13 试举出下述某一类型的 LP 问题的实例：产品配比问题，配料问题，物资调运问题，食谱问题，下料问题及其它 LP 问题，然后建模并化标准形，再设法找出一个基本可行解。1.14 用枚举法求解下述 LP 问题：（1）min w= 1234xs.t. 1320,0xx（2）min
8、 w= 13s.t. 1234100,x(3)1.3 题之（2）(4)1.3 题之（6）1.15 某农户年初承包了 40 亩土地，并备有生产专用资金 2500 元。该户劳动力情况为：春夏季 4000 工时，秋冬季3500 工时。若有闲余工时则将为别的农户帮工，其收入为： 春夏季 0.5.元/工时， 0.40 元/工时。该户承包的地块只适宜种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养奶牛和鸡。每年每头奶牛需投资 400 元，每只鸡需投资 3 元。每头奶牛需用地 1.5 亩种植饲草，并占用劳动力：春夏季 0.3 工时和秋冬季 0.6 工时，每年净收入 10 元
9、。该农户现有鸡舍最多能容纳 300 只鸡，牛棚最多能容纳 8 头奶牛。三种农作物一年需要的劳动力及收入情况如下表所示。问该农户应如何拟订经营方案才能使当年净收入最大？试建立该问题的数学模型。大豆 玉米 小麦春夏季需工时/亩 20 35 10秋冬季需工时/亩 50 75 40净收入（元/亩） 50 80 401.16 某罐头食品长用 A,B 两个等级的西红柿加工成整番茄、番茄汁、番茄酱三种罐头。A,B 原料质量评分分别为 90，50 分。为保证产品质量，该厂规定三种罐头的品格（所用原料的质量平均分）如下表所示：罐头品名 整番茄 番茄汁 番茄酱品格（分） 80 60 50该厂现以 0.5 公斤 6
10、 分的价格购进 1500 吨西红柿，其中可挑出 A 等西红柿 20%，其余为 B 等。据市场预测，三种罐头的最大需求量为：整番茄 800 万罐，番茄汁 50 万罐，番茄酱 80 万罐。原料耗量为：整番茄 0.75 公斤/罐，番茄汁 1.0 公斤/罐，番茄酱 1.25 公斤/罐。三种罐头的价格及生产费用（其中不包括西红柿原料费）如下表所示。问该厂应如何拟订西红柿罐头的生产计划才能获利最大？试建立数学模型。（元/罐）整番茄 番茄汁 番茄酱价格 0.86 0.90 0.76加工费 0.236 0.264 0.108其它费用 0.351 0.384 0.3171.17 某厂生产甲、乙两种产品，每种产品
11、都要在 A,B 两道工序加工。其中 B 工序可由或 B2 完成，但乙产品不能用 B1 加工。生产这两种产品都需要 C,D,E 三种原材料，有关数据如下表所示。又据市场预测，甲产品每天销售不超过 30 件。问应如何安排生产才能获利最大？试建立数学模型。产品单耗 日供应量 单位成本甲 乙 数量 单位 数量 单位工序AB1B223114806070工时工时工时625元/工时元/工时元/工时原材料CDE3541231.5300100150米件公斤214元/米元/件元/公斤其他费用（元/件） 26 29单价（元/件） 80 1001.18 制造某机床需要 A,B,C 三种轴，其规格、需要量如下表所示。各
12、种轴都用长 7.4 米的圆钢来截毛坯。如果制造 100 台机床，问最少要用多少根圆钢？试建立数学模型。轴件 规格：长度（米） 每台机床所需轴件数量ABC2.92.11.21111.19 某木材公司经营的木材储存在仓库中，最大贮存量为 20 万米 3。由于木材价格随季节变化，该公司于每季初购进木材，一部分当季售出，一部分贮存以后出售。贮存费为 a+bu, 其中 a=7 元/米 3，b=10 元/米 3 /季，u 为贮存的季度数。由于木材久贮易损，因此当年所有库存木材应于秋末售完。各季度木材单价及销量如下表所示。为获全年最大利润，该公司各季应分别购销多少木材？试建立数学模型。季 购时价（元/米 3
13、） 售出价（元/米 3） 最大销售量（万米 3）冬春夏秋31032534834032133335234410142016单纯型法习题二2.1 分别用图解法和单纯形法求解下述 LP 问题，并指出单纯形法迭代中每一基本可行解跟图解法可行域中哪一极点相互对应。（1）max z=10x 1+5x2s.t. 12349580,x(2) max z=2x1+x2s.t. 126450,x2.2 用单纯形法求解 1.7 题。2.3 用单纯形法求解下述 LP 问题：（1）max z= x 1+2x2+3x3+4x4s.t. 1234,0（2）第一章例 4（3）max z= x 1+x2+x3+x4s.t. 1
14、2346,0x（4）min w= x 2-3x3+2x5+2x6s.t. 413526127800,.j xx2.4 用单纯形法求解下述 LP 问题：(1) max z=2x1+2x2s.t. 120.5,x(2) max z=10x1+5x2s.t. 120,x(3) max z= 5x1+3x2+2x3+4x4s.t. 123445810,xx(4) min w= 2x1+3x2+x3s.t. 12386,0x(5) min w=2 x1+x2-x3-x4s.t. 123467,0x(6) max z=10 x1+15x2+12x3s.t. 12335965,0x(7) min z= 3x
15、1-4x2+x3-2x4s.t. 1234123431055,0xxx2.5 以 2.1 题之（1）为例，具体说明当目标函数中变量的系数怎样改变时，能够：（1）分别使每个极点成为最优点；（2）使该 LP 问题有多重最优解。2.6 分别举出符合下述情况的 LP 问题之例：（1）多重最优解；（2）最优解为退化的基本可行解；（3）最优解无界；（8）无可行解。2.7 求解 1.18 题。2.8 在一块地上种植某种农作物，据以往经验，在其生长过程中至少需要氮 32 公斤，磷恰以 24 公斤为宜，钾不得超过 42 公斤。现有四种肥料，其单价及氮磷钾含量（%）如右表所示。问在该地块上施用这四种肥料各多少公斤
16、，才能满足该农作物对氮磷钾的需要，又使施肥的总成本最低？成分 肥含量 （%）料成 分甲 乙 丙 丁氮磷钾3 30 0 155 0 20 1014 0 0 7 单价（元/公斤） 0.04 0.15 0.10 0.132.9 试用矩阵形式的单纯形法解答下列问题：（1）已知用单纯形法求解某 LP 问题所得到的初始单纯形表及最末单纯形表如下，试将表中空白处填上适当字符。Cj 3 2 5 0 0 0基 解 X1 X2 X3 X4 X5 X64346421 2 1 1 0 03 0 2 0 1 01 4 0 0 0 1检验行. .1/2 -1/4 00 1/2 0-2 1 1检验行 (2)已知用单纯形法求
17、解某 LP 问题，中间某两次迭代的单纯形表如下，试将表中空白处填上适当字符。Cj 3 5 4 0 0 0基 解 X1 X2 X3 X4 X5 X62 1 1 0 1 0 0210-1 0 1 -1 1 01 0 4 0 0 1检验行. .X2 4/5 -1/51/5 1/5-4/5 1/5检验行 2.10 试用改进单纯形法求解下述 LP 问题：（1）max z=10 x 1+15x2+12x3213256,0x(2) max w=10 x1+7x2+4x3+3x4+x512345780,jx对偶原理习 题 三3.1 试建立下述 LP 问题的对偶关系表，并写出其对偶问题：（1）max z=4x
18、1+3x2+6x3s.t. 1233604,xx（2）min w=60x 1+10x2+20x3s.t. 1230,0xx（3）min w=5x 1-3x2s.t. 312340,0xx（4）max z=4x 1+3x2+6x3s.t. 123405,xx3.2 试写出下述 LP 问题的对偶问题：（1）1.1（1）题 （2）1.5 题 （3）2.4（5）题 （4）2.4（7）题（5）min w=2x 1+2x2+4x3s.t. 123537460,x(6) min w=2x1+3x2+6x3+x4s.t. 123471850,0xx3.3 试证明 LP 问题（P 2）是（D 2）的对偶， （P 2）是（D 2）的对偶。3.4 试写出下述 LP 问题的对偶问题：（1）min w=C TXs.t. (0)Aba(2) min z= 1mnijicxs.t. 1,2,.,.0nijimijjijaxbn(3) max z= 1njcx
