《管理运筹学卷二参考答案》20年春山东大学辅导题目

一、名词解释
1. 最优解：在可行域中使目标函数达到最优的可行解。
2. 策略：一个按时间或空间次序排列的决策序列的集合。
3.        连通图：任何两点之间至少存在一条链的图称为连通图。
4.        增广链：f为一可行流，u为vs至vt的链，令u+=  正向弧，u-= 反向弧 。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。
二、简答题
1.        答：（1）把一般线形规划模型转换成标准型；（2）确定初始基可行解；（3）利用检验数 对初始基可行解进行最优性检验，若  ，则求得最优解，否则，进行基变换；（4）基变换找新的可行基，通过确定入基变量和出基变量，求得新的基本可行解；（5）重复步骤（3）、（4）直至 ，求得最优解为止。  
2.        答：分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件，则求出整数规划的上下界，用增加约束条件的办法，把相应的线性规划的可行域分成子区域（称为分枝），再求解这些子区域上的线性规划问题，不断缩小整数规划的上下界的距离，最后得整数规划的最优解。
3.        答：对于n阶段的动态规划问题，在求子过程上的最优指标函数时，k子过程与k+1过程有如下递推关系：
对于可加性指标函数，基本方程可以写为
终端条件：fn+1 (sn+1) = 0
对于可乘性指标函数，基本方程可以写为
终端条件：fn+1 (sn+1) = 1
4答：（1）绘制计划网络图；（2）从网络的始点开始，按顺序计算出每个工序的最早开始时间（ES )和最早结束时间（EF) ；（3）从网络的终点开始，计算出在不影响整个工程最早结束时间的情况下，各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF)；（4）计算出每一个工序的时差TS；（5）时差等于零的工序为关键工序。把关键工序依次从始点到终点连接成的路线确定为关键线路。
三、计算题
1.解：（1）加入松弛变量 ,  得到该线形规划问题的标准型
（2）利用单纯形表逐步迭代
Cj        2        5        0        0        0        比值
CB        XB        b        x1        x2        x3        x4        x5       
0        x3        4        1        0        1        0        0        -
0        x4        12        0        [2]        0        1        0        6
0        x5        18        3        2        0        0        1        9
2        5        0        0        0       
0        x3        4        1        0        1        0        0        4
5        x2        6        0        1        0        1/2        0        -
0        x5        6        [3]        0        0        -1        1        2
2        0        0        -5/2        0       
0        x3        2        0        0        1        1/3        -1/3       
5        x2        6        0        1        0        1/2        0       
2        x1        2        1        0        0        -1/3        1/3       
0        0        0        -11/6        -2/3