运筹学远程CAI课件

1、1,3. 1 运输问题模型与性质 运输模型 例、1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？,3、运 输 问 题（3.1）,2,解： 产销平衡问题： 总产量 = 总销量 设 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 + x2

2、3 = 200 xij 0 ( i = 1、2；j = 1、2、3）,3、运 输 问 题（3.1）,3,系数矩阵 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 特点： 1、共有m+n行，分别表示产地和销地；mn列分别表示各变量； 2、每列只有两个 1，其余为 0，分别表示只有一个产地和一个销地被使用；,3、运 输 问 题（3.1）,4,设 xij 为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型： m n Min f = cij xij i=1 j=i n s.t. xij = si i = 1,2,m j

3、=1 m xij = dj j = 1,2,n i=1 xij 0 (i = 1,2,m ; j = 1,2,n),一般运输模型：产销平衡 A1、 A2、 Am 表示某物资的m个产地； B1、B2、Bn 表示某物质的n个销地；si 表示产地Ai的产量； dj 表示销地Bj 的销量； cij 表示把物资为从产地Ai运往销地Bj的单位运价。,3、运 输 问 题（3.1续）,5,3、运 输 问 题（3.1续）,变化： 1）有时目标函数求最大，如求利润最大或营业额最大等； 2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束； 3）产销不平衡时，可加入虚设的产地（产大于销时）或销地

4、（销大于产时）。,6,3、运 输 问 题（3.1续）,求解思路 是 基本可行解 最优否 结束 否 换基 运输问题基变量的特点 * 运输问题的基变量共有 m + n -1 个，A的秩为 m + n -1。 * 运输问题的 m + n -1 个变量构成基变量的充分必要条件是不含闭回路。 要弄清下列概念 ：闭回路、闭回路的顶点。,7,3. 2 运输问题的表上作业法 本章重点 1、初始基本可行解的确定： （1）西北角法：从西北角（左上角）格开始，在格内的右下角标上允许取得的最大数。然后按行（列）标下一格的数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可

5、行解。 （2）最小元素法：从运价最小的格开始，在格内的右下角标上允许取得的最大数。然后按运价从小到大顺序填数。若某行（列）的产量（销量）已满足，则把该行（列）的其他格划去。如此进行下去，直至得到一个基本可行解。 注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列，只有最后一个元例外（同时划去一行和一列）。当填上一个数后行、列同时饱和时，也应任意划去一行（列）在保留的列（行）任意没被划去的格内标一个0。,3、运 输 问 题（3.2）,8,*,3、运 输 问 题（3.2）,9,*,3、运 输 问 题（3.2）,10,2、最优性检验： 因为求最小，当所有检验数均大于等于0时为最优解 （1）

6、位势法求检验数： 位势：设对应基变量 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, , n,3、运 输 问 题（3.2）,11,前例，位势法求检验数： step 1 从任意基变量对应的 cij 开始，任取 ui 或 v

7、j ，然后利用公式 cij = ui + vj 依次找出 m + n 个 ui , vj ；从 c14 = 10 开始 step 2 计算非基变量的检验数 ij = cij - ui - vj ；填入圆圈内,3、运 输 问 题（3.2）,12,3、主元变换： （1）选负检验数中最小者 rk，那么 xrk 为主元，作为进基变量；（上页图中 x24 ） （2）以为 xrk 起点找一条闭回路，除 xrk 外其余顶点必须为基变量格；（上页图中 蓝色回路） （3）为闭回路的每一个顶点标号， xrk 为 1，沿一个方向依次给各顶点标号； （4）求=minxijxij对应闭回路上的偶数标号格= xpq那么确

8、定xpq为出基变量，为调整量； （5）对闭回路的各奇标号顶点 xij + ，对各偶标号顶点 xij - ，特别 xpq - = 0，变为非基变量；,3、运 输 问 题（3.2）,重复2、3步，直到所有检验数均非负，得到最优解。,13,主元变换： 由前面得到 = 1，于是,3、运 输 问 题（3.2）,ij 0，得到最优解 x13 = 5, x14 = 2, x21 = 3, x24 = 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-2,14,3. 3

9、产销不平衡的运输问题 1、产量大于销量 例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个虚设的销地运输费用为0,3、运 输 问 题（3.3）,15,2、销量大于产量 例、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往个销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 解：增加一个虚设的产地运输费用为0,3、运 输 问 题（3.3）,16,下面给出一些例题，可作为建模的练习： 例、石家庄北方研

10、究院有一、二、三，三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价如下表。由于需大于供，经院研究决定一区供应量可减少0-200吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。,3、运 输 问 题（例题）,17,解： 根据题意，作出产销平衡与运价表： 取 M 代表一个很大的正数，其作用是强迫相应的 x31、 x33、 x34取值为0。,3、运 输 问 题（例题）,18,例、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表。

11、试求总费用为最低的化肥调拨方案。,3、运 输 问 题（例题）,19,解： 根据题意，作出产销平衡与运价表： 最低要求必须满足，因此把相应的虚设产地运费取为 M ，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为 0 。对应 4”的销量 50 是考虑问题本身适当取的数据，根据产销平衡要求确定 D的产量为 50。,3、运 输 问 题（例题）,20,例、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合

12、同的情况下，使该厂全年生产总费用为最小的决策方案。,3、运 输 问 题（例题）,21,解： 设 xij为第 i 季度生产的第 j 季度交货的柴油机数目，那末应满足： 交货：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 个销售点的销量；成本加储存、维护等费用看作运费。可

13、构造下列产销平衡问题： 目标函数：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44,3、运 输 问 题（例题）,22,例、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表 已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7-8月份销售淡季，全厂停产1个月

14、，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1-6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？,3、运 输 问 题（例题）,23,解： 这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地 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月份加班生产情况。 续下页

15、 产销平衡与运价表：,3、运 输 问 题（例题）,24,*习题：p 124 习题3 3-3，3-4,3、运 输 问 题（例题）,返回目录,25,4. 1 动态规划概念与模型 多阶段决策过程特点 要点：阶段，状态，决策，状态转移方程，k-后部子过程,4、动 态 规 划(4.1),26,动态规划模型 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 )：目标函数（

16、最优值函数） xk+1 = Tk ( xk , uk ) ：状态转移方程 Xk ：状态可能集合 Uk：决策允许集合,4、动 态 规 划(4.1),27,建模过程 确定阶段与阶段变量； 明确状态变量与状态可能集合； 明确决策变量与决策允许集合； 明确状态转移方程； 确定阶段效应和目标。,4、动 态 规 划(4.1),28,4. 2 动态规划求解 求解动态规划模型： 从起始状态 x1 开始，找最优策略、最优路线和最优目标值。 最优性原理 最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所确定的某一状态而言，余下的决策序列必构成最优策略。 最优策略的任何一子策略也是相应初始状态的最

17、优策略；每个最优策略只能由最优子策略构成。,4、动 态 规 划(4.2),29,贝尔曼函数：（ k - 子过程的最优目标函数 ) n fk(xk) = opt ri ( xi , ui ) k=1,n i=k 动态规划求解问题的一般过程： 逆序地求出条件最优目标函数值集合和条件最优决策集合： fn+1(xn+1) = 0 (边界条件) fk(xk) = opt rk ( xk , uk ) + fk+1(xk+1) u k = n,1,4、动 态 规 划(4.2),30, 顺序地求最优决策序列： 初始状态唯一：R* = f1(x1)，u1* (x1)=u1(x1) 若不唯一：R* = optf

18、1(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.2),31,1、动态规划的四大要素、一个方程 重点 状态变量及其可能集合 xk Xk 决策变量及其允许集合 uk Uk 状态转移方程 xk+1 = Tk ( xk , uk ) 阶段效应 rk ( xk , uk ) 动态规划基本方程 fn+1(xn+

19、1) = 0 (边界条件) fk(xk) = opt rk ( xk , uk ) + fk+1(xk+1) u k = n,1,4、动 态 规 划(4.2),32,4. 3 动态规划应用举例 例：一个线路网络图，从A到E要修建一条石油管道，必须 在B、C、D处设立加压站。各边上的数为长度，现需要找一条路使总长度最短。,4、动 态 规 划(4.3),33,解： 可分成4个阶段：A到B、B到C、C到D、D到E ； 每个阶段 k 的起点称为状态 S k ； 从 k 阶段的起点出发可以做一选择，即决定到下一阶段的哪个节点，称为决策 X k ； 可见， S k+1 是由 S k 和 X k 所决定的。

20、 那麽，从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 ，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.3续),34, 最短路问题的特点：如果从 A 到E 的最优策略经过某节点，那么这个策略的从该节点到E的一段，必定是该节点到E的所有线路中 S k 最

21、短的一条，即这一段的长度为 f k（S k）。 （1）逆序法：从E到A （2）顺序法：对节点 S k ，从 A到 S k 所有线路中，最短的一条的长度记为 k（S k），例如 1（A）= 0 ，称为问题的边界条件。,4、动 态 规 划(4.3续),动态规划文本,35,学习方法建议： 第一步 先看问题，充分理解问题的条件、情况及求解目标； 第二步 结合前面讲到的理论和解题过程，考虑如何着手进行求解该问题的工作。分析针对该动态规划问题的“四大要素、一个方程”这一步在开始时，会感到困难，但是一定要下决心去思考，在思考过程中深入理解前文讲到的概念和理论；,4、动 态 规 划(4.3续),36,第三步

22、动手把求解思路整理出来，或者说，把该问题作为习题独立的来做； 第四步 把自己的求解放到一边，看书中的求解方法，要充分理解教材中的论述； 第五步 对照自己的求解，分析成败。 *习题： p175-177 4 -1，4 -2，4 -3，4 -6； *练习：4 -4，4 -5，4 -7,4、动 态 规 划(4.3续),返回目录,37,5. 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的关联

23、边,5、图 与 网 络 分 析（5.1）,图的其他概念 ： 相邻点，相邻边， 环，多重边（平行边）， 多重图，简单图,38,端点的次d(v)：点 v 作为边端点的次数； 奇点：d(v)=奇数； 偶点：d(v)=偶数； 悬挂点：d(v)=1；悬挂边：与悬挂点连接的边， 孤立点：d(v)=0；空图：E = ，无边图。 定理一：所有顶点次数之和等于所有边数的2倍。 定理二：在任一图中，奇点的个数必为偶数。,5、图 与 网 络 分 析（5.1续）,39,图的连通性： 链：由两两相邻的点及其相关联的边构成的点边序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1

24、 , en , vn ； v0 , vn分别为链的起点和终点 简单链：链中所含的边均不相同； 初等链：链中所含的点均不相同，也称通路； 回路：若 v0 vn 分称该链为开链，否则称为闭链或回路； 圈：出起点和终点外链中所含的点均不相同的闭链； 连通图：图中任意两点之间均至少有一条通路，否则称作不连通图。,5、图 与 网 络 分 析（5.1续）,40,子图 设 G1 = V1 , E1 , G2 = V2 , E2 子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图； 部分图：如果 V2 = V1 ,

25、E2 E1 称 G2 是 G1 的部分图； 导出子图：如果 V2 V1 , E2 = vi , vj vi , vj V2 ，称 G2 是 G1 中由V2 导出的导出子图。,5、图 与 网 络 分 析（5.1续）,41,有向图：关联边有方向 弧：有向图的边 a = ( u , v )，起点 u，终点 v； 路：若有从 u 到 v 不考虑方向的链，且各方向一致，则称之为从 u 到 v 的路； 初等路：各顶点都不相同的路； 初等回路：u = v 的初等路 连通图：若不考虑方向 是无向连通图 强连通图：任两点有路,5、图 与 网 络 分 析（5.1续）,42,树：无圈连通图；无圈图又称为树林，子连通

26、图是树 定理：六种等价描述。 设：边数 q , 顶点数 p . 1、无圈连通图； 2、边数q = 顶点数p - 1； 3、连通，且 q = p - 1； 4、无圈，但加一边则得到唯一的圈； 5、连通，但若去一边则图不连通； 6、每对顶点之间有且仅有一条链。 部分树：若一个图 G 的部分图 T 是树，则称 T 为部分树，又称生成树 余树：G 中去掉 T 所有的边后得到的部分树称为 G 中 T 的余树，余树不一定是树。,5、图 与 网 络 分 析（5.1续）,43,5、图 与 网 络 分 析（5.2）,5. 2 网络最短路问题 网络：规定起点、中间点和终点的赋权图； 有向网络：网络中每个边都是有向

27、边； 无向网络：网络中每个边都是无向边； 混合网络：网络中既有有向边，又有无向边； 网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。 Min L() = lij 为从 v1 到 vn 的通路； lij 其中， lij为从 vi 到 vj 的一步距离。,44,结合例题学习、掌握求最短路的狄克斯拉、海斯和福德三个方法： 1、狄克斯拉方法：适用于满足所有权系数大于等于0（lij0）的网络最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离； 2、海斯方法：基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi 到 vj 的两步距离再求出 vi 到 vj 的四步距离经有限次迭代可求出 vi 到 vj 的最短距离； 3、福德方法：适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。 *习题： p218-219 习题5 5-2,5、图 与 网 络 分 析（5.2续