《最全运筹学习题集与答案解析.doc》由会员分享，可在线阅读，更多相关《最全运筹学习题集与答案解析.doc（63页珍藏版）》请在三一办公上搜索。
1、 运筹学习题答案第一章（39页）1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max 5+1050+14，0（2）min z=+1.5+33+2，0（3）max z=2+2-1-0.5+2，0（4）max z=+-03-3，0解：（1）（图略）有唯一可行解，max z=14（2）（图略）有唯一可行解，min z=9/4（3）（图略）无界解（4）（图略）无可行解1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。（1）min z=-3+4-2+54-+2-=-2+3-14-2+3-+22，0，无约束（2）max 0 (i=1n; k
2、=1,m)（1）解：设z=-,=-, ,0标准型：Max =3-4+2-5(-)+0+0-M-Ms. t . -4+-2+-+=2+3-+=14-2+3-+2-2-+=2,0 初始单纯形表:3-42-5500-M-Mb-M2-41-21-100012014113-11100014-M2-23-12-20-1102/3-4M3-6M4M-42-3M3M-55-3M0-M00(2)解：加入人工变量，得：Max s=(1/)-M-M-.-Ms.t. (i=1,2,3,n)0, 0, (i=1,2,3n; k=1,2.,m)M是任意正整数初始单纯形表：-M-M-Mb-M110011000-M10100
3、000-M1001000111-snM0001.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）max z=2+3+4+7 2+3-4=8-2+6-7=-3,0(2)max z=5-2+3-6+2+3+4=72+2=30（1）解：系数矩阵A是：令A=(，)与线形无关，以（，）为基，为基变量。有 2+3=8+4-2=-3-6+7令非基变量，=0解得：=1；=2基解=（1，2，0，0为可行解=8同理，以（，）为基，基解=（45/13，0，-14/13，0是非可行解；以（，）为基，基解=（34/5，0，0，7/5是可行解，=117/5；以（，
4、）为基，基解=（0，45/16，7/16，0是可行解，=163/16；以（，）为基，基解=（0，68/29，0，-7/29是非可行解；以（，）为基，基解=（0，0，-68/31，-45/31是非可行解；最大值为=117/5；最优解=（34/5，0，0，7/5。（2）解：系数矩阵A是：令A=(，)，线性无关，以（，）为基，有：+2=7-3-42+=3-2令 ，=0得=-1/3，=11/3基解=（-1/3，11/3，0，0为非可行解；同理，以（，）为基，基解=（2/5，0，11/5，0是可行解=43/5；以（，）为基，基解=（-1/3，0，0，11/6是非可行解；以（，）为基，基解=（0，2，1，
5、0是可行解，=-1；以（，）为基，基解=（0，0，1，1是=-3；最大值为=43/5；最优解为=（2/5，0，11/5，0。1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。（1）max z=2+ 3+515 6+224，0（2）max z=2+542123+218，0解：（图略）（1）max z=33/4 最优解是(15/4,3/4)单纯形法：标准型是max z=2+0+0s.t. 3+5+=15 6+2+=24,0单纯形表计算：2100b0153510502462014-z0210003041-1/23/42411/301/612-z-801/30
6、-1/313/4011/4-1/8215/410-1/125/24-z-33/400-1/12-7/24解为：（15/4，3/4，0，0 Max z=33/4迭代第一步表示原点；第二步代表C点（4，0，3，0；第三步代表B点（15/4，3/4，0，0 。（2）解：（图略）Max z=34 此时坐标点为（2，6）单纯形法，标准型是：Max z=2+5+0+0+0s.t. +=4 2+=12 3+2+=18,0(表略)最优解 X=（2，6，2，0，0 Max z=34迭代第一步得=（0，0，4，12，18表示原点，迭代第二步得=（0，6，4，0，6，第三步迭代得到最优解的点。1.5以1.4题（1）
7、为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。解：目标函数：max z=+(1)当0时=-（/）+z/ 其中，k=-/=-3/5，=-3l k 时，同号。当0时，目标函数在C点有最大值当0时，目标函数在原点最大值。l k时，同号。当0， 目标函数在B点有最大值；当0，目标函数在原点最大值。l k 0时，同号。当0时，目标函数在A点有最大值当0时，目标函数在原点最大值。l k 0时，异号。当0，0时，目标函数在A点有最大值；当0，0时，目标函数在C点最大值。l k= 时，同号当0时，目标函数在AB线断上任一点有最大值当0，目标函数
8、在原点最大值。l k= 时，同号。当0时，目标函数在BC线断上任一点有最大值当0时，目标函数在原点最大值。l k=0时，=0当0时，目标函数在A点有最大值当0，目标函数在OC线断上任一点有最大值（2）当=0时，max z= l 0时，目标函数在C点有最大值l 0时，目标函数在OA线断上任一点有最大值l =0时，在可行域任何一点取最大值。1.6分别用单纯形法中的大M法和两阶段法求解下列线性问题，并指出属于哪类解。（1）max z=2+3-5+152-5+24，0（2）min z=2+3+4+283+26，0（3）max z=10+15+125+3+9-5+6+15152+5，0（4）max z=
9、2-+2+6-2+22-0，0解：（1）解法一：大M法化为标准型：Max z=2+3-5-M+0-Ms.t. +=7 2-5+-+=10,0 M是任意大整数。单纯形表：23-5-M0-Mb-M71111007-M102-510-115-z17M3M+23-4M2M-50-M0-M207/21/211/2-1/24/7251-5/21/20-1/21/2-z2M-100(7/2)M+80.5M-600.5M+1-1.5M-134/7011/72/71/7-1/7245/7106/75/7-1/71/7-z-102/700-50/7-M-16/7-1/7-M+1/7最优解是： X=（45/7，4/
10、7，0，0，0 目标函数最优值 max z=102/7有唯一最优解。解法二：第一阶段数学模型为 min w=+S.t. +=72-5+-+=10,，,0（单纯形表略）最优解X=（45/7，4/7，0，0，0 目标函数最优值 min w=0第二阶段单纯形表为：23-50b34/7011/71/7245/7106/7-1/7-z-102/700-50/7-1/7最优解是X=（45/7，4/7，0，0，0 Max z=102/7（2）解法一：大M法=-z 有max =-min （-）=-min z化成标准形：Max =-2-3-+0+0-M-MS.T. +4+2-+=4 3+2-+=6,，,，0（单
11、纯性表计算略）线性规划最优解X=（4/5，9/5，0，0，0 ，0 目标函数最优值 min z=7非基变量的检验数=0，所以有无穷多最优解。两阶段法：第一阶段最优解X=（4/5，9/5，0，0，0，0 是基本可行解,min w=0第二阶段最优解（4/5，9/5，0，0，0，0 min z=7非基变量的检验数=0，所以有无穷多最优解。（3）解：大M法加入人工变量，化成标准型：Max z=10+15+12+0+0+0-Ms.t. 5+3+=9 -5+6+15+=15 2+-+=5,，,，0单纯形表计算略当所有非基变量为负数，人工变量=0.5，所以原问题无可行解。两阶段法（略）（4）解法一：大M法单
12、纯形法，（表略）非基变量的检验数大于零，此线性规划问题有无界解。两阶段法略1.7求下述线性规划问题目标函数z的上界和下界；Max z=+其中：，解：l 求Z的上界Max z=3+6s.t. -+212 2+414，0加入松弛变量，化成标准型，用单纯形法解的，最优解X=（0，7/2，5，0 目标函数上界为z=21存在非基变量检验数等于零，所以有无穷多最优解。l 求z的下界线性规划模型：Max Z=+4s.t. 3+58 4+610，0加入松弛变量，化成标准型，解得：最优解为X=（0，8/5，0，1/5 目标函数下界是z=32/51.8表1-6是某求极大化线性规划问题计算得到的单纯形表。表中无人工
13、变量，d，为待定常数，试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）该线性规划问题具有无界解；（4）表中解非最优，对解改进，换入变量为，换出变量为。基b d4100 2-1-301-10 3-500-4100-30解：（1）有唯一最优解时，d0，0，0（2）存在无穷多最优解时，d0，0，=0或d0，=0，0.（3）有无界解时，d0，0，0且（4）此时，有d0，0并且，3/d/41.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下：班次时间所需人数16点到10点60210点到14点70314点到18点60418点到
14、22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解 ：设（k=1，2，3，4，5，6）为个司机和乘务人员第k班次开始上班。建立模型：Min z=+s.t. +60+70+60+50+20+30,01.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B1.52500C20%60%50%112
15、00加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。解:解：设，是甲糖果中的A，B，C成分，是乙糖果的A，B，C成分，是丙糖果的A，B，C成分。线性规划模型：Max z=0.9+1.4+1.9+0.45+0.95+1.45-0.05+0.45+0.95s.t. -0.4+0.6+0.60 -0.2-0.2+0.80 -0.85+0.15+0.150 -0.6-0.6+0.40 -0.7-0.5+0.50+2000+2500+1200,01.11某厂生产三种产品I、III。每种产品经过AB两道加工程序，该厂有两种设备能完成
16、A工序，他们以,表示；有三种设备完成B工序，分别为，；产品I可以在AB任何一种设备上加工，产品可以在任何规格的A设备上加工，但完成B工序时，只能在设备上加工；产品III只能在，上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用IIIIII5106000300791210000321684000250411700078374000200原料费0.250.350.5单价1.252.002.8解：产品1，设,完成A工序的产品，件；B工序时，,，完成B工序的，件，产品，设,完成A工序的产品，件；B工序时，完成B的产品为件；产品111，完成A工序的件，
17、完成B工序的件；+=+ = 建立数学模型：Max z=(1.25-0.25)*(+)+(2-0.35)*(+ )+(2.8-0.5) -(5+10)300/6000-(7+9 +12 )321/10000-(6+8 )250/4000-(4+11 )783/7000-7*200/4000s.t 5+1060007+9 +12 100006+8 40004+11 700074000+=+ = ,0最优解为X=（1200，230，0，859，571，0，500，500，324 最优值1147.试题：1. （2005年华南理工大学）设某种动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素
18、。现有5种饲料可供选择，每种饲料每公斤营养成分的含量及单价如下表所示：试建立既满足动物生长需要，又使费用最省的选用饲料方案的线性规划模型。表 11饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310.50.2220.510.7310.20.20.446220.35180.50.80.8解题分析：这是一道较简单的数学规划模型问题，根据题意写出约束即可。解题过程：第二章（67页）2.1用改进单纯形法求解以下线性规划问题。（1）Max z=6-2+32-+32+44，0（2）min z=2+3+=34+36+23,0解：（1）先化成标准型：Max z=6-2+3+0+0s.t. 2-+
19、2+=2+4+=4,0令=（，）=（,=(0,0)=(,)= ,=（，=(6,-2,3)，=,=非基变量的检验数=-=(6,-2,3)因为的检验数等于6，是最大值，所以，为换入变量，=；=由规则得：=1为换出变量。=(，)=,=（,，=(6,0).=(,), =（，=(0，-2，3)，=,=非基变量的检验数 =（-3，1，-3）因为的检验数为1，是正的最大数。所以为换入变量；=由规则得：=6所以是换出变量。=(，)=,=（,，=(6,-2).=(,，), =（，=(0，0，3)，=,=非基变量的检验数 =（-2，-2，-9）非基变量的检验数均为负数，愿问题已达最优解。最优解X= 即：X=（4,
20、6,0目标函数最优值 max z=12（2） 解 ：Min z=2+0+M+M+0S.T. 3+=34+3-+=6+2+=3,0M是任意大的正数。（非基变量检验数计算省略）原问题最优解是X=（0.6，1.2，0）目标函数最优值： z=12/52.2已知某线性规划问题，用单纯形法计算得到的中间某两步的加算表见表，试将空白处数字填上。354000b58/32/3101/300014/3-4/305-2/310020/35/304-2/301-1/304-5/300.15/418/41-10/41-6/415/414/41-2/41-12/4115/41-解：354000b58/3014/3020/
21、3-.580/4101015/41450/41001-6/41344/41100-2/41-000-45/412.3写出下列线性规划问题的对偶问题。（1）min z=2+2+4 2+3+523+73+4+65,0（1）解：对偶问题是：Max w=2-3-5s.t. 2-3-2 3-42 5-7-64,0(2)max z=+2+3+4 -+-3=56+7+3-5812-9-9+920,0;0;无约束解：对偶问题：Min w=5+8+20S.t. -+6+121+7-92 -+3-93 -3-5+9=4无约束，0；0（3）min z= i=1,m j=1,n0解：对偶问题: max w=+s.t.
22、 +, 无约束 i=1,2,.m; j=1,2,.n(4)Max z=, i=1,., i=0,当j=1，.，无约束，当j=解：Min w=s.t. j=1,2,3 j=+1, +2,.n0 i=1,2.无约束， i=+1, +2.m2.4判断下列说法是否正确，并说明为什么.(1)如线性规划问题的原文题存在可行解，则其对偶问题也一定存在可行解。（2）如线性规划的对偶问题无可行解，则原问题也一定无可行解。（3）如果线性规划问题的原问题和对偶问题都具有可行解，则该线性规划问题一定有有限最优解。(1)错误，原问题有可行解，对偶问题可能存在可行解，也可能不存在；（2）错误，对偶问题没有可行解，原问题可
23、能有可行解也可能有无界解；（3）错误，原问题和对偶问题都有可行解，则可能有有限最优解也可能有无界解；2.5设线性规划问题1是：Max = ，i=1，2，m（）是其对偶问题的最优解。又设线性规划问题2是Max + ，i=1，2，m其中是给定的常数，求证：+解：证明：把原问题用矩阵表示：Max =CXs.t. AXb X0b=（,.设 可行解为,对偶问题的最优解=（， ）已知。Max =CXs.t. AXb+k X0k=（,.设可行解为，对偶问题最优解是,对偶问题是，Min w=Y(b+k)S.t. YAC Y0因为是最优解，所以（b+k）（b+k）是目标函数的可行解，Ab+k ；A（b+k）b+
24、Yk原问题和对偶问题的最优函数值相等，所以不等式成立，证毕。2.6已知线性规划问题 Max z=用单纯形法求解，得到最终单纯形表如表所示，要求：（1） 求，的值；（2） 求的值；3/21011/2-1/221/210-12-3000-4解：（1）初始单纯形表的增广矩阵是：=最终单纯形表的增广矩阵为=是作初等变换得来的，将作初等变换，使得的第四列和第五列的矩阵成为的单位矩阵。有：=9/2； =1； =4； =5/2； =1； =2；=9； =5由检验计算得：=-3； =02.7已知线性规划问题Max z=2+5+6s.t. 2+82+2+2120，j=1,4对偶变量，其对偶问题的最优解是=4，试
25、应用对偶问题的性质，求原问题的最优解。解：对偶问题是：Min w=8+12s.t. 2+22 21+5+26，0互补松弛性可知，如，是原问题和对偶问题的可行解，那么，=0和=0，当且仅当，是最优解。设 X,Y是原问题和对偶问题的可行解，=（，）有：Y=0; 且 X=0=0，原问题约束条件取等号，=4；=4最优解X=（0，0，4，4 目标函数最优值为44。2.8试用对偶单纯形法求解下列线性规划问题。（1）min z=+ 2+4+77,0(2) min z=3+2+42+4+5+03-+7-225+2+1015,0解：（1）取w=-z，标准形式：Max w=-+0+0s.t. -2-+=-4-7+
26、=-7，0单纯形法求解（略）：最优解：X=（21/13，10/13，0，0 目标函数最优值为31/13。（2）令：w=-z，转化为标准形式：Max w=-3-2-4+0+0+0s.t.-2-4-5-+=0-3+-7+2+=-2-5-2-6+=-15，0单纯形法略原问题最优解：X=（3，0，0，0，6，7，0 目标函数最优值为9。2.9现有线性规划问题max z=-5+5+13-+32012+4+1090，0先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化？（1） 约束条件1的右端常数20变为30（2） 约束条件2的右端常数90变为70（3） 目标函数中的系数变为8（4）
27、的系数向量变为（5） 增加一个约束条件2+3+550（6） 将约束条件2变为10+5+10100解： 把原问题化成标准型的：Max z=-5+5+13+0+0s.t-+3+=2012+4+10+=90，0单纯形法解得：最优解：X=（0，20，0，0，10 目标函数最优值为100。非基变量的检验数等于0，原线性问题有无穷多最优解。（1）约束条件的右端常数变为30有 因此 单纯形法解得：最优解：X=（0，0，9，3，0 目标函数最优值为117。（2）约束条件右端常数变为70 有 因此 单纯形法解得，最优解：X=（0，5，5，0，0目标函数最优值为90。（3）的系数变成8，是非基变量，检验数小于0，
28、所以最优解不变。（4）的系数向量变为是非基变量，检验数等于-5，所以最优解不变。（5）解：加入约束条件用对偶单纯形表计算得：X=（0，25/2，5/2，0，15，0目标函数最优值为95。（6）改变约束条件，没有变化，线性规划问题的最优解不变。2.10已知某工厂计划生产I,II,III三种产品，各产品在ABC设备上加工，数据如下表，设备代号IIIIII每月设备有效台时A8210300B1058400C21310420单位产品利润/千元322.9（1）如何充分发挥设备能力，使生产盈利最大？（2）如果为了增加产量，可借用其他工厂的设备B，每月可借用60台时，租金为1.8万元，问借用是否合算？（3）若
29、另有两种新产品IV,V，其中IV为10台时，单位产品利润2.1千元；新产品V需用设备A为4台时，B为4台时，C为12台时，单位产品盈利1.87千元。如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否划算？（4）对产品工艺重新进行设计，改进结构，改进后生产每件产品I，需要设备A为9台时，设备B为12台时，设备C为4台时，单位产品利润4.5千元，问这对原计划有何影响？解：（1）设：产品三种产品的产量分别为，建立数学模型：Max z=3+2+2.9s.t. 8+2+1030010+5+84002+13+10420,0把上述问题化为标准型，用单纯形法解得：最优解：X=（338/15，11
30、6/5，22/3，0，0，0目标函数最优值为2029/15。（2）设备B的影子价格为4/15千元/台时，借用设备的租金为0.3千元每台时。所以，借用B设备不合算。（3）设备,V生产的产量为，系数向量分别为：检验数=-0.06，所以生产不合算，=37/300，生产V合算。单纯形法计算得：最优解：X=（107/4，31/2，0，0，0，0，55/4目标函数最优值为10957/80。（4）改进后,检验数=253/300，大于零。所以，改进技术可以带来更好的效益。2.11分析下列参数规划中当t变化时最优解的变化情况。（1）Max =(3-6t)+(2-2t)+(5-5t) (t0)s.t. +2+43
31、03+2460+4420，0（2）Max =(7+2t)+(12+t) +(10-t) (t0)s.t. +202+2+30，0（3）Max =2+ (0 t 25)s.t. 10+2t+25-t10+2t，0（4）Max =21+12+18+15 (0 t 59)s.t. 6+3+6+330+t6-3+12+678-t9+3-6+9135-2t，0解：（1）化成标准形式：Max =(3-6t)+(2-2t)+(5-5t)+0+0+0 (t0)s.t. +2+=4303+2+=460+4+=420，, 0令t=0，用单纯形表计算，3-6t2-2t5-5t000B2-2t100-1/4100.5
32、-1/40-5-5t2303/20101/20460020200-21120-z1350t-1350t-400t-12t-20t增大，t大于1，首先出现，大于0，所以当0t1时有最优解。X=（0，100，230，0，0，20目标函数最优值为1350（t-1） （0t1）。t=1是第一临界点。t大于1时，是换出变量。t大于1，最优解是：X=（0，0， 0，430，460，420目标函数最优值为Max =0， （t大于1）（2）化成标准型，然后令t=0，单纯形法解得：t开始增大时，当t大于8/3时，首先出现大于0，所以0t8/3，得最优解。目标函数最优值Max =220，（0t8/3）所以，t=8
33、/3为第一临界点。当8/3t5，首先大于0，8/3t5的时候，最优解为：X=（0，15，0，5目标函数最优值为180+15t ，（8/35时，是换入变量，为换出变量，单纯性法计算，当t继续增大，所有检验数都非正，所以当t5，最优解：X=（15，0，0，5目标函数最优值为105+30t， t0(3)化成标准型，令t=0,用单纯形法计算得：当t开始增大，t大于5时，首先出现小于0，当0t5，最优解为：X=（10+2t，0，10+2t，5-t，0目标函数最优值为6t+30 ，（0t5）。所以t=5是第一临界点。当t大于5时，是换出变量，是换入变量。用对偶单纯形法计算，当t大于5时，最优解为：X=（1
34、0+2t，15+t，0，0，t-5目标函数最优值为35+5t。（4）解：先化为标准型，令t=0，用单纯形法计算，得：当t开始增大，当t大于6时，首先出现小于0，当0t6，有最优解：X=（0，0，0，10+t/3，0，18-3t，45-5t目标函数最优值为150+5t （0t6）。当t大于6时，首先出现小于0，是换出变量，是换入变量，使用单纯形法计算得：t继续增大，当t大于11时，首先小于零，是换出变量，为换入变量，对偶单纯形法迭代得：当 t59，有最优解：X=（0，t/3-2，t/8-11/8，59/4-t/4，0，0，0目标函数最优值为5t/2+345/2 ，（11t59）。试题：1. （2
35、006年西北工业大学）已知线性规划：（1） 用单纯形法求解该线性规划问题的最优解和最优值；（2） 写出线性规划的对偶问题；（3） 求解对偶问题的最优解和最优值。解题分析：本题考察了线性规划与对偶问题的知识，要求读者熟知对偶理论。解题过程：，有无穷多解。对偶问题为：2. （2005年东南大学）写出如下线性规划问题的对偶问题：无限制并利用弱对偶性说明的最大值不大于1。解题过程：原问题的对偶问题为：由于（0，1，0）是上述对偶问题的可行解，由弱对偶性可知，对原问题的任一可行解都有 而，所以的最大值不大于1。第三章（86页）3.1判断表中给出的调运方案能否作为用表上作业法求解时的最初解？为什么？表31
36、销地产地1234产量1015152151025355销量5151510表32销地产地12345产量1150250400220030050032505030049021030058020100销量24041055033070解：表31中，有5个数字格，作为初始解，应该有m+n-1=3+4-1=6个数字格，所以表3-1的调运方案不能作为用表上作业法求解时的初始解。表3-2中，有10个数字格，而作为初始解，应该有m+n-1=9个数字格，所以表3-2的调运方案不能作为表上作业法的初始解。3.2表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。表3-3 销地产地123产量15181222411433674销量91011表3-4 销地产地12345产量11023159252520152430315514715204201513M830销量2020301025解：（1）在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到： 销
