2017年华东理工大学理学院运筹学复试仿真模拟三套题
● 摘要
一、简答题
1． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
2． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
二、计算题
3． 写出下列线性规划的对偶问题
【答案】
4． 求图中，从任意一点到另外任一点的最短路。
【答案】用Dijtstra 算法寻求最短路，计算结果如表所示。
表
从表可以得出任意一点到另外任一点的最短路。 （l ）从v 1开始到各点的最短路。
（2）从v 2开始到v j 的最短路。
V 2不能到达v l ，故对v 2而言，v 1为不可达点。 （3）从v 3出发到各点的最短路。
v 3不能到达v l 和v 2，故v 1，v 2为v 3的不可达点。
，且d （v 4，v 6）=3。 （4）从v 4出发，只有一条路（v 4，v 6）
，且d （v 5，v 6）=6。 （5）从v 5出发，只有一条路（v 5，v 6）（6）从v 6出发，则无路。
5． 某工厂生产三种产品，各产品重量与利润关系如表所示，现将此三种产品运往市场出售，运输能 力总重量不超过6吨，问如何安排运输使总利润最大。
表
【答案】设运输三种产品的重量分别为x 1，x 2，x 3，则可建立数学模型
用动态规划方法来求解，此问题转化成求f 3（6）。 ①计算f 3（6）。
，必须先求f 2（6），f 2（2）可见，要计算f 3（6）。 ，f 2（2）②计算f 2（6）。
，f 2（2），必须先求出f 1（6），f 1（3），f 1（0），f 1（2）可见，要求f 2（6）。 ，f 1（3） ，f 1（0），f 1（2）③计算f 1（6）。
④所以，
x 3=0，f 2（2）=f1（2）=80, 此时x 1=1，x 2=0，x 3=1
x 1=0，x 2=0，此时，
相关内容
相关标签