运筹学(胡运权第四版及答案)ppt课件

管理运筹学主讲：谢先达2014.09.*我纳闷 联系方式 办公室：QL64387313663 手机：13600512360 邮箱：xxdhz@163.com.绪论.绪论 什么是运筹学？ 运筹学发展历史 运筹学主要内容 运筹学的基本特征与基本方法.*我们绪论 什么是运筹学？定义：为决策机构在对其控制下业务活动进行决策时，提供以数量化为基础的科学方法。 西蒙：管理就是决策 决策 定性管理者的判断和经验定量运筹学.*我们绪论 运筹学发展历史古代运筹思想：田忌赛马、丁渭修皇宫二战期间的OperationalResearch研究成果被应用到生产、经济领域，且研究不断深化，逐步形成“运筹学”.绪论.绪论 运筹学的主要内容有哪些？ 线性规划 运输问题 整数规划 目标规划 动态规划 图与网络模型 排序与统筹方法 存储论 排队论 对策论 决策分析 预测.绪论 运筹学研究的基本特征系统的整体观念多学科的综合模型方法的应用.绪论 运筹学研究的基本方法 分析和 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述问题 建立模型 求解模型和优化 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 测试模型及对模型进行必要的修正 建立对解的有效控制 方案的实施.第一章：线性规划及单纯形法.第一章：线性规划及单纯形法 线性规划问题及其数学模型 线性规划图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论.第一章：线性规划及单纯形法 例题：某工厂在 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 期内要安排Ⅰ、Ⅱ两种产品的生产，生产单位产品所需的设备台时及A、Ｂ两种原材料的消耗以及资源的限制如表所示工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少单位产品Ⅰ和产品Ⅱ才能获利最多？ Ⅰ Ⅱ 资源限制 设备 1 1 300台时 原料A 2 1 400KG 原料B 0 1 250KG.第一章：线性规划及单纯形法 线性规划问题的数学模型目标函数：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1≥0，x2≥0概念：可行解、最优解、最优值约束条件：非负约束：.第一章：线性规划及单纯形法500万m3 练习：靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为每天200万m3支流，第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二化工厂每天排放这种工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自净化。根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需各自处理一部分工业污水，第一化工厂处理工业污水的成本是1000元/万m3。第二化工厂处理污水的的成本是800元/万m3。现问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。200万m3工厂1工厂2.第一章：线性规划及单纯形法 线性规划问题的数学模型目标函数：minz=1000x1+800x2约束条件：(2-x1)/500≤0.2%〔0.8(2-x1)+(1.4-x2)〕/700≤0.2%x1≤2x2≤1.4非负约束：x1≥0，x2≥0. 线性规划的一般模式目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn约束条件：a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1a21x1+a22x2+a23x3+…+a2nxn≤(=≥)b2…………am1x1+am2x2+am3x3+…+amnxn≤(=≥)bn非负性约束：x1≥0,x2≥0,…,xn≥0第一章：线性规划及单纯形法. 解得：最大利润：27500X1=50X2=250 代入得：设备台时：300原料A：350原料B：250 概念：松弛变量剩余变量第一章：线性规划及单纯形法. 线性规划的标准型maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj≥0j=1,2,…,n第一章：线性规划及单纯形法标准型的四个标准：求最大值、约束条件为等式、bj≥0.xj≥0. 化非标准形线性规划为标准形式minz=x1+2x2+3x3-2x1+x2+x3≤9-3x1+x2+2x3≥4004x1-2x2-3x3=-6x1≤0,x2≥0,x3取值无约束第一章：线性规划及单纯形法. 练习：将下面线性规划问题化为标准形式minz=2x1-2x2+3x3-x1+x2+x3=4-2x1+x2-x3≤6x1≤0,x2≥0,x3取值无约束第一章：线性规划及单纯形法.第一章：线性规划及单纯形法 线性规划问题及其数学模型 线性规划图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论.4002001001002003004003000x1x2第一章：线性规划及单纯形法2x1+x2=400x2=250x1+x2=300目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250非负约束：x1≥0，x2≥0.4002001001002003004003000x1x22x1+x2=400x2=250x1+x2=300第一章：线性规划及单纯形法可行域.4002001001002003004003000x1x22x1+x2=400x2=250x1+x2=300Z=0=50x1+100x2Z=1000=50x1+100x2Z=20000=50x1+100x2Z=27500=50x1+100x2第一章：线性规划及单纯形法等值线. 线性规划问题解的几种情况线性规划存在唯一最优解线性规划存在有无穷多个最优解的情况线性规划可能存在无界解线性规划存在无可行解的情况第一章：线性规划及单纯形法. 练习： P43：1.1（1）（2）第一章：线性规划及单纯形法.第一章：线性规划及单纯形法 线性规划问题及其数学模型 线性规划图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论.基本概念：可行解最优解基基解基可行解可行基第一章：线性规划及单纯形法.解的几何意义例:线性规划问题基本可行解的意义：第一章：线性规划及单纯形法.解的几何意义 第一章：线性规划及单纯形法.解的几何意义 第一章：线性规划及单纯形法.解的几何意义 第一章：线性规划及单纯形法.解的几何意义 第一章：线性规划及单纯形法.解的几何意义第一章：线性规划及单纯形法.解的几何意义第一章：线性规划及单纯形法.算法思路 求一个初始基本可行解 是判断基本可行解是否最优结束 不是 求使目标得到改善的基本可行解 是否存在？如何得到？是否唯一？如何判断？如何改善？如何判断没有有限最优解？第一章：线性规划及单纯形法.基本定理 定理1若线性规划问题存在可行解，则该问题的可行解集（即可行域）是凸集。 定理2线性规划问题的基可行解x对应线性规划问题可行域(凸集)的顶点 定理3若线性规划问题有最优解，一定存在一个基可行解（可行域顶点）是最优解，如果在几个顶点上都出现最优解，则这些顶点的每个凸组合上也达到最优。第一章：线性规划及单纯形法.凸集的概念1、基本概念：凸集——设K是n维欧氏空间的一个点集，若任意两点X（1）∈K，X（2）∈K的连线上的一切点：αX（1）+（1-α）X（2）∈K（0<α<1），则称K为凸集。第一章：线性规划及单纯形法.凸集的概念 凸组合——设X（1），X（2），…，X（k）是n维欧氏空间中的K个点，若存在k个数μ1，μ2，…，μk,满足0≤μi≤1,i=1,2,…,k；则称X=μ1X（1）+μ2X（2）+…+μkX(k)为X（1）,，X（2），…，X（k）的凸组合。 顶点——设K是凸集，XK；若K中不存在两个不同的点X（1）K，X（2）K使X=αX（1）+（1-α）X（2）（0<α<1）则称X为K的一个顶点（也称为极点或角点）。第一章：线性规划及单纯形法.凸集的概念凸集凸集不是凸集第一章：线性规划及单纯形法.表格单纯形法基变量检验数基变量系数右端常数最小比值列第一章：线性规划及单纯形法.表格单纯形法基变量检验数基变量系数右端常数最小比值列第一章：线性规划及单纯形法.表格单纯形法第一章：线性规划及单纯形法 cj 21000 比值bi/aij cB基b x1x2x3x4x5 0x3150x4240x55 05100[6]201011001 cj-zj 21000.表格单纯形法第一章：线性规划及单纯形法 cj 21000 比值bi/aij cB基b x1x2x3x4x5 0x3152x140x51 0510012/601/600[4/6]0-1/61 cj-zj 01/30-1/30.表格单纯形法第一章：线性规划及单纯形法 cj 21000 比值bi/aij cB基b x1x2x3x4x5 0x315/22x17/21x23/2 0015/4-15/21001/4-1/2010-1/43/2 cj-zj 000-1/4-1/2.1、人工变量法（大Ｍ法）2、两阶段法第一章：线性规划及单纯形法单纯形法的进一步讨论：.第一章：线性规划及单纯形法 人工变量法目标函数：maxz=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9x1，x2，x3≥0约束条件：.第一章：线性规划及单纯形法 化成标准形式：目标函数：maxz=-3x1+x3+0x4+0x5x1+x2+x3+x4=4-2x1+x2-x3-x5=13x2+x3=9x1，x2，x3,x4,x5≥0约束条件：.第一章：线性规划及单纯形法 添加人工变量：目标函数：maxz=-3x1+x3+0x4+0x5-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9x1，x2，x3,x4,x5,x6,x7≥0约束条件：. cj -30100-M-M 比值bi/aij CB基b x1x2x3x4x5x6x7 0x44-Mx61-Mx70 1111000-2[1]-10-1100310000 Cj-zj -2M-34M10-M00 0x430x21-Mx76 30211-10-21-10-110[6]0403-31 Cj-zj 6M-304M+103M-4M0 0x400x23-3x11 0001-1/2-1/2-1/2011/30001/310[2/3]01/2-1/21/6 Cj-zj 00303/2-M-3/2-M+1/2 0x400x25/21x33/2 0001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4 Cj-zj -9/2000-3/4-M+3/4-M-1/4. cj 00000-1-1 比值bi/aij CB基b x1x2x3x4x5x6x7 0x44-1x61-1x79 1111000-2[1]-10-1100310000 Cj-zj -2400-100 0x430x21-1x76 30211-10-21-10-110[6]0403-31 Cj-zj 60403-40 0x400x230x11 0001-1/21/2-1/2011/30001/3102/301/2-1/21/6 Cj-zj 00000-1-1.第一章：线性规划及单纯形法 两阶段法：目标函数：maxw=x6+x7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9x1，x2，x3,x4,x5,x6,x7≥0约束条件：. cj -30100 比值bi/aij CB基b x1x2x3x4x5 0x400x23-3x11 00011/2011/300102/301/2 Cj-zj 00303/2 0x400x25/21x33/2 0001-1/2-1/2100-1/43/20103/4 Cj-zj -9/2000-3/4.第三章运输问题 例1：某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示.第三章运输问题例1：某公司从两个产地A1，A2将物品运往三个销地B1，B2，B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示.minf=6x11+4x12+6x12+6x21+5x22+5x23x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥(i=1,2;j=1,2,3)第三章运输问题解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表。.第三章运输问题 一般运输模型：产销平衡A1、A2、…、Am表示某物资的m个产地；B1、B2、…、Bn表示某物质的n个销地；si表示产地Ai的产量；dj表示销地Bj的销量；cij表示把物资从产地Ai运往销地Bj的单位运价。 设xij为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：mnMinf=cijxiji=1j=1nxij=sii=1,2,…,mj=1mxij=djj=1,2,…,ni=1xij≥0(i=1,2,…,m;j=1,2,…,n).第三章运输问题 变化：1）有时目标函数求最大。如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，在模型中直接加入约束条件（等式或不等式约束)；3）产销不平衡时，可加入假想的产地（销大于产时）或销地（产大于销时）。.第三章运输问题. 例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个 虚设的销地 运输费用为0第三章运输问题. 例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个 虚设的产地 运输费用为0第三章运输问题.第三章运输问题 产销不平衡问题石家庄北方研究院有三个区，即一区、二区、三区，每年分别需要生活用煤和取暖用煤3000T，1000T，2000T，由河北临城、山西盂县两处煤矿负责供应，这两处煤矿的价格相同，煤的质量也基本相同，两处煤矿能供应北方研究院的煤的数量，山西盂县为4000T，河北临城为1500T，由煤矿至北方研究院的单位运价（百元/T）如表所示。由于需大于供，经院研究决定一区供应量可减少0--300吨，二区必须满足需求量，三区供应量不少于1500吨，试求总费用为最低的调运方案。.第三章运输问题解：根据题意，作出产销平衡与运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。. 例设有三个化肥厂供应四个地区的农用化肥,假定等量的化肥在这些地区使用效果相同,各化肥厂年产量、各地区年需求及各化肥厂到各地区运送单位化肥的运价如表所示，试求出总的运费最节省的的化肥调拨方案。第三章运输问题 Ⅰ Ⅱ Ⅲ Ⅳ 产量/万吨 Ａ 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 -- 50 最低需求/万吨 30 70 0 10 最高需求/万吨 50 70 30 不限.解：根据题意，作出产销平衡与运价表：第三章运输问题最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。 Ⅰ′ Ⅰ″ Ⅱ Ⅲ Ⅳ′ Ⅳ″ 产量/万吨 Ａ 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 销量/万吨 30 20 70 30 10 50 210210.求解结果如下：第三章运输问题 Ⅰ′ Ⅰ″ Ⅱ Ⅲ Ⅳ′ Ⅳ″ 产量/万吨 Ａ 50 50 B 20 10 30 60 C 30 20 0 50 D 30 20 50 销量/万吨 30 20 70 30 10 50 210210.第三章运输问题 生产与储存问题例某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如右表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。.第三章运输问题.第三章运输问题某公司承担4条航线的运输任务，已知：（1）各条航线的起点城市与终点城市及每天的航班数（见下表1）；（2）各城市间的航行时间（见下表2）；（3）所有航线都使用同一船只，每次装船和卸船时间均为1天。问该公司至少应配备所少条船才能满足所有航线运输的需要？表1： 航线 起点城市 终点城市 每天航班数 1 E D 3 2 B C 2 3 A F 1 4 D B 1.第三章运输问题某公司承担4条航线的运输任务，已知：（1）各条航线的起点城市与终点城市及每天的航班数（见下表1）；（2）各城市间的航行时间（见下表2）；（3）所有航线都使用同一船只，每次装船和卸船时间均为1天。问该公司至少应配备所少条船才能满足所有航线运输的需要？表2： A B C D E F A 0 1 2 14 7 7 B 1 0 3 13 8 8 C 2 3 0 15 5 5 D 14 13 15 0 17 20 E 7 8 5 17 0 3 F 7 8 5 20 3 0. 表上作业法 按某种规则找出一个初始基可行解； 对现行解作最优性判断，即求各非基变量的检验数，判别是否达到最优解，如已是最优解，则停止计算，如不是最优解，则进行下一步骤； 在表上对初始方案进行改进，找出新的基可行解，再按第二步进行判别，直至找出最优解。第三章运输问题.图：运输问题求解思路图第三章运输问题. 初始基本可行解的确定甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示，求使总运输费用最少的调运方案。第三章运输问题. 有关信息表450200150100日销量（需求量）250756580乙2001007090甲日产量（供应量）CBA运距城市煤矿第三章运输问题. 西北角法不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销要求 .用西北角法确定初始调运方案1001001005050200200 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 450.得到初始调运方案为：x11=100，x12=100，x22=50，x23=200. 最小元素法：从运价最小的格开始，在格内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。.用最小元素法确定初始调运方案150100100100100100100 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 450.得到初始调运方案为：x11=100，x13=100，x22=150，x23=100. 最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后，按照表上作业法的第二步，下面需对这个解进行最优性判别，看它是否为本运输问题的最优解..以xij空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号；那麽，该非基变量xij的检验数：现在，在用最小元素法确定例2初始调运方案的基础上，计算非基变量X12的检验数： 闭回路法.初始调运方案中以X12(X21)为起点的闭回路 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 450.非基变量X12的检验数：非基变量X21的检验数：经济含义：在保持产销平衡的条件下，该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。. 位势法 检验数公式： 分别表示前m个约束等式对应的对偶变量； 分别表示后n个约束等式对应的对偶变量。 .初始调运方案对偶变量对应表 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 450 对偶变量vj v1 v2 v3.2、位势法.在式中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。.在式中，令u1=0，则可解得v1=90，v3=100，u2=-25，v2=90，于是σ12=c12-（u1+v2）=70-（0+90）=-20σ21=c21-（u2+v1）=80-（-25+90）=15与前面用闭回路法求得的结果相同。.位势法计算非基变量xij检验数的公式σij=cij-（ui+vj）复习比较检验数计算的两种方法思考：试解释位势变量的含义（提示：写出运输问题的对偶问题）. 解的改进如检验出初始解不是最优解，即某非基变量检验数为负， 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 将这个非基变量变为基变量时运费会下降。根据表上作业法的第三步，需对初始方案进行改进。. 解的改进步骤为： 1．（如存在多个非基变量的检验数为负时，以最小负检验数所在空格对应的变量）为换入变量，找出它在运输表中的闭回路； 2．以这个空格为第一个奇数顶点，沿闭回路的顺（或逆）时针方向前进，对闭回路上的每个折点依次编号； 3．在闭回路的所有偶数折点中，找出运输量最小的一个折点，以该格中的变量为换出变量； 4．将闭回路上所有奇数折点的运输量都增加这一换出变量值，所有偶数折点处的运输量都减去这一数值，最终得出一个新的运输方案。 对得出的新方案再进行最优性检验，如不是最优解，就重复以上步骤继续进行调整，一直到得出最优解为止.继续上例，因σ12=-20，画出以x12为起始变量的闭回路 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 450. 计算调整量：ε=Min（100，150）=100。 按照下面的方法调整调运量：闭回路上，奇数次顶点的调运量加上ε，偶数次顶点的调运量减去ε；闭回路之外的变量调运量不变。 得到新的调运方案：.重复上面的步骤，直至求出最优调运方案： 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 45034250. 调销地运量产地 B1 B2 B3 产量 A1 90X11 70X12 100X13 200 A2 80X21 65X22 75X23 250 销量 100 150 200 450.结果最优调运方案是：x11=50，x12=150，x21=50，x23=200相应的最小总运输费用为：Zmin=90×50+70×150+80×50+75×200=34000.课堂练习： 销产 B1 B2 B3 B4 产量 A2 4 12 4 11 16 A2 2 10 3 9 10 A3 8 5 11 6 22 销量 8 14 12 14 48. 几点说明 若运输问题的某一基可行解有多个非基变量的检验数为负，在继续迭代中。通常取中最小者对应的变量为换入变量； 当迭代到运输问题的最优解时，如果有某非基变量的检验数等于0，则说明该运输问题有多重最优解； 当运输问题某部分产地的产量和，与某部分销地的销量和相等时，在迭代过程中间有可能有某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个格中填入0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-1)个。.第四章目标规划. 目标规划问题举例 例1．企业生产:不同企业的生产目标是不同的。多数企业追求最大的经济效益。但随着环境问题的日益突出，可持续发展已经成为全社会所必须考虑的问题。因此，企业生产就不能再如以往那样只考虑企业利润，必须承担起社会责任，要考虑环境污染、社会效益、公众形象等多个方面。兼顾好这几者关系，企业才可能保持长期的发展。 例2．商务活动:企业在进行盈亏平衡预算时，不能只集中在一种产品上，因为某一种产品的投入和产出仅仅是企业所有投入和产出的一部分。因此，需要用多产品的盈亏分析来解决具有多个盈亏平衡点的决策问题（多产品的盈亏平衡点往往是不一致的）。. 例3．投资:企业投资时不仅仅要考虑收益率，还要考虑风险。一般地，风险大的投资其收益率更高。因此，企业管理者只有在对收益率和风险承受水平有明确的期望值时，才能得到满意的决策。 例4．裁员:同样的，企业裁员时要考虑很多可能彼此矛盾的因素。裁员的首要目的是压缩人员开支，但在人人自危的同时员工的忠诚度就很难保证，此外，员工的心理压力、工作压力等都会增加，可能产生负面影响。 例5．营销:营销方案的策划和执行存在多个目标。既希望能达到立竿见影的效果，又希望营销的成本控制在某一个范围内。此外，营销活动的深入程度也决定了营销效果的好坏和持续时间。. 目标规划的图解法例6．一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1： 从上表可知，A股票的收益率为（3／20）×100％＝15％，股票B的 收益率为4／50×100％＝8％，A的收益率比B大，但同时A的风险也 比B大。这也符合高风险高收益的规律。试求一种投资方案，使得一 年的总投资风险不高于700，且投资收益不低于10000元。. 目标规划的图解法显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标的优先权。假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。 建立模型：设x1、x2分别表示投资商所购买的A股票和B股票的数量。首先考虑资金总额的约束：总投资额不能高于90000元。即20x1＋50x2≤90000。. 目标规划的图解法 约束条件再来考虑风险约束：总风险不能超过700。投资的总风险为0.5x1＋0.2x2。引入两个变量d1+和d1-,建立等式如下：0.5x1+0.2x2=700+d1+-d1-其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的部分，d1+≥0。目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。.把等式转换，可得到0.5x1+0.2x2-d1++d1-=700。再来考虑年收入:年收入=3x1+4x2引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。于是，第2个目标可以表示为3x1+4x2-d2++d2-=10000。. 有优先权的目标函数本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过700。分配给第一个目标较高的优先权P1,分配给第二个目标较低的优先权P2。针对每一个优先权，应当建立一个单一目标的线性规划模型。首先建立具有最高优先权的目标的线性规划模型，求解；然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，并求解。. 图解法针对优先权最高的目标建立线性规划建立线性规划模型如下：Mind1+s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥0..针对优先权次高的目标建立线性规划优先权次高（P2）的目标是总收益超过10000。建立线性规划如下：Mind2-s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000d1+＝0x1,x2,d1+,d1-,d2+,d2-≥0..目标规划的这种求解方法可以表述如下：1．确定解的可行区域。2．对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。3．对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。4.重复第3步，直至所有优先权的目标求解完。. 目标规划模型的标准化例6中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：MinP1（d1+）+P2（d2-）s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-,d2+,d2-≥0. 复杂情况下的目标规划例7．一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍。试求如何安排生产？.解：本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。对应P1有两个目标：每周总耗费人力资源不能低于600工时,也不能超过680工时；对应P2有一个目标：每周的利润超过70000元；对应P3有两个目标：每周产品A和B的产量分别不低于200和120件。.采用简化模式，最终得到目标线性规划如下：MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.2x1+3x2-d1++d1-=680对应第1个目标2x1+3x2-d2++d2-=600对应第2个目标250x1+125x2-d3-+d3+＝70000对应第3个目标x1-d4++d4-=200对应第4个目标x2-d5++d5-=120对应第5个目标x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0.使用运筹学软件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+=0；d5-=60，目标函数d4-+2d5-=120。可见，目标1、目标3和目标4达到了，但目标2、目标5都有一些偏差。. 加权目标规划 加权目标规划是另一种解决多目标决策问题的方法，其基本方法是通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。 如果在例7中我们对每周总耗费的人力资源超过680工时或低于600工时 的每工时罚数权重定为7；每周利润低于70000元时，每元的罚数权重为 5；每周产品A产量低于200件时每件罚数权重为2，而每周产品B产量低 于120件时每件罚数权重为4。. 则其目标函数化为：min7d1++7d2-+5d3-+2d4-+4d5-这就变成了一个普通的单一目标的线性规划问题 min7d1++7d2-+5d3-+2d4-+4d5- s.t.2x1+3x2-d1++d1-=680 2x1+3x2-d2-+d2+=680 250x1+125x2-d3-+d3+=70000 x1-d4++d4-=200 x2-d5++d5-=120 x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-≥0。.第八章整数规划. 在整数规划中，如果所有的变量都为非负整数，则称为 纯整数规划问题；如果有一部分变量为负整数，则称之 为混合整数规划问题。在整数规划中，如果变量的取值 只限于0和1，这样的变量我们称之为0-1变量。在纯整数 规划和混合整数规划问题中，如果所有的变量都为0-1变 量，则称之为0-1规划。第五章整数规划. 整数规划的图解法例:某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型 目标函数：Maxz=2x1+3x2 约束条件：195x1+273x2≤1365 4x1+40x2≤140 x1≤4 x1，x2≥0为整数。 如果去掉最后一个约束，就是一个线性规划问题。利用图解法，.得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值为14。性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。 整数规划的图解法.例2：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0为整数例3：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3为整数x3为0-1变量用《管理运筹学》软件求解得：x1=5x2=2x3=2用《管理运筹学》软件求解得：x1=4x2=1.25x3=1z=16.25 整数规划的计算机求解. 整数规划的应用 投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。 Aj各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?.解：设：0--1变量xi=1(Ai点被选用）或0(Ai点没被选用）。这样我们可建立如下的数学模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x9+x10≥2xi≥0且xi为0--1变量，i=1,2,3,……,10. 固定成本问题例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。.解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）。引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0yj为0--1变量，i=1,2,3. 指派问题有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。例6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。.解：引入0—1变量xij，并令xij=1(当指派第i人去完成第j项工作时)或0（当不指派第i人去完成第j项工作时)．这可以表示为一个0--1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(A工作只能一人干)x12+x22+x32+x42=1(B工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij为0--1变量，i,j=1,2,3,4***求解可用《管理运筹学》软件中整数规划方法。. 分布系统设计例7．某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?.解：a)设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak被选中时)或0（当Ak没被选中时),k=2,3,4,5．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13≤30(A1厂的产量限制)x21+x22+x23≤10y2(A2厂的产量限制)x31+x32+x33≤20y3(A3厂的产量限制)x41+x42+x43≤30y4(A4厂的产量限制)x51+x52+x53≤40y5(A5厂的产量限制)x11+x21+x31+x41+x51=30(B1销地的限制)x12+x22+x32+x42+x52=20(B2销地的限制)x13+x23+x33+x43+x53=20(B3销地的限制)xij≥0，i=1,2,3,4,5；j=1,2,3，yk为0--1变量，k=2,3,4,5。***求解可用《管理运筹学》软件中整数规划方法。. 投资问题例8．某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?.解：1)设xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分别表示第i年年初给项目A，B，C，D的投资额；设yiA，yiB，是0—1变量，并规定取1时分别表示第i年给A、B投资，否则取0（i=1,2,3,4,5）。设yiC是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；这样我们建立如下的决策变量： 第1年第2年第3年第4年第5年 Ax1Ax2Ax3Ax4A Bx3B Cx2C=20000y2C Dx1Dx2Dx3Dx4Dx5D .2）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是x1A+x1D=100000；第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。关于项目A的投资额规定:x1A≥40000y1A，x1A≤200000y1A，200000是足够大的数；保证当y1A=0时，x1A=0；当y1A=1时，x1A≥40000。关于项目B的投资额规定:x3B≥30000y3B，x3B≤50000y3B；保证当y3B=0时，x3B=0；当y3B=1时，50000≥x3B≥30000。关于项目C的投资额规定:x2C=20000y2C，y2C=0，1，2，3，4。.3）目标函数及模型：Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=100000；x2A+x2C+x2D=1.06x1D；x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A≥40000y1A，x1A≤200000y1A，x3B≥30000y3B，x3B≤50000y3B；x2C=20000y2C，yiA，yiB=0或1，i=1,2,3,4,5y2C=0，1，2，3，4xiA，xiB，xiC，xiD≥0(i=1、2、3、4、5）.第八章图与网络分析.图论中图是由点和边构成，可以反映一些对象之间的关系。例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。 图与网络的基本概念.当然图论不仅仅是要描述对象之间关系，还要研究特定关系之间的内在规律，一般情况下图中点的相对位置如何、点与点之间联线的长短曲直，对于反映对象之间的关系并不是重要的，如对赵等七人的相互认识关系我们也可以用图11-2来表示，可见图论中的图与几何图、工程图是不一样的。 图与网络的基本概念. 图与网络的基本概念如果我们把上面例子中的“相互认识”关系改为“认识”的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。图11-3就是一个反映这七人“认识”关系的图。相互认识用两条反向的弧表示。. 无向图：由点和边构成的图，记作G=（V，E）。 有向图：由点和弧构成的图，记作D=（V，A）。 连通图：对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。 回路：若路的第一个点和最后一个点相同，则该路为回路。 赋权图：对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 网络：在赋权的有向图D中指定一点，称为发点，指定另一点称为收点，其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称为网络。 图与网络的基本概念. 最短路问题 最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从Vs到Vt的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。一、求解最短路的Dijkstra算法(双标号法）步骤：1.给出点V1以标号(0,s)2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合3.如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则vs到vt的距离为lt，而从vs到vt的最短路径，则可以从kt反向追踪到起点vs而得到。如果vt未标号，则可以断言不存在从vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。4.对上述弧的集合中的每一条弧，计算sij=li+cij。在所有的sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。. 最短路问题例1求下图中v1到v6的最短路 解：采用Dijkstra算法，可解得 最短路径为v1v3v4v6 各点的标号图如下：.例2电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图，即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点到未标号的点的边的集合即可。V1（甲地）1517624431065v2V7（乙地）v3v4v5v6.例2最终解得：最短路径v1v3v5v6v7，每点的标号见下图.例3设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。已知：设备每年年初的价格表 设备维修费如下表 年份 1 2 3 4 5 年初价格 11 11 12 12 13 使用年数 0-1 1-2 2-3 3-4 4-5 每年维修费用 5 6 8 11 18.例3的解：将问题转化为最短路问题，如下图：用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的设备一直使用到第j年年初。把所有弧的权数计算如下表： 1 2 3 4 5 6 1 16 22 30 41 59 2 16 22 30 41 3 17 23 31 4 17 23 5 18 6.(继上页)把权数赋到图中，再用Dijkstra算法求最短路。 最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1v3v6和v1v4v6. 课堂练习：P2531. 最小生成树问题 树是图论中的重要概念，所谓树就是一个无圈的连通图。图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不是树，(c)因为不连通所以也不是树。.给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中，(b)和(c)都是(a)的生成子图。如果图G的一个生成子图还是一个树，则称这个生成子图为生成树，在图11-12中，(c)就是(a)的生成树。最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成树，并使得这个生成树的所有边的权数之和为最小。(a)(b)(c). 求解最小生成树的破圈算法算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。.例4用破圈算法求图（a）中的一个最小生成树图11-13.例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得，也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19百米。“管理运筹学软件”有专门的子程序可以解决最小生成树问题。. 最大流问题 最大流问题：给一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。最大流的数学模型例6某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化，它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/小时。如果使用这个网络系统从采地v1向销地v7运送石油，问每小时能运送多少加仑石油？v563522241263v1v2v7v4v3v6图11-26v5.我们可以为此例题建立线性规划数学模型：设弧(vi,vj)上流量为fij，网络上的总的流量为F，则有：.在这个线性规划模型中，其约束条件中的前6个方程表示了网络中的流量必须满足守恒条件，发点的流出量必须等于收点的总流入量；其余的点称之为中间点，它的总流入量必须等于总流出量。其后面几个约束条件表示对每一条弧(vi,vj)的流量fij要满足流量的可行条件，应小于等于弧(vi,vj)的容量cij，并大于等于零，即0≤fij≤cij。我们把满足守恒条件及流量可行条件的一组网络流{fij}称之为可行流，（即线性规划的可行解），可行流中一组流量最大（也即发出点总流出量最大）的称之为最大流（即线性规划的最优解）。我们把例6的数据代入以上线性规划模型，用“管理运筹学软件”，马上得到以下的结果：f12=5，f14=5，f23=2，f25=3，f43=2，f46=1，f47=2，f35=2，f36=2，f57=5，f67=3。最优值（最大流量）=10。. 最大流问题网络图论的解法对网络上弧的容量的表示作改进。为省去弧的方向，如下图:(a)和(b)、(c)和(d)的意义相同。用以上方法对例6的图的容量标号作改进，得下图vivjvivjcij0（a）（b）cijcijvivj（cji）（c）vivjcijcji（d）. 求最大流的基本算法（1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。（2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。（3）在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤（1）。用此方法对例6求解：第一次迭代：选择路为v1v4v7。弧（v4,v7）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：.第二次迭代：选择路为v1v2v5v7。弧（v2,v5）的顺流容量为3，决定了pf=3，改进的网络流量图如下图：第三次迭代：选择路为v1v4v6v7。弧（v4,v6）的顺流容量为1，决定了pf=1，改进的网络流量图如下图：.第四次迭代：选择路为v1v4v3v6v7。弧（v3,v6）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：第五次迭代：选择路为v1v2v3v5v7。弧（v2,v3）的顺流容量为2，决定了pf=2，改进的网络流量图如下图：.经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。最大流量图如下图：“管理运筹学软件”中还有专门的子程序用于解决最大流问题。. 最小费用最大流问题 最小费用最大流问题：给了一个带收发点的网络，对每一条弧（vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要求一个最大流F，并使得总运送费用最小。一、最小费用最大流的数学模型例7:由于输油管道的长短不一，所以在例6中每段管道（vi,vj）除了有不同的流量限制cij外，还有不同的单位流量的费用bij，cij的单位为万加仑/小时，bij的单位为百元/万加仑。如图。从采地v1向销地v7运送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最大流量和最小费用。.这个最小费用最大流问题也是一个线性规划的问题。解：我们用线性规划来求解此题，可以分两步走。第一步，先求出此网络图中的最大流量F，这已在例6中建立了线性规划的模型，通过管理运筹学软件已经获得结果。第二步，在最大流量F的所有解中，找出一个最小费用的解，我们来建立第二步中的线性规划模型如下：仍然设弧（vi,vj）上的流量为fij，这时已知网络中最大流量为F，只要在例6的约束条件上，再加上总流量必须等于F的约束条件：f12=f14=F,即得此线性规划的约束条件，此线性规划的目标函数显然是求其流量的最小费用。由此得到线性规划模型如下：..用管理运筹学软件，可求得如下结果：f12=4,f14=6,f25=3,f23=1,f43=3,F57=5,f36=2,f46=1,f47=2,f67=3,f35=2。其最优值(最小费用)=145。对照前面例6的结果，可对最小费用最大流的概念有一个深刻的理解。如果我们把例7的问题改为：每小时运送6万加仑的石油从采地v1到销地v7最小费用是多少？应怎样运送？这就变成了一个最小费用流的问题。一般来说，所谓最小费用流的问题就是：在给定了收点和发点并对每条弧(vi,vj)赋权以容量cij及单位费用bij的网络中，求一个给定值f的流量的最小费用，这个给定值f的流量应小于等于最大流量F，否则无解。求最小费用流的问题的线性规划的模型只要把最小费用最大流模型中的约束条件中的发点流量F改为f即可。在例6中只要把f12+f14=F改为f12+f14=f=6得到了最小费用流的线性规划的模型了。. 最小费用最大流的网络图论解法 对网络上弧（vi,vj）的（cij,bij）的表示作如下改动，用(b)来表示(a)。 用上述方法对例7中的图形进行改进，得图如下页：vivjvivj（cij,bij）（0,-bij）（a）（b）（cij,bij）（cij,bij）vivj（cji,bji）（cij,bij）vivj（cji,bji）（0,-bji)（0,-bji)（c）（d）. 求最小费用最大流的基本算法在对弧的标号作了改进的网络图上求最小费用最大流的基本算法与求最大流的基本算法完全一样，不同的只是在步骤（1）中要选择一条总的单位费用最小的路，而不是包含边数最小的路。.用上述方法对例7求解：第一次迭代：找到最短路v1v4v6v7。第一次迭代后总流量为1，总费用10。v5. 第二次迭代：找到最短路v1v4v7。第二次迭代后总流量为3，总费用32。. 第三次迭代：找到最短路v1v4v3v6v7。第三次迭代后总流量为5，总费用56。.第四次迭代：找到最短路v1v4v3v5v7。第四次迭代后总流量为6，总费用72。. 第五次迭代：找到最短路v1v2v5v7。第五次迭代后总流量为9，总费用123。.第六次迭代：找到最短路v1v2v3v5v7。第六次迭代后总流量为10，总费用145。已经找不到从v1到v7的每条弧容量都大于零的路了，故已求得最小费用最大流了。.如果对例7求一个最小费用流的问题：每小时运送6万加仑石油从v1到v7的最小费用是多少，或者每小时运送7万加仑呢？我们可以从第四次迭代及图11-32即可得到运送6万加仑最小费用72百元，其运送方式通过比较图11-28及图11-32即得图11-36所示。至于每小时运送7万加仑，我们可以在图11-36的基础上，再按第五次迭代所选的最短路运送1万加仑即得最小费用：72+1*17=89百元，其运送方式如图11-37所示。.注：“管理运筹学软件”有专门的子程序用于解决这类问题。.第十二章网络计划.第一节车间作业计划模型第二节统筹方法在本章中，我们将介绍车间作业计划模型和统筹方法。这两个问题尽管处理的方法有所不同，但当我们面临必须完成若干项不能同时进行的工作时，它们都将帮助我们应该按照怎样的次序、怎样的时间表来做这些工作，使得效果最佳（例如完成全部工作所用时间最短或费用最少等等）。. 车间作业计划模型车间作业计划是指一个工厂生产工序的计划和安排。 一、一台机器、n个零件的排序问题 二、两台机器、n个零件的排序问题. 车间作业计划模型 一台机器、n个零件的排序问题例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间.如下表所示。 应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零 件在车间里停留的平均时间为最少？ 零件 加工时间（小时） 零件 加工时间（小时） 123 1.82.00.5 456 0.91.31.5.车间作业计划模型例1解：如果我们用Pi表示安排在第i位加工的零件所需的时间，用Tj表示安排在第j位加工的零件在车间里总的停留时间，则有Tj=P1+P2+…+Pj-1+Pj=不同的加工顺序得到不同的各零件的平均停留时间，如何得到一个使得各零件的平均停留时间最少的排序呢？这就是我们最后要解决的优化问题，而且我们要设法找到一种简便的算法。对于某种加工顺序，我们知道安排在第j位加工的零件在车间里总的停留时间为Tj，Tj=可知这六个零件的停留时间为：T1+T2+T3+T4+T5+T6＝P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)＝6P1+5P2+4P3+3P4+2P5+P6.那么各个零件平均停留时间为从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。.两台机器、n个零件例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表12-5所示。表12-5 应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为 最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加 工零件的顺序与在磨床上加工零件的顺序是一样的。 如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1 中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和 车床、磨床在每个时间段的状况的图形所构成。 零件 车床 磨床 零件 车床 磨床 123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25.图12-1从上图中我们可以看出，加工时间的延长主要是由于磨床的停工待料造成的，只要减少磨床的停工待料的时间就能减少整个加工任务的总时间。为了减少磨床的停工待料，我们应该一方面把在车床上加工时间越短的零件越早加工，减少磨床等待的时间；另一方面把在磨床上加工时间越长的零件越晚加工，以便充分利用前面的时间，这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法。.寻找例2的最优解：我们在表12-5中找到所列出的最短加工时间是0.25,它是第二道工序磨床加工零件2的所需时间，由于这个时间与磨床有关，故我们把零件2放在加工顺序的末尾，即第五位，并在表中划去零件2所在行。如表12-6中红色线条所示。 接着，我们又找到最短加工时间为0.5，这一时间与磨床（第二工序）有关，我们把磨床加 工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把表中的零件1所在 的行划去。如表12-6中黄色线条所示。 下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故 把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所 示。表12-6 零件 车床（第一工序） 磨床（第二工序） 零件 车床（第一工序） 磨床（第二工序） 123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25.同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条所示。这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能完成全部加工。从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部任务总的时间最短的排序算法。在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所需时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量靠后。在表上划去零件j的所在行，回到步骤1。. 统筹方法统筹方法包括绘制计划网络图、进度安排、网络优化等环节，下面进行分别讨论：计划网络图统筹方法的第一步工作就是绘制计划网络图，也就是将工序（或称为活动）进度表转换为统筹方法的网络图。例3、某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12-8所示，请画出其统筹方法网络图。表12-8 工序代号 工序内容 所需时间（天) 紧前工序 abcde 产品设计与工艺设计外购配套零件外购生产原料自制主件主配可靠性试验 601513388 -aacb,d.解:用网络图表示上述的工序进度表,网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相邻工序在时间上的分界点,点用圆圈表示,圆圈里的数字表示点的编号。弧表示一个工序（或活动），弧的方向是从工序开始指向工序的结束，弧上是各工序的代号，下面标以完成此工序所需的时间（或资源）等数据，即为对此弧所赋的权数． １２４５３abcde601383815图12-4.例４、把例３的工序进度表做一些扩充，如表12-9，请画出其统筹方法的网络图。 表12-9 工序代号 所需时间（天） 紧前工序 工序代号 所需时间（天） 紧前工序 abcd 60151338 －aac efgh 810165 b，ｄdde,ｆ,ｇ.解：我们把工序ｆ扩充到图12-4发生了问题，由于ｄ是ｆ的紧前工序，故ｄ的结束应该是ｆ的开始，所以代表ｆ的弧的起点应该是④，由于工序ｂ的结束也是④，所以工序ｂ也成了工序ｆ的紧前工序，与题意不符。为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。　　　152643a60b158e1013dc38f图12-5.在网络图上添加ｇ、ｈ工序得网络图12-6。 　　　 在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加了 一个点和虚工序如图12-7。1256734a6015bec13d388h510fg16图12-6.在绘制统筹方法的网络图时，要注意图中不能有缺口和回路。1257834a6015bec13d388h510f616g图12-7. 网络时间与关键路线在绘制出网络图之后，我们可以由网络图求出：1、完成此工程项目所需的最少时间。2、每个工序的开始时间与结束时间。3、关键路线及其应用的关键工序。4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时间可以推迟多久。例5、某公司装配一条新的生产线，具体过程如表12-10,求：完成此工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以推迟多久。.表12-10 工序代号 工序内容 所需时间（天） 紧前工序 abcdefghij 生产线设计外购零配件下料、锻件工装制造1木模、铸件机械加工1工装制造2机械加工2机械加工3装配调试 60451020401830152535 /aaaacdd,egb,i,f,h.解：据表12-10,绘制网络图如图12-8。 图12-8 如图12-8,①-②-③-⑦-⑧就是一条关键路线，我们要干完所有的工 序就必须走完所有这样的路线，由于很多工序可以同时进行，所以网 络中最长的路线就决定了完成整个工程所需的最少时间，这条路线称 为关键路线。12346785a60b45echj35ig1030d204025f1815. 下面我们给出找关键路线的 办法 鲁班奖评选办法下载鲁班奖评选办法下载鲁班奖评选办法下载企业年金办法下载企业年金办法下载 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间（ES)和最早结束时间（EF)，设一个工序所需的时间为t，这对于同一个工序来说，有EF=ES+t。工序a的最早开始时间工序a的最早完成时间11a[0，60]60图12-9.图12-10其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF),显然对同一工序有LS=LF-t.运用此法则，可以从首点开始计算出每个工序的LF与LS，如图12-11所示。接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序的时差，对每个工序来说其时差记为Ts有Ts=LS-ES=LF-EF.最后将各工序的时差，以及其他信息构成工序时间表如表12-11所示。这样就找到了一条由关键工序a,d,g,i和j依次连接成的从发点到收点的关键路线。. 完成工序所需时间与关键路线当完成工序所需时间不确定的情况下如何求网络时间和关键路线？例6.长征研究院培训中心负责明年春天的各干部的工商管理培训，培训中心列出有关培训组织的各项活动的信息如表12-12所示，要求绘制出统筹方法的网络图，设法求出网络时间和关键路线，并确定开始这个组织工作的时间以保证培训工作如期举行。解：由表12-12，绘出统筹方法的网络图如图12-12所示。图12-12. 活动（工序） 活动（工序）内容 紧前活动（工序） abCdefgHi 制定培训计划选聘培训教师列出一些可供选择的培训地点确定培训地点确定培训的日程安排落实教学设备，器材，资料发培训通知并确定学员名单订旅馆房间处理最后的一些事务 -a-cb,deb,dgf,g.由于是第一次搞培训，缺乏统计来确定完成每个活动所需时间，但对所需时间做了三种估计：1.乐观时间。指所需最少时间，用a表示。2.最可能时间。指正常时间，用m表示。3.悲观时间。指不顺利情况下，最多时间，用b表示。如表12-13所示：表12-13单位：周 活动 乐观时间 最可能时间 悲观时间 abcdefghi 1.52.01.01.50.51.03.03.01.5 2.02.52.02.01.02.03.54.02.0 2.56.03.02.51.53.07.05.02.5.显然这三种完成活动所需时间都具有一定概率，由经验，我们可以可以假定这些时间的概率分布近似服从分布。我们可以用如下公式计算出完成活动所需的平均时间：以及方差例如：完成工作g所需平均时间：同时求出方差为.同样可以求出每个活动的完成所需平均时间及方差，如表12-14：表12-14 活动 T（平均时间） 方差 活动 T 方差 a 2 0.028 f 2 0.111 b 3 0.445 g 4 0.445 c 2 0.111 h 4 0.111 d 2 0.028 i 2 0.028 e 1 0.028.下面就用平均时间代替完成活动所需时间，并在网络图上标上每个活动最早开始时间和最早结束时间，如图12-14所示。同样也可以标上最晚开始时间和最晚完成时间等。.从表12-15上我们找到了一条从发点到收点由关键工序a,b,g,h,i组成的关键路线，用双线标出来。则完成培训工作所需的平均时间为各关键路线的时间之和：=2+3+4+4+2=15（周）=同时完成时间近似服从一定的概率分布正态分布，则均值为关键路线上各关键活动之均值之和15，方差也为关键路线上各关键活动方差之和1.05。由此我们可以计算出此项培训组织工作不同完工时间的概率，如16周内完工的概率。为求此概率，可以先求u值。式中的T为预定完工时间16，E（T）=15，算得u=0.976。查正态分布函数表可知概率为0.8355。即16周内完工的概率为83.55%..其正态分布图如图12-16所示：16图12-16. 网络优化得到初始的计划方案，但通常要对初始方案进行调整与完善。根据计划目标，综合考虑资源和降低成本等目标，进行网络优化，确定最优的计划方案。1.时间-资源优化做法：1）优先安排关键工序所需的资源。2）利用非关键工序的时差，错开各工序的开始时间。3）统筹兼顾工程进度的要求和现有资源的限制，多次综合平衡。下面列举一个拉平资源需要量最高峰的实例。在例5中，若加工工人为65人，并假定这些工人可完成这5个工序任一个，下面来寻求一个时间-资源最优方案。如表12-16所示：.表12-16若上述工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人人数如图12-17所示。 工序 需要人数 最早开始时间 所需时间 时差 d 58 60 20 0 f 22 70 18 47 g 42 80 3 0 h 39 100 15 20 i 26 110 25 0.在图的上半部中，工序代号后的数字是人数，线下面的数字是非关键工序时差长度。图的下半部表示从第60天至135天内的75天里，所需机械加工工人数，这样的图称为资源负荷图。f(22人）15图12-17.同时我们应优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰。经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始。找到了时间-资源优化的方案，如图12-18所示，在不增加工人的情况下保证了工程按期完成。图12-18.2.时间-费用优化需要考虑时间与费用的问题：在既定的时间前工程完工的前提下，使得所需的费用最少，或者在不超工程预算的条件下使工程最早完工。这些是时间-费用优化要研究和解决的问题。直接费用：为了加快工程进度，需要增加人力、设备和工作班次，这需要增加一笔费用，成为直接费用。间接费用：由于工程早日完工，减少了管理人员的工资办公费等费用称为间接费用。一般说工序越短，直接费用越多，间接费用越少。.工序的最快完成时间：指完成时间的最高限度。我们设完成工序j的正常所需时间为Tj;直接费用为cj;完成工序j的最快完成时间为T`j,直接费用为c`j。这样我们可以计算出缩短工序j的一天工期所增加的直接费用，用kj表示，称为直接费用变动率。有时间--费用优化问题可建立两个线性规划模型。模型一，在既定的时间T完工的前提下，问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少。设工序（i,j)的提前完工时间为Yij,我们用Tij,T`ij分别表示正常完工时间与最快完工的时间，则有工序（i,j)的实际完工时间为：Tij-Yij。我们用Cij,C`ij表示用正常完工时间和最快完成时间完成工序所需要的费用，Kij为工序（i,j)的直接费用变动率。得到这个问题的线性规划模型如下：minf=（Kij*Yij)（i,j)S.t.Xj-XiTij-Y`ij,对一切弧（i,j)YijTij-T`ij,对一切弧（i,j)Xn-X1T,Xi0，Yij0。.例7.例5所提供的信息都作为本例的信息，另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用，如表12-17所示。表12-17 工序 Tij正常完工 Cij直接费用 T`ij最快完工 C`ij直接费用 直接费用变动率 a 60 10000 60 10000 - b 45 4500 30 6300 120 c 10 2800 5 4300 300 d 20 7000 10 11000 400 e 40 10000 35 12500 500 f 18 3600 10 5440 230 g 30 9000 20 12500 350 h 15 3750 10 5750 400 i 25 6250 15 9150 290 j 35 12000 35 12000 -.该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。如果工期要求在140天完工呢？图12-19.解：绘出如图12-19所示，根据此网络图建立数学模型。设此网络图上第i点发生的时间为xi，工序提前完工的时间为yij。目标函数minf=120y27+300y23+400y24+500y25+230y37+350y46+400y57+290y67.s.t.x2-x160-y12,x7-x245-y27x3-x210-y23x4-x220-y24x5-x240-y25x7-x318-y37x6-x430-y46x5-x40虚拟弧（4，5）x7-x515-y57x7-x625-y67.x1=0,y120,y2715,y235y2410y255y378y4610y575y780x8150xi0，yij0.（对一切可能的ij)运算得到结果：f=6400。.模型二，我们知道直接费用是随着完成时间的缩短而增加，而间接费用却会随着完成时间的缩短而减少，设单位时间的间接费用为d,计划期的间接费用与总工期成正比，即为d(xn-x1),那么求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间的模型为：目标函数minf=d(xn-x1)+s.t.xj-xiTij-yij，对一切弧（i,j)yijTij-T`ij，对一切弧（i,j)xi0，yij0。.例8如果在例7中，每天的间接费用为330元，求使包括间接费用与直接费用在内的总费用最少的整个工程最优完成时间T和各个工序最优完成时间。解：决策变量的含义同例7。此数学模型的目标函数为：minf=330(x8-x1)+120y27+300y23+400y24+500y25+230y37+350y46+290y67此模型的约束条件与例7的约束条件基本相同，只要在例子的约束条件中去掉x8150就得到了例8模型的约束条件了。计算得到以下结果：f=55700.x1=0,y12=0,y67=10,x2=60,y27=0,y78=0..x3=125,y23=0,x4=107,y24=0,x5=110,y25=0,x6=110,y37=0,x7=125,y46=0,x8=160,y57=0, 也就是说整个工程工期为160天时总费用最少为55700元，各个工序开始 时间如解所示，工序i要提前10天完工，其余的工序按正常时间完 工。.第十一章存贮论.. 存储论简介 存储是常见的社会和日常现象 存储论的核心问题是成本分析. 存储论简介 存储的环节 存储模型的类别确定型存储模型不确定型存储模型.模型一：经济订购批量模型 模型假设及有关参数：需求是均匀的，单位时间的需求量为常数(D；时间通常以年为单位)；补充可以瞬时实现；采用t-循环策略，一次订货量为常数Q，订货周期为常数t；单位货物单位时间的存储费为常数C1；单位缺货费C2为无穷大（即不允许缺货）；每次订货费为常数C3；费用由存储费与订购费两部分组成；... 研究目的？确定怎么样的存储方案使得费用最少。 分析：总费用=总存储费用+总订购费用在总需求一定的情况下，存储费用与订购费用均由每次订货量Q决定。.每次订多少货?基本决策内容目标：费用最少！.定性分析：订货量Q总存储费总订购费越小越小越大越大越大越小.定量分析：为什么?.定量分析：就是存贮论中著名的经济订购批量公式。.定量分析：一个结论：按最优订购批量订购时产生的存储费与订货费是相同的。.经济订购批量模型最优订货量示意图费用订货量QQ*总存储费总订购费总费用.模型二：经济生产批量模型经济生产批量模型也称不允许缺货、生产需要一定时间模型，这也是一种确定型的存贮模型。它的存贮状态图为存贮量时间t生产时间不生产时间平均存贮量最高存贮量p-dd.模型二：经济生产批量模型这种存贮模型的特点：1.需求率（单位时间的需求量）为d；2.生产率（单位时间的产量）为p—有限供货率；3.不允许缺货；4.单位产品单位时间的存贮费c1；5.每次的生产准备费c3；6.每期初进行补充。.模型二：经济生产批量模型设每次生产量为Q，生产率是p，则每次的生产时间t为Q/p，于是最高库存量为(p-d)Q/p。到T时刻存贮量为0，则0到T时间内的平均存贮量为(p-d)Q/2p。故单位时间的存贮费为：另一方面，设D为产品的单位时间需求量，则单位时间的生产准备费为c3D/Q，进而，单位时间的总费用TC为：.使TC达最小值的最佳生产量单位时间的最低总费用生产量为Q＊时的最大存贮量为每个周期所需时间为显然，时，经济生产批量模型趋于经济订购批量模型。模型二：经济生产批量模型.例1.有一个生产和销售图书馆设备的公司，经营一种图书馆专用书架，基于以往的销售记录和今后市场的预测，估计该书架今年一年的需求量为4900个。存贮一个书架一年的费用为1000元。这种书架的生产能力为每年9800个，组织一次生产的费用为500元。为了降低成本，该公司如何组织生产？要求求出最优的生产量，相应的周期，最少的年度费用，每年的生产次数。解：从题可知，年需求率d=D=4900，年生产率p=9800,c1=1000,c3=500代入公式可得，模型二：经济生产批量模型.模型二：经济生产批量模型.THEEND！.*我纳闷*我们*我们