2017年武汉轻工大学运筹学(同等学力加试)复试仿真模拟三套题
● 摘要
一、简答题
1． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界
; 。分支定界法就是将B 的可行域分成
子区域（称为分支）的方法，逐步减小和增大:， 最终求到z*。
2． 试说明C 一W 节约算法的基本思想，你认为还可用它解决哪些方面的问题? 举例加以说明。
【答案】（1）C 一W 节约算法的基本思想（以旅行商问题为例）:优先考虑将节约值最大的弧 这样在满足访问若干城市各一次且仅一次的条件下， 插入到旅行线路中，最大限度地缩短了路程。
（2）举例。运用C 一W 节约算法:设n 个不同用户为n 个点，维修点为基点，n 个用户点中从点i 到点j 的 长度为工人骑摩托车的交通时间加上点i 与点j 维修时间总和的一半。优先考虑将节约值最大的长度加入工作线路中去进行迭代。
二、计算题
3． 甲、乙两个企业生产同一种电子产品，两个企业都想通过改革管理获取更多的市场销售份额。
甲企业的策略措施有:①降低产品价格; ②提高产品质量，延长保修年限; ③推出新产品。 乙企业考虑的策略措施有:①增加广告费用; ②增设维修网点，扩大维修服务; ③改进产品性能。
假定市场份额一定，由于各自采取的策略措施不同，通过预测，今后两个企业的市场占有份额变动情况如表所示（正值为甲企业增加的市场占有份额，负值为甲企业减少的市场占有份额）。试通过对策分析，确定两个企业各自的最优策略。
表
【答案】令甲企业考虑的策略措施①，②和③分别记为②和③分别记为
，则由题意有:
; 乙企业考虑的策略措施①，
因为
的最优措施为“改进产品性能”。
4． 现有线性规划问题
，V G =5。甲企业的最优策略措施为“推出新产品”，乙企业考虑所以，对策G 的解为（3，3）
先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化? （1）约束条件式②的右端常数由20变为30; （2）约束条件式②的右端常数由90变为70; （3）目标函数中x 3的系数由13变为8; （4）x 1的系数向量由
、变成
;
; 。
（5）增加一个约束条件式③:
（6）将原约束条件②改变为
【答案】在上述线性规划问题的第①，②个约束条件中分别引入松弛变量x 4，x 5，得
建立初始单纯形表，并利用单纯形法进行迭代计算，如表所示。
表
所以，原问题得到最优解为
（l ）约束条件式①的右端常数由20变为
30
，最优目标函数值为z*=100。
列出单纯形表，并利用对偶单纯形法求解，求解过程如表所示。
表
所以，线性规划为题的最优解变为（2） 约束条件②的右端常数由90变为
70
，最优目标函数值为。
列出初始单纯形表，并利用对偶单纯形法进行迭代计算，求解过程如表所示。