运筹与优化复习题(含答案)

运筹学（OperationsResearch）复习题答案一.用图解法求解下列线性规划问题。并说明是唯一最优解，无穷多最优解，无界解还是无可行解。2,1,041102..3max2212121jxxxxxxtsxxzj1.一.用图解法求解下列线性规划问题。并说明是唯一最优解，无穷多最优解，无界解还是无可行解。2,1,0242..max212121jxxxxxtsxxzj2.3,2,1,06214222max21321321jxxxxxxxxxzj二.已知线性规划问题:1.用单纯形法求解；2.写出其对偶规划；并根据对偶理论，直接写出对偶规划的最优解；3.试做如下灵敏度分析：(1)当b1由14变为10时，最优解有何变化？(2)最优基不变的情况下，△b2的变化范围？(3)当c1由1变为10时，最优解有何变化？(4)当p2由变为时，最优解有何变化？2132cj1-2-100iCBXBbx1x2x3x4x50x41421-2100x56120011-2-10-2j5,,1,06214222max5214321321jxxxxxxxxxxxzj76【】cj1-2-100iCBXBbx1x2x3x4x50x420-3-21-21x16120010-4-10-1j最优单纯形表1.标准形：最优解x*=(6,0,0)T,最优值z*=6×1=62.原问题:3,2,1,06214222max21321321jxxxxxxxxxzj对偶问题:2,1,0122212614min1212121jyyyyyyyywj根据对偶理论，对偶规划的最优解为Y*=(0,1)。3(1).当b1由14变为10时，最优解有何变化？6261010211bBXBcj1-2-100iCBXBbx1x2x3x4x50x420-3-21-21x16120010-4-10-1j原最优单纯形表-2用对偶单纯法4/31/21/2【】cj1-2-100iCBXBbx1x2x3x4x5-1x3103/21-1/211x16120010-5/20-1/20j新最优单纯形表最优解变为x*=(6,0,1)T,最优值变为z*=5cj1-2-100iCBXBbx1x2x3x4x50x420-3-21-21x16120010-4-10-1j原最优单纯形表(2)最优基不变的情况下，△b2的变化范围？0062261410212221bbbbBXB162bcj1-2-100iCBXBbx1x2x3x4x50x420-3-21-21x16120010-4-10-1j原最优单纯形表(3)当c1由1变为2时，最优解有何变化？622)3(02222-6102)2(013-1212)2(005-2仍是最优单纯形表000所以最优解不变。(4)当p2由变为时，最优解有何变化？3432102121pB1)3(14022-2x21/201-1/21/4-1/21x115/210-3/23/4-1/200-1/2-1/4-1/2jcj1-2-100iCBXBbx1x2x3x4x50x420-3-21-21x16120010-4-10-1j-3411/2-【4】原最优单纯形表用单纯形法最优解变为x*=(15/2,1/2,0)T,最优值变为z*=13/2.2132三.已知线性规划问题:1.用大M法求解；2.写出其对偶规划；3.试做如下灵敏度分析：(1)当b2由2变为11时，最优解有何变化？(2)最优基不变的情况下，△c1的变化范围？(3)当p2由变为时，最优解有何变化？12413,2,1,0228232max321321321jxxxxxxxxxxzj1.标准形：6,,1,0228232max53214321321jxxxxxxxxxxxxzj大M规划：6,,1,0228232max5321643216321jxxxxxxxxxxMxxxxzj大M规划：cj-2-3-100-MiCBXBbx1x2x3x4x5x6-Mx68121-1010x52-211010-2+M-3+2M-1+M-M00jcj-2-3-100-MiCBXBbx1x2x3x4x5x6-Mx6450-1-1-21-3x22-211010-8+5M02-M-M3-2M0j42【】6,,1,0228232max5321643216321jxxxxxxxxxxMxxxxzj4/5-【】cj-2-3-100-MiCBXBbx1x2x3x4x5x6-2x14/510-1/5-1/5-2/51/5-3x218/5013/5-2/51/52/5002/5-8/5-1/5-M+8/5j6-【】最优单纯形表cj-2-3-100-MiCBXBbx1x2x3x4x5x6-2x1211/30-1/3-1/31/3-1x3605/31-2/31/32/30-2/30-4/3-1/3-M+4/3j最优解x*=(2,0,6)T,最优值z*=-10.2.原问题:对偶问题:2,1,01322228min21212121jyyyyyyyyywj3,2,1,0228232max321321321jxxxxxxxxxxzj原问题变形为：3,2,1,0228232max321321321jxxxxxxxxxxzj3(1).当b2由2变为11时，最优解有何变化？911183/13/23/13/11bBXB原最优单纯形表新最优单纯形表最优解变为x*=(0,0,8)T,最优值变为z*=-8。cj-2-3-100-MiCBXBbx1x2x3x4x5x6-2x1211/30-1/3-1/31/3-1x3605/31-2/31/32/30-2/30-4/3-1/3-M+4/3j-141【】用对偶单纯法9cj-2-3-100-MiCBXBbx1x2x3x4x5x60x53-3-1011-1-1x38121-101-1-10-10-M+1j原最优单纯形表(2)最优基不变的情况下，△c1的变化范围？cj-2-3-100-MiCBXBbx1x2x3x4x5x6-2x1211/30-1/3-1/31/3-1x3605/31-2/31/32/30-2/30-4/3-1/3-M+4/3j-2+△c1-2+△c13235)1(31)2(3112cc00034)32()1()31()2(0114cc3131)1()31()2(0115cc33432)1(31)2(116cMcM0121c321c341c311c3341cM(3)当p2由变为时，最优解有何变化？32)1()1()2(32原最优单纯形表最优解不变。124121413/13/23/13/121pBcj-2-3-100-MiCBXBbx1x2x3x4x5x6-2x1211/30-1/3-1/31/3-1x3605/31-2/31/32/30-2/30-4/3-1/3-M+4/3j2-3-1仍是最优单纯形表0四.已知线性规划问题：(1)写出其对偶问题；(2)已知原问题的最优解为，试用对偶理论找出其对偶问题的最优解。56,53*2*1xx2,1,0236343323min21212121jxxxxxxxxxzj(1)写出其对偶规划；原问题:对偶问题:3,2,1,0233343263max321321321jyyyyyyyyyywj2,1,0236343323min21212121jxxxxxxxxxzj①②③(2)已知原问题的最优解，试用对偶理论找出其对偶问题的最优解。56,53*2*1xx将代入①②③，得③为严格不等式，56,53*2*1xx0*3y又0,0*2*1xx23343*2*1*2*1yyyy解得53,51*2*1yy05/3,5/1*，y五.写出下列线性规划的对偶问题。4,3,2,1,020999128537653432max4321432143214321jxxxxxxxxxxxxxxxxxzj解：原问题变形为：4,3,2,1,020999128537653432max4321432143214321jxxxxxxxxxxxxxxxxxzj原问题：4,3,2,1,020999128537653432max4321432143214321jxxxxxxxxxxxxxxxxxzj对偶问题：3,2,0,495339329711262085min1321321321321321jyyyyyyyyyyyyyyyyywj无约束六.求解下列运输问题。销地产地B1B2B3B4产量aiA11056725A2827630A3934835销量bj15203035解:(1)运输不平衡问题，总销量总产量，需增加虚拟产地A4销地产地B1B2B3B4产量aiA11056725A2827630A3934835销量bj15203035销地产地B1B2B3B4产量aiA11056725A2827630A3934835A4000010销量bj15203035100(2)求出初始可行方案(最小元素法)vjui销地产地B1B2B3B4产量aiA1105625725A28202710630A35933040835A410000010销量bj152030351000837-131-8(2)(3)(1)(5)(-1)(2)(5)(5)(1)(+)(-)(+)(-)(+0)(-0)(+0)(-0)(3)用位势法求出各非基变量检验数(4)有负检验数，用闭回路调整，得新的运输方案。vjui销地产地B1B2B3B4产量aiA1105625725A28202710630A35903304835A410000010销量bj15203035100(0)用位势法求出各非基变量检验数无负检验数，当前运输方案为最优运输方案。0937-140-9(2)(2)(4)(1)(6)(5)(2)(1)最小运费为440。七.判断下列运输方案是否最优，若不是，试求出最优方案。601401309080170033062150014211713180013351820207080313020260120154321jibAAAaBBBBBvjui销地产地B1B2B3B4B5产量aiA120183512013600180A2132017