运筹与决策复习题.doc

复 习 课x3=0x2=0x2x4=0-3 -2 -1 0 1 2 3 4 5 6654321ABCDEFGHJIx1x1=0x5=0一、 对于以下线性规划问题minz=-x1+2x22x1+3x212(1)3x1+x26(2)-x1+3x23(3)x1x20三个约束对应的松弛变量分别为x3，x4，x5；三个约束条件对应的对偶变量分别为w1，w2，w3。这个问题可行域为（EFHI）；这个问题最优解为（F）；这个问题基础解为（ABCDEFGHIJ）；这个问题基础可行解为（EFHI）；G点对应的解中，大于0的变量为（x1,x2），等于0的变量为（x3,x5），小于0的变量为（x4）；E点对应的基变量为（x2,x3,x4），非基变量为（x1,x5）；D点对应的基变量为（x1,x3,x4），非基变量为（x2,x5）；从E到F的单纯形叠代，进基变量为（x1），离基变量为（x4）；*F点对应的对偶变量，大于0的是（w3），等于0的是（w1,w4,w5），小于0的是（w2）。二、对于以上线性规划问题（1）写出以上问题的对偶问题；（2）用单纯形表求出这个问题和它的对偶问题的最优解。原料消耗（吨/件）产品A产品B产品C原料限量（吨）原料甲128102400原料乙610151500原料丙15181800原料丁20222000产品利润（万元/件）120180210三、一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料数量（表中“”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如右表所示。1、写出原料限制条件下利润最大化的线性规划模型；2、写出以上问题的对偶问题；3、已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格（写出单位）；4、分别计算三种产品的机会成本（写出单位）；5、产品B对原料乙的消耗系数（10吨/件）降低到多少，产品B在最优解中才能安排生产？四、对于以下运输问题运价（元/吨）B1B2B3B4供应量（吨）A1912108240A214761180A35131520180需求量（吨）90120130160（1） 求总运费最小的运输方案（2） 求c11=9在什么范围内变化，最优解保持不变；（3） 求c23=6在什么范围内变化，最优解保持不变。五、求以下网络的最小费用流 b1=5 c15=5 b5=2 1 5 c13=2 c54=3 b3=4 b4=-2 c12=3 3 4 c65=2 c34=0 c23=1 c46=5 2 6 b2=-3 c26=3 b6=-6六、求以下网络的最大流和最小割集234567818546432231963uij七、最短路径问题67851011129234134762514863724198八、动态规划资源分配问题有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）的关系见下表：效益（万吨）项 目ABC投入资金（万元）125万吨18万吨13万吨232万吨33万吨32万吨338万吨45万吨48万吨443万元54万元62万元求对三个项目的最优投资分配，使总投资效益最大。九、动态规划背包问题有5万元资金,用于购买3种设备,每种设备的单台价格和单台生产能力见下表：设 备ABC价格pk（万元/台）213生产能力qk（万吨/台）231131三种设备应各购买多少台，使总的生产能力最大？解答二、minz=-x1+2x22x1+3x2123x1+x26-x1+3x23x1x20引进松弛变量minz=-x1+2x22x1+3x2+x3=123x1+x2+x4=6-x1+3x2-x5=3x1x2x3x4x50第三个约束两边乘以-1minz=-x1+2x22x1+3x2+x3=123x1+x2+x4=6x1-3x2+x5=-3x1x2x3x4x50列出单纯形表zx1x2x3x4x5RHSz11-20000x302310012x40310106x501-3001-3先解决原始可行性，用对偶单纯形法，x5离基，x2进基zx1x2x3x4x5RHSz11/3000-2/32x303010199/3x4010/30011/3515/10x20-1/3100-1/31再解决对偶可行性，用单纯形法，x1进基，x4离基zx1x2x3x4x5RHSz11/3000-2/32x30301019x401/3001/101/301/2x20-1/3100-1/31zx1x2x3x4x5RHSz1000-1/10-7/103/2x30001-9/107/109/2x401/3001/101/301/2x200101/10-3/103/2zx1x2x3x4x5RHSz1000-1/10-7/103/2x30001-9/107/109/2x101003/101/103/2x200101/10-3/103/2得到最优解：（x1，x2，x3，x4，x5）=（3/2，3/2，9/2，0，0），min z=3/2对偶问题的最优解为（w1，w2，w3，w4，w5）=（0，-1/10，7/10，0，0），max y=3/2三、1、maxz=120x1+180x2+210x3s.t.12x1+8x2+10x324006x1+10x2+15x3150015x1+18x2180020x2+22x32000x10x20x302、对偶问题为miny=2400w1+1500w2+1800w3+2000w4s.t.12w1+6w2+15w31208w1+10w2+18w3+20w418010w1+15w2+22w4210w1w2w3w403、maxz=120x1+180x2+210x3s.t.12x1+8x2+10x3+x4=24006x1+10x2+15x3+x5=150015x1+18x2+x6=180020x2+22x3+x7=2000x1x2x3x4x5x6x70x4=2400-(12x1+8x2+10x3)=2400-(1440+0+520)=2400-1960=440x5=1500-(6x1+10x2+15x3)=1500-(720+0+780)=1500-1500=0x6=1800-(15x1+18x2)=1800-(1800+0)=1800-1800=0x7=2000-(20x2+22x3)=2000-(0+1144)=856miny=2400w1+1500w2+1800w3+2000w4s.t.12w1+6w2+15w3-w5=1208w1+10w2+18w3+20w4-w6=18010w1+15w2+22w4-w7=210w1w2w3w4w5w6w70x1w5=0，x2w6=0，x3w7=0，x4w1=0，x5w2=0，x6w3=0，x7w4=0由x1，x3，x4，x70，得到w5=w7=w1=w4=06w2+15w3=12010w2+18w3-w6=18015w2=210解得w2=14，w3=2.4，w6=3.2原料甲的影子价格为：0万元/吨；原料乙的影子价格为：14万元/吨；原料丙的影子价格为：2.4万元/吨；原料丁的影子价格为：0万元/吨；4、 产品A的机会成本为：12w1+6w2+15w3=120+614+152.4=120（万元/件）产品B的机会成本为：8w1+10w2+18w3+20w4=80+1014+182.4+200=183.2（万元/件）产品B的机会成本为：10w1+15w2+22w4=100+1514+220=210（万元/件）5、（180-182.4）14=9.77，即消耗系数下降到9.77吨/件，B产品在最优解中将会投入生产。四、用最小元素法得到初始基础可行解B1B2B3B4A1912108240-53050160A214761180-14+180-7A351315201809090-4-1190120130160x22进基，x12离基B1B2B3B4A1912108240-6-180160A214761180-153050-7A351315201809090-3-1090120130160最优解。最优解为：x11=0，x12=0，x13=80，x14=160x21=0，x22=30，x23=50，x24=0x31=90，x32=90，x33=0，x34=0。min z=4216五、求以下网络的最小费用流 b1=5 c15=5 b5=2 1 5 c13=2 c54=3 b3=4 b4=-2 c12=3 3 4 c65=2 c34=0 c23=1 c46=5 2 6 b2=-3 c26=3 b6=-6 b1=5 b5=2 1 5 x13=2 x54=2 b3=4 b4=-2 x12=3 3 4 c65=2 x34=6 x46=6 2 6 b2=-3 b6=-6确定一个初始的基础可行解，计算各非基变量的检验数：z15-c15=(-c54+c34+c13)-c15=(-3+0+2)-5=-6z23-c23=(c13-c12)-c23=(2-3)-1=-2z26-c26=(c46+c34+c13-c12)-c26=(5+0+2-3)-3=+1z65-c65=(-c54-c46)-c65=(-3-5)-2=-10（2，6）进基，当x26=2时，x13=0离基。 b1=5 b5=2 1 5 x54=2 b3=4 b4=-2 x12=5 3 4 c65=2 x34=4 x46=4 2 6 b2=-3 x26=2 b6=-6z15-c15=(-c54-c45+c26+c12)-c15=(-3-5+3+3)-5=-7z23-c23=(-c34-c46+c26)-c23=(-0-5+3)-1=-3z13-c13=(-c34-c46+c26+c12)-c13=(-0-5+3+3)-2=-1z65-c65=(-c54-c46)-c65=(-3-5)-2=-10已获得最优解。最优解为：x12=5，x26=2，x34=4，x46=4，x54=2，其余xij=0。min z=35+32+04+54+32=47。六、流量xij间隙Dij和不饱和链2345678179464368311045uij2345678179464368311045Dij不饱和链（1,2,5,8），间隙为min(7,6,10)=6不饱和链（1,3,6,8），间隙为min(9,6,4)=4不饱和链（1,4,7,8），间隙为min(4,8,5)=423456781154432431444Dij66144234567817944368311045uijx=6x=6x=6f=14x=4x=4x=4f=14x=4x=4x=4不饱和链（1,3,6,5,8），间隙为min(5,2,3,4)=26234567817944368311045uijx=6x=6x=8f=16x=6x=6x=4f=16x=4x=4x=4x=2644623456781134643411244Dij681662已不存在从1到8的不饱和链，得到最大流234567817944368311045uijx=6x=6x=8f=16x=6x=6x=4f=16x=4x=4x=4x=26最大流为f=16X=1，2，3，=4，5，6，7，8最小割集（X，）=（1，4），（2，5），（3，6）最小割集的容量为：u14+u25+u36=6+6+4=16七、求以下网络从1到8的最短路径w12=0w11=0w10=0w9=0w8=0w7=0w6=0w5=0w4=0w3=0w2=0w1=04273684152674314329121110587X=16981min(0+3,0+6)=3,w2=3X=1,267851011129234134762514863724w1=0w2=3w3=0w4=0w5=0w6=0w7=0w8=0w9=0w10=0w11=0w12=0198min(0+6,3+4,3+2)=5,w6=5X=1,2,66785101112923413474863724w1=0w2=3w3=0w4=0w5=0w6=5w7=0w8=0w9=0w10=0w11=0w12=01986251min(0+6,3+4,5+9)=6,w5=6X=1,2,5,667851011129234134762514863724w1=0w2=3w3=0w4=0w5=6w6=5w7=0w8=0w9=0w10=0w11=0w12=0198min(6+4,3+4,5+9)=7w3=7,X=1,2,3,5,667851011129234162514863724w5=6w6=5w7=0w8=0w9=0w10=0w11=0w12=0198347w1=0w2=3w3=7w4=0min(6+4,7+7,5+9)=10,w9=10,X=1,2,3,5,6,967851011129234134762514863724w1=0w2=3w3=7w4=0w5=6w6=5w7=0w8=0w9=10w10=0w11=0w12=0198min(7+7,5+9,10+7)=14w4=14,X=1,2,3,4,5,6,967851011129234134762514863724w1=0w2=3w3=7w4=14w5=6w6=5w7=0w8=0w9=10w10=0w11=0w12=0198min(14+1,5+9,10+7)=14,w7=14X=1,2,3,4,5,6,7,967851011129234134762514863724w1=0w2=3w3=7w4=14w5=6w6=5w7=14w8=0w9=10w10=0w11=0w12=0198min(14+1,14+8,14+6,10+7)=15,w8=15,X=1,2,3,4,5,6,7,8,967851011129234162514863724w5=6w6=5w7=14w8=15w9=10w10=0w11=0w12=0198w1=0w2=3w3=7w4=14min(10+7,14+6,15+3)=17,w10=17,X=1,2,3,4,5,6,7,8,9,1067851011129234134762514863724w1=0w2=3w3=7w4=14w5=6w6=5w7=14w8=15w9=10w10=17w11=0w12=0198min(17+2,14+6,15+3)=18,w12=18,X=1,2,3,4,5,6,7,8,9,10,1267851011129234134762514863724w1=0w2=3w3=7w4=14w5=6w6=5w7=14w8=15w9=10w10=17w11=0w12=18198min(14+6,17+2)=19,w11=19,X=1,2,3,4,5,6,7,8,9,10,11,1267851011129234134762514863724w1=0w2=3w3=7w4=14w5=6w6=5w7=14w8=15w9=10w10=17w11=19w12=18198获得最优解。从1到12的最短路径长度为12，路径为1-2-3-4-8-12。从1到其他各点的最短路径如图所示。八、动态规划资源分配问题有资金4万元，投资A、B、C三个项目，每个项目的投资效益与投入该项目的资金有关。三个项目A、B、C的投资效益（万吨）和投入资金（万元）的关系见下表：效益（万吨）项 目ABC投入资金（万元）125万吨18万吨13万吨232万吨33万吨32万吨338万吨45万吨48万吨443万元54万元62万元求对三个项目的最优投资分配，使总投资效益最大。这是一个资源分配问题。阶段k：每投资一个项目作为一个阶段；状态变量xk：投资第k个项目前的资金数；决策变量dk：第k个项目的投资；决策允许集合：0dkxk状态转移方程：xk+1=xk-dk阶段指标：vk(xk,dk)见表中所示；递推方程：fk(xk)=maxvk(xk,dk)+fk+1(xk+1)终端条件：f4(x4)=0k=4，f4(x4)=0k=3，0d3x3，x4=x3-d3x3D3(x3)x4v3(x3,d3)v3(x3,d3)+f4(x4)f3(x3)d3*00000+0=00010100+0=0131101313+0=13*20200+0=0322111311+0=11203232+0=32*30300+0=0483121313+0=13213232+0=32304848+0=48*40400+0=0624131313+0=13223232+0=32314848+0=48406262+0=62*k=2，0d2x2，x3=x2-d2x2D2(x2)x3v2(x2,d2)v2(x2,d2)+f3(x3)f2(x2)d2*00000+0=00010100+130=18*20200+32=32*320或1111818+13=32*203333+0=2930300+48=48501121818+32=50*213333+13=46304545+0=4540400+62=62652131818+48=56223333+32=65*314545+13=58405454+0=54k=1，0d1x1，x2=x1-d1x1D1(x1)x2v1(x1,d1)v1(x1,d1)+f2(x2)f1(x1)d1*40400+65=65751132525+50=75*223232+32=64313838+18=56404343+0=43最优解为x1=4, d1*=1, x2=x1-d1=3, d2*=1, x3=x2-d2*=2, d3*=2, x4=x3-d3*=0，即项目A投资1万元，项目B投资1万元，项目C投资2万元，最大效益为75万吨。九、动态规划背包问题有5万元资金,用于购买3种设备,每种设备的单台价格和单台生产能力见下表：设 备ABC价格pk（万元/台）213生产能力qk（万吨/台）231131三种设备应各购买多少台，使总的生产能力最大？这是一个背包问题。阶段k：每购买一种设备作为一个阶段，k=1,2,3,4；状态变量xk：购买第k种设备以前的