第二章 最优化方法.docx

1、第二章 最优化方法第二章 最优化方法运筹学简述运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”。 故有人称之为最优化技术。最优化最优化： 指针对决策问题，按照决策的目标，从多个可能的方案中选择出最好的方案的过程。 最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。运筹学的主要内容 数学规

2、划（线性规划、整数规划、目标规划、动态规划等） 图论 存储论 排队论 对策论 排序与统筹方法 决策分析运筹学在工商管理中的应用 运筹学在工商管理中的应用涉及几个方面： 生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计 另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。第一节 线性规划 (Linear Programming)线性规划问题的数学模型1. 规划问题线性规划问题的数学模型例1.1 如图所示，如何截取x使铁皮所围成的容积最大？ 线性规划问题的数学模型线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：线性规划问题的数学模

3、型线性规划问题的数学模型线性规划问题的求解方法线性规划问题的求解方法图解法max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0图解法单纯形法的计算步骤例1.9 用单纯形法求解单纯形法的计算步骤在Excel中建立线性规划模型和求解的方法在Excel中建立线性规划模型和求解的方法在Excel中建立线性规划模型和求解的方法在Excel中建立线性规划模型和求解的方法 线性规划模型的应用 一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。 线性规划在管理中

4、的应用 人力资源分配问题 线性规划在管理中的应用解：设xi表示第i班次时开始上班的司机和乘务人员人数。 线性规划在管理中的应用2. 生产计划问题 线性规划在管理中的应用 线性规划在管理中的应用解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有： 线性规划在管理中的应用目标是利润最大化，即利润的计算公式如下： 线性规划在管理中的应用因此该规划问题的模型为： 线性规划在管理中的应用 线性规划在管理中的应用 线性规划在管理中的应用3. 套裁下料问题 线性规划在管理中的应用 线性规划在管理中的应用4. 配料问题 线性规划在管理中的应用解：设Xj 表示Bj 种食物用量第二节 运输规划 运输

5、规划问题的数学模型例 某公司从两个产地A1、A2将物品运往三个销地B1, B2, B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？运输规划问题的数学模型解：产销平衡问题：总产量 = 总销量500 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表：运输规划问题的数学模型运输问题的一般形式：产销平衡运输规划问题的数学模型产销不平衡的运输问题 当总产量与总销量不相等时,称为不平衡运输问题.这类运输问题在实际中常常碰到,它的求解方法是将不平衡问题化为平衡问题再按平衡问题求解。运输规划问题的数学模型由于总产量大于总销量，必有部分

6、产地的产量不能全部运送完，必须就地库存，即每个产地设一个仓库，假设该仓库为一个虚拟销地Bn+1， bn+1作为一个虚设销地Bn+1的销量(即库存量)。各产地Ai到Bn+1的运价为零，即Ci,n+1=0,（i=1，m）。则平衡问题的数学模型为：运输规划问题的数学模型 当销大于产时，即：运输规划问题的数学模型运输规划问题的数学模型例：求下列表中极小化运输问题的最优解 运输问题的应用所以是一个产大于销的运输问题。表中A2不可达B1，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列 ，得到新的运价表。运输规划问题的数学模型下表

7、为计算结果。可看出：产地A4还有20个单位没有运出。运输规划问题的Excel解法例：设有某种物资共有三个产地A1、A2、A3，其产量分别为9、5、7个单位；另有四个销地B1、B2、B3、B4，期销量分别为3、8、4、6个单位。已知由产地Ai（i=1,2,3）运往销地Bj（j=1,2,3,4）的单位运价为Cij。问如何调运才能使总运费最省？运输规划问题的Excel解法 MinZ=2x11+9 x12+10 x13+7x14+x21+3 x22 +4x23+2x24+8x31+4x32+2x33+5 x34 x11+x12+x13+x14=9 x21+x22+x23+x24=5 x31+x32+x

8、33+x34=7 x11+x21+x31=3 x12+x22+x32=8 x13+x23+x33=4 x14+x24+x34=6 xij0（i=1,2,3；j=1,2,3,4）运输规划问题的Excel解法运输规划问题的Excel解法运输规划问题的Excel解法运输规划问题的Excel解法例：某设备厂的非平衡运输问题。某设备厂下设三个位于不同地点的分厂A、B、C，该三个分厂生产同一种设备，设每月的生产能力分别为25台、35台、45台。某设备厂有四个固定的用户，四个用户下月的设备需求量分别为20台，15台，23台，32台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表，而且各分厂

9、本月末的设备库存量为零。问该厂如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。运输规划问题的Excel解法运输规划问题的Excel解法运输规划问题的Excel解法第三节 分配问题 分配问题指派问题的数学模型的标准形式：分配问题指派问题的数学模型为：分配问题例 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？分配问题不平衡的指派问题分配问题 一个人可做几件事的指派问题分配问题某事一定不能由某人做的指派问题分配问题 解：由于任务数多于人数

10、，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为：分配问题的Excel解法分配问题的Excel解法第四节 动态规划 多阶段决策 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。多阶段决策 各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示。多阶段决策多阶段决策各个阶段的决策构成一个决策序列，称为一个策

11、略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。动态规划多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。动态规划中的术语 阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段。例中，第一个阶段就是点A-B，而第二个阶段就是点B-

12、C，第三个阶段是点C-D，而第四个阶段是点D-E。动态规划中的术语 状态：状态表示每个阶段开始面临的自然状况或客观条件。例子中状态就是某阶段的出发位置，它既是该阶段某支路的起点，同时又是前一阶段某支路的终点。例中，第一个阶段有一个状态即A，而第二个阶段有三个状态B1，B2和B3，第三个阶段是三个状态C1，C2和C3，第四个阶段是两个状态D1，D2。动态规划中的术语 决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。 最优策略：

13、集合中达到最优效果的策略称为最优策略。多阶段决策过程最优化问题举例下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。多阶段决策过程最优化问题举例用穷举法的计算量: 如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-12条路径； 计算各路径长度总共要进行 (k+1) 3k-12次加法以及3k-12-1次比较。随着 k 的值增加时，需要进行的加法和比较的次数将迅速增加；例如当 k=20时，加法次数为 4.271015次，比较 1.771014 次。若用1亿次/秒的计算机计算需要约508天。 怎么办？多阶段决策过程最优化问题举例动态规划是解决类似这种难题的一种思考方法。最优

14、化原理 美国学者R.Bellman提出的最优化原理是解决动态规划问题的基础，内容是“作为整个过程的最优策略具有这样的性质，无论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优化原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。最优性原理实际上是要求问题的最优策略的子策略也是最优。比如：从A到E，最短路径是A-B4-C3-D1-E，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优的。

15、B4-C3-D1-E是B4-E的最短路径，出C3-D1-E也是C3-E的最短路径 最优化原理 例如，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。 这可用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。动态规划的基本方法 由最后一个阶段的优化开始，按逆向顺序逐步向前一阶段扩展； 并将后一阶段的优化结果带到扩展后的阶段中去； 以此逐步向前推进，直到得到全过程的优化结果。动态规划的基本方法例：从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。

16、问应该选择什么路线，使总距离最短？ 动态规划的应用：资源分配问题 最短路径问题的阶段性很明显。而在很多其他类型的决策问题中，问题的阶段性可能并不明显。 这一类问题的基本模式是，现有一定数量的资源（如资金、原材料、设备、劳力等等）要分配给m个（m1）下属企业（或工厂、个人）。由于各企业的人员素质、生产能力、销售情况、成本与质量水平等情况的不同，各企业获得一定数量的该资源后，产生的效益不同。问题是，如何合理地分配这些资源，使该资源发挥的总效益最大。动态规划的应用：资源分配问题 在这类问题中，按时间的阶段并不明显，但在考虑建立动态规划模型时，可以从分配的先后次序上来人为地赋予分配过程的阶段性。 如：

17、先考虑分配给企业1的数量，再考虑分配给企业2,3，m的数量。很显然在每一个分配阶段都有一个分配给该企业多少资源的决策问题。动态规划的应用：资源分配问题某公司拟将某种高效设备5台分配给所属甲、乙、丙三厂。各厂获此设备后可产生的效益如下表。问应如何分配，可使产生的总效益最大？动态规划的应用：资源分配问题阶段k =1,2,3依次表示把设备按顺序分为三个阶段分配给甲、乙、丙厂的过程。状态SK 表示在第k阶段初还剩有的可分台数,或者说，是分配给第K个工厂以后（含第K个工厂）的各工厂的设备总数；决策XK 表示第k阶段分配的设备台数，或分配给第K个工厂的设备台数；状态转移 SK+1 = SK XK阶段指标V

18、K表示第K阶段分配后产生的效益；最优指标函数fK 表示是从第K阶段开始到最后阶段为止的最大利润，指标函数递推关系式：动态规划的应用：资源分配问题动态规划的应用：资源分配问题动态规划的应用：资源分配问题例：某厂计划在一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。第五节 目标规划 目标规划概述 目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。（一）目标规划与线性规划的比较1、线性规划只讨论一个线性目标函数在一组线性

19、约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。2、线性规划求最优解；目标规划是找到一个满意解。目标规划概述3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。 1961年，查恩斯（A.Charnes）和库柏（W.W.Cooper）提出目标规划。目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。目标规划概述（二）目标规划的基本概念1、目标值和偏差变量目标规划通

20、过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj 选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为 d 。正偏差变量：表示实现值超过目标值的部分，记为 d。负偏差变量：表示实现值未达到目标值的部分，记为 d。目标规划概述目标规划概述目标规划概述3、达成函数（即目标规划中的目标函数）达成函数是一个使总偏差量为最小的目标函数，记为 minZ = f（d、d）。 一般说来，有以下三种情况，但只能出现其中之一： .要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ = f（d d）。 .要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ = f（d）。 .要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ = f（d）。 对于由绝对约束转化而来的目标函数，也照上述处理即可。目标规划概述4、优先因子（优先等级）与优先权系数5、满意解（具有层次意义的解）目标规划概述目标规划概述目标规划的数学模型目标规划的数学模型目标规划的数学模型目标规划的数学模型目标规划的图解法目标规划的图解法