excel在运筹学中的应用

1、1,第一章,线性规划模型（LP）,1. 数学模型 2. 应用举例 3. 运输问题 4. 任务指派问题 5. 0-1变量应用,2,1. 线性规划数学模型,Max (or Min) Z = c1x1 + c2x2 + + cnxn,a11x1 + a12x2 + + a1nxn (,= ) b1 a21x1 + a22x2 + + a2nxn (,= ) b2 am1x1 + am2x2 + + amnxn (,= ) bm x1, x2 , , xn 0, or Int. or Bin.,s.t.,可行解 满足约束条件的解，可行方案 可行域 全体可行解（可行方案） 最优解 使目标函数取得最优的可

2、行解 X* = (x1*, x2*, , xn*)T Z* = Z(X*) = Zmax (or min),3,2. 应用举例,Ex. 总利润最大，生产计划（产品最优组合）？,解. 设生产计划 x1、x2 （件） 总利润 Z,Max Z = 2x1 + 3x2 s.t. 2x1 +2x2 12 x1 +2x2 8 4x1 16 4x2 12 x1, x2 0,最优解 X* = (4，2)T Z* = 14,4,例 人事安排 连续工作 8 小时，总人数最少，排班规则？,解. 设 6 班倒，第 i 班人数 xi，i = 1,26, 总人数 Z,x1,x2,x3,x4,x5,x6,x6,X*= （6

3、0, 10, 50, 0, 30, 0）T Z*= 150,5,P.108 人员排程,一天10个时段5个班 8小时工作，每日总成本最小，如何排班？,x1,x2,x3,x4,x5,解：设每班代理商个数 xj，j=1,25, 日总成本 Z,最优解（P.110） X*= (48, 31, 39, 43, 15) Z*= $30,610,6,P. 65 借贷款,目前现金 1 百万，0312年现金流需要，10年长贷率0.07，1年短贷率0.1，每年末现金余额 50万，如何贷款，项目余额最大？,1,6 2,1,1,-0.42,-0.2,-2,1.38,- - - -,Max,非整数求解：Z*=2.92，

4、整数求解： Z*=2.40,7,建模： 设长贷 x，每年初短贷 y1，y2，y10，项目结算余额 Z 约束： 每年末余额至少0.5百万。目标： 项目结算余额 Z 最大。,约束： 第 1年末： 1 - 8 +x +y1 0.5 第 2年末： 上左 - 2 +y2 -0.07x -0.1y1 -y1 0.5 第 3年末： 上左 - 4 +y3 -0.07x -0.1y2 -y2 0.5 第 4年末： 上左 + 3 +y4 -0.07x -0.1y3 -y3 0.5 第 5年末： 上左 + 6 +y5 -0.07x -0.1y4 -y4 0.5 第 6年末： 上左 + 3 +y6 -0.07x -0

5、.1y5 -y5 0.5 第 7年末： 上左 - 4 +y7 -0.07x -0.1y6 -y6 0.5 第 8年末： 上左 + 7 +y8 -0.07x -0.1y7 -y7 0.5 第 9年末： 上左 - 2 +y9 -0.07x -0.1y8 -y8 0.5 第 10年末： 上左 +10 +y10 -0.07x -0.1y9 -y9 0.5 目标： MAX Z = 上左 -x -0.07x -0.1y10 -y10,8,整理： 约束： 第 1年末： - 7 +x +y1 0.5 第 2年末： - 9 +0.93x +y2 -0.1*（y1） 0.5 第 3年末： -13 +0.86x +

6、y3 -0.1*（y1+y2） 0.5 第 4年末： -10 +0.79x +y4 -0.1*（y1+y2+y3） 0.5 第 5年末： - 4 +0.72x +y5 -0.1*（y1+y2+y3+y4） 0.5 第 6年末： - 1 +0.65x +y6 -0.1*（y1+y2+y3+y4+y5） 0.5 第 7年末： - 5 +0.58x +y7 -0.1*（y1+y2+y3+y4+y5+y6） 0.5 第 8年末： 2 +0.51x +y8 -0.1*（y1+y2+y3+y4+y5+y6+y7） 0.5 第 9年末： 0 +0.44x +y9 -0.1*（y1+y2+y3+y4+y5+y

7、6+y7+y8） 0.5 第 10年末： 10 +0.37x +y10-0.1*（y1+y2+y3+y4+y5+y6+y7+y8+y9）0.5 变量性质： x，y1，y2，y10 0，or 整数 目标：MAX Z = 10 -0.7*x-0.1*(y1+y2+y3+y4+y5+y6+y7+y8+y9+y10),9,P.101 资金预算,如何投资项目，总净现值最大？,解 Max NPV= 45OB+ 70H+ 50SC s.t. 40 OB+ 80 H+ 90 SC 25 100 OB+ 160 H+ 140 SC 45 190 OB+ 240 H+ 160 SC 65 200 OB+ 310

8、H+ 220 SC 80 OB, H, SC 1 OB, H, SC 0,最优解（P.104） OB* = 0 % H* = 16.5 % SC* = 13.11 % NPV* = 18.11（百万）,10,例 投资组合；50 万元如何投资组合使平均年收益率最高？,解. 设xi为第i投资品种在总投资中的比率，年平均收益率Z(%),Max Z = 11x1 + 15x2 + 25x3 + 20 x4 + 10 x5 + 12x6 + 3x7,s.t.,3x1 + 10 x2 + 6x3 + 2x4 + x5 + 5x6 5 11x1 + 15x2 + 25x3 + 20 x4 + 10 x5 +

9、 12x6 + 3x7 13 x1 + 3x2 + 8x3 + 6x4 + x5 + 2x6 4 15x2 + 30 x3 + 20 x4 + 15x5 + 10 x6 10 x1 + x2 + x3 + x4 + x5 + x6 + x7 = 1 xj 0, j = 1, , 7.,Z* = 17%,11,例 两个工厂生产的油漆要运给三个客户；油漆在工厂必须经过着色和调和两道工序；如何生产销售使总费用最小？,12,x1 x2 x3 x4 x5 x6,解. 工厂1 生产 ( x1+x2+x3 ) 吨，工厂2 生产 ( x4+x5+x6 ) 吨 总费用 Z （元）,Min Z = 总运费 + 总

10、处理成本 = 总运费 + + 380()+ 260()+ 400()+ 250(),x1+x4 55 （建材订单） x2+x5 100 （化工订单） x3+x6 85 （建筑订单） 5(x1+x2+x3) 600 （厂1 着色） 7(x1+x2+x3) 800 （厂1 调和） 4(x4+x5+x6) 1000（厂2 着色） 6(x4+x5+x6) 1200（厂2 调和） xj 0, j=1,2,6,13,例 一个五位数的4倍（5、6、7、8 倍），正好数位反转过来，求这个数；不存在、唯一、多个？,解. 设这个数位数的数字是 a b c d e , 这个数是 Z,4(10000a+ 1000b+

11、100c+10d+e )=10000e+1000d+100c+10b+a 0 a,b,c,d,e 9, 整数 a, e 1,Max Z = 10000a + 1000b + 100c + 10d + e,Min Z = 10000a + 1000b + 100c + 10d + e,Zmax = Zmin = 21978（唯一）,14,例. 某公司拟在 A1 A7 中选址建立门市部，要求 A1 A2 A3 至多选两个 A4 A5 至少选一个 A6 A7 选一个 Ai 需要资金 bi ，年获利 ci ，总资金 B 年总获利最大，如何选点？,解. 令 xi = 1 ( yes) , xi = 0

12、( no ), 总利润 Z,Max Z = c1x1 +c7x7 s.t. x1 +x2 +x3 2 x4 +x5 1 x6 +x7 = 1 b1x1 + b7x7 B xj = 0或1，j = 17,15,例. 6 个区，每个区都可以设消防站；政府希望设置的消防站数量最少，但必须满足 15 分钟内赶到火警区域现场；在哪些区设消防站使总数最少？,解. 设 xi = 1(Yes), 0(No) 总数量 Z,Min Z=x1+x2+x3+x4+x5+x6,x1+ x2 1 x1+ x2+ x61 x3+ x4 1 x3+ x4+ x51 x4+ x5+ x61 x2+ x5+ x61 xj = 0

13、,1 j = 1, , 6,16,P.377 航班排程,总成本最小，航程方案？,17,设 12 个 0-1 变量 x j = 1（取第 j 航程），0（不取第 j 航程）,18,Min Z = 2x1+3x2+4x3+6x4+ +8x11+9x12 s.t. x1 + x2 + + x11 + x12 3 x1 + x4 + x7 + x10 1 x2 + x5 + x8 + x11 1 x3 + x6 + x9 + x12 1 x4 + x7 + x9 + x10 + x12 1 x1 + x6 + x10 + x11 1 x4 + x5 + x9 1 x7 + x8 + x10 + x11

14、 + x12 1 x2 + x4 + x5 + x 9 1 x5 + x8 + x11 1 x3 + x7 + x8 + x12 1 x6 + x9 + x10 + x11 + x12 1 xj = Bin. j = 1, ,12,最优解（P.380） x3*, x4*, x11* = 1 Z* = 18 (千元),19,例. 有出租车票若干，允许报销一定数额的发票，如何做？,20,例 修污水处理站，备选的站址有3个；每年清除8万吨污染物1和6万吨污染物2；要求年运营费和年处理费总和最小。,解. 设第i站yi=1(Yes), 0(No)；处理量xi(万吨)；总费用Z(万元),Min Z = 0

15、.02x1+0.03x2+0.04x3+400y1+300y2+250y3,s.t. 80 x1+50 x2 +40 x3 80000 60 x1+40 x2 +50 x3 60000 x1 800y1 x2 500y2 x3 400y3 xi 0, yi = 0,1, i=1,2,3,最优解 Y* = ( 1, 0, 1 ) X* = (800, 0, 400) Z* = 682 (万元),21,例 某钻井队要从 s1s10 十个井位中确定 5 个，使总费用最少；已知 si 钻井费 ci ，要求 1要么取 s1和s7 ，要么取 s8 （二居一） 2取 s3或/和s4 ，就不能取 s5 ，反之

16、亦然 （三个都不取也可） 3s5 s6 s7 s8中最多取两个,解. 设 xi = 1（Yes） xi = 0 （No） 总费用Z,22,例 篮球队从 6 名队员中选 3 名正式队员，平均身高最高,至少一名后卫 李田只取一名 最多一名中锋 要么李或/和赵， 要么周（二居一）,23,例 变量（线性函数 f(X) ）的特殊取值,x3 or f(X) = 0, 5, 9, 12,可转化为,24,例. 44排列,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16,解. Max Z = x1 s.t. x1 + x2 + x3 + x4 = 34 x1 + x6+ x11 +

17、x16 = 34 1 xj 16，Int. j =1,2, ,16,xi xj （如何实现 ？）,25,解. Max Z = x1 s.t. x1 + x2 + x3 + x4 = 34 x1 + x6+ x11 + x16 = 34 x1 = y1 + 2y2 + + 15y15 + 16y16 x16 = y241 + 2y242 + + 15y255 + 16y256 y1 + y2 + + y16 = 1 y241 + y242 + + y256 = 1 y1 + y17 + + y241 = 1 y16 + y32 + + y256 = 1 xj 0, Int. yi = Bin.

18、All i, j,（可消去 x 减少变量）,26,3. 运输问题,总运费最小， 调运方案？,解. 约束关系 运出量 与 产量 接收量 与 需量,总费用 = SUMPRODUCT（单位物资运费，调运量）,27,P.113 网络配送,（平衡运输）如何运送，总成本最小？,解,Min C = SUMPRODUCT（单位运输成本，运送量） x11+x12+x13 = 12 x21+x22+x23 = 15 x11+x21 = 10 x12+x22 = 8 x13+x23 = 9 x11, , x23 0,（P.116）最小总费用 = $20,500,28,P.203 分配资源（需产）,总成本最小，如何调

19、水？,解（P. 204） “” 添加约束 “产量 = 0 ”,最小总成本 = 1,975 $millions,29,P.201 选择顾客（高低需求运输）,顾客 1 应满足需求，顾客 2、3 只满足 1/3 需求，顾客 4 可以不给；总利润最大，如何供给？,解（P. 202）,最大总利润 = $1,076,000,30,P.207 划分区域（高低需求运输）,如何划分，总人英里数最小？,31,解（P.209）,最少人英里数 = 3,530,注：同一个区域学生不允许被分割到不同学校，见P229,32,例. 月生产 270 吨糖分至A1A2A3仓库，库容 50, 100, 150 吨，再运往B1B5需

20、地；运价表如下，最佳调运方案？,解.,最小总运费 6100,33,270,分装？ 不计费,总费用最小？ 调运？,34,例. 生产交货 (积压费 0.15万元/台季) 总费用最低，生产交货？,解. 运输模型：,最小总费用 773,35,P.205 生产交货,总成本最小，如何生产交付？,解： 运 输 模 型,36,解（P.206）,最小总成本 = 77.4 $millions,37,P.211 案例 新炼油厂选址,配送中心 360万桶,炼油厂 360 万桶,油 田 360 万桶,表6-17单位 运费,最小运费,单位：亿元,表6-18单位 运费,最小运费,表6-19 运营费用,38,4. 任务指派问

21、题,问题： n 个人完成 n 项任务，一人一项 第 i 人干第 j 项任务的时间 cij 问： 如何指派使总时间最少？,案例 3. 可靠性分配问题 案例 9. 网络计划任务指派问题,39,指派问题表格表示,注 1 n 个不同行不同列的数，这些数总和最小 注 2 指派问题可以建立 0-1 规划模型 注 3 指派问题是特殊的运输问题,40,例 甲乙丙丁 4 人将一份说明书翻译成英日德俄 4 种文字，所用时间如下；总时间最少，最优指派方案？,41,P.220 标准指派,总费用最小，如何指派？,解（P. 222） 时间每小时工资 指派问题,最小总费用 = $1957,42,例 选 4 名运动员参加仰、

22、蛙、碟、自由泳 200 米接力赛，使总时间最少；平时成绩如下,最优指派方案 X* = (甲, 自由) (乙, 蝶) (丙, 仰) (丁, 蛙) (戊, 休息) 总时间最少 Z* = 126.2 秒,43,P.229 学生指派,原最优解 1. 区域5 学生被分割给学校1、学校2 2. 容量最大的学校1只满足最小招生量1200 新条件 1. 每个区域指派一个学校 2. 每所学校招收三个区域,P.207 划分区域（新条件）,解 人英里数 = 距离学生数 指派问题（ 一个区到一个学校，一个学校接收三个区） 最优解 区域 2、3、5 学生 学校 1 区域 1、4、7 学生 学校 2 区域 6、8、9 学

23、生 学校 3 最小总人英里数 = 3,560,44,例 子系统串联，系统可靠性(乘积)最大，指派方案？,解：取对数变为求和指派,最大可靠性 0.48,45,5. 0-1变量应用,例 资源选用（约束条件取舍） 设资源利用例中资源1、2只能用一种 即第1、2个约束条件只能取一个（起作用） 原模型,Max Z = 2x1 + 3x2 s.t. 2x1 +2x2 12 x1 +2x2 8 （ 第2资源允许超额 ） 4x1 16 4x2 12 x1， x2 0，整数,46,两个线性规划,Max Z1 = 2x1 + 3x2 2x1 +2x2 12 4x1 16 4x2 12 x1, x2 0, 整数 最

24、优解 X1*, Z1*,Max Z2 = 2x1 + 3x2 x1 +2x2 8 4x1 16 4x2 12 x1, x2 0, 整数 最优解 X2*, Z2*,比较 Z1* 和 Z2* ，取 X1* 还是 X2* ？,47,引进0-1变量将两个 LP 合并成一个LP（混合型）,设 yi = 0 用第 i 种资源（取约束） yi = 1 不用第 i 种资源（舍约束）,Max Z = 2x1+ 3x2 s.t. 2x1+2x2 12 x1+2x2 8 4x1 16 4x2 12 x1, x2 0, 整数,y1, = 0, 1,+ My1,+ 0y1,y2,- My2,+ 0y2,y1+ y2 = 1,X* =（x1*, x2*, y1*, y2*）T ， Z*,48,例 等式约束取舍 2x1+3x2 = 5 应改为 5 2x1