运筹学复习题及-答案.doc

《运筹学复习题及-答案.doc》由会员分享，可在线阅读，更多相关《运筹学复习题及-答案.doc（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date运筹学复习题及-答案运筹学复习题及-答案运筹学复习题及答案一、一个毛纺厂用羊毛和涤纶生产A、B、C混纺毛料，生产1单位A、B、C分别需要羊毛和涤纶3、 2； 1、 1； 4、4单位，三种产品的单位利润分别为4、1、5。每月购进的原料限额羊毛为8000单位，涤纶为3000单位，问此毛纺厂如何安排生产能获得最大利润？（要求：建立该问题的数学模型）解：设 生产混纺毛料ABC

2、各x1、x2、x3单位max zx1+x2+5x33x1+x2+4x380002x1+x2+4x33000x1,x2,x30二、写出下述线性规划问题的对偶问题max s=2x1+3x2-5x3+x4x1+x2-3x3+x452x1 +2x3-x44x2 +x3+x4=6 x1,x2,x30；x4无约束解：先将原问题标准化为：max s=2x1+3x2-5x3+x4-x1-x2+3x3-x4-52x1 +2x3-x44x2 +x3+x4=6x1,x2,x30；x4无约束则对偶问题为：min z=-5y1+4y2+6y3-y1+2y22-y1+ y233y1+ 2y2+y3-5-y1-y2+y3=

3、1y1,y20,y3无约束三、求下述线性规划问题min S =2x13x25x3x1x23x3 52x1 2x3 4 x1，x2，x30解：引入松弛变量x4，x5，原问题化为标准型：max Z=-S =-2x1-3x2+5x3x1x23x3 x4=52x1 2x3 +x5=4 x1，x2，x3, x4,x50对应基B0（P2,P5）的单纯形表为T(B0)=51 1 -3 -1 042 0 2 0 1151 0 -4 -3 0x1的检验数为正，x1进基，由min5/1,4/2=4/2知，x5出基，迭代得新基B1=(P2,P1),对应的单纯形表为T(B1)=30 1 -4 -1 -1/221 0

4、1 0 1/2130 0 -5 -3 -1/2至此，检验数全为非正，已为最优单纯形表。对应的最优解为：x1=2,x2=3,x3=x4=x5=0,max z=-13,故原问题的最优解为：x1=2,x2=3,x3 =0,min s=13。四、利用大M法求解下面线性规划问题: 解：引入松弛变量x4和人工变量x5，构造如下规划：对应基B0（P4,P5）的单纯形表为T(B0)=42 1 1 1 061 2 0 0 16M-1+M 2+2M 1 0 0x1的检验数为-1+ M0，x1进基，由min6/1=6/1知，x5出基，迭代得新基B1=(P4,P1),对应的单纯形表为T(B1)=160 5 1 1 2

5、61 2 0 0 160 4 1 0 1-Mx3的检验数为10，x3进基，由min16/1=16/1知，x4出基，迭代得新基B2=(P3,P1),对应的单纯形表为T(B2)=160 5 1 1 261 2 0 0 1-100 -1 0 -1 -1-M至此，检验数全为非正，已为最优单纯形表。对应的最优解为：x1=6,x2=0,x3=16,x4=x5=0,最优值max z=10。五、已知线性规划问题(L):(1) 写出该问题的对偶表,从而给出其对偶问题(D).(2)用对偶单纯形法求解问题.解：(1)该问题的对偶表,x1x2x3MinMax其对偶问题(D)为max Z=6y1+8y22y1+ y21

6、 y1+3y222y1+2y23 y1,y20123cb2126y11328y2(2)用对偶单纯形法求解问题. 引入松弛变量x4、x5，构造如下规划：对应基B0（P4,P5）的单纯形表为T(B0)=6-2 -1 -2 1 08-1 -3 -2 0 10-1 -2 -3 0 0检验数全为非正，基变量x46，x4出基,利用偶单纯形法，由min1/2，2/-1,-3/-2=1/2知，x1进基，迭代得新基B1=(P1,P5),对应的单纯形表为T(B1)=31 1/2 1 -1/2 050 -5/2 -1 -1/2 130 -3/2 -2 -1/2 0基变量x55，x5出基,利用偶单纯形法知，x2进基，

7、迭代得新基B2=(P1,P2),对应的单纯形表为T(B2)=21 0 4/5 -3/5 1/520 1 2/5 1/5 -2/560 0 -7/5 -1/5 -3/5至此,得到最优解:x1=x2=2,x3=x4=x5=0,最优值maxZ=-6,故原问题的最优解为: x1=x2=2,x3=0, 最优值minS=6.六、某运输问题的产销平衡表和运价表如下，试用表上作业法求最优调运方案。 销地产地B1B2B3产量A1A2A310324162571211销量10101030解：由最小元素法得初始运输方案B1B2B3产量A1A2A3101072171211销量10101030总运费S=010110672

8、251=61经计算11（60）（21）30,调整量=min（7,10）7，经调整，得新运输方案：B1B2B3产量A1A2A37310 9171211销量10101030总运费S=613740至此，所有检验数均以非正，该运输方案已为最优。即：A1运到B1 7个单位；A2运到B1 3个单位；A2运到B3 9个单位A3运到B2 10个单位；A3运到B3 1个单位；总运费S40个单位七、某极大化整数规划对应的线性规划的最优单纯形表如下：5/20 1 1/2 -1/213/41 0 -1/4 3/4-69/40 0 -3/4 -3/4试建立割平面方程并求原整数规划的最优解。解：由x2=5/2为非整数，对

9、应方程为：5/2=x2+1/2x3-1/2x4即：x2x4-2=1/2-(1/2x3+1/2x4),得Gomery割平面：1/2-(1/2x3+1/2x4)0引入松弛变量x5,添加约束： -1/2x3-1/2x4 x5=1/2,由表5/20 1 1/2 -1/2 013/41 0 -1/4 3/4 0-1/20 0 -1/2 -1/2 1-69/40 0 -3/4 -3/4 0利用对偶单纯形法迭代得到新单纯形表：20 1 0 -1 17/21 0 0 1 -1/210 0 1 1 -2-33/20 0 0 0 -3/2由7/2=x1+x4-1/2x5,得Gomery割平面：1/2-1/2x5+

10、0-2/3 1/384/3故最优基不变，最优解改变为：x14/3,x2=10/3,对应的最优值为16/3。（4）设c2的摄动量为，最优基不变。此时，C=(-1,2+,0,0),CB=(2+,-1),由C -CBB-1A0,得4010因此1，即c22+1，故当c2在1,+)变化时,最优基不变,生产计划不变.九、某物资的产销平衡表及运价表如下，求总运费最省的调运方案。 平衡表运价表(百元/吨) 销地产地B1 B2 B3 B4产量(吨)B1 B2 B3 B4A1A2A33572 5 9 81 9 2 67 5 4 3销量(吨)6 3 2 415解:利用最小元素法得到初始可行解(运输方案) 销地产地B

11、1 B2 B3 B4产量(吨)A1A2A31 25 1 2 4357销量(吨)6 3 2 415对应的总运费s0=12+2551152443=42(百元)利用位势法计算检验数ij=cij-(ui+vj),如下: B1 B2 B3 B4uiA1A2A3 5 5 5 -1 450-10vj2 5 4 3检验数23=c23-(u2+v3)=2-(4-1)=-1,表中不是最优运输方案,需调整,调整量为=min=2,2,5=2,新运输方案为: 销地产地B1 B2 B3 B4产量(吨)A1A2A33 03 2 3 4357销量(吨)6 3 2 415对应的总运费s1=32+0531352243=40(百元

12、)或s1=s0+23=42-12=40(百元)利用位势法计算检验数ij=cij-(ui+vj),如下: B1 B2 B3 B4uiA1A2A3 5 5 5 45 20-10vj2 5 3 3此时,检验数全为非负, 表中已是最优运输方案, 总运费为40百元.十、利用割平面法,求下面问题:解：引入松弛变量x3，x4，构造辅助LP：对应基B0（P3P4）的单纯形表T(B0)=61 1 1 031 4 0 102 1 0 0迭代得到新基B1（P3P1）,对应的单纯形表为：T(B1)=30 5 1 131 4 0 160 9 0 2迭代得到新基B2（P2P1）,对应的单纯形表为：T(B2)=3/50 1

13、 1/5 1/527/51 0 4/5 1/557/50 0 -9/5 1/5检验数已经全为非正，得到辅助LP的最优单纯形表，由于解不是整数，所以不是原整数规划问题的解.对应第二个方程的Gomery割平面：2/5（4/5x31/5x5）0引入松弛变量x5,添加约束： -4/5x3-1/5x4 x5=1/5,由表3/50 1 1/5 1/5 027/51 0 4/5 1/5 0-2/50 0 -4/5 -1/5 157/50 0 -9/5 1/5 0利用对偶单纯形法迭代得到新单纯形表：10 1 1 0 151 0 0 0 120 0 4 1 5110 0 1 0 1至此，得到原整数规划的最优解：x15，x21，最优值为maxS=11.-