2016年上海对外经贸大学运筹学(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 对于线性规划问题:
设A 中存在可行基B ，其对应的基变量和非基变量分别为X B 和X N ，C B 和C N 为它们在目标函数中的系数， 则对应干基B 的单纯形表如表所示
表
若B 为最优基，则上述单纯形表为最优单纯形表。当原问题的某右端常数项b k 变为b k +△b k 时，试推导出使 最优基不变的△b k 的变化范围。（提示，自己假定B 及B b 的具体形式） 【答案】设
，且
, 其中Pi 为列向量,
，则有
2． 己知有m 个生产地点A i ，i=1，…，m ，可供应某种物资，其供应量为a i ，i=1，…，m ; 有n 个销售地B j ，j=l，…，n ，需要该种物资，其需要量为b j ，j=l，…，n ; 从各生产点往需求点发运时，均需经过P 个中间编组站之一转运，若启用第k 个编组站，不管转运量多少，均发生固定费用f k ，而第k 个编组站的转运容量为Q k （k=1，…，p ）。从A i 到P k 及P k 到B i 运输单位物资的运价分别为c ik 和c kj ，
现要制定一个使总运费最小的调运方案。建立该问题的混合整数规划数学模型。
【答案】设
组站k 运往销售点j 的运量。则得模型
表示销售点i 运往编组站k 的运量，x kj 表示编
, 其中
为正数
-1
-1
3． 在图中，分别求v l 至v 6，v l 至V 4，v6至vZ 和vZ 至vs 的最短路和最短距离。
图
【答案】用Floyd 方法求解 令网络的权矩阵为
其中，
为
到
的距离
由表示从v i 到v j 点的或直接
有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得
表示从vi 到vj 点最多经v l ，v 2的最短路长，得
以此
类推，
所以v l 至v 6的最短路是v 1一v 3一v 5一v 6，最短距离是-1; v l 至v 4的最短路是v 1一v 3一v 5一v 4，最短距离是3; v 6至v 2的最短路是v 6一v 4一v 2，最短距离是3: v 2至v 5的最短路是v 2一v3一v 5，最短距离1;