《运筹学补充课件.ppt》由会员分享，可在线阅读，更多相关《运筹学补充课件.ppt（29页珍藏版）》请在三一办公上搜索。
1、第一章,例2 某厂在今后四个月内需租用仓库堆存物资。已知各个月所需的仓库面积如表所示。当仓库租借合同期限越长，享受的折扣优待越大，仓库租借费用随着租借期限增长而不断减小，具体租借费用如表2所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租借合同，且每次办理时，可签一份，也可同时签若干份租用面积和租借期限不同的合同，总的目标是使所付的租借费用最小。,第二章,需求假设（The Requirements Assumption）：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个
2、需求量都必须由出发地满足成本假设（The Cost Assumption）：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量,可行解特性（The Feasible Solutions Property）当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解整数解性质（Integer Solutions Property）只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件,第三章,例1 有五项设计任务可供选择。各项设计任务的预期完成时
3、间分别为3，8，5，4，10（周），设计报酬分别为7，17，11，9，21（万元）。设计任务只能一项一项地进行，总的期限是20周。选择任务时必须满足下面要求：1.至少完成3项设计任务；2.若选择任务1，必须同时选择任务2；3.任务3和任务4不能同时选择。应当选择哪些设计任务，才能使总的设计报酬最大？,例2 某公司的研发部最近开发出了三种新产品，但为了防止生产线的过渡多元化，公司的管理层决定在三种新产品中，最多只能选择两种进行生产。这些产品都可以在两个工厂中生产，为了管理的方便，管理层决定在两个工厂中必须选出一个专门生产新产品。两个工厂中各种产品的单位生产成本是相同的，但由于生产设备的不同，每单
4、位产品所需的生产时间是不同的。数据见下表。管理层制定的目标是通过选择产品、工厂以及确定各种产品的生产率，使得总利润最大化。,例3 某企业有2个仓库和3个客户，需要经常由仓库发货给各客户。对于货物的运输，企业可以选择自营，也可以选择外包。若选择自营，每年因车辆的折旧费、保养费、专职运输人员的工资等，预计支出为15万元；若选择外包，则没有固定费用，但每件货物的运输费用要高于自营相应的费用。具体数据见下表。试确定运输业务的经营模式及各仓库与各供应商之间的供应关系使企业所支出的总费用最小。,第四章,七桥问题要在图中找一条经过每边一次且仅一次的路，通称欧拉回路。中国邮路问题：一个邮递员从邮局出发要走遍他
5、所负责的每条街道去送信，问应如何选择适当的路线可使所走的总路程最短。与欧拉回路有密切的关系。,第五章,例1：印刷厂每周需要用纸32卷，每次订货费(包括运费等)为250元；存贮费为每周每卷10元。问每次订货多少卷可使总费用为最小？例2 某商店经售甲商品成本单价500元，年存储费用为成本的20%，年需求量365件，需求速度为常数。甲商品的定购费为20元，提前期为10天，求E.O.Q、最低费用及订货点。,例4 某电视机厂自行生产扬声器用以装配本厂生产的电视机。该厂每天生产100部电视机，而扬声器生产车间每天可以生产5000个。已知该厂每批电视机装备的生产准备费为5000元，而每个扬声器在一天内的保管
6、费为0.02元。试确定该厂扬声器的最佳生产批量、生产时间和电视机的安装周期。,例5 某电子设备厂对一种元件的需求为每年2000件，不需要提前订货，每次订货费为25元。该元件每件成本为50元，年存贮费为成本的20%。如发生供应短缺，可在下批货到时补上，但缺货损失为每件每年30元。(1)求经济订货批量及全年的总费用；(2)如不允许发生供应短缺，重新求经济订货批量，并与(1)中的结果比较。,例7设某货物的需求量在17件至26件之间，已知需求量r的概率分布如下表并知其成本为每件5元，售价为每件10元，处理价为每件2元。问应进货多少，能使总利润的期望值最大？,第六章,进行决策分析时所依据的决策信息是过去
7、经验、资料、历史数据或决策者的估计，这种状态信息称为先验信息。所谓先验概率，是指试验前做出的状态概率的估计，一般是根据历史资料或经验判断得到的。根据这些先验信息进行决策，有可能信息并不能完全地、准确地反映所做出的决策在实施过程中所遇到的状态，决策的准确性就会受到影响。为了提高决策分析的准确性，需要在进行决策分析时，获得更多的信息，修正、改善先验信息，以获得一个比先验信息更完全、更准确的决策信息，这种信息称为后验信息。把在解决实际问题时搜集的新信息补充进来，这种补充通常会改变原有的估计，这样得到的状态的概率估计称为后验概率。,先验分析利用先验信息进行终端决策；预后分析后验分析的预分析；在补充新的
8、信息前，先对补充信息是否合算作出分析，从而决定是否补充新信息。后验分析利用后验信息进行终端决策，并计算出补充信息的价值。,4.4 预后分析,信息的价值在于它能提高决策的最大期望收益值，但如为获得信息所花费的费用超过它所能提高的期望收益值，这种补充信息是不合算的。预后分析，首先估算出完全信息的价值EVPI（任何信息的价值均不会超过完全信息的价值），并以它为一个标准。补充信息费用远远小于完全信息的价值EVPI，则补充信息合算；补充信息费用接近甚至超过完全信息的价值EVPI，则补充信息不合算。,完全信息价值（EVPI）,完全信息：能够准确无误地预报将发生状态的信息。当完全信息预报出现Qk状态时，问题
9、变为确定型决策问题。最优方案为在完全信息下，决策所能获得的最大收益期望值,完全信息价值：具有完全信息的期望收益与无附加信息时最优决策的期望收益之差，记EVPI。即EVPI=EPPI-EMV*既然EVPI 反映了完全信息的价值，而完全信息是可获信息的最高水准，因此，EVPI在决策分析中提供了为获取附加信息而值得付费的上限。,4.5 后验分析,补充信息的可能结果状态集合：S1,S2,Ss 为补充信息的各种可能状态提供条件概率：依据贝叶斯公式计算后验概率先验概率为 是获得新的补充信息的概率，表示 的补充信息，则有：其中，表示在S发生条件下，发生的概率。这一概率就是后验概率。,在Sk补充信息出现的条件
10、应选择的决策A*k计算每一方案的期望收入：后验分析中的最大期望收入和信息价值：信息价值=,例6.3 商店现需对某种货物下周的进货数量做出决策。设这种货物进货成本为每件800 元，售价为每件1000 元，但一周内如不能售出则变质报废。已知市场对这种货物的一周需求量的概率分布如表所示：因此进货数量也决定由25、26、27、28（件）四种可能中做出决策。（1）列出本问题的损益表，由最大期望收益准则确定最优决策；（2）列出机会损失表，由最小机会损失准则确定最优决策；（3）求本问题的EVPI。,（1）E(d1)=5000;E(d2)=5100;E(d3)=4900;E(d4)=4200。d*=d2，即进
11、货26 件（2）EOL(d1)=320;EOL(d2)=220;EOL(d3)=420;EOL(d4)=1220。d*=d2，即进货26件。（3）EVPI=220。,例6-2-2 某工程项目按合同应在三个月内完工，其施工费用与工程完工期有关。假定天气是影响工程能否按期完工的决定因素，如果天气好，工程能按时完工，施工单位可获利5万元；如果天气不好，不能按时完工，施工单位将被罚款1万元；若不施工就要损失窝工费0.2万元。根据过去的经验，在计划施工期内天气好的可能性为30。为了更好地掌握天气情况，可请气象中心作进一步天气预报，并提供同一时期天气预报资料，这需支付信息资料费0.08万元。从提供的资料中
12、可知，气象中心对好天气预报准确性为80，对坏天气预报准确性为90。问该如何进行决策？,决策树的结点与分枝决策结点：由此出发的分枝称决策分枝，表示不同的决策方案，该分枝下的数字为进行该项决策时的费用支出；状态（事件）结点：由此出发的分枝称机会（概率）分枝，表示不同的状态，该分枝下的数字表示对应状态出现的概率；后果结点：位于树的末梢处，后标结果的损益值。,例：有笔生意，存在三种状态：好，一般，坏。现有两个方案u1和u2，收益矩阵如下（单位：元）。很明显，收益从300元到1000元，通常定义效用函数值为01的闭区间内。最低的收益值对应效用函数值为0，最高的收益值对应效用函数值为1。即有：u(300)
13、=0，u(1000)=1现在要问自己：对同等机会下或得到300元，或得到1000元的确定当量是多少？假设是500元。因为需要确定当量的期望效用相一致，就应有：u(500)=0.5u(300)+0.5u(1000)=0.5,进一步又可得到下面两个确定当量。考虑：（1）同等机会得到300元或500元，假设确定当量是375元，就有：u(375)=0.5u(300)+0.5u(500)=0.25（2）同等机会得到500元或1000元，假设确定当量是700元，就有：u(700)=0.5u(500)+0.5u(1000)=0.75由此得到效用函数上的5个点：（300，0），（375，0.25），（500，0.5），（700，0.75），（1000，1）类似的，重复以上过程，可以得到更多的点，将这些点用平滑的曲线连起来，就得到了效用函数的曲线，如图5-7所示：,现在可用效用函数分析较复杂的决策问题。上例中能将收益值转换成效用值，得到效用矩阵如下：,根据期望效用值，方案u2为最优方案。综上所述，使用效用曲线有以下几步：（1）由确定当量得到一条效用函数曲线；（2）利用这条效用函数曲线把收益值转换成效用值；（3）应用期望值准则选优。,
