资源描述
运运 筹筹 学学 Operations Research 第一章 线性规划及单纯形法 运 筹 学 Operations Res第一章线性规划及单纯形法如何转化为标准形式?1、目标函数为求极小值,即为:。因为求 min z 等价于求 max(-z),令 z=-z,即化为:2、约束条件为不等式,xn+1 0松弛变量如何处理?第一章 线性规划及单纯形法如何转化为标准形式?1、目标1 线性规划问题及其数学模型、右端项bi 0时,只需将等式两端同乘(-1)则右端项必大于零4、决策变量无非负约束 设 xj 没有非负约束,若 xj 0,可令 xj=-xj,则 xj 0;又若 xj 为自由变量,即 xj 可为任意实数,可令 xj=xj-xj,且 xj,xj 01 线性规划问题及其数学模型、右端项bi 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 zmax z=x1-2x2+3x4-3x5 s.t.x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70 第一章 线性规划及单纯形法e.g.3试将 LP 问题2 线性规划问题的图解法max z=15x1+25x2s.t.x1+3x2 60 x1+x2 40 x1,x2 0(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数变形:x2=-3/5 x1+z/25x2x1最优解:x1=30 x2=10最优值:zmax=700B点是使z达到最大的唯一可行点2 线性规划问题的图解法max z=15x1+25第一章线性规划及单纯形法LP问题图解法的基本步骤:1、在平面上建立直角坐标系;2、图示约束条件,确定可行域和顶点坐标;3、图示目标函数(等值线)和移动方向;4、寻找最优解。第一章 线性规划及单纯形法LP问题图解法的基本步骤:12 线性规划问题的图解法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 x1x2ox1-1.9 x2=3.8 x1+1.9 x2=3.8x1+1.9 x2=11.4(7.6,2)D0=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)绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.22 线性规划问题的图解法max z=3x1+5.7第一章线性规划及单纯形法max z=2x1+2x2 s.t.2x1 x2 2 -x1+4x2 4 x1,x2 0OA(,0)x1x2Note:可行域为无界区域,目标函数值可无限增大,即解无界。称为无最优解。可行域为无界区域一定无最优解吗?第一章 线性规划及单纯形法max z=2x12 线性规划问题的图解法由以上两例分析可得如下重要结论:1、LP 问题从解的角度可分为:有可行解 无可行解a.有唯一最优解b.有无穷多最优解C.无最优解2、LP 问题若有最优解,必在可行域的某个顶点上取 到;若有两个顶点上同时取到,则这两点的连线上 任一点都是最优解。2 线性规划问题的图解法由以上两例分析可得如下重要结论:13 3:差值法(伏格尔法):差值法(伏格尔法)最小元素法的缺点是:为了节省一处的费用,有时造成其它处要多花几倍的运费。伏最小元素法的缺点是:为了节省一处的费用,有时造成其它处要多花几倍的运费。伏格尔法考虑到,一产地的产品假如不能按最小费用就近供应,就考虑次小费用,这就有格尔法考虑到,一产地的产品假如不能按最小费用就近供应,就考虑次小费用,这就有一个差额,差额越大,说明不按最小运费调运时,运费增加越多。因而对差额最大处,一个差额,差额越大,说明不按最小运费调运时,运费增加越多。因而对差额最大处,就应当采用最小调运方案。就应当采用最小调运方案。基于此,伏格尔法的步骤是:每次从当前运价表上,计算各行各列中最小费用与次基于此,伏格尔法的步骤是:每次从当前运价表上,计算各行各列中最小费用与次小费用这两个运价的差值,优先取最大差值的行或列中最小的运价来确定运输关系,直小费用这两个运价的差值,优先取最大差值的行或列中最小的运价来确定运输关系,直到求出初始方案。到求出初始方案。3:差值法(伏格尔法)仍然考虑先前的例子 销地产地B1B2B3B4产量A1 3113107A2 19284A3741059销量3656伏格尔法的步骤如下:仍然考虑先前的例子 销地B1B2B3B4 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A37410591销量3656列差额2513(1 1)先分别计算出各行各列最小费用与次小费用的差额,并填入该表的最右列和最)先分别计算出各行各列最小费用与次小费用的差额,并填入该表的最右列和最下行。下行。销地B1B2B3B4产量行差额A1 31(2 2)从行差额和列差额中选出最大者,选择它所在的行或列中的最小元素所在的格作为)从行差额和列差额中选出最大者,选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选优先的运输方案。在这里优先选A3A3满足满足B2 6B2 6个单位,个单位,B2B2列已满足,划去列已满足,划去B2B2列。列。销地产地B1B2B3B4产量行差额A1 31131070A2 192841A374 610591销量3656列差额2513(2)从行差额和列差额中选出最大者,选择它所在的行或列中的最(3 3)计算剩余元素的行差额和列差额,并选出最大者,选择它所在的行或列中的最小元)计算剩余元素的行差额和列差额,并选出最大者,选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选素所在的格作为优先的运输方案。在这里优先选A3A3供应供应B4 3B4 3个单位,个单位,A3A3行已满足,划去行已满足,划去A3A3行。行。销地产地B1B2B3B4产量行差额A1 31131070A2 192841A374 6105 392销量3656列差额2513(3)计算剩余元素的行差额和列差额,并选出最大者,选择它所在(4 4)继续进行。在这里优先选)继续进行。在这里优先选A2A2供应供应B1 3B1 3个单位,个单位,B1B1列已满足,划去列已满足,划去B1B1列。列。销地产地B1B2B3B4产量行差额A1 31131070A2 1 392841A374 6105 392销量3656列差额2512(4)继续进行。在这里优先选A2供应B1 3个单位,B1(5 5)继续进行)继续进行 销地产地B1B2B3B4产量行差额A1 3113 5 1077A2 1 392846A374 6105 392销量3656列差额2512(5)继续进行 销地B1B2B3B4产量行(6 6)继续进行)继续进行 销地产地B1B2B3B4产量行差额A1 3113 5 10 7A2 1 3928 14A374 6105 392销量3656列差额2512(6)继续进行 销地B1B2B3B4产量行 销地产地B1B2B3B4产量A1 3113 510 27A2 1 3 928 14A374 6 105 39销量3656(7 7)继续进行得最终结果为:)继续进行得最终结果为:销地B1B2B3B4产量A1 3113(8 8)得到初始方案:)得到初始方案:X X1313=5=5,X X1414=2=2,X X2121=3=3,X X2424=1=1,X X3232=6=6,X X3434=3=3总运费总运费=3*5+10*2+1*3+8*1+4*6+5*3=85=3*5+10*2+1*3+8*1+4*6+5*3=85(元)(元)销地产地B1B2B3B4产量A1 3113 510 27A2 1 3928 14A374 6105 39销量3656(8)得到初始方案:X13=5,X14=2,X21=3,X2例:求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682例:求v1至v8的最短路。v2v3v7v1v8v4v5v66v2v3v7v1v8v4v5v66134105275934682(1)v1:0,v1计算min 0+2,0+1,0+3=min 2,1,3=1 v4:1.v11,v10,v1(2)A=v1检查边(v1,v2),(v1,v4),(v1,v3)v2v3v7v1v8v4v5v661341052759346v2v3v7v1v8v4v5v66134105275934682(3)A=v1,v4计算 min0+2,0+3,1+10,1+2=min 2,3,11,3=2 v2:2,v10,v11,v12,v1考虑边(v1,v2),(v1,v6),(v4,v2),(v4,v7)v2v3v7v1v8v4v5v661341052759346v2v3v7v1v8v4v5v66134105275934682(4)A=v1,v2,v4 计算min 0+3,2+6,2+5,1+2=min 3,8,7,3=3 v6:3,v12,v11,v10,v13,v1考虑边(v1,v6),(v2,v3),(v2,v5),(v4,v7)v2v3v7v1v8v4v5v661341052759346v2v3v7v1v8v4v5v66134105275934682(5)A=V1,V2,V4,V6计算 min 2+6,2+5,1+2,3+4=min 8,7,3,7=3 v7:3,v42,V11,V10,V13,V13,v4考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)v2v3v7v1v8v4v5v661341052759346V2V3V7V1V8V4V5V66134105275934682(6)A=V1,V2,V4,V6,V7计算min 2+6,2+5,3+3,3+8=min 8,7,6,11=6 v5:6,v72,v11,v10,v13,v13,v46,v7考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8)V2V3V7V1V8V4V5V661341052759346v2v3v7v1v8v4v5v66134105275934682(7)A=V1,V2,V4,V6,V7计算min 2+6,6+9,6+4,3+8=min 8,15,10,11=8 v3:8,v22,V11,V10,V13,V13,V46,V78,v2考虑边(v2,v3),(v5,v3),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v661341052759346v2v3v7v1v8v4v5v66134105275934682(8)A=v1,v2,v3,v4,v6,v7 计算 min 8+6,6+4,3+8=min 14,10,11=10 v8:10,v52,v11,v10,v13,v13,v46,v78,v210,v5考虑边(v3,v8),(v5,v8),(v7,v8)v2v3v7v1v8v4v5v661341052759346v2v3v7v1v8v4v5v66134105275934682(9)A=v1,v2,v3,v4,v6,v7,v8v1到v10的最短路径为v1v4v7v5v8,最短路长度为10。2,v11,v10,v13,v13,v46,v78,v210,v5反向追踪:v8-v5-v7-v4-v1v2v3v7v1v8v4v5v661341052759346
展开阅读全文