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

运筹学 试卷B一、名词解释〔3×5=15〕1.可行基 2.阶段变量 3.决策变量 4.时差 5.偏差变量二、推断题〔1×10=10〕线性规划问题的根本解对应可行域的顶点。假设 、 是某线性规划问题的最优解，则 也是该问题的最优解。用单纯形法求解标准型的线性规划问题时，假设存在界解〕。

，且该列系数 ，则线性问题最优解不存在〔无假设线性规划的可行域是空集，则说明存在冲突的约束条件。

时，即可判定表中的解为最优解。用大M法处理人工变量时，假设最终单纯形表上基变量中仍含人工变量，则原问题无可行解。线性规划原问题的对偶问题是原问题。线性规划原问题无可行解，其对偶问题必无可行解。线性规划原问题存在可行解，其对偶问题必定存在可行解。在目标线性规划问题中，正偏差变量取正值，负偏差变量取负值。三、线性规划问题(10某线性规划问题的初始单纯行表〔见表1〕和用单纯形法迭代后得到的表〔见表2〕如下，试求括弧中未知数1

的值。xxbi6101-13012200xbi〔f〕xbi〔f〕2-11/20411/21-7四、线性规划的最终单纯形表〔3〕〔10〕3250101/21/2131000103001-1/23/2〔1〕写出其对偶问题。000-1-2解出对偶问题最优解。写出最优基矩阵及其逆矩阵 。五、线性规划问题〔20〕用单纯形法求得最优解的单纯形表〔见表4〕。试分析在以下各种条件单独消灭的状况下，最优解将如何变化。424/3012/3-1/300310/310-1/32/3000300-111002/300-2/31/30100-1/3-4/300第①、②两个约束条件的右端项分别由6784；增加一个变量 ,其在目标函数中系数 =4，在约束方程中的系数列向量为 ;增加一个的约束条件 。六、求解以下运输问题使总运费最低〔方框内数字为运价〕〔10分〕七、目标规划问题〔10〕用图解法找出以下目标规划问题的满足解八、网络图计算〔15〕工序紧前工序工序时间〔天〕工序紧前工序工序时间〔天〕a—10hf10b—8if4ca,b6jg12db16kh,i,j16ec24lc8fd,e4mｌ24gf4nk,m4要求：绘制网络图。计算各工序的最早开工时间、最早完工时间、最迟开工时间、最迟完工时间。计算各工序的总时差。确定关键路线。一、名词解释〔5×3=15〕可行基：对应于基可行解的基称为可行基。阶段变量：动态规划中，按时间段或空间特征分解成假设干相互联系的阶段，表示阶段的变量称为阶段变量。决策变量：在动态规划中，表示决策的变量叫做决策变量。时差：网络规划中，工作的机动时间或富有时间叫做时差，分为总时差和单时差。偏差变量：在目标规划中，对于每一个决策目标，引入的正、负变量d+、d-称为偏差变量。二、推断题〔10×1=10〕123.45.678910．错三、线性规划问题(10解：此题目虽然没有给出目标函数中各个变量的系数，但由于题目不涉及求目标函数值，故可以认为此问12〔2〕〔3〕〔2〕由以上等式得出一个线性方程组。留意到表中是基变量的检验数，而向量，所以=0，h=0。解此方程组，得到：〔3〕

是第一个基变量 的系数四、线性规划的最终单纯形表〔3〕〔10〕对偶规划为：〔4〕对偶问题最优解为：〔4〕〔3〕 〔2〕五、线性规划问题〔20〕由于：所以：最终单纯形表变为：210/3012/3-1/30031/310-1/32/3000-200[-1]1100-4/300-2/31/30100-1/3-4/300220101/32/30311001/3-1/3002001-1-1000000-1/3-2/31000-5/3-1/30最优解为： 。〔7分〕在最终表中的检验数为：而故最终单纯形表为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此时题目有无穷多最优解，其中之一为 。〔8分〕原问题的最优解满足增加的约束条件 ,所以最优解不变，仍旧为 〔5分〕六、运输问题〔10〕由表可知产量=销量，供需平衡。用最小元素法确定的初始调运方案为：承受闭回路法进展计算，得出确定值最大的负检验数为 ,沿着闭回路动身进展调整后的表为：即当

是唯一的检验数，然后沿着闭回路动身进展调整，调整后的表为：时为最优，最小费用为155个单位。七、目标规划问题〔10〕系统约束确定的范围为第一象限，第一优先级目标优化后得区域直线①、OX2、OX1所围成的开区域，其次优先级目标优化后得凸集OABC，第三级优化后得到凸集OABED，此凸集内的点均为满足解。〔2〕八、网络计算〔15〕〔1〕画出网络图如下图：〔8〕〔2〕〔3〕表上计算：〔6〕最早开最早完最迟开最迟完工序a工时间0工时间10工时间0工时间10总时差0b082102c101610160d824244016e164016400f404440440g44484