2016年哈尔滨工业大学经济与管理学院850运筹学考研强化班模拟试题及答案
● 摘要
一、简答题
1． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
2． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界
域（称为分支）的方法，逐步减小和增大
3． 简述影子价格的经济含义。
【答案】影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。影 子价格对市场具有调节作用，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资 源用于扩大生产; 而当某种资源的市场价高于企业影子价格时，则企业的决策者应把己有资源卖掉。
4． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐次求
，即可求出目标规划的满意解。 解k 个线性规划（k 为优先级的个数）; 。分支定界法就是将B 的可行域分成子区:， 最终求到z*。
二、计算题
5． 给出如下线性规划问题的最优单纯型表如表所示，其中S 1、S 2分别为两个约束条件的松弛变量
表
要求:（l ）求出使最优基不变的b 2的变化范围;
（2）求出使最优解不变的c 2的变化范围;
（3）在原线性规划的约束条件上，增加约束条件:
试求出最优解。
【答案】（l ）假设b 2变化后的最优解为X B ，只要X B ≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化。
设b 2变化了λ，则
所以 ，其最优解是否变化? 如变化，
当b ≥0时问题最优基不变，解得λ≥0故b 2≥30
（2）由题意知c 2-4≥0得c 2≥4
（3）约束条件可变为x 1+2x2+2x3+s3=12
列出单纯形表
最优解（12/5, 0, 24/5）
6． 用大M 法（极小化为标准形式）求解得某极小化线性规划问题的最优单纯形表如表所示。
表
表中x 4为松弛变量、x 5为剩余变量、x 6和x 7为人工变量。试回答如下问题:
（l ）计算C 1和C 2的数值;
（2）求使最优基不变的C 1、C 2的关系;
（3）求原问题的三个右端常数。
【答案】（l ）由最优单纯形表得到下列关系式为:
（2）若最优基不变，则有下列关系式:
（3）
解得原问题的三个右端常数为
7． 设有三个电视机厂生产同一种彩色电视机，日生产能力分别是:50，60，50（台），供应三个
，从各分厂运往个门市部的单位运费如表所示，试安门市部，日销售量分别是:60，40，60（台）
排一个运费最低的运输计划。 若工厂1到门市部1的运价由9减为6，试寻求最优运输计划。
表