一． 线性规划

1.问题背景：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.

线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题

2.求解方法：

a.单纯形法：

适用的问题：约束条件全部为≤，右边常数全部为非负，对目标函数的系数没有要求。

min z=3x1-2x2

s.t. x1+2x2≤12

2x1+ x2≤18

x1,x2≥0

求解步骤：

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+2x2

s.t. x1+2x2≥12

2x1+ x2≤18

x1,x2≥0

求解步骤：

步骤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，求解单目标问题

第二步：选择整数r>1，确定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 ) 按其重 要程度排一次序。依次求单目标规划的最优解。

2．2. 过程：无妨设其次序为 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,uj﹦wij(若不存在点 1 到点 j 的路则记 w1j=∞),p={1},T={2,3,?,n}(p 为以确定的点之集，

T 为未确定的点之集)；

②（指出永久标号）在 T 中找出一点 k 使得 uk= min {uj}。令 p:=p∪{k},T=T\{k},若 T=空集算法结束，

并令 di=ui(I=1,2,?n),否则进入(3)；

③（修改临时标号）对 T 中每一个点 j，令 uj=min{uj,uk+wij}，然后返回②。 对于无向图也可以有

最短路问题。实际上可以把赋权无向图看成赋权有向图，只需把 一条边{u,v}看成两条弧(u,v)和(v,u)，并且他们的权都等于{u,v}的权。显然，所有的权必须 非负。 。 例 6.2.1 求图 6-2-1 中点 v1 到其它各点的最短路（弧旁的数字表示距离）

七．最大流问题

问题背景：流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统中有 电流量问题等等。 最大流问题是在单位时间内安排一个运送方案， 将发点的物质沿着弧的方 向运送到收点，使总运输量最大。 求解方法：

a.标号法：

方法描述：标号法是一种图上迭代计算方法，该算法首先给出一个初始可行流，通过标号找出一 条增广链，然后调整增广链上的流量，得到更大的流量。再用标号找出一条新的增广链，再 调整直到标号过程不能进行下去为止，这时的可行流就是最大流。

方法步骤：

第一步 找出一个初始可行流 fij(0),例如所有

弧的流量 fij(0) =0

第二步 对点进行标号找出一条增广链。 （1） 起点标号（∞） （2） 选一个点 vi 已标号且另一端未标号的弧沿着某条链向收点检查 （a）如果弧是前向弧且有 fij＜cij，则 vj 标号 θ j=cij﹣fij （b）如果弧是后向弧且有 fij﹥0，则 vj 标号 θ j=fij 当收点已得到标号时， 说明已找到增广链， 依据 vi 的标号反向追踪得到一条增广链。 当收点不能得到标号时，说明不存在增广链，计算结束。

第三步 调整流量 (1) 求增广链上点的 vi 标号的最小值，得到调整量号 θ = min { θ j}

第二篇：运筹学课程学总结

《运筹学》课程的学习体会

从6月25日开始至今，学习《运筹学》已经有一个多月了。在这一个多月里，我们在熊老师的帮助下，学习了有关运筹学的基础理论、应用方法的技巧等知识，使得我更进一步的了解到运筹学的实践意义的重要性，特别是在熊老师的案例讲解中，更是体会到运筹学对我们生活的方方面面所具有的指导作用。

运筹学是经济管理类专业的核心基础课之一，他体现了“优化”的思想，学习运筹学，可以提高一个人的组织，协调和控制能力，而这些对于我现在的本职工作来说就更具有现实的指导意义。运筹学应用分析，试验，量化的方法，对经济管理系统中人财物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。运筹学涉及到建立数学模型与求解的方法问题，这能够为实际问题的概括与提炼提供很好的解决方案。在熊老师的课堂上，更是把运筹学的实际运用给我们讲授得清清楚楚，使我们对学习运筹学充满了兴趣。并在熊老师的指导下，我逐渐学会了把运筹学的方法和思想应用到我的工作和生活中，给我带来了很多意想不到的收获。

我从事的工作是市场营销专业的教学工作，并担任着多门市场营销专业课程的教学，如何上好这些课程并做好课程教学创新是令人头疼的事情？ 然而幸运的是，通过这段时间对运筹学的学习，我发现了运用运筹学帮我解决教学工作出现的问题的方法。比如说：

一、在上《市场营销案例分析》这门课时，我可以运用运筹学中“运输与指派问题”的方法来解决课堂学生的学习积极性问题，有效的调动学生的积极性，具体做法如下：

1、首先将学生按人数均等的分为4个小组，然后给出案例，让学生以小组的形式讨论案例的内容，并要求学生解决案例中出现的问题的方案。

2、其次，让学生在有限的信息和大量的不确定性的条件下，积极的运用自己的智力和情感，不断的锻炼自己面对复杂问题做出决策的能力。

3、学生通过讨论和对案例所显示的数据的分析，可以得到自己小组的结论， 1

而且甚至可以提出新的问题。

4、最后，由教师总结并与学生一起对他们的分析进行比较和验证，最后找出最优的解决方案。

在这样的课堂教学中，已经将学生完全融入到课堂主角的这个角色中，教师只是在其中扮演着一个配角的辅助作用，这是非常有意义的教学形式，而这种课堂的教学方法是属于对运筹学中“运输指派问题”的应用。在这样的课堂中运用“运输指派问题”主要是在于找出解决案例中问题的最优方案的方法，让学生分小组讨论也就是希望可以得到多种解决案例中提出的问题的解决方案，然后再在多种方案中，由教师引导学生寻找出最优方案的一个课堂管理教学模式，这样做使得整个教学课堂有了更多的师生互动性，从而使得课堂的气氛变得活跃起来，学生也会对市场营销案例分析这门课充满兴趣。

二、在上《市场营销调研》这门课时，我可以运用运筹学中“目标规划” 的方法来解决学生完成调研任务的评估结果问题。“目标规划”原来是指研究企业考虑现有的资源的条件下，在多个经营目标中去寻求满意解，即使得达到目标的总体结果离事先制定目标的差距最小。运用这一思想的指导，我的《市场营销调研》课的教学方法可以做如下的改变：

1、指导我的学生进行实践调研的时候，首先要给学生制定一个调研的目标和调研报告的标准，（这包括调研所花费的时间限制、调研的内容、调研数据要求等）这样做是为了让学生在调研的过程中遵照科学的原则充分去调动自己的积极性，并能够促使学生自觉的形成自己的调研规划设计，提高学生的动手能力。

2、当学生完成自己的调研数据的收集工作后，要指导学生进行调研数据的整理和分析，在这个过程中，有些学生也许会因为某些原因不能按照要求全部完成规定的调研任务，但是，这部分学生却使自己的动手能力得到了提高，也锻炼了自己应对出现困难问题的能力，这在某种程度上说也是可以被接受完成调研工作的任务目标的。因为对于教师的教学来说，学生学习的过程比结果更有意义。而且，学生也可以通过学习的过程锻炼自己的能力这也是可行的。

那么，在运筹学中的“目标规划”的思想告诉了我一个道理，对目标的规划 2

是必须的，但有时，我们的工作并不能完全做到实现目标的理想状态，但是，在现实生活中，当我们的工作和生活状态能够做到与目标接近，或与目标差距最小，那么我们也可以认为我们是成功的。在这要套用熊老师的一句话，“运筹学中的目标规划问题的解决是现实生活中相对意义下的满意，而不是绝对意义上的最优”。

综上所述，通过这段时间对运筹学的学习，使我获得了不少的收获，我本来是文科专业出生，而运筹学偏理科，虽然学起来有点吃力，但是我还是坚持下来了，在这要感谢运筹学熊伟老师的耐心指导。熊老师在课堂上，把运筹学与生活相结合，特别是在讲授运筹案例的时候，更是讲解得清晰而精彩，使我更深刻的体会到运筹学对我生活的重要性和指导应用的重要意义。相信在今后的生活和工作中，运筹学对我的帮助会有更多的指导和实践意义，运筹学的逻辑思想就是“从提出问题开始，然后到分析建模，最后求解方案”，这个解决问题的方式方法是科学而严密的，也是值得推广的， 我想，在今后我要把运筹学的思想贯彻到我的工作和生活当中，做一个会做事，也会学以致用的人。

以上是我学习运筹学的心得体会。

3