2016年南京大学859系统分析与集成专业基础之《运筹学教程》考研强化班模拟试题及答案
● 摘要
一、简答题
1． 考虑一个（线性）目标规划在计算机上求解的问题。假设手头只有一个线性规划的求解软件，想要仅仅 借助该软件来实现对目标规划的求解，请问你的策略是什么（不超过200字）?
【答案】想要仅仅借助该软件来实现对目标规划的求解，则应按如下步骤进行。
先以第一级目标为目标函数，以原来的约束为约束，求解一个线性规划; 其次，将己经实现的第一个目标作 为一个附加约束，以第二级目标为目标函数，再求解一个线性规划。以此类推，逐次求
，即可求出目标规划的满意解。 解k 个线性规划（k 为优先级的个数）
2． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T
，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）
（3）比较所有具有T 标号的点，把最小者改为P 标号，即: 当存在两个以上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
二、计算题
3． 考虑下列线性规划:
取x 4，x 5分别为第1、2个约束的松弛变量，则最优单纯形表为:
表
填写出此线性规划最优单纯形表中空格外的数值，并求:
（l ）. 写出此线性规划的最优解、最优值、最优基B 和它的逆B ;
（2）. 求此线性规划的影子价格?
（3）. 试求c 2在什么范围内，此线性规划的最优解不变; -1
【答案】（l ）
最优答:
最优值:
， （2）由最优单纯形表得影子价格（0.5）
（3）设C 2=x，则:
4． 用图解法找出以下目标规划问题的满意解。
（2）
（3）
【答案】 （1）令各偏差变量为0，作出所有的约束直线，并标示出各偏差量增加对约束直线的影响，如图所示。
图
从图中可以看到，在考虑具有p l 的目标实现后，x 1，x 2的取值在直线+++及上; 考虑p 2的目标要求实现时，因为d 2的权系数大于d 3的权系数，故考虑mind d2，所以点A 为满
， 即满意解是（50，0）。 意解，其坐标为（50，0）
（2）令各偏差变量为0，作出所有的约束直线，并标示出各偏差量增加对约束直线的影响，如图所示。
T
图
从图中可以看到，在考虑具有p l 的目标实现后，x l ，x 2的取值范围为OADFO ; 考虑p 2的目标要求实现后，x l ，x 2的取值范围为OABEFO ; 考虑p 3的目标要求实现后，x l ，x 2的取值范围为BE ; 考虑p 4的目标要求实现时，因为d 4不的权系数大于d 3的权系数，故考虑mind 4，所以点E 为满意解，
，即满意 解是（25，15）。 其坐标为（25，15）
（3）令各偏差变量为0，作出所有的约束直线，并标示出各偏差量增加对约束直线的影响，如图所示。
T ---
图
从图中可以看到，在考虑具有p l 的目标实现后，x l ，x 2的取值范围为直线AB ; 考虑p 2的目标要求实现时，要实现mind 2，从图中可以看出，只有B 点可使d 2最小，所以B 点为满足目标规划
--
相关内容
相关标签