2017年上海大学管理学院911运筹学(专)考研导师圈点必考题汇编
● 摘要
一、计算题
1． 用两阶段法求解以下线性规划问题
【答案】第一阶段:加入松弛变量x 4，x 5，人工变量x 6，数学模型为:
用单纯形法求解如表所示。
表
第一阶段的最优解为X=
第二阶段：除去人工变量x 6，目标函数为：
求解结果为
2． 有四个工件J 1，J 2，J 3，J 4，要求在三台设备A ，B ，C 上顺次加工，各工件在各设备上的加工时间示于表中，试构造一启发式算法，用于寻求使总加工时间最短的工件加工顺序。
表
【答案】可设计如下启发式算法:
利用该启发式算法求解，求解过程如表所示。
表
所以，最优加工顺序为，总加工时间为40。
3． 在图中，分别求v 1至v 6，v 1至V 4，v 6至v Z 和v Z 至vs 的最短路和最短距离。
图
【答案】用Floyd 方法求解 令网络的权矩阵为
其中，
为
到
的距离
由表示从v i 到v j 点的或
直接有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得
表示从vi 到vj 点最多经v l ，v 2的最短路长，得
以此类推，
相关内容
相关标签