第二章最优化方法

第二章优化方法运营研究概述操作研究(Operations Research)在美国，运营研究被称为经营科学，是系统工程最重要的理论基础之一。运筹学中研究的问题可以简单地用一句话概括。根据给定的条件和目标，从众多方案中选择最佳方案.有人称之为优化技术。优化优化：指针根据决策问题的决策目标从多个可能的方案中选择最佳方案的过程。优化方法的主要研究对象是各种人类组织的管理问题和生产管理活动，其目的是想出合理使用人力、物力、财力的方案，充分发挥资源的使用效率，最终达到最佳目标。运营研究的主要内容数学构造(线性、整数、目标、动态构造等)图论储存论排队理论对抗性论对齐和调整方法决策分析运筹学在管理学中的应用经营学中操作研究的应用包括很多方面。生产计划运输问题人事管理库存管理营销财务和会计这也适用于设备维护、更新和可靠性分析、项目选择和评估、工程优化设计等。第一部分线性规划(Linear Programming)线性规划问题的数学模型1.计划问题线性规划问题的数学模型如范例1.1插图所示，如何截取x，使铁皮封闭的体积最大化？线性规划问题的数学模型线性规划问题的数学模型解决方案：如果将x1，x2分别设置为甲，将设置为两种产品的产量，则数学模型如下：线性规划问题的数学模型线性规划问题的数学模型线性规划疑难排解线性规划疑难排解图形方式Max z=2x12X1 1.9X2 3.8X1-1.9X2 3.8S.t. X1 1.9X2 10.2X1-1.9X2 -3.8X1、X2 0图形方式单纯形法计算步骤示例1.9单纯形法单纯形法计算步骤在Excel中创建线性编程模型和解决方案在Excel中创建线性编程模型和解决方案在Excel中创建线性编程模型和解决方案在Excel中创建线性编程模型和解决方案线性规划模型的应用一般来说，线性计划模型是符合以下条件的经济管理问题：线性规划在管理中的应用人力资源分配问题线性规划在管理中的应用解决方案：第一班开始上班的司机和乘务员的数量，请由塞西先生指示。线性规划在管理中的应用2.生产计划问题线性规划在管理中的应用线性规划在管理中的应用解决方案：设置xijk以表示产品I在工序j的设备k中加工的数量。约束条件包括：线性规划在管理中的应用目标是利润最大化。也就是说，利润计算如下：线性规划在管理中的应用因此，此计划问题的模型如下：线性规划在管理中的应用线性规划在管理中的应用线性规划在管理中的应用3.切割问题集线性规划在管理中的应用线性规划在管理中的应用4.材料问题线性规划在管理中的应用解决方案：Xj表示Bj的食物使用量。第二节运输计划运输计划问题的数学模型例如，两个原产地A1、A2中的三个插针B1、B2和B3，每个原产地的生产、每个销售和从每个原产地发运到每个发货方的每个项目的运费如下表所示：如何最大限度地降低总运输成本？运输计划问题的数学模型解决方案：生产和市场营销平衡问题：总生产=总销售=500将Xij从产地Ai运送至pin Bj的运输量，取得下列运输单位标准：运输计划问题的数学模型运输问题的一般形式：产销平衡运输计划问题的数学模型销售不平衡的运输问题如果总生产不等于总销售，这就称为不平衡运输问题。这些运输问题实际上经常发生，有解决不平衡问题的方法，也有按平衡问题解决的方法。运输计划问题的数学模型由于总产量大于总销售量，部分原产地不能完全发运，目前必须有库存。也就是说，每个产地都必须有一个仓库。假设仓库是虚拟销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，在表格右侧添加行以获得新的陆运单。运输计划问题的数学模型下表是计算结果。看来原产地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=2x1 9x12 10x13 7x214 x21 3x224x23 2x24 8x331 4x322x33 5x4X11 x12 x13 x14=9X21 x22 x23 x24=5X31 x32 x33 x34=7X11 x21 x31=3X12x2x32=8X13 x23 x33=4X14 x24 x34=6Xij 0 (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解决方案第三节分配问题分配问题指定问题的数学模型的标准形式：分配问题分配问题的数学模型如下：分配问题例如，有一份汉语手册，翻译成英语、工作、德国和俄罗斯四种语言。分别用a、b、c和d表示。现在，甲、乙、丁4人问，把中文说明书翻译成其他语言所需的时间如下表所示，如何分配任务，总时间最少。分配问题不平衡分配问题分配问题一个人能做几件事的分配问题分配问题有人不能做的分配问题分配问题解决方法：假设一个虚拟人设置为e，因为任务数大于任务数。由于必须完成任务e，因此完成e的时间为M(M是一个非常大的数字)，其馀效率系数为0，则标准效率矩阵显示如下：分配问题的Excel解决方案分配问题的Excel解决方案第四节动态编程多阶段决策在现实生活中，由于其特殊性，一种活动过程，该过程可以分为相互连接的多个阶段，每个阶段都需要做出决策，因此整个过程可以达到最佳的活动结果。多阶段决策每个阶段的决策选择不是随机的，取决于当前面临的状态，影响未来的发展，确定每个阶段的决策后，将确定整个过程的一个活动路径，如图所示。多阶段决策多阶段决策每个阶段的决策构成了一个决策序列，即一个策略。每个阶段都有一些决策可供选择，因此可以选择多个策略。也就是说，这相当于确定操作效果的策略，此效果可以通过计数来确定。策略不同，效果就会不同，产生多阶段决策问题。这意味着您可以从可选择的策略中选择最佳策略，以便根据预定的标准获得最佳结果。动态编程在多个阶段的决策问题中，每个阶段所做的决策通常与时间相关，决策依赖于当前状态，立即发生状态转移，一个决策序列发生在变化的状态中，因此解决多阶段决策优化问题的这种方法具有“动态”的意义，称为动态计划方法。动态编程中的术语步骤：将给定的故障诊断过程适当地分为多个相互连接的步骤。在范例中，第一个步骤是点A-B，第二个步骤是点B-C，第三个步骤是点C-D，第四个步骤是点D-E。动态编程中的术语状态：状态指示每个步骤开始的自然状态或客观条件。例如，状态是特定阶段的出发位置，是该阶段的开始点，也是上一阶段特定分支的结束点。在范例中，第一个步骤具有名为a的状态，第二个步骤具有3个状态B1、B2及B3，第三个作业具有3个状态C1、C2及C3，第四个作业具有2个状态D1、D2。动态编程中的术语决策：给定一个阶段的状态后，从该状态演化到下一阶段的任何状态的选择(活动)称为决策。策略：每个阶段的决策组成的序列称为策略。对于每个实际多阶段决策过程，可以选择的策略都有特定的范围限制，此范围称为允许策略集。最佳策略：在集合中实现最佳效果的策略称为最佳策略。多阶段决策过程优化问题示例下图显示了起点a到终点e之间的点距离。求从a到e的最短路径。多阶段决策过程优化问题示例宫内计算量：如果从a到e的站点为k个，则除a，e外，每个工作站都有3个位置，总共有3k-12条路径。计算每个路径长度需要总计3k-12个加法和3k-12-1个比较。k值增加时，所需的添加和比较次数会快速增加。例如，当k=20时，加法比较4.277115次，1.771014次。计算1亿次/秒需要大约508天。怎么办？多阶段决策过程优化问题示例动态编程是解决这种难题的一种思维方法。优化原理美国学者R.Bellman提出的优化原则是解决动态计划问题的基础，内容是“作为整个过程的最佳战略具有这样的性质，无论过去的状态和决策形成的状态，剩下的决策必须形成最佳战略”，即优化战略的子战略总是最佳的。问题满足优化原理也称为最优子结构特性。优化原理作为整个过程的最佳策略，其馀子策略与以前决策的状态相比构成了“最佳子策略”。崔宇成的原理实际上要求问题的最佳战略的子战略也是最佳的。例如，从A到E的最短路径是A-B4-C3-D1-E，这些点的选择构成了本例中的最佳策略，根据最佳原理，此策略中的每个子策略都应该是最佳的。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，矛盾。证明j是b到c的最优路径。动态编程的基本方法从最后一步的优化开始，反向向前扩展一步。将下一步骤的优化结果导入到扩展步骤中。逐步前进，直到获得整个过程的优化结果。动态编程的基本方法示例：要铺设从a分区到d分区的燃气管道，必须经过两个步骤中间站(如图所示)，并且两点之间的连接必须显示数字以指示距离。问我应该选择哪个路线，以便总距离最短？动态编程的应用：资源分配问题最短路径问题的阶段很明显。在许多其他类型的决策问题中，问题的步骤可能不明显。此类型问题的基本模型是当前一定数量的资源(如资金、原材料、设备、劳动力等)等于m (m)？每个企业都有不同的员工质量、生产能力、销售情况、成本和质量水平，因此，获得特定数量的资源会带来很多好处。问题是如何合理分配这些资源，使这些资源发挥的总效果最大化。动态编程的应用：资源分配问题在这些问题中，随时间变化的步骤并不明显，但是在考虑建立动态计划模型时，可以根据分配顺序人为地指定分配过程中的步骤。例如，指定给企业1的数量和企业2、3.考虑中指定的数量。很明显，每个分配阶段都有分配给该企业的资源数量的决定问题。动态编程的应用：资源分配问题某公司计划将某高效设备分配给所属a、b、c 3工厂5台。每个工厂取得此设备的好处如下表所示。如何分配才能最大化总利润？动态编程的应用：资源分配问题步骤K=1，2，3表示将设备依次分成3个步骤分配给a、b和c工厂的过程。状态SK表示在步骤k开始时剩馀的可拆卸平台数，或自第k个工厂(包括第k个工厂)以来分配给每个工厂的设备总数。决策XK表示分配给步骤k的设备表数，或分配给第k个工厂的设备表数。状态转移SK 1=SK -XK阶段指标VK表示k阶段分配后的优势