第五节 线性规划建模举例

第五节线性规划建模举例线性规划是运筹学中应用最广泛和最有效的一个分支，在用线性规划方法解决实际问题时，建模是十分重要和很关键的一步，它是在把实际问题条理化和抽象化的基础上进行的，是一种创造性的思维过程，兴有当建立的模型能正确反映实际问题的条件和决策者的要求时，才能进一步得出有意义的解答，为决策者作出正确决策提供帮助。线性规划问题建模可按以下步骤进行：分析实际问题，弄清需要确定的未知量，在此基础上假定自变量（决策变量）。这些自变量应彼此独立，意义明确，且可借助它们将实际问题正确、方便地表达出来。确定有关参数的数据，包括价值系数c、约束条件右侧常数b和约束j 1条件中的系数a。认清决策者想要达到的主要目标，据此列出目标函数（自变量的线性函数），并决定是要极大化或极小化。分析并汇总问题的限制条件（包括明显的和隐含的）将其与有关自变量和参数联系起来，并逐一表达成等式或不等式约束。约束条件既不要遗漏（有些限制条件未考虑到）也不要重复。写出完整的线性规划数学模型，并进一步检验是否与描述的实际问题一致，如有不一致之处，则应适当修改模型。对复杂的实际问题，有时还需在求解时进一步修正模型。下面在本章第一节的基础上，再举出另外一些线性规划问题建模的例子，供读者分析思考，从中得到启发。例14裁料问题在某建筑工程施工中需要制作10000套钢筋，每套钢筋由2.9m2.1m和1.5m三种不同长度的钢筋各一根组成，它们的直径和材质相同。目前在市场上采购到的同类钢筋的长度每根均7.4m问应购进多么根7.4m长的钢筋才能满足工程的需要？解该问题最简单的处理方法是：在每根.4m长的钢筋上截取2.9m2.1m和1.5m的短钢筋各一根，剩下料头0.9m共用去10000根7.4m长的钢筋。但这样做常是不经济的，基改用套裁就会节约原材料。为此，必须分析共有多少种不同的裁法，该问题的可能裁料方案示于表1.10中。表1.10*裁得根'方案下料长度（m^^\^裁料方案编号i123456782.9211100002.1021032101.510130234料头长度（m）0.10.30.901.10.20.81.4设以x（i=1’2，…，8）表示按第i种裁料方案下料的原材料数量，则可i得该问题的数学模型如下fminz=x+x+x+x+x+x+x+x1 2 3 4 5 6 7 8I2x+x+x+x=10000」2x1+x+3x+2x+x=10000x2x辛3x卓2x牛3x7+4x=10000x1>0,j=f,2,,8 7 8j最后算出的z=1?x就是所需使用的7.4m钢筋原料的总数。jj=1该问题的目标函数也可改用总料头长度极小化。由本例的分析过程可知，这类问题的建模需列出所有裁料方案，当方案很多时常是十分困难的。为此，需设立一些准则删除明显不合理的方案，以减少计算工作量。例15工作人员计划安排问题某昼夜服务的公共交通系统每天各时间段（每4小时为一个时间段）所需

班次时间r•nA段1n・nn所需人数16:0010:0060210：00-一-14：0070314：00-一-18：0060418：00-一-22:0050522:00-一2:002062：00-一6：0030表1.11解在本例中，每一时段上班的工作人员，既包括本时段开始上班的人，又包括上一个时段开始上班的人。为便于的值班人数如表1.11所示，这些值班人员在某一时段开始上班后要连续工作8表1.11解在本例中，每一时段上班的工作人员，既包括本时段开始上班的人，又包括上一个时段开始上班的人。为便于建模，可设x为第i个时段开i始上班的人员数，如此可得数学模型如下:'minz=x+x+x+x+x+xx+x2苴60 6x6M>70x12+x3>60x2+x>50x34+x>20x45+x>30x56>0,j=1,2,,6（仅在2（仅在2：1.9现给出它的一个解（如图.9中所示，可知该系统有150人好够1.9234521r60Ajr60A]1 50人「20A•,r30A节2：00这个时段多10人】x14:002040201030图6:00Z10:0018: 22:■:OC/2■:00 630x=40x=30x=30x=40x=10x=201例16厂址选择问题考虑A、B、C三地，每地都出产一定数量的原料，也消耗一定数量的产

品（见表1.12）。已知制成每吨产品需吨原料，各地之间的距离为：A—B:150kmA—C：100kmB—C：200km假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其它条件限制，在B处建厂的规模（生产的产品数量）不超过5万吨。表1.12解令x为由i地运到j地的原料数量（万吨），y为由主地运往解令x为由i地运到j地的原料数量（万吨），y为由主地运往j地的产ij ij品数量（万吨），i，j=1,2，3（分别对应A、B、C三地）。根据题意，'x+x+x<2012 13■厂x+x+x<16i21+x22+x23<2431 32 33y+y+y=7y11+y21+y31=1322 32注意，本来还可列出方程y+y+y=0，13 23 33而有y二y二y=0，从而可将该方程略去。13 23 33若设Q为第i处的设厂规模（年产产品数量，iQ=y+y2 21但因y、y和y132333万吨）则有Q=y122非负，因+y，11 12将x、11如下：x12Q=y+y。从而得到3 31 32x+x+x=3(y+y)x11+x12+x13=3(y11+y12)x21+x22+X3=3/1+y)31 32 33 31 32和x消去，并考虑y+yW5和变量非负条件，得约束条件33 21 22地点年产原料（万吨）年销产品（万吨）生产费用（万元万吨）A207150B1613120C240100i+3yi2+xi?+xi厂xkx3冬20+3y-x+x+x-x<16TOC\o"1-5"\h\z21 22 12 21 23 323y+3y-x-x+x+x<24y*y *y 翌7 23 31 32y11+y21+项1=1312 22 32y+y<5x2E0,2,2j=1,2,3；丰j顼圣0,i=1,2,3j=1,2j目标函数为（包括原材料运输费、产品运输费和生产费）minz=75x+75x+50x+50x+100x+100xTOC\o"1-5"\h\z12 21 13 31 23 32+90y+90y+60y+60y+150(y+y)12 21 31 32 11 12+120(y+y)+100(y+y)21 22 31 32=75x+75x+50x+50x+100x+100x12 21 13 31 23 32+150y+240y+210y+210y+160y+220y11 12 21 22 31 32某石油公司用A、B、C三种原料混合成普通汽油、高级汽油和低铅汽油3种成品出售。3种原料的单位成本及每月最大购入如表3-1。表3-1原料单位成本（元/她）每月最大购入量（也Aa100Bb150Cc50每公斤成品售价为：普通汽油d元，高级汽油e元，低铅汽油？元。低铅汽油每月最多销售50匕各种汽油规格如下：普通汽油R：A不少于20%C不多于30%高级汽油P：A不少于40%B不少于10%并不多于20%C不多于10%低铅汽油L:B不少于30%要求建立线性规划模型，以决定各种汽油的销售数量来取得最大利润。解通常，建立数学模型的第一步是确定决策变量。如果我们设x、x、x3分别为3种成品的销售数量，那么，必须知道各种汽油的成本和售价2，以便决定c。现在题目中已给出了售价，但由于各种汽油的确切配方不知道，算不出各种汽油的单位成本，因此用上面设的决策变量不能建立问题的线性规划模型。在这个问题里，必须作出两个决策，即每种汽油各用多少入、B、C原料以及各生产多少。遇到这种情况，采用双下标决策变量往往能顺利建立模型。我们设:x=j种汽油中所用的原料i(kg)，" i=A，B，C；j=R，P，L。这样，j种汽油的生产量就是：（3-1）T二丈x,j=RZFJL（3-1）ji1ij例如对普通汽油：T=x+x+xRARBRCR与此相似，原料i的需要量是：D=ILx,i=A,B,C （3-2）'j=Rj例如对原料A：D=x+x+xAARAPAL目标函数是总销售收入减总成本的余额最大，maxz=d+e+f-a-b-cTRTPTLDADBDC将式（3-1）、3-2）代入得maxz=d（x+x+x）+e（x+x+x）+f（x+x+x）ARBRCR APBPCP ALBLCL-a(x+x+x)-b(x+x+x)-c(x+x+x)(3-3)ARAPAL BRBPBL CRCPCL根据各种原料的每月最大购入量列出第一组约束条件方程：

x+x+xW100000(3-4)ARAPALx+x+xW150000(3-5)BRBPBLx+x+xW50000(3-6)CRCPCL第二组约束条件方程是对低铅汽油销售量的限制:X+X+xW50000 (3-7)ALBLCL第三组约束条件方程是各种汽油规格的限制，以普通汽油规格1为例：普通汽油中原料A的重量普通汽油中原料A的重量普通汽油重量N0.2X

AR N0.2■X +xAR+X(3-8(3-8)-0.8x+0.2x+0.2xW0与此相似，普通汽油规格2aR BRCRTOC\o"1-5"\h\z-0.3x +0.3x +0.7x W0 (3-9)高级汽油规格1： CR-0.6x +0.4x +0.4x W0 (3-10高级汽油规格2： BP C'0.1x -0.9x + 0.1x W0 (3-1D-0.2x +0.8x -0.2x W0 (3-12)AP BP CP高级汽油规格3：-0.1x-0.1x+0.9xW0 (3-13)低铅汽油规格： APBPC'0.3x-0.7x+0.3xW0 (3-14)式(3-3)至(3-14,加上^(N0,i=AB,C；j=RP,L,就是这个问j题的线性规模模型。用单纯形法求出这个问题的解以后，决策人不但知道最有利的各种汽油数量，而且知道各种汽油的确切配方。例3多阶段投资问题某公司有200000元可用于投资，投资方案有以下5种，每种方案的投资额不受限制。方案A：5年内每年都可投资，在年初投资1元，2年后可收回1.2元；方案B：5年内每年都可投资，在年初投资1元，3年后可收回1.3元；方案C：只在第1年初有一次投资机会，每投资1元，4年后可收回1.4元；方案D：只在第2年初有一次投资机会，每投资1元，4年后可收回1.7元；方案E:只在第4年初有一次投资机会，每投资元，年后可收回1.4元。此外，每年年初若将1元资金存入银行，年末可收回1.06元。投资所得的收益及银行利息也可用于投资。要求建立线性规划模型，使公司在第5年末收回的资金最多。解和例2一样，若将投资及收益情况归纳成表3-2对建立数学模型，将有帮助。表中投资方案的下标表示投资年级。用F表示未投资完而存入银行的金额。在第4年，因有投资方案E，所以没有F4。此外，不考虑B4A5，B5,因这些投资收回时已过了5年的期限。表3-2中虚线的起点是当年初投资的金额，虚线的终点是当年初可用的金额（第1年初是20000（元），两者必须相等。这样，对第年至第5年初的资金情况，都可建立一个约束条件方程：第1年A+B+C+F=2000001111第2年A+B+D+F=1.06F2 2 2 2 1或A+B+D+F—1・06F=02 2 2 2 2表3-2年份（年初）12456I.2A1.3B1气1

F……1TO6F1A…2B…F……1TO6F1A…2B…2D…2F…21.06F2A31.2A21.3B21.2A31.06FA•…4B…41.4E4F-5I1.7D1.3B1.2A31.06F第3年A+B+F—1.2A-1.06F=03 3 3 1 2第4年A+E—1.3B—1.2A—1.06F=04 4 1 2 3第5年 F5—1.4C1—1.3B2—1.2^—1.4E4=0L还有非负约束A,B.，C，D.，E.，F.N0,jjjjjjj=1,…，5。目标函数是第6年初（即第5年末）收回的的资金最大;maxz=1.7D+1・3B+1・2A+1・06F2 3 4 5这个问题也可以用动态规划解决。例4城市间汽车运输问题现举例说明建立数学模型的技巧，为不使问题太大，我们举出下面被简化了的例题。某汽车运输公司经营A、B、C三个城市之间的货物运输业务，在任两个城市之间都有公路连通，货运量及每车利润如表3-5和表3-6所列。到站发站\^ABC到站发站\^ABCA150250B100200C500100每周货运量（车）表3-5到站发站\^ABCA150200B50300C100150每年利润（元）表3-6该公司有汽车250辆，每周每辆车最多在两城市间单程运行4次，由于技术上及业务上的原因，全部汽车每周末必须停在A城。汽车回空没有利润，也不计成本。要求建立最大利润的线性规划模型。解建立这个问题的数学模型，有两种不同的思路，从而有两种确定决策变量的方法，两个表面看来不同的线性规划模型。第一种方法是按照例6下料问题的方法，以采用某种方案的次数作为决策变量。第二种方法是用三下标变量。现分别叙述如下：题目中规定周初的汽车必须由A城开出，最多运行4个单程，周末必须返回A城，所以汽车运行路线可以有8个，设x为采用第j种行车路线的次数即j按此路线行车的汽车数，行车路线如表3-7所示。标号（j）行车路线标号（j）行车路线1A一B一A一C-A5A一C一A-B一A2A—B—C一A6A—C一B—A3A-B—C-B—A7A—C一B—C一A4A-B—A-B—A8A-C-A—C-A由于题止中规定空车不计成本，因此可能产生空车运行，再设:y=A-B间重车数，iy=A-C间重车数，y2二B-A间重车数，3y=B-C间重车数，4y=C-A间重车数，y5=C-B间重车数6目标函数为：maxz=150y+200y+50y+300y+100y+150y。1 2 3 4 5 6第一组约束条件方程是按8种行车路线开行的汽车数等于250（因空车不计成本，所以全部开出）28x=250j

j=1第二组约束条件方程是两地间运行的重车数小于或等于运量：y1^150七W2502ywiooy4W200y5W500yW10Q8第三组约束条件是两地间的重车数小于等于空重车总数:y〔Wx+x+x+2x+x，1 2 3 4 5y2Wx+x+x+x+2x，yv1」6g8□y3Wxx++++xx*+x+2xx+x+-x+2+2xx121，5326437548y有x+x+xx++4x1 25 36 74x+xy1 y+W3xxx~++2xx++<x++x2x++2x+x^++xx+2xx++xx。+2x1 12 53 64 7最后一组约束条件是非负及整数约束：xN0，x为整数，j=1,2，…，8，yjN0，yj为整数，k=1,2，…，8。kk这个线性规划模型有14个决策变量，13个约束条件方程（不包括非负及整数约束）。若城市数增多，要列举所有行车方案而不遗漏，费时费事，第三组约束条件方程也很易列错。因此，这个模型在题目规模较大时无实用价值。如果用三下标变量，就可克服上述缺点。现设：x=第i次从j地开往k地的空重车数：y=第i'次从j地到k地的重车数，ijk 一i=1,2,3,4；j=ABC；k=ABC根据题目所给条件，可以列出表3-8题目中规定的周初只能从A出发，周末全部返回心以及每周最多单程运行4次，都在表3-8中确定决策变量时考虑到了。目标函数是:

表3-8第1次第2次第3次第4次A—BAtCX1ab：3朋B―AB―C1ACAx3ACX3BAX4BAC―Ax2BCx3BCxC―Bx2CAX2cb3CAX3CB4CAmaxz=15y+15y+20y+20y +5y+5y+5y+30y1AB3AB1AC3AC2BA3BA4BA2BC30y+10y+10y+10y+15y+15y。 (3-183BC2CA3CA4CA2CB3CB第一组约束条件方程是第1,2,3次单程的重空车总数等于250辆(因空车不计成本，所以宁愿放空车也不停在原地不发，使问题简化一些第3次单程到达A的车不再走，所以第4单程车数小于等于25Qx+x二250，(3-181AB1ACx+x+x+x二250，(3-17)2BA2BC2CA2CBx+x+x+x+x+x=250(3-183AB3AC3BA3BC3CA 3CBx+x<250(3-194BA4CA第二组约束条件方程是每个单程从某地出发之车数等于上一个单程到达该地的车数：x+x二x，(3-202BA2BC1ABx+x二x，(3-21)2CA2CB1ACx+x二x+x，(3-22)3AB3AC2BA 2CAx+x二x，(3-23)3BA3BC2CBx+x二x，(3-243CA3CB2BCx=x+x，(3-25)4BA3AB3CBx二x+x。(3-284CA3AC3BC第三组约束条件方程是每次两地间重车数小于等于运量:yWx, (3-27)TOC\o"1-5"\h\z\o"CurrentDocument"yW250 (3-28ACvAW10O (3-29yBAyW200 (3-30BC\o"CurrentDocument"yW500 (3-3DCA\o"CurrentDocument"yW10Q (3-32CB第四组约束条件方程是两地间重车数等于空重车总数：y Wx +x , (3-33)AB 1AB 3ABTOC\o"1-5"\h\zy Wx +x , (3-34AC 1AC 3ACy Wx +x +x , (3-35BA 2BA 3BA 4BAy Wx +x , (3-38BC 2BC 3BCy Wx +x +x , (3-37)CA 2CA 3CA 4CAy Wx +x , (3-38CB 2CB 3CB第五组约束条件是非负和整数约束：xNO,x是整数，ijk ijktyNO,y是整数，jk jki=1,2,3,，4；j=AB,C；k=AB,Cx与y均为表3-7中所列的变量。因•为有式(3-16、3-2。和(3