……… … … … … … 名…姓…… … … … 密 … … … 号…学…… … 级… … 封 … … …业…专… … … … … 线 … … … 院…学…… … … … … … … … 山东大学 管理运筹学 本科 课程试卷 试卷三 学年 学期 一、 名词解释 三、计算题 1.解：（1）加入人工变量x4,x6 ，减去剩余变量x5 得到该线形规划问题的标准型 1. 可行域：所有可行解的集合。 2. 策略：一个按时间或空间次序排列的决策序列的集合。 maxz?2x3. 连通图：任何两点之间至少存在一条链的图称为连通图。 1?3x2?5x3?Mx4?Mx6 4. 截量：截集上的容量和称为截量，记为C(V1 ,V2)。 ? ?x1?x2?x3?x4?7二、 简答题 ?2x1?5x2?x3?x5?x6?10 ?1.答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利?x1,x2,x3,x4,x5,x6?0用检验数?（2）利用单纯形表逐步迭代 j对初始基可行解进行最优性检验，若?j?0 ，则求得最优解，否则，Cj 2 3 -5 -M 0 -M 比值 进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得CB XB b x1 x2 x3 x4 x5 x6 新的基本可行解；（5）重复步骤（3）、（4）直至?-M x4 7 1 1 1 1 0 0 7 j?0，求得最优解为止。 -M x6 10 [2] -5 1 0 -1 1 5 2.答：分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数2M-5 0 -M 0 条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划?3M+2 3-4M j 的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断-M x4 2 0 [7/2] 1/2 1 1/2 -1/2 4/7 缩小整数规划的上下界的距离，最后得整数规划的最优解。 2 x1 5 1 -5/2 1/2 0 -1/2 1/2 - 3.答：（1）最优解不一定在顶点上达到；（2）最优解不一定是松弛问题最优解的?0 3M/2+8 M/2-6 0 M/2+1 -3M/2-1 j 邻近整数解；（3）整数可行解远多余于顶点，枚举法不可取；（4）整数规划的3 x2 4/7 0 1 1/7 2/7 1/7 -1/7 最大函数值小于或等于相应的线性规划的最大目标函数值；（5）整数规划的最2 x1 45/7 1 0 6/7 5/7 -1/7 1/7 小目标函数值大于或等于相应的线性规划的最小目标函数值。 ?j 0 0 -50/7 -M-16/7 -1/7 -M+1/7 4答：（1）绘制计划网络图；（2）从网络的始点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（EF) ；（3）从网络的终点开始，计算出在最优解X*?(45/7,4/7,0,0,0)T,z*?102/7 不影响整个工程最早结束时间的情况下，各个工序的最晚开始时间(缩写为LS)2.解：用逆序算法。设 和最晚结束时间（缩写为LF)；（4）计算出每一个工序的时差TS；（5）时差等 （1）阶段：每个研究小组为一个阶段，该问题分3个阶段： 于零的工序为关键工序。把关键工序依次从始点到终点连接成的路线确定为关 阶段 1 2 3 键线路。 小组 1 2 3 （2）决策变量xn：分配给第n小组的高级科学家数目，相应的失败概率为 Pn(xn)； （3）状态变量sn：在阶段n时可分配于阶段n，n-1，…，1的高级科学家人数。 递推关系： 第 页 共 页
山东大学网络教育运筹学试卷三参考答案期末考试复习题
