资源描述
2017年上海海事大学攻读硕士学位研究生入学考试试题 （ 重要提示 ：答案必须做在答题纸上，做在试题上不给分） 考试科目 代码 836 考试科目名称 运筹学模型与算法 一、（ 30 分）分别用图解法和单纯形法求解下列线性规划问题，并对照指出单纯形法迭代的每一步相当于图解法可行域中的哪一个顶点。 01536232min21212121,x x xx xxxxzs .t . -二、（ 30 分） 如下表所示的运输问题中，若产地 i 有一个单位物资未运出，则将发生存储费用。假定1、 2、 3 产地单位物资存储费用分别为 5、 4、 3。 又假定产地 2 的物资至少运出 38 个单位，产地 3 的物资至少运出 27 个单位，试求解此运输问题的最优解。 销地 产地 A B C 产量 销量 三 、（ 30 分）用分枝定界法求解整数规划问题 ： 且为整数0,5.45.01432.23m ax21212121xxxxxxtsxxz四、（ 30 分）有一辆最大货运量为 10 吨的卡车，用于装载 A、 B、 C 的 3 种货物，每种货物单位重量及相应单位价值如下表，应如何装载可使总价值最大？ （请用动态规划方法求解，并画出状态转移图 。 ） 货物编号 A B C 单位重量 （ Kg） 5 4 3 单位价值 （元） 6 5 4 五、 （ 30 分） 求解 0-1 整数规划问题时，可 引入目标函数 作为 过滤约束条件 ，从而加快求解过程，该方法称巴拉斯方法。 其计算步骤为： 第一步： 先用试探法，求出一个可行解作为初始解 ， 设 为 x1，其目标函数 Z1 = Zb ； 第二步： 建立过滤约束条件 Z =cjxjZb ； 第三步：判断 各组合 的解是否 先满足过滤约束条件， 再 检验其它约束条件； 第四步：若存在一可行解满足 Z Zb ，则令 Zb= Z， 转到第二步； 第五步：所有组合的解检验完即结束。 请你根据以上的搜索步骤， ， 求解以下整数规划问题 ，并画出程序框图 。 )( 10( mjxnibxaxcZjnjijijnjjj,.2,1或),.2,1max11113或0,6434422523max32132213213221xxxxxxxxxxxxxxxxZ
展开阅读全文