数学规划ch4线

1、第四章 运筹与优化模型 4.1 线性规划模型 4.2 非线性规划模型 4.3 动态规划模型 4.4 变分法模型 4.5 层次分析法模型1 数学规划2规划模型（1）效益最大化或费用最小化（2）各种条件约束3 数学规划许多实际问题都可以归结为以下形式的 数学模型：44.1 线性规划模型5 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000 元与3000 元。生产甲机床需用A、B 机器加工，加工时间分别为每台2 小时和1 小时；生产乙机床需用A、B、C 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时，问该厂每

2、天应生产甲、乙机床各几台，才能使总利润最大？线性规划引例6 设该厂生产 台甲机床和 台乙机床时总利润最大，则 应满足 （目标函数） (约束条件)数学模型：7线性规划(linear Programming)模型目标函数约束条件决策变量8 1、有关线性规划问题的几个例子 2、线性规划问题的标准形式 3、关于整数规划 4、应用本节内容91.线性规划问题的几个例子 某化工厂生产A1，A2，A3，A4四种化工产品，每种产品生产1吨消耗的工时、能源和获得的利润如下表：产品A1A2A3A4工时(h)10025038075能源(吨标准煤)0.20.30.50.1利润(万元)2581 已知该厂明年的工时限额为1

3、8480h，能耗限额为100t标准煤，欲使该厂明年的总利润最高，请确定各种产品的生产数量。10模型产品A1A2A3A4生产数量x 1x 2x 3x 4假设：工时限制供煤限制11例 某商品有m 个产地、n 个销地，各产地的产量分别为 各销地的需求量分别为 。若该商品由i 产地运到 j 销地的单位运价为 ，问应该如何调运才能使总运费最省？运输问题(产销平衡)12解：引入变量 ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为13运输问题(产销不平衡)上例中，若产大于销，即 时, 运输模型可写为 14河流污染与净化问题 某河流边有两个化工厂, 流经第一个化工厂的河水流量是每天500万立方米,

4、 在两个工厂之间有一条流量为每天200万立方米的支流. 两个化工厂每天排放工业污水分别为2万与1.4万立方米, 从第一个化工厂排出的污水流到第二个化工厂之前, 有20可自然净化. 根据环保部门的要求,河流中工业污水的含量应不大于0.2 . 因此两个化工厂都必须各自处理净化一部分污水,已知他们治污成本分别为0.1元和0.08元每立方米。问在满足环保要求的条件下，两厂各需要处理多少污水，可使两厂总的处理污水费用最少。15分析: (1) 假设第一、二厂每天各自处理x1和x2万立方米的污水; (2) 根据环保部门的要求，应有 同时应有 16 (3) 记 f 为两厂治污的总费用,则有从而该问题的数学模型

5、为172. 线性规划问题的标准形式若写成向量和矩阵形式, 则有 18求解方法：（1）单纯形法 （2）软件求解:Lindo， matlab，Lingo等 其中 注: 任何线性规划模型都可以化为标准形式. 19实例 将以下LP问题化为标准型:20解 令得标准型为松弛变量剩余变量21线性规划的Matlab 标准形式其中c 和x 为n 维列向量， A 、Aeq 为适当维数的矩阵， b 、beq 为适当维数的列向量。22Matlabx,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)fval 返回目标函数的值，LB 和UB 分别是变量x 的下界和上界， x0 是x

6、 的初始值，OPTIONS 是控制参数。23Matlab（i）编写M 文件c=2; 3; -5;a=-2,5,-1;1,3,1; b=-10;12;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c*x （ii）将M文件存盘，并命名为example1.m。 （iii）在Matlab指令窗运行example1即可得所求结果。x = 6.4286 0.5714 0.0000value = 14.5714求最大值24 编写Matlab程序如下：c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-

7、b,zeros(3,1)25LP问题的图解法(仅适用二维问题)实例 用图解法求解以下LP问题:26解:最优解为(4,4/3)最优目标值为44/3273.整数规划(Integer Linear Programming)模型28 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及价值（元），问此人应如何选择携带的物品（各几件），使所带物品价值最大？物品 1 2 j n重量（公斤/件） a1 a2 aj an每件价值 c1 c2 cj cn 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。背包问题2

8、9设xj 为第j 种物品的装件数（非负整数）则问题的数学模型如下：30LP问题的Lindo输入范例ST2) 3) 4) END31ST2) 3) 4) ENDGIN2 (!表示前两个变量为一般整数)ILP问题的Lindo输入范例之一32ST2) 3) 4) ENDGIN(X1);GIN(X2);ILP问题的Lingo输入范例33例：运输问题(产销不平衡) 设有三个化肥厂供应四个地区的农用化肥. 各化肥厂产量(单位：万吨), 各地区年需求量(单位：万吨)及从各化肥厂到各地区的单位运价(单位：万元/万吨)如表所示，试建立使总运费最省的化肥调拨方案.表4.1.434 地 区化 肥 厂 I I II

9、III IV IV产 量ABCD 16 16 13 22 17 17 14 14 13 19 15 15 19 19 20 23 M M M 0 M 0 M 050605050需求 30 20 70 30 10 50 210模型的建立与求解 设 表示第i个化肥厂运到各地区的满足最低需求部分， 表示第i个化肥厂运到各地区的满足最高需求的部分，则调运方案数学模型为35例：综合运输问题的0-1规划模型 设某种物质有 m 个产地 第 i 个产地的产量为 该物资将销往 n 个销地 第 j 个销地的销量为 且有 已知从各个产地运往各销地需经过 p 个中间编组站 转运, 若启用第 k 个编组站，不管转运量多

10、少，均发生固定费用 且第 k 个中间编组站转运的最大容量限制为 用 和 分别表示从 到 和从 到 的单位物质的运输费用，试建立使总运费为最小的该种物资的调运方案的数学模型。 36 分析 从产地到中转站和从中转站到销地，均为运输问题，关键是各中转站是否启用，用哪几个。对于中转站而言，具有用与不用两种状态，故可以考虑引入0-1变量来处理。 模型建立和求解 设 表示从产地 运至中转站 的物资的数量， 表示从中转站运至销地 的物资数量，记37 周一 18人 周二 15人 周三 12人 周四 16人 周五 19人 周六 14人 周日 12人例 某百货商场每周内至少需要售货员人数如下：规定每个员工每周连续

11、工作五天，休息两天。求总员工数最少的排班方案。38ILP问题的图解法(仅适用二维问题)实例 用图解法求解以下ILP问题:39解:对应LP问题最优解为(4,4/3),不是ILP问题的可行解ILP问题的最优解为X*=(4,1),最优目标值为 z*=14,可行域顶点可以是非可行解40投资的效益和风险(1998年全国大学生数学建模竞赛A题)41原题还有一组 n=25的数据，现略去。42问题分析优化问题决策每种资产的投资额（投资组合）目标净收益最大整体风险最小 在一定风险下收益最大的决策 在一定收益下风险最小的决策 收益和风险按一定比例组合最优的决策一组解(如在一系列风险值下收益最大的决策)二者矛盾 冒

12、险型投资者从中选择高风险下收益最大的决策 保守型投资者则可从低风险下的决策中选取43模型建立用数学符号和式子表述决策变量、构造目标函数、确定约束条件。xi对Si(i=0,1,n)的投资, x0表示存入银行.目标函数 总收益投资Si的收益减去交易费，对i求和 总体风险投资Si的风险，对i求最大值对Si的投资xi加交易费ci(xi)，对i求和，不超过给定资金M.决策变量约束条件440uixicipiui1）投资Si的交易费、净收益、风险、资金表达式交易费净收益(收益率ri)风险资金(风险损失率qi)452）投资方案、总收益、总体风险、资金表达式投资方案总收益总体风险资金3）两目标（总收益、总体风险

13、）优化模型464）单目标优化模型47模型简化交易费ui很小M很大资金约束设M=1投资Si的比例48设M=1线性规划模型LP1模型M1的简化M149模型M2的简化M2极大极小规划模型线性规划模型LP2引入人工变量 xn+150模型M3的简化M3线性规划模型LP3模型求解LP1,LP2,LP3都很容易用MATLAB, MATHEMATICA或其它数学软件求解51线性规划模型LP152模型一的求解535455LP1的结果风险水平取k=02.5%, 得投资比例y0y456LP1的结果57LP3的结果与LP1相同58实例 某厂生产A,B, C三种产品,每种产品的单位利润分别为12,18和15,资源消耗和

14、资源总数量如下表,求总利润最大的生产方案. A B C 限制 原料1/单位产品 6 9 5 200 原料2/单位产品 12 16 17 360 人工/单位产品 25 20 12 78059解:设生产A,B,C分别为x1,x2,x3个单位,数学模型为:60整数规划的计算方法分枝定界法主要思路 1.分枝 把全部可行解空间反复地分割为越来越小的子集； 2.定界对每个子集内的解集计算一个目标下界（对于最小值问题）； 3.剪枝在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑61 设有最大化的整数规划问题A ，与它相应的线性规划为问题B ，从解问题B 开始，若

15、其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z* 的上界，记作 ；而A 的任意可行解的目标函数值将是z* 的一个下界 。分枝定界法就是将B 的可行域分成子区域的方法。逐步减小 和增大 ，最终求到z*.62 例 求解下述整数规划解 （i）先不考虑整数限制，即解相应的线性规划B ，得最优解为：此时 取 63（ii）因为 当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 进行分枝，把可行集分成2 个子集：这两个子集的规划及求解如下：问题B1 问题B264（iii）对问题 再进行分枝得问题 和 ,它们的最优解为再定界： 340 z* 349，并将 剪枝。（iv）对

16、问题 再进行分枝得问题 和 ，它们的最优解为将 于是可以断定原问题的最优解为：65例 某校篮球队准备从以下队员中选拔3名为正式队员，并使平均身高尽可能高，这6名预备队员情况如下表所示。预备队员 号码 身高 位置 大张 1 193 中锋 大李 2 191 中锋 小王 3 187 前卫 小赵 4 186 前卫 小田 5 180 后卫 小周 6 185 后卫66 队员的挑选要满足下列条件：至少补充一名后卫(5、6)队员；大李(2号)或小田(5号)中间只能入选一名；最多补充一名中锋(1、2)；若大李(2)或小赵(4)入选，小周(6)就不能入选。 试建立此问题的数学模型。解:则该问题的数学模型为:67上

17、述形式的数学规划模型称为(0-1)规划 队员的挑选要满足下列条件：至少补充一名后卫(5、6)队员；大李(2号)或小田(5号)中间只能入选一名；最多补充一名中锋(1、2)；若大李(2)或小赵(4)入选，小周(6)就不能入选。 试建立此问题的数学模型。68 0-1规划 一个公司有22亿元资金用来投资，现有6个项目可供选择，各项目所需投资金额和预计年收益如下表所示：项目123456投资526468收益0.50.40.60.50.91 应选择哪几个项目投资收益最大？69指派问题 0-1规划问题：70 上述指派问题的可行解可以用一个矩阵表示，其每行每列均有且只有一个元素为1，其余元素均为0。 问题中的变

18、量只能取0 或1，从而是一个0-1 规划问题。一般的0-1 规划问题求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为 1），其非负可行解的分量只能取0 或1，故约束 或 可改写为 而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中m = n ， 。71指派问题的计算机解法7273解指派问题的匈牙利算法74五、网络问题问题： 右图是一公路交通图，弧上数字为路程，求汽车从（1）到（7）最短路。75模型：76问题变形最大流问题上图77问题变形最小费用流问题上图78六、问题应用钢管下料问题：某钢管零售商从钢管厂进货，将钢管按顾客 的要求

19、切割后售出，从钢管厂进货时得到的 原料钢管都是19m。（1）现有一客户需要50根4m、20根6m和15根8m 的钢管，应如何下料最省。79问题(1)分析： 首先，应当确定哪些切割模式是可行的。所谓一个切割模式，是指按照客户需要在原料钢管上安排切割的一种组合。显然，可行的切割模式是很多的。 其次，应当确定哪些切割模式是合理的。通常假设一个合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸。例如，将19m 长的钢管切割成3 根4m的钢管是可行的，但余料为7m，可以进一步将7m 的余料切割成4m 钢管（余料为3m），或者将7m 的余料切割成6m 钢管（余料为1m）。在这种合理性假设下，切割

20、模式一共有7 种，如表3 所示。80问题（1）解答钢管下料合理切割模式：问题：按何种切割模式，切割多少根原钢管，最为节省。节省： 1）余料最少 2）原钢管总数最少81模型设x i表示照第i种模式切割原材料钢管的根数总余料最小 原钢管条数最少82求解 运用Lingo软件对上述整数规划问题分别求解. 对第一个目标模型，求得:按照模式2 切割12 根原料钢管，按照模式5 切割15 根原料钢管，共27 根，总余料量为27m。但4m 长的钢管比要求多切割了1 根，6m 长的钢管比要求多切割了7 根。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割方式（模式2 和模式5 的余料为1m），这会

21、导致切割原料钢管的总根数较多。83 对第二个目标模型，求得: 按照模式2 切割15 根原料钢管，按模式5 切割5 根，按模式7 切割5 根，共25 根，可算出总余料量为35m。但各长度的钢管数恰好全部满足要求，没有多切割。与上面得到的结果比较，总余料量增加了8m，但是所用的原料钢管的总根数减少了2根。在余料没有什么用途的情况下，通常选择总根数最少为目标。84（2）零售商如果采用的不同切割模式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定只能采用3种不同的切割模式。此外，该客户除需要（1） 中的三种钢管外，还需要10根5m的钢管，应如何下料最省。85问题（2）解答问题分

22、析： 按照问题（1）的思路，可以通过枚举法首先确定哪些切割模式是可行的。但由于需要的钢管规格增加到4 种，所以枚举法的工作量较大。 一合理的切割模式的余料不应该大于或等于客户需要的钢管的最小尺寸，故本题中合理的切割模式的余量不能大于3m。这里，仅选择总根数最少为目标进行求解。86模型建立设x i表示照第i种模式切割原材料钢管的根数（i=1,2,3）r ji分别表示在第i种切割模式下一根原钢管生产第j种(j=1,2,3,4 分别对应长度是4,5,6,8米的钢管)钢管数量(满足4米钢管数需求)(满足5米钢管数需求)(满足6米钢管数需求)(满足8米钢管数需求)(第i种模式所得钢管 总长度, i=1,

23、2,3)87七、应用（AMCM-88B） 将七种不同规格的包装箱装到两辆铁路平板车上，各包装箱宽、高均相等，但厚度t(厘米)与重量w(公斤)不同。每平板车有10.2米长的地方用来装包装箱，载重40吨。由于货运限制，对c5、c6、c7类包装箱总数有限定：总厚度不超过302.7(厘米)。试把箱子装到平板车并使空间浪费最小。88八、应用（AMCM-89B） 机场通常按“先来先走”的原则来分配飞机跑道，即当飞机准备好离开登机口时，驾驶员电告地面控制中心，加入等候跑道的队伍。假设控制中心可以从快速联机数据库中得到每架飞机如下信息： 1、预定离开登机口的时间 2、实际离开登机口的时间 3、机上乘客人数 4、预定在下一站转机的人数和时间 5、到达下一站的预定时间。 又设飞机共有七种型号，载客量从100人起以50人递增，载客最多达400人。 试开发和分析一种能使乘客和航空公司双方满意的数学