《运筹学(远程)CAI课件》由会员分享，可在线阅读，更多相关《运筹学(远程)CAI课件（47页珍藏版）》请在金锄头文库上搜索。
1、运筹学运筹学(远程远程)CAI课件课件解：解： 产销平衡问题： 总产量 = 总销量 设 xij 为从产地Ai运往销地Bj的运输量，得到下列运输量表： Min f = 6x11+ 4x12+ 6x13+ 6x21+ 5x22+ 5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x13 + x23 = 200 xij 0 ( i = 1、2；j = 1、2、3）3 3、运、运 输输 问问 题（题（3.13.1） 2系数矩阵 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0
2、 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 特点：特点： 1、共有m+n行，分别表示产地和销地；mn列分别表示各变量；2、每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用；3 3、运、运 输输 问问 题（题（3.13.1） 3设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： m n Min f = cij xij i=1 j=i n s.t. xij = si i = 1,2,m j=1 m xij = dj j = 1,2,n i=1 xij 0 (i = 1,2,m ; j = 1,2,n) 一般运输模型：一般运输模型：产销平
3、衡 A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资为从产地Ai运往销地Bj的单位运价。3 3、运、运 输输 问问 题（题（3.13.1续）续） 43 3、运、运 输输 问问 题（题（3.13.1续）续） 变化：变化： 1）有时目标函数求最大，如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； 3）产销不平衡时，可加入虚设的产地（产大于销时）或销地（销大于产时）。53 3、运、运 输输 问问 题（题（3.13.1续）续） 求解思
4、路求解思路 是 基本可行解 最优否 结束 否 换基运输问题基变量的特点运输问题基变量的特点 * 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 * 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 要弄清下列概念 ：闭回路、闭回路的顶点。63. 2 运输问题的表上作业法运输问题的表上作业法 本章重点1、初始基本可行解的确定：、初始基本可行解的确定：（1）西北角法：）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至
5、得到一个基本可行解。（2）最小元素法：）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。注：注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个0。3 3、运、运 输输 问问 题（题（3.23.2） 7*3 3、运、运 输输 问问 题（题（3.23.2） 8*3 3、运、运 输输 问问 题（题（3.23.
6、2） 92、最优性检验：、最优性检验： 因为求最小，当所有检验数均大于等于0时为最优解（1）位势法求检验数：位势：设对应基变量 xij 的 m + n - 1 个 ij ，存在 ui , vj 满足 ui + vj = cij ，i = 1, , m ; j = 1, , n . 称这些 ui , vj 为该基本可行解对应的位势。 由于有 m + n 个变量（ ui , vj ），m + n - 1 个方程（基变量个数），故有一个自由变量，位势不唯一。利用位势求检验数： ij = cij - ui - vj i = 1, , m ; j = 1, , n3 3、运、运 输输 问问 题（题（3.
7、23.2） 10前例，位势法求检验数： step 1 从任意基变量对应的 cij 开始，任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj ；从 c14 = 10 开始 step 2 计算非基变量的检验数 ij = cij - ui - vj ；填入圆圈内3 3、运、运 输输 问问 题（题（3.23.2） 113、主元变换：、主元变换：（1）选负检验数中最小者 rk，那么 xrk 为主元，作为进基变量；（上页图中 x24 ）（2）以为 xrk 起点找一条闭回路，除 xrk 外其余顶点必须为基变量格；（上页图中 蓝色回路）（3）为闭回路的每
8、一个顶点标号， xrk 为 1，沿一个方向依次给各顶点标号；（4）求=minxijxij对应闭回路上的偶数标号格= xpq那么确定xpq为出基变量，为调整量；（5）对闭回路的各奇标号顶点 xij + ，对各偶标号顶点 xij - ，特别 xpq - = 0，变为非基变量；3 3、运、运 输输 问问 题（题（3.23.2） 重复重复2、3步，直到所有检验数均非负，得到最优解。步，直到所有检验数均非负，得到最优解。12主元变换：主元变换： 由前面得到 = 1，于是3 3、运、运 输输 问问 题（题（3.23.2） ij 0，得到最优解 x13 = 5, x14 = 2, x21 = 3, x24
9、= 1, x32 = 6, x34 = 3, 其余 xij = 0 ; 最优费用：f* = 3*5+10*2+1*3+8*1+4*6+5*3 = 85*习题：p 123 习题3 3-1, 3-2133. 3 产销不平衡的运输问题产销不平衡的运输问题 1、产量大于销量、产量大于销量 例、例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解解：增加一个虚设的销地运输费用为03 3、运、运 输输 问问 题（题（3.33.3） 142、销量大于产量、销量大于产量 例、例、某公司从两个
10、产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解解：增加一个虚设的产地运输费用为03 3、运、运 输输 问问 题（题（3.33.3） 15下面给出一些例题，可作为建模的练习：下面给出一些例题，可作为建模的练习：例、例、石家庄北方研究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价如下表。由于需大于供，经院研究决定一区供应量可减少0-200吨，二区必须满足需求量，三区供应量
11、不少于1700吨，试求总费用为最低的调运方案。3 3、运、运 输输 问问 题（例题）题（例题）16解：解： 根据题意，作出产销平衡与运价表： 取 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。 3 3、运、运 输输 问问 题（例题）题（例题）17例、例、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。试求总费用为最低的化肥调拨方案。3 3、运、运 输输 问问 题（例题）题（例题）18解：解： 根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排
12、，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。3 3、运、运 输输 问问 题（例题）题（例题）19例、例、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。3 3、运、运 输输 问问 题（例题）题（例题）20解：解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满
13、足：交货：x11 = 10 生产：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第 i 季度生产的柴油机数目看作第 i 个生产厂的产量；把第 j 季度交货的柴油机数目看作第 j 个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题： 目标函数：目标函数：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22
14、+11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 3 3、运、运 输输 问问 题（例题）题（例题）21例、例、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1-6月份的生产，可使总的生产费用（包
15、括运输、仓储、维护）最少？3 3、运、运 输输 问问 题（例题）题（例题）22解：解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地各月生产与交货分别视为产地和销地 1）1-6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36； 2）上年末库存103台，只有仓储费和运输费，把它列为的0行； 3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台； 4）1-6表示1-6月份正常生产情况， 1-6表示1-6月份加班生产情况。续下页 产销平衡与运价表：3 3、运、运 输输 问问 题（例题）题（例题）23 *习题
16、：p 124 习题3 3-3，3-43 3、运、运 输输 问问 题（例题）题（例题）返回目录244. 1 动态规划概念与模型动态规划概念与模型多阶段决策过程特点要点：阶段，状态，决策，状态转移方程，k-后部子过程4 4、动、动 态态 规规 划划(4.1) (4.1) 25动态规划模型动态规划模型 n opt R( u1, , un ) = rk ( xk , uk ) k=1 s.t. xk+1 = Tk ( xk , uk ) xk Xk ；uk Uk k = 1,n ：表示对n阶段效应进行综合（常用 或 ）； opt ：最优化（ Max 或 Min） R( u1, , un )：目标函数（
17、最优值函数） xk+1 = Tk ( xk , uk ) ：状态转移方程 Xk ：状态可能集合 Uk：决策允许集合4 4、动、动 态态 规规 划划(4.1) (4.1) 26建模过程 确定阶段与阶段变量； 明确状态变量与状态可能集合； 明确决策变量与决策允许集合； 明确状态转移方程； 确定阶段效应和目标。4 4、动、动 态态 规规 划划(4.1) (4.1) 274. 2 动态规划求解动态规划求解 求解动态规划模型：求解动态规划模型： 从起始状态 x1 开始，找最优策略、最优路线和最优目标值。 最优性原理最优性原理 最优策略具有的基本性质是：无论初始状态和最优策略具有的基本性质是：无论初始状态
18、和初始决策如何，对于前面决策所确定的某一状态而初始决策如何，对于前面决策所确定的某一状态而言，余下的决策序列必构成最优策略。言，余下的决策序列必构成最优策略。 最优策略的任何一子策略也是相应初始状态的最优策略；每个最优策略只能由最优子策略构成。4 4、动、动 态态 规规 划划(4.2) (4.2) 28贝尔曼函数：（ k - 子过程的最优目标函数 ) nfk(xk) = opt ri ( xi , ui ) k=1,n i=k动态规划求解问题的一般过程： 逆序地求出条件最优目标函数值集合和条件最优决策集合： fn+1(xn+1) = 0 (边界条件) fk(xk) = opt rk ( xk
19、, uk ) + fk+1(xk+1) u k = n,14 4、动、动 态态 规规 划划(4.2) (4.2) 29 顺序地求最优决策序列：初始状态唯一：R* = f1(x1)，u1* (x1)=u1(x1)若不唯一：R* = optf1(x1) x1X1 = f1(x1*)， u1* (x1*)=u1(x1*) xk+1 = Tk ( xk , uk ) uk+1* (xk+1*) = uk+1(xk+1*) k=1,n最优策略：u1* (x1*), u2*(x2*), un* (xn*) 最优路线：x1* , x2*, , xn*, xn+1*) 4 4、动、动 态态 规规 划划(4.2
20、) (4.2) 30 1、动态规划的四大要素、一个方程 重点 状态变量及其可能集合状态变量及其可能集合 xk Xk 决策变量及其允许集合决策变量及其允许集合 uk Uk 状态转移方程状态转移方程 xk+1 = Tk ( xk , uk ) 阶段效应阶段效应 rk ( xk , uk ) 动态规划基本方程动态规划基本方程 fn+1(xn+1) = 0 (边界条件) fk(xk) = opt rk ( xk , uk ) + fk+1(xk+1) u k = n,14 4、动、动 态态 规规 划划(4.2) (4.2) 314. 3 动态规划应用举例动态规划应用举例例：一个线路网络图，从A到E要修
21、建一条石油管道，必须 在B、C、D处设立加压站。各边上的数为长度，现需要找一条路使总长度最短。4 4、动、动 态态 规规 划划(4.3) (4.3) 32解：解： 可分成4个阶段：A到B、B到C、C到D、D到E ； 每个阶段 k 的起点称为状态 S k ； 从 k 阶段的起点出发可以做一选择，即决定到下一阶段的哪个节点，称为决策 X k ； 可见， S k+1 是由 S k 和 X k 所决定的。 那麽，从A出发经过4个阶段：A到B、B到C、C到D、D到E，逐次作出决策，构成从A到E 的一条路线，记为 u 。即， u = S1 X1 S2 X2 S3 X3 S4 X4 S5 其中 S1 = A
22、 ，S5 = E 记 d 为两个相邻节点之间的长度，如 d（A，B 3）= 3 。 记 f k（S k）为从 S k 到E 的最短长度，称为从 S k 到E的距离。那么， f 1（A）是从A到E 的最短距离，即最优策略的值。4 4、动、动 态态 规规 划划(4.3(4.3续续) ) 33 最短路问题的特点：如果从 A 到E 的最优策略经过某节点，那么这个策略的从该节点到E的一段，必定是该节点到E的所有线路中 S k 最短的一条，即这一段的长度为 f k（S k）。 （1）逆序法：从E到A （2）顺序法：对节点 S k ，从 A到 S k 所有线路中，最短的一条的长度记为 k（S k），例如 1
23、（A）= 0 ，称为问题的边界条件。4 4、动、动 态态 规规 划划(4.3(4.3续续) ) 动态规划文本动态规划文本34学习方法建议：学习方法建议： 第一步 先看问题，充分理解问题的条件、情况及求解目标； 第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时，会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论；4 4、动、动 态态 规规 划划(4.3(4.3续续) ) 35第三步 动手把求解思路整理出来，或者说，把该问题作为习题独立的来做；第四步 把自己的求解放到一边，看书中的求解方法
24、，要充分理解教材中的论述；第五步 对照自己的求解，分析成败。 *习题： p175-177 4 -1，4 -2，4 -3，4 -6； *练习：4 -4，4 -5，4 -74 4、动、动 态态 规规 划划(4.3(4.3续续) ) 返回目录365. 1 图的基本概念图的基本概念 本节主要是概念 图图 G（V，E）：）： V是顶点集合（是顶点集合（vi , i=16） E是边的集合（是边的集合（ej , j=19） 顶点数顶点数 p (G) = 6 边数边数 q (G) = 9 对于边对于边 e3 = v1, v4 ，v1, v4是是 e3的端点的端点e3 是是v1, v4的关联边的关联边5 5、图
25、、图 与与 网网 络络 分分 析（析（5.15.1） 图的其他概念图的其他概念 ： 相邻点，相邻边，相邻点，相邻边， 环，多重边（平行边），环，多重边（平行边）， 多重图，简单图多重图，简单图37端点的次端点的次d(v)：点 v 作为边端点的次数；奇点：奇点：d(v)=奇数； 偶点：偶点：d(v)=偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边，孤立点：孤立点：d(v)=0；空图空图：E = ，无边图。定理一：定理一：所有顶点次数之和等于所有边数所有顶点次数之和等于所有边数的的2 2倍。倍。定理二：定理二：在任一图中，奇点的个数必为偶在任一图中，奇点的个数必为偶数。数。5
26、 5、图、图 与与 网网 络络 分分 析（析（5.15.1续）续） 38图的连通性：图的连通性：链：链：由两两相邻的点及其相关联的边构成的点边序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn ； v0 , vn分别为链的起点起点和终点终点 简单链：简单链：链中所含的边均不相同；初等链：初等链：链中所含的点均不相同，也称通路通路；回路：回路：若 v0 vn 分称该链为开链，否则称为闭链闭链或回路回路；圈：圈：出起点和终点外链中所含的点均不相同的闭链；连通图连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。5 5、图、图
27、与与 网网 络络 分分 析（析（5.15.1续）续） 39子图子图 设设 G1 = V1 , E1 , G2 = V2 , E2 子图定义：子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图；真子图：真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图；部分图：部分图：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图；导出子图：导出子图：如果 V2 V1 , E2 = vi , vj vi , vj V2 ，称 G2 是 G1 中由V2 导出的导出子图。5 5、图、图 与与 网网 络络 分分 析（析（5.15.1续）续） 40有向图：有向
28、图：关联边有方向弧：弧：有向图的边 a = ( u , v )，起点起点 u，终点终点 v；路：路：若有从 u 到 v 不考虑方向的链，且各方向一致，则称之为从 u 到 v 的路；路；初等路：初等路：各顶点都不相同的路； 初等回路：初等回路：u = v 的初等路 连通图：连通图：若不考虑方向 是无向连通图 强连通图：强连通图：任两点有路5 5、图、图 与与 网网 络络 分分 析（析（5.15.1续）续） 41树：树：无圈连通图；无圈图又称为树林，子连通图是树定理：定理：六种等价描述。 设：边数 q , 顶点数 p . 1、无圈连通图； 2、边数q = 顶点数p - 1； 3、连通，且 q =
29、p - 1； 4、无圈，但加一边则得到唯一的圈； 5、连通，但若去一边则图不连通； 6、每对顶点之间有且仅有一条链。部分树：部分树：若一个图 G 的部分图 T 是树，则称 T 为部分树，又称生成树余树：余树：G 中去掉 T 所有的边后得到的部分树称为 G 中 T 的余树，余树不一定是树。5 5、图、图 与与 网网 络络 分分 析（析（5.15.1续）续） 425 5、图、图 与与 网网 络络 分分 析（析（5.25.2）5. 2 网络最短路问题网络最短路问题 网络：网络：规定起点、中间点和终点的赋权图；有向网络：有向网络：网络中每个边都是有向边；无向网络：无向网络：网络中每个边都是无向边；混合
30、网络：混合网络：网络中既有有向边，又有无向边；网络最短路线问题：网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。 Min L() = lij 为从 v1 到 vn 的通路； lij 其中， lij为从 vi 到 vj 的一步距离。43结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法： 1、狄克斯拉方法：适用于满足所有权系数大于等于0（lij0）的网络最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离； 2、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四
31、步距离经有限次迭代可求出 vi 到 vj 的最短距离； 3、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。 *习题： p218-219 习题5 5-25 5、图、图 与与 网网 络络 分分 析（析（5.25.2续）续） 445. 3 最短树问题（最小树问题）（最短树问题（最小树问题）（ p198-201 ）依据树的特点（即无圈和连通），按照最短的要求构造求最短树的方法。结合例题学习、掌握求最小树的破圈法和生长法两个方法： 1、破圈法 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； 去掉该圈中权数最大
32、的边； 反复重复 两步，直到求出最短树。 2、生长法 从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联的权数最小的另一边。注意寻找过程中，节点不得重复，即在找最小权数边时不考虑已选过的边。反复进行，直到得到最短树或证明网络不存在最短树。 *习题： p218-219 习题5 5-1， 5-35 5、图、图 与与 网网 络络 分分 析（析（5.35.3） 455. 4 最大流问题（最大流问题（ p201-212 ）网络最大流问题 * 在一定条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题。 * 规定： 一个起点和一个终点；有向网络
33、；各弧上有权表示允许的最大流量；除起点和重点外，各节点流入量总和等于流出量总和。最大流最小割定理（在理解割集和最小割集概念的基础上掌握此定理） 最大流最小割定理：流过网络的最大流量等于最小割集的容量。结合例题学习、掌握求最大流的福德 富克逊方法 在理解算法原理的基础上，掌握算法思想及过程。通过例题掌握此方法。 *习题： p219 习题5 5-45 5、图、图 与与 网网 络络 分分 析（析（5.45.4） 465. 5 最小费用最小费用 最大流问题（最大流问题（ p212-218 ）最小费用 最大流问题 本节讨论的问题是在5.4节问题的基础上增加关于使费用最小的目标。对偶法原理 先用5.4节讨论的方法求出网络的最大流量，然后在原始的网络中用5.2.4的福德算法找出从起点 vs 到终点 vt 的最短路线最短增广链，在该增广链上找出最大调整量，并调整流量得到一个可行流，则此可行流的费用最小。如果此时流量等于最大流量，那么它就是最小费用最大流；否则应继续调整。结合例题学习、掌握求最小费用 最大流问题对偶法。 *习题： p 220 习题5 5-55 5、图、图 与与 网网 络络 分分 析（析（5.55.5） 返回目录47
