第二章最优化方法

第二章最优化方法运运筹筹学学简简述述运筹学（OperationsResearch）系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(ManagementScience)。运筹学所研究的问题，可简单地归结为一句话：“依照给定条件和目标，从众多方案中选择最佳方案”。故有人称之为最优化技术。最最优优化化最优化：指针对决策问题，按照决策的目标，从多个可能的方案中选择出最好的方案的过程。最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。运运筹筹学学的的主主要要内内容容•数学规划（线性规划、整数规划、目标规划、动态规划等）•图论•存储论•排队论•对策论•排序与统筹方法•决策分析运运筹筹学学在在工工商商管管理理中中的的应应用用运筹学在工商管理中的应用涉及几个方面：•生产计划•运输问题•人事管理•库存管理•市场营销•财务和会计另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。第一节线性规划(LinearProgramming)线线性性规规划划问问题题的的数数学学模模型型1.规划问题线线性性规规划划问问题题的的数数学学模模型型例1.1如图所示，如何截取x使铁皮所围成的容积最大？线线性性规规划划问问题题的的数数学学模模型型线线性性规规划划问问题题的的数数学学模模型型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：线线性性规规划划问问题题的的数数学学模模型型线线性性规规划划问问题题的的数数学学模模型型线线性性规规划划问问题题的的求求解解方方法法线性规划问题的求解方法图图解解法法maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0图图解解法法单单纯纯形形法法的的计计算算步步骤骤例1.9用单纯形法求解单单纯纯形形法法的的计计算算步步骤骤在在EExxcceell中中建建立立线线性性规规划划模模型型和和求求解解的的方方法法在在EExxcceell中中建建立立线线性性规规划划模模型型和和求求解解的的方方法法在在EExxcceell中中建建立立线线性性规规划划模模型型和和求求解解的的方方法法在在EExxcceell中中建建立立线线性性规规划划模模型型和和求求解解的的方方法法线线性性规规划划模模型型的的应应用用一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。线线性性规规划划在在管管理理中中的的应应用用•人力资源分配问题线线性性规规划划在在管管理理中中的的应应用用解：设xi表示第i班次时开始上班的司机和乘务人员人数。线线性性规规划划在在管管理理中中的的应应用用2.生产计划问题线线性性规规划划在在管管理理中中的的应应用用线线性性规规划划在在管管理理中中的的应应用用解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：线线性性规规划划在在管管理理中中的的应应用用目标是利润最大化，即利润的计算公式如下：线线性性规规划划在在管管理理中中的的应应用用因此该规划问题的模型为：线线性性规规划划在在管管理理中中的的应应用用线线性性规规划划在在管管理理中中的的应应用用线线性性规规划划在在管管理理中中的的应应用用3.套裁下料问题线线性性规规划划在在管管理理中中的的应应用用线线性性规规划划在在管管理理中中的的应应用用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，用一个很大的正数M表示运价C21。虚设一个销量为b5=180-160=20，Ci5=0，i=1,2,3,4，表的右边增添一列，得到新的运价表。运运输输规规划划问问题题的的数数学学模模型型下表为计算结果。可看出：产地A4还有20个单位没有运出。运运输输规规划划问问题题的的EExxcceell解解法法例：设有某种物资共有三个产地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。问如何调运才能使总运费最省？运运输输规规划划问问题题的的EExxcceell解解法法MinZ=2x11+9x12+10x13+7x14+x21+3x22+4x23+2x24+8x31+4x32+2x33+5x34x11+x12+x13+x14=9x21+x22+x23+x24=5x31+x32+x33+x34=7x11+x21+x31=3x12+x22+x32=8x13+x23+x33=4x14+x24+x34=6xij≥0（i=1,2,3；j=1,2,3,4）运运输输规规划划问问题题的的EExxcceell解解法法运运输输规规划划问问题题的的EExxcceell解解法法运运输输规规划划问问题题的的EExxcceell解解法法运运输输规规划划问问题题的的EExxcceell解解法法例：某设备厂的非平衡运输问题。某设备厂下设三个位于不同地点的分厂A、B、C，该三个分厂生产同一种设备，设每月的生产能力分别为25台、35台、45台。某设备厂有四个固定的用户，四个用户下月的设备需求量分别为20台，15台，23台，32台。设各分厂的生产成本相同，从各分厂到各用户的单位设备运输成本如下表，而且各分厂本月末的设备库存量为零。问该厂如何安排下月的生产与运输，才能在满足四个用户需求的前提下使总运输成本最低。运运输输规规划划问问题题的的EExxcceell解解法法运运输输规规划划问问题题的的EExxcceell解解法法运运输输规规划划问问题题的的EExxcceell解解法法第三节分配问题分分配配问问题题指指派派问问题题的的数数学学模模型型的的标标准准形形式式：：分分配配问问题题指派问题的数学模型为：分分配配问问题题例有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？分分配配问问题题不不平平衡衡的的指指派派问问题题分分配配问问题题一一个个人人可可做做几几件件事事的的指指派派问问题题分分配配问问题题某某事事一一定定不不能能由由某某人人做做的的指指派派问问题题分分配配问问题题解：由于任务数多于人数，所以假定一名虚拟人，设为戊。因为工作E必须完成，故设戊完成E的时间为M（M为非常大的数），其余效率系数为0，则标准型的效率矩阵表示为：分分配配问问题题的的EExxcceell解解法法分分配配问问题题的的EExxcceell解解法法第四节动态规划多多阶阶段段决决策策•在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。多多阶阶段段决决策策•各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，如图所示。多多阶阶段段决决策策多多阶阶段段决决策策各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。动动态态规规划划多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。动动态态规规划划中中的的术术语语阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段。例中，第一个阶段就是点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-1×2条路径；•计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015次，比较1.3726075472977×1014次。若用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的