运筹学方法总结.doc

一 线性规划1.问题背景：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题2.求解方法： a.单纯形法：适用的问题：约束条件全部为，右边常数全部为非负，对目标函数的系数没有要求。min z=3x1-2x2s.t. x1+2x212 2x1+ x218 x1,x20求解步骤：STEP 0 将线性规划问题标准化STEP 1 是否有明显的初始基础可行解，如果有，转STEP 3，否则，转STEP 2。STEP 2 构造辅助问题，用两阶段法求解辅助问题。如果辅助问题最优解的目标函数值大于0，原问题无可行解，算法终止。否则转STEP 3。STEP 3 写出单纯形表，将基变量在约束条件中的系数消为单位矩阵，将基变量在目标函数中的系数消为0。转STEP 4。STEP 4 如果所有非基变量的检验数全为负数或0，则已获得最优解，算法终止。否则， 选择检验数为正数并且绝对值最大的非基变量为进基变量。转STEP 5。STEP 5 如果进基变量在约束条件中的系数全为负数或0，目标函数无界，算法终止。否则根据右边常数和正的系数的最小比值，确定离基变量。转STEP 6。STEP 6 进基变量列和离基变量行交叉的元素称为主元。对单纯形表进行行变换，将主元变为1，将主元所在列的其他元素变为0。转STEP 4。b.对偶单纯形法：适用的问题:约束条件中至少有一个是，相应的右边常数为非负，目标函数系数全部为非负。min z=3x1+2x2s.t. x1+2x212 2x1+ x218 x1,x20求解步骤：步骤1 确定原问题（L）的初始基B，使所有检验数 ，即是对偶可行解，建立初始单纯形表。步骤2 检查基变量的取值，若0，则已得最优解，计算停；否则求确定单纯形表第L行对应的基变量为旋出变量。 步骤3 若所有,则原问题无可行解，计算停；否则，计算确定对应的为旋入变量。 步骤4 以为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。可以证明，按上述方法进行迭代，所得解始终是对偶可行解。二 运输问题1.问题背景：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。2.求解方法:a. 表上作业法:方法描述：表上作业法是一种求解运输问题的特殊的方法，其实质是单纯形法，它针对运输问题变量多,结构独特的情况，大大简化了计算过程的求解方法求解步骤：1 找出初始基本可行解2. 求各非基变量的检验数，即在表上计算除了上述的m+n-1个数字格以外的空格的检验数判别是否达到最优解,如已是最优解，则停止计算,否则转到下一步。在运输问题中都存在最优解。3. 确定入基变量与出基变量，找出新的基本可行解。在表上用闭回路法调整。4. 重复2、3直至得到最优解。三 目标规划1. 问题背景：目标规划（Goal programming） 目标规划是线性规划的一种特殊应用，能够处理单个主目标与多个目标并存，以及多个主目标与多个次目标并存的问题。2. 求解方法：a. 约束法：方法描述：在多个目标函数中选择一个主要目标作为 基本思想： 基本思想 目标函数，其它目标处理为适当的约束。 目标函数，其它目标处理为适当的约束。求解步骤：min f1 ( x) ( P)s.t. g i ( x) 0, i = 1,2, L, m f j ( x) f j ( x ( 0 ) ), j = 2,3, L, p 第一步： （1）对 j = 1,2, L, p，min f j ( x) (VPj ) s.t. x S，求解单目标问题第二步：选择整数r1，确定0 jt，f j0的r个不同阀值第三步：对 t = 0,1,L, r 1 ，分别求解问题：min f k ( x) ( Pt j )s.t. g i ( x) 0, i = 1,2, L, m f j ( x) f jt j 0, j = 1, L, k 1, k + 1,L, p ) 各目标函数 f ( j k ) 可对应不同的 t (t = 0,1,L, r 1（共 有 r p 1 个约束问题）。求解后可得到(VP)的一有 效解集合，是(VP)有效解集合的一个子集。为主目标。b. 分层序列法：求解步骤：1. 把(VP)中的p个目标 f ( x ), L , f ( x ) 按其重 要程度排一次序。依次求单目标规划的最优解。 22. 过程：无妨设其次序为 f1 , f 2 , L , f p 先求解 四整数规划问题背景：规划中的变量（部分或全部）限制为整 数时，称为整数规划。若在线性规划模 型中，变量限制为整数，则称为整数线 性规划求解方法：a.割平面法：方法描述：通过增加新的约束来切割可原问题伴随规划的可行域，使它在不断缩小的过程中，将原问题的整数最优解逐渐暴露且趋于可行域极点的位置，这样就有可能用单纯形法求出。求解步骤：第一步：用单纯形法解松弛问题，得到最优单纯形表。第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。b.匈牙利法：方法描述：在现实生活中，有各种性质的指派问题(assignment problem)。指派问题也是整数规划的一类重要问题。例如：有n项工作需要分配给n个人(或部门)来完成；有n项合同需要选择n个投标者来承包；有n个班级需要安排在各教室上课等。诸如此类问题，它们的基本要求是在满足特定的指派要求条件下，使指派方案的总体效果最佳。求解步骤：第一步：变换效率矩阵，使指派问题的系数矩阵经过变换，在各行各列中都出现0元素。具体作法是：先将效率矩阵的各行减去该行的最小非0元素，再从所得系数矩阵中减去该列的最小非0元素。这样得到的新矩阵中，每行每列都必然出现零元素。 第二步：用圈0法求出矩阵C1中的独立零元素。经第一步变换后，系数矩阵中每行每列都已有了独立零元素；但需要找出n个独立的0元素。若能找出，就以这些独立0元素对应的决策变量矩阵中的元素为1，其余为0，就得到了最优解。当n较小时，可用观察法、试探法去找出n个独立0元素；若n较大时，就必须按照一定的步骤去找，常用的步骤为：(1) 从只有一个0元素的行(或列)开始，给这个0元素加圈，记作。这表示对这行所代表的人，只有一种任务可指派，然后划去所在列(行)的其他元素，记作，这表示这列所代表的任务已指派完，不必再考虑别人了。(2) 给只有一个0元素列(行的) 0元素加圈，记作。然后划去所在行(列)的其他元素，记作。(3) 反复进行(1),(2)两步，直到每一列都没有未被标记的0元素或至少有两个未被标记的0元素时止。第三步：进行试指派若情况(1)出现，则可进行指派：令圈0位置的决策变量取值为1，其它决策变量的取值均为0，得到一个最优指派方案，停止计算。本例中得到C2后，出现了情况(1)，可令x14=x22=x31=x43=1,其余xij=0。即为最佳指派方案。若情况(2)出现，则再对每行，每列中有两个未被标记过的0元素任选一个，加上标记，即圈上该0元素。然后给同行、同列的其他未被标记的0元素加标记“”。然后再进行行、列检验，可能出现(1)或(3)。若出现(3)，则要转入下一步。 第四步：作最少直线覆盖当前所有的0元素（以例题说明）五动态规划问题背景：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。求解方法：a.分支定界法：方法描述：对有约束条件的最优化问题（其可行解为有限数）的可行解空 间恰当地进行系统搜索，这就是分枝与定界内容。通常，把全 部可行解空间反复地分割为越来越小的子集，称为分枝；并且 对每个子集内的解集计算一个目标下界（对于最小值问题）， 这称为定界。在每次分枝后，凡是界限不优于已知可行解集目 标值的那些子集不再进一步分枝，这样，许多子集可不予考虑， 这称剪枝。这就是分枝定界法的主要思路。 分枝定界法可用于解纯整数或混合的整数规划问题。在二 十世纪六十年代初由Land Doig和Dakin等人提出。由于这方 法灵活且便于用计算机求解，所以现在它已是解整数规划的 重要方法。目前已成功地应用于求解生产进度问题、旅行推 销员问题、工厂选址问题、背包问题及分配问题等。求解步骤：（i）先不考虑整数限制，即解相应的线性规划（ii）记作 z, 即 0 z * 356. （ii）因为 x1 , x2 当前均为非整数，故不满足整数要求， 任选一个进行分枝。设选 x1 进行分枝，把可行集分成 2个子集（iii）对问题B1再进行分枝得问题B11和B12（iv）对问题B2再进行分枝得问题 B21和B22,它们的最优解为（v） 将 B22 无可行解。 B21 , B22 剪枝。 于是可以断定原问题的最优解六最短路径问题背景：最短路问题就是在一个网络图中，给定一个起点，要求其到另一顶点的权数最小的距 离。最短路问题在实际生活中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设 备更新、投资等问题也都可以归结为求最短路问题。a. 最短路的矩阵算法：方法描述：最短路的矩阵算法（适用于所有权非负的情况） 最短路的矩阵算法是将图表示成是矩阵形式， 然后利用矩阵表计算出最短路。 矩阵算法 的原理与 Dijkstra 算法标号算法完全相同，只是它采用了矩阵形式，显得更为简洁，有利于 计算机计算。下面先介绍图的矩阵表示。 （1） 图的矩阵表示 无权图矩阵表示：两顶点之间有边相连的记为“1” ，无边相连的记为“0” ，对角线上 记为“0” 。所得到的矩阵一定是对阵矩阵。 赋权无向图矩阵表示：两顶点之间有边相连的，写上它们的权数，无边相连的记为 “” ，对角线上记为 0。所得到的矩阵也一定是对阵矩阵。方法步骤：第一步： 在已标号的第一行中找最小的元素 a13=1,将其圈起来， 将其所在的第三列划去， 给第三行标号第二步:类似的第二步，第三步，第四步均可由算法的步骤得矩阵 B、C、D。由于终点 v4 已 得到标号 5，故知 v1 到 v4 的最短路是 5。第三步:下面再找出 v1 到 v4 的最短路走法。用逆推的方法。第四步：若迭代到某一步 k 时，有 d(k)(j)=d(k-1)(j) 则运算结束，且 d(j)=d(k)(j) (j=1,2,3,n)中 v1 到其它各点的最短路b. Dijkstra算法（适用于所有权非负的情况）方法描述： Dijkstra 算法 Dijkstra 算法是 E.W. Dijkstra 于 1959 年提出的， 是目前公认的对所有权非负的情况的最 好算法。它给出从指定顶点到图中每个顶点的最短路。方法步骤：令 u1=0,ujwij(若不存在点 1 到点 j 的路则记 w1j=),p=1,T=2,3,n(p 为以确定的点之集，T 为未确定的点之集)；（指出永久标号）在 T 中找出一点 k 使得 uk= min uj。令 p:=pk,T=Tk,若 T=空集算法结束，并令 di=ui(I=1,2,n),否则进入(3)； （修改临时标号）对 T 中每一个点 j，令 uj=minuj,uk+wij，然后返回。 对于无向图也可以有最短路问题。实际上可以把赋权无向图看成赋权有向图，只需把 一条边u,v看成两条弧(u,v)和(v,u)，并且他们的权都等于u,v的权。显然，所有的权必须 非负。 。 例 6.2.1 求图 6-2-1 中点 v1 到其它各点的最短路（弧旁的数字表示距离）七最大流问题问题背景：流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有 电流量问题等等。 最大流问题是在单位时间内安排一个运送方案， 将发点的物质沿着弧的方 向运送到收点，使总运输量最大。求解方法：a.标号法：方法描述：标号法是一种图上迭代计算方法，该算法首先给出一个初始可行流，通过标号找出一 条增广链，然后调整增广链上的流量，得到更大的流量。再用标号找出一条新的增广链，再 调整直到标号过程不能进行下去为止，这时的可行流就是最大流。 方法步骤：第一步 找出一个初始可行