建筑钢结构全部图片

复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点1第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。因为求minz等价于求max(-z)，令z’=-z，即化为：

2、约束条件为不等式，xn+1≥0松弛变量如何处理？第一章线性规划及单纯形法如何转化为标准形式？1、目标2§1线性规划问题及其数学模型

３、右端项bi<0时，只需将等式两端同乘（-1）则右端项必大于零

4、决策变量无非负约束

设xj

没有非负约束，若xj≤0，可令xj=-xj’，则xj’≥0；

又若xj为自由变量，即xj可为任意实数，可令xj=xj’-xj’’，且xj’,xj’’≥0§1线性规划问题及其数学模型３、右端项bi<0时，只3第一章线性规划及单纯形法e.g.3试将LP问题minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0化为标准形式。解：令x3=x4-x5

其中x4、x5

≥0；对第一个约束条件加上松弛变量x6；对第二个约束条件减去松弛变量x7；对第三个约束条件两边乘以“-1”；令z’=-z把求minz改为求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

第一章线性规划及单纯形法e.g.3试将LP问题4§2线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数变形：x2=-3/5

x1+z/25x2x1最优解：

x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点§2线性规划问题的图解法maxz=15x1+255第一章线性规划及单纯形法LP问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。第一章线性规划及单纯形法LP问题图解法的基本步骤：16§2线性规划问题的图解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1

，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2§2线性规划问题的图解法maxz=3x1+5.77第一章线性规划及单纯形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？第一章线性规划及单纯形法maxz=2x18§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴有可行解⑵无可行解有唯一最优解b.有无穷多最优解C.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。§2线性规划问题的图解法由以上两例分析可得如下重要结论：193：差值法（伏格尔法）

最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小费用就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小调运方案。基于此，伏格尔法的步骤是：每次从当前运价表上，计算各行各列中最小费用与次小费用这两个运价的差值，优先取最大差值的行或列中最小的运价来确定运输关系，直到求出初始方案。3：差值法（伏格尔法）10仍然考虑先前的例子

销地产地B1B2B3B4产量A13113107A219284A3741059销量3656伏格尔法的步骤如下：

仍然考虑先前的例子

销地B1B2B3B411销地产地B1B2B3B4产量行差额A131131070A2192841A37410591销量3656列差额2513（1）先分别计算出各行各列最小费用与次小费用的差额，并填入该表的最右列和最下行。销地B1B2B3B4产量行差额A13112（2）从行差额和列差额中选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3满足B26个单位，B2列已满足，划去B2列。销地产地B1B2B3B4产量行差额A131131070A2192841A374610591销量3656列差额2513（2）从行差额和列差额中选出最大者，选择它所在的行或列中的最13（3）计算剩余元素的行差额和列差额，并选出最大者，选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选A3供应B43个单位，A3行已满足，划去A3行。销地产地B1B2B3B4产量行差额A131131070A2192841A3746105392销量3656列差额2513（3）计算剩余元素的行差额和列差额，并选出最大者，选择它所在14（4）继续进行。在这里优先选A2供应B13个单位，B1列已满足，划去B1列。销地产地B1B2B3B4产量行差额A131131070A21392841A3746105392销量3656列差额2512（4）继续进行。在这里优先选A2供应B13个单位，B115（5）继续进行销地产地B1B2B3B4产量行差额A1311351077A21392846A3746105392销量3656列差额2512（5）继续进行销地B1B2B3B4产量行16（6）继续进行销地产地B1B2B3B4产量行差额A131135107A21392814A3746105392销量3656列差额2512（6）继续进行销地B1B2B3B4产量行17销地产地B1B2B3B4产量A1311351027A21392814A374610539销量3656（7）继续进行得最终结果为：销地B1B2B3B4产量A1311318（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（元）销地产地B1B2B3B4产量A1311351027A21392814A374610539销量3656（8）得到初始方案：X13=5，X14=2，X21=3，X219例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682例：求v1至v8的最短路。v2v3v7v1v8v4v5v6620v2v3v7v1v8v4v5v66134105275934682(1)v1:[0,v1]计算min{0+2,0+1,0+3}=min{2,1,3}=1v4:[1.v1][1,v1][0,v1](2)A={v1}检查边（v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v66134105275934621v2v3v7v1v8v4v5v66134105275934682(3)A={v1,v4}计算min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2v2:[2,v1][0,v1][1,v1][2,v1]考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v66134105275934622v2v3v7v1v8v4v5v66134105275934682（4）A={v1,v2,v4}计算min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3v6:[3,v1][2,v1][1,v1][0,v1][3,v1]考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v66134105275934623v2v3v7v1v8v4v5v66134105275934682(5)A={V1,V2,V4,V6}计算min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3v7:[3,v4][2，V1][1，V1][0，V1][3，V1][3,v4]考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)v2v3v7v1v8v4v5v66134105275934624V2V3V7V1V8V4V5V66134105275934682(6)A={V1,V2,V4,V6,V7}计算min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6v5:[6,v7][2,v1][1,v1][0,v1][3,v1][3,v4][6,v7]考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8)V2V3V7V1V8V4V5V66134105275934625v2v3v7v1v8v4v5v66134105275934682(7)A={V1,V2,V4,V6,V7}计算min{2+6,6+9,6+4,3+8}=m