第六章 运筹与优化模型

1、1第六章 运筹与优化模型6.1 简单的运筹与优化模型 一、 线性规划模型 线性规划是运筹学的一个重要分支，它起源于工业生产组织管理的决策问题。在数学上它用来确定多变量线性函数在变量满足线性约束条件下的最优值；随着计算机的发展，出现了如单纯形法等有效算法，它在工农业、军事、交通运输、决策管理与规划等领域中有广泛的应用。 例例 1 1 生产计划问题生产计划问题假设某厂计划生产甲、乙两种产品，这两种产品都要分别在A，B，C三种不同设备上加工按工艺资料规定：生产每件甲产品需占用设备的小时数分别为2，l，4；生产每件乙产品需占用设备的小时数分别为2，2，0. 已知各设备计划期内用于生产这两种产品的能力(

2、小时数)分别为12，8，16；又知每生产一件甲产品，该厂会获得利润2元，每生产一件乙产品，该厂能获利润3元，问该厂应安排生产两种产品各多少件才能使总的利润收入为最大?解解 (1)明确决策变量 工厂需要确定的是甲、乙两种产品的计划生产量，设x1, x2分别为甲、乙两种产品的计划生产量，总的利润为z (2)明确约束条件因设备A在计划期内有效时间为12小时，不允许超过 故有 12 2212xx对设备B，C也可列出类似的不等式12 28xx14 16x 此外产品的产量 12,x x只能取非负值，即 1x0 2x0 这种限制称为变量的非负约束条件(3)明确目标 工厂的目标是在各种设备能力允许的条件下，使

3、总利润收入 1223zxx为最大 综合起来，该问题的数学模型为：求一组变量 12,x x的值在满足约束条件 的情况下，1212112221228 4 16x ,0 xxxxxx1223zxx 为最大 使利润例例 运输问题运输问题 设有三个地方 l23A ,A ,A生产某种物资 简称为产地) (四个地方 l234B ,B ,B ,B需要该种物资 简称为销地) 产地的产量和销地的销量以及问如何组织物资的运输，才能在满足供需的条件下使总的运费最少产地到销地的单位运价表见表1(表1产销运输表 例例 3 合理下料问题合理下料问题(后面详述其解法后面详述其解法) 某工厂生产某一种型号的机床，每台机床上需要

4、2.9m，2.1m ，1.5m的轴分别为一根、二根、一根，这些轴需用同一种圆钢制作，圆钢的长度为7.4m，如果要生产100台机床，问应如何安排下料，才能使用料最省?7 例4、某工厂制造A.B两种产品，制造A每吨需用煤9t，电力4kw，3个工作日；制造B每吨需用煤5t，电力5kw，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元，现工厂只有煤360t，电力200kw，工作日300个可以利用，问A、B两种产品各应生产多少吨才能获利最大？解：设 ,（单位为吨）分别表示A、B产品的计划生产数； 1x2x f 表示利润（单位千元） 则问题归结为如下线性规划问题：8目标函数 21127

5、maxxxf约束条件 3605921 xx2005421 xx30010321xx. 0, 021xx 其中( , )为决策向量， 1x2x满足约束条件的( , )称为可行决策。 1x2x 线性规划问题就是指目标函数为诸决策变量的线性函数，给定的条件可用诸决策变量的线性等式或不等式表示的决策问题。线性规划求解的有效方法是单纯形法（进一步了解可参考有关书籍），当然简单的问题也可用图解法。 线性规划的图解法(解的几何表示)： 对于只有两个决策变量的线性规划问题，可以二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。 图解法求解线性规划问题的步骤如下： (1)建立直角坐标系： 分别取决策变量

6、x1 ,x2 为坐标向量。 （2）绘制可行域： 对每个约束（包括非负约束）条件，作出其约束半平面（不等式）或约束直线（等式）。 各半平面与直线交出来的区域若存在，其中的点为此线性规划的可行解。称这个区域为可行集或可行域。然后进行下步。否则若交为空，那么该线性规划问题无可行解。 （3）绘制目标函数等值线，并移动求解： 目标函数随着取值不同，为一族相互平行的直线。 首先，任意给定目标函数一个值，可作出一条目标函数的等值线（直线）； 然后，确定该直线平移使函数值增加的方向； 最后，依照目标的要求平移此直线。 结果 若目标函数等值线能够移动到既与可行域有交点又达到最优的位置，此目标函数等值线与可行域的

7、交点即最优解（一个或多个），此目标函数的值即最优值。 否则，目标函数等值线与可行域将交于无穷远处，此时称无有限最优解。 Max z = 1500 x1 + 2500 x2 s.t. 3x1+ 2x2 65 (A) 2x1+ x2 40 (B) 3x2 75 (C) x1 , x2 0 (D, E)例题作图（例题作图（1 1）按照图解法的步骤： （1）以决策变量x1 ，x2 为坐标向量作平面直角坐标系； （2 2）对每个约束（包括非负约束）条件）对每个约束（包括非负约束）条件作出直线（作出直线（A A、B B、C C、D D、E E），），并通过判断并通过判断确定不等式所决定的半平面。确定不等式

8、所决定的半平面。 各约束半平面交出来的区域即可行集或各约束半平面交出来的区域即可行集或可行域如下图阴影所示。可行域如下图阴影所示。 例题作图（例题作图（2 2） 第2步图示(1) 分别作出各约束半平面X2 0 x1 03x2 753x1+ 2x2 65 2x1+ x2 40 例题作图（例题作图（3 3） 第2步图示(2) 各约束半平面的交可行域 （3）任意给定目标函数一个值（例如37500）作一条目标函数的等值线，并确定该等值线平移后值增加的方向（向上移动函数值增大），平移此目标函数的等值线，使其达到既与可行域有交点 又 不 可 能 使 值 再 增 加 的 位 置 ， 得 到 交 点 (5,2

9、5)T ，即最优解。此目标函数的值为70000。 例题作图（例题作图（4 4）w第3步图示 作出目标函数等值线函数值增大2.2.线性规划的图解法线性规划的图解法 例题作图（例题作图（5 5） 第3步图示(2) 求出最优解121一般线性规划问题的数学表达式： nnxcxcxcf2211max(min) s.t 11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx 线性规划问题可以用单纯形方法求解，但是比较复杂，可以用常用的数学软件如MATLAB，MATHEMATICA,LINGO等求解，这里只介绍用LINGO求解

10、的方法。当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model LINGO1的窗口是LINGO的默认模型窗口，建立的模型都都要在该窗口内编码实现。 例例4 4 如何在LINGO中求解如下的LP问题：0,6002100350.32min212112121xxxxxxxtsxx在模型窗口中输入如下代码：min=2*x1+3*x2;x1+x2=350;x1=100;2*x1+x2=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7求

11、解可以得到最优解如下：30OBJECTIVE 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根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量为27m。 显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的

12、切割模式（模式2和5的余料为1 m），这会导致切割原料钢管的总根数较多。31 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.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 即按

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

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

15、rrrr4321,（非负整数）。 决策目标 切割原料钢管的总根数最小，目标为)6(321xxxMin约束条件 为满足客户的需求，应有)7(50313212111xrxrxr)8(10323222121xrxrxr)9(20333232131xrxrxr)10rxrxr35 每一种切割模式必须可行、合理，所以每根原料钢管的成品量不能超过19m，也不能少于16 m（余量不能大于3 m），于是)11(1986541641312111rrrr)12(1986541642322212rrrr)13(1986541643332313rrrr模型求解 在（7）（10）式中出现决策变

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

17、割模式下只生产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如下：38model：min=x1+x2+x3；x1*r11+x2*r12+x3*r13=50；x1*r21+x2*r22+x3*r23=10；x1*r3

18、1+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) ；gin(r12) ；gin(r13) ；gin(r21) ；gin(r22) ；gin(r23) ；gin(r

19、31) ；gin(r32) ；gin(r33) ；gin(r41) ；gin(r42) ；gin(r43) ；end39Local 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

20、.000000 R31 1.00000 0.000000 R32 1.00000 0.000000 R33 0.00000 0.000000 R41 0.00000 0.000000 R42 0.00000 0.000000 R43 2.00000 0.00000040 即按照模式1，2，3分别切割10，10，8根原料钢管，使用原料钢管总根数为28根， 第一种切割模式下一根原料钢管切割成3根4m钢管和1根6 m钢管； 第二种切割模式下一根原料钢管切割成2根4 m钢管、1根5 m钢管和1根6 m钢管； 第三种切割模式下一根原料钢管切割成2根8 m钢管。41二、非线性规划模型非线性规划模型的一般形

21、式为： )2(., 2 , 10)(.miXgtsi)3(., 2 , 10)(ljXhiDX 为为可可行行集集其其中中nTnRDxxxX,),(21 f(X)为目标函数， (2)、(3)为约束条件， (2)为不等式约束，(3)为等式约束；若只有(1)称为无约束问题。 ) 1 ()(minXf4232321213215),(minxxxxxxxxf如如0516223121xxxxx010312221xxxx 注：LINGO软件用于求解非线性规划（包括含有整数变量的），输入总是以“model：”开始，以“end”结束；中间的语句必须以“；”分开。约束中“gin(x1)”表示x1为整数，其他类似（

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

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

24、额为3万元； 项目D，每年初投资，年末收回本金且获利6%。问如何确定投资策略使第五年末本息总额最大。46问题的目标函数是第五年末的本息总额， 决策变量是每年初各个项目的投资额， 约束条件是每年初拥有的资金。 用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 11x21x31x41x32x23x14x24x34x44x54x47 因为项目D 每年初可以投资，且年末能收回本息，所以每年初都应把资金全部投出去， 项目A,从第一年到第

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

26、资，次年末收回本金且从第一年到第四年每年初投资，次年末收回本金且获利获利15%15%； 项目项目B B，第三年初投资，第五年末收回本金且获利，第三年初投资，第五年末收回本金且获利25%25%，最，最大投资额为大投资额为4 4万元；万元； 项目项目C C，第二年初投资，第五年末收回本金且获利，第二年初投资，第五年末收回本金且获利40%40%，最，最大投资额为大投资额为3 3万元；万元； 项目项目D D，每年初投资，年末收回本金且获利，每年初投资，年末收回本金且获利6%6%。 每项投资应为非负的每项投资应为非负的： 0ijx第五年末本息总额为第五年末本息总额为5432234106. 125. 14

27、0. 115. 1xxxxz将上条件等价变形如1424232106. 1xxxx006. 124232114xxxx49由此得投资问题的线性规划模型如下：5432234106. 125. 140. 115. 1maxxxxxzs.t. 101411 xx006. 124232114xxxx006. 115.xxxx006. 115, 144413421xxxx006. 115. 1544431xxx3, 42332xx0ijx50求解得4008. 0, 0,000. 3,5436. 3,1732. 6,8268. 3312423211411xxxxxx4609. 0,

28、 0,0752. 4, 0,0000. 45444413432xxxxx3750.14z 即即第第1年项目年项目A,D分别投资分别投资3.8268和和6.1732(万元万元)；第第2年项目年项目A,C分别投资分别投资3.5436和和3(万元万元)；第第3年项目年项目A,B分别投资分别投资0.4008和和4(万元万元)；第第4年项目年项目A投资投资4.0752(万元万元)；第第5年项目年项目D投资投资0.4609(万元万元)；5年后总资金年后总资金 14。375万元，即盈利万元，即盈利43.75%.51二、货机装运（了解）问题 某架货机有三个货舱：前仓、中仓、后仓。三个货舱所能装载的货物的最大重

29、量和体积都有限制，如表3所示。并且，为了保持飞机的平衡，三个货舱中实际装载货物的重量必须与其最大容许重量成比例。前仓中仓后仓重量限制（吨）10168体积限制（米3）680087005300 现有四类货物供该货机本次飞行装运，其有关信息如表4，最后一列指装运后所获得的利润。52重量（吨）空间（米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850应如何安排装运，使该货机本次飞行获利最大？模型假设 问题中没有对货物装运提出其它要求，我们可作如下假设： 1）每种货物可以分割到任意小； 2）每种货物可以在一个或多个货舱中任意分布；533

30、）多种货物可以混装，并保证不留空隙。 模型建立 决策变量： ijx表示第i种货物装入第j个货舱的重量（吨）， 货舱j=1,2,3分别表示前仓、中仓、后仓。 决策目标是最大化总利润，即)(3800)(3100232221131211xxxxxxZMax)(2850)(3500434241333231xxxxxx)13(约束条件包括以下4个方面：1）从装载的四种货物的总重量约束，即)14(18131211xxx54)15(15232221xxx)16(23333231xxx)17(12434241xxx2）三个货舱的重量限制，即)18(1041312111xxxx)19(1642322212xxx

31、x)20(843332313xxxx3）三个货舱的空间限制，即)21(680039058065048041312111xxxx122232424806505803908700(22)xxxx132333434806505803905300(23)xxxx554）三个货舱装入重量的平衡约束，即)24(81610433323134232221241312111xxxxxxxxxxxx模型求解 将以上模型输入LINDO求解，可以得到：56OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000

32、000X12 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 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000实际上，不妨将所得最优解作四舍五入， 57结果为 货物2装入前仓10吨、装入后仓5吨； 货物3装入中仓13吨、装入后仓3吨； 货物4装入中仓3吨， 最大利润约121516元。 评注 初步看来，本例与运输问题类似，似乎可以把4种货物看成4个供应点，3个货舱看成3个需求点（或者反过来，把货舱看成供应点，货物看成需求点）。但是，这里对供需量的限制包括两个方面：重量限制和空间限制，且有装载均匀要求，因此它只能看成是运输问题的一种变形和扩展。 58 例 某工厂制造A.B两种产品，制造A每吨需用煤9t，电力4kw，3个工作日；制造B每吨需用煤5t，电力5kw，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元，现工厂只有煤360t，电力200kw，工作日300个可以利用，问A、B