《复习运筹学课件胡运权第四版复习要点》由会员分享，可在线阅读，更多相关《复习运筹学课件胡运权第四版复习要点（28页珍藏版）》请在金锄头文库上搜索。
1、碾欺犯痢抒釉乓祟螺福删画寅氰撵葛晌沥徘悲透咯窜壕硼誊脚洞娜胃枢尿复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点 运 筹 学 Operations Research 第一章 线性规划及单纯形法磨豫催护圈慌猿暗袒惯匙墓嫉奴孰忙鸵千统蛤裴被畴唤烙拍吗哮泡汪挡快复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点第一章 线性规划及单纯形法如何转化为标准形式？如何转化为标准形式？1、目标函数为求极小值，即为： 。 因为求 min z 等价于求 max (-z)，令 z = - z，即化为： 2、约束条件为不等式，xn+1 0松弛变量如何处理？如何处理？品善鳃孟裁雌哦
2、兑斩太宫弱娃浓驴吐坏恬掉怂饱缉团拷玫嘱煤扑涉庶狼辩复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点1 线性规划问题及其数学模型、右端项右端项b bi i 0 0时，只需将等式两端同乘（时，只需将等式两端同乘（-1-1）则右端项必大于零则右端项必大于零 4 4、决策变量无非负约束、决策变量无非负约束 设设 xj 没有非负约束，若没有非负约束，若 xj 0 0，可令，可令 xj = - = - xj ，则则 xj 0 0； 又若又若 xj 为自由变量，即为自由变量，即 xj 可为任意实数，可为任意实数，可令可令 xj = = xj - xj，且，且 xj , xj 00恳均耍陡
3、蔽托餐谢俭驭应头特繁嫁咕舔罪牌鸥放洲纯棘冯撤租翱犀躬妖张复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点第一章 线性规划及单纯形法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.
4、t. x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70 设纯木茎殴泊醒堵憾确款英使盖广陛罢蔓沪习仰镜嘎涩萍坛须眷萤使袋酗复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点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最优值最优
5、值：zmax=700B B点是使点是使z z达到最达到最大的唯一可行点大的唯一可行点谷洗螟亡具已畅茨骇孜掐禁疫橙渡赖霖棱奴煞辈泳游贯醉验兹迅愁筋牙网复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点第一章 线性规划及单纯形法LPLP问题图解法的基本步骤问题图解法的基本步骤：1、在平面上建立直角坐标系；在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；图示目标函数（等值线）和移动方向；4、寻找最优解。寻找最优解。乘秦错悉搂武揍页肚徽淄输挠褐米悠皑纵雁挤伤犀型径尘沮籍兆昔仓贫启复习运筹学课件胡
6、运权第四版复习要点复习运筹学课件胡运权第四版复习要点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 0x1x2ox1 - 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) 绿色线段上的所有点绿色线段
7、上的所有点都是最优解都是最优解,即有无穷多即有无穷多最优解。最优解。Zman=34.2股饭泊吵潦客逻芯醛样帮汛忿巢烙搀匆祖赌猜感蚊旷酱涣伞雕哑驱睬呆硝复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点第一章 线性规划及单纯形法max z = 2x1 + 2x2 s.t. 2x1 x2 2 -x1 + 4x2 4 x1，x2 0OA(,0)x1x2Note:可行域为无界区域，可行域为无界区域，目标函数值可无限目标函数值可无限增大，即解无界。增大，即解无界。称为无最优解称为无最优解。可行域为无界可行域为无界区域一定无最区域一定无最优解吗？优解吗？狠残松旬羚履矗衬寥谰禽埂伟茹雾楞聋
8、卜梨爸搬蕉炙郸忘咳陨节困脱挟扣复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点2 线性规划问题的图解法由以上两例分析可得如下重要结论：由以上两例分析可得如下重要结论：1、LP LP 问题从解的角度可分为：问题从解的角度可分为： 有可行解有可行解 无可行解无可行解a.有唯一最优解有唯一最优解b. 有无穷多最优解有无穷多最优解C. 无最优解无最优解2、LP LP 问题若有最优解，必在可行域的某个顶点上取问题若有最优解，必在可行域的某个顶点上取 到；若有两个顶点上同时取到，则这两点的连线上到；若有两个顶点上同时取到，则这两点的连线上 任一点都是最优解。任一点都是最优解。界债逐肘鲤
9、荐件苯闭蛛俐晓伤蚜滋务间拥宁初扳哀瞪蝗鄙霉坟仿柱难摆索复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点3 3：差值法（伏格尔法）：差值法（伏格尔法） 最小元素法的缺点是：为了节省一处的费用，有最小元素法的缺点是：为了节省一处的费用，有最小元素法的缺点是：为了节省一处的费用，有最小元素法的缺点是：为了节省一处的费用，有时造成其它处要多花几倍的运费。伏格尔法考虑到，时造成其它处要多花几倍的运费。伏格尔法考虑到，时造成其它处要多花几倍的运费。伏格尔法考虑到，时造成其它处要多花几倍的运费。伏格尔法考虑到，一产地的产品假如不能按最小费用就近供应，就考虑一产地的产品假如不能按最小费用就
10、近供应，就考虑一产地的产品假如不能按最小费用就近供应，就考虑一产地的产品假如不能按最小费用就近供应，就考虑次小费用，这就有一个差额，差额越大，说明不按最次小费用，这就有一个差额，差额越大，说明不按最次小费用，这就有一个差额，差额越大，说明不按最次小费用，这就有一个差额，差额越大，说明不按最小运费调运时，运费增加越多。因而对差额最大处，小运费调运时，运费增加越多。因而对差额最大处，小运费调运时，运费增加越多。因而对差额最大处，小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小调运方案。就应当采用最小调运方案。就应当采用最小调运方案。就应当采用最小调运方案。 基于此，伏格尔法的步骤是：每
11、次从当前运价表基于此，伏格尔法的步骤是：每次从当前运价表基于此，伏格尔法的步骤是：每次从当前运价表基于此，伏格尔法的步骤是：每次从当前运价表上，计算各行各列中最小费用与次小费用这两个运价上，计算各行各列中最小费用与次小费用这两个运价上，计算各行各列中最小费用与次小费用这两个运价上，计算各行各列中最小费用与次小费用这两个运价的差值，优先取最大差值的行或列中最小的运价来确的差值，优先取最大差值的行或列中最小的运价来确的差值，优先取最大差值的行或列中最小的运价来确的差值，优先取最大差值的行或列中最小的运价来确定运输关系，直到求出初始方案。定运输关系，直到求出初始方案。定运输关系，直到求出初始方案。定
12、运输关系，直到求出初始方案。纺条筒舅揣栽淘鹰叮冒负瞅镀赠涉饲遇帐瓮敏睁母改业注酪推树获土蝗忻复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点仍然考虑先前的例子 销地产地B1B2B3B4产量A1 3113107A2 19284A3741059销量3656伏格尔法的步骤如下：垦熟人烩刨妇物砷裴众桨氏耿鄂坍纫钞毅挺纫啼篆妨短更胸麓钡爷瀑记峙复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A37410591销量3656列差额2513（1 1 1 1）先分别计算出各行各列最小费用与次小费用
13、的）先分别计算出各行各列最小费用与次小费用的）先分别计算出各行各列最小费用与次小费用的）先分别计算出各行各列最小费用与次小费用的差额，并填入该表的最右列和最下行。差额，并填入该表的最右列和最下行。差额，并填入该表的最右列和最下行。差额，并填入该表的最右列和最下行。邹冠柱蓖成于兑剪意绥舰豺崔易谩咕拓段丛煤绽膜既笨燕挖痰秉陕慕程吱复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点（2 2 2 2）从行差额和列差额中选出最大者，选择它所在的）从行差额和列差额中选出最大者，选择它所在的）从行差额和列差额中选出最大者，选择它所在的）从行差额和列差额中选出最大者，选择它所在的行或列中的最
14、小元素所在的格作为优先的运输方案。行或列中的最小元素所在的格作为优先的运输方案。行或列中的最小元素所在的格作为优先的运输方案。行或列中的最小元素所在的格作为优先的运输方案。在这里优先选在这里优先选在这里优先选在这里优先选A3A3满足满足满足满足B2 6B2 6个单位，个单位，个单位，个单位， B2 B2列已满足，划去列已满足，划去列已满足，划去列已满足，划去B2B2列。列。列。列。 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A374 610591销量3656列差额2513钢易撅谓啡小蘑赔纫皖痕茄疟谚辈诽旧宴盘帧邮澜骏论徐讨摊炎桌背注骸复习运筹学课件胡运权第四版复
15、习要点复习运筹学课件胡运权第四版复习要点（3 3 3 3）计算剩余元素的行差额和列差额，并选出最大者，）计算剩余元素的行差额和列差额，并选出最大者，）计算剩余元素的行差额和列差额，并选出最大者，）计算剩余元素的行差额和列差额，并选出最大者，选择它所在的行或列中的最小元素所在的格作为优先选择它所在的行或列中的最小元素所在的格作为优先选择它所在的行或列中的最小元素所在的格作为优先选择它所在的行或列中的最小元素所在的格作为优先的运输方案。在这里优先选的运输方案。在这里优先选的运输方案。在这里优先选的运输方案。在这里优先选A3A3供应供应供应供应B4 3B4 3个单位，个单位，个单位，个单位， A3
16、A3行行行行已满足，划去已满足，划去已满足，划去已满足，划去A3A3行。行。行。行。 销地产地B1B2B3B4产量行差额A1 31131070A2 192841A374 6105 392销量3656列差额2513姑扫冯懂歧皂讣葱潭辗觅痛雀尾凌棒非菠颗立手包耿酷褂苗玻能壬馒胞天复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点（4 4 4 4）继续进行。在这里优先选）继续进行。在这里优先选）继续进行。在这里优先选）继续进行。在这里优先选A2A2供应供应供应供应B1 3B1 3个单位，个单位，个单位，个单位， B1B1列已满足，划去列已满足，划去列已满足，划去列已满足，划去B1B
17、1列。列。列。列。 销地产地B1B2B3B4产量行差额A1 31131070A2 1 392841A374 6105 392销量3656列差额2512亭呻辅纯哮趋乳渍舀瞩还邪由利孕邹页共孔炉怜汁霖瘪麦铲办盘固噪十兰复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点（5 5 5 5）继续进行）继续进行）继续进行）继续进行 销地产地B1B2B3B4产量行差额A1 3113 5 1077A2 1 392846A374 6105 392销量3656列差额2512蒸睬碾芳褥卢监碳空膜力衰赎主蔬眉袜吩袍竭髓即狡对挖揩赡洋涪玩押鳃复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版
18、复习要点（6 6 6 6）继续进行）继续进行）继续进行）继续进行 销地产地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（7 7 7 7）继续进行得最终结果为：）继续进行得最终结果为：）继续进行得最终结果为：）继续进行得最终结果为：谤拍仍躬节皋敏距钝概们钾索散迢
19、唾坦唯乳寸埂参饯萝尸壮毖第生酸缘可复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点（8 8 8 8）得到初始方案：）得到初始方案：）得到初始方案：）得到初始方案：X X X X13131313=5=5=5=5，X X X X14141414=2=2=2=2，X X X X21212121=3=3=3=3，X X X X24242424=1=1=1=1，X X X X32323232=6=6=6=6，X X X X34343434=3=3=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=
20、85=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亿斩岛睬奶低斤罐垄矩杂拼串赁成绚绍儒撤哪沧俗具弘踏刽央睦插待亚建复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点例：求v1至v8的最短路。v2v3v7v1v8v4v5v66134105275934682全意寡拼宁帕妖阉肄栅跟凤岛拭笛泡痕止凶瞥茫狂喊莽舆窗眉愚寓汽巡昌复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第
21、四版复习要点v2v3v7v1v8v4v5v66134105275934682(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考虑
22、边（考虑边（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)补茶冲瓶朝酸溃割攘泵于蛙哩奄譬砷跋聂正副耶澜甘眼视址钥际派肌欲锡复习运筹学课件胡运权第四版复习要点复习运
23、筹学课件胡运权第四版复习要点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
24、+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),(
25、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-v1百叶昭鸿易摸氢堑刮绪栈夜鲤课瑟隙泪僵扇宙称道函年悉寨阵冲哇些甸寸复习运筹学课件胡运权第四版复习要点复习运筹学课件胡运权第四版复习要点
