最新复习运筹学课件胡运权第四版复习要点幻灯片.ppt
第一章 线性规划及单纯形法如何转化为标准形式？如何转化为标准形式？1、目标函数为求极小值，即为： 。njjjxcz1minnjjjxcz1max 因为求 min z 等价于求 max (-z)，令 z = - z，即化为： 2、约束条件为不等式，njinjijbxxa11njijijbxa1njijijbxa1xn+1 0松弛变量如何处理？如何处理？2 线性规划问题的图解法由以上两例分析可得如下重要结论：由以上两例分析可得如下重要结论：1、LP LP 问题从解的角度可分为：问题从解的角度可分为： 有可行解有可行解 无可行解无可行解有唯一最优解有唯一最优解b. 有无穷多最有无穷多最优解优解C. 无最优解无最优解2、LP LP 问题若有最优解，必在可行域的某个顶点上取问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。任一点都是最优解。仍然考虑先前的例子 销地产地B1B2B3B4产量A1 3113107A2 19284A3741059销量3656伏格尔法的步骤如下： 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A37410591销量3656列差额2513 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A374 610591销量3656列差额2513 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A374 6105 392销量3656列差额2513 销地产地B1B2B3B4产量行差额A1 31131070A2 1 392841A374 6105 392销量3656列差额2512 销地产地B1B2B3B4产量行差额A1 3113 5 1077A2 1 392846A374 6105 392销量3656列差额2512 销地产地B1B2B3B4产量行差额A1 3113 5 10 7A2 1 3928 14A374 6105 392销量3656列差额2512 销地产地B1B2B3B4产量A1 3113 510 27A2 1 3 928 14A374 6 105 39销量3656 销地产地B1B2B3B4产量A1 3113 510 27A2 1 3928 14A374 6105 39销量3656例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682v2v3v7v1v8v4v5v66134105275934682(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)v2v3v7v1v8v4v5v66134105275934682(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)v2v3v7v1v8v4v5v66134105275934682（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)v2v3v7v1v8v4v5v66134105275934682(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)V2V3V7V1V8V4V5V66134105275934682(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)v2v3v7v1v8v4v5v66134105275934682(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)v2v3v7v1v8v4v5v66134105275934682(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)v2v3v7v1v8v4v5v66134105275934682(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-v129 结束语结束语
