运筹学II

第1页共3页《运筹学》(II)一、填空题1．表1为用单纯形法计算时某一步的表格，已知该线性规划的目标函数为2135maxxxz，约束形式为，3x，4x为松弛变量，表中解代入目标函数后得z＝10。表11x2x3x4x3x2c011/51xade01jjzcb-1fg（1）a＝______，b＝______，c＝______，d＝______，e＝______，f＝______，g＝______；（2）表中给出的解为___________（提示：最优解，满意解，可行解……）。2．影子价格是一种____________，它相当于在资源得到最优利用的生产条件下，ib每增加一个单位时目标函数z的增量。3．若原问题及其对偶问题均具有可行解，则两者均具有__________，且它们最优解的目标函数值_________。4．动态规划中的状态必须具备____________。二、判断题1.线性规划问题的每一个基解对应可行域的一个顶点。（）2.对偶问题的对偶问题一定是原问题。（）3.表上作业法实质上就是求解运输问题的单纯形法。（）4.对一个动态规划问题，应用顺推法或逆推法可能会得到不同的最优解。（）5.求图的最小支撑树以及求图中一点至另一点的最短路问题，都可以归结为求解整数规划问题。（）三、简答题1.简述动态规划方法的基本思想。答：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。2.简述不确定型决策方法中的乐观准则。答：也称折衰决策法，决策者确定一个乐观系数ε（0.5，1），运用乐观系数计算出各方案的乐观期望第2页共3页值，并选择期望值最大的方案。四、计算题1.用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解或无可行解。0,81022.84max21212121xxxxxxstxxz2.已知线性规划问题：无约束321321321321,0,064.22minxxxkxxxxxxstxxxz（1）写出其对偶问题，并求对偶问题的最优解；（2）求k的值。3.已知运输问题的产销地、产销量及各产销地间的单位运价如下表所示，试据此列出其数学模型。表2产地销地甲乙丙产量11016321521422407322243416销量128204.用隐枚举法求解下列0－1规划问题：)4,,1(1014424204.4352min4321432143214321ixxxxxxxxxxxxxstxxxxzi或5.用匈牙利法求解下述指派问题，已知效率矩阵为：1096109532485724679278310283五、建模题某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C的含量、原料成本、各种原料每月的限制用量，三种牌号糖果的单位加工费及售价如表3所示：表3甲乙丙原料成本（元/kg）每月限制用量（kg）A%60%152.002000第3页共3页B1.502500C%20%6050%1.001200加工费（元/kg）0.500.400.30售价（元/kg）3.402.852.25若该糖果厂建立生产计划的目标优先级为：p1：达到利润目标；p2：甲、乙、丙三种糖果的原材料比例上应满足配方要求；p3：充分利用又不超出规定的原材料供应量。根据上述要求，对此问题建立目标规划的数学模型。