数学建模：第五章 运筹及优化模型

1、1第五章 运筹与优化模型5.1 简单的运筹与优化模型 一、 线性规划模型 线性规划是运筹学的一个重要分支，它起源于工业生产组织管理的决策问题。在数学上它用来确定多变量线性函数在变量满足线性约束条件下的最优值；随着计算机的发展，出现了如单纯形法等有效算法，它在工农业、军事、交通运输、决策管理与规划等领域中有广泛的应用。 2 例1、某工厂制造A.B两种产品，制造A每吨需用煤9t，电力4kw，3个工作日；制造B每吨需用煤5t，电力5kw，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元，现工厂只有煤360t，电力200kw，工作日300个可以利用，问A、B两种产品各应生产多少吨才

2、能获利最大？解：设 ,（单位为吨）分别表示A、B产品的计划生产数； 1x2x f表示利润（单位千元） 则问题归结为如下线性规划问题：3目标函数 21127maxxxf约束条件 3605921 xx2005421 xx30010321xx. 0, 021xx其中( , )为决策向量， 1x2x满足约束条件的( , )称为可行决策。 1x2x 线性规划问题就是指目标函数为诸决策变量的线性函数，给定的条件可用诸决策变量的线性等式或不等式表示的决策问题。线性规划求解的有效方法是单纯形法（进一步了解可参考有关书籍），当然简单的问题也可用图解法。4如用图解法求解例1： 由约束条件决定的可行域如图阴影所示，

3、 目标函数的等值线向右上方移动时其值增大，在到达点 时f取得最大值； 2Q5当 =20, =24时，即产品A生产20t，产品B生产24t时，生产方案最优。 1x2x其最大利润为：7201224428千元例2：某两个煤厂 . ，每月进煤数量分别为60t和100t联合供应3个居民区 。3个居民区每月对煤的需求量依次分别为50t,70t,40t，煤厂 离3个居民区 的距离依次为10km,5km,6km，煤厂 离3个居民区 的距离依次分别为4km,8km,12km，问如何分配供煤量使得运输费（即tkm）达到最小？1A2A321,BBB321,BBB2A321,BBB1A6 解：设 表示 (i=1.2)

4、煤厂提供给 （j=1.2.3)居民区的煤量； ijxiAjBf表示总运输费此问题归结为： 23222113121112846510minxxxxxxfts.60131211xxx100232221xxx502111 xx702212 xx402313 xx, 3 , 2 , 1, 2 , 1, 0jixij7一般线性规划问题的数学表达式： nnxcxcxcf2211max(min) s.t 11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx8例3：生产组织与计划问题 设有m种资源，第i(i=1,2,m)种资源

5、的现存量为 ，现要生产n种产品，已知生产j(j=1,2,n)种产品时，每单位产品需要第i种资源量为 ，而每单位j种产品可得利润 ，问如何组织生产才能使利润最大？ ibijajc 解：用 表示生产第j(j=1,2,n)种产品的计划数， jx上述问题可归结为如下的数学问题： njjjxc1maxts.mibxainjjij2 . 11njxj2 . 109 二、整数规划模型对于线性规划： njxmibxaxcfjnjijijnjjj2 , 102 , 1min11 决策变量是连续变量，最优解可能是小数或分数。 10 但是在许多实际问题中，往往要求所得的解为整数，例如投资项目的选择、机器的台数、完成

6、工作的人数、装货的车数等，分数和小数的答案就没有现实意义了。 在现性规划中，若限制 (j=1,2,n)是非负整数，则这种线性规划问题称为整数规划问题。 jx为整数为整数如如212112121,0,115851215maxxxxxxxxxxf11 例4：分配问题 假设某工厂用m台机床加工n种零件。在一个生产周期内，第i(i=1,2,m)台机床只能工作 个机时，而第j(j=1,2,n)种零件必须完成 个，又第i台机床加工第j种零件所需机时和成本分别为 （机时个）和 （元个）。问在这个生产周期内怎样安排各机床的生产任务，才能使得既完成加工任务，又使总的加工成本最少？ iajbijtijc 解：在一个

7、生产周期内，假设第i台机床加工第j种零件的个数为 。 ijx由于 是零件个数，因此 必须是非负整数， ijxijx12本问题的数学模型为： minjijijxc11mints.injijijaxt1mi2 , 1jmiijbx 1nj2 , 1 为为非非负负整整数数ijx13三、非线性规划模型非线性规划模型的一般形式为： )2(., 2 , 10)(.miXgtsi)3(., 2 , 10)(ljXhiDX 为为可可行行集集其其中中nTnRDxxxX,),(21 f(X)为目标函数， (2)、(3)为约束条件， (2)为不等式约束，(3)为等式约束；若只有(1)称为无约束问题。 ) 1 ()(

8、minXf1432321213215),(minxxxxxxxxf如如0516223121xxxxx010312221xxxx15例5：容器的设计问题 某公司专门生产储藏用容器，定货合同要求该公司制造一种敞口的长方体容器，容积恰好为12立方米，该容器的底必须为正方形，容器总重量不超过68公斤。已知用作容器四壁的材料为每平方米10 元，重3公斤；用作容器底的材料每平方米20元，重2公斤。试问制造该容器所需的最小费用是多少？ 模型建立 设该容器底边长和高分别为 米、 米， 1x2x则问题的数学模型为 21212040)(minxxxXf（容器的费用） . 0, 0,68212,12. .21212

9、1221xxxxxxxts（容器重量）（容器重量）（容器体积）（容器体积）16一般来说，非线性规划模型的求解要比线性规划模型求解困难得多，虽然现在已经发展了许多非线性规划的算法，但到目前为止，还不象线性规划那样有通用的单纯形算法，而是各种算法都有自己特定的适用范围，如求解法有：最速下降法、牛顿法、可行方向法、惩罚函数法等。尽管如此，非线性规划的实际应用还是相当广泛的。17 5.2 实际问题中的优化模型一、投资策略 某部门现有资金10万元，五年内有以下投资项目供选择： 项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%； 项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额

10、为4万元； 项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元； 项目D，每年初投资，年末收回本金且获利6%。问如何确定投资策略使第五年末本息总额最大。18问题的目标函数是第五年末的本息总额， 决策变量是每年初各个项目的投资额， 约束条件是每年初拥有的资金。 用ijx表示第i年初（5 , , 2 , 1i）项目4 , 3 , 2 , 1(jj分别代表A,B,C,D)的投资额， 根据所给条件只有下表1列出的ijx才是需要求解的。 项目 年份 A B C D 1 2 3 4 5 11x21x31x41x32x23x14x24x34x44x54x19 因为项目D 每年初可以投资，

11、且年末能收回本息，所以每年初都应把资金全部投出去， 项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%； 项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元； 项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元； 项目D，每年初投资，年末收回本金且获利6%。由此可得如下的约束条件： 第一年初： 101411 xx第二年初： 1424232106. 1xxxx第三年初 241134323106. 115. 1xxxxx第四年初： 3421444106. 115. 1xxxx第五年初： 44315406. 115. 1xxx项目B,C对投资额的限

12、制： 3, 42332xx20项目A,从第一年到第四年每年初投资，次年末收回本金且获利15%； 项目B，第三年初投资，第五年末收回本金且获利25%，最大投资额为4万元； 项目C，第二年初投资，第五年末收回本金且获利40%，最大投资额为3万元； 项目D，每年初投资，年末收回本金且获利6%。 每项投资应为非负的： 0ijx第五年末本息总额为5432234106. 125. 140. 115. 1xxxxz将上条件等价变形如1424232106. 1xxxx006. 124232114xxxx21由此得投资问题的线性规划模型如下：5432234106. 125. 140. 115. 1maxxxxx

13、zs.t. 101411 xx006. 124232114xxxx006. 115.xxxx006. 115, 144413421xxxx006. 115. 1544431xxx3, 42332xx0ijx22求解得4008. 0, 0,000. 3,5436. 3,1732. 6,8268. 3312423211411xxxxxx4609. 0, 0,0752. 4, 0,0000. 45444413432xxxxx3750.14z 即第1年项目A,D分别投资3.8268和6.1732(万元)；第2年项目A,C分别投资3.5436和3(万元)；第3年项目A,B分别投

14、资0.4008和4(万元)；第4年项目A投资4.0752(万元)；第5年项目D投资0.4609(万元)；5年后总资金 14。375万元，即盈利43.75%.23二、货机装运问题 某架货机有三个货舱：前仓、中仓、后仓。三个货舱所能装载的货物的最大重量和体积都有限制，如表3所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容许重量成比例。前仓中仓后仓重量限制（吨）10168体积限制（米3）680087005300 现有四类货物供该货机本次飞行装运，其有关信息如表4，最后一列指装运后所获得的利润。24重量（吨）空间（米3/吨）利润（元/吨）货物1184803100货物21565

15、03800货物3235803500货物4123902850应如何安排装运，使该货机本次飞行获利最大？模型假设 问题中没有对货物装运提出其它要求，我们可作如下假设： 1）每种货物可以分割到任意小；2）每种货物可以在一个或多个货舱中任意分布；253）多种货物可以混装，并保证不留空隙。模型建立决策变量： ijx表示第i种货物装入第j个货舱的重量（吨）， 货舱j=1,2,3分别表示前仓、中仓、后仓。 决策目标是最大化总利润，即)(3800)(3100232221131211xxxxxxZMax)(2850)(3500434241333231xxxxxx)13(约束条件包括以下4个方面：1）从装载的四种

16、货物的总重量约束，即)14(18131211xxx26)15(15232221xxx)16(23333231xxx)17(12434241xxx2）三个货舱的重量限制，即)18(1041312111xxxx)19(1642322212xxxx)20(843332313xxxx3）三个货舱的空间限制，即)21(680039058065048041312111xxxx)22(870039058065048042322212xxxx)23(530039058065048043332313xxxx274）三个货舱装入重量的平衡约束，即)24(81610433323134232221241312111x

17、xxxxxxxxxxx模型求解将以上模型输入LINDO求解，可以得到：28OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000000X12 0.000000 57.894737X13 0.000000 400.000000X21 10.000000 0.000000X22 0.000000 239.473679X23 5.000000 0.000000X31 0.000000 0.000000X32 12.947369 0.000000X33 3.000000 0.000000X41

18、 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000实际上，不妨将所得最优解作四舍五入， 29结果为 货物2装入前仓10吨、装入后仓5吨； 货物3装入中仓13吨、装入后仓3吨； 货物4装入中仓3吨， 最大利润约121516元。 评注 初步看来，本例与运输问题类似，似乎可以把4种货物看成4个供应点，3个货舱看成3个需求点（或者反过来，把货舱看成供应点，货物看成需求点）。但是，这里对供需量的限制包括两个方面：重量限制和空间限制，且有装载均匀要求，因此它只能看成是运输问题的一种变形和扩展。 30 三、原油采购与加工 问题 某

19、公司用两种原油（A和B）混合加工成两种汽油（甲和乙）。甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元。该公司现有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A。原油A的市场价为：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨。该公司应如何安排原油的采购和加工？31问题分析 安排原油采购、加工的目标只能是利润最大， 题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收

20、入与购买原油A的支出之差。 这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在。模型建立 设原油A的购买量为x， 采购的支出C(x)可表为如下的分段线性函数（价格为千元/吨）：)9()15001000(63000)1000500(81000)5000(10)(xxxxxxxc32设原油A用于生产甲、乙两种汽油的数量分别为，和1211xx 设原油B用于生产甲、乙两种汽油的数量分别为，和2221xx则总的收入为 )(6 . 5)(8 . 422122111xxxx于是本例的目标函数利润为）（ 10)()(6 . 5)(8 . 4

21、22122111xcxxxxzMax 约束条件包括加工两种汽油用的原油A、原油B库存量的限制，和原油A购买量的限制，以及两种汽油含原油A的比例限制，它们表示为）（ 115001211xxx）（ 1210002221 xx）（ 131500 x33）（ 145 . 0211111 xxx）（ 156 . 0221212 xxx）（ 160,22211211xxxxx 由于（9）式中的C(x)不是线性函数，（9）（16）给出的是一个非线性规则。而且，对于这样用分段函数定义的C(x)，一般的非线性规划软件也难以输入和求解。 能不能想办法将该模型化简，从而用现成的软件求解呢？ 34模型求解 下面介绍3

22、种解法。 第1种解法 一个自然的想法是将原油A的采购量x分解为三个量， 321,xxx 分别表示以价格10千元/吨、8千元/吨、6千元/吨采购的原油A的吨数， 总支出为 3216810)(xxxxc)17(321xxxx这时目标函数（10）变为线性函数：)6810()(6 . 5)(8 . 432122122111xxxxxxxzMax)18(35应该注意到，只有当以10千元/吨的价格购买5001x吨时，才能以8千元/吨的价格购买)0(22xx这个条件可以表示为)19(0)500(21xx同理，只有当以8千元/吨的价格购买5002x吨时，才能以6千元/吨的价格购买)0(33xx，于是)20(0

23、)500(32xx321,xxx的取值范围是)21(500,0321xxx 由于有非线性约束（19），（20），（11）（21）构成非线性规划模型。将该模型输入LINGO软件如下： 36Model：Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*02-6*x3；x11+x12x+500；x21+x220；0.4*x12-0.6*x220；x=x1+x2+x3；(x1-500)*x2=0；(x2-500)*x3=0；x1500；x2500；x30；x110；x120；x210；x220；x10；x20；x30；end37 注：程序以“Model：”开始，每

24、行最后加“；”，并以“end”结束；非负约束可以省略；乘号*不能省略，式中可有括号，右端可有数学符号。 将文件存储并命名后，选择菜单“Solve”，运行该程序得到：Objective value: 4800.000 Variable Value Reduced Cost X11 500.0000 0.0000000E+00 X21 500.0000 0.0000000E+00 X12 0.0000000E+00 0.0000000E+00 X22 0.0000000E+00 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.0

25、00000 X3 0.0000000E+00 6.000000 X 0.0000000E+00 0.0000000E+0038 最优解是用库存的500吨原油A、500吨原油B生产1000吨汽油甲，不购买新的原油A，利润为4800000元。 但是LINGO得到的以上结果只是一个局部最优解，还能得到更好的解吗？第2种解法 引入0-1变量将（19）和（20）转化为线性约束。 1, 1, 1321yyy令 分别表示以10千元/吨、8千元/吨、6千元/吨的价格采购原油A， 则约束（19）和（20） 可以替换为)19(0)500(21xx)20(0)500(32xx39）（ 22500500112yxy）

26、（ 23500500223yxy）（ 2450033yx ）（或2510,321yyy（11）（18），（21）（25）构成整数规划模型， 将它输入LINGO软件如下： 40Max 4.8x11+4.8x21+5.6x12+5.6x22-10 x1-8x2-6x3Stx-x1-x2-x3=0 x11+x12-x500 x21+x2200.4x12-0.6x220 x1-500y10 x2-500y20 x3-500y30 x2-500y30endint y1int y2int y341运行该程序得到：OBJECTIVE FUNCTION VALUE1) 5000.000VAIABLE VALU

27、E REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.00000042 最优解是购买1000吨原油A，与库存的500吨原油A和100

28、0吨原油B一起，共生产2500吨汽油乙，利润为5000000元，高于非线性规划模型得到的结果。第3种解法 直接处理分段线性函数C(x)， )9()15001000(63000)1000500(81000)5000(10)(xxxxxxxc（9）式表示的C(x)如图2。43记x轴上的分点为1500,1000,500, 04321bbbb。 当x在第1个小区间,21bb 0, 1,21212211zzzzbzbzx记因为C(x)在,21bb是线性的， 所以 )()()(2211bczbczxc44同样，当x在第2个小区间,32bb时， 0, 1,32323322zzzzbzbzx)()()(332

29、2bczbczxc当x在第3个小区间,43bb时， 0, 1,43434433zzzzbzbzx)()()(4433bczbczxc为了表示x在哪个小区间，引入0-1变量)3, 2, 1( kyk， 当x在第k个小区间时，1ky 否则，0ky。 这样，3214321,yyyzzzz应满足45）（ 26,3432321211yzyyzyyzyz）（ 27)4, 3, 2, 1(0, 14321kzzzzzk）（或2810, 1321321yyyyyy此时x和C(x)可以统一地表示为）（ 291500100050043244332211zzzbzbzbzbzx)()()()()(44332211b

30、czbczbczbczxc）（ 301200090005000432zzz （ 10）（18），（26）（30）也构成一个整数规划模型， 将它输入LINDO软件求解，得到的结果与第2种解法相同。46评注 这个问题的关键是处理分段线性函数， 第3种解法更具一般性，其做法如下： 设一个n段线性函数f(x)的分点为11nnbbb引入kz将x和f(x)表示为11nkkkbzx11)()(nkkkbfzxfkz和0-1变量ky满足nnnnnyzyyzyyzyz1121211,10, 121或knyyyy) 1, 2, 1(0, 1121nkzzzzkn47 生产中常会遇到通过切割、剪裁、冲压等手段，将原

31、材料加工成所需尺寸这种工艺过程，称为原料下料问题。按照进一步的工艺要求，确定下料方案，使用料最省，或利润最大，是典型的优化问题。下面通过两个实例讨论用数学规划模型解决这类问题的方法。48四、钢管下料问题 某钢管零售商从钢管厂进货，将钢管按照顾客的要求切割后售出，从钢管厂进货时得到的原料钢管都是19m。（1）现有一客户需要50根4 m、20根6 m和15根8 m的钢管，应如何下料最节省？（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5 m的钢管。应如何下

32、料最节省。问题（1）的求解问题分析 首先，应当确定哪些切割模式是可行的。 49 所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。 例如：我们可以将19 m的钢管切割成3根4 m的钢管，余料为7 m；或者将19 m的钢管切割成4 m、6 m和8 m的钢管各1根，余料为1 m。 显然，可行的切割模式是很多的。其次，应当确定哪些切割模式是合理的。 通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。 例如：将19 m的钢管切割成3根4 m的钢管，余料为7 m，可进一步将7m的余料切割成4m 钢管（余料为3 m），或者将7 m的余料切割成6 m钢管（余料为1 m

33、）。 50 在这种合理性假设下，切割模式一共有7种，如表9所示。4 m钢管根数6 m钢管根数8 m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023 问题化为在满足客户需要的条件下，按照哪些种合理的模式，切割多少根原料钢管，最为节省。 而所谓节省，可以有两种标准： 51一是切割后剩余的总余料量最小， 二是切割原料钢管的总根数最小。 下面将对这两个目标分别讨论。模型建立决策变量 ix表示按照第i种模式（7 , 2, 1i ）切割的原料钢管的根数，显然它们应当是非负整数。 决策目标 以切割后剩余的总余料量最小为目标，则由表9可得 )

34、 1 (333376543211xxxxxxxZMin以切割原料钢管的总根数最少为目标，则有)2(76543212xxxxxxxZMin524 m钢管根数6 m钢管根数8 m钢管根数余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023约束条件 为满足客户的需求，按照表9应有 )3(5023454321xxxxx)4(20326542xxxx)5(152753xxx模型求解53 1将（1），（3），（4），（5）构成的整数线性规划模型（加上整数约束）输入LINDO如下： Min 3x1+x2+3x3+3x4+x5+x6+3x7s.t. 4x

35、1+3x2+2x3+x4+x5=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7求解可以得到最优解如下：54OBJECTIVE FUNCTION VALUE1) 27.00000VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 即按照模式2切割12根原料钢管，按照模

36、式5切割15根原料钢管，共27根，总余料量为27m。 显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和5的余料为1 m），这会导致切割原料钢管的总根数较多。55 2将（2）（5）构成的整数线性规划模型（加上整数约束）输入LINDO求解，可以得到最优解如下： OBJECTIVE FUNCTION VALUE1） 25.00000VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.0000

37、00 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 即按照模式2切割15根原料钢管、按模式5切割5根、按模式7切割5根、共25根，可算出总余料量为35 m。 与上面得到的结果相比，总余料量增加了8 m，但是所用的原料钢管的总根数减少了2根。 在余料没有用途情况下，通常选择总根数最小为目标。 56问题（2）的求解问题（2）：零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割模式不能超过3种。此外，该客户除需要（1）中的三种钢管外，还需要10根5 m的钢管。应如何下料最节省。问题

38、分析 按照（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需求的钢管规格增加到4种，所以枚举法的工作量较大。 下面介绍的整数非线性规划模型，可以同时确定切割模式和切割计划，是带有普遍性的方法。 57 同（1）类似，一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸（本题中为4 m），切割计划中只使用合理的切割模式，而由于本题中参数都是整数，所以合理的切割模式的余量不能大于3 m。 此外，这里我们仅选择总根数最小为目标进行求解。模型建立决策变量 由于不同切割模式不能超过3种， 可以用ix表示按照第i种模式（3, 2, 1i ）切割的原料钢管的根数，显然它们应当是非负

39、整数。 58 设所使用的第i种切割模式下每根原料钢管生产4 m，5 m，6 m和8 m的钢管数量分别为iiiirrrr4321,（非负整数）。 决策目标 切割原料钢管的总根数最小，目标为)6(321xxxMin约束条件 为满足客户的需求，应有)7(50313212111xrxrxr)8(10323222121xrxrxr)9(20333232131xrxrxr)10rxrxr59 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16 m（余量不能大于3 m），于是)11(1986541641312111rrrr)12(198654164

40、2322212rrrr)13(1986541643332313rrrr模型求解 在（7）（10）式中出现决策变量的乘积，是一个整数非线性规划模型，虽然用LINGO软件可以直接求解，但我们发现运行很长时间也难以得到最优解。 为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。 60 例如，由于3种切割模式的排列顺序是无关紧要的，所以不妨增加以下约束)14(321xxx 又例如，我们注意到所需原料钢管的总根数有着明显的上界和下界。 首先，无论如何，原料钢管的总根数不可能少于19158206105504根即至少需26根。 其次，考虑一种非常特殊的生产计划： 第一种切割模式下只生产

41、4m钢管，一根原料钢管切割成4根4 m钢管，为满足50根4 m钢管的需求，需要13根原料钢管； 61 第二种切割模式下只生产5 m、6 m钢管，一根原料钢管切割成1根5 m钢管和2根6 m钢管，为满足10根5 m和20根6 m钢管的需求，需要10根原料钢管； 第三种切割模式下只生产8 m钢管，一根原料钢管切割成2根8 m钢管，为满足15根8 m钢管的需求，需要8根原料钢管。 于是满足要求的这种生产计划共需13+10+8=31根原料钢管，这就得到了最优解的一个上界。 所以可增加以下约束)15(3126321xxx将（6）（15）构成的模型输入LINGO如下：62model：min=x1+x2+x

42、3；x1*r11+x2*r12+x3*r13=50；x1*r21+x2*r22+x3*r23=10；x1*r31+x2*r32+x3*r33=20；x1*r41+x2*r42+x3*r43=15；4*r11+5*r21+6*r31+8*r41=19；4*r12+5*r22+6*r32+8*r42=19；4*r13+5*r23+6*r33+8*r43=16；4*r12+5*r22+6*r32+8*r42=16；4*r13+5*r23+6*r33+8*r43=16；x1+x2+x3=26；x1+x2+x3=x2；x2=x3；gin(x1) ；gin(x2) ；gin(x3) ；gin(r11) ；

43、gin(r12) ；gin(r13) ；gin(r21) ；gin(r22) ；gin(r23) ；gin(r31) ；gin(r32) ；gin(r33) ；gin(r41) ；gin(r42) ；gin(r43) ；end63 注：LINGO软件用于求解非线性规划（包括含有整数变量的），输入总是以“model：”开始，以“end”结束；中间的语句必须以“；”分开。约束中“gin(x1)”表示x1为整数，其他类似（如果要表示x1为0-1整数，应该用“int(x1)”）。在LINGO8.0版本中，缺省设置假定所有变量非负，所以上面的输入中没有关于变量非负的显式约束。经过运行（一般需要几分钟），

44、得到输出如下：64Local optimal solution found at iteration： 12211Objective value： 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.00000 1.000000 R11 3.00000 0.000000 R12 2.00000 0.000000 R21 0.00000 0.000000 R22 1.00000 0.000000 R31 1.00000 0.000000 R32 1.00000 0.000000 R

45、33 0.00000 0.000000 R41 0.00000 0.000000 R42 0.00000 0.000000 R43 2.00000 0.00000065 即按照模式1，2，3分别切割10，10，8根原料钢管，使用原料钢管总根数为28根， 第一种切割模式下一根原料钢管切割成3根4m钢管和1根6 m钢管； 第二种切割模式下一根原料钢管切割成2根4 m钢管、1根5 m钢管和1根6 m钢管； 第三种切割模式下一根原料钢管切割成2根8 m钢管。66五、 易拉罐下料 问题 某公司采用一套冲压设备生产一种罐装饮料的易拉罐，这种易拉罐是用镀锡板冲压制成的。易拉罐为圆柱形，包括罐身、上盖和下底，

46、罐身高10cm，上盖和下底的直径均为5cm。该公司使用两种不同规格的镀锡板原料：规格1的镀锡板为正方形，边长24cm；规格2的镀锡板为长方形，长、宽分别为32cm和28cm。由于生产设备和生产工艺的限制，对于规格1的镀锡板原料，只可以按照图3中的模式1、模式2或模式3进行冲压；对于规格2的镀锡板原料只能按照模式4进行冲压。使用模式1、模式2、模式3、模式4进行每次冲压所需要的时间分别为1.5s、2s、1s、3s。6768 该工厂每周工作40小时，每周可供使用的规格1、规格2的镀锡板原料分别为5万张和2万张。目前每只易拉罐的利润为0.10元，原料余料损失为0.001元/厘米2（如果周末有罐身、上

47、盖或下底不能配套组装成易拉罐出售，也看作是原料余料损失）。 问工厂应如何安排每周的生产？问题分析 与钢管下料问题不同的是，这里的切割模式已经确定，只需计算各种模式下的余料损失。 已知上盖和下底的直径d=5cm， 可得其面积为6 .1942 dscm2， 周长为7 .15dLcm； 69已知罐身高h=10cm，可得其面积为 21 .157 cmLhS罐于是模式1下的余料损失为229 .2221024cmSs罐 同理计算其它模式下的余料损失，并可将4种冲压模式的特征归纳，如表10。罐身个数底、盖个数余料损失（cm2）冲压时间（s）模式1110222.61.5模式224183.32模式3016261

48、.81模式445169.5370 问题的目标显然应是易拉罐的利润扣除原料余料损失后的净利润最大，约束条件除每周工作时间和原料数量外，还要考虑罐身和底、盖的配套组装。模型建立决策变量 ix表示按照第i种模式的冲压次数（4, 3, 2, 1i）， 1y表示一周生产的易拉罐个数。 为计算不能配套组装的罐身和底、盖造成的原料损失， 2y表示不配套的罐身个数， 3y表示不配套的底、盖个数。 虽然实际上这些量应该是整数。但是由于生产量相当大，可以把它们看成是实数，从而用线性规划模型处理。 71决策目标 假设每周生产的易拉罐能够全部售出，公司每周的销售利润是11 . 0 y。 原料余料损失包括两部分： 4种

49、冲压模式下的余料损失和不配套的罐身和底、盖造成的原料损失。 按照前面的计算及表10的结果， 罐身个数底、盖个数余料损失（cm2）冲压时间（s）模式1110222.61.5模式224183.32模式3016261.81模式445169.53总损失为 72总损失为 )6 .191 .1575 .1698 .2613 .1836 .222(001. 0324321yyxxxx决策目标为 )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax约束条件时间约束： 每周工作时间不超过40小时=144000s，由表2最后一列得）（1

50、7144000325 . 14321xxxx原料约束： 每周可供使用的规格1、规格2的镀锡板原料分别为50000张和20000张， ）（1673）（ 1850000321xxx）（ 19200004x配套约束： 由表2一周生产的罐身个数为42142xxx一周生产的底、盖个数为4321516410 xxxx， 因为应尽可能将它们配套组装成易拉罐销售。 ）（202/ )516410(,42min43214211xxxxxxxy这时不配套的罐身个数，和不配套的底、盖个数应为）（214214212yxxxy）（222516410143213yxxxxy（16）（22）就是我们得到的模型， 74）（20

51、2/ )516410(,42min43214211xxxxxxxy 其中（20）是一个非线性关系，不易直接处理，但是它可以等价为以下两个线性不等式）（23424211xxxy）（242)516410(43211xxxxy模型求解 将模型（16）（19）和（21）（24）输入LINDO，求解时LINDO发出警告信息： 模型中数据之间的数量级差别太大，建议进行预处理，缩小数据之间的差别。 实际上，约束（17）（19）中右端项的数值过大（与左端的系数相比较），LINDO在计算中容易中产生比较大的误差，所以出现此警告信息。 75 为了解决这一问题，可以将所有决策变量扩大10000倍（相当于iiyx、以

52、万次为单位）。 此时，目标（16）可以保持不变（记住得到的结果单位为万元就可以了） )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax）（ 16而约束（17）（19）改为）（254 .14325 . 14321xxxx）（265321xxx）（2724x将模型（16）和（21）（27）输入LINDO求解得到：76OBJECTIVE FUNCTION VALUE1) 0.4298337VARIABLE VALUE REDUCED COSTY1 16.025000 0.000000X1 0.000000 0.00005

53、0X2 4.012500 0.000000X3 0.375000 0.000000X4 2.000000 0.000000Y2 0.000000 0.223331Y3 0.000000 0.036484 即模式1不使用，模式2使用40125次，模式3使用3750次，模式4使用20000次，可生产易拉罐160250个，罐身和底、盖均无剩余，净利润为4298元。77 评注 下料问题的建模主要有两部分组成，一是确定下料模式，二是构造优化模型。确定下料模式尚无通用的方法，对于钢管下料这样的一维问题，当需要下料的规格不太多时，可以枚举出下料模式，建立整数线必规划模型；否则就要构造整数非线性规划模型，而这

54、种模型求解比较困难，本节介绍的增加约束条件的方法是将原来的可行域“割去”一部分，但要保证剩下的可行域中仍存在原问题的最优解。而像易拉罐下料这样的二维问题，就要复杂多了，读者不妨试一下，看看还有没有比图3给出的更好的模式。至于构造优化模型，则要根据问题的要求和限制具体处理，其中应特别注意配套组装的情况。78六：平板车的优化装载（MCM88B) 问题：有7种规格的包装箱要装到两辆平板车上去，包装箱的宽和高是一样的，但厚度t及重量w是不同的，下表给出了每种包装箱的厚度、重量以及数量7654321ccccccc包包装装箱箱类类型型t（厘米） 48 52 61 72 48 52 64w（吨） 2 3 1

55、 0.5 4 2 1 件数 8 7 9 6 6 4 8 每辆平板车有10.2米长的地方可用来装包装箱（象面包片那样），载重为40吨。 79 由于当地货运的限制，对, ,类的包装箱的总数有一个特别的限制： 5c6c7c 这类箱子所占的空间（厚度）不能超过302.7厘米，试把包装箱装到平板车上去，使得浪费的空间最小。 解：设 表示装到平板车j(j=1,2)上的 型包装箱的个数(1i7)； ijxic表示类型为 的包装箱的件数； iNic表示类型为 的包装箱的重量； iWic表示类型为 的包装箱的厚度；itic S表示剩余空间。 所以使平板车上剩下的空间最小转化为如下整数规划模型： 80717121

56、)1020()1020(miniiiiiixtxtS7121)(2040iiiixxt为整数，为整数，ijijxxts, 0.7111020iiixt（平板车1的长度限制）7121020iiixt（平板车2的长度限制） 71140000iiixw（平板车1的载重量限制）8171240000iiixw（平板车2的载重量限制） iiiNxx21（ 型包装箱的件数限制） ic7 .302)()()(727176261652515xxtxxtxxt（对三种型号 箱长度的特别限制） 765,ccc思考：上面的限制是否可理解为一辆平板车的限制？目前，求解整数规划模型常用方法有： (1)割平面法； (2)分

57、枝界限法。它们都是建立在线性规划求解的单纯形法基础上的。 82 如上例，用分枝定界法即可得35个不同的最优解，使没有利用的空间为0.6cm。 下面给出几组最优解： 1 2 3 4 5 6 7 1 2 3 4 5 6 7 4 2 9 1 2 0 0 4 5 0 5 1 3 0 4 2 5 3 3 1 0 4 5 4 3 0 2 0 车1 车2 4 3 5 3 3 0 0 4 4 4 3 0 3 083七：一个飞行管理问题（95全国数学建模竞赛A题） 问题：在约10000米高空的某边长160公里的正方形区域内，经常有若干架飞机作水平飞行，区域内每架飞机的位置和速度向量均由计算机记录其数据，以便进行

58、飞行管理。当一架欲进入该区域的飞机到达区域边缘时，记录其数据后，要立即计算并判断是否会与区域内的飞机发生碰撞。如果会碰撞，则应计算如何调整各架（包括新进入的）飞机飞行的方向角，以避免碰撞。现假定条件如下：1)不碰撞的标准为任意两架飞机的距离大于8公里； 2)飞机飞行方向角调整幅度不超过30度； 3)所有飞机飞行速度均为每小时800公里； 845)最多需考虑6架飞机； 6)不必考虑飞机离开此区域后的状况。 请你对这个避免碰撞的飞行管理问题建立数学模型。列出计算步骤，用以下数据进行计算（方向角误差不超过0.01度）。要求飞机飞行方向角调整的幅度尽量小。 设该区域4个顶点的坐标为 (0,0),(16

59、0,0),(160,160),(0,160) 记录数据为： 4)进入该区域飞机在到达区域边缘时，与区域内飞机的距离应在60公里以上； 85飞机编号 横坐标X 纵坐标Y 方向角（度） 1 130 140 243 2 85 85 236 3 150 155 220.5 4 145 50 139 5 130 150 230 新进入 0 0 52注：方向角指飞行方向与X轴正向的夹角。试根据实际应用背景对你的模型进行平价与推广。本问题可归结为非线性规划模型求解： 86设六架飞机在调整前的方向角为 ， i 调整后的方向角为 iii (i=1,2,6) 任意两架飞机在区域内的最短距离为 ， ),(jiijd

60、 则问题的非线性规划模型如下 61minii 8),(jjiiijd jiji6,1030i 注：也可用 或 作为目标 261ii ii 61max87 5.3 动态规划模型例8：最短线路问题0A6A 问题：现选择一条从 到 的铺管线路，使总距离最短？ 若用穷举法要算23222148种不同线路，比较这48种结果即可得出，但当段数增加，且各段选择也增加时，穷举法将变得非常庞大，以至利用计算机都十分困难。 88下面用动态规划的方法计算最短线路问题的特性： 如果最短线路在第k站通过点 ，则这一线路在由 出发到达终点的那一部分线路，对于从 点到达终点的所有可能选择的不同线路来说，必定也是距离最短的。（