模型决策法课件(PPT35张).ppt

1、章模型决策法章模型决策法 线性规划等线性规划等时序与路径规划时序与路径规划分派问题分派问题最短路问题最短路问题最大流问题最大流问题模型决策法优化模型max (min) 目标函数目标函数 s. t. 约束条件约束条件线性规划模型的建立线性规划模型的建立实例 1 两种产品的生产。已知生产单位产品所需的设备台时及A、B两种原材料的消耗，资源限制及市场价格如下表： 资源限制设备11300台时原材料A21400千克原材料B01250千克市场价格 50100 问题：如何安排生产，才能使工厂获利最多？规划与决策规划与决策分析：（1）设 x1 生产产品的数量； x2 生产产品的数量。（2）目标函数：MAX 5

2、0 x1+100 x2 （3）约束条件：subject to (s.t.): x1+x2 300 2x1+x2 400 x2 250 x1,x2 0 规划与决策规划与决策线性规划模型： max 50 x1+100 x2 s.t. x1+x2 300 2x1+x2 400 x2 250 x1,x2 0规划与决策规划与决策线性规划模型的一般形式线性规划模型的一般形式 max c1x1+c2x2+ + cn xn s. t. a11x1 + + a1nx n (,=) b1 a21x1 + + a2nx n (,=) b2 am1x1 + + amnx n (,=) bm xij 0 i = 1,

3、,n, j =1, ,m规划与决策规划与决策线性规划应用领域线性规划应用领域： 合理利用板、线材问题； 配料问题； 投资问题； 生产计划问题、劳动力安排问题； 运输问题、电子商务配送问题； 企业决策问题；企业或商业竞争对策问题等。规划与决策规划与决策一一般线性规划建模过程般线性规划建模过程Step 1. 理解及分析实际问题，资源状况，解决问题实现的目标；Step 2. 确定决策变量（x1, ，xn） 解决问题的具体方案（量化方案）；Step 3. 确定目标函数及约束条件；Step 4. 应用线性规划软件求解；Step 5. 检验所求得的解决方案是否可行：如可行，则开始具体实施；否则，转Step

4、 1 或 Step2 修改模型。规划与决策规划与决策案例2：（生产计划问题）某公司面临一个外协加工还是自行生产问题。该公司生产甲、乙、丙三种产品，这三种产品都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸造可以外协加工，亦可以自行生产。但丙产品的铸造必须自行生产才能保证质量。有关数据见下表：规划与决策规划与决策工时与成本甲乙丙总工时每件铸造工时（小时）51078000每件机加工工时（小时）64812000每件装配工时（小时）32210000自产铸件每件成本（元）354外协铸件每件成本（元）56-机加工每件成本（元）213装配每件成本（元）322每件产品售价（元）231816问题：如何安

5、排生产计划，使公司获利最大？规划与决策规划与决策分析：设 xi 公司加工甲、乙、丙三种产品数量，i=1,2,3。x4、x5由外协铸造后再由本公司机加工和装配的甲、 乙两种产品数量；目标函数： 每件产品利润分别是：每件x1产品利润: 23-（3+2+3） =15元每件x2产品利润: 18-（5+1+2） =10元每件x3产品利润: 16-（4+3+2） =7元每件x4产品利润: 23-（5+2+3） =13元每件x5产品利润: 18-（6+1+2） =9元目标函数为： max 15 x1+10 x2+7 x3+13 x4+9 x5规划与决策规划与决策约束条件： 5 x1+10 x2+7 x3 8

6、000 6 x1+4 x2+8 x3+6 x4+4 x5 12000 3 x1+2 x2+2 x3+3 x4+2 x5 10000 xi 0 i=1,5规划与决策规划与决策图解法:Step 1. 确定可行域 D = x | x 满足上述约束条件如下图2-1：Step 2. 确定直线 50 x1+100 x2=0如下图2-2：Step 3. 向上移动直线 50 x1+100 x2=0如图2-2，z=50 x1+100 x2 的值不断地增加，达到B点时， 达到最大；Step 4. 最优解为B=(50,250), z最大=27500。规划与决策规划与决策 0 100 200 300300200100

7、D图 2-1规划与决策规划与决策 0 100 200 300300200100DB(50,250)Z= 50 x1+100 x2图 2-2时序与路径规划时序与路径规划 讨论各种时序规划问题讨论各种时序规划问题 介绍时序规划原则介绍时序规划原则 分派问题分派问题 运输问题运输问题 网络的最短路径网络的最短路径 网络的最大流网络的最大流时序规划问题时序规划问题 ABEFDC机器机器DEFCAB等待处理的一批工作按最优次序排队一台机器工作的时序规划一台机器工作的时序规划时序规划问题时序规划问题原则：原则：(1) 最紧迫的优先最紧迫的优先实例实例 1： 6种部件作为一批等待一台机器加工。每一部件的平均

8、周需求量、当前的存货水平以及加工一批所需时间如下表，你将如何安排各种部件的生产次序？ 部 件 A B C D E F 平均需求量 10 4 26 34 7 3 当前存货量 72 21 48 92 28 23 加工时间 2.0 1.5 0.5 0.5 1.0 1.5时序规划问题时序规划问题 1最紧迫的优先最紧迫的优先23数据数据4项目ABCDEF5当前存货7221489228236平均需求1042634737存货用完的时间7,205,251,852,714,007,6789经整理的数据经整理的数据10存货用完的时间1,852,714,005,257,207,6711项目CDEBAF12当前存货4

9、8922821722313平均需求2634741031415生产时间0,50,51,01,52,01,516开始生产时间0,00,51,02,03,55,517完成生产时间0,51,02,03,55,57,018容余时间1,41,72,01,81,70,7时序规划问题时序规划问题 23数据数据4项目ABCDEF5当前存货7221489228236平均需求1042634737存货用完的时间7,205,251,852,714,007,6789经整理的数据经整理的数据10存货用完的时间1,852,714,005,257,207,6711项目CDEBAF12当前存货48922821722313平均需求

10、2634741031415生产时间0,50,51,01,52,01,516开始生产时间0,00,51,02,03,55,517完成生产时间0,51,02,03,55,57,018容余时间1,351,7121,751,70,67时序规划问题时序规划问题 ABCDEFGHI1加工时间最短者优先加工时间最短者优先23数据数据4工作ABCDEFGH5加工时间2538472367整理后数据整理后数据8工作AGCHEBFD9加工时间223345781011 开始加工时间0,02,04,07,010,014,019,026,012 完成加工时间2,04,07,010,014,019,026,034,0以“加

11、工时间最短者优先”为原则时序规划问题时序规划问题 23数据数据4工作ABCDEFGH5加工时间2538472367整理后数据整理后数据8工作AGCHEBFD9加工时间223345781011 开始加工时间0,02,04,07,010,014,019,026,012 完成加工时间2,04,07,010,014,019,026,034,0以“加工时间最短者优先”为原则时序规划问题时序规划问题(3) 到期日最近者原则到期日最近者原则BCDEFGHIABCDEFGH1378301420236GBCAEFDH2781314203036253247830,02,07,010,012,016,023,031

12、,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0时序规划问题时序规划问题(3) 到期日最近者原则到期日最近者原则BCDEFGHIABCDEFGH1378301420236GBCAEFDH2781314203036253247830,02,07,010,012,016,023,031,02,07,010,012,016,023,031,034,00,00,02,00,02,03,01,00,0时序规划问题时序规划问题(4) 延误的工作项目最少延误的工作项目最少第1步：运用先到期者优先的原则排出工作的初始次序。如果已经没有工作被延误，

13、这便是最优解，否则，则进行第2步。第2步：在安排的时序中找到1项延误的工作。第3步：找出第2步所找工作之前（包括这一工作本身）加工时间最长的工作。第4步：将这一工作从时序安排中抽出来，并更新相应的时间。如果仍然有被延误的工作，再转向第2步，否则转向第5步。第5步：将第4步抽出的工作放到时序的末尾。实例实例 3：沿用上述实例的8项工作，求解工作延误项数最少的时序。 为此我们采用上述五个步骤。 工 作 A B C D E F G H 加工时间 2 5 3 8 4 7 2 3 到期时间 13 7 8 30 14 20 2 36时序规划问题时序规划问题第1步：将工作按到期时间排序。 工 作 G B C

14、 A E F D H 到期时间 2 7 8 13 14 20 30 36 开始加工时间 0 2 7 10 12 16 23 31 加工时间 2 5 3 2 4 7 8 3 完成加工时间 2 7 10 12 16 23 31 34 延误工作 * * * * 第2步：在上述时序中，第1项被延误的工作是C。第3步：到C之前，包括C在内，加工时间最长的工作是B，加工时间为5。时序规划问题时序规划问题第4步：抽出工作B，更新相关的时间： 工 作 G C A E F D H 到期时间 2 8 13 14 20 30 36 开始加工时间 0 2 5 7 11 18 26 加工时间 2 3 2 4 7 8 3

15、 完成加工时间 2 5 7 11 18 26 29第5步：现在已经没有工作被延误了，所以我们将工作B加到时序的最后。 工 作 G C A E F D H B 到期时间 2 8 13 14 20 30 36 7 开始加工时间 0 2 5 7 11 18 26 29 加工时间 2 3 2 4 7 8 3 5 完成加工时间 2 5 7 11 18 26 29 34 现在只有一项工作被延误，平均排队时间为98/8=12.25，平均延误时间为27/8=3.375天。时序规划问题时序规划问题(5) Johnsons rule(约翰逊原则约翰逊原则)步骤1：列出各项工作及它们在每台机器上的加工时间。步骤2：

16、找出下一个在各台机器上加工时间最短的工作。步骤3：如果这是在机器1上，尽量将这一工作安排在前面；如果这是在机器2上，尽量将这一工作安排在后面。在重复做这些的时候，总是从时序的两端向内进行，新安排的工作离时序的中间更近。步骤4：不必再考虑这一工作，回到步骤2。如果再找不到这样的任务，这就是最优解。 实例 4： 有7项工作要顺序经过机器1和机器2加工。每项工作在每台机器上所需的加工时间如下，如何安排时序才能使机器利用率最高。 工作 A B C D E F G 机器1 2 5 10 8 4 12 9 机器2 14 7 3 10 5 6 6时序规划问题时序规划问题 ABCDEFGH1约翰逊原则约翰逊原

17、则23工作ABCDEFG4在机器1上的时间2510741295在机器2上的时间14731056667最优时序AEBDGFC8在机器1上开始的时间026111928409在机器1上完成的时间26111928405010 在机器2上开始的时间216212838445011 在机器2上完成的时间16212838445053时序规划问题时序规划问题 23工作ABCDEFG4在机器1上的时间2510741295在机器2上的时间14731056667最优时序AEBDGFC8在机器1上开始的时间026111928409在机器1上完成的时间26111928405010 在机器2上开始的时间2162128384

18、45011 在机器2上完成的时间16212838445053分派问题分派问题如何以总成本最低为目标将操作员分派到各台机器上。原则：每个操作员只能分派给一项任务，每项任务只能由一人完成。 Cij 第i个操作员完成第j项任务的成本 Xij min CijXij Xij=1 Xij=1 Xij=0,1 i=1,n, j=1,m=1 (分派操作员i完成任务j)=0 (不分派操作员i完成任务j)ji最短路问题最短路问题最短路问题G(V,E) 为 连通图，边（vi,vj)的权为lij，求一条道路，使它从vs到vt的总权最少？方法：1 动态规划法 2 Dijkstra算法引例：某一配送中心要给一个快餐店送快

19、餐原料，应按什么路线送货才能使送货时间最短？V2 16 v4 7 v64 6V1 12 2 8 v718 5V3 6 v5（配送中心）（快餐店）最大流问题最大流问题最大流问题引例：某石油公司拥有一个管道网络（如图），使用这个网络可以把石油从采地运送到一些销售地。弧上的数字为该管道的容量， 问如果使用这个网络系统从v1向销地v7运送石油， 每小时能运送多少石油？v1V2 ( 3,0) v5(6,0) (2,0) (2,0) (5,0)v3V6 v7(6,0) (3,0) (1,0) (2,0)v4(2,0) (4,0) 1、最孤独的时光，会塑造最坚强的自己。2、把脸一直向着阳光，这样就不会见到阴

20、影。3、永远不要埋怨你已经发生的事情，要么就改变它，要么就安静的接受它。4、不论你在什么时候开始，重要的是开始之后就不要停止。5、通往光明的道路是平坦的，为了成功，为了奋斗的渴望，我们不得不努力。6、付出了不一定有回报，但不付出永远没有回报。7、成功就是你被击落到失望的深渊之后反弹得有多高。8、为了照亮夜空，星星才站在天空的高处。9、我们的人生必须励志，不励志就仿佛没有灵魂。10、拼尽全力，逼自己优秀一把，青春已所剩不多。11、一个人如果不能从内心去原谅别人，那他就永远不会心安理得。12、每个人心里都有一段伤痕，时间才是最好的疗剂。13、如果我不坚强，那就等着别人来嘲笑。14、早晨给自己一个微

21、笑，种下一天旳阳光。15、没有爱不会死，不过有了爱会活过来。16、失败的定义：什么都要做，什么都在做，却从未做完过，也未做好过。17、当我微笑着说我很好的时候，你应该对我说，安好就好。18、人不仅要做好事，更要以准确的方式做好事。19、我们并不需要用太华丽的语言来包裹自己，因为我们要做最真实的自己。20、一个人除非自己有信心，否则无法带给别人信心。21、为别人鼓掌的人也是在给自己的生命加油。22、失去金钱的人损失甚少，失去健康的人损失极多，失去勇气的人损失一切。23、相信就是强大，怀疑只会抑制能力，而信仰就是力量。24、那些尝试去做某事却失败的人，比那些什么也不尝试做却成功的人不知要好上多少。

22、25、自己打败自己是最可悲的失败，自己战胜自己是最可贵的胜利。26、没有热忱，世间便无进步。27、失败并不意味你浪费了时间和生命，失败表明你有理由重新开始。28、青春如此华美，却在烟火在散场。29、生命的道路上永远没有捷径可言，只有脚踏实地走下去。30、只要还有明天，今天就永远是起跑线。31、认真可以把事情做对，而用心却可以做到完美。32、如果上帝没有帮助你那他一定相信你可以。33、只要有信心，人永远不会挫败。34、珍惜今天的美好就是为了让明天的回忆更美好。35、只要你在路上，就不要放弃前进的勇气，走走停停的生活会一直继续。36、大起大落谁都有拍拍灰尘继续走。37、孤独并不可怕，每个人都是孤独

23、的，可怕的是害怕孤独。38、宁可失败在你喜欢的事情上，也不要成功在你所憎恶的事情上。39、我很平凡，但骨子里的我却很勇敢。40、眼中闪烁的泪光，也将化作永不妥协的坚强。41、我不去想是否能够成功，既然选了远方，便只顾风雨兼程。42、宁可自己去原谅别人，莫等别人来原谅自己。43、踩着垃圾到达的高度和踩着金子到达的高度是一样的。44、每天告诉自己一次：我真的很不错。45、人生最大的挑战没过于战胜自己！46、愚痴的人，一直想要别人了解他。有智慧的人，却努力的了解自己。47、现实的压力压的我们喘不过气也压的我们走向成功。48、心若有阳光，你便会看见这个世界有那么多美好值得期待和向往。49、相信自己，你

24、能作茧自缚，就能破茧成蝶。50、不能强迫别人来爱自己，只能努力让自己成为值得爱的人。51、不要拿过去的记忆，来折磨现在的自己。52、汗水是成功的润滑剂。53、人必须有自信，这是成功的秘密。54、成功的秘密在于始终如一地忠于目标。55、只有一条路不能选择那就是放弃。56、最后的措手不及是因为当初游刃有余的自己57、现实很近又很冷，梦想很远却很温暖。58、没有人能替你承受痛苦，也没有人能抢走你的坚强。59、不要拿我跟任何人比，我不是谁的影子，更不是谁的替代品，我不知道年少轻狂，我只懂得胜者为。60、如果你看到面前的阴影，别怕，那是因为你的背后有阳光。61、宁可笑着流泪，绝不哭着后悔。62、觉得自己

25、做得到和做不到，只在一念之间。63、跌倒，撞墙，一败涂地，都不用害怕，年轻叫你勇敢。64、做最好的今天，回顾最好的昨天，迎接最美好的明天。65、每件事情都必须有一个期限，否则，大多数人都会有多少时间就花掉多少时间。66、当你被压力压得透不过气来的时候，记住，碳正是因为压力而变成闪耀的钻石。67、现实会告诉你，不努力就会被生活给踩死。无需找什么借口，一无所有，就是拼的理由。68、人生道路，绝大多数人，绝大多数时候，人都只能靠自己。69、不是某人使你烦恼，而是你拿某人的言行来烦恼自己。70、当一个人真正觉悟的一刻，他放弃追寻外在世界的财富，而开始追寻他內心世界的真正财富。71、失败并不意味你浪费了

26、时间和生命，失败表明你有理由重新开始。72、人生应该树立目标，否则你的精力会白白浪费。73、山涧的泉水经过一路曲折，才唱出一支美妙的歌。74、时间告诉我，无理取闹的年龄过了，该懂事了。75、命运是不存在的，它不过是失败者拿来逃避现实的借口。76、人总是在失去了才知道珍惜！77、要铭记在心：每天都是一年中最美好的日子。78、生活远没有咖啡那么苦涩，关键是喝它的人怎么品味！每个人都喜欢和向往随心所欲的生活，殊不知随心所欲根本不是生活。79、别拿自己的无知说成是别人的愚昧！80、天空的高度是鸟儿飞出来的，水无论有多深是鱼儿游出来的。81、思想如钻子，必须集中在一点钻下去才有力量。82、如果我坚持什么

27、，就是用大炮也不能打倒我。83、我们要以今天为坐标，畅想未来几年后的自己。84、日出时，努力使每一天都开心而有意义，不为别人，为自己。85、有梦就去追，没死就别停。86、今天不为学习买单，未来就为贫穷买单。87、因为一无所有这才是拼下去的理由。88、只要我还有梦，就会看到彩虹!89、你既认准这条路，又何必在意要走多久。90、尽管社会是这样的现实和残酷，但我们还是必须往下走。91、能把在面前行走的机会抓住的人，十有八九都会成功。92、你能够先知先觉地领导产业，后知后觉地苦苦追赶，或不知不觉地被淘汰。93、强烈的信仰会赢取坚强的人，然后又使他们更坚强。94、人生，不可能一帆风顺，有得就有失，有爱就有恨，有快乐就会有苦恼，有生就有死，生活就是这样。95、好习惯的养成，在于不受坏习惯的诱惑。96、凡过于把幸运之事归功于自我的聪明和智谋的人多半是结局很不幸的。97、如果我们一直告诫自己要开心过每一天，就是说我们并不开心。98、天气影响身体，身体决定思想，思想左右心情。99、不论你在什么时候结束，重要的是结束之后就不要悔恨。100、只要还有明天，今天就永远是起跑线。