试题2答案.doc

运筹学答案与评分标准（试题2）一、（30分）给出线性规划问题：max st.用单纯形法求最优解，写出最终单纯形表。试分析下列各种条件下最优解（基）的变化：（1）目标函数中变量x3的系数变为5 ；（2）分别确定目标函数中变量x1的系数c1在什么范围内变动时最优解不变；（3）约束右端项由变为；解：将线性规划问题化为：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的系数变为5 时，得如下单纯形表，并用单纯形法求解步骤进行计算，其过程如下：cj23500CB基bx1x2x3x4x52x1110-14-13x22012-11cj- zj001-5-1因20，所以选x3进基，因20，故选x2出基，则得cj23500CB基bx1x2x3x4x52x1211/207/2-1/25x3101/21-1/21/2cj- zj0-1/20-5/4-3/2得最优解为：（2，0，1），代入目标函数得z = 9 。（5分）（2）设目标函数中变量x1的系数为c1，则由原单纯形表得如下单纯形表：cjc13100CB基bx1x2x3x4x5c1x1110-14-13x22012-11cj- zj00c1-53-4c1c1-3若要保持原问题最优解不变，则应有所有检验数均小于等于0；即 即 （5分）（3）约束右端项由变为；有 = 将上述结果反映到单纯形表中得：cj23100CB基bx1x2x3x4x52x1010-14-13x23012-11cj- zj00-3-5-1此时，上表中的解仍为可行解，故最优解为：（0，3，0），代入目标函数得z = 9 。（5分）评分标准：1. 单纯形法求最优解15分，若结果不正确，但步骤正确可得10分。2.（1）、（2）（3）小题各5分。3. 其他情况酌情给分。二、（10分）已知线性规划问题求：（1）写出其对偶问题；（5分）（2）直接写出对偶问题的最优解。（5分）解：该问题的对偶问题为： 由对偶问题性质可知： 解之得： 所以Y*=（0，-2）T Max Z=-4 评分标准：写出对偶问题得5分，求解得5分，其他情况酌情给分。三、（15分）已知某运输问题如下（单位：百元/吨）：单位运价 销地产地B1B2B3供应量（吨）A137218A2581012A394515需求量（吨）161217求：（1）使总运费最小的调运方案和最小运费。（12分）（2）该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再求出一个最优调运方案来。（3分）解：（1）用伏格尔法确定初始调运方案为：B1B2B3供A111718A21212A331215需16121712=9；22=0；23=6；33=-3 （5分）有ij0,所以需要调整为：B1B2B3供A141418A21212A312315需16121712=6；22=5；23=6；31=3 （5分）因为ij0， 所以为最优方案。 Min Z=3*4+2*14+12*5+12*4+3*5=163 为唯一最优解。 （2分）（2）无，因为ij0，所以该题仅有唯一最优方案。 （3分）评分标准：1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。四、（10分）某市准备在下一年度预算中购置一批救护车，已知每辆救护车购置价为20万元。救护车用于所属的两个郊区县，各分配x1台和x2台。1县救护站从接到电话到救护车出动的响应时间为40-3x1 min，2县相应的响应时间为50-4x2 min。该市确定如下优先级目标：P1：用于救护车购置费用不超过400万元；P2：1县的响应时间不超过5min；P3：2县的响应时间不超过5min。建立求解该问题的目标规划模型。解：其目标规划模型为：评分标准：1. 本题主要考察学生对目标规划的理解。2.求出目标规划的模型得10分。3. 其他情况酌情给分。五、（15分）甲、乙、丙、丁四人加工A、B、C、D四种工件所需时间（分钟）如下表所示。应指派何人加工何种工件，能使总的加工时间最少？工件人ABCD甲149415乙117910丙132105丁1791513工件人ABCD甲149415乙117910丙132105丁1791513解：使用匈牙利方法求上述指派问题的最优解。第一步:变换系数矩阵。（5分）6508002070804061第二步:确定独立零元素。（8分）658278461已经找到4个独立的零元素，故可以确定指派问题的最优指派方案。即甲去加工C工件, 乙去加工A工件, 丙去加工D工件, 丁去加工B工件；其总的加工时间最少，为：4 + 11 + 5 + 9 = 29 。（2分）评分标准：1. 本题主要考察学生指派问题的应用。2.变换系数矩阵得5分，求最优解给8分，得出结论给2分，若结果不正确，但步骤正确可得8分。3. 其他情况酌情给分。六、（20分）某工厂生产三种产品，每种产品重量与利润关系如下表所示。现将此三种产品运往市场出售，运输能力总重量不超过10t，问如何安排运输使总利润最大？种类重量（t/件）利润（元/件）121002314034180解：设第i种产品装载的件数为xi(i=1,2,3) 。则问题可表示为：max 建立动态规划模型，由于决策变量取离散值，所以可用列表法求解。当k=1时，计算结果见下表：S2012345678910f1(s2)00100100200200300300400400500x1*00112233445当k=2时，计算结果见下表S301234567x20000 10,10, 10,1,20,1,2C2+f100100100,140200,140200,240300,240,280300,340,280f2(s3)00100140200240300340x2*00010101S38910x20,1,2,0,1,2,3,0,1,2,3,C2+f1400,340,380400,440,380,420500,44,480,420f2(s3)400440500x2*010当k=3时，=m