17[1].优化.ppt

1、数学规划模型,数学规划俗称最优化,首先是一种理念, 其次才是一种方法,它所追求的是一种 “至善”之道,一种追求卓越的精神.,小明同学，烧一壶水要8分钟，灌开水要1分钟，取牛奶和报纸要5分钟，整理书包要6分钟，为了尽快做完这些事，怎样安排才能使时间最少？最少需要几分钟？,数学规划(最优化)作为一门学科孕育于20世纪的30年代,诞生于第二次世界大战弥漫的硝烟中。 数学规划指在一系列客观或主观限制条件下，寻求合理分配有限资源使所关注的某个或多个指标达到最大（或最小）的数学理论和方法，是运筹学里一个十分重要的分支。,最优化问题的数学模型的一般形式为：,（1）,（2）,三个要素：决策变量decision

2、 bariable，目标函数objective function，约束条件constraints。,所确定的x的范围称为 可行域(feasible region）， 满足(2)的解x称为 可行解(feasible solution）， 同时满足(1)(2)的解x称为 最优解(Optimal solution)， 整个可行域上的最优解称为 全局最优解(global optimal solution)， 可行域中某个领域上的最优解称为 局部最优解(local optimal solution), 最优解所对应的目标函数值称为 最优值(optimum)。,优化模型的分类,（一）按有无约束条件可分为：

3、 1.无约束优化（unconstrained optimization）。 2.约束优化（constrained optimization）。,大部分实际问题都是约束优化问题。,（二）按决策变量取值是否连续可分为：,1.数学规划或连续优化,可继续划分为 线性规划(LP)Linear programming 和 非线性规划(NLP) Nonlinear programming。 在非线性规划中有一种 规划叫做 二次规划(QP)Quadratic programming， 目标为二次函数，约束为线性函数。,2.离散优化或组合优化。 包含： 整数规划(IP)Integer programming，

4、整数规划中又包含很重要的一类规划： 0-1（整数）规划Zero-one programming， 这类规划问题的决策变量只取0或者1。,（三）按目标的多少可分为： 1.单目标规划 2.多目标规划,（四）按模型中参数和变量是否具有不确定性可分为： 1.确定性规划 2.不确定性规划,（五）按问题求解的特性可分为： 1.目标规划 2.动态规划 3.多层规划 4.网络优化 5.等等,生产计划问题,例1 汽车厂生产计划,制订生产计划，使利润最大,获利 2x1,3 x2,原料供应,劳动时间,决策变量,目标函数,总获利,约束条件,4 x3,非负约束,且为整数,生产小型64台，中型168台，大型0台，利润63

5、2,例2 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,每天：,制订生产计划，使每天获利最大,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 243x1,获利 164 x2,原料供应,劳动时间,决策变量,目标函数,每天获利,约束条件,非负约束,20桶牛奶生产A1, 30桶生产A2，利润3360元,加工能力,运输问题,例3 自来水输送,支出：引水管理费,收入：900元/千吨,其他支出：450元/千吨,如何分配水库供水量，公司才能获利最多？,问题分析：,水库i向j区的日供水量为xij (x34=0),供应约束,决策变量,目标函数,约束条件,需求约束,引水管理费：24400

6、（元）,最大利润：47600（元）,例4 货机装运,三个货舱最大载重(吨),最大容积(米3),飞机平衡：三个货舱中实际载重与最大载重成比例,如何装运，可使本次飞行获利最大？,模型假设：,（1）每种货物可以分割到任意小 （2）每种货物可以在一个或多个货舱中任意分布 （3）多种货物可以混装，并保证不留空隙,决策变量,货物i装在第j舱的重量为xij 吨,i=1,2,3,4依次表示4种货物 j=1,2,3 分别代表前、中、后舱,目标函数,约束条件,重量约束,容积约束,供应约束,平衡约束,练 习,Model: sets: Wh/w1,w2,w3/:ai; Vd/v1,v2,v3/:dj; Links(w

7、h,vd):c,x; Endsets Data: Ai=60 55 51; Dj=35 37 22; C=6 2 6 4 9 5 5 2 1; Enddata Min=sum(links(i,j):c(i,j)*x(i,j); for(wh(i):sum(vd(j):x(i,j)=ai(i); for(vd(j):sum(wh(i):x(i,j)=dj(j); End,下料问题,例5 材料分割,圆钢原材料每根长5.5m，现需要A，B，C三种圆钢材料， 长度分别为3.1m，2.1m，1.2m，数量分别为100,200, 400根，试安排下料方式，使所需圆钢原材料总数最少。,问题分析,决策变量,设

8、第i种截法的数量为xi,目标函数,约束条件,需求约束,非负约束,一维下料问题的一般表述,需要m种材料A1,A2,Am ，数量分别为bj，对一件长的 原材料可得出k种不同的切割方法，nij表示第i种方法得 到Aj部件的数量。用xi表示第种截法的原材料数量，则 该问题的模型为：,(),(),其中：L表示总长度，lj表示部件长度。,练 习,钢管原材料每根长19m，现需要A，B，C，D四种钢管材 料，长度分别为4m，5m，6m，8m，数量分别为50,10, 20，15根，因不同下料方式之间的转换会增加成本，因 而要求不同的下料方式不超过3种，试安排下料方式， 使所需钢管原材料总数最少。,Model:

9、Sets: Cutfa/1,2,3/:x; Buj/1.4/:L,need; Shul(cutfa,buj):n; Endsets Data: L=4 5 6 8 ; Need=50 10 20 15; Zl=19; Enddata Min=sum(cutfa:x); for(buj(j):sum(cutfa(i):n(i,j)*x(i)=need(j); for(cutfa(i):sum(buj(j):n(i,j)*L(j)=16); for(shul:gin(n); for(cutfa:gin(x); End,配料问题,例6 菜单制订,某疗养院营养师要为某类病人拟定本周蔬菜类菜单，当前可供

10、选 择的蔬菜品种、价格和营养成分含量、以及病人所需养分的最低 数量列如下表。病人每周需14份蔬菜，为了口味的原因，规定一 周内卷心菜不多于2份，胡萝卜不多于3份，其他蔬菜不多于4份且 至少一份，在满足要求的前提下，制订费用最少的一周菜单方案。,决策变量,6种蔬菜的份数分别为xi ，蔬菜单价为ai,每 周最低营养需求为bj,第i种蔬菜第j种养分含 量为cij.,目标函数,约束条件,总费用：20.6元,Model: Sets: Shc/a1.a6/:ai,x; Yf/b1.b5/bj; hanliang(shc,yf):c; Endsets Data: Ai=2 1 1.8 1.2 2 1.2;B

11、j=6 125 12500 345 5; C=0.45 20 415 22 0.3 0.45 28 4065 5 0.35 0.65 40 850 43 0.6 0.4 25 75 27 0.2 0.5 26 76 48 0.4 0.5 75 235 8 0.6; Enddata Min=sum(shc:ai*x); for(shc(i):gin(x(i);for(shc(i):x(i)=1); sum(shc(i):x(i)=14;x(2)=bj(j); End,练 习,某工厂要用四种原料B1,B2,B3,B4混合生产三种产品A1,A2,A3， 各产品的原料含量、加工费用和销售价格如下表,四

12、种原料的每天最大供货量及单价如下表：,假如生产能力和销售都不成问题，应如何安排生产计划才能使 利润最大？,指派问题,设有 n项工作分配给n个人去做，每人做一项，由于各 人的工作效率不同，因而完成同一工作所需要的时间 也就不同，设人员i完成工作j所需要的时间为cij，问如何 分配工作，使完成所有工作所用的总时间最少？,常用解法：0-1规划,指派问题也称最优匹配问题,决策变量,目标函数,约束条件,第i个人不做第j项工作 第i个人做第j项工作,例7 任务分配,分配甲，乙，丙，丁，戊去完成A，B，C，D，E五项 任务，每人完成一项，每项任务只能由一个人去完成， 五个人分别完成各项任务所需要的时间如下表

13、，试作 出任务分配使总时间最少。,Model: Sets: Worker/w1.w5/; Job/j1.j5/; Links(worker,job):c,x; Endsets Data: C=8 6 10 9 12 9 12 7 11 9 7 4 3 5 8 9 5 8 11 8 4 6 7 5 11; Enddata Min=sum(links:c*x); for(worker(i):sum(job(j):x(i,j)=1); for(job(j):sum(worker(i):x(i,j)=1); for(links:bin(x); End,练 习,某公司要把4个有关能源工程项目承包给4个互

14、不相关的 外商投标者，规定每个承包商只能且必须承包一个项目， 试在总费用最小的条件下确定各个项目的承包者，总费 用为多少？各承包商对工程的报价如下表。,项目1 项目2 项目3 项目4 外商甲 15 18 21 24 外商乙 19 23 22 18 外商丙 26 17 16 19 外商丁 19 21 23 17,投资问题,例8 投资方案,某部门现有资金100万元,在今后五年内考虑对以下四个 项目投资,已知项目1:从第一年到第四年每年年初需要 投资,并于次年末收回本利112%;项目2:第三年年初需 要投资,到第五年末能收回本利118%,但规定最多投资 额不超过40万元;项目3:第二年年初需要投资到

15、第五年 末能收回本利126%,但规定最多投资不超过30万元;项 目4:五年内每年年初可购买公债,于当年末归还,并加利 息5%.试确定投资方案,使收益最大.,问题分析：,项目4每年年初可投资且年末能收回，手上资金应全部投出,决策变量,第i年初投资给项目 j的资金记为为xij,决策变量,目标函数,约束条件,第i年初投资给项目 j的资金记为为xij,练 习,某校基金会得到了一笔数额为M万元的基金，打算将其 存入银行，校基金会计划在n年内每年用部分本息奖励 优秀师生，要求每年的资金额相同，且在n年末仍保留 原基金数额。银行存款税后年利率如下表：,请在M=5000，n=5年的情况下设计具体存款方案，让校

16、 基金会获得最佳的基金使用计划，以提高每年的奖金额。,选址问题,例9 料场选址,某公司有6个建筑工地要开工，工地位置（xi, yi）(单位：km)和 水泥日用量di(单位：t)由下表给出，公司目前有两个临时存放水 泥的料场，分别位于A(5,1)和B(2,7)，日存储量各20t: (1)假设从料场到工地之间均有直线道路相连，试制定日运输计 划，即从A，B分别向各工地送多少水泥，使总吨千米数最小。 (2)为进一步减少吨千米数，打算舍弃目前的两个料场，改建两 个新料场，日存储量不变，问建在何处为好？,决策变量,目标函数,约束条件,料场的位置用(pxj, pyj)表示，日存储用gj表示， 从料场j向工

17、地i日运输量为cij,问题一,Model: Sets: Gd/1.6/x,y,d; Lch/a,b/px,py,g; Links(gd,lch):c; Endsets Data: X=1.25 8.75 0.5 5.75 3 7.25; Y=1.25 0.75 4.75 5 6.5 7.75; D=3 5 4 7 6 11; Px=5 2; py=1 7; g=20 20; Enddata Min=sum(links(i,j):c(i,j)*(px(j)-x(i)2+(py(j)-y(i)2)(1/2); for(gd(i):sum(lch(j):c(i,j)=d(i); for(lch(j)

18、:sum(gd(i):c(i,j)=g(j); end,最优调运方案,总吨千米数：136.2275,Model: Sets: Gd/1.6/x,y,d; Lch/a,b/px,py,g; Links(gd,lch):c; Endsets Data: X=1.25 8.75 0.5 5.75 3 7.25; Y=1.25 0.75 4.75 5 6.5 7.75; D=3 5 4 7 6 11; g=20 20; Enddata Min=sum(links(i,j):c(i,j)*(px(j)-x(i)2+(py(j)-y(i)2)(1/2); for(gd(i):sum(lch(j):c(i,

19、j)=d(i); for(lch(j):sum(gd(i):c(i,j)=g(j); end,问题二,区别之处：取消了对px,py的赋值,非线性规划：全局优化求解器,多初始点求解程序的Attempts设置为4,最优调运方案,总吨千米数：85.266,料场位置：,A（3.255，5.652） B（7.250，7.750）,练 习,某公司计划在A、B、C三个区建立销售部，确定了7个 位置M1，M7可供选择，并且规定： （1）在A区，从M1、M2、M3三个点中至多选两个； （2）在B区，从M4、M5两个点中至少选一个； （3）在C区，从M6、M7两个点中至少选一个。 已知：如果选择M1，M7，则分别

20、投资为200、300、 350、250、350、200、400（万元），现在公司可用于 投资的资金共有1200万元，问应如何建立销售部？,决策变量,目标函数,约束条件,不选择Mi投资 选择Mi投资,记M1，M7的投资分别是bi万元，每年获利ci万元， 总资金为b万元,装箱问题,设有许多长为c的一维箱子及长为wi(wic),i=1,2, ,n 的n件物品,要把这些物品全部装入箱中，怎样装法才 能使所用的箱子数尽可能少？,不用第j个箱子 用第j个箱子,决策变量,第i件物品不放入第j个箱子 第i件物品放入第j个箱子,目标函数,约束条件,例10 物品装箱,已知30个物品，其中6个长0.51m，6个长0

21、.27m，6个 长0.26m，余下12个长0.23m，箱子长为1m。问最少 需要多少个箱子才能把30个物品全部装进箱子。,Model: Sets: Wp/w1.w30/:w; Xz/v1.v30/:y; Links(wp,xz):x; Endsets Data: W=0.51 0.51 0.51 0.51 0.51 0.51 0.27 0.27 0.27 0.27 0.27 0.27 0.26 0.26 0.26 0.26 0.26 0.26 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23 0.23; Enddata minsum(xz(i):y(i);c=1; for(xz:bin(y);for(links:bin(x); for(wp(i):sum(xz(j):x(ij)