运筹学练习参考答案

1、线性规划问题1、某工厂生产I、II、III三种产品，分别经过 A、B、C三种设备加工。已知生 产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见 下表：IIIIII设备能力(台时厂A111100B1045600C226300单位利润(元)1064(1)求获利最大的产品生产计划；(2)产品III每件的利润增加到多大时才值得安排生产；(3)如有一种新产品，加工一件需设备A、B、C的台时各为1, 4, 3小时，预期每件的利润为8元，是否值得安排生产。解：(1)设xi, X2, X3分别为I、II、III三种产品的产量，z表示利润。该问 题的线性规划模型为：maxz 10 x1 6

2、x2 4x3x1 x2 x3 10010 x1 4x2 5x3 600s.t2x1 2x2 6x3 300 TOC o 1-5 h z 为？2%0用单纯形法求上述线性规划问题。化为标准形式：maxz 10 x1 6x2 4x3 0 x4 0 x5 0 x6x1x2 x3 x410010 x1 4x2 5x3 x5600s.t2x1 2x2 6x3x6 300% 0,j 1,2,6Cj1064000CBxBbx1x2x3x4乂5x0 x41001111001000乂56001045010600 x6300226001150j010640000 x44000.60.51-0.10200/310 x

3、16010.40.500.101500 x618001.250-0.211501 / 13j-60002-10-106X2200/3015/65/3-1/6010Xi100/3101/6-2/31/600X6100004-201j-2200/300-8/3-10/3-2/30所以最优解为 X* =(100/3, 200/3, 0, 0, 0, 100)T,即产品 量分别为：100/3, 200/3, 0;最优解目标函数值 z* =2200/3(2)设产品III每件的利润为C3I、II、II的产3 C3 CbB R C3 CbE5/6c36,10,0 1/6C3 20/3 0c3 20/34产品

4、III每件的利润增加到20/3时才值得安排生产。(3)设X7为新产品的产量。17 c7 CBB 1P7 8 ( ,2,0) 42 0值得投产3 335/31/6 0 111P7 B 1P72/3 1/6 0 4020131cj10640008cBXbbXiX2X3X4X5X6X76X2200/3015/65/3-1/601200/310Xi100/3101/6-2/31/600-0X6100004-2011100-2200/300-8/3-10/3-2/3028X7200/3015/65/3-1/60110Xi100/3101/6-2/31/6000X6100/30-119/6-11/31/6

5、10-2600/30-2-13/3-20/3-1/3002 / 13所以最优解为x* =(100/3 , 0, 0, 0, 0, 200/3)t,即产品I的产量：100/3,新产品的产量：200/3 ;最优解目标函数值z* =2600/32、已知下列线性规划问题：maxz 6xi 3x2 3x33x1 x2 x3 602xi 2x2 4x3 20s.t3xi 3x2 3x360 xi,x2,x3 0求：(1)用单纯形法求解，并指出问题属于哪一类解；(2)写出该问题的对偶问题，并求出对偶问题的最优解;解：(1)将原问题划为标准形得：64 3x解：(1)将原问题划为标准形得：64 3x2 3x3

6、0 x4 0 x5 0 x6 x? x3 x4602x2 4x3x5203x2 3x3x6 600,j 1,2,6maxz3x12x1st3x1cj6-33000cBxbbx1x?x3x4x5x60 x460311100200 x5202-24010100 x6603-3300120j06-330000 x43004-51-3/2015/26x1101-1201/20-0 x63006-90-3/215j-6003-90-300 x4100011-1/2-2/36x115101/201/41/63 / 13-3x2501-3/20-1/41/6j-7500-9/20-9/4-1/2最优解为x*

7、 =(15 , 5, 0, 10, 0, 0)T最优解目标函数值z* =75 非基变量的检验数0,为唯一最优解.(2)该问题的对偶问题为：min w 60 yl 20y2 60y3 TOC o 1-5 h z 3yi 2y2 3y36y1 2y2 3y33s.ty1 4y2 3y33y1，y2,y30对偶问题的最优解：y* =(0 , 9/4, 1/2)max z x1 2x22x1 x2 8s.t. x2 4 x) ,x2 03、已知线性规划问题：求：(1)用图解法求解；(2)写出其对偶问题；(3)根据互补松弛定理，写出对偶问题的最优解解：(1)图解法由上图可知：在B(2,4)处，目标函数达

8、到最大值。即最优解为x*=(2,4) T最优解目标函数值z*=10为唯一最优解(2)该问题的对偶问题为：4 / 13min w 8yl 4y22yi 1s.t yi y22yi 0, y2 0(3)原问题的最优解x*=(2,4) 丁代入约束条件，可知约束条件取等式，因为X1*, 乂2*不为0,在对偶问题中相应的约束条件为紧约束，即 2yi 1, yi V22对偶问题的最优解及最优目标函数值为：y (i/2,3/ 2) w i0运输问题i、某产品有三个产地、四个销地，各产地的产量、各销地的销量以及产地到销 地之间的单位运价见下表：销地BiB2B3B4J里Ai4i24iii6A22i039i0A3

9、85ii622销量8i4i2i4(D用表上作业法求该运输问题的最优调运方案。(i5分)(2)该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再 求出一个最优调运方案来。(5分)解：(i)先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法 求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案, 再检验最优性。求初始基可行解(Vogel法)销地BiB2B3B4J里差额AiI Ii24.46-0 0 0 7 04 nr -i2 1r-hriA281一L一2i0i i i 6 03-9I yJA3i4L 8一 _i 2飞5iiI6LN2销量8i4 1i2 iiI

10、差额2215i335 / i3211222初始解为：x13=12, x14=4, x21=8, x24=2, x32=14, x34=8,其余变量为 0;相应的目标函数值 z= 4 M2+11M+2X8+9X2+5X14+6X8= 244最优性检验(位势法)根据基变量的检验数为0,即j13= c13 刀1-V3 = 4V3=021= C21 -u2 -v1 = 2 -U2 -v1 =032= c32 3 V2 = 5 山3 V2 =0u1 =0易得：u2= -2, u3= -5,计算非基变量的检验数：cij 2 vj =014= c14 -U1 -v4 = 11 -U1 -V4 =024= c

11、24 -u2 -v4 = 9 -u2 -v4 =034= C34 q v4 = 6 q v4 =0v1 =4, v2=10, v3=4, v4=1111= c11 -u1 -v1 = 4 -0 -4=022= % u2 V2 = 10 X Z - 10=231= C31 % v1 = 8 (-4=912= c12 -u1 -v2 = 12 -0 -10=29o= c9o _u-v = 3 _(Z - 4=1 23232333= C33 qv3 = 11 (与4=12所有非基变量xj的检验数ij0,即得最优解最优解为：x*13=12, x 14=4, x 21=8, x 24=2, x 32=1

12、4, x 34=8,其余变量为 0;最优目标函数值z* = 244（2）因为非基变量x11的检验数11=0,所以该问题有多个最优调运方案从非基变量x11出发找一条闭回路（见下表）销地BiB2B3B4）里A1小12124_ (-)4 11 :16A28 _8 2(-)103一 1 29 (+)10A381451186226 / 13销量8141214闭回路调整后得到另一最优解:销地B1B2B3B4J里A144124121116A2241039610A38514116822销量8141214即最优解为：x*11=4, x*13=12, x*21=4, x*24=6, x*32=14, x*34=8

13、,其余变量为 02、一个运输网络有4个发点和4个收点，发点的发量，收点的收量与单位运价 如下表所小：B1B2B3B4供应量A120801020100A210252050200A320302040100A4401201030100 需求使总运费最小的运输方案。解：产量销量，假想一个销地 B5,销量为100先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量 的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优 性。求初始基可行解（Vogel法）销地B1B2B3B4B5供应量差额110 011001A12*硕：一回20!阿100 1

14、0 10 10150I 50I1A210 20 ；50 0 ;-20010 10 10 10 5 0 0 01 100A320 30 |20 j40 fB10 ；一100200 0010 0 0T11 0110011A440 I20110 30 0 1 -TO010 10 10 10 10 0需求量15050r 100100100差额10501007 / 131010105555550 0 10 1010初始解 x13=0, x14=100, x21=150, x22=50, x32=0, x35=100, x42=0, x43=100，其余变量为 0最优性检验（位势法）：根据基变量的检验数为

15、0,即ij = Cjj -Uj -Vj =013= C13= C13 1V3= 10 R V3=021= C21 -U2 -V1 = 10 -U2 -V1 =032= c32 -u3 -v2 = 30 -u3 -v2 =042= C42 -U4-V2 = 20 -U4 -V2 =0u1 =0易得：u2= 5, u3= 10, u4= 0,计算非基变量的检验数：11= c11 -U1 -V1 = 20 -0- 5=1515= c15 u1 -v5 = 0 -0 -(-10)=1024= c24 -u2 -v4 = 50 -5-20 =2531= c31 0V1 = 20 T0 5=534= c3

16、4 -u3 -v4 = 40 -10 -20 =1044= c44 P4-V4= 30 - 0-20=1014= c14 R v4 = 20 -u1 -v4 =022= c22 -u2 v2 = 25 -u2 v2 =035= c35 q V5 = 0 q V5 =043= c43 UV3= 10 V3 =0V1=5, v2=20, v3=10, v4=20, v5= -1012= c12 R _ V2 = 80 -0 - 20=6023= c23 u2 V3 = 20 5 T0=525= c25 -u2 -v5 = 0 七-(-10) =533= c33 -u3-v3 = 20 0- 10

17、=0 33333341= c41 -u4 -V1 = 40 -0- 5 =3545= c45 q-V5= 0 0-(-10)=10所有非基变量xj的检验数ij0,即得最优解。最优解为：x*13=0, x*14=100, x*21 = 150, x*22=50, x*32=0, x*35=100, x*42=0, x*43=100其余变量为0;最优目标函数值z* = 57508 / 13目标规划某工厂计划生产A、B两种产品，需要消耗甲、乙、丙三种资源、单位产品 利润及资源限量如表所示：产品资源AB资源限制甲21140乙1060丙01100产品利润（元/件）3012该厂的经营目标是:首先要求总利润

18、必须超过2500元；然后考虑到产品受市场影响，为避免积压，A、B的产量不超过60件和100件;由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型。解：设xi, x2为产品A、B产量，以产品A、B的单件利润比2.5 : 1为权系 数，目标规划模型如下：minz Rd1 P2（2.5d2 d3） gd430% 12x2 di di 2500 TOC o 1-5 h z x1d3d360 x2d4d41002为x2d2d2140 x1,x2 0,di ,di 0 （i 1,2,3,4）整数规划1、在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用见下表， 假定每一项已经批准的

19、工程要在整个 3年内完成，目标是要选出使总收入达到最 大的那些工程，试将这个问题表示成 0-1整数规划模型。工程费用（千元）收入（千元）第一年第二年第三年15182024710403:392 I2014741159 / 135861030最大可用资金 （S252525-解：设玉1,对第j个项目投资解：设玉0,不对第j个项目投资j必”该问题的0-1整数规划模型为:maxz5x1Xs.t门 8KXj20 x1 40 x2 20 x3 15x4 30 x54x2 3x3 7x4 8x5 257x2 9x3 4x4 6x5 2510 x2 2x3 x4 10% 250或 1 (j 1,2,5)2、分配

20、甲、乙、丙、丁、戊五个人去完成 A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。（10分）（表中单位：小时）任ABCDE不2528314138乙4038262633丙3527284032丁2442372345戊3029262032已知甲不可能完成任务 D, 丁只可以完成任务B、C,试确定最优分配方案，使 完成任务的总时间为最少。解：若不可能完成任务，则效率矩阵相应的元素为 M,变换效率矩阵:10 / 13252831M3825036 M25134038262633261412007352728403227801135M4237MM37M 3750 M37M ：302926203220109601237M 251412 013M 37 5 0M 37M 4