第二章最优化方法

第二章优化方法运营学概要运营计划学(Operations Research )系统工程学最重要的理论基础之一，在美国有把运营学称为管理科学的人。 运营计划学研究的问题，可以简单地归纳成一句话“根据给定的条件和目标，从许多方案中选择最佳方案”。被称为优化技术。最佳化优化：针对决策问题，根据决策目标，从多个可能的方案中选择最佳方案的过程。优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的是寻求合理运用人才、物资和财力的方案，充分发挥资源使用效果，最终达到最佳目标。运营学的主要内容数学规划(线性规划、整数规划、目标规划、动态规划等)图说记忆论排队论反提案论排序和调整方法决策分析运输计划学在工商管理中的应用运营计划学在工商管理中的应用涉及几个方面生产计划运输问题人力资源管理库存管理市场营销财务和会计同时还应用于设备维护、更新与可靠性分析、项目选择与评价、工程优化设计等方面。第一节线性规划线性编程(Linear Programming )线性规划问题的数学模型1 .规划问题线性规划问题的数学模型例1.1如图所示，如何切割x，使用铁皮包围的容积达到最大？线性规划问题的数学模型线性规划问题的数学模型解：将x1、x2分别作为甲、乙两种产品的产量，数学模型如下线性规划问题的数学模型线性规划问题的数学模型线性规划问题的求解方法线性规划问题的求解方法图式法max Z=2X1 X2X1 1.9X2 3.8X1 - 1.9X2 3.8s.t. X1 1.9X2 10.2X1 - 1.9X2 -3.8X1，x20图式法单纯形法的计算步骤例1.9用简单形式法求解单纯形法的计算步骤用Excel建立和求解线性规划模型的方法用Excel建立和求解线性规划模型的方法用Excel建立和求解线性规划模型的方法用Excel建立和求解线性规划模型的方法线性规划模型的应用一般来说，如果经济和管理问题满足以下条件，可建立线性规划模型：线性规划在管理中的应用人力资源分配问题线性规划在管理中的应用解： xi表示第I班上班的司机和乘务员的人数。线性规划在管理中的应用2 .生产计划问题线性规划在管理中的应用线性规划在管理中的应用解： xijk表示产品I在工序j设备k中加工的数量。 约束条件如下：线性规划在管理中的应用目标是利润的最大化，即利润的计算公式如下线性规划在管理中的应用因此，该计划问题的模式如下：线性规划在管理中的应用线性规划在管理中的应用线性规划在管理中的应用三.裁决问题线性规划在管理中的应用线性规划在管理中的应用4 .原料问题线性规划在管理中的应用解： Xj表示Bj种食物的用量第二节运输计划运输规划问题的数学模型有的公司从两个产地A1、A2向三个销路B1、B2、B3运送货物。 各产地的产量、各销路的销售量和从各产地到各销路的货物运费如下表所示运输规划问题的数学模型解：产销平衡问题：总产量=总销售量=500将xij作为从产地Ai向销售地Bj的输送量的话，可以得到以下的输送尺度运输规划问题的数学模型运输问题的一般形式：生产销售平衡运输规划问题的数学模型生产销售不平衡的运输问题总产量和总销售量不相等的情况下，被称为不均衡运输问题。 这种运输问题实际上经常遇到，其解决方法是将不均衡问题作为平衡问题用平衡问题来解决。运输规划问题的数学模型由于总产量超过总销售量，部分产地的产量无法全部运输，必须在当地库存，也就是说必须按产地设置仓库，假设该仓库为虚拟销售地Bn 1、Bn 1，作为虚拟销售地Bn 1的销售量(库存量)。 各产地从Ai到Bn 1的运费为零，即Ci、n 1=0、(i=1、m )。 平衡问题的数学模型如下：运输规划问题的数学模型如果销售超过生产，则是：运输规划问题的数学模型运输规划问题的数学模型例：求下面列表中的极小化运输问题的最佳解运输问题的应用所以，是生产大于销的运输问题。 表中的A2不得达到B1，运价C21用大的正数m表示。 虚拟销售量为b5=180-160=20、Ci5=0、i=1、2、3、4，在表的右侧添加列，得到新的运行价目表。运输规划问题的数学模型下表列出了计算结果。 可以看出产地a-4还没有发货20单位。运输规划问题的Excel解法例：某物资具有3个产地A1、A2、A3，其产量分别为9、5、7单位，此外还有4个据点B1、B2、B3、B4，期间销售量分别为3、8、4、6单位。 众所周知，从产地ai(I=1、2、3 )到销售地bj(j=1、2、3、4 )的单位运费为Cij。 如何最大限度地节省运费总额？运输规划问题的Excel解法minz=2x11x12x13x14x21x22x224 x 232 x 248 x 31x 32 x 33 x 24x11 x12 x13 x14=9x21 x22 x23 x24=5x31x3x2x3x4=7x11 x21 x31=3x12 x22 x32=8x13 x23 x33=4x 14 x 24 x 24=6xij0 (I=1，2，3； j=1，2，3，4 )运输规划问题的Excel解法运输规划问题的Excel解法运输规划问题的Excel解法运输规划问题的Excel解法/某设备工厂的非平衡运输问题。某设备厂设有不同场所的三个厂a、b、c，这三个厂生产同样的设备，每月生产能力分别为25台、35台、45台。 某设备厂有4名固定用户，4名用户下月的设备需求量分别为20台、15台、23台、32台。 各工厂的生产成本相同，从各工厂到各用户的单位设备运输成本如下表所示，并且各工厂本月末的设备库存量为零。 问问该厂如何安排下个月的生产和运输，以满足4个用户的需要为前提可以降低总运输成本。运输规划问题的Excel解法运输规划问题的Excel解法运输规划问题的Excel解法第三节分配问题分配问题分配问题的数学模型的标准格式：分配问题分配问题的数学模型如下：分配问题例如有中文的说明书，翻译成英语、日语、德语、俄语4种文字，分别记为a、b、c、d。 现在甲、乙、丙、丁四个人，把中文说明书翻译成不同语言说明书所需的时间如下表所示，如何分配任务，使总时间最小化？分配问题不均衡的分配问题分配问题一个人可以做几件事的分配问题分配问题某事一定有人不能做的分配问题分配问题解：因为任务数比人数多，所以假定虚拟人，变成戊。 由于工作e必须完成，因此标准形式的效率矩阵由m表示，其中m为非常大的整数，并且馀数效率系数为0指定问题的Excel解法指定问题的Excel解法第四节动态规划多阶段决策在现实生活中，有活动的过程。 因此，必须将过程分为几个阶段，在各个阶段作出决定。 因此，整个过程可以达到最好的活动效果。多阶段决策每个阶段的决策选择并非任意决定，而是依赖于当前面临的状态，影响今后的发展，每个阶段的决策确定后，构成决策顺序，决定整个过程的活动路线。多阶段决策多阶段决策各阶段的决策构成决策序列，称为战略。 每个阶段都有一些决策，我们可以选择很多策略，可以对应一个策略来决定活动的效果，这个效果可以由数量来决定。 不同策略的效果不同，多阶段的决策问题是，在可选择的策略中选择最佳策略，在预定标准下达到最佳效果。动态规划在多阶段决策问题中，各阶段的决策通常与时间有关，决策依赖于当前状态，很快就会发生状态转移，一个决策序列发生在变化的状态下，因此，解决多阶段决策优化问题的方法称为动态规划方法。动态规划术语阶段：将解决给定问题的过程恰当地分为几个相互关系的阶段。 例如，第一个阶段是点A-B，第二个阶段是点B-C，第三个阶段是点C-D，第四个阶段是点D-E。动态规划术语状态：状态表示各阶段开始面对的自然或客观条件。 在本例中，状态是一个阶段的起点，它是该阶段的一个分支的起点，同时也是前一阶段的一个分支的终点。 在示例中，第一阶段具有状态a，第二阶段具有状态B1、B2和B3，第三阶段具有状态C1、C2和C3，第四阶段具有状态D1和D2。动态规划术语决策：在给定某一阶段的状态后，从该状态转移到下一阶段的某一状态的一个选择(行动)叫做决策。策略：由各阶段决策组成的序列称为策略。 对于每个实际的多阶段决策过程，可选择的策略都有一定的范围限制，这种范围称为授权策略集。最优战略：在集合中达到最优效果的战略被称为最优战略。多阶段决策过程优化问题实例下图显示了从起点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次。 用一亿次/秒的计算机计算大约需要508天。怎么办？多阶段决策过程优化问题实例动态规划是解决这类课题的一种思路。优化原理美国学者R.Bellman提出的优化原理是解决动态规划问题的基础，内容是“作为整个过程的优化策略具有这样的性质，无论过去的状态和决策如何，对于前一决策形成的状态，其馀的决策都必须构成优化策略”。 简言之，优化策略的子策略总是最优的。 一个问题满足优化原理也称为具有最佳子结构性质。优化原理作为整个过程的最优策略，对于前面的决策形成的状态，馀下的子策略必定满足构成“最优子策略”。 最优性原理实际要求问题的最优策略子策略也是最优的。例如，从a到e，最短路径是a b4- c3d1e，选择这些点配置了该示例优化策略，基于优化原理，策略的每个子策略应当是优化的。 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地铺设煤气管道。 其中需要通过两段中间站，两点之间的线的数字表示距离。 我应该选哪条路线，使总距离最短？应用动态规划：资源分配问题最短路径问题的阶段性是明显的。 在许多其他类型的决策问题中，问题的阶段性可能不明确。这样的问题的基本模型是将现有的一定数量的资源(例如资金、原材料、设备、劳动力等)分配给m个(m1 )下属企业(或者工厂、个人)。 根据各企业人员素质、生产能力、销售情况、成本和质量水平等情况的不同，各企业获得一定数量的该资源后产生的利益也不同。问题是如何合理分配这些资源，使其资源的总利润最大化。应用动态规划：资源分配问题在这样的问题中，时间阶段还不清楚，但是考虑到构建动态规划模型，可以从分配的优先顺序中人为地给出分配过程的阶段。例如，考虑要分配给企业1的数量，然后考虑要分配给企业2、3、m的数量。 显然，在每个分配阶段，存在与向企业分配的资源量有关的判定问题。应用动态规划：资源分配问题某公司计划将某高效设备5台分配给所属甲、乙、丙三个工厂。 各工厂获得该设备后可获得的利润如下表所示。 怎样分配才能使总利润达到最大？应用动态规划：资源分配问题阶段k=1、2、3表示按顺序将设备分为3个阶段分配给甲、乙、丙工厂的过程。状态SK表示在第k阶段开始时保留的可分配台数，或分配给第k工厂以后(包括第k工厂)的各工厂的设备总数。决定XK表示第k阶段分配的设备台数，或第k工厂分配的设备台数状态转移SK 1=SK -XK阶段指示符VK指示在第k阶段分配之后产生的益处最