《运筹与决策复习题》由会员分享，可在线阅读，更多相关《运筹与决策复习题（15页珍藏版）》请在金锄头文库上搜索。
1、复 习 课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点对应的基变
2、量为（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三、一个工厂用四种原料生产三种产品，生产
3、每种产品要消耗的各种原料数量（表中“”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如右表所示。1、写出原料限制条件下利润最大化的线性规划模型；2、写出以上问题的对偶问题；3、已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格（写出单位）；4、分别计算三种产品的机会成本（写出单位）；5、产品B对原料乙的消耗系数（10吨/件）降低到多少，产品B在最优解中才能安排生产？四、对于以下运输问题运价（元/吨）B1B2B3B4供应量（吨）A1912108240A214761180A35131520180需求量（吨）9
4、0120130160（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三个项
5、目，每个项目的投资效益与投入该项目的资金有关。三个项目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+3x23x1x
6、20引进松弛变量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再解决对偶
7、可行性，用单纯形法，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
8、），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.12
9、x1+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=1
