2017年南昌大学线性规划复试实战预测五套卷
● 摘要
一、简答题
1． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧插入到旅行线路中， 这样在满足访问若干城市各一次且仅一次的条件下，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
二、计算题
3． 用图解法求解下列线性规划，并指出该问题所有基可行解在图中的位置。
【答案】如图所示可得阴影部分即为可行域，且可知在A （2，2）处取得最小值18。
基可行解有3个，分别是（6，0），（2，2），（0，6）
4． 如下线性规划问题:
当t l =t2=0时用单纯形法求解得最终单纯形表如下表所示: 试分析说明如下问题: （l ）确定
（2）当t 2=0时，t 1在什么范围内变化上述最优解不变:; （3）当t l =0时，t 2在什么范围内变化上述最优基不变。
表
的值;
【答案】（1）
（2）当t 2=0，变化的只有x l 的系数，代入到最优单纯形表，如表所示
表
若最优解不变，则
（3）当t l =0，变化的只有b l ，b 2的系数，最优解若不变，则
5． 国内某化妆品公司（简称M 公司），其管理层已经为他们公司的两种新产品制定了各自的市场目标，也就是说，产品1必须占据15%的市场份额，而产品2必须占有10%的市场份额。为了获得市场，准备开展三次广告活动·其中两个广告是分别针对产品1和产品2的，而广告3是为提高整个公司及其产品的声誉。以x l 、x 2、x 3分别表示分配在二个广告上的资金（单位:千万元）。则相应的两种产品取得市场份额估计值（以百分比表示）可表示为:
产品1的市场份额=0.05x1十0.02x 3，产品2的市场份额=0.03x2十0.02x 3公司投入广告的总预算为5500万元，其中规定必须至少有1000万元投入在第二个广告上。如果两个产品的市场份额不能同时实现，管理层认为两种产品目标偏离的严重性是同等的，管理层希望得到的最有效的资金分配方案。试在上述条件下，完整写出反映该问题的目标规划数学模型（注:不用求解）。
【答案】按照决策者所要求的，这个问题的数学模型是:
6． 已知线性规划问题，
写出其对偶问题，且当其最优解为X=（-5, 0, -1）时，求k 值; 【答案】对偶问题是: