运筹学教材课件汇总完整版ppt全套课件最全教学教程整本书电子教案全书教案合集最新课件汇编

1、第一章 绪论运 筹 学（Operations Research） 运筹学的产生和发展 运筹学作为一门数学学科，用纯数学的方法来解决最优方法的选择安排，却是在二十世纪四十年代才开始兴起。 运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。随着客观实际的发展，运筹学的许多内容不但研究经济和军事活动，有些已经深入到我们的日常生活当中去了。 运筹学的研究方法有：（1）从现实生活中抽出本质的要素来构造数学模型，因而可寻求一个跟决策者的目标有关的解；（2）探索求解的结构并导出系统的求解过程；（3）从可行方案中寻求系统的最优解法。运筹学的主要内容 数学规划线性规划非线性规划整数规划

2、参数规划动态规划目标规划 排队论库存论图论博弈论运筹学的主要内容 数学规划线性规划 约束条件和目标函数都是线性函数的数学规划； 主要解法是：单纯形法； 主要应用于企业规划和工农业的管理决策等方面。 非线性规划 它是线性规划的进一步发展和继续。许多实际问题如设计问题、经济平衡问题都属于非线性规划的范畴。 整数规划 整数规划是研究决策变量取正整数或部分取整数的一类规划问题。 运筹学的主要内容 数学规划参数规划 参数规划是系数或常数项中带有参数的规划问题，主要研究问题的解法：当参数在什么范围变化时问题有解以及参数的变化对最优解的影响。动态规划 它是与时间有关的规划问题，它是研究多阶段决策过程最优化问

3、题。目标规划 目标规划就是在给定的决策环境中，使决策结果与预定目标的偏差达到最小的数学模型。 与线性规划有很大的区别，主要表现在：在线性规划中，要求单个目标的优化，而目标规划则强调使多个目标得到满意的解答。另一方面，线性规划中，为得到一个可行解，必须满足所有的约束条件。 运筹学的主要内容 排队论 它是运筹学的又一个分支，它也叫做随机服务系统理论。它的研究目的是要回答如何改进服务机构或组织被服务的对象，使得某种指标达到最优的问题。 因为排队现象是一个随机现象，因此在研究排队现象的时候，主要采用研究随机现象的概率论作为主要工具。 库存论 它是一种研究物资最优存储及存储控制的理论。 图论 图论是研究

4、由节点和边所组成的图形的数学理论和方法 博弈论 博弈论是使用严谨的数学模型研究冲突对抗条件下最优决策问题的理论。 运筹学在管理中的应用 工程管理与优化设计 生产计划与管理 市场营销管理 库存管理 会计与财务分析及管理 人力资源管理 设备维修、更新和可靠性、项目选择和评价等 物流管理与交通运输问题 教学要求：第二章 线性规划和单纯形法 掌握线性规划的基本建模法和单纯形法基本原理会在不同条件下运用单纯形法求解线性规划问题了解线性规划在经济和管理中的基本应用方法目 录线性规划实例与模型线性规划的图解法与基本性质单纯形法原理线性规划的初始解解法目 录线性规划实例与模型线性规划的图解法与基本性质单纯形法

5、原理线性规划的初始解解法实用举例 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元

6、。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？实用举例 某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。 通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。 通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是

7、10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解！线性规划模型的建立 建立相应的线性规划模型 ：其中的 称为决策变量。目标函数约束条件一般线性规划模型Max z = c1x1 + c2x2 + + cnxns.t. a11x1+ a12x2 + + a1nxn = b1 ( 0) a21x1+ a22x2 + + a2nxn = b2 ( 0) : am1x1+ am2x2 + + amnxn= bm( 0) x1,x2 , ,xn 0s.t. 为约束限制（Subject to）的缩写(LP)x1.xnb1.bma11 a1nam1 am

8、nx =b =A = c =其中c=(c1,c2,cn)，称为价值系数向量；称为资源限制向量 X=(x1,x2,xn)T 称为决策变量向量称为技术系数矩阵(也称消耗系数矩阵)一般线性规划模型线性规划模型的标准形式Max Z = c1x1 + c2x2 + + cnxnSubject to (s.t.)a11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2 + + a2nxn = b2 am1x1 + am2x2 + + amnxn= bmx1 0, x2 0, , xn 0为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即标准化原问题标准化方法目标

9、函数Max f(x)Max f(x)Min f(x)Max f(x)约束条件引入松弛变量和人工变量引入松弛变量, 不变变量 不变对某个对某个是任意的 线性规划模型的标准化例:将如下线性规划模型标准化：min z= x1 + 5 x2 - 8 x3 - x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束。 max z1=-x1-5 x2+8 x3 +x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 - x

10、4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束。 目标优化标准化线性规划模型的标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0 决策变量的标准化: y2 - y3 = x2max z1=-x1-5 x2+8 x3 +x4s.t. 2 x1 - 3 x2 + x3 + x4 20 x1+ 2 x2 + 3 x3 -

11、 x4 30 2x2 + 2 x3 +3 x4- 50 x1 , x3 , x4 0，x2取值无约束 线性规划模型的标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 +x5 =20 -x1- 2 y2 +2y3 - 3 x3 + x4 +x6 = -30 -2y2 +2y3 - 2 x3 -3 x4 +x7 = 50 x1 , x3 , x4 , x5, x6, x7, y2, y3 0约束关系标准化Max z2 =-x1-5y2+5y3+8x3+x4 s.t. 2 x1 - 3 y2+3y3 + x3 + x4 20 -

12、x1- 2 y2 +2y3 - 3 x3 + x4 -30 -2y2 +2y3 - 2 x3 -3 x4 50 x1 , x3 , x4 ,y2,y3 0 可行解:满足所有约束条件的解x=（x1，x2，.，xn），称为线性规划问题的可行解。所有可行解的集合称为可行域。基：设A是约束方程组的mn阶系数矩阵，秩为m， 是A中阶非奇异子矩阵（即 ），则称是线性规划问题的一个基矩阵，简称基。B中的列向量称为基向量，与基向量对应的变量x称为基变量，其它变量称为非基变量。 基本解：令非基变量=0，则由Ax=b可求出一个解，这个解x称为基本解。基本可行解：满足非负条件的基本解称为基本可行解。最优解：使目标函

13、数达到最优值的可行解称为最优解。 线性规划的解 可行解、基本解、基本可行解的关系可行解基本解基本可行解目 录线性规划实例与模型线性规划的图解法与基本性质单纯形法原理线性规划的初始解解法线性规划的图解法 当只有两个决策变量时，可用图解法求解！例：用图解法求解以下线形规划问题。 max z=4x1+3x2 s.t. x16 2x28 2x1+3x218 x10，x20 x1 x2 L3：2x1+3x2=18可行域L1：x1=6L2：x2=4最优解B4x1+3x2解的特殊情况多个最优解解的特殊情况无可行解解的特殊情况无界解线性规划的基本性质 X可行域内部的点 可行解? 是 最优解? 不 若线性规划有

14、最优解，则最优解必在可行域的顶点上达到。凸集的概念 凸集是线性规划中一个很重要的概念，凸集的一般定义为：如果在集合C中任意取两个点x1，x2，其连线上的所有点也都在集合C中，则称集合C为凸集合。用数学解析式表达为：对任意 ，均有 ，则称C是凸集合。非凸集非凸集凸集线性规划的基本性质 定理2.1：线性规划的可行域： 是凸集（凸多面体）。 引理2.1：线性规划的可行解 为基本可行解的充分必要条件是x的正分量所对应的系数列向量是线性无关的，即每个正分量都是一个基变量。 定理2.2：线性规划问题的基本可行解x对应于可行域的顶点 定理2.3：若线性规划有最优解，则最优解必在可行域的顶点上达到。目 录线性

15、规划实例与模型线性规划的图解法与基本性质单纯形法原理一、初始基本可行解的确定考虑如下形式的线性规划问题max z=c1x1+c2x2+.+cnxn s.t. a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 (2.17） . am1x1+am2x2+ +amnxnbm x1，x2，.，xn0 （2.18）对每个不等式约束引入一个非负松弛变量，得标准形式：max z=c1x1+c2x2+.+cn xns.t. a11x1+a1nxn+xn+1 =b1 a21x1+a2nxn +xn+2 =b2 （2.19） . am1x1+amn xn +xn+m =bm x1，x

16、2，.，xn，xn+1，xn+m0是线性规划(2.19)的一个可行基。令 得由此得到一个初始基本可行解为二、最优性检验 定理2.4： 在最大化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。 在最小化问题中，对于某个基本可行解，如果所有 的 ，则这个基本可行解是最优解。单纯形法求解步骤将所给问题化为标准形找出一个初始可行基,建立初始单纯形表检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步)考察是否无解(若是,计算停止,否则继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换单纯形方法的一般步骤确定一个初始可行角点根据某种法则进行角点的最优性判

17、断不是最优角点是最优角点考察与当前角点相邻的 “更好”的一个角点，并置为当前角点。根据某种法则进行LP的无界或不可行判断无界或不可行还不能做出判断求解结束单纯形法举例解：引进松驰变量x3, x4，化为标准形得： 4 3 0 0 CBXBb x1 x2 x3 x4 b/y00 x3x42426 2 3 1 0 24/2 3 2 0 1 26/3 0 4 3 0 04=4（03+02）；3=3（02+03） 4 3 0 0CBXBb x1 x2 x3 x4 b/y04x3x120/326/3 0 5/ 3 1 -2/3 1 2/3 0 1/3 -104/3 0 1/3 0 -4/3 4 3 0 0

18、CBXBb x1 x2 x3 x434x2x146 0 1 3/5 -2/5 1 0 -2/5 3/5 36 0 0 -1/5 -6/5表中最后一行的所有检验数均为非正数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为Z=36 4 3 0 0CBXBb x1 x2 x3 x4 b/y04x3x120/326/3 0 5/ 3 1 -2/3 4 1 2/3 0 1/3 13 -104/3 0 1/3 0 -4/3大M法基本思想：在约束条件中增加人工变量，同时修改目标函数，对目标函数加上具有很大正系数M的惩罚项，为使人工变

19、量不影响目标函数取值，在迭代过程中，应把人工变量从基变量中退出，使其成为非基变量。 其中，M是很大的正数，同时增加两个人工变量。 不容易找到初始可行解找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00 要求最后得到的基变量中不含人工变量X1进基，x7出基11-300MMbi/yibx1x2x3x4x5x6x7-3X340011/3-2/32/3-5/31X210100-11-211X191002/3-4/34/3-7/30001/31/3M-1/3M-2

20、/3 可以从表中移去，然后继续求解 经过几次变换，得到基变量为x1，x2，x3两阶段法原理两阶段法的第一阶段是用单纯形法 消去人工变量，即把人工变量都变为非基变量，求出原问题的一个基本可行解。如果第一阶段求解结果表明问题有可行解时，进行第二阶段，就是从得到的基本可行解出发，用单纯形方法求原问题的最优解。两阶段法举例例：第一阶段：第二阶段：用单纯形法求得第一阶段的解为： 用单纯形法求解规划问题得最优解 目标函数的最优解是 Excel Solver（规划求解） Excel采用了电子表格的形式，帮助管理者提高数据管理的能力，因而得以广泛应用。Solver插件专门用于求解带约束的最优化问题。 Solv

21、er“规划求解”，可在Excel的工作表中根据对话框提示调用该项功能。加载 “规划求解”如果在您的Excel中，没有在“工具”菜单中发现“规划求解”，请在下图所示的界面中点击“加载宏”。加载 “规划求解”点击“加载宏”后，显示界面如下：如果列表中没有 “规划求解”，表明您还没有安装该插件。这时，您需要插入Microsoft Office安装盘，选择“添加安装”后选择该插件的安装。第1步 导入已知数据可采用 复制粘贴 或 直接输入 的方式导入数据。第2步 确定 可变单元格 可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数图中，规定B16、C16为可变单元格第3步 确定 目标单元格 在

22、目标单元格中，需要填入计算目标函数值的公式。第4步 确定 约束单元格 在约束单元格中，需要填入计算约束函数值的公式。第5步 调用 规划求解 模块在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。第6步 填写目标单元格和可变单元格第7步 添加约束第8步 “选项”设置选择：采用线性模型，假定非负。 如果求解过程在找到结果之前即达到最长运算时间或最大迭代 次数，则会弹出 “显示中间结果” 对话框。第9步 保存求解结果显示求解结果使用Excel求解例2.10掌握线性规划对偶理论及其基本经济学意义；第三章 线性规划对偶理论及其应用教学要求：了解运用对偶理论对线

23、性规划最优解进行分析的基本方法；会运用对偶理论对一些基本的管理问题进行经济学分析。目 录线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析目 录线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析对偶问题的提出 某工厂甲生产A、B、C三种产品。这三种产品的单位利润分别是60、30、20。生产这三种单位产品所占用M、N、P三种机器的时间已知，机器M、N、P每天可供使用的时间分别是48、20、8小时。这三种产品每天生产多少才能使工厂获得最大效益。现有另一工厂乙，因生产需要。拟向甲厂租用所有的机器，则乙厂希望租金越少越好，当然必须保证甲厂的利润。显然，如果甲厂的利润

24、得不到保证，甲厂是不可能出租的。 原问题对偶问题当 时，工厂的决策者认为这两种考虑有相同结果，都是最优方案！ 对偶问题的一般形式 原线性规划问题（LP） 原问题（LP）的对偶问题（LD）对偶问题的变量表示单位资源的价值。 在实际问题中，对偶问题的目标函数表示可利用资源的数量。最小化问题的对偶问题的一般步骤对偶问题是最大化；当原问题有n个决策变量，则对偶问题有n个约束条件。对偶问题的第一约束条件对应的是原问题中的x1变量，对偶问题的第二个约束条件对应的是原问题中的x2变量，依此类推。当原问题有m个约束条件，则对偶问题有m个决策变量。对偶问题的u1变量对应的是原问题中的第一约束条件，对偶问题的u2

25、变量对应的是原问题中的第二约束条件，依此类推。原问题的约束条件的右侧值成为对偶问题的目标函数系数。原问题的目标函数系数成为对偶问题中的约束条件的右侧值。目标函数中原问题第i个变量的系数成为对偶问题中第i个约束条件的常数项。 原问题与对偶问题线性规划问题的对偶问题举例写出下列线性规划问题的对偶问题：先化为最小化问题：最小化问题的对偶问题：也可把对偶问题化为最小化问题： 变成目标函数的系数系数变成约束条件右侧值变成第一个约束条件的系数目 录线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析对偶规划的基本性质 一、对称性 对偶问题的对偶问题就是原问题。即对偶问题与原问题互为对偶问题

26、。二、弱对偶性如果x，u分别是原问题和对偶问题的可行解，则 。 三、最优性 如果x，u分别是原问题和对偶问题的可行解,且 则 x，u分别是原问题和对偶问题的最优解。四、强对偶性 若原问题有最优解x，则对偶问题也有最优解y，且目标函数值相等，即 。 五、松驰性 设 ， 分别是原问题和对偶问题的可行解，则 ， 是最优解的充要条件是对所有的i和j，下列关系成立： 1如果 ，有 ； 2如果 ，有 ； 3如果 ，有 ； 4如果 ，有 。 其中pj是A的第j列，Ai是A的第i行。 对偶规划的基本性质 目 录线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析对偶单纯形法的计算步骤 1给定一

27、个初始对偶可行的基本解，设相应的基为B。2若 ，则停止计算，现行对偶可行的基本解为最优解。否则令 ，则该行所对应的变量 为换出基的变量； 3若对所有j， ，则停止计算，原问题无可行解。否则，令则 为换入基的变量；4以 为主元进行主元消去，返回2。对偶单纯形法举例标准化乘以(-1)3100Bx1x2x3x40 x3-1-1-1100 x4-2-2-3013100初始对偶单纯形表：出基进基主元 直到B0，停止。对偶单纯形法具有如下优点：1 初始解可以是原问题的非可行解；2 对变量个数多于约束条件的线性规划宜用对偶单纯形法计算，因此当变量数少于约束条件个数时，可先求其对偶规划，然后用对偶单纯形求解。

28、 用单纯形法求解对偶问题（LD）（即 最大化问题）时，其最后一行的检验数行对应原问题（LP）的一个基本解。并且在最终的单纯形表中，对偶松弛变量对应的检验数的负数就是原问题（LP）的最优解。 例3.4：用对偶单纯形法求解线性规划解：在第2个约束方程的两边同乘以-1，然后引入变量x4,x5得：用对偶单纯形法求解得最优解 ： 最优目标函数值 ：单纯形算法和对偶单纯形算法之差别 目 录线性规划的对偶问题对偶规划的基本性质对偶单纯形法影子价格和灵敏度分析影子价格和对偶价格 约束条件右侧（即资源）改变1个单位时，目标函数（即利润）的变化量，它度量了约束条件对应的那种资源的价值，经济学上称为影子价格。对偶价

29、格：约束条件的右侧值每增加一个单位导致最优解的增加量。对偶价格只适用于约束条件右侧值变化比较小的情况。当资源越来越多时，约束条件右侧的值也越来越大，其它的约束条件就有可能成为紧约束，限制目标函数值的变大。决策变量、影子价格之间的对应关系 例3.7：求下列原问题的最优解及影子价格和对偶问题的最优解及影子价格。 min z=4x1+7x2 +8x3 s.t. x1+ x2 3 x2 +2x3 1 （LP） x1+ x2 + x3 8 x10,x20,x30其对偶问题为： max w=3u1+u2 +8x3 s.t. U1 + u3 4 u1+u2 + u3 7 （LD） 2u2 + u3 8 u1

30、0,u20 ,u30求解（LP）得最优解为x*=7.5, 0, 0.5；最优值为34。 求解（LD）得最优解为u*=0，2，4；最优值为34。所以（LP）的影子价格是：0，2，4 ；（LD）的影子价格为7.5, 0, 0.5； 例3.8：A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划才能使A工厂获益最大？ 解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线性规划问题： max z=7x1 + 12x2 (总销售收入) s.t. 9x1 + 4x2 360 (煤资源限制) 4x1 + 5x2 200 (电资源限制) 3x

31、1 + 10 x2 300 (油资源限制) x1 0，x2 0 (非负条件)用单纯形法求解得：x1=20，x2=24。其对偶问题是：min w = 360y1+200y2 +300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0用单纯形法求解得：y1=0，y2 =1.36，y3=0.52。所以，煤、电、石油的影子价格分别为：0、1.36、0.52。直观上，如果在一个生产计划下，每一种资源都有所剩余，必然还可进一步通过剩余资源的组合增加生产收入(例如，将x2增加到24)。这表明该生产计划必定不是最优的生产计划。换言之，如果一

32、个生产计划是最优的，则该计划必然会耗尽某些资源。在一个最优生产计划下，被耗尽的资源对于A工厂来说就是所谓的稀缺资源。如果追加这些稀缺资源的量，则可进一步提高产量以增加生产收入。于是，提出了这样一个实际问题：如果在一个最优生产计划下，出现多种稀缺资源，那么，哪些稀缺资源最值得追加？或者说，如果A工厂始终按照最优化的计划组织生产，哪些资源对其最为紧缺？另外，根据稀缺资源对提高整个生产收入的贡献，A工厂甚至可考虑以高于市场价格的采购策略追加这些资源。这类实际问题，可通过影子价格得以解答。 影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑： 第一，是

33、否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。影子价格的经济含义 在报告列表框中选择“敏感性报告”影子价格Max z = 7x1 + 12x2 s.t. 9x1 + 4x2 360 4x1 + 5x2 200 3x1 + 10 x2 300 x1 0，x2 0Min g = 360y1 + 200y2 + 300y3 s.t. 9y1 + 4y2 + 3y3 7 4y1 + 5y2 + 10y3 12 y1 0，y2 0，y3 0根据影子价格确定某

34、种资源的追加价值。 例如：煤、电、石油的影子价格分别为0、1.36、0.52，则可确定应首先增加电资源，因为相比之下它能导致更多的生产收入。 又如：每增加1度电能使生产收入增加1.36 ，如果1度电的价格高于1.36 就不划算了；反之，如果1度电的价格低于1.36 ，则购买电资源是有利可图的。根据影子价格制定新产品的价格。 例如，A工厂要生产一种新产品，如果每单位新产品需耗用煤、电、石油分别为5、10、3单位，则新产品的价格必须大于 50+101.36+30.52 = 15.19才可能增加生产收入。如果售价低于15.19，生产该新产品是不划算的。 根据影子价格分析生产工艺的改变对资源节约所带来

35、的收益。 例如，如果A工厂经过工艺改造后使石油节约了2%，则带来的经济收益为 3002%0.52=3.12在线性规划中，我们假定模型的系数都是已知常数。而在实际中，各种条件都是动态变化的，因此这种假定很难成立。灵敏度分析将回答：最优解对线性规划模型中各种系数变化的敏感性灵敏度分析灵敏度分析目标函数系数的变化 Max Z = 40 x + 50y利润s.t.1x + 2y 40时间约束4x + 3y 120人力约束x, y 0非负约束目标函数系数在什么范围变化时，目标函数的最优解不会发生变化？ 图像表示x240403020 x1 最优解变化图像表示x240403020 x1 最优解变化 约束条件

36、右边值的变化 右侧值在什么范围变化时，目标函数的最优解不会发生变化？Max Z = 40 x + 50y利润s.t.1x + 2y 40时间约束4x + 3y 120人力约束x, y 0非负约束x240403020 x1最优解变化最优解变化 图像描述 用图解法对例2.1进行灵敏度分析 利用计算机管理软件进行灵敏度分析 当Excel已经找出了线形规划问题的最优解时，屏幕上就会出现一个“规划求解结果”的对话框（图3-3）。如果这个解就是你所要的，在“报告”一栏里选择“敏感性报告”，单击“确定”，有关灵敏度分析的报告就会保存在同一个Excel工作簿的另外一张工作表上。对于球袋公司，我们得到最优解所在

37、的工作表如图2-7和敏感性分析所在的工作表如图3-4。图 3-3图 2-7利用计算机管理软件进行灵敏度分析图 3-4此报告中将包含缩减成本、影子价格、目标系数(允许有小量增幅)以及右侧约束区域。 注：必须选择 “假定线性模型” 才能提供完整的敏感性报告接受求解结果，并将其输入可变单元格中。用Excel对例3.8的敏感性报告在不改变最优解结构的前提下，单个目标系数的可变上下限。如果其中有0出现，表明存在多个最优解。仅当资源增幅在允许的范围内，才能利用影子价格进行分析。即产品的边际收入与按影子价格折算的边际成本之差。当递减成本小于零时，表示不应该安排该产品的生产。列出目标单元格和可变单元格以及它们

38、的初始值、最终结果、有关约束条件的信息。运算结果报告列出目标单元格和可变单元及其数值、在满足约束条件和保持其它可变单元格数值不变情况下的上下限和目标值。极限值报告教学要求：第五章目标规划了解目标规划在多目标决策中的作用 掌握目标规划的建模方法和线性目标规划基本求解方法 了解目标规划在经济和管理中的基本应用方法 目标规划60年代初，查恩斯（Charnes）和库伯（Cooper）提出了一种用于求解多于一个目标的线性决策模型的方法，并提出了目标规划的概念。与线性规划的区别在线性规划中，要求单个目标的优化，而目标规划则强调使多个目标得到满意的解答 线性规划中，为得到一个可行解，必须满足所有的约束条件。

39、在目标规划中，并不认为所有约束都是绝对的，因此对于非绝对的约束，目标规划并不要求绝对满足，而是设法使各目标离原先设定的意向指标值的偏差尽可能的小。 目 录目标规划实例与模型目标规划求解方法目标规划的灵敏度分析用Excel求解目标规划的解目 录目标规划实例与模型目标规划求解方法目标规划的灵敏度分析用Excel求解目标规划的解实 例 设某公司生产两种型号的电扇，一种为普通型，装配一个需要1小时，另一种为豪华型，装配一个需要2小时。正常的装配时间每周限定为40小时。市场调查表明每周销售普通型不超过30件，豪华型不超过15件。普通型每件的净利润为8元，豪华型为每件12元。公司经理提出如下优先次序的要求

40、： 1总利润最大2装配线尽可能少加班3销售尽可能多的电扇（这同尽可能获取最大利润一致）。 4根据市场调研要求每周生产的产品数不能多于销售的数量，即普通型电扇为30件，豪华型电扇为15件。该问题的决策目标是：（1）总利润最大；（2）尽可能少加工；（3）尽可能多销售电扇；（4）生产数量不能超过预销售数量。（5）绝对目标约束。所谓绝对目标约束就是必须要严格满足的约束。绝对目标约束是最高优先级，在考虑较低优先级的目标之前它们必须首先得到满足。实 例模型建立第一优先级决策目标 正偏差：决策值超过目标值的偏差部分 负偏差：决策值小于目标值的偏差部分 指标偏离函数 约束条件决策变量建立目标规划模型的步骤 第

41、一步：定义决策变量和有关的常量 建立模型的第一步就是定义决策变量和决策目标约束等式右边的常数。等式右边的常数是可利用的资源或是决策者特定的目标值。第二步：建立决策目标约束 通过分析决策变量之间的关系以及决策变量与目标值之间的关系，建立一组目标约束。并从所有的决策目标中，找出绝对决策目标（即，如果不满足将导致最终结果无法实现的目标），将这些目标作为第一优先级。而后再确定其余目标的优先级。第三步：建立指标偏差函数目标规划的一般模型为：其中xj（ ）为决策变量；Pk（ ）为第k级优先因子； 分别为第l个目标约束的正负偏差变量的权系数，在同一等级的目标中，根据对各因子考虑的先后次序的不同，赋予不同权系

42、数。 （ ）为目标的预期目标值；bj 为系统的资源量。 这里 仅表示目标的优先等级， 后的函数表示该等级内的目标函数。在这里，我们规定 优先于 ，等等。记为：在对目标规划问题求解时，只有在尽量满足 等级内的目标函数前提下，才能考虑实现 等级内的目标。在这里 不是一个具体的数，而只表示各等级间的从属关系。所以，我们称 为优先权因子。 称为目标规划的目标函数。目 录目标规划实例与模型目标规划求解方法目标规划的灵敏度分析用Excel求解目标规划的解 再满足P4 ,使 , 极小化，由于 是 的1.5倍，先考虑先满足P1 =0, =0图解法再满足P2使 =0再满足P3使 极小化单纯形方法问题 单纯形方法

43、解决 ciP15P33P3P4P2ziVBx1x2d1 -d2-d3-d11-d1+d11+P1d1 -80111-15P3d2-70113P3d3 -4511d11 -1011-1P40-1P348553P20-1P18011-1 在选择最优列时，先从检验数栏中最优等级 行开始寻找最大正检验数。如 行内有最大正检验数，就确定它为最优列，进行迭代。直到 行内检验数没有正值为止，再转入 行寻找最大检验数。如此继续下去，直到所有检验数全部检查完毕。检验数的计算：以 列为例，此时， ， 所以， 。故在检验数栏中的 行和 行与 列的交叉点处的数分别为1和5。 目 录目标规划实例与模型目标规划求解方法目

44、标规划的灵敏度分析用Excel求解目标规划的解 目标规划的灵敏度分析 优先权因子( )的变化 1对应最优解的非基变量的 的变化:改变它们的优先等级，并不影响最优解的值,进改变他们的系数。2对应基变量的组合或基变量与非基变量组合的 的变化 ：重新写出初始单纯形表，计算最有解。目标值（ ）的变化 计算最终的单纯形表中的B-1b，看所得结果；如果所有分量都大于零，则解不变；如果存在分量小于零，则用对偶单纯形方法求新的最有解。目 录目标规划实例与模型目标规划求解方法目标规划的灵敏度分析用Excel求解目标规划的解 用Excel求解目标规划问题例5.3 将目标规划化为如下形式 建立电子表格模型如下：通过

45、规划求解，得到如下的结果121了解整数规划在经济和管理中的基本应用方法。 第六章 整数规划 教学要求：掌握线性整数规划的建模方法，特别是0-1变量的运用；掌握分支定界求解方法的基本原理；了解割平面求解方法的基本原理；122目 录整数规划实例与模型01整数规划的建模方法分支定界法割平面法指派问题应用举例和Excel求解123目 录整数规划实例与模型01整数规划的建模方法分支定界法割平面法指派问题应用举例和Excel求解124应用与实例 在现实生活中，经常遇到一些需要变量取整数才有实际意义的问题，例如制定计划、规划时需要确定工人的人数，设备的台数等。许多有名的最优化问题，如旅行商问题、背包问题、下

46、料问题、工序安排问题等，也都可以归结为整数规划问题。125应用与实例 具体实例 现有一位于城市B5的工厂，其年生产量是30000件，产品被运往A1，A2，A3三个城市的销售中心。经预测该厂产品的需求量将会增长，工厂决定将在B1，B2，B3，B4四个城市中的一个或多个城市中新建工厂以增加生产力(如有图）。综合考虑在这四个城市中新建工厂的年固定成本和生产能力，以及每件产品从每个工厂送到每个销售中心的运费。问如何选择新的厂址，才能使该工厂每年的总成本最小。B1B2B3B4B5A3A2A1126 首先做如下假设： 如果在B1建新厂，y1=1；否则，y1=0。 如果在B2建新厂，y2=1；否则，y2=0

47、。 如果在B3建新厂，y3=1；否则，y3=0。 如果在B4建新厂，y4=1；否则，y4=0。 xij：表示从工厂i 到销售中心j的运输量；i=1,5；j=1,2,3。 利用已知的数据，年运输成本为： TC1=5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32 +5x33+10 x41+4x42+2x43+8x51+4x52+3x53127TC2=175y1+300y2+375y3+500y4；总成本为：TC=TC1+TC2；生产能力的约束条件为：从新工厂B1运到A1，A2，A3三个城市销售中心的总量应小于等于B1的生产能力，所以约束条件为： x11+x12+x13

48、10y1 B1的生产能力；同理可得：x21+x22+x2320y2 B2的生产能力；x31+x32+x3330y3 B3的生产能力；x41+x42+x4340y4 B4的生产能力；x51+x52+x5330 B5的生产能力；三个销售中心的需求量为：x11+x21+x31+x41+x51=30 A1的需求量；x12+x22+x32+x42+x52=20 A2的需求量；x13+x23+x33+x43+x53=20 A3的需求量；建新工厂的年固定成本为：128所以选址模型为：min TC= TC1+TC2s.tx11+x12+x1310y1； x21+x22+x2320y2； x31+x32+x33

49、30y3； x41+x42+x4340y4； x51+x52+x5330； x11+x21+x31+x41+x51=30； x12+x22+x32+x42+x52=20； x13+x23+x33+x43+x53=20； xij0，对所有的i，j； y1，y2，y3，y4=0，1 129整数规划的一般模型130目 录整数规划实例与模型01整数规划的建模方法分支定界法割平面法指派问题应用举例和Excel求解131实例分析 某电冰箱厂正在考虑随后4年内有不同资金要求的投资方案。面对每年有限的资金，工厂领导需要选择最好的方案，使资金预算方案的当前估算净值最大化。每种方案的现金估算净值（现金估算净值为第

50、一年开始时的净现金流的值）、资金需求和4年内拥有的资金见下表：132实例分析 x1表示扩建工厂的变量，=1表示扩建工厂，0表示不扩建 同理，变量x2,x3,x4依次表示扩建仓库、更新机器、新产品研制。变 量第1年的可用资金为40千元，所以相应的约束条件为：同理得到后三年的约束条件。约束条件当前估算净值最大，即max 目标函数13301整数规划的标准型和解法必须 必须大于等于0 解法 全枚举法（不展开论述） 隐枚举法（重点讲述）标准型134隐枚举法求解步骤（一）（1）令全部都是自由变量且取0值，检验解是否可行。若可行，已得最优解；若不可行，进行步骤（2）。（2）将某一变量转为固定变量，令其取值为

51、1或0，使问题分成两个子域。令一个子域中的自由变量都取0值，加上固定变量取值，组成此子域的解。（3）计算此解的目标函数值，与已求出的可行解最小目标函数值比较。如果前者大，则不必检验其是否可行而停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝即使得到可行解，其目标函数值也较大，不会是最优解；如前者小，进行步骤（4）。对第一次算出的目标函数值，不必进行比较，直接转到步骤（4）。（4）检验解是否可行。如可行，已得一个可行解，计算并记下它的z值，并停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝，即使得到可行解，目标函数值也比记下的z值大，不会是最优解；如不可行

52、，进行步骤（5）。135隐枚举法求解步骤（二）（5）将子域固定变量的值代入第一个不等式约束条件方程，并令不等式左端的自由变量当系数为负时取值为1，系数为正时取值为0，这就是左端所能取得最小值。若此最小值大于右端值，则称此子域为不可行子域，不再往下分枝，若子域都检验过，转步骤（7），否则，转步骤（6）；若此最小值小于右端值，则依次检验下一个不等式约束方程，直至所有的不等式约束方程都通过，若子域都检验过，转步骤（7），否则，转步骤（6）。（6）定出尚未检验过的另一个子域的解，执行步骤（3）（5），若所有子域都停止分枝，计算停止，目标函数值最小的可行解就是最优解；否则，转（7）。（7）检查有无自由变

53、量。若有，转（2）；如没有，计算停止。目标函数值最小的可行解就是最优解。136隐枚举法举例(0,0,0,0,0)(0,1,0,0,0)(0,1,0,1,0)(0,1,0,0,0)(0,1,1,0,0)(0,0,0,0,0)(0,1,0,0,0)(0,0,0,0,0)(1,0,0,0,0)说明： 彩色字体为固定变量。Z1=8，可行，停止分支。Z2=0 Z1 ，不可行；可行子域，分支。Z3=2 Z1 ，不可行，可行子域，分支。Z4=0 Z1 ，不可行，不可行子域，停止分支。Z5=6 Z1 ，可行，停止分支。Z6=2 Z5 ，停止分支。Z8=20时，c(x)=3+2x。每月最多生产4个单位，每月的需

54、求是随机的，或为1或为2单位。如果生产的数量大于需求，就出现库存。每个月末检查库存，1个单位的库存费用是1元。因为库存能力有限，每月末的库存量不能超过3单位。但同时要求必须及时满足需求。在第3个月末要把现有的库存以每单位2元的价格售出。在第1月的月初，公司有1单位的库存。如何制定生产策略使三个月内的期望费用最小。 划分阶段 将三个月分为三个阶段，每个月为一个阶段 状态变量 sk表示第k个月初的库存数 决策变量 xk表示第k月生产的单位数 建立状态转移方程 ，其中 为一随机需求量或为1或为2 最优指标函数 fk(sk)表示第k个月初的库存是时，第k个月至第3个月内的最小期望费用。设备更新问题 在

55、企业中，经常遇到设备陈旧或部分损坏需要更新的问题。从经济上分析，一种设备应该使用多少年后进行更新最合算。这就是要研究的问题。一般来说，一台新设备出故障少，维护费用低，带来的经济效益就高；随着使用年限的增加，新设备逐渐变旧，维护费用增加，效用降低。在适当的时候，就要卖掉旧设备，购买新设备。当然，设备越旧越不值钱，购买新设备又需要一定数额的购买费，这就是设备的更新决策问题。 rk(t)：在第k年设备已使用过t年，再使用1年的效益 uk(t)：在第k年设备已使用过t年，再使用1年的维修费用 ck(t)：在第k年卖掉一台已使用过t年的设备，买进一台新设备的更新费用 a：折扣因子，表示一年以后的单位收入

56、价值相当于现在的a单位 fk(t)：已使用了t年的旧设备，从第k年开始在以后继续使用到规定的第n年未知几年内的总回收额设备更新问题 划分阶段 k表示计划使用该设备的年限数 状态变量 sk表示第k年初，设备已使用过的年数 决策变量 xk表示第k年初更新，还是继续使用旧设备，分别用R和K表示。 建立状态转移方程 动态规划的基本方程资源分配问题 将一种或多种有限的资源，分配给若干个使用者，而使目标达到最优设有一原料，总量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其产生的效益为ri(xi)。问如何分配，才能使生产n种产品的总收入最大？ 。 划分阶段 将n种产品按1,2,n的序号排列,每

57、种产品为一个阶段,分为n个阶段,k=1,2,n. 状态变量 sk表示分配给第k个产品至第n 种产品的资源数。 决策变量 xk表示分配给第k个产品的资源数。 建立状态转移方程 sk+1=sk-xk 最优指标函数 fk(sk)表示在拥有资源sk，分配给第k种产品至第n 种产品所得到的最大总收入。 基本方程 确定边界条件 因为在第1阶段时的资源为总资源，到第n+1阶段时资源已分配完毕，所以 so=a，sn+1=0,fn+1(sn+1)=0.复合系统可靠性问题 若某种机器的工作系统有N个部件组成，只要有一个部件失灵，整个系统就不能正常工作。这些部件的正常工作关系为串接关系，为提高系统工作的可靠性，在每

58、一个部件上均装有主要元件的备用件，并且设计了备用件自动投入装置。显然，备用元件越多，整个系统正常工作的可靠性越大。但备用元件多了，整个系统的成本、重量、体积均相应加大，工作精度也降低。因此，最优化问题是在考虑上述限制条件下，应如何选择各部件的备用元件数，使整个系统的工作可靠性最大？设部件i上装有zi个备用远见时，它正常工作的概率是pi(zi)。因此，整个系统正常工作的可靠性，可以用它的正常工作的概率来衡量。即设部件i的一个备用元件的费用为ci，重量为wi，要求整个系统所装备用元件的总费用不超过C，总重量不超过W Xk表示由第k个到第n个部件所容许使用的总费用 Yk表示由第k个到第n个部件所容许

59、使用的总重量 Xk+1=xk-zkck Yk+1=yk-zkwk 允许决策集合 动态规划基本方程复合系统可靠性问题 教学要求：第八章 马尔可夫链和马尔可夫决策过程 掌握掌握马尔可夫分析的基本原理和方法 会运用马尔可夫决策过程解决一些基本问题 了解马尔可夫决策过程的建模和求解方法 目 录马尔可夫链 n步转移概率 马尔可夫链中状态的分类 稳态概率 马尔可夫决策规划 目 录马尔可夫链 n步转移概率 马尔可夫链中状态的分类 稳态概率 马尔可夫决策规划 定义离散时间随机过程 ：假设我们观测一个系统在离散时间点上某个特性的情况，令 为此系统特性在时刻t的值。离散时间的随机过程就是关于随机变量 之间关系的描

60、述。 马尔可夫链 ：称一个离散时间随机过程为马尔可夫链，如果对于所有的 和状态，成立 称概率规则在时间上是平稳的链为平稳马尔可夫链。转移概率 ：在马尔可夫链中，对于所有的状态i和j，以及所有的时刻t，有 ，称 为马尔可夫链的转移概率。对于平稳马尔可夫链，转移概率可以用一个转移概率矩阵P表示。 例题赌徒问题 考虑一赌徒，在时刻0拥有赌金2元，在时刻 进行赌局。在每赌博中，赢一元的概率是 ，输一元的概率是 。赌徒的目标是赌金增加到4元，所以当赌金增加到4元或输光时赌博结束。 请描述此离散时间随机过程 ，并判断其是否为一个平稳马尔可夫链？若是，请写出其概率转移矩阵。解答 我们定义 为赌徒在第t场赌局