运筹学试题含答案.docVIP

简述惩罚函数法的基本思想，并给出其典型形式。（10分） 二、证明： 设在点处的Hesse矩阵存在，若，并且正定，则是的严格局部最优解。（10分） 三、用两阶段法求解下列线性规划问题：（20分） 四、运用分枝定界方法求解下列整数规划问题：（20分） 五、试写出用动态规划方法求解下列问题时的基本方程（20分） 设有一个外贸公司计划在1月至4月份从事某种商品的经营。已知它的仓库最多可存储1000件这种商品，该公司开业时有存货500件，并根据预测知道，该种商品1月至4 月的进价和售价如表5所示。 表5 月份 1 2 3 4 进价c（百元/件） 10 9 11 15 售价p（百元/件） 12 9 13 17 问如何安排进货量和销售量，使该公司获得最大利润。（假设四月底库存为零。） 六、已知有6个村子，相互间道路的距离如图1所示。拟合建一所小学，已知A处有小学生50人，B处40人，C处60人，D处20人，E处70人，F处90人，问小学应建在哪一个村子，使学生上学最方便（走的总路程最短）。（20分） 简述惩罚函数法的基本思想，并给出其典型形式。 答：罚函数类方法的基本思想是：通过构造惩罚函数，将带有约束的非线性规划问题转化为无约束优化问题的求解。 由不同的构造罚函数的思路就可以导出不同的具体罚函数算法，因此，有下列典型形式： （1）等式约束问题的平方罚函数： （2）不等式约束问题的内点罚函数（障碍罚函数） （3）分（倒）数罚函数 （4）对数罚函数 二、证明： 设在点处的Hesse矩阵存在，若，并且正定，则是的严格局部最优解。 证明：将在处进行Taylor展开，有 由的正定性得： 而为的高阶无穷小量。 必然存在，使得,. 因此结论得证，证毕。 三、用两阶段法求解下列线性规划问题： 解：引入辅助问题 利用单纯形法求解辅助问题的过程，见表3。 表3 0 0 0 0 0 1 1 0 1 -2 1 1 0 0 0 11 1 -4 1 2 0 -1 1 0 3 1 -2 0 （1） 0 0 0 1 1 6 -1 -3 0 1 0 0 -4 0 3 -2 0 1 0 0 -1 10 1 0 （1） 0 0 -1 1 -2 1 0 -2 0 1 0 0 0 1 -1 0 -1 0 0 1 0 2 1 0 3 0 0 1 -2 2 -5 12 0 0 1 0 0 -1 1 -2 1 0 -2 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 在最优表中，基变量已无人工变量。消去第一阶段最终计算表中人工变量所在列，并将目标函数系数换成LP问题相应系数，进行第二阶段的单纯形法迭代，计算过程列于表4中。 表4 -3 1 1 0 0 0 (3) 0 0 1 -2 12 1 0 1 0 0 -1 1 1 -2 0 1 0 0 1 -1 0 0 0 1 -2 -3 1 0 0 4 1 0 1 0 0 -1 1 1 0 0 1 9 0 0 0 2 从表4知最优解为：，最优值为：。 四、运用分枝定界方法求解下列整数规划问题： 解：记整数规划问题为(IP)，它的松弛问题为(LP)。 用单纯形法解(LP),最优解为，而. (LP)的最优解不符合整数条件(5).选择较小的进行分枝。由于最接近的整数是1和2，因而可以构造两个约束条件： (6) (7) 将(6)、(7)分别并入(LP)，形成两个分枝，即子问题(LP1)和(LP2)，分别由(LP)及(6)和(LP)及(7)组成。S1和S2分别是(LP1)和(LP2)的可行域。 解(LP1)，最优解为，，该点不符合整数条件(5)。因此，解(LP2)，其最优解为，，该点也不符合整数条件(5)。因此，继续分枝。 由于，所以优先选择S1进行分枝。此时只有不符合整数条件，故可以构造两个约束条件： (8) (9) 将(8)和(9)分别并入(LP1)，形成两个新分枝，即后继子问题(LP11)和(LP12)，分别由(LP1)及(8)和(LP1)及(9)组成。S12为(LP12)的可行域。由于约束条件(8)和(LP1)不相容，故(LP11)无可行解，也就是说只需考虑子问题(LP12)。 在S12上解(LP12)，最优解为，. 对于原问题来讲，此时还剩下两个分枝：子问题(LP2)和(LP12)，(LP2)最优解的目标函数值为，(LP12) 最优