补充线性规划问题练习题解答.doc

《补充线性规划问题练习题解答.doc》由会员分享，可在线阅读，更多相关《补充线性规划问题练习题解答.doc（16页珍藏版）》请在三一文库上搜索。

1、补充线性规划问题习题及解答1某铜厂轧制的薄铜板每卷宽度为100cm，现在要在宽度上进行切割以完成下列订货任务：24cm宽的75卷，40cm宽的50卷和32cm宽的110卷，长度是一样的，试将这个要解决的切割方案问题列成线性规划模型，使切余的边料最少。答：有下面八种切法方案出品数（卷）规格一二三四五六七八需要数量（卷）24cm40cm32cm4000200031111022102010117550110余料4204412122028设x1，x2，x3，x4，x5，x6 ，x7，x8分别表示八种下料方案切割的铜卷数，求解x1，x2，x3，x4，x5，x6，x7，x8使满足条件：并使余料总数：Z=

2、4x1+20x2+4x3+4x4+12x5+12x6 +20x7 +28x8 取得最小值。近似最优解x1=25/4,x3=20,x4=50 其他为0，最优值z*=305。（不是整数解）2某养鸡场养鸡10000只，用大豆和谷物饲料混合喂养，每天每只平均吃混合饲料0.5kg，其中应至少含有0.1kg蛋白质和0.002kg钙。已知大豆中含50%蛋白质和0.5%的钙，价格是1.00元/kg，谷物中含有10%的蛋白质和0.4%的钙，价格是0.30元/kg，粮食部门每周只保证供应谷物饲料25000kg，大豆供应量不限，问应如何搭配两种饲料，才能使喂养成本最低，建立该问题的数学模型。50%x1 +10%x2

3、0.1710000=7000 蛋白质0.5%x1+0.4%x20.002710000=140 钙 x1 +x20.5710000=35000 总量 x225000 谷物限量x10,x20min z=x1+0.3x2解：设每周用大豆x1公斤，谷物x2公斤,数学模型为 图解最优解x1=9333.33 , x2=23333.33,最小值z*=16333.33。3一家昼夜服务的饭店，24小时内需要服务员的人数如下每个服务员每天连续工作8小时，且在表中时段开始上班，试求要求满足以上要求的最少上班人数，建立该问题的数学模型。解：设在j钟点上班的人数为xj(j=1,2,6)，上班之后连续工作8小时，下班离开

4、，每班中间不允许交接班离开。故有4人8人10人7人12人4人 26时 x1610时 x21014时 x31418时 x41822时 x5222时 x6据题意有26时 x1 +x6 4 610时 x1+x2+ 81014时 x2+x3 101418时 x3+x4 71822时 x4+x5 12222时 x5+x6 4 min z=x1+x2+x3+x4+x5+x6最优解x1=4 , x2=10 , x4=8 , x5=4 , 其他xj=0, 最优值min z=26（人）4设有四个投资机会：甲：在三年内，投资人应在每年年初投资，每年每元可获利息0.2元，每年取息后可重新将本息投入生息。乙：在三年内

5、，投资人应在第一年年初投资，每两年每元可获得利息0.5元，两年后取息，可重新将本息投入生息。丙：在三年内，投资人应在第二年年初投资，两年后每元可获得利息0.6元，这种投资最多不得超过15000元。丁：投资人应在第三年年初投资，一年内每元投资可获利息0.4元，这种投资不得超过10000元。假定在这三年为期的投资中，开始时有30000元可供投资，投资人应怎样决定投资，才能在第三年底获得最高的收益，试建立其数学模型。解：设xij为第i年初投放到j项目的资金数，其数学模型为：max z=1.2x31+1.6x23+1.4x34x11+x1230000x21+x231.2x11x31+x341.2x21

6、+1.5x12x2315000x3410000xij0 ,(i=1,2,3 ,j=1,2,3,4)最优解x11=12500, x12=17500, x23=15000, x31=16250, x34=10000,其他为0；最优值z*=575005某一求目标函数最大值的线性规划问题，用单纯形法求解时得到的某一步的单纯形表如下：问a1，a2，a3，c，d各为何值及变量xj属于那一类性质的变量时：（1）现有解为唯一最优解。（2）现有解为最优，但最优解有无穷多个。（3）存在可行解，但目标函数无界。（4）此问题无可行解。答：1.c0, d0, x3, x4 ,x5都不是人工变量；2.c=0, d0 ,

7、a1，a2至少一个大于零，x3,x4,x5都不是人工变量；3.c0 , d 0 , a10，a20，x3,x4,x5都不是人工变量； 4.c0 , d0 且x3,x4,x5 至少一个是人工变量。6. 某线性规划问题的初始单纯形表及迭代后的表格如下：求a，b，k，l各个值。答：a=3, b=2, c=4, d=-2, e=2, f=3,g=1, h=0, i=5, j=5, k=-3/2, l=07. 写出下列线性规划问题的对偶问题：（1） 答:（2）答:8用对偶单纯形法求解下列线性规划问题:（1） 解:化成标准形式，列对偶单纯形表 cj -1 -1 0 0 bCBXB x1 x2 x3 x4

8、0 0x3x4 -2 -1 1 0 -1 -7 0 1 -4 -7j=cj-zj -1 -1 0 0 0采用对偶单纯形迭代规则得最优表：-1-1x1x2 1 0 7/13 1/13 0 1 1/13 -2/13 21/1310/13j=cj-zj 0 0 -6/13 -1/13 31/13最优解X=(21/13,10/13,0,0) ,最优值minZ= 31/13(maxZ=-31/13) 。（2）解: 化成标准形式，列对偶单纯形表cj -4 -12 -18 0 0 bCBXB x1 x2 x3 x4 x5 0 0X4X5 -1 0 -3 1 0 0 (-2) -2 0 1 -3 -5j=cj

9、-zj -4 -12 -18 0 0 0-12X4X2 -1 0 (-3) 1 0 0 1 1 0 -1/2 -3 5/2j=cj-zj -4 0 -6 0 -6 -18-12X3X2 1/3 0 1 -1/3 0 1/3 1 0 0 -1/2 1 3/2j=cj-zj -2 0 0 -2 -6 最优解X=(0,3/2,1,0,0) ,最优值minZ=36(maxZ=0-(3/2)12-118=-36) 。9设 （1）写出其对偶问题。（2）求解对偶问题。（3）从对偶解中求出原问题的解。答：（1）对偶模型 （2）求解对偶问题，图解法。得Y=(-3,1) ,w*=-15 。（3）利用互补松弛性求原

10、问题解，由y1,y2异于0，知原约束均为等式；又由对偶约束1，2，4式为严格不等式，故可得x1,x2,x4等于0。代入原约束方程组，解得x3=3，x5=3, 即X*=(0,0,3,0,3)T ,最优值z*=-13-43=-15=w*。10从下面最优单纯形表中（最大化问题，约束条件均为“”连接）-5Z=-5（1）写出原问题与对偶问题的最优解。（2）求，并解释这两个数值的含义。（3）如果以代价增添第一种资源一个单位，是否值得？（4）若有人原向你购买第三种资源，应要价多少才合算？（5）是否有其它最优解，如果没有，说明为什么？如果有，则求出另一个最优解。解：(1)原问题最优解X*=(2,0,3/2,0

11、,1,0)T ,对偶问题最优解Y*=(4,0,9,0,0,0)。 (2)在最优表上可以得到最优基的逆B-1,根据最优表上Pj=B-1Pj ,可解得Pj=BPj,从而得A,对偶解-单纯形因子再由检验数 ,可得 解得C=(1,1,2,0,0,0) ，最优值z*=12+0+2(3/2)=5。在最优方案时，有 ,因为b1影子价格大于0,是稀缺资源，故在一定范围内每增加一个单位该种资源就会增加4个单位总收入（影子价格或边际收入为4）。对 ，x6表示第三种资源剩余数量，该偏导数值表示资源剩余量对总收入的影响率。在初始方案时其值为0，在最佳方案时其值为-9，从另外角度说明引入该资源有利于减少短缺造成的损失或

12、增加收入（影子价格为9）。(3) 如果以代价增添第一种资源一个单位, 会增加4个单位总收入，值得。 (4) 若有人愿向你购买第三种资源，要价不低于其影子价格9才合算。 (5) 在最优表上,非基变量x2的检验数为0，故最优解不唯一。令x2进基，x1出基，换基迭代得新最优解X*=(0,2,3/2,0,5)T ,最优值z*=0+12+2(3/2)=5 。11设 先用单纯形法求出最优解，再分析在下列各条件单独变化的情况下最优解的变化。（1）约束条件（2）右端常数由90变为70。（2）目标函数中x3的系数由13变为8。（3）增加一个约束条件：解: 先用单纯形法求出最优解MAX:-5X1 +5X2 +13

13、X3 ST: 1 -1X1 +1X2 +3X3 +1X4 = 20 2 12X1 +4X2 +10X3 +1X5 = 90得到了第一个可行基用最大检验数法- I BA C -5 5 13 0 0 b X1 X2 X3 X4 X5- 1 X2 5 20 -1 1 3 1 0 2 X5 0 10 16 0 -2 -4 1- Cj-Zj -100 0 0 -2 -5 0迭代次数 = 2最优解MAX Z= 100变量名 取值 检验数 X1 0 0.000000 X2 20 X3 0 -2.000000 X4 0 -5.000000 X5 10 约束标号 对偶价格( 1) 5.000000( 2) 0.

14、000000在最优基不变的条件下, 变量在目标函数中的系数的取值区间变量名 现系数 系数取值区间 X1 -5.0000 ( - ? , -5.0000 ) X2 5.0000 ( 4.3333 , 5.0000 ) X3 13.0000 ( - ? , 15.0000 ) X4 0.0000 ( - ? , 5.0000 ) X5 0.0000 ( 0.0000 , 1.0000 )在最优基不变的条件下, 右端常数项的取值区间约束序号 现常数 常数取值区间( 1) 20.0000 ( 0.0000 , 22.5000 )( 2) 90.0000 ( 80.0000 , ? )-(1) 约束条件

15、（2）右端常数由90变为70,不影响最优基,只须验证可行性。由最优表找到最优基的逆, x5不可行,采用对偶单纯形迭代，x5出基，x3进基， - I BA C -5 5 13 0 0 b X1 X2 X3 X4 X5- 1 X3 13 5 -8 0 1 2 -1/2 2 X2 5 5 23 1 0 -5 3/2- Cj-Zj -90 -16 0 0 -1 -1-最优解变量名 取值 检验数 X1 0 -16.000000 X2 5 X3 5 X4 0 -1.000000 X5 0 -1.000000MAX Z= 90(2) 目标函数中非基变量x3的系数c3由13变为8。检查检验数3=c3-CBB-

16、1P3=8-(5,0)(3,10)T=8-15=-70,最优解，最优值不变。(3) 增加一个约束条件：,引进松弛变量x6作为一个基变量，在最优表添加一行，迭代出单位矩阵和检验数形式，判断是否最优解。- I BA C -5 5 13 0 0 0 b X1 X2 X3 X4 X5 X6- 1 X2 5 20 -1 1 3 1 0 0 2 X5 0 10 16 0 -2 -4 1 0 3 X6 0 50 2 3 5 0 0 1- Cj-Zj -100 0 0 -2 -5 0 0- I BA C -5 5 13 0 0 0 b X1 X2 X3 X4 X5 X6- 1 X2 5 20 -1 1 3 1

17、 0 0 2 X5 0 10 16 0 -2 -4 1 0 3 X6 0 -10 5 0 (-4) -3 0 1- Cj-Zj -100 0 0 -2 -5 0 0采用对偶单纯形迭代，x6出基，x3进基，- I BA C -5 5 13 0 0 0 b X1 X2 X3 X4 X5 X6- 1 X2 5 25/2 11/4 1 0 -5/4 0 3/4 2 X5 0 15 27/2 0 0 -5/2 1 -1/2 3 X3 13 5/2 -5/4 0 1 3/4 0 -1/4 - Cj-Zj -95 -5/2 0 0 -7/2 0 -1/2最优解MAX Z= 95变量名 取值 检验数 X1 0

18、 -2.500000 X2 25/2 X3 5/2 X4 0 -3.500000 X5 15 X6 0 -0.500000约束标号 对偶价格( 1) 3.500000( 2) 0.000000( 3) 0.500000在最优基不变的条件下, 变量在目标函数中的系数的取值区间变量名 现系数 系数取值区间 X1 -5.0000 ( - ? , -2.5000 ) X2 5.0000 ( 4.3333 , 7.8000 ) X3 13.0000 ( 8.3333 , 15.0000 ) X4 0.0000 ( - ? , 3.5000 ) X5 0.0000 ( -0.1852 , 1.0000 )

19、 X6 0.0000 ( - ? , 0.5000 )在最优基不变的条件下, 右端常数项的取值区间约束序号 现常数 常数取值区间( 1) 20.0000 ( 16.6667 , 26.0000 )( 2) 90.0000 ( 75.0000 , ? )( 3) 50.0000 ( 33.3333 , 60.0000 )12设 （1）求在不影响最优基的条件下各个cj的允许变化的范围。（2）求在不影响最优基的条件下各个bi的允许变化的范围。解：列单纯形表求解得最优表，利用最优基不变时求解各系数区间MAX: 2X1 +5X2 +8X3 ST: 1 3X1 +2X2 -1X3 +1X4 =610 2

20、-1X1 +6X2 +3X3 +1X5 =125 3 -1X1 +1X2+1/2X3 +1X6 =420MAX: 2X1 +5X2 +8X3 ST: 1 3X1 +2X2 -1X3 +1X4 =610 2 -1X1 +6X2 +3X3 +1X5 =125 3 -1X1 +1X2+1/2X3 +1X6 =420得到了第一个可行基用最大检验数法- I BA C 2 5 8 0 0 0 b X1 X2 X3 X4 X5 X6 - 1 X4 0 610 3 2 -1 1 0 0 2 X5 0 125 -1 6 3 0 1 0 125/3 3 X6 0 420 -1 1 1/2 0 0 1 840- C

21、j-Zj 0 2 5 8 0 0 0 -旋转元是 A23用最大检验数法- I BA C 2 5 8 0 0 0 b X1 X2 X3 X4 X5 X6 - 1 X4 0 1955/3 8/3 4 0 1 1/3 0 1955/8 2 X3 8 125/3 -1/3 2 1 0 1/3 0 3 X6 0 2395/6 -5/6 0 0 0 -1/6 1 - Cj-Zj -1000/3 14/3 -11 0 0 -8/3 0 -旋转元是 A11用最大检验数法- I BA C 2 5 8 0 0 0 b X1 X2 X3 X4 X5 X6- 1 X1 2 1955/8 1 3/2 0 3/8 1/8

22、 0 2 X3 8 985/8 0 5/2 1 1/8 3/8 0 3 X6 0 9645/16 0 5/4 0 5/16 -1/16 1- Cj-Zj -5895/4 0 -18 0 -7/4 -13/4 0-迭代次数 = 2最优解MAX Z= 5895/4 = 1473 3/4 = 1473.750000变量名 取值 检验数 X1 1955/8 = 244 3/8 = 244.375000 X2 0 -18.000000 X3 985/8 = 123 1/8 = 123.125000 X4 0 -1.750000 X5 0 -3.250000 X6 9645/16 = 602 13/16

23、= 602.812500约束标号 对偶价格( 1) 1.750000( 2) 3.250000( 3) 0.000000(1) 在不影响最优基的条件下各个cj的允许变化的范围在最优基不变的条件下, 变量在目标函数中的系数的取值区间变量名 现系数 系数取值区间 X1 2.0000 ( -2.6667 , ? ) X2 5.0000 ( - ? , 23.0000 ) X3 8.0000 ( 0.8000 , ? ) X4 0.0000 ( - ? , 1.7500 ) X5 0.0000 ( - ? , 3.2500 ) X6 0.0000 ( -5.6000 , 52.0000 )（2）在不影响最优基的条件下各个bi的允许变化的范围B-1b0在最优基不变的条件下, 右端常数项的取值区间约束序号 现常数 常数取值区间( 1) 610.0000 ( -41.6667 , ? )( 2) 125.0000 ( -203.3333 , 9770.0000 )( 3) 420.0000 ( -182.8125 , ? )