《数学规划模型》PPT课件.ppt

《《数学规划模型》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数学规划模型》PPT课件.ppt（33页珍藏版）》请在装配图网上搜索。

1、数学规划模型 实际问题中 的优化模型 mixgts xxxxfzM a xM i n i T n ,2,1,0)(. ),(),()( 1 或 x决策变量 f(x)目标函数 gi(x)0约束条件 决策变量个数 n和 约束条件个数 m较大 最优解在可行域 的边界上取得 数 学 规 划 线性规划 非线性规划 整数规划 重点在模型的建立和结果的分析 优化模型的 简单分类 线性规划 (LP) 目标和约束均为线性函数 非线性规划 (NLP) 目标或约束中存在非线性函数 二次规划 (QP) 目标为二次函数、约束为线性 整数规划 (IP) 决策变量 (全部或部分 )为整数 整数 线性 规划 (ILP)，整数

2、 非线性 规划 (INLP) 一般整数规划， 0-1（整数）规划 n j i Dx ljxg mixhts xf ,. . .,1,0)( ,. . .,1,0)(. )(m i n 连 续 优 化 离 散 优 化 数学规划 例 1 加工奶制品的生产计划 获利 24元 /公斤 1桶 牛奶 3公斤 A1 12小时 8小时 4公斤 A2 或 获利 16元 /公斤 50桶牛奶 时间 480小时 甲设备至多加工 100公斤 A1 制订生产计划，使每天获利最大 每天： 线性规划模型 1桶 牛奶 3公斤 A1 12小时 8小时 4公斤 A2 或 获利 24元 /公斤 获利 16元 /公斤 x1桶牛奶生产

3、A1 x2桶牛奶生产 A2 获利 24 3x1 获利 16 4 x2 原料供应 50 21 xx 劳动时间 480812 21 xx 加工能力 1003 1 x 决策变量 目标函数 21 6472 xxzM a x 每天获利 约束条件 非负约束 0, 21 xx 线性 规划 模型 (LP) 时间 480小时 至多加工 100公斤 A1 50桶牛奶 每天 模型求解 软件实现 LINGO model: max = 72*x1+64*x2; milk x1 + x250; time 12*x1+8*x2480; cpct 3*x1100; end Global optimal solution fo

4、und. Objective value: 3360.000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 MILK 0.000000 48.00000 TIME 0.000000 2.000000 CPCT 40.00000 0.000000 20桶牛奶生产 A1, 30桶生产 A2，利润 3360元 . 如何 装运， 使本次飞行 获利最大？

5、三个货舱 最大 载 重 (t),最大容积 (m3) 例 2 货机装运 重量 （ t） 体积 ( m3/t） 利润 （元 /t） 货物 1 18 480 3100 货物 2 15 650 3800 货物 3 23 580 3500 货物 4 12 390 2850 三个货舱中实际载重必须与其最大 载 重成比例 . 前仓： 10； 6800 中仓： 16； 8700 后仓： 8； 5300 飞机平衡 WET=(10,16,8), VOL=(6800,8700,5300); w=(18,15,23,12), v=(480,650, 580,390), p=(3100,3800,3500,2850).

6、 已知参数 i=1,2,3,4（货物） j=1,2,3 (分别代表前、中、后仓 ) 货舱 j的重量限制 WETj 体积限制 VOLj 第 i种货物的重量 wi，单位重量的体积 vi，利润 pi 货机装运 决策 变量 xij-第 i 种货物装入第 j 个货舱的重量 (t） i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓 ) 模型假设 每种货物可以分割到任意小； 货机装运 每种货物可以在一个或多个货舱中任意分布； 多种货物可以混装，并保证不留空隙； 所给出的数据都是精确的，没有误差 . 模型建立 货舱 容积 目标 函数 (利润 ) 约束 条件 货机装运 模型建立 货舱 重量 10；6

7、800 16；8700 8；5300 xij-第 i 种货物装入第 j 个货舱的重量 m a x 4 1 3 1 i j iji xpZ j i ij W E Tx 4 1 j i iji V O Lxv 4 1 约束 条件 平衡 要求 货物 供应 货机装运 模型建立 10； 6800 16； 8700 8； 5300 xij-第 i 种货物装入第 j 个货舱的重量 i j ij wx 3 1 k i ikj i ij W E TxW E Tx / 4 1 4 1 j,k=1,2,3; jk !定义集合及变量 ; sets: cang/1.3/:WET,VOL; wu/1.4/:w,v,p;

8、link(wu,cang):x; endsets !对已知变量赋值 ; data: WET=10,16,8; VOL=6800,8700,5300; w=18,15,23,12; v=480,650, 580,390; p=3100,3800,3500,2850; enddata max=sum(wu(i):p(i)*sum(cang(j):x(i,j); for(wu(i):sum(cang(j):x(i,j)w(i); for(cang(j):sum(wu(i):x(i,j)WET(j); for(cang(j):sum(wu(i):v(i)*x(i,j)VOL(j); for(cang(

9、j): for(cang(k)|k #GT# j: !#GT#是大于等于的含义 ; sum(wu(i):x(i,j)/WET(j)=sum(wu(i):x(i,k)/WET(k); ); END 货机装运 LINGO程序 Global optimal solution found. Objective value: 121515.8 Total solver iterations: 12 Variable Value Reduced Cost X( 1, 1) 0.000000 400.0000 X( 1, 2) 0.000000 57.89474 X( 1, 3) 0.000000 400.

10、0000 X( 2, 1) 7.000000 0.000000 X( 2, 2) 0.000000 239.4737 X( 2, 3) 8.000000 0.000000 X( 3, 1) 3.000000 0.000000 X( 3, 2) 12.94737 0.000000 X( 3, 3) 0.000000 0.000000 X( 4, 1) 0.000000 650.0000 X( 4, 2) 3.052632 0.000000 X( 4, 3) 0.000000 650.0000 货物 2：前仓 7,后仓 8； 货物 3: 前仓 3, 中仓 13； 货物 4: 中仓 3. 货机装运

11、模型求解 最大利润约 121516元 如果生产某一类型汽车，则至少要生产 80辆， 那么最优的生产计划应作何改变？ 例 1 汽车厂生产计划 汽车厂生产三种类型的汽车，已知各类型每辆车对 钢材、劳动时间的需求，利润及工厂每月的现有量 . 小型 中型 大型 现有量 钢材（ t） 1.5 3 5 600 劳动时间（ h） 280 250 400 60000 利润（万元） 2 3 4 制订月生产计划 ， 使工厂的利润最大 . 4.3 汽车生产与原油采购 IP可用 LINGO直接求解 整数规划 (Integer Programming,简记 IP) IP 的最优解 x1=64， x2=168， x3=0

12、， 最优值 z=632 max=2*x1+3*x2+4*x3; 1.5*x1+3*x2+5*x3600; 280*x1+250*x2+400*x3 60000; gin(x1);gin(x2);gin(x3); Global optimal solution found. Objective value: 632.0000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 64.00000 -2.000000 X2 168.0000 -3.000000 X3 0.000000 -

13、4.000000 321 432m a x xxxz 6 0 0535.1t.s. 321 xxx 6 0 0 0 04 0 02 5 02 8 0 321 xxx 为非负整数321 , xxx IP 结果输出 设每月生产小、中、大型 汽车的数量分别为 x1, x2, x3 其中 3个 子模型应 去掉，然后 逐一求解，比较目标函数值， 再加上整数约束，得最优解： 80,0,0 321 xxx 0,80,0 321 xxx 80,80,0 321 xxx 0,0,80 321 xxx 0,80,80 321 xxx 80,0,80 321 xxx 80,80,80 321 xxx 0, 321

14、xxx 方法 1：分解为 8个 LP子模型 汽车厂生产计划 若生产某类汽车，则至少生产 80辆，求生产计划 . 321 432m a x xxxz 6 0 0535.1t.s. 321 xxx 6 0 0 0 04 0 02 5 02 8 0 321 xxx x1,x2, x3=0 或 80 x1=80， x2= 150， x3=0，最优值 z=610 LINGO中对 0-1 变量的限定： bin(y1); bin(y2); bin(y3); 方法 2： 引入 0-1变量，化为整数规划 M为大的正数 , 本例可取 1000 Objective Value: 610.0000 Variable

15、Value Reduced Cost X1 80.000000 -2.000000 X2 150.000000 -3.000000 X3 0.000000 -4.000000 Y1 1.000000 0.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 若生产某类汽车，则至少生产 80辆，求生产计划 . x1=0 或 80 x2=0 或 80 x3=0 或 80 1,0,80, 11111 yyxMyx 1,0,80, 22222 yyxMyx 1,0,80, 33333 yyxMyx 最优解同前 max=2*x1+3*x2+4*x3; 1.5*

16、x1+3*x2+5*x3600; 280*x1+250*x2+400*x30; x2*(x2-80)0; x3*(x3-80)0; gin(x1);gin(x2);gin(x3); 方法 3： 化为非线性规划 非线性规划 （ Non- Linear Programming， 简记 NLP） 若生产某类汽车，则至少生产 80辆，求生产计划 . x1=0 或 80 x2=0 或 80 x3=0 或 80 0)80( 11 xx 0)80( 22 xx 0)80( 33 xx 最优解同前 . 一般地，整数规划和非 线性规划的求解比线性 规划困难得多，特别是 问题规模较大或者要求 得到全局最优解时 .

17、 汽车厂生产计划 决策变量为整数 , 建立 整数规划模型 . 求解整数规划和非线性规划比线性规划 困难得多 (即便用数学软件 ) . 当整数变量取值很大时 , 可作为连续变量 处理 , 问题 简化为线性规划 . 对于类似于“ x=0 或 80”这样的条件，通常 引入 0-1变量 处理，尽量不用非线性规划（特 别是引入的整数变量个数较少时） . 应如何安排原油的采购和加工 ？ 例 2 原油采购与加工 市场上可买到不超过 1500t的原油 A： 购买量不超过 500t时的单价为 10000元 /t； 购买量超过 500t但不超过 1000t时，超过 500t的 部分 8000元 /t； 购买量超过

18、 1000t时，超过 1000t的部分 6000元 /t. 售价 4800元 /t 售价 5600元 /t 库存 500t 库存 1000t 汽油甲 (A50%) 原油 A 原油 B 汽油乙 (A60%) 决策 变量 目标 函数 问题 分析 利润：销售汽油的收入 购买原油 A的支出 . 难点：原油 A的购价与购买量的关系较复杂 . )()(6.5)(8.4m a x 22122111 xcxxxxz 甲 (A50%) A B 乙 (A60%) 购买 x x11 x12 x21 x22 4.8千元 /t 5.6千元 /t 原油 A的购买量 ,原油 A, B生产 汽油 甲 ,乙的数量 c(x) 购

19、买原油 A的支出 利润 (千元 ) c(x)如何表述？ 原油供应 约束 条件 xxx 5 0 01211 1 0 0 02221 xx 1500 x 5 0 0 )1( 1 0 0 0 3 0 0 06 1 0 0 0 )( 5 0 0 1 0 0 0 8 5 0 0 )(0 10 )( xx xx xx xc x 500t单价为 10千 元 /t； 500t x 1000t，超过 500t的 8千 元 /t； 1000t x 1500t，超过 1000t的 6千 元 /t. 目标 函数 购买 x A B x11 x12 x21 x22 库存 500t 库存 1000t 目标函数中 c(x)不

20、是线性函数，是非线性规划； 对于用分段函数定义的 c(x)，一般的非线性规划软 件也难以输入和求解； 想办法将模型化简，用现成的软件求解 . 汽油含原油 A 的比例限制 5.0 2111 11 xx x 6.0 2212 12 xx x 2111 xx 2212 32 xx 约束 条件 甲 (A50%) A B 乙 (A60%) x11 x12 x21 x22 x1 , x2 , x3 以价格 10, 8, 6(千元 /t)采购 A的吨数 目标 函数 只有当以 10千元 /t的价格购买 x1=500(t)时，才能以 8千 元 /t的价格购买 x2 方法 1 )6810()(6.5)(8.4m

21、a x 32122122111 xxxxxxxz 5 0 0,0 321 xxx 非线性规划模型 ，可以用 LINGO求解 模型求解 x= x1+x2+x3, c(x) = 10 x1+8x2+6x3 500t x 1000t，超过 500t的 8千 元 /t 增加约束 0)500( 21 xx 0)5 0 0( 32 xx类似地有 方法 1： LINGO求解 Model: Max= 4.8*x11 + 4.8*x21 + 5.6*x12 + 5.6*x22 - 10*x1 - 8*x2 - 6*x3; x11+x12 x + 500; x21+x22 0; 2*x12 - 3*x22 0;

22、x=x1+x2+x3; (x1 - 500) * x2=0; (x2 - 500) * x3=0; x1 500; x2 500; x3 0 y=1 与方法 1（全局最优解）的结果相同 引入 0-1变量 模型求解 b1 b2 b3 b4 方法 3 b1 xb2， x= z1b1+z2b2， z1+z2=1， z1, z20, c(x)= z1c(b1)+z2c(b2). c(x) x 12000 9000 5000 O 500 1000 1500 b2 x b3， x= z2b2+z3b3， z2+z3=1， z2, z3 0, c(x)= z2c(b2)+z3c(b3). b3 x b4，

23、x= z3b3+z4b4， z3+z4=1， z3, z4 0, c(x)= z3c(b3)+z4c(b4). 5 0 0 )1( 1 0 0 0 3 0 0 06 1 0 0 0 )( 5 0 0 1 0 0 0 8 5 0 0 )(0 10 )( xx xx xx xc 直接处理分段线性函数 c(x) IP模型， LINGO 求解，得到的结 果与方法 2相同 . 44332211 bzbzbzbzx )()()()()( 44332211 bczbczbczbczxc bkxbk+1yk=1,否则 ,yk=0 3432321211 , yzyyzyyzyz )4,3,2,1(0,14321

24、 kzzzzz k 10,1 321321 或 yyyyyy 方法 3 bkxbk+1 ,x= zkbk+z k+1 bk+1 zk+zk+1 =1， zk, zk+1 0, c(x)= zkc(bk)+zk+1 c(bk+1 ). c(x) x 12000 9000 5000 O 500 1000 1500 b1 b2 b3 b4 对于 k=1,2,3 方法 3: 直接处理分段线性函数 ， 方法更具一般性 . 分段函数 无法直接用非线性规划方法或软件求 解 . 原油采购与加工 方法 1: 增加约束化为 非线性规划 ,可以用 LINGO 求解 , 但可能 得到的是局部最优解 . 方法 2: 引

25、入 0-1变量 , 化为 线性规划模型 , 可用 LINGO求解 . 如何选拔队员组成 4100m混合泳接力队 ? 例 1 混合泳接力队的选拔 5名候选人的 百米成绩 甲 乙 丙 丁 戊 蝶泳 仰泳 蛙泳 自由泳 8601 6511 721 685 275 35 495 275 601 4601 811 8701 6421 011 2411 6901 4701 111 8321 4201 目标 函数 若选择队员 i参加泳姿 j 的比赛，记 xij=1, 否则记 xij=0 0-1规划模型 cij(s)队员 i第 j 种泳姿的百米成绩 约束 条件 每人最多入选泳姿之一 cij i=1 i=2 i

26、=3 i=4 i=5 j=1 66.8 57.2 78 70 67.4 j=2 75.6 66 67.8 74.2 71 j=3 87 66.4 84.6 69.6 83.8 j=4 58.6 53 59.4 57.2 62.4 4 1 5 1 m in j i ijij xcZ 每种泳姿有且只有 1人 5,1,1 4 1 ix j ij 4,1,1 5 1 jx i ij 模型求解 MODEL: sets: person/1.5/; position/1.4/; link(person,position): c, x; endsets data: c= 66.8, 75.6, 87, 58.

27、6, 57.2, 66, 66.4, 53, 78, 67.8, 84.6, 59.4, 70, 74.2, 69.6, 57.2, 67.4, 71, 83.8, 62.4; enddata 输入 LINGO求 解 min=sum(link: c*x); for(person(i): sum(position(j):x(i,j)=1;); for(position(i): sum(person(j):x(j,i)=1;); for(link: bin(x); END 混合泳接力队的选拔 指派 (Assignment)问题 ： 有若干项任务 , 每项任务必 有且只能有一人承担，每人只能承担一项 ，不同人员 承担不同任务的效益 (或成本 )不同，怎样分派各项任 务使总效益最大 (或总成本最小 )? 人员数量与任务数量相等 人员数量大于任务数量 (本例 ) 人员数量小于任务数量 ? 建立 0-1规划模型是常用方法