浙江大学管理学院ppt课件

1、n狭义的管文科学：数理方法制定管理决策狭义的管文科学：数理方法制定管理决策 n Management Science = Operations research n (MS=OR) n 决策制定主体、环境、过程决策制定主体、环境、过程n 定量分析数学、概率、统计定量分析数学、概率、统计n 运筹方法问题、建模、处理运筹方法问题、建模、处理 n 定性分析的方法定性分析的方法n 德尔菲方法德尔菲方法n 小组讨论小组讨论n n 定量模型的运用定量模型的运用n 运筹模型运筹模型n 管文科学的方法论管文科学的方法论运筹方法处理典型管理问题运筹方法处理典型管理问题解决方法解决方法典型的办法典型的办法 财务模

2、型财务模型 线性规划线性规划 目标规划目标规划 预预 测测 网络分析网络分析 决策分析决策分析 库存模型库存模型 概率统计概率统计 排队模拟排队模拟盈亏平衡与经营安全分析盈亏平衡与经营安全分析在线性目标和约束条件下取得最优结果在线性目标和约束条件下取得最优结果在多个相对立的目标下寻得合理结果在多个相对立的目标下寻得合理结果设计时间序列，或找到因果关系设计时间序列，或找到因果关系用各种活动和事件的网络排列来说明项目计划用各种活动和事件的网络排列来说明项目计划风险决策与不确定决策的基本方法风险决策与不确定决策的基本方法寻求使库存成本降至最低的存储策略寻求使库存成本降至最低的存储策略数学期望与概率分

3、布数学期望与概率分布分析等待的队列分析等待的队列, ,模拟合理作业时间和资源利用模拟合理作业时间和资源利用第三章第三章 线性规划模型线性规划模型n决策变量本身能否有限制条决策变量本身能否有限制条件？件？第三章第三章 线性规划模型线性规划模型nnxcxcxcz 2211max(min)mnmn22m11m2nn22221211nn1212111b).(xaxaxab).(xaxaxab).(xaxaxa. t . s第三章第三章 线性规划模型线性规划模型nn一切参数一切参数a、b、c都应是确定值都应是确定值n决策变量的非负性决策变量的非负性第三章第三章 线性规划模型线性规划模型 Max z =

4、X1+3X2 s.t. X1+ X26 -X1+2X28 X1 , X20z=0z=3z=6z=9z=12z=15.30 1 2 3 4 5 6-8 -7 -6 -5 -4 -3 -2 -1654321x1x2目的函数等值线目的函数等值线Z = X1+3X2可行域可行域(4/3,14/3)第三章第三章 线性规划模型线性规划模型n对偶问题与影子价钱对偶问题与影子价钱n 定义：定义： 设以下线性规划问题设以下线性规划问题n MAX Z = CTXn s.t. AXb X0n 为原始问题，那么称以下问题为原始问题，那么称以下问题n MIN W = bTYn s.t. ATYC Y0n 为原始问题的对

5、偶问题，最优为原始问题的对偶问题，最优值值Y为影子价钱为影子价钱 第三章第三章 线性规划模型线性规划模型n对偶问题与原始问题的关系目标极大化问题极大化问题 Cj（max Z）极小化问题极小化问题bi（min W）目标变变量量nxj0 aTijyicj约约束束nxj无约束无约束 aTijyi=cjxj0 aTijyicj约约束束m aijxjbiyi0变变量量m aijxj=biyi无约束无约束 aijxjbiyi0么么 X*,Y*为最优解的充分必要条件是为最优解的充分必要条件是Y*XL=0和和YSX*=0。第三章第三章 线性规划模型线性规划模型原问题规范型：原问题规范型：Max Z= CXAX

6、 + XL= bX,XL0对偶问题规范型：对偶问题规范型：Min W= YbYA - YS= CY,YS0第三章第三章 线性规划模型线性规划模型原问题和对偶问题的互补松松弛关系：原问题和对偶问题的互补松松弛关系：第三章第三章 线性规划模型线性规划模型对偶问题求解举例：对偶问题求解举例：对以下线性规划问题：对以下线性规划问题： MIN Z2X1X22X3 s.t. X1X2X34 X1X2KX36 X10，X2 0，X3 无约无约束束知其最优解为知其最优解为 X1* =5 , X2* = 0 , X3* =1。写出其对偶问题并求其最优解和写出其对偶问题并求其最优解和 K 的值。的值。写出对偶问题

7、：写出对偶问题： MAX W = 4Y1+6Y2 s.t. -Y1-Y2 2 Y1+Y2-1 Y1-KY2=2 Y20根据对偶性质：根据对偶性质： 4Y1+6Y2 = -12 -Y1-Y2 =2 Y1-KY2=2Y1*=0,Y2*=-2,K=1 第三章第三章 线性规划模型线性规划模型第三章第三章 线性规划模型线性规划模型n展展n义务指派问题线性规划问题扩义务指派问题线性规划问题扩展展第四章第四章 线性规划的扩展线性规划的扩展n第四章第四章 线性规划的扩展线性规划的扩展第四章第四章 线性规划的扩展线性规划的扩展nX=0,1 等价于X1, X0 且取整数。nn 0-1规划问题求解：思绪与LP、IP

8、问题一致。n教材P8183 实例4.7、实例4.8 jnjjXCz1maxmibXanjijij,.2 , 1,1 思索固定本钱的最小消费费用问题 某工厂有三种设备均可消费同一产品，第j种设备运转的固定本钱为dj，运转的单位变动本钱为cj，那么消费本钱与产量xj的关系为： j=1,2,3 如何使设备运转的总本钱最小？ 0 xxcd0 x0)x(fjjjjjjj当当第四章第四章 线性规划的扩展线性规划的扩展引入01变量 yj ， 令 建立以下模型：这里M是一个很大的正数。当yj=0时，xj=0，即第j种设备不运转，相应的运转本钱 djyj+cjxj=0当yj1时，0 xjM，实践上对xj没有限制

9、，运转本钱为 dj+cjxj 这是一个混合0-1规划问题 1 , 0, 03 , 2 , 1. .)(min31jjjjjjjjjyxjMyxtsxcydz0 x种设备时，即j当采用第10 x种设备时，即j当不采用第 0jjjy第四章第四章 线性规划的扩展线性规划的扩展互斥约束的处置：如：互斥约束的处置：如：f(x) a (a0) 当问题需求同时思索一对分段约束时，如何将其当问题需求同时思索一对分段约束时，如何将其同时出如今模型中非线性变成线性：同时出如今模型中非线性变成线性： 如：如： f(x)-30 (1) ; f(x)0 (2) 经过引入一个经过引入一个01整数变量整数变量 y 和一个充

10、分大的正和一个充分大的正实数实数M, 可化为：可化为： f(x)+3My (3) f(x) M(1-y) (4) 当当y=0时，时，(3)=(1), (4)自然成立，不起作用自然成立，不起作用 当当y=1时，时，(4)=(2),(3)为：为：3M+f(x),当当M很很大时也自然成立，因此也不起作用。大时也自然成立，因此也不起作用。 3和和4可同时进入模型约束。可同时进入模型约束。第四章第四章 线性规划的扩展线性规划的扩展多中选一的处置： 模型希望在以下n个约束中，只能有一个约束有效： fi (x) 0 (i=1,2,n) 1 引入n个01整数变量yi ,(i=1,2,n),可将上式改写为： f

11、i (x) M(1- yi) (i=1,2,n), (2) (3) M为恣意大的正数。 (2) : 当yi1 时 ，(2)=(1) ; yi 0 时，自然满足 (3) : 保证了yi 有且只需一个取值为1，其他为0。 11niiy第四章第四章 线性规划的扩展线性规划的扩展多中选一的处置： 模型希望在以下n个约束中，只能有一个约束有效： fi (x) 0 (i=1,2,n) 1 引入n个01整数变量yi ,(i=1,2,n),可将上式改写为： fi (x) M(1- yi) (i=1,2,n), (2) (3) M为恣意大的正数。 (2) : 当yi1 时 ，(2)=(1) ; yi 0 时，自

12、然满足 (3) : 保证了yi 有且只需一个取值为1，其他为0。 11niiy第四章第四章 线性规划的扩展线性规划的扩展多中选一的处置： 模型希望在以下2个约束中，只能有一个约束有效： 3X1+4X2 5，4X3-2X2 3 引入2个01整数变量yi ,(i=1,2),可将上式改写为： Y=1时不采用，Y0时采用 3X1+4X2 5 + MY1 4X3-2X2 3 +MY2 Y1+Y2=1 M为恣意大的正数。第四章第四章 线性规划的扩展线性规划的扩展第四章第四章 线性规划的扩展线性规划的扩展n Xij = n 0 当不指派当不指派Ai去去完成完成Bj任务任务第四章第四章 线性规划的扩展线性规划

13、的扩展n指派问题数学模型的规范型n n MIN Z = Cij0)n i= 1,2,n)n n (j= 1,2,n)n Xij 皆为 0 或 1n 由 Cij 组成的方阵 C = ( Cij )nn 称为效率矩阵 ninjCijXij11njXij11niXij11第四章第四章 线性规划的扩展线性规划的扩展n指派问题规范型的求解匈牙利法指派问题规范型的求解匈牙利法n 指派问题有以下性质：指派问题有以下性质：n 假设从效率矩阵假设从效率矩阵C的任何一行列各的任何一行列各元素中分别减去一个常数元素中分别减去一个常数KK可正可负得可正可负得到新矩阵到新矩阵D,那么以那么以D为效率矩阵的指派问题为效率

14、矩阵的指派问题与原问题有一样的解，但最优值比原问题最与原问题有一样的解，但最优值比原问题最优值小优值小K。n n 用匈牙利法求解的条件：用匈牙利法求解的条件：n MIN、i=j 、Cij0第四章第四章 线性规划的扩展线性规划的扩展n匈牙利法的主要步骤：匈牙利法的主要步骤：n 第一步：变换效率矩阵，使在各行各列都出第一步：变换效率矩阵，使在各行各列都出现零元素。现零元素。n 1、从矩阵、从矩阵C的每行元素减去该行的最小元的每行元素减去该行的最小元素；素；n 2、再从所得矩阵的每列中减去该列最小元、再从所得矩阵的每列中减去该列最小元素。素。n 第二步：以最少数目的程度线和垂直线划去第二步：以最少数

15、目的程度线和垂直线划去一切的零元素。假设所用的直线等于行或列数，一切的零元素。假设所用的直线等于行或列数，那么终了指派。否那么继续。那么终了指派。否那么继续。n 第三步：找到没有被划去的最小的元素，一第三步：找到没有被划去的最小的元素，一切没有被划中的元素减去这一最小值。而被划切没有被划中的元素减去这一最小值。而被划中两次的元素该元素行列都被划中那么要中两次的元素该元素行列都被划中那么要加上这一最小值。再前往到第一步。加上这一最小值。再前往到第一步。n 第四步：最后根据零元素的位置，确定最优第四步：最后根据零元素的位置，确定最优分配方案。分配方案。练习题：建立线性规划模型练习题：建立线性规划模

16、型练习题练习题1：建立线性规划模型：建立线性规划模型n确定决策变量：确定决策变量：n X1，X2，X3为每月买进的商品量为每月买进的商品量n Y1，Y2，Y3为每月卖出的商品量为每月卖出的商品量n确定目的函数：确定目的函数：n MAX Z=3.31Y1+3.25Y2+2.95Y3n -2.85X1-3.05X2-2.90X3n确定约束条件：确定约束条件：n买进的商品当月到货下月卖出，每月卖出的量应买进的商品当月到货下月卖出，每月卖出的量应小于月初时的库存量小于月初时的库存量n在买卖时间没有严厉要求的情况下，先卖再买总在买卖时间没有严厉要求的情况下，先卖再买总是有利的，因此每月最大库存量为月初库

17、存减去是有利的，因此每月最大库存量为月初库存减去卖出再加上买进的量卖出再加上买进的量练习题练习题1：建立线性规划模型：建立线性规划模型 月初库存量月初库存量 买进买进 卖卖出出 一月一月 1000 X1 Y1 二月二月 1000Y1+X1 X2 Y2 三月三月 1000Y1+X1-Y2+X2 X3 Y3 因此：因此： Y1 1000 Y2 1000Y1+X1 Y3 1000Y1+X1-Y2+X2每月库存容量最多为每月库存容量最多为5000，三月末为，三月末为2000 ： 一月：一月： 1000Y1+X1 5000 二月：二月： 1000Y1+X1-Y2+X2 5000 三月：三月： 1000Y

18、1+X1-Y2+X2-Y3+X2 = 2000练习题练习题1：建立线性规划模型：建立线性规划模型n每月进货的资金应小于拥有的资金和卖出商品每月进货的资金应小于拥有的资金和卖出商品的收入之和：先卖再买的收入之和：先卖再买n 一月：一月：2.85 X1 20000 + 3.10 Y1n 二月：二月：3.05 X2 20000 + 3.10 Y1n -2.85X1+3.25Y2n 三月：三月：2.90 X3 20000 + 3.10 Y1n -2.85X1+3.25Y2n -3.05X2+2.95Y3nX1,X2,X3,Y1,Y2,Y3非负整数非负整数n 练习题练习题2：建立线性规划模型：建立线性规

19、划模型练习题练习题2：建立线性规划模型：建立线性规划模型n决策变量确定：能否投资需求决策决策变量确定：能否投资需求决策n n X11，X12，X21，X31 均为均为01变量变量n约束条件确定：约束条件确定：n第一种产品的方案一和方案二最多只能选一：第一种产品的方案一和方案二最多只能选一：n X11+X12 1n第二种产品、第三种产品可选也可不选：第二种产品、第三种产品可选也可不选：n X21 1 ， X31 1n 全部投资额应不超越全部投资额应不超越550万万n 300X11+280X12+260X21+240X31 550第一种产品第一种产品方案方案1 方案方案2X11 X12第二种产品第

20、二种产品X21第三种产品第三种产品X31练习题练习题2：建立线性规划模型：建立线性规划模型n目的函数确定：每年的收益和最大n 每年的总收益包含两部分：n第一部分：工程投资收益，利用投资回收系数n第二部分：剩余资金的普通投资收益1)26. 01 ()26. 01 (26. 03124010.28)(10.28)0.28(1X212601)28. 01 ()28. 01 (28. 0122801)3 . 01 ()3 . 01 (3 . 01130055555555XXX1) 1 . 01 () 1 . 01 ( 1 . 0)31240212601228011300(55055XXXXn练习题练习

21、题3：n n 有张、王、李、赵有张、王、李、赵4位教师被分配教语文、位教师被分配教语文、数学、物理、化学数学、物理、化学4门课程，每位教师教一门门课程，每位教师教一门课程，每门课程由一位教师教。根据这四位课程，每门课程由一位教师教。根据这四位教师以往教课的情况，他们分别教这四门课教师以往教课的情况，他们分别教这四门课程的平均成果如下表：程的平均成果如下表：n 四位教师每人只能教一门课，每一门课四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成果之和为最高。哪一门课，使四门课的平均成果之和为最高。n 结果：张化

22、学结果：张化学76 王物理王物理77 n 李数学李数学90 赵语文赵语文93 指派问题线性规划模型举例指派问题线性规划模型举例n设设xiji=1, 2, 3, 4；j=1, 2, 3, 4为第为第i个教师能否教第个教师能否教第j门课，门课，xij只能取值只能取值0或或1，这个指派问题的线性规划模型，这个指派问题的线性规划模型为：为：nmax z= 92x11+68x12+85x13+76x14+82x21 +91x22+77x23+63x24+83x31+90 x32+74x33n +65x34+93x41+61x42+83x43+75x44ns.t.x11+x12+x13+x14=1 1n

23、x21+x22+x23+x24=1 2n x31+x32+x33+x34=1 3n x41+x42+x43+x44=1 4n x11+x21+x31+x41=1 5n x12+x22+x32+x42=1 6n x13+x23+x33+x43=1 7n x14+x24+x34+x44=1 8n xij=0, 1 x14=1，x23=1，x32=1，x41=1，max z=336 第四章第四章 线性规划的扩展线性规划的扩展地的要求，又使总的运输费用或地的要求，又使总的运输费用或里程、时间等最小。里程、时间等最小。第四章第四章 线性规划的扩展线性规划的扩展 设有同一种货物从m个出发地1，2，m运往n

24、个到达地1，2，n。第i个出发地的供应量Supply为sisi0， 第j个到达地的需求量Demand为 djdj0。 每单位货物从产地 i 运到销地 j 的运价为Cij。求一个使总运费最小的运输方案。 1 2 3 n 供应 1 c11 c1n s1 2 c21 本钱 c2n s2 cij m cm1 cmn sm 需求 d1 dn 出发地到达地第四章第四章 线性规划的扩展线性规划的扩展ninjCijXij11njiSXij1mijdXij1n产销平衡的运输问题模型产销平衡的运输问题模型n 令令Xij为为 从从i地运到地运到j地的数量地的数量n MIN Z = Cij0)n i= 1,2,m)

25、供应约供应约束束n n (j= 1,2,n) 需求约束需求约束n n Xij0n 由由 Cij、Si、dj 组成的组成的 (m+1)(n+1) 矩阵称为运输矩阵矩阵称为运输矩阵第四章第四章 线性规划的扩展线性规划的扩展n目的约束：把约束右端项看成是要追目的约束：把约束右端项看成是要追求的目的值，求的目的值，在到达此目的时允许在到达此目的时允许有正负偏向，线性规划问题的目的函有正负偏向，线性规划问题的目的函数，在给定目的值和参与正、负偏向数，在给定目的值和参与正、负偏向后可变换为目的约束，也可将绝对约后可变换为目的约束，也可将绝对约束变换为目的约束。束变换为目的约束。第四章第四章 线性规划的扩展

26、线性规划的扩展要求恰好到达目的值正负偏向都要尽能够地要求恰好到达目的值正负偏向都要尽能够地小，这时小，这时 MIN Z = fd+ d- )要求不超越目的值允许达不到，正偏向要尽能要求不超越目的值允许达不到，正偏向要尽能够地小够地小 MIN Z = fd+ )要求不低于目的值：要求不低于目的值： MIN Z = fd- )练习：建立目的规划模型某单位指点在思索本单位职工的晋级调资方案时，依次遵守以下某单位指点在思索本单位职工的晋级调资方案时，依次遵守以下规定：规定：不超越年工资总额不超越年工资总额60000元；元；每级的人数不超越定编规定的人数；每级的人数不超越定编规定的人数；II，III级的

27、晋级面尽能够到达现有人数的级的晋级面尽能够到达现有人数的20；III级缺乏编制的人数可录用新职工，又级缺乏编制的人数可录用新职工，又I级的职工中有级的职工中有10 要退要退休。休。有关资料汇总于下表中，问该指点应如何拟定一个称心的方案。有关资料汇总于下表中，问该指点应如何拟定一个称心的方案。等级工资额（元/年）现有人数编制人数IIIIII200015001000101215121515合计3742目的规划求解：目的规划求解：n设设X1,X2,X3分别表示提升到分别表示提升到I,II级和录用级和录用到到III级的人数。级的人数。n优先因子优先因子P1:不超年工资总额不超年工资总额60000元元n

28、 优先因子优先因子P2:每级人数不超越定编人数每级人数不超越定编人数 n 优先因子优先因子P3:II,III级晋级面尽能够到级晋级面尽能够到达达n建立目的约束：建立目的约束：n 2000(10100.1X1)+1500(12-X1+X2)+1000(15-X2+X3)+d1d1+=60000目的规划求解：目的规划求解：每级人数不超越定编人数：每级人数不超越定编人数： I级有：级有：10(1-0.1)+X1+d2-d2+=12II级有：级有：12-X1+X2+d3- -d3+=15III级有：级有：15-X2+X3+d4- -d4+=15II,III级晋级面不大于现有人数的级晋级面不大于现有人数

29、的20，但，但尽能够多提；尽能够多提；对对II级有：级有：X1+d5- -d5+=120.2对对III级有：级有：X2+d6- -d6+=150.2目的函数：目的函数： MIN Z=P1 d1+P2(d2+ d3+ + d4+ )+P3(d5- +d6- )第四章第四章 线性规划的扩展线性规划的扩展nn动态规划没有规范模型，没有独一动态规划没有规范模型，没有独一确定的解法确定的解法决策决策1决策决策2决策决策3决策决策n1形状形状123n形状形状n形状形状4形状形状3形状形状2阶段阶段1阶段阶段2阶段阶段3阶段阶段n第四章第四章 线性规划的扩展线性规划的扩展n允许采取决策的全体。允许采取决策的

30、全体。n形状转移方程形状转移方程Xk+1=T(Xk,dk)：某一：某一形状以及该形状下的决策，与下一形状形状以及该形状下的决策，与下一形状之间的函数关系。之间的函数关系。第四章第四章 线性规划的扩展线性规划的扩展n最优化原理最优化原理n 最正确途径中任一形状中间点到最最正确途径中任一形状中间点到最终形状最终点的途径也是该形状到最终形状最终点的途径也是该形状到最终形状一切能够中的最短途径。终形状一切能够中的最短途径。CjABiCjDtE阶段1阶段2阶段3阶段4Dt第四章第四章 线性规划的扩展线性规划的扩展动态规划练习动态规划练习第四章第四章 线性规划的扩展线性规划的扩展S1=2S4=0S3=2S

31、3=1S3=0S2=2S2=1S2=00.060.480.300.160.300.500.800.300.500.800.200.400.600.600.400.600.150.200.40第一组第一组第三组第三组第二组第二组剩余人数剩余人数效率最高？效率最高？n系统时间加工时间排队系统时间加工时间排队时间时间n延误的任务项数最少延误的任务项数最少n 先按先到期者优先的原那么排初先按先到期者优先的原那么排初次次序次次序 n 假设没有延误的任务，那么是最假设没有延误的任务，那么是最优解。优解。n 假设有延误的任务，那么找出其假设有延误的任务，那么找出其中的一项，找出到此项任务之前包中的一项，找出

32、到此项任务之前包括该项加工时间最长的一项，并将括该项加工时间最长的一项，并将之抽去，重新安排时间，假设已没有之抽去，重新安排时间，假设已没有延误的任务，那么将被抽取的这一项延误的任务，那么将被抽取的这一项放置最后；如仍有被延误的任务，那放置最后；如仍有被延误的任务，那么再反复这一步。么再反复这一步。n时序规划扩展约翰逊原那么：时序规划扩展约翰逊原那么：n 两台顺序机器完成一批任务两台顺序机器完成一批任务n n 每项任务在机器每项任务在机器1和机器和机器2上的上的加工时间不一样，如何使系统效率加工时间不一样，如何使系统效率最高？最高？ 3214机器机器1机器机器2任务任务n约翰逊原那么约翰逊原那

33、么n 找出各台机器上加工时间最短的一项找出各台机器上加工时间最短的一项任务，任务， n 假设在机器假设在机器1上，这项任务最先上，这项任务最先做；做；n 假设在机器假设在机器2上，这项任务最后上，这项任务最后做；做；n 不断反复，从两端往内排。一样时间不断反复，从两端往内排。一样时间可任选一可任选一 个，普通先安排机器个，普通先安排机器1上任务。上任务。n例例53：教材：教材P110 实例实例5.6n最小树最小树n 一个网络中有很多树，其中边的长一个网络中有很多树，其中边的长度权数之和为最小的树为最小树。度权数之和为最小的树为最小树。n最小树的获取破圈法最小树的获取破圈法n 从图中任取一个圈，去掉该圈的一从图中任取一个圈，去掉该圈的一条最大边，将此圈破去