2017年河北大学管理学院868运筹学考研导师圈点必考题汇编
● 摘要
一、简答题
1． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐
，即可求出目标规划的满意解。 次求解k 个线性规划（k 为优先级的个数）
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解;
（2）某枝域内没有可行解时，即是不可行域;
（3）某枝所得数据不优于当前最优解时。
3． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
4． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧
这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
二、计算题
5． 试用乘子法求解非线性规划问题（取c=2）:
【答案】设
定义拉格朗日函数 于是得到
解得，
6． 某公司从两个不同的仓库向三个客户提供某种产品，由于在计划期内供不应求，公司决定重
，各客户的需点保证某些 客户的需要，同时又使总运输费用最低，现已知各仓库的供应量（吨）
，相关数据如表所示。 求量（吨）及从各仓库到每一客户的单位运费（元/吨）
表公司供应客户需求量表
根据供求关系和公司经营的条件，公司确定了以下目标变量:
P 1表示客户几的需要;
P 2表示至少满足各客户75%的需要;
P 3表示使总运费最少;
P 4表示从仓库A 2至客户B 1，只能用船运货，最小运量为1000吨;
P 5表示从仓库A 2至客户B 3，从仓库戊至客户残之间的公路正在大修，运货量应尽量少; P 6表示平衡用于
B l 和B 2之间的供货满意水平。试建立该问题的目标规划模型。
-+【答案】设Xij 为仓库i 到用户j 的运输量（i=1，2；j=1，2，3）; d i ，d i 为第i 个目标约束
条件中，未达到规定目标的负偏差变量和超过目标的正偏差变量。
由题意可建立如下的目标规划模型:
7． 线性规划问题
当t l =t2=0时，该问题的最优单纯型表如表所示。
表
（l ）确定所有参数，并写出该线性规划问题; （2）当t 2=0时，分析使最优解不变的t 1的变化范围; （3）当t 1=0时，分析使最优基不变的t 2的变化范围。
【答案】（l ）由最优单纯型表得出，x l 和x 3为基变量x B ，则对应初始单纯形表中为:
由最优单纯型表得到
由，得, 所以, 求得
，即 ,