《复习运筹学课件胡运权第四版复习要点.ppt》由会员分享，可在线阅读，更多相关《复习运筹学课件胡运权第四版复习要点.ppt（28页珍藏版）》请在三一文库上搜索。
1、运 筹 学,Operations Research,第一章 线性规划及单纯形法,第一章 线性规划及单纯形法,如何转化为标准形式？,1、目标函数为求极小值，即为： 。,因为求 min z 等价于求 max (-z)，令 z = - z， 即化为：,2、约束条件为不等式，,xn+1 0 松弛变量,如何处理？,1 线性规划问题及其数学模型,、右端项bi 0时，只需将等式两端同乘（-1） 则右端项必大于零,4、决策变量无非负约束,设 xj 没有非负约束，若 xj 0，可令 xj = - xj ， 则 xj 0；,又若 xj 为自由变量，即 xj 可为任意实数， 可令 xj = xj - xj，且 xj
2、 , xj 0,第一章 线性规划及单纯形法,e.g. 3,试将 LP 问题,min z = -x1+2x2-3x3 s.t. x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3 = -5 x1,x2 0 化为标准形式。,解：,令 x3= x4 - x5 其中x4、x5 0；,对第一个约束条件加上松弛变量 x6 ；,对第二个约束条件减去松弛变量 x7 ；,对第三个约束条件两边乘以“-1” ；,令 z=-z 把求 min z 改为求 max z,max z= x1-2x2+3x4- 3x5 s.t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-
3、2x4+2x5=5 x1,x2,x4,x5,x6,x70,2 线性规划问题的图解法,max z = 15x1 +25x2 s.t. x1 + 3x2 60 x1 + x2 40 x1，x2 0,(40,0),(0,0),B,C,(30,10),O,L1,L2,Z=250,目标函数变形：,x2=-3/5 x1+z/25,x2,x1,最优解： x1=30 x2 =10 最优值：zmax=700,B点是使z达到最大的唯一可行点,第一章 线性规划及单纯形法,LP问题图解法的基本步骤：,1、在平面上建立直角坐标系；,2、图示约束条件，确定可行域和顶点坐标；,3、图示目标函数（等值线）和移动方向；,4、寻
4、找最优解。,2 线性规划问题的图解法,max z =3x1 + 5.7x2 s.t. x1 + 1.9x2 3.8 x1 - 1.9x2 3.8 x1 + 1.9x2 11.4 x1 - 1.9x2 -3.8 x1 ，x2 0,x1,x2,o,x1 - 1.9 x2 = 3.8,x1 + 1.9 x2= 3.8,x1 + 1.9 x2 = 11.4,（7.6,2）,D,0=3 x1 +5.7 x2,max Z,min Z,（3.8,4）,34.2 = 3 x1 +5.7 x2,可行域,x1 - 1.9 x2 = -3.8,(0,2),(3.8,0),绿色线段上的所有点 都是最优解,即有无穷多最
5、优解。Zman=34.2,第一章 线性规划及单纯形法,max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0,O,x1,x2,Note: 可行域为无界区域， 目标函数值可无限 增大，即解无界。 称为无最优解。,可行域为无界区域一定无最优解吗？,2 线性规划问题的图解法,由以上两例分析可得如下重要结论：,1、LP 问题从解的角度可分为：, 有可行解, 无可行解,有唯一最优解 b. 有无穷多最优解 C. 无最优解,2、LP 问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。,3：差值法（伏格尔法
6、） 最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小费用就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小调运方案。 基于此，伏格尔法的步骤是：每次从当前运价表上，计算各行各列中最小费用与次小费用这两个运价的差值，优先取最大差值的行或列中最小的运价来确定运输关系，直到求出初始方案。,仍然考虑先前的例子,伏格尔法的步骤如下：,（1）先分别计算出各行各列最小费用与次小费用的差额，并填入该表的最右列和最下行。,（2）从行差额和列差额中选出最大者，选择它所在的行或列
7、中的最小元素所在的格作为优先的运输方案。在这里优先选A3满足B2 6个单位， B2列已满足，划去B2列。,（3）计算剩余元素的行差额和列差额，并选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3供应B4 3个单位， A3行已满足，划去A3行。,（4）继续进行。在这里优先选A2供应B1 3个单位， B1列已满足，划去B1列。,（5）继续进行,（6）继续进行,（7）继续进行得最终结果为：,（8）得到初始方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3 总运费=3*5+10*2+1*3+8*1+4*6+5*3=85（元）,例：求v1至v
8、8的最短路。,v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(1) v1:0,v1,计算min 0+2, 0+1, 0+3= min 2,1,3=1 v4:1.v1,1,v1,0,v1,(2)A=v1,检查边（v1,v2),(v1,v4),(v1,v3),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(3)A=v1,v4,计算 min0+2, 0+3, 1+1
9、0, 1+2=min 2,3,11,3=2 v2:2,v1,0,v1,1,v1,2,v1,考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,（4）A=v1,v2,v4,计算min 0+3, 2+6, 2+5, 1+2=min 3,8,7,3=3 v6:3,v1,2,v1,1,v1,0,v1,3,v1,考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,
10、6,8,2,(5)A=V1,V2,V4,V6,计算 min 2+6, 2+5, 1+2, 3+4=min 8,7,3,7=3 v7:3,v4,2，V1,1，V1,0，V1,3，V1,3,v4,考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7),V2,V3,V7,V1,V8,V4,V5,V6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(6)A=V1,V2,V4,V6,V7,计算min 2+6, 2+5, 3+3, 3+8=min 8,7,6,11=6 v5:6,v7,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,考虑边(v2,v3),(v2,v
11、5),(v7,v5),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(7)A=V1,V2,V4,V6,V7,计算min 2+6, 6+9, 6+4, 3+8=min 8,15,10,11=8 v3:8,v2,2,V1,1,V1,0,V1,3,V1,3,V4,6,V7,8,v2,考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(8)A=v1,v2,v3,v4,v6,v7,计算 min 8+6, 6+4, 3+8=min 14,10,11=10 v8:10,v5,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,8,v2,10,v5,考虑边（v3,v8),(v5,v8),(v7,v8),v2,v3,v7,v1,v8,v4,v5,v6,6,1,3,4,10,5,2,7,5,9,3,4,6,8,2,(9)A=v1,v2,v3,v4,v6,v7,v8,v1到v10的最短路径为v1v4v7v5v8，最短路长度为10。,2,v1,1,v1,0,v1,3,v1,3,v4,6,v7,8,v2,10,v5,反向追踪：v8-v5-v7-v4-v1,