中国石油大学运筹学期末试题B.doc

运筹学试卷B一、名词解释（3U5=15分）4.时差5.偏差变量1. 可行基2.阶段变量3.决策变量二、判断题（1叮0=10分）1.线性规划问题的基本解对应可行域的顶点2叮珞、迤是某线性规划问题的最优解，则+(l-^)X2(0<1)也是该问题的最优解3．用单纯形法求解标准型的线性规划问题时，若存在er-=ci-zi>0，且该列系数Pi<0，则线性问题最优解不存在（无界解）4．用单纯形法求解标准型的线性规划问题时，当所有的检验数时，即可判定表中的解为最优解5．若线性规划的可行域是空集，则表明存在矛盾的约束条件6口用大M法处理人工变量时，若最终单纯形表上基变量中仍含人工变量，则原问题无可行解7．线性规划原问题的对偶问题是原问题8．线性规划原问题无可行解，其对偶问题必无可行解9．线性规划原问题存在可行解，其对偶问题必定存在可行解10．在目标线性规划问题中，正偏差变量取正值，负偏差变量取负值三、线性规划问题（10分）已知某线性规划问题的初始单纯行表（见表1）和用单纯形法迭代后得到的表（见表2）如下，试求括弧中未知数的值表1xbi6101-1301200表2xbi□f)2-11/20411/21-73）（10分）表3250101/21/2131000103001-1/23/2000-1-2四、已知线性规划的最终单纯形表（见表（1）写出其对偶问题。

2）解出对偶问题最优解3）写出最优基矩阵B及其逆矩阵五、已知线性规划问题（20分）已知用单纯形法求得最优解的单纯形表(见表十2疋空<62zl+<8-^+a2<1乜乞2①②③④24/3012/3-1/300310/310-1/32/3000300-111002/300-2/31/30100-1/3-4/3004)试分析在下列各种条件单独出现的情况下，最优解将如何变化表46变成7，由8变成4；(1)第①、②两个约束条件的右端项分别由(2)增加一个变量心，其在目标函数中系数=4，在约束方程中的系数列向量为(3)增加一个新的约束条件可兰厲六、求解下列运输问题使总运费最低(方框内数字为运价)(10分）七、目标规划问题(10分）用图解法找出下列目标规划问题的满意解min2-pxd:++-X］十2花十-=4用］-2x3+皿］一=4心十2x2+^3-^=Sx1?x2>0?00=U5八、网络图计算（15分）工序紧前工序工序时间（天）工序紧前工序工序时间（天）a—10hf10b—8if4ca,b6jg12db16kh,i,j16ec24lc8fd,e4mD24gf4nk,m4要求：（1）绘制网络图。

2）计算各工序的最早开工时间、最早完工时间、最迟开工时间、最迟完工时间3）计算各工序的总时差4）确定关键路线一、名词解释（5U3=15分）1. 可行基：对应于基可行解的基称为可行基2. 阶段变量：动态规划中，按时间段或空间特征分解成若干相互联系的阶段，表示阶段的变量称为阶段变量3. 决策变量：在动态规划中，表示决策的变量叫做决策变量4. 时差：网络规划中，工作的机动时间或富裕时间叫做时差，分为总时差和单时差d+、d-称为偏差变量5. 偏差变量：在目标规划中，对于每一个决策目标，引入的正、负变量二、判断题（10叮=10分）1.错2.对3.对4.错5.对6．错7．对8．错9．错10．错三、线性规划问题（10分）解：此题目虽然没有给出目标函数中各个变量的系数，但由于题目不涉及求目标函数值，故可以认为此问（1）对偶规划为：（1）对偶规划为：题目标函数中各个变量的系数即是表1检验数行的各个数记表2中的可行基为B，便得C—=—120,0)—0,0)-1矿％=<1/21/21)2分）^1/2（3分）<1/2OYbL：（1）对偶规划为：（1）对偶规划为：（2分）由以上等式得出一个线性方程组注意到表中是基变量的检验数，而.t是第一个基变量的系数向量，所以‘=0,h=0。

解此方程组，得到：（3分）（1）对偶规划为：（1）对偶规划为：abcdefghjkI32斗-2231055-3/2（1）对偶规划为：（1）对偶规划为：四、已知线性规划的最终单纯形表（见表3）（10分）（1）对偶规划为：mm①=2y1+7y2+范-2yi+y5芒1山+>271?72^3（4分）（2）对偶问题最优解为：「1-21B=2-10_010（3）五、已知线性规划问题（（4分）_01/21/2B'1=001_1-1/23/220分）（2分）（1）因为：所以：『2/3-1/3c2/3最终单纯形表变为：-1/32/31/3Wm+D10/3-33-5^2/3-2^210/3012/3-1/30031/310-1/32/3000-200[-1]1100-4/300-2/31/30100-1/3-4/300220101/32/30在最终表中的检验数为：最优解为：故最终单纯形表为（2）24/3012/3-1/3000310/310-1/32/30010300-1110402/300-2/31/301[2]00-1/3-4/300124/3012/3-1/3000331001/20-1/2005/3001/3-1/31-2041/300-1/31/601/21000-3/20-1/20此时题目有无穷多最优解，其中之一为x.=3,=4/3,x,=5/3,=1/3（3）原问题的最优解满足新增加的约束条件Xy

口8分)六、运输问题（10分）采用闭回路法进行计算，得出绝对值最大的负检验数为，沿着闭回路出发进行调整后的表为：由表可知产量=销量，供需平衡用最小元素法确定的初始调运方案为：、一销地*产地产霽2^1弘21410+J1P12g护1弘131P121加35^1如6P销量］4p24产地躺、产量申%210^1+J1Wy.：j1OPJj14^12^1Jj2"|1知销壘］4卩9P重新计算检验数，得出巧严-m是唯一的检验熱然后沿着厨回路出发5S行调整，调整后的表天h+J、J肖地d产地卜\E严*产量卅灵严1弘210^JJ」1•扣1W備」10<：'y->?14门1却6^加1销量户口］4=—重新计算检验数，得出是唯一的检验数，然后沿着闭回路出发进行调整，调整后的表为：即当巧1=3^13=1，巧4=5也1=1，也2=殳也3=6时为最优，最小费用为155个单位七、目标规划问题（10分）系统约束确定的范围为第一象限，第一优先级目标优化后得区域直线①、优先级目标优化后得凸集OABC,第三级优化后得到凸集0X2、0X1所围成的开区域，第二0ABED,此凸集内的点均为满意解口2分）八、网络计算（15分）（8分）（2）（3）表上计算：（6分）工序最早开工时间最早完工时间最迟开工时间最迟完工时间总时差a0100100b082102c101610160d824244016e164016400f404440440g444844480h445450606i4448566012j4860。