运筹学方法总结

《运筹学方法总结》由会员分享，可在线阅读，更多相关《运筹学方法总结（4页珍藏版）》请在金锄头文库上搜索。

1、线性规划1. 问题背景：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支它是辅助人 们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不 可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备 和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好一般地，求线性目标 函数在线性约束条件下的最大值或最小值的问题2. 求解方法：a单纯形法：适用的问题：约束条件全部为W，右边常数全部为非负，对目标函数的系数没有

2、要求。min z=3x1-2x2s.t. x1+2x2122x1+ x20求解步骤：STEP 0将线性规划问题标准化STEP 1是否有明显的初始基础可行解，如果有，转STEP 3，否则，转STEP 2。STEP 2构造辅助问题，用两阶段法求解辅助问题。如果辅助问题最优解的目标函数值大于0，原问题无可行解，算法终止。否则转STEP 3OSTEP 3写出单纯形表，将基变量在约束条件中的系数消为单位矩阵，将基变量在目标函数 中的系数消为0。转STEP 4OSTEP 4如果所有非基变量的检验数全为负数或0,则已获得最优解，算法终止。否则，选 择检验数为正数并且绝对值最大的非基变量为进基变量。转STEP

3、 5。STEP 5如果进基变量在约束条件中的系数全为负数或0，目标函数无界，算法终止。否则 根据右边常数和正的系数的最小比值，确定离基变量。转STEP 6。STEP 6进基变量列和离基变量行交叉的元素称为主元。对单纯形表进行行变换，将主元变 为1，将主元所在列的其他元素变为0。转STEP 4。b.对偶单纯形法：适用的问题:约束条件中至少有一个是N，相应的右边常数为非负，目标函数系数全部为非负。min z=3x1+2x2s.t. x1+2x2122x1+ x20求解步骤：步骤1确定原问题（L）的初始基B，使所有检验数，即是对偶可行解，建立初始单纯形表。步骤2检查基变量的取值，若N0,则已得最优解

4、，计算停；否则求确定单纯形表第L行对 应的基变量为旋出变量。步骤3若所有，则原问题无可行解，计算停；否则，计算确定对应的为旋入变量。步骤4以为主元作（L，K）旋转变换，得新的单纯形表，转步骤2。可以证明，按上述方法 进行迭代，所得解始终是对偶可行解。二运输问题1.问题背景：一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产 地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使 得总的运输费用最小的方案。2.求解方法：a.表上作业法：方法描述：表上作业法是一种求解运输问题的特殊的方法，其实质是单纯形法，它针对运输问题变量多结构独特的情况，大大简

5、化了计算过程的求解方法求解步骤：1. 找出初始基本可行解2. 求各非基变量的检验数，即在表上计算除了上述的m+n-1个数字格以外的空格的检验数判别是否 达到最优解,如已是最优解，则停止计算，否则转到下一步。在运输问题中都存在最优解。3. 确定入基变量与出基变量，找出新的基本可行解。在表上用闭回路法调整。4. 重复2、3直至得到最优解。三-目标规划1. 问题背景：目标规划(Goal programming)目标规划是线性规划的一种特殊应用，能够处理单个主目标与多 个目标并存，以及多个主目标与多个次目标并存的问题。2. 求解方法：a. 约束法：方法描述：在多个目标函数中选择一个主要目标作为基本思想

6、：基本思想目标函数，其它目标处理为 适当的约束。目标函数，其它目标处理为适当的约束。求解步骤：min fl ( x) ( P) s.t. g i ( x) N 0, i = 1,2, L, m f j ( x) W f j ( x ( 0 ) ), j = 2,3, L, p第一步：(1)对 j = 1,2, L, p，min f j ( x) (VPj ) s.t. x E S，求解单目标问题第二步：选择整数r1，确定0 jt，f j0的r个不同阀值第三步：对t = 0,1,L, r -1，分别求解问题：min f k ( x) ( Pt j ) s.t. g i ( x) N 0, i =

7、 1,2, L, m f j ( x) - f jt j W 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 )按其重要程度排一次序。依次求单目标规划的最优解。2. 2.过程：无妨设其次序为f1 , f 2 , L , f p先求解四. 整数规划问题背景：规划中的变量(部分或全部)限制为整数时，称为整

8、数规划。若在线性规划模型中，变量限制为 整数，则称为整数线性规划求解方法：a. 割平面法：方法描述：通过增加新的约束来切割可原问题伴随规划的可行域，使它在不断缩小的过程中，将原 问题的整数最优解逐渐暴露且趋于可行域极点的位置，这样就有可能用单纯形法求出。求解步骤：第一步：用单纯形法解松弛问题，得到最优单纯形表。第二步：求一个割平面方程，加到最优单纯形表中，用对偶单纯形法继续求解。第三步：若没有得到整数最优解，则继续作割平面方程，转第二步。b. 匈牙利法：方法描述：在现实生活中，有各种性质的指派问题(assignment problem)。指派问题也是整数规划的 一类重要问题。例如：有n项工作需

9、要分配给n个人(或部门)来完成；有n项合同需要选择n个投标 者来承包；有n个班级需要安排在各教室上课等。诸如此类问题，它们的基本要求是在满足特定的指 派要求条件下，使指派方案的总体效果最佳。求解步骤：第一步：变换效率矩阵，使指派问题的系数矩阵经过变换，在各行各列中都出现0元素。具体作法是：先将效率矩阵的各行减去该行的最小非0元素，再从所得系数矩阵中减去该列的最小 非0元素。这样得到的新矩阵中，每行每列都必然出现零元素。第二步：用圈0法求出矩阵C1中的独立零元素。经第一步变换后，系数矩阵中每行每列都已有了独立零元素；但需要找出n个独立的0元素。若能 找出，就以这些独立0元素对应的决策变量矩阵中的

10、元素为1，其余为0，就得到了最优解。当n较小时，可用观察法、试探法去找出n个独立0元素；若n较大时，就必须按照一定的步骤去 找，常用的步骤为：(1) 从只有一个0元素的行(或列)开始，给这个0元素加圈，记作。这表示对这行所代表的人， 只有一种任务可指派，然后划去所在列(行)的其他元素，记作由，这表示这列所代表的任务已指派 完，不必再考虑别人了。(2) 给只有一个0元素列(行的)0元素加圈，记作.然后划去所在行(列)的其他元素，记作由。(3) 反复进行(1),(2)两步，直到每一列都没有未被标记的0元素或至少有两个未被标记的0元素时 止。第三步：进行试指派若情况(1)出现，则可进行指派：令圈0位

11、置的决策变量取值为1，其它决策变量的取值均为0，得到 一个最优指派方案，停止计算。本例中得到C2后，出现了情况(1)，可令x14=x22=x31=x43=1，其余xij=0。即为最佳指派方案。若情况(2)出现，则再对每行，每列中有两个未被标记过的0元素任选一个，加上标记，即圈上该0 元素。然后给同行、同列的其他未被标记的0元素加标记“X”。然后再进行行、列检验，可能出现(1) 或(3)。若出现(3)，则要转入下一步。第四步：作最少直线覆盖当前所有的0元素(以例题说明)五. 动态规划问题背景：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如 最短路线、库存管

12、理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。求解方法：a分支定界法：方法描述：对有约束条件的最优化问题(其可行解为有限数)的可行解空间恰当地进行系统搜索，这就 是分枝与定界内容。通常，把全 部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个 子集内的解集计算一个目标下界(对于最小值问题)，这称为定界。在每次分枝后，凡是界限不优于已 知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝 定界法的主要思路。分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig和Dakin等人提出。由

13、于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方 法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。求解步骤：(i) 先不考虑整数限制，即解相应的线性规划(ii) 记作z,即0 W z * W 356. (ii)因为x1 , x2当前均为非整数，故不满足整数要求，任选一个 进行分枝。设选x1进行分枝，把可行集分成2个子集(iii) 对问题B1再进行分枝得问题B11和B12(iv) 对问题B2再进行分枝得问题B21和B22,它们的最优解为(v) 将B22无可行解。B21 , B22剪枝。于是可以断定原问题的最优解六. 最短路径问题背景：最

14、短路问题就是在一个网络图中，给定一个起点，要求其到另一顶点的权数最小的距离。最短路问题 在实际生活中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也都可以归结为求最 短路问题。a.最短路的矩阵算法：方法描述：最短路的矩阵算法(适用于所有权非负的情况)最短路的矩阵算法是将图表示成是矩阵形式，然 后利用矩阵表计算出最短路。矩阵算法的原理与Dijkstra算法标号算法完全相同，只是它采用了矩阵形式， 显得更为简洁，有利于计算机计算。下面先介绍图的矩阵表示。(1)图的矩阵表示无权图矩阵表示：两 顶点之间有边相连的记为“1” ，无边相连的记为“0” ，对角线上记为“0” 。所得

15、到的矩阵一定是对阵 矩阵。赋权无向图矩阵表示：两顶点之间有边相连的，写上它们的权数，无边相连的记为“8” ，对角线上记为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,uj= wij(若不存在点1到点j的路则记w1j=8),p=1,T=2,3,n(p为以确定的点之集， T为未确定的点之集)； (指出永久标号)在T中找出一点k使得uk= min uj。令p:=p U k,T=Tk若丁=空集算法结束，