运筹学自测题答案.docVIP

第二、三章练习自测试卷 一、填空题 1.线性规划问题的标准形式：。 2.整数规划中如果所有的变量都限制为(非负)整数，就称为 纯整数规划问题 ，如果仅一部分变量限制为整数，则称为 混合整数规划问题 。 3.图解法求解线性规划问题，如果目标函数存在有限最优值，则最优解一定可以在可行域顶点达到。 4.x是可行域的顶点充分必要条件是x是线性规划问题的基本可行解。 5.如果x是问题的可行解, w是问题的可行解, 则 = 。 6. x和w分别是问题和问题的最优解的充要条件是。 7. 线性规划问题用两阶段方法求解的辅助问题：。 8.两阶段方法求解线性规划问题时，第一阶段结束辅助问题目标函数大于零则原问题无解。 二、解答题 9.线性规划问题（1）写出标准形（2）单纯形方法求解，（3）写出对偶问题，（4）利用（2）求得的解以及互补松紧条件写出对偶问题的最优解，（5）求c1的取值范围使得当前最优解仍为最优解，（6）求b1的取值范围使得当前最优基仍为最优基。 解：（1）标准形 （2）单纯形法： X1 X2 X3 X4 RHS z 2 -1 0 0 0 X3 X4 3 -6 1 0 1 2 0 1 3 3 z 0 3 -2/3 0 -2 X1 X4 1 -2 1/3 0 0 4 -1/3 1 1 2 z 0 0 -5/12 -3/4 -7/2 X1 X2 1 0 1/6 1/2 0 1 -1/12 1/4 2 1/2 标准线性规划问题的最优解为，最优值为-7/2； 原问题的最优解为，最优值为-7/2。 （3）对偶问题： （4）互补松紧条件：和 解得：最优值为：7/2。 （5） z -c1 -1 0 0 0 X1 X2 1 0 1/6 1/2 0 1 -1/12 1/4 2 1/2 z 0 0 -1/12+c1/6 1/4+c1/2 1/2+2c1 X1 X2 1 0 1/6 1/2 0 1 -1/12 1/4 2 1/2 所以即时，当前最优解仍为最优。 （6），即时，当前最优基仍为最优基。 10. 用分枝定界法解： 解： 答：因为，所以原整数规划的最优解为或。 用Gomory割平面法解： 解：将该整数规划的松弛问题化为标准形： 用单纯形法解松弛的线性规划问题得： 对下表所示效率矩阵的指派问题建立数学模型并用匈牙利方法求最小解。 任务 人员 A B C D 甲 乙 丙 丁 8 7 15 4 9 14 17 10 6 12 6 7 6 9 10 9 三. 建模题 13.某市今年要兴建大量住宅，已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表： 资源 住宅体系 造价 元/米2 钢材 公斤/米2 水泥 公斤/米2 砖 块/米2 人工 工日/米2 砖混住宅 105 12 110 210 4.5 壁板住宅 135 30 190 0 3.0 大楼住宅 120 25 180 0 3.5 资源限量 110000 千元 20000 吨 150000 吨 147000 千块 4000 千工日 要求在充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。 解：设建造砖混住宅为平方米，壁板住宅平方米，大楼住宅平方米，则 1