运筹学期末复习与串讲PPT学习教案

1、会计学1 运筹学期末复习与串讲运筹学期末复习与串讲 考试时间：第十六周考试时间：第十六周 第1页/共67页 一、线性规划部分一、线性规划部分 ： 基本概念：基本概念： 定义：满足所有约束条件的解为可行解；可行解的全体称为可 行（解）域。 定义：达到目标的可行解为最优解。 由图解法得到的三个结论： 线性规划模型的可行解域是凸集； 如果线性规划模型有唯一的最优解的话，则最优解一定是凸 集（可行解域）的角顶； 任何一个凸集，其角顶个数是有限的。 第2页/共67页 运输问题运输问题 1.运输问题的概念：运输问题的概念： 设有m个产地Ai（i=1，2，m），n个销地Bj（j=1，2， ，n）, Ai产量

2、（供应量）Si，Bj销量（需求量）di，若产、销 平衡，则： n j j m i i ds 11 2.表上作业法的基本步骤和求解的特点表上作业法的基本步骤和求解的特点 3.闭回路闭回路 第3页/共67页 1.整数规划的特点整数规划的特点 2.整数规划解的特点整数规划解的特点 最优解不一定在顶点上达到最优解不一定在顶点上达到。 最优解不一定是松弛问题最优解的邻近整数解最优解不一定是松弛问题最优解的邻近整数解。 整数可行解的个数远多于松弛问题的顶点整数可行解的个数远多于松弛问题的顶点, ,枚举法枚举法 不可取不可取。 若松弛的若松弛的LPLP问题无解问题无解, ,则原则原ILPILP问题无解问题无

3、解。反之反之, ,不不 一定成立一定成立。 如果松弛的如果松弛的LPLP问题无界呢问题无界呢? ? 可以证明原可以证明原ILPILP问题也问题也 无界无界。 （三）整数规划与分配问（三）整数规划与分配问 题题 第4页/共67页 1.网络分析中的一些常用名词：网络分析中的一些常用名词： 无向图无向图：由点和边构成的图，记作：由点和边构成的图，记作G=G=（V V，E E）。）。 有向图有向图：由点和弧构成的图，记作：由点和弧构成的图，记作D=D=（V V，A A）。）。 连通图连通图：对无向图：对无向图G G，若任何两个不同的点之间，至少存在一条，若任何两个不同的点之间，至少存在一条 链，则链，

4、则G G为连通图。为连通图。 回路回路：若路的第一个点和最后一个点相同，则该路为回路。：若路的第一个点和最后一个点相同，则该路为回路。 赋权图赋权图：对一个无向图：对一个无向图G G的每一条边的每一条边(v(vi i,v,vj j) )，相应地有一个数，相应地有一个数 w wij ij，则称图 ，则称图G G为赋权图，为赋权图，w wij ij称为边 称为边(v(vi i,v,vj j) )上的权。上的权。 网络网络：在赋权的有向图：在赋权的有向图D D中指定一点，称为发点，指定另一点称中指定一点，称为发点，指定另一点称 为收点，其它点称为中间点，并把为收点，其它点称为中间点，并把D D中的每

5、一条弧的赋权数称为中的每一条弧的赋权数称为 弧的容量，弧的容量，D D就称为网络。就称为网络。 树：就是一个无圈的连通图树：就是一个无圈的连通图 （四）图与网络分析（四）图与网络分析 第5页/共67页 l有关网络最大流的几个概念： 网络的每条弧上的最大通过能力称为该弧的容量 。 容量限制条件。容量网络上所有的弧满足： 0fijcij 网络N中的流f 是最大流当且仅当N中不包含任何 增广链 树：无圈的连通图即为树 性质1：任何树中必存在次为1的点。 性质2：n 个顶点的树必有n-1 条边。 性质3：树中任意两个顶点之间，恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：

6、树无回圈，但不相邻的两个点之间加一条边，恰 得到一个圈。 第6页/共67页 1. 常用名词：常用名词： 作业作业 事件事件 路线及关键路线路线及关键路线 网络图网络图 （五）计划评审方法和关键路线法（五）计划评审方法和关键路线法 2. 建立建立PERT网络图的准则网络图的准则 3. 6个时间参数个时间参数 第7页/共67页 例1 某企业计划生产甲、乙两种产品。这些产品分别 要在A、B、C、D、四种不同的设备上加工。按工艺 资料规定，单件产品在不同设备上加工所需要的台时 如下表所示，企业决策者应如何安排生产计划，使企 业总的利润最大？ 设设 备备 产产 品品 A B C D利润（元）利润（元）

7、甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12 第8页/共67页 第9页/共67页 标准型的特点： (1) 目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程，且右端常数项bi都大于或等于 零 (3) 决策变量xj为非负。 ,0, 523 24 7 5 32min 321 321 321 321 321 无无约约束束xxx xxx xxx xxx xxxZ 第10页/共67页 令 解:（）因为x3无符号要求 ，即x3取正值也可取负值， 标准型中要求变量非负， 333 xxx 0, 33 x x ,0, 523 24 7 5 32mi

8、n 321 321 321 321 321 无无约约束束xxx xxx xxx xxx xxxZ 在“”左端加入松驰变量x4，x40,化 为等式； x4 在“”左端减去剩余变量x5，x50 x5 右端常数项为-5，方程两边同乘以(-1), 将右端常数项化为正数 目标函数是最小值，为了化为求最大值 ，令z=-z,得到max z=-z，即当z达 到最小值时z达到最大值，反之亦然。 x4 x5 第11页/共67页 标准形式如下： x4 x5 x4 x5 0, 543321 xxxxxx 第12页/共67页 C图解法 例3 用图解法求解线性规划问题 12 1 2 28 4 16 412 xx x x

9、0,1,2 i xi 最优解 ( 4 , 2 ) ,1 4Xz 第13页/共67页 0, 303 402 43max 21 21 21 21 xx xx xx xxZ C单纯形法求解 第14页/共67页 1.将问题化为标准型 2.建立初始单纯形表 3.进行最优性检验 若检验数 ,则当前解为最优解，计算停止。 否则继续下一步：迭代 ； 4.迭代 l单纯形法求解步骤（教材P18） 0 j 确定换入基的变量。选择 ，对应的变量xj作为换入变量 ，当有一个以上检验数大于0时，一般选择最大的一个检验数， 即： ，其对应的xk作为换入变量。0|max jjk 0 j 用换入变量xk替换基变量中的换出变量，

10、得到一个新 的基。对应新的基可以找出一个新的基可行解，并相 应地可以画出一个新的单纯形表。 5 .重复3）、4）步直到计算结束为止。 确定换出基变量。根据下式计算并选择 ，选最小的对应基变量作 为换出变量。 0min ik ik i L a a b 第15页/共67页 j c nmm cccc 11 B c B Xb m c c 1 m x x 1 m b b 1 nmm xxxx 11 i m 1 mnmm nm aa aa 1, 11, 1 10 01 0 0 ijijj acc 0 kj kj i i a a b 最小比值列 基变量系数基变量系数 基变量基变量 约束条件等式右 边的常量

11、目标函数中的系数值 约束条件 系数区 检验系数区检验系数区 jjj zc 第16页/共67页 0, 303 402 43max 21 21 21 21 xx xx xx xxZ 解：1）将问题化为标准型，加入松驰变 量x3、x4则标准型为: 0, 303 402 43max 4321 421 321 21 xxxx xxx xxx xxZ i 3) 1020(3)( 21411311 acacc 检验数 cj 3400 基基 x3 x4 cB 0 0 b 40 30 x1x2x3x4 2110 1301 3400 - ijijj acc 第17页/共67页 cj3400 i cB基变量基变量b

12、x1x2x3x4 0 x3402110 0 x4301301 3400 换入列b i / a i 2 ， ai20 40 10 换出 行 将3化为1 5/3 1 180 1/301/310 11/330 30 05/304/3 乘以1/3后得到 103/5 1/5 18 011/5 2/5 4 00 11 j j j 0 x3 4x2 - x1 3 4x2 Max z=3*18+4*4=70 第18页/共67页 第19页/共67页 0, 124 164 82 1222 . 32max 21 2 1 21 21 21 xx x x xx xx ts xxz 原问题 （对偶问题） 对偶问题 （原问

13、题） 22 12 40 0 4 minW=12y1+8y2+16y3+12y4 2y1+y2+4y3+0y4 y1 y2 y3 y4 2 2y1+2y2+0y3+4y43 y1 , y2 , y3, y40 第20页/共67页 原问题原问题 约束条件右端项约束条件右端项 目标函数变量的系数目标函数变量的系数 目标函数目标函数 max 约约 束束 条条 件件 m个个 = 变变 量量 n个个 0 0 无约束无约束 对偶问题对偶问题 目标函数变量的系数目标函数变量的系数 约束条件右端项约束条件右端项 目标函数目标函数 min m个个 0 0 无约束无约束 n个个 = （或原问题）（或原问题） （或对

14、偶问题）（或对偶问题） 变变 量量 约约 束束 条条 件件 第21页/共67页 3 , 2 , 1, 0 1622 102 43max 321 321 321 jx xxx xxx xxxz j 的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。 解：写出原问题的对偶问题，即 0, 1 422 32 1610min 21 21 21 21 21 yy yy yy yy yyw 0, 1 422 32 1610min 54321 521 421 321 21 yyyyy yyy yyy yyy yyw 标准化 第22页/共67页 0 0 s s XY XY 即：即： 0),)(,( 0),

15、)(,( 5421 321543 T T xxyy xxxyyy 因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零 ，即y30，y40，带入方程中： 422 32 21 21 yy yy 解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为 ： Y=(1,1)，最优值w=26 X=(6,2,0)T 0, 1 422 32 54321 521 421 321 yyyyy yyy yyy yyy 第23页/共67页 性质1 对称性定理：对偶问题的对偶是原问题 min W= Y b s.t. YA C Y 0 max Z=C X s.t. AXb X 0 第24页/共67页 性

16、质2 弱对偶原理(弱对偶性)：设 和 分别是问题(P) 和(D)的可行解，则必有 0 X 0 Y n j m i iijj byxcbYCX 11 00 即即： 推论1: 原问题任一可行解的目标函数值是其对偶问题目标函数值 的下届；反之，对偶问题任意可行解的目标函数值是其原问题目 标函数值的上界。 推论2: 在一对对偶问题（P）和（D）中，若其中一个问题可行 但目标函数无界，则另一个问题无可行解；反之不成立。这也是 对偶问题的无界性。 第25页/共67页 性质3 最优性定理：如果 是原问题的可行解， 是其对偶 问题的可行解，并且: 0 X 0 Y wz: 00 即即BYCX 则 是原问题的最优

17、解， 是其对偶问题的最优解。 0 X 0 Y 第26页/共67页 ), 1, 1(0, 0 ), 1( . max 1 1 njmixx mibxxa ts xcz sij n j isijij n j jj , 0 Y), 1(0miyi 0 YAC ), 1( 1 njcya n i jiij ), 1(0miyi bBCxc B n j jj 1 1 m i ii yb 1 Dual property） 性质4 强对偶性：若原问题及其对偶问题均具有可行解 ，则两者均具有最优解，且它们最优解的目标函数值相 等，即wzminmax 第27页/共67页 还可推出另一结论：若（LP）与（DP）

18、都有可行解，则两者都有最优解，若一个问 题无最优解，则另一问题也无最优解。 第28页/共67页 Dual property） 性质5 互补松弛性：设X0和Y0分别是P问题 和 D问题 的可 行解，则它们分别是最优解的充要条件是： 0 0 0 s s 0 XY XY 其中：Xs、Ys为松弛变量 y1 yi ym vm+1 vm+j vm+n x1 xj xn un+1 un+i un+m 对偶问题的变量 对偶问题的剩余变量 xjvm+j=0 yiun+i=0(i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0 第29页/共67页 0 0 s s XY XY 互补松

19、弛条件 由于变量都非负，要使求和式等于零，则必定每一分量为零， 因而有下列关系： 若Y0，则Xs必为0；若X0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组 ，方程组的解即为最优解。 第30页/共67页 B1B2B3B4生产能力生产能力 A13113107 A219284 A3741059 需求3656 第31页/共67页 确定初始确定初始方案方案 ( (初始基可行解初始基可行解) ) 改进调整改进调整 （换基迭代）（换基迭代） 否否 判定是否判定是否 最最 优？优？ 是是 结结 束束 最优方案最优方案 求解思路图求解思路图 第32页/共67页 即即 7 4 9 365

20、620 3 3 1 B 2 B 3 B 4 B 1 A 2 A 3 A ( (一一) ) 初始方案的给定初始方案的给定 第33页/共67页 7 4 9 365620 1 B 2 B 3 B 4 B 1 A 2 A 3 A 第34页/共67页 优选考虑优选考虑最大差额（最小运价优势）最大差额（最小运价优势）方案方案 罚数罚数次小次小运价系数运价系数- -最小最小运价系数运价系数 1 B 2 B 3 B 4 B 1 A 2 A 3 A 产量产量 销地销地 产地产地 1 B 2 B 3 B 4 B 1 A 2 A 3 A 0 0 1 1 1 1 2 25 51 13 3( )( ) 6 6 2 2

21、2 2 0 0 0 0 7 7 1 1 3 3 1 12 2 1 12 2 1 1 1 1 6 6 2 2 ( )( ) 3 3 3 3 ( )( ) 5 52 2 1 1 1010 8 8 ( )( ) 第35页/共67页 1 B 2 B 3 B 4 B 1 A 2 A 3 A 产量产量 销地销地 产地产地 1 B 2 B 3 B 4 B 1 A 2 A 3 A 6 63 3 3 3 5 52 2 1 1 一般当产销地数量不多时，一般当产销地数量不多时， (Vogel)(Vogel)法给出的初始方案法给出的初始方案 有时就是最优方案。有时就是最优方案。 第36页/共67页 最小元素法或最小元

22、素法或VogelVogel法给出的是一个运输问题的基可行法给出的是一个运输问题的基可行 解，需要通过最优性检验判别该解得目标函数值是否最优解，需要通过最优性检验判别该解得目标函数值是否最优 ，当为否时，应进行调整得到优化，当为否时，应进行调整得到优化. . ( (二二) ) 最优性检验与方案的调整最优性检验与方案的调整 基本思想：基本思想： 计算非基变量计算非基变量（未填上数值的格，即空格）（未填上数值的格，即空格） 的检验数的检验数（也称为（也称为空格的检验数空格的检验数），若全部），若全部大于大于 等于零等于零，则该方案就是，则该方案就是最优最优调运方案，调运方案，否则否则就应就应 进行调

23、整。进行调整。 1.1.闭回路法闭回路法 .对偶变量法（对偶变量法（位势法位势法） ijij kk xzz )()1( 第37页/共67页 3- 132222111 , jijijijijiji sss xxxxxx 132222111 , jijijijijiji sss PPPPPP 0 132222111 jijijijijiji sss PPPPPP m+n-1个变量构成个变量构成基变量基变量的充要条件是该变的充要条件是该变 量组量组不含闭回路不含闭回路。 第38页/共67页 将如下表中将如下表中6 6个顶点间用水平或垂直线段连接起来，个顶点间用水平或垂直线段连接起来， 组成一条封闭的

24、回路。组成一条封闭的回路。 1 B 2 B 3 B 4 B 1 A 2 A 3 A 销量销量 产产 量量 销地销地 产地产地 (A(A2 2 ,B ,B1 1 ), (A ), (A3 3 ,B ,B2 2) )无法连入闭回路中无法连入闭回路中 闭回路闭回路 孤 立 格孤 立 格 是 指是 指 在 所 在 行在 所 在 行 或或 列 中列 中 唯 一唯 一 出 现 的 变 量 。出 现 的 变 量 。 孤立格一定不会成为闭回路的顶点孤立格一定不会成为闭回路的顶点 最小元最小元 素法得素法得 初始方初始方 案案 第39页/共67页 ijij kk xzz )()1( (1)( ) 1, kk i

25、jij xzzz 这里则 4.4.如果如果所有所有代表非基变量的空格的检验数也即非基变量代表非基变量的空格的检验数也即非基变量 的检验数都大于等于零，则已求得最优解，否则进的检验数都大于等于零，则已求得最优解，否则进 行行方案调整（后续）方案调整（后续） 第40页/共67页 1 B 2 B 3 B 4 B 1 A 2 A 3 A 同理可以找出所有空格（即非基变量）的检验数。同理可以找出所有空格（即非基变量）的检验数。 1 11 3 1231 即此新可行解较原来解运费增加即此新可行解较原来解运费增加1 1元元 第41页/共67页 闭回路法求检验数闭回路法求检验数 1 B 2 B 3 B 4 B

26、1 A 2 A 3 A 31 10 12 22 24 33 2; 1; 1; 12; 75 1032 110 约定约定奇数次顶点奇数次顶点 ij 第42页/共67页 - -1 11 1 A A2 2 12121010A A3 3 2 21 1A A1 1 B B4 4B B3 3B B2 2B B1 1 销地销地 产地产地 检验数表检验数表 闭回路法求调整方案闭回路法求调整方案 在作业表上以在作业表上以（A A2 2 , B , B4 4 ）为起点作一条除该空为起点作一条除该空 格外其余顶点均为有数格外其余顶点均为有数 字格组成的闭回路字格组成的闭回路 第43页/共67页 闭回路法求调整方案闭

27、回路法求调整方案 1 B 2 B 3 B 4 B 1 A 2 A 3 A 20206 65 56 63 3 9 9 4 4 13 7 7 4 4 6 3 3 调运方案（最小元素法得到）调运方案（最小元素法得到） + + 1 1 - -1 1 调整量=min3,1=1 离离 基基 ？ 在作业表上以在作业表上以（A A2 2 , B , B4 4）为起点作一条除该空为起点作一条除该空 格外其余顶点均为有数字格组成的闭回路格外其余顶点均为有数字格组成的闭回路 在这条闭回路上，在保持产销平衡的条件下对在这条闭回路上，在保持产销平衡的条件下对偶数偶数 顶点格子的运量做最大可能的调整顶点格子的运量做最大可

28、能的调整 +1+1 - - 1 1 第44页/共67页 闭回路法求调整方案闭回路法求调整方案 1 B 2 B 3 B 4 B 1 A 2 A 3 A 20206 65 56 63 3 9 9 4 4 3 7 7 5 5 63 2 调运方案（最小元素法得到）调运方案（最小元素法得到） 1 1 继续 用闭 回路 检验 1 12 2A A2 2 12129 9A A3 3 2 20 0A A1 1 B B4 4B B3 3B B2 2B B1 1 销地销地 产地产地 检验数表检验数表 检验数0 ，所以该调 运方案是最 优方案。 第45页/共67页 例8 有一份说明书, 要分别译成英、日、德、俄四种文

29、 字, 交甲乙丙丁四个人去完成. 因各人专长不同, 他们完 成翻译不同文字所需的时间如表所示. 应如何分配, 使这 四人分别完成 这四项任务总的时间最小. 译成英文译成英文译成日文译成日文译成德文译成德文译成俄文译成俄文 甲甲 21097 乙乙 154148 丙丙 13141611 丁丁 415139 工工 作作 人人 教材P87，例2 第46页/共67页 例9 有甲,乙,丙,丁,戊,己6名运动员报名参加 A,B,C,D,E,F 6个项目的比赛。下表中打的是各运 动员报告参加的比赛项目。问6个项目的比赛顺序 应如何安排，做到每名运动员都不连续地参加两项 比赛。 ABCDEF 甲甲 乙乙 丙丙

30、丁丁 戊戊 己己 第47页/共67页 A B C D E F 在图中找到一个点 序列，使得依次排 列的两点不相邻， 即能满足要求。 如： 1) A,C,B,F,E,D 2) D,E,F,B,C,A ABCDEF 甲甲 乙乙 丙丙 丁丁 戊戊 己己 第48页/共67页 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 4 5 2 2 3 10 3 96 12 6 4 11 6 6 18 8 12 24 8 24 18 所有点都已标号，点上的标号就是v1到该点的最短距离，最短 路线就是红色的链。 第49页/共67页 例11 用标号算法求下图中st的最大流量，并找出最小割 。 v

31、1v3 v2v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) 第50页/共67页 v1v3 v2v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) (0,) 第51页/共67页 v1 v3 v2v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) (0，) (2) 检查与s点相邻的未标号的点，因fs1cs1，故对v1标号 =min, cs1-fs1=1, )1( (s，1) 第52页/共67页 v1v3 v2v4 8(7) 9(3) 5(4) 10(8) 6

32、(1) 2(0) 9(9) 5(4) 7(6) (0， ) (s，1) (2) 检查与v1点相邻的未标号的点，因f13c13，故对v3标号 =min1, c13-f13= min1, 6= 1)3( (v1，1) 第53页/共67页 v1v3 v2v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(4) 7(5) (0， ) (s，1) (v1，1) (3) 检查与v3点相邻的未标号的点，因f3tc3t，故对vt标号 =min1, c3t-f3t= min1, 1= 1 )(t (v3，1) 找到一条增广链 sv1v3t 第54页/共67页 (4) 修改增广链上的

33、流量，非增广链上的流量不变，得到新 的可行流。 v1v3 v2v4 8(7) 9(3) 5(4) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) 1 1 s f 1 13 f 1 3 t f (0， ) (s，1) (v1，1) (v3，1) 所有非增广链上的弧所有非增广链上的弧 对增广链上所有后向弧对增广链上所有后向弧 对增广链上所有前向弧对增广链上所有前向弧 f tf tf f)( )( 第55页/共67页 (5) 擦除所有标号，重复上述标号过程，寻找另外的增广链 。 v1v3 v2v4 8(8) 9(4) 5(5) 10(8) 6(0) 2(0) 9(9) 5(3) 7(5

34、) (0， ) (s，1) (v1，1) (v3，1) 第56页/共67页 (5) 擦除所有标号，重复上述标号过程，寻找另外的增广链 。 v1v3 v2v4 8(8) 9(4) 5(5) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) (0，) (s，2) (2)=min,2=2 (v2，2) (1) =min(v2),f12 =min2,3=2 (3)=min2,5=2(v1，2) (v3，1) (4)=min2,1=1 (v4，1) (t)=min1,2=1 第57页/共67页 (6) 修改增广链上的流量，非增广链上的流量不变，得到新 的可行流。 v1v3 v2v4 8(8) 9(4) 5(5) 10(8) 6(1) 2(0) 9(9) 5(3) 7(5) 1 2 s f 1 21 f 1 13 f 1 34 f 1 4 t f (0，) (s，2) (v2，2)(v1，2) (v3，1) (v4，1) 第58页/共67页 v1v3 v2v4 8(8) 9(5) 5(5) 10(9) 6(0) 2(0) 9(9) 5(2) 7(6) (7) 擦除所有标号，重复上述标号过程，寻找另外的增广链 。 (0，) (s，2)