2012级运筹学A卷.doc

2012级运筹学课程试题（A卷）题号一二三四五六七总分分数合分人： 复查人： 一、填空题：（共21分）分数评卷人1、（4分）线性规划问题的解的类型有：唯一最优解、 、 和无可行解四种类型。运输问题是特殊的线性规划问题，它的解的类型有 。2、（2分）若原问题无可行解，则对偶问题解的类型为 。3、（3分）m个产地、n个销地的产销平衡的运输问题的变量个数为 个。求解运输问题初始基可行解的常用表上作业法主要包括西北角法、 、 和 三种。4、（4分）如下目标规划问题： 用图解法进行求解，得到图形如下： 该模型在 点取得满意解，该满意解满足了第 级目标，没有满足第 级目标。5、（2分）对于求极大化的整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：XBbx1x2x3x4x213/70111/7-20/7则对应的割平面约束（或方程）为 。6、（2分）用分支定界法求解极小化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的 。7、（2分）用动态规划求解某生产计划问题。已知第一期期初库存为0，第五期期末库存也必须是0，每期的生产数量不大于5，决策变量xk表示第k期生产量，状态变量sk表示第k期初库存量，则状态变量s4的取值范围是 。（已知第15期市场对产品的需求量分别为2，4，3，4，4。）8、（1分）算法和Floyd法都是求解最短路问题的算法。其中， 法适宜于求解图中任意两点之间的最短路。9、（1分）一个有n个顶点的树图的边数为 。二、建模题（共16分）分数评卷人1、（7分）某省外贸局拟从下列应试者中招聘四名工作人员，希望所招四人平均业务能力评分最高，且满足下述要求：专业不得相同；女性最多不超过二人；至少有一名精通日语者；精通英语者最多入选一人。编号性别专业精通语种业务能力评分123456男女男女男女纺织机械化工电子机械食品英英德法日日959387878373 试建立该问题的0-1规划模型（不求解）。2、（9分）企业计划生产甲、乙两种产品， 这些产品需要使用两种材料， 要在两种不同设备上加工。工艺资料如下表所示。 产品 资源产品甲产品乙现有资源材料3012（kg）材料0414（kg）设备A2212（h）设备B5315(h)产品利润（元）2040企业在安排生产计划时， 依次尽可能满足下列目标：P1：力求使利润指标不低于80元； P2：考虑到市场需求， 甲、乙两种产品的生产量需相等； P3：设备A既要求充分利用，又尽可能不加班；P4：设备B加班时间尽可能少；另外，考虑到材料购买困难，一定不能超用。建立该生产计划问题的目标规划模型（不求解）。三、计算题（共63分）分数评卷人1、（共22分）已知某生产计划问题（两种资源、三种产品）的线性规划模型如下：引入松弛变量和，用单纯形法求得其最优单纯形表如下：41500415/41-1/401/4-1/459/209/101-1/103/100-5/20-1/2-1/2 (1)写出该线性规划的对偶问题,并写出对偶问题的最优解。(2)目前单位产品一的利润为4，在其他条件不变的前提下，该利润在什么范围之内变化时，最优解不变？(3)若有一种新产品丁，其原料消耗定额为：A为4单位，B为2单位，单位产品利润为2.5，问该种产品是否值得生产，并求出新的最优生产计划。(4)若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B若数量不足可从市场购买，单价为0.25，问：该厂是否购买该种资源？并说明理由。若购买，以购买多少为宜？2、（共10分）已知某运输问题的产销量、单位运价以及初始调运方案如下表所示。（1）用表上作业法求最优调运方案。（2）A2到B1的单位产品运费在什么范围之内变动时，最优方案不变。 销地产地B1B2B3B4B5（虚销地）产量A1370624305A22423202A3343380506销量332233、（共9分）用匈牙利法求解如下最小值的指派问题 1010 4 2 8C= 711 10 14 12 56 9 12 14 1315 11 10 74、（共11分）用动态规划方法求出下述问题的最优解。5、（共11分）（1）求下图所示的网络的最大流（每个弧旁的数字表示该弧的容量和流量）。（2）该网络的最