运筹学试题4答案.doc

运筹学答案与评分标准（试题4）一、（30分）给出线性规划问题：max st.用单纯形法求最优解，写出最终单纯形表。试分析下列各种条件下最优解（基）的变化：（1）目标函数中变量x3的系数变为6 ；（2）约束右端项由变为；（3）增加一个新的变量x6，, c6 = 7 ；解：将线性规划问题化为：max st. （3分）因此，可得如下初始单纯形表：（5分）cj23100CB基bx1x2x3x4x50x411/31/31/3100x531/34/37/301cj- zj23100因321，所以选x2进基，因3/(4/3)1/(1/3)，故选x5出基，则得cj23100CB基bx1x2x3x4x50x41/41/40-1/41-1/43x29/41/417/403/4cj- zj5/40-17/40-9/4因5/40，所以选x1进基，因(1/4)/(1/4)(9/4)/(1/4)，故选x4出基，则得cj23100CB基bx1x2x3x4x52x1110-14-13x22012-11cj- zj00-3-5-1最优解为：（1，2，0）。（7分）（1）目标函数中变量x3的系数变为6 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下：cj23600CB基bx1x2x3x4x52x1110-14-13x22012-11cj- zj002-5-1因20，所以选x3进基，因20，故选x2出基，则得cj23600CB基bx1x2x3x4x52x1211/207/2-1/26x3101/21-1/21/2cj- zj0-10-4-2得最优解为：（2，0，1），代入目标函数得z = 10 。（5分）（2）约束右端项由变为；有 = 将上述结果反映到单纯形表中得：cj23100CB基bx1x2x3x4x52x1510-14-13x21012-11cj- zj00-3-5-1此时，上表中的解仍为可行解，故最优解为：（5，1，0），代入目标函数得z = 13 。（5分）（4）增加一个新的变量x6，, c6 = 7 ；检验数 c6- z6 = 7 - 3*2 = 1 ，将上述结果反映到单纯形表中得：cj231007CB基bx1x2x3x4x5x6 2x1110-14-133x22012-110cj- zj00-3-5-11因x6的检验数10，所以原最优解已经不是新问题的最优解；选x6进基，因30，故选x1出基，则得cj231007CB基bx1x2x3x4x5x6 7x61/31/30-1/34/3-1/313x22012-110cj- zj-1/30-8/3-19/3-2/30故最优解为：（0，2，0，0，0，1/3），代入目标函数得z = 6 + 7/3 = 25/3 。（5分）评分标准：1. 单纯形法求最优解15分，若结果不正确，但步骤正确可得10分。2.（1）、（2）（3）小题各5分。3. 其他情况酌情给分。二、（15分）甲、乙、丙三个城市每年需要煤炭分别为320、250、350万吨，由A、B两处煤矿负责供应。已知煤炭年供应量分别为A-400万吨，B-450万吨。由煤矿至各城市的单位运价（万元/万吨）如下表，由于需大于供，经研究平衡决定，甲城市供应量可减少0-30万吨，乙城市需求量应全部满足，丙城市供应量应不少270万吨。试求供应量分配完又能使总运费为最低的调运方案。甲乙丙A151822B212516评分标准：1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。三、（10分）写出线性规划问题的对偶问题。解：其对偶问题为 评分标准：写出对偶问题的模型即可得10分。四、（10分）某科学试验卫星拟从下列仪器装置中选若干件装上。有关数据资料见下表。要求：（1）装入卫星的仪器装置总体积不超过V，总重量不超过W；（2）A1与A3中最多安装一件；（3）A2与A4中至少安装一件；（4）A5与A6或者都安上，或者都不安。总的目的是装上去的仪器装置使该科学卫星发挥最大的试验价值。试建立这个问题的数学模型。装置代号体积重量试验价值A1V1W1C1A2V2W2C2A3V3W3C3A4V4W4C4A5V5W5C5A6V6W6C6解：此问题的数学模型为：评分标准：模型正确即可得10分，其他情况酌情给分。五、（15分）用匈牙利法求解典型指派问题，已知效率矩阵如下： 4931149831087538695346101171011解：评分标准：1. 本题主要考察学生指派问题的应用。2.变换系数矩阵得5分，求最优解给8分，得出结论给2分，若结果不正确，但步骤正确可得8分。3. 其他情况酌情给分。六、（20分）某工厂生产三种产品，每种产品重量与利润关系如下表所示。现将此三种产品运往市场出售，运输能力总重量不超过8t，问如何安排运输使总利润最大？种类重量（t/件）利润（元/件）121002314034180种类重量（t/件）利润（元/件）121002314034180种类重量（t/件）利润（元/件）121002314034180解：设第i种产品装载的件数为xi(i=1,2,3) 。则问题可表示为：max 建立动态规划模型，由于决策变量取离散值，所以可用列表法求解。当k=1时，计算结果见下表：S2012345678f1(s2)00100100200200300300400x1*001122334当k=2时，计算结果见下表S3012345678x20000 10,10, 10,1,20,1,20,1,2,C2+f100100100,140200,140200,240300,240,280300,340,280400,340,380f2(s3)00100140200240300340400x2*000101010当k=3时，=max400,180+200,360