第二章-最优化方法

《第二章-最优化方法》由会员分享，可在线阅读，更多相关《第二章-最优化方法（12页珍藏版）》请在金锄头文库上搜索。

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

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

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

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、考方法。最优化原理u 美国学者R.Bellman提出的最优化原理是解决动态规划问题的基础，内容是“作为整个过程的最优策略具有这样的性质，无论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优化原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。最优性原理实际上是要求问题的最优策略的子策略也是最优。比如：从A到E，最短路径是A-B4-C3-D1-E，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优的。B4-C3-D1-E是B4-E的最短路径，出C3-D1-E也是C3-E的最短路径 最优化原理u 例如，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。u 这可用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。动态规划的基本方