2017年沈阳师范大学数学与系统科学学院849线性规划考研题库
● 摘要
一、计算题
1． 分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代的每一步相当于图形上哪一个顶点。
（1）
（2）
（3）以（l ）为例，具体说明当目标函数中变量的系数怎样改变时，使满足约束条件的可行域的每 一个顶点，都有可能使目标函数值达到最优。
【答案】 （1）图解法
图
该线性规划问题的可行域如图所示。由图可知该线性规划的惟一最优解为对应于图上的点A 2，其最优目标函数值z*=33/4。
②单纯形法 引入松弛变量
用单纯形法逐步迭代，求解过程如表所示。
第 2 页，共 51 页
得该线性规划问题的标准型
表
故问题的最优解单纯形表第一步迭代得单纯形表第二步迭代得单纯形表第三步迭代得（2）①图解法
最优目标函数值z*=33/4。 对应于图中的的坐标原点; 对应于图中的点A 3（4，0）; 对应于图1-5中的点A2（15/4，3/4）。
图
该线性规划的可行域如图所示，由图知该线性规划的惟一最优解为，最优目标函数值为的点A 2（2，6）
②单纯形法
在上述问题的约束条件中引入松弛变量x 3，x 4，x 5，得到该规划问题的标准型
，对应于图上
利用单纯形表进行迭代计算如表所示。
表
第 3 页，共 51 页
故问题的最优解单纯形表第一步迭代得单纯形表第二步迭代得单纯形表第三步迭代得（3）当
时，目标函数
，最优目标函数值。
，对应于图中的的坐标原点; ，对应于图中的点A 1（0, 6）; ，对应于图中的点A 2（2, 6）。
①若k<-3，则当c 2>0时，目标函数在点A 3（4, 0）处取得最大值; 当c 2<0时，目标函数在原点（0，0）处取得最大值;
②若-3≤k<-3/5，则当c 2>0时，目标函数在点A 2（15/4，3/4）处取得最大值，其中k=-3时，在线段 A 2A 3上的任一点取得最大值; 当c 2<0时，目标函数在原点处取得最大值;
③若-3/5≤k<0，则当c 2>0时，目标函数在点A 1（0, 3）处取得最大值，其中k=-3/5时，在线段A l A 2上的任一点取得最大值; 当c 2<0时，目标函数在坐标原点处取得最大值;
④若k>0，则当c 2>0时，目标函数在点A 1（0, 3）处取得最大值; 当c 2<0时，目标函数在点A 3（4, 0）处取得最大值。
（2）当c 2=0时，目标函数
①当c 1>0时，目标函数在点A 3（4，0）处取得最大值;
②当c 1=0时，目标函数在可行域OA 1A 2A 3中的任一点处均可取得最大值; ③当c 1<0时，目标函数在线段OA 1上的任一点取得最大值。
2． 在如图所示的网络中，每弧旁的数字是
（l ）确定所有的截集; （2）求最小截集的容量; （3）证明指出的流是最大流。
第 4 页，共 51 页
。
相关内容
相关标签