1.5 线性规划应用举例与分析

线性规划目前应用非常广泛也非常成功，但由于实际问题是复杂的、千变万化的，因此要根据问题的求解目标，分析问题内在逻辑关系，正确构建线性规划模型。

例1-11 （合理下料问题）某工厂要制作100套专用钢架，每套钢架需要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料每根长7.4m，现考虑应如何下料，可使所用原料最省？

解：利用7.4m长的圆钢截成2.9m、2.1m、1.5m的圆钢共有表1-19所示的8种下料方案。

一般情况下，可以设x1,x2,x3,x4,x5,x6,x7,x8分别为上面8种方案下料的原材料根数，根据目标的要求，建立如下目标函数。

材料根数最少：

min z=x1+x2+x3+x4+x5+x6+x7+x8

约束方程是要满足各种方案剪裁得到的2.9m、2.1m、1.5m三种圆钢各自不少于100个，即

2.9m：2x1+x2+x3+x4≥100

2.1m：2x2+x3+3x5+2x6+x7≥100

1.5m：x1+x3+3x4+2x6+3x7+4x8≥100

非负条件 x1,x2,x3,x4,x5,x6,x7,x8≥0

这样可建立如下数学模型：

利用单纯形法求解可得：x*=(10,50,0,30,0,0,0,0)T，最少使用的材料为90（根），各种圆钢数均正好100个。

有同学可能会考虑从料头最省的角度建立模型：

利用单纯形法求解可得：x*=(0,0,0,100,0,50,0,0)T，最少的剩余料头为10m。这时2.9m和2.1m的圆钢数正好100个，而1.5m的圆钢数多300个。显然，这不是最优解，为什么会出现误差呢？仔细思考会发现，原因出现在方案4的剩余料头为零，求解过程中目标函数最小对它失去了作用。

例1-12 （连续投资问题）某企业现有资金200万元，计划在今后5年内给A，B，C，D4个项目投资。根据有关情况的分析得知：

对于项目A，从第一年到第五年，每年年初都可进行投资，当年末就能收回本利110%；

对于项目B，从第一年到第四年，每年年初都可进行投资，当年末能收回本利125%，但是要求每年最大投资额不能超过30万元；

对于项目C，若投资则必须在第三年年初投资，到第五年年末能收回本利140%，但是限制最大投资额不能超过80万元；

对于项目D，若投资则需在第二年年初投资，到第五年年末能收回本利155%，但是规定最大投资额不能超过100万元；

根据测定每万元每次投资的风险指数为：项目A为1，项目B为3，项目C为4，项目D为5.5。

问题：应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？

解：（1）确定决策变量。本题是一个连续投资的问题，由于需要考虑每年年初对不同项目的投资数，为了便于理解，建立双下标决策变量。

设xij(i=1,2,3,4,5；j=1,2,3,4)表示第i年初投资于项目A(j=1)、项目B(j=2)、项目C(j=3)、项目D(j=4)的金额。根据题意，我们建立如下决策变量：

第一年年初 第二年年初 第三年年初 第四年年初 第五年年初项目A项目B项目C项目D

（2）考虑约束条件。由于项目A的投资当年末就可以收回本息，因此在每一年的年初必然把所有的资金都投入到各项目中，否则一定不是最优的。下面我们分年来考虑。

第一年年初：由于只有项目A和项目B可以投资，又应把全部200万元资金投出去，于是有：

x11+x12=200

第二年年初：由于项目B要次年年末才可收回投资，故第二年年初的资金只有第一年年初对项目A投资后在年末收回的本利110%x11，而投资项目为A，B和D，于是有：

整理后得：

x21+x22+x24=1.1x11

−1.1x11+x21+x22+x24=0

第三年年初：年初的资金为第二年年初对项目A投资后在年末收回的本利110%x21，以及第一年年初对项目B投资后在年末收回的本利125%x12。可投资项目有A，B和C，于是有：

x31+x32+x33=1.1x21+1.25x12

整理后得：

−1.1x21−1.25x12+x31+x32+x33=0

第四年年初：年初的资金为第三年年初对项目A投资后在年末收回的本利110%x31，以及第二年年初对项目B投资后在年末收回的本利125%x22。可投资项目只有A和B，于是有：

x41+x42=1.1x31+1.25x22

整理后得：

−1.1x31−1.25x22+x41+x42=0

第五年年初：年初的资金为第四年年初对项目A投资后在年末收回的本利110%x41，以及第三年年初对项目B投资后在年末收回的本利125%x32。可投资项目只有A，于是有：

x51=1.1x41+1.25x32

整理后得：

−1.1x41−1.25x32+x51=0

其他的还有项目B，C，D的投资限制以及各决策变量的非负约束。

项目B的投资限制：xi2≤30（i=1，2，3，4）

项目C的投资限制：x33≤80

项目D的投资限制：x24≤100

各决策变量的非负约束：xi1，xj2，x33，x24≥0（i=1，2，3，4，5；j=1，2，3，4）

（3）建立目标函数。问题要求在第五年末公司这200万元用于4个项目投资的运作获得本利最大，而第五年末的本利获得有4项：

第五年年初对项目A投资后，在年末收回的本利110%x51；

第四年年初对项目B投资后，在年末收回的本利125%x42；

第三年年初对项目C投资后，在年末收回的本利140%x33；

第二年年初对项目D投资后，在年末收回的本利155%x24。于是得到目标函数为：

z=1.1x51+1.25x42+1.4x33+1.55x24

根据上面的分析得到线性规划模型：

例1-13 （场地租借问题）某厂在今后四个月内需租用仓库堆存货物。已知各个月所需的仓库面积数如表1-20所示。又知，当租借合同期限越长时，场地租借费用享受的折扣优待越大，有关数据如表1-21所示。

表1-20 场地面积需求

表1-21 场地租借费用

租借仓库的合同每月都可办理，每份合同应具体说明租借的场地面积和租借期限。工厂在任何一个月初办理签约时可签一份，也可同时签若干份租借场地面积数和租借期限不同的合同。为使所付的场地总租借费用最小，试建立一个线性规划模型。

解：设xij为第i个月初签订的租借期限为j个月的合同租借面积（单位：百米2），于是，有下列决策变量：

各个月生效的合同的租借面积为：

第一个月：x11+x12+x13+x14

第二个月：x12+x13+x14+x21+x22+x23

第三个月：x13+x14+x22+x23+x31+x32

第四个月：x14+x23+x32+x41

从而，我们得如下线性规划模型：

例1-14 （环境保护问题）某河流旁设置有甲、乙两座化工厂，如图1-3所示。已知流经甲厂的河水日流量为500×104m3,在两厂之间有一条河水日流量为200×104m3的支流。甲、乙两厂每天生产工业污水分别为2×104m3和1.4×104m3，甲厂排出的污水经过主流和支流交叉点P后已有20%被自然净化。按环保要求，河流中工业污水的含量不得超过0.2%，为此两厂必须自行处理一部分工业污水，甲、乙两厂处理每万立方米污水的成本分别为1000元和800元。问：在满足环保要求的条件下，各厂每天应处理多少污水，才能使两厂的总费用最少？试建立规划模型。

解：设甲、乙两厂每天分别处理污水量为x、y（单位：104m3）目标

函数minz=1000x+800y

在甲厂到P点之间，河水中污水含量不得超过0.2%，所以满足

在P点到乙厂之间，河水中污水含量也不得超过0.2%，所以应满足

流经乙厂以后，河水中污水含量仍不得超过0.2%，所以应满足

综上，得线性规划模型：

求解结果为x=1×104m3,y=0.8×104m3，总费用最少为1640元。