运筹学复习资料

,蒋绍忠 制作,浙江大学 管理学院2005年6月,运筹学复习资料,线性规划的基本概念单纯形法和对偶单纯形法对偶线性规划运输问题网络最小费用流问题网络最大流问题网络最短路径问题动态规划最短路径问题动态规划资源分配问题动态规划背包问题,学而时习之不亦乐乎,线性规划的基本概念,min z=x1+2x2s.t. x1+x24(1) -x1+x21(2) x2 3(3) x1, x2 0,引进松弛变量x3, x4, x5min z=x1+2x2s.t. x1+x2+x3 =4 -x1+x2 -x4=1 x2 +x5=3 x1, x2 x3, x4, x50,基础解,O,A,B,C,D,E,F,G,H,B,C,E,F,B C E F,基础可行解,可行域,目标函数等值线.,最优解,C,A不是可行解，是由于变量（ ） 0。G不是可行解，是由于变量（ ）18 !总产量约束end,LP OPTIMUM FOUND AT STEP 4 OBJECTIVE FUNCTION VALUE 1) 77.00000 VARIABLE VALUE REDUCED COST X1 1.000000 0.000000 X2 17.000000 0.000000 X3 0.000000 10.500000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 2.500000 3) 7.000000 0.000000 4) 100.000000 0.000000 5) 0.000000 -1.000000 NO. ITERATIONS= 4,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 9.000000 INFINITY 1.000000 X2 4.000000 0.500000 INFINITY X3 1.000000 10.500000 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 38.000000 14.000000 2.000000 3 26.000000 INFINITY 7.000000 4 100.000000 100.000000 INFINITY 5 18.000000 1.000000 8.500000,原料是紧缺约束，增加原料供应可以增加利润，边际利润为2.5万元/吨总产量不小于18吨限制了利润增加，减少总产量的限制对增加利润有利产品C不生产，是由于利润太小，利润至少要增加到11.5万元/吨，才有可能安排生产,给出运输问题的初始基础可行解,最小元素法,西北角法,求出各非基变量的检验数,对偶变量法,闭回路法,确定离基变量,确定进基变量,调整运量,运输问题,用最小元素法得到一个初始基础可行解,125,85,180,30,35,75,-7,求非基变量x11的检验数,125,85,180,30,35,75,-7,-8,求非基变量x14的检验数,125,85,180,30,35,75,-7,-8,-4,求非基变量x22的检验数,125,85,180,30,35,75,-7,-8,-6,-7,求非基变量x31的检验数,125,85,180,30,35,75,-7,-8,-4,-7,+1,求非基变量x32的检验数,125,85,180,30,35,75,-7,-8,-4,-7,+1,+4,求非基变量x33的检验数,125,85,180,30,35,75,-7,-8,-6,-7,+1,+4,x33=75进基，x23=0离基，x24=30+75=105，x34=180-75=105,确定进基变量和离基变量,125,85,105,35,-3,求非基变量x11的检验数,125,85,105,35,-3,-4,求非基变量x14的检验数,125,85,105,35,-3,-4,-8,求非基变量x22的检验数,125,85,105,35,-6,-4,-4,-8,求非基变量x23的检验数,125,85,105,35,-5,-4,-4,-7,-8,求非基变量x31的检验数,125,85,105,35,-5,-4,-4,-7,-3,-8,得到最优解：x12=85, x13=35, x21=125, x24=105, x33=75, x34=105 min z = 3660,求非基变量x32的检验数,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,网络最小费用流问题,给出最小费用流问题的初始基础可行解,求出各非基变量的检验数,对偶变量法,闭回路法,确定离基变量,确定进基变量,调整流量,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,找到一个初始的基础可行解生成树,x12=3,x13=6,x35=1,x57=5,x46=8,x67=1,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c35=7,c67=9,c57=8,计算各非基变量的检验数,x12=3,x13=6,x35=1,x57=5,x46=8,x67=1,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c46=5,c13=2,c34=3,c35=7,c67=9,c57=8,计算各非基变量的检验数,x12=3,x13=6,x35=1,x57=5,x46=8,x67=1,z24-c24=(-c46-c67+c54+c35+c13-c12)-c24=-5-9+8+7+2-4-6=-7,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c46=5,c13=2,c45=1,c35=7,c67=9,c57=8,计算各非基变量的检验数，确定进基变量,x12=3,x13=6,x35=1,x57=5,x46=8,x67=1,z24-c24=(-c46-c67+c54+c35+c13-c12)-c24=-5-9+8+7+2-4-6=-7,z34-c34=(-c46-c67+c57+c35)-c34=-5-9+8+7-3=-2,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,确定离基变量,x12=3,x13=6,x35=1,x57=5,x46=8,x67=1,min x67,x46=min1,8=1，x67离基,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,得到新的基础可行解,x12=3,x13=6,x35=1,x57=6,x46=7,x45=1,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,求非基变量x24的检验数,x12=3,x13=6,x35=1,x57=6,x46=7,x45=1,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,x12=3,x13=6,x35=1,x57=6,x46=7,x45=1,求非基变量x34的检验数,z24-c24=(-c45+c35+c13-c12)-c24=-1+7+2-4-6=-2,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,x12=3,x13=6,x35=1,x57=6,x46=7,x45=1,求非基变量x67的检验数，确定进基变量,z24-c24=(-c45+c35+c13-c12)-c24=-1+7+2-4-6=-2,z34-c34=(-c45+c35)-c34=-1+7-3=+3,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,x12=3,x13=6,x35=1,x57=6,x46=7,x45=1,确定离基变量,minx35=1，x35离基,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,x12=3,x13=6,x34=1,x57=6,x46=7,x45=2,得到新的基础可行解,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,x12=3,x13=6,x34=1,x57=6,x46=7,x45=2,分别求非基变量x24 、x35、 x67的检验数,z24-c24=(c34+c13-c12)-c24=3+2-4-6=-5z35-c35=(c45+c34)-c35=1+3-7=-3z67-c67=(c57-c45+c46)-c67=8+1-5-9=-5，获得最优解,1,2,5,4,3,6,7,b1=9,b2=-3,b3=-5,b4=8,b5=4,b6=-7,b7=-6,c12=4,c14=6,c46=5,c13=2,c34=3,c45=1,c35=7,c67=9,c57=8,x12=3,x13=6,x34=1,x57=6,x46=7,x45=2,最优解,最优解如上图所示min z=c12x12+c13x13+c34x34+c45x45+c46x46+c57x57 =(43)+(2 6)+(3 1)+(1 2)+(5 7)+(8 6)=112,1,2,5,4,3,6,7,最大流问题,3,6,11,2,7,4,3,8,4,7,12,5,uij,求从1到7的最大流,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,检查每一条边不饱和的方向，用 表示,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0, =min12, 26, 67=min3,6,12=3 =min13, 35, 57=min11,4,5=4,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 ,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,x=0,=3,=6,=12,=11,=4,=5,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,增加不饱和链的流量检查每一条边不饱和的方向，用 表示,x=3,x=3,x=4,x=0,x=0,x=0,x=0,x=0,x=3,x=4,x=4,x=0,f=7,f=7,寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 ,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,x=3,x=3,x=4,x=0,x=0,x=0,x=0,x=0,x=3,x=4,x=4,x=0,=7,f=7,f=7,=min13, 34, 46 , 67=min7,3,4,8=3,=3,=4,=9,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,增加不饱和链的流量检查每一条边不饱和的方向，用 表示,x=3,x=3,x=7,x=0,x=0,x=3,x=3,x=0,x=6,x=4,x=4,x=0,f=10,f=10,寻找从1到7的不饱和链，用 表示，求出每一条不饱和链的间隙 ,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,x=3,x=3,x=7,x=0,x=0,x=3,x=3,x=0,x=6,x=4,x=4,x=0,f=10,f=10, =min13, 32, 26 , 67=min4,2,3,6=2,=4,=2,=3,=6,增加不饱和链的流量检查每一条边不饱和的方向，用 表示,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,x=3,x=5,x=9,x=2,x=0,x=3,x=3,x=0,x=8,x=4,x=4,x=0,f=12,f=12,寻找从1到7的不饱和链,1,2,5,4,3,6,7,3,6,11,2,7,4,3,8,4,7,12,5,uij,x=3,x=5,x=9,x=2,x=0,x=3,x=3,x=0,x=8,x=4,x=4,x=0,f=12,f=12,已不存在从1到7的不饱和链。获得最大流， f=12X=1,3，X=2,4,5,6,7最小割集为(1,2),(3,2),(3,4),(3,5)，用 表示最小割集的容量为u12+u32+u34+u35=3+2+3+4=12,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,最短路径问题,求1到8的最短路径,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,X=1min0+2,0+6,0+3=min2,6,3=2，w2=2,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,X=1,2min2+9,2+5,2+4,0+6,0+3=min11,7,6,6,3=3，w4=3,w2=2,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X=1,2,4min2+9,2+5,2+4,0+6,3+7,3+6,3+10=min11,7,6,6,10,9,13=6，w3=6,w4=3,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X=1,2,3,4min2+9,2+5,6+8,3+6,3+10=min11,7,14,9,13=7，w6=7,w4=3,w3=6,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X=1,2,3,4,6min2+9,7+4,7+11,3+10=min11,11,18,13=11，w5=11,w4=3,w3=6,w6=7,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X=1,2,3,4,5,6min11+12,7+7,7+11,3+10=min23,14,18,13=13，w7=13,w4=3,w3=6,w6=7,w5=11,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X=1,2,3,4,6,7min11+12,7+7,13+6=min23,14,19=14，w8=14,w4=3,w3=6,w6=7,w5=11,w7=13,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,X=1,2,3,4,6,7,8min11+12,7+7,13+6=min23,14,19=14，w8=14,w4=3,w3=6,w6=7,w5=11,w7=13,w8=14,1,2,3,4,5,6,7,8,2,6,3,9,5,8,4,7,6,10,4,11,7,12,6,w1=0,w2=2,w4=3,w3=6,w6=7,w5=11,w7=13,w8=14,从1到8的最短路径为14，最短路径为12 6 8从1到其他节点的最短路径如上图红线所示，其中到3和5的最短路径有两条。,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,一、最短路径问题,求从A到E的最短路径,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D1)=5,f5(E)=0,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C1)=8,f4(D1)=5,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C2)=7,f4(D1)=5,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f3(C1)=8,f3(C2)=7,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B1)=20,f3(C2)=7,f3(C1)=8,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B2)=14,f3(C2)=7,f3(C1)=8,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f2(B1)=21,f2(B2)=14,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2，C1） C1,2,5,1,12,14,10,6,10,4,13,11,12,3,9,6,5,8,10,5,2,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f4(D2)=2,f5(E)=0,f3(C3)=12,f4(D1)=5,f2(B3)=19,f3(C2)=7,f3(C1)=8,f1(A)=19,f2(B2)=14,f2(B1)=21,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B2） B2 （B2