运筹学复习整理

《运筹学复习整理》由会员分享，可在线阅读，更多相关《运筹学复习整理（15页珍藏版）》请在装配图网上搜索。

1、运筹学：是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学模型的种类：形象模型、仿真模型、数学模型可行流：所谓可行流，要满足下列条件：(1) 容量限制条件：弧的流量不超过容量，即0WfijWCij(2) 平衡条件：对于中间点：流出垦流入量，对于发点和收点则有：发点的流出量=收点 的流入量弧的种类：饱和弧、非饱和弧、零流弧、前向弧、后向弧增广链：设f是网络D=(V,A,C)上的一个可行流，p是从vs到vt的一条链，若p满足下列条件：(1) 前向弧均为非饱和弧；(2) 后向弧均为非零流弧，则称p是关于可行流f的

2、一条增广链。网络计划的流程：1. 确定目标2. 分解工程项目，列出工序明细表3. 绘制网络图4. 网络计划方案的优化网络图的绘制规则：1. 网络图从左向右依次展开2. 箭线与结点对应3. 虚工序的运用：应付不暇时出现4. 不允许出现循环路线5. 只有一个始点和一个终点PERT：即计划评审技术，属于随机型网络，与关键路线法的应用环境不同，专门针对工序 时间不确定的工程项目。可行解：满足所有约束条件的解称为可行解，即“一致同意原则”可行域：可行解的集合叫做可行域决策：是贯穿管理的全过程，管理就是决策决策四个要素：决策目标、决策环境、备选方案、损益值决策的分类：战略决策，战术决策程序性决策和非程序性

3、决策确定型决策，不确定型决策，风险型决策PPT184-193以下的内容舄老弗:了解效用：效用是指事物的有用性，指一项决策、物品或事物对当事人的主观价值。这里强调效用是决策者的主观价值，就是说是该决策者的主观判断，是此人、此情、此境、 此知识、观念下，对此事物的价值判断。1. 效用与决策者个人的需求有关2. 效用与个人的价值观念有关3. 效用与决策者的风险偏好有关层次分析法AHP： AHP将人的思维方式和决策逻辑结构化、定量化、模型化，是定性与定 量有机结合的典范。工序的最早可能开工时间受紧前工序的制约，工序最早可能何时开工工序的最早可能完工时间最早可能开工时间+工序时间工序的最迟必须完工时间受

4、紧后工序的制约，工序最迟必须何时完工工序的最迟必须开工时间最迟必须完工时间-工序时间工序的总时差：在不影响紧后工序最迟必须开工时间的前提下，本工序的机动时间工序最迟必须开工时间-最早可能开工时间工序的单时差：在不影响紧后工序最早可能开工时间的前提下，本工序的机动时间 紧后工序的最早可能开工时间-本工序的最早可能完工时间T2J)丁 顼 八一Jv_r.tCij)1； 1tQk)i 丁叩眼3 乂7凶幻 N、广丁忒宙卜必 it(j；k)! R(iJ) !H例3.筹备餐馆的网络计划第三，计算事项时间参数的图算法1. 看图填表，得到I、ii、m、w栏2. 第V栏:TES=紧前工序TES+t(i,j)，多中

5、取大，即3. 第W栏：最早可能完工时间W = W+V4. 第W栏：从后向前推 TLF(i,j)=TLF(j,k)-t(j,k)5. 第伽 栏：最迟必须开工时间 W = -W6. 总时差：IX = V 或IX = W W7. 单时差：紧后工序的TES减去本工序的TEFInmIVVVIvaVtIXX工序名称ijt(i, j)TesTef上TlsR(i, J)r (i, j)A50510555B1001010000B501010101000C71017241770D61016161000IT01616242481IT01616161600E31013161333F41721282477G121628

6、2811600例瓣扁1. 张生看好大学生的消费潜力，）隹备在校园旁边开一个餐馆。假定选址已经完 成，接下来需要做的事情：筹备资金、准备文件、注册公司、装修门店、购置设 备、人员培训、商品采购等。工序代号签前工序工序时间工序代号签前工序工序时间做文件A5设备购置EB3B10商品采购FQD4CA.B肾AW训GD.E12装修门店仰A.B62. 某公司生产A、B两种矿产品，销路不成问题。制约因素主要有技术工人、 设备台时和原材料供应。已知A产品B产品资源限量人力64300设备46280矿石28320售价（元/公斤）80140该公司应该如何制定每天的生产计划，使其产值最大？题解：设X1为A产品产量，X2

7、为B产品的产量，用z表示产值，则每天的产值表示为maxz=80X1+140X2，称为目标函数。将制约因素表达出来，即有：人力不超过300工时:6X1+4X200设备不超过280台时:4X1+6X2 80矿石不超过320公斤:2X1+8X2 320得出数学模型：max z = 80x +140x126x + 4x 3004x + 6x 2802x1 + 8x2 0123. 医院的护士 24小时都需要值班，不同时段需要的人数不同，按照4小时一个时段排班，每班工作8小时，具体的统计数据如下表:序号时段最低人数16 : 00-10 : 0060210 : 00-14 : 0070314 : 00-18

8、 : 0060418 : 00-22 : 0050522 : 00-2 : 002062 : 00-6 : 0030设第时段上班的人数为Xjmin z x + x + x123囹/刁x+ x60x+ x70x+ x60x+ x50s.tx+ x20x+ x30x： 0： j 1,2.4.500万立方/天200万立方/河流沿岸有某公司的两个化工厂，A厂每天排放污水2万方；B厂每天排放污水 1.4万方。A厂排出的污水流到B厂之前 有20%可以自然净化 根据环保要求， 河水中污水含量不得超过0.2%。已知A厂污水处理成本1000元/万方，B厂污 水处理成本800元/万方。问公司应该如何分配污水处理的

9、数量，使得总成本最 低？ 设A厂处理X1万方/天，B厂处理X2万方/天主要约束：2 工 A厂的排放点不超标：* 罚龙 B厂的排放点不超标：（2一气）xEL4一罚.2%500 + 200A厂处理量不可能超过2万方B厂处理量不可能超过1.4万方模型min z = 1000x + 800xx 110.8x + x 1.6x 21x 05. 某学校为建造车棚，需要用100个铝合金三角架作龙骨，底梁长度2.9米，两 个斜梁分别是2.1米和1.5米，已知原料长度7.4米。问如何下料使得所用原料 最省？本题的变量设置不是显而易见的。首先要设计若干个截取方案，把按照某方案截 取的根数作为决策变量。方案要尽可能

10、完备，遗漏了方案则会影响最优化的 结果。长度 方案123456782_9M120101002_ IM002211301_5M31203104余料00-10-2030-80-9LI1-4模型:-min z = z xjj=1x + 2 x + x + x = 10012467+ X + X = 1002 x + 2 x + x + x + 3 x = 10034563 x + x + 2 x + 3 x1235xj 0, j = 1,2,86. 新任经理发现小金库里有100万元资金，令企划部找项目投资，力争第五年末本利和最大。企划部提出四个投资项目：A项目，从第一年到第四年每年年初投资，并于次年

11、末收回本利110%，每年至 少投资10万元；B项目，第二年初投资，第五年末收回本利135%，投资额度不超过20万元；C项目，第三年初投资，第五年末收回本利125%，投资额度在20-40万元之间；D项目，每年年初投资，年末收回本利104%。问应该如何安排不同项目不同年度的投资额度？X解：设第i年投资于j项目的金额为司万元D项目1.04C项目1.25B项目1.35A项目1.1第一年 第二年 第三年 第四年 第五年模型max z - 1.1x +1.35x +1.25x +1.04x4 A2 B3C5 DX + X = 100x + x + x = 1.04 xx + X + x = 1.1x +1

12、.04 xX + x = 1.1x +1.04 xx = 1.1x +1.04 xX 10, X 10, X 10, X 10X 20, x 0, i = 1,.,5; j = A, B, C, Dij7. 四个外语学院学生组成翻译公司，接到一项业务：把一个产品说明书翻译成 A、B、C、D四种语言，应指派何人做何种工作，能使总的时间最少？学生语种1234A149415B117910C136105D1791513JOBAssigned toCostA学生34.B学生111.C学生45.D学生28.Total28.(untitled) Solution8. 80万兀留学资金，制定一个理财计划首先亏

13、损10万元；其次，存款和国债不少于40万元；再次，一年内要收回30万元，两年内能够回收60万元；最后，钱嘛，当然是赚得越多越好。备选法案：一年期国债利率3.45%；两年期存款利率4.15%;三年期国债 利率5.18%；购买两年期企业债券利率10% :购买天虹基金，预期年收益 15% :购买朋友推荐的股票ST天龙，据说一年内将有50%的回报。怎样安排 投资才能使父胃满意？分析：建模：设各项目的投入金额为万元，由于父胃要求控制风险，故此给出各项目的 风险系数：银行存款和国债的风险系数几乎为零，企业债券风险系数为0.2,天 虹基金风险系数为0.3, ST天龙风险系数为0.5。投资回报多多益善，也要有

14、个 目标期望值，尽管其父胃没有明确的要求，设定为200万元，对于没有上限的要 求，只要足够大就可以了。minz = Pd + + P d- + P (d- + d-) + P d-1 12 23344 5x + x + x + x + x + x 0,d- 0,d + 0;i = 1,.,5, j = 1,.,6j i i9.某运输问题如下:B1b2b3玖供应量Ai546480A?6857120A37698100需求量8090110120公司有关部门根据供求关系和经营条件，确定了下列目标：P1：尽我所能，满足客户需要，产地不留存货；P2:完全满足用户B2的需要；A3向B1提供的产品数量不少于6

15、0吨;P3：每个用户的供应量不少于其需求的50%;P4:力求总运费最省；P5:从仓库Al到用户B2之间的公路经常维修，运货量应尽量少。试求满意的调运方案。min z - P (d - + d + + d - + d + + d - + d +) 1112233+ P (d - + d + + d -) + P (d - + d -) + P d + + Pd +24453674 85 9+ x + x + x + d d + 8011 12131411x + x + x + x + d d + 1202122232422x + x + x + x + d d + 100P23132333433

16、:x + x + x + dd + = 9012 223244x + dd+ - 60p : x + x + x +dd + 553 13233366x + x + x + d d + 6014243477p :枣 4 c x + d - - d + 04 ij ij 8 8i=1 j=1p : x + d d + 051299x 0,d-,d + 0;i 1,2,3;j = 1,.,4;k = 1,.,9 ij k k10. 某公司制定广告计划，可选媒体有电视、广播、网络，广告费用指标10万 元，调查公司提供的相关数据如下表电告广播广告网络广告黄金时段普通时段广告费用（汐个）60002000

17、1200800受众总数（人）20000600030003000妇女受众（人）13000400020001500公司希望：（1）电视广告不超过6万元；（2）总受众达到30万人，妇女受众不少于20万人，尤其希望更多的妇女看到 广告。（3）黄金时段电视广告不少于3个，网络广告不多于5个；设黄金时段电视广告数量为X 1，普通时段电视广告数为X 2，广播广告X 3,网 络广告X 4min z = Pd + + P （d- + 2d-） + P （d- + d +）1 12233456000X + 2000X +1200X + 800x 0,d-,d + 0;i = 1,.5;j = 1,.4j i i年

18、收入6万元。张华应该做出怎样的人生规划？好工作捋A 18167读博123141236_6企业5&6考中就业 83考研7考不中差工作形干得16.1从商8干不 6企W工作”/6&6 考中(5As11. 学生张华面临考研还是就业的抉择。张华学习成绩不错，自己估计考研成功 的概率0.6,如果考中了就能够顺利毕业；硕士毕业之后又有读博、从商两种选 择，博士毕业找到好工作（概率0.8）年收入18万元，找不到好工作年收入8 万元；硕士毕业从商干得好（概率0.7）年收入20万元，干不好年收入7万元。 考研不中或直接就业面临两种选择：考公务员（考中概率0.3）年收入8万元， 到企业工作是保底的选择12. 美的决

19、策美的准备开发信息家电，专家估计未来市场和预期损益如下未来状态：销路好销路中销路差状态概率P( 0 0=0.45P(0 2)=0-3P( 03)=0-25投资利润158-10美的公司有意委托麦迪逊咨询公司进行市场调研，麦迪逊要价500万元，谈判正 在进行中美的公司要审查麦迪逊的资信水平，根据其业绩资料和当年的市场状况，美的公 司归纳出麦迪逊的预测信度表麦迪逊公司业绩统计$01 : 销路好02 : 销路中03 : 销路差乐观Si0.750.150.10中性&0.150.700.15悲观S30.100.150.75求解睥冏)0 P(S)0!:销路好02 :销路中。3 *销路差P(0i0-45?(0

20、20-30P(03O-25P(SJ= 0-40750.750.150.10P(SA 031500.150.700.15P(S3 0_27750.100.150.75P(0j/Si) gj Si0!:销路好02 :销路中03 ：销路差P(0i 尸045P(02030P(030-25P(SJ= 0-40750.82820.11040.0614P(S ) 031500.21430.66670.1190P(S 沪 0-27750.16220.16220.67561269 o13. 设最大收益15亿元的效用值为1,最小收益-10亿元，设其效用值为0； 询问决策者：A方案：以50%的概率获得15亿元，以5

21、0%的概率损失10亿元B方案：100%获得2.5亿元，你将选择何者？如果选B,修订为100%获得1亿元，如果继续选择B,进一步降低金额，直 至他认为A和B没有差异。假如100%获得0与50%概率得15亿元，50%损失10亿元无差别则0亿元的效用值为U(0)=1 0.5+0 0.5 = 0.5。继续询问：人方案：以50%的概率损失10亿元，以50%的概率获得0亿元，与 B方案：100%损失5亿元，选择何者？U(-6.5)=U (-10)X).5+U(0) 0.5 = 0.25询问：A方案：以50%的概率获得0亿元，以50%的概率获得15亿元，与B 方案：100%获得7.5亿元，如何选择？U (5)=0.5 0.5+1 0.5 = 0.75-10 -505101514.