2375 运筹学基础

1、第1章1 运筹学是一门研究如何有效地组织和管理人机系统的科学。在管理领域，运筹学也是进行决策的计量方法。2 决策的分类1) 定性决策 根据主观经验和感觉进行决策2) 定量决策 借助计量方法做出决策3) 混合决策 运用定性和定量两种方法进行决策第2章1 预测方法1) 外推法 利用历史数据来预测事物发展趋势，常用的有时间序列分析法2) 因果法 利用事物内部因素的因果关系来预测事物的发展趋势，常用的有回归分析法2 预测时间1) 经济预测 长期3-5年；中期1-3年；短期年内2) 科技预测 长期30-50年；中期10-30年；短期5-10年3 定性预测，也叫判断预测法1) 特尔斐法 在“专家群”中取得

2、一致意见的方法匿名发表意见->多次反馈->取得共识。适用于中长期预测。2) 专家小组法 成立一个专家小组，面对面地进行讨论磋商，最后得出比较一致的意见。适用于短期预测。4 时间序列预测法的原理 1) 承认事物发展的延续性 2) 考虑事物发展中随机因素的影响和干扰5 时间序列预测法1) 滑动平均预测法(1) 简单平均预测法设某厂生产和销售某号电池6个月后，得到的出厂价格为：1元、1.1元、1.1元、1.2元、1.2元、1.3元，使用此方法预测的第7个月的出厂价格为 1+1.1+1.1+1.1+1.2+1.36=1.15(2) 加权平均预测法上例中，如果预测人员认为应加大最近的出厂价格

3、的指数，将它们分别定为1、2、2、3、3、4，使用此方法预测的第7个月的出厂价格为 1×1+1.1×2+1.1×2+1.1×3+1.2×3+1.3×41+2+2+3+3+4=1.192) 指数平滑预测法，公式如下：Ft+1 = Ft + a(xt Ft) = Ft + aetFt+1、Ft t+1期、t期的预测值xt t期的实际值a 平滑系数et t期的实际值与预测值之间的误差指数平滑预测是定量与定性方法相结合的一种预测方法。a的取值范围 0a1，当误差较大进，可加大平滑系数a的值。6 回归模型预测法1) 一元线性回归方程 y = a

4、 + bx2) 回归参数a、b的计算公式b= nxy- xynx2-x2 a= y-bxn3) 判断y与x之间相关程序的相关系数R的取值范围为 -1R1。当R=0时，y与x之间完全不相关，当R=±1时，y与x之间完全相关。4) 预测值不可能是一个确定值，应该是一个区间，一般要求实际值位于这个区间的概率应达到95%以上，这个区间称为预测值的置信区间。7 对季节性变动的预测，采用指数平滑预测法较好。第3章1 决策分类1) 常规性决策 例行的、重复性的决策 2) 特殊性决策 特殊的、无先例可循的决策2 决策步骤1) 选定目标 2) 拟定方案 3) 编制决策收益表(或损失表)，又叫决策矩阵

5、4) 选定最优方案3 自然状态 指不是决策者所能控制的未来状态4 不确定条件下的决策 存在一种以上的自然状态，但不知道它们发生的概率1) 最大最大决策标准，也称为乐观主义决策标准。选择原则为大中取大，首先选择每个方案的最大值，再选择其中最大的一个作为备选方案收益状态方案销路较好销路一般销路较差方案最大值较高价格出售(A1)中等价格出售(A2)较低价格出售(A3)20000016000012000012000016000012000080000100000120000200000160000120000最大最大标准200000所对应的方案为A1，方案的收益值为2000002) 最大最小决策标准，

6、也称为保守主义决策标准。首先选择每个方案的最小值，再选择其中最大的一个作为备选方案收益状态方案销路较好销路一般销路较差方案最小值较高价格出售(A1)中等价格出售(A2)较低价格出售(A3)2000001600001200001200001600001200008000010000012000080000100000120000最大最小标准120000所对应的方案为A3，方案的收益值为1200003) 最小最大遗憾值决策标准，将每种状态下的最大值减去其它值(称为遗憾值或后悔值)，找出每个方案的最大值，然后从中选择一个最小的作为备选方案收益状态方案销路较好销路一般销路较差较高价格出售(A1)中等价

7、格出售(A2)较低价格出售(A3)*200000160000120000120000*16000012000080000100000*120000遗憾值状态方案销路较好销路一般销路较差方案最大值较高价格出售(A1)中等价格出售(A2)较低价格出售(A3)040000800004000004000040000200000400004000080000最小最大遗憾值40000所对应的方案为A1、A2，两个方案的遗憾值均为400004) 现实主义决策标准，也称为折中主义决策标准。将方案中最好的状态的概率定为a，最差的状态的概率定义为1-a，a的取值范围为0<a<1。下表中，取a=0.8收

8、益状态方案销路较好销路一般销路较差折中方案值较高价格出售(A1)中等价格出售(A2)较低价格出售(A3)20000016000012000012000016000012000080000100000120000176000148000120000最大折中值176000所对应的方案为A1，折中收益为176000。各方案的折中收益计算方法：A1 = 200000 x 0.8 + 80000 x (1 0.8) = 176000A2 = 160000 x 0.8 + 100000 x (1 0.8) = 148000A3 = 120000 x 0.8 + 120000 x (1 0.8) = 120

9、0005 风险条件下的决策 存在一种以上的自然状态，并且知道它们发生的概率1) 最大期望收益值标准，先计算方案各状态的条件利润，再计算方案的期望利润，最后选中期望利润最大的方案作为备选方案。下表中，假设每本利润为30元，成本为50元，折余值为20元。从表中可以看出，最优方案为A3，期望利润为4860状态条件利润概率方案售出150本(B1)售出160本(B2)售出170本(B3)售出180本(B4)期望利润0.10.20.40.3购进150本(A1)购进160本(A2)购进170本(A3)购进180本(A4)45004200390036004500480045004200450048005100

10、480045004800510054004500474048604740最大期望收益值4860现以A4方案为例，各状态的条件利润为B1 = 150*30 (180-150)*50 + (180-150)*20 = 3600B2 = 160*30 (180-160)*50 + (180-160)*20 = 4200B3 = 170*30 (180-170)*50 + (180-170)*20 = 4800B4 = 180*30 (180-180)*50 + (180-180)*20 = 5400A4方案的期望利润为3600*0.1+4200*0.2+4800*0.4+5400*0.3=47402

11、) 最小期望损失值标准，先用各状态下的最大值减去其它值，再计算方案的期望损失值，最后选中期望损失最小的方案作为备选方案。以上表为例，对角线上半部分为机会损失，下半部分为报废损失。最优方案为A3，期望损失值为210状态条件利润概率方案售出150本(B1)售出160本(B2)售出170本(B3)售出180本(B4)期望损失0.10.20.40.3购进150本(A1)购进160本(A2)购进170本(A3)购进180本(A4)0300600900300030060060030003009006003000570330210330最小期望损失值210各方案的期望损失值计算如下：A1 = 300*0.2

12、+600*0.4+900*0.3=570A2 = 300*0.1+300*0.4+600*0.3=330A3 = 600*0.1+300*0.2+300*0.3=210A4 = 900*0.1+600*0.2+300*0.4=3306 决策树 - 以下表为例，有3个备选方案，各方案的投资额分别为100万、200万、20万，企业经营期为10年，画出决策树状态条件利润概率方案销路好销路一般销路差销路极差期望收益值0.50.30.10.1扩建(100万)新建(200万)联营(20万)507030253015-25-40-5-45-80-1025.53218第4章1 存货台套法 以存货台套作为存货管理

13、的单位，在存货台套中包括相关的各种单项存货2 ABC分析法 按存货台套或存货单元的年度需用价值，将它们分为A、B、C三类，分别采用不同的管理方法1) A类：数量10%，总价值70%，某些需要特殊保存方法的存货单元(易燃、易爆、剧毒等)，也归入此类2) B类：数量30%，总价值20%3) C类：数量60%，总价值10%3 建立库存模型主要是为了探讨库存数量与库存费用之间的关系，即寻求库存费用最低的采购量或生产批量4 两类库存模型1) 原材料库存费用模型 库存费用 = 订货费用 + 保管费2) 半成品和成品库存费用模型 库存费用 = 工装调整费 + 保管费5 三种库存费用1) 订货费：当安排某项订

14、货时，每一次都要承担的费用。订货费=年需求量订货量×一次订货费其中，运费包含在物品单价，也即物品单价=进厂价=出厂价+运费2) 工装调整费：进行批量生产时，调整工艺、设备所需的费用。工装调整费=年计划产量生产批量×一次工装调整费3) 保管费：保管库存物资所需的费用。多采用保管费率的方式，即用库存资金的百分比表示。椐统计，保管费平均占库存的20%以上。6 平均库存量和平均库存额平均库存受订货量和订货次数的影响，等于订货量的一半，相应地，平均库存额等于最高存货额的一半7 经济订货量 使全年的保管和订货总费用达到最小值的最佳订货量。经济订货量的保管费用与订货费用必然相等。计算公式

15、如下 N=2APR2C，其中N: 经济订货量 A: 全年所需的台套总值 P: 每次订货费用 R: 台套单位价格 C: 用百分比表示的保管费率8 每次订货的最佳总金额计算公式：P=2APC；最佳订货次数计算公式：Z=AC2P9 再订货点有两种含义：一种是时间上的含义，即什么时间为某项存货再订货；另一种是存货水平上的含义，即某项存货的存量达到什么水平时，就应再订货。10 安全库存量，也称为保险库存量，是为了预防可能出现的缺货现象而保持的额外库存量。11 正确评估折扣，主要是比较全年的采购价+订货费用+保管费用第5章1 线性规划的基本解法有图解法和单纯形法两种。图解法又称几何法，一般只适用于2-3个

16、变量的情况；单纯形法适用于多变量的情况2 图解法1) 求最大值设某家具厂生产桌子和碗橱两种产品，分别由加工、装配、油漆三个工序组成，两种产品的相关数据如下：工段工时定额可用工时桌子X1碗橱X2加工装配油漆4时/张2时/张2时/张2时/个4时/个3时/个604836利润8元/张6元/个要求在不超过可用工时的情况下，通过合理搭配获取最大利润，建立线程规划模型并求出最优解目标函数：极大值S = 8X1 + 6X2约束条件：4X1 + 2X2 602X1 + 4X2 482X1 + 3X2 36X1 , X2 0(1) 画出几何图形(2) 将各极点的值代入目标函数，求得最大利润2) 求最小值某林场需药

17、水500公斤，该药水由甲(5元/公斤)、乙(8元/公斤)两种药水混合而成，要求甲药水不能超过400公斤，乙药水不少于200公斤。要求通过合理搭配，使成本最小，建立线程规划模型并求出最优解目标函数：极小值S = 5X1 + 8X2约束条件：X1 400X2 200X1 + X2 = 500X1 , X2 0(1) 画出几何图形(2) 将各极点的值代入目标函数，求得最小成本3 单纯形法1) 求最大值设某电视机厂生产两种电视，每种电视要依次经过两条流水线进行装配。其数据如下表所示，如何搭配生产两种电视才能获取最大利润？工时工段工时定额可用工时彩色电视机黑白电视机装配线1装配线223418060单位利

18、润10080目标函数：极大值S = 100X1 + 80X2约束条件：2X1 + 4X2 80 3X1 + X2 60 X1、X2 0(1) 引入辅助变量，建立初始单纯形表100X1 + 80X2 + 0K1 + 0K2= S2X1 + 4X2 + K1 = 803X1 + X2 + K2 = 60Cj基变量100X180X20K10K2S00K1K223411001806080/2=4060/3=20，退基ZjCj - Zj010008000000S非基变量为0基变量为0X1，也就是系数最大者，入基(2) 换基。根据以下公式：3X1 + X2 + K2 = 60 -> X1 + X2/

19、3 + K2/3 = 20 -> X1 = 20 - X2/3 - K2/32X1 + 4X2 + K1 = 80 -> 2(20 - X2/3 - K2/3) + 4X2 + K1 = 80 -> 103X2- 23K2+ K1=40 Cj基变量100X180X20K10K2S0100K1X10110/31/310-2/31/34020ZjCj - Zj1000100/3140/300100/3-100/32000S-2000非基变量为0基变量为0(3) 重复第2步，真到Cj - Zj行所有系统为0或负数。2) 求最小值目标函数：极小值S = 4X1 + 3X2约束条件：2

20、X1 + 4X2 16 3X1 + 2X2 12 X1、X2 0(1) 引入辅助变量，建立初始单纯形表S = 4X1 + 3X2 + 0K1 + 0K2 + MA1 + MA22X1 + 4X2 K1 + A1 = 163X1 + 2X2 - K2 + A2 = 12Cj基变量4X13X20K10K2MA1MA2SMMA1A22342-100-11001161216/4=4，A1出基12/2=6Zj1Zj2Cj - Zj1 - Zj22M3M4-5M4M2M3-6M-M0M0-MMM000M016M12MS-28M非基变量为0，也即MA1 + MA2基变量为0因为M是一个很大的正数，所以选X2

21、入基有助于降低目标函数值(2) 换基，同上例(3) 重复第2步，同上例第6章1 需求量等于供应量的运输问题设某公司有三个采石场，供应能力如下：W厂(56车/周)、X厂(82车/周)、Y厂(77车/周)，公司的客户有3个工程段，各工程段的需求量如下：A段(72车/周)、B段(102车/周)、C段(41车/周)，3个采石场到3个工程段的运费如下表所示，按要求完成下列任务采石场工程段A段B段C段W场X场Y场401608080240160801602401) 建立运输图从到A段B段C段供应量W场40808056X场16024016082Y场8016024077需求量7210241215215152)

22、求原始方案(1) 从西北角开始，将第一行(W场)的供应量先分配给第一列(A段)(2) 当W场供应量大于A段所需时，剩余的往B段分(3) 当W场供应量小于A段所需时，转入第二行分配，依此类推从到A段B段C段供应量W场4056808056X场160162406616082Y场80160362404177需求量7210241215 215总运费：56x40 + 16x160 + 66x240 + 36x160 + 41x240 = 362403) 求改进方案(1) 挑选绝对值最大的改进指数(最小的负数)进行调整(2) 当各个空格的改进指数都大于或等于0时，就是最优方案2需求量小于供应量的运输问题1)

23、 虚设一个需求点，需求量=总供应量-总需求量2) 任何供应点到虚设的需求点的运费都是0在第1个例子中，将W厂的供应量增加到76车后，原始的运输方案如下从 到A段B段C段D段(虚设)供应量W场407280480076X场16024082160082Y场80160162404102077需求量721024120235235215总运费：72x40 + 80x4 + 82x240 + 16x160 + 41x240 + 0x20 = 352803需求量大于供应量的运输问题1) 虚设一个供应点，供应量=总需求量-总供应量2) 虚设的供应点到任何需求点的运费都是0在第1个例子中，将A点的需求增加到82车

24、，C点的需求增加到61车后，原始的运输方案如下从到A段B段C段供应量W场4056808056X场160262405616082Y场80160462403177Z场(虚设)0003030需求量8210261245245215总费用：56x40 + 26x160 + 56x240 + 46x60 + 31x240 + 30x0 = 34640第7章1 网络图1) 网络图分类(1) 箭线式：以箭线代表活动，以结点代表活动的开始和完成(2) 结点式：以结点代表活动，以箭线代表活动之间的承接关系未讨论2) 箭线式网络图构成(1) 活动有些活动需要消耗资源，有些不需要消耗资源，但都需要占用时间。在不按时间

25、坐标绘制的网络图中，箭线的长短与活动消耗的时间不成比例。虚活动不消耗资源，不占用时间。两种情况下需引进虚活动：一是两个以上的活动具有同一个始点和终点，二是为了表示各活动之间的先后承接关系(2) 结点结点不占用时间，也不消耗资源。一个规划一般只有一个总开始点(开工)和一个总结束点(完成)。除始点和终点外，中间的结点具有两重性，即对结点前面的活动而言，它是终点，对结点后面的活动而言，它是始点。结点的编号原则：箭尾结点小于箭头结点，而肯采用非连续编号(3) 线路从始点到终点，经过的箭线和结点联结起来，构成一条线路。在一条线路上，把各活动的作业时间加起来，就是该线路的总作业时间也称路长。总作业时间最长

26、的线路就是关键线路，它决定整个网络计划的完工时间，用双线或红线标出。网络分析主要是找出关键线路，因为它决定着总完工期。2 网络时间 图上计算法重点、表格计算法、矩阵计算法1) 相关符号：结点符号。上半部分是结点号；下半部分左侧是最早开始时间，右侧是最迟完成时间：活动最早开始/完成时间符号。该符号放在箭线的上方：活动最迟开始/完成时间符号。该符号放在箭线的下方2) 作业时间 完成一项活动所需的时间。确定作业时间，有两种方法：(1) 单一时间估计法，参照同类活动的统计资料，确定一个时间值(2) 三种时间估计法，先估计三个时间值(a - 最乐观时间，b - 最保守时间，m - 最可能时间)，再求出一

27、个时间值(a+4m+b6=16a+46m+16b)3) 结点时间(1) 结点最早开始/完成时间 两者是同一个时间，对后续活动而言是最早开始时间，对前接活动是最早完成时间。从网络的始点开始(0)，自左向右，顺着箭线的方向，直至终点。计算公式ESj = maxi<j ESi + Ti,j(2) 结点最迟开始/完成时间 两者是同一个时间，对后续活动而言是最迟开始时间，对前接活动是最迟完成时间。从网络的终点开始(总工期)，自右向左，逆着箭线的方向，直至始点。计算公式LFj = mini<j LFi - Ti,j4) 活动时间1) 最早开始时间，顺着箭线的方向，逐个计算2) 最早完成时间，顺

28、着箭线的方向，逐个计算3) 最迟开始时间，逆着箭线的方向，逐个计算4) 最迟完成时间，逆着箭线的方向，逐个计算3 网络时差 代表机动时间，可以利用时差去支援关键线路1) 结点时差：Si = LFi ESi，即结点下半部分右侧和左侧之差。结点时差等于0的结点，叫关键结点。2) 活动时差(1) 总时差：最迟开始时间和最早开始时间之差，或者最迟完成时间和最早完成时间之差。关键活动的总时差等于0。(2) 局部时差1：开始结点的时差(3) 局部时差2：完成结点的时差(4) 专用时差：总时差 局部时差1 局部时差23) 线段时差：线段各个活动之中总时差最大者。4) 线路时差：从始点到终点各条线路的时差。关

29、键线路的线路时差等于0。4 网络优化1) 时间优化(1) 采取措施缩短关键活动的时间 (2) 利用时差支援关键活动2) 时间与资源优化(1) 优先保证关键活动和时差较小活动的需求 (2) 合理利用资源，避免骤增、骤减3) 时间与成本优化(1) 直接费用指直接构成产品成本的费用，如材料费和工人工资；间接费用指不能直接按产品计算的费用，如管理费、办公费(2) 直接费用占总成本的比重较大，又与工期的长短直接相关，是时间与成本优化的重点(3) 完成一项活动的时间介于极限时间和正常时间之间，对应的费用称为正常费用和极限费用(赶工费用)，根据它们之间的关系，可以求出直接费用增长与作业时间缩短之间的比率，即

30、直接费用增长率=极限费用-正常费用正常时间-极限时间(4) 时间与成本优化原则a) 在关键路线上，缩短费用增长率最低的活动的作业时间 b) 利用非关键线路上的时差第8章1 图是反映对象之间关系的一种工具。树是连通的、不含圈的图。树中的线数必定是点数减1。 2 最小枝杈树问题1) 在所有可以连通网络结点的方案中，找出长度最短的或费用最低的一个。2) 两种方法：a) 普赖姆法各种网络，重点 b) 克鲁斯喀尔法小网络3) 普赖姆法算法步骤:(1) 从始点出发，找到与始点最近/费用最低的点(2) 找到最近/费用最低的未连通点，加入网络(3) 重复第2步，直到连通整个网络3 最短路线问题1) 从终点开始

31、逆向运算，标记每一个到终点的节点的距离和路径2) 向上逆推一级节点，计算到上1级的最短距离和路径3) 重复第2步，只到始点4 最大流量问题1) 选择任意一条线路，找出流量最低的支线，标记在各支线尾部，在各支线头部标出剩余流量2) 重复第一步，只到找不出流量大于0的线路3) 将找到的各个线路的流量相加第9章1 矩阵乘法设某厂有甲、乙两个车间，分别生产产品A1、A2、A3，产量如下A1A2A3甲a11a12a13乙a21a22a23现制定两套价格方案A1b11b12A2b21b22A3b31b32按这两套销售方案，甲、乙两个车间的销售总收入分别为甲c11c12乙c21c22其中c11 = a11

32、b11 + a12 b21 + a13 b31c12 = a11 b12 + a12 b22 + a13 b32c21 = a21 b11 + a22 b21 + a23 b31c22 = a21 b12 + a22 b22 + a23 b322 基本概念1) 概率向量 内部元素为非负，且总和等于1的向量2) 概率矩阵(方阵) 内部各行都是概率向量的矩阵(方阵)3) 马尔柯夫分析 通过分析某变量的当前状况来预测该变量的未来状况的一种方法3 马尔柯夫分析过程1) 分析品牌转换数据设某小区的牛奶全部由A、B、C三个年牛奶场供应。三个奶厂的订户转移情况如下：奶厂6月1日订户数获得损失保持概率7月1日

33、订户数从A从B从C给A给B给CABC200500300020203501525200035252002020150160/200=0.8450/500=0.9255/300=0.852204902902) 建立转换概率矩阵根据以上数据，得出概率矩阵：ABCABC160/200=0.835/500=0.0725/300=0.08320/200=0.1450/500=0.920/300=0.06720/200=0.115/500=0.03255/300=0.85进一步简化后，得得到ABCABC0.80.070.0830.10.90.0670.10.030.85行表示丧失的订户，列表示获得的订户数3

34、) 计算未来的市场份额要预测8月1日的数据，将7月1日的市场份额排成矩阵x转换概率矩阵0.80.10.1(0.22, 0.49, 0.29) x0.070.90.030.0830.0670.85 0.22x0.1 + 0.49x0.03 + 0.29x0.85)= (0.234, 0.483, 0.283)要预测9月1日的市场份额，有2种办法(1) 将8月1日的市场份额x转换概率矩阵(2) 将7月1日的市场份额x转换概率矩阵20.80.10.1 2(0.22, 0.49, 0.29) x0.070.90.030.0830.0670.854) 确定最终的市场份额将转换概率改写成三个方程式：(1) A = 0.8A + 0.07B + 0.083C(2) B = 0.1A + 0.9B + 0.067C(3) C = 0.1A + 0.03B + 0.85C由于三个市场份额之和等于1，所以可添加别一个方程式(4) 1 = A + B + C可以选前3个中的任意2个和第4个方程式求出A、B、C的市场份额第10章1 盈亏分析模型的结