当前位置：问答库＞考研试题

一、计算题

1． 试求解下列线性规划问题:

将本问题的目标变成minz=x1+x2，约束条件不变，何为其解?

【答案】（l ）将原问题化为标准型:

采用单纯形法求解，如表所示。

最优解为

可求得最优解为:

（2）若目标变成minz=x1+x2，则标准型中目标函数变为 其他不变。修改单纯型表中的系数，即

2． 出从1节点到U 节点的最短路径

图

【答案】Dijkstra 算法，即标号法求解

（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为

而

（2）修改节点3、5的T 标号

因为

（3）修改节点6，8的标号

因为

（4）修改节点9的标号

因为

（5）修改节点7的标号

因为

（6）修改节点9、11的标号

因为

（7）修改节点12的标号

因为故将点12进行P 标号，

故将节点2进行P 标号， 故将点5进行P 标号， 故将点6进行P 标号， 故将点4进行P 标号， 故将点8进行P 标号， 故将点9进行P 标号，

顶节点12已经进行了P 标号，且

线为1→2→5→8→11→12

于是得到节点1到节点12的最短路程为18，最短路

3． 在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并代入目标函数，确定哪一个是最优解。

（1）

（2）

【答案】 （1）在第二个约束条件两边同时乘以-1，得到该线性规划问题的系数矩阵

因为P 1、P 2线性无关，故有

令非基变量x 3=x4=0，解得x 1=1，x 2=2，故有基可行解x （1）=（1, 2, 0, 0）T ，z 1=8。

因为P 1、P 3线性无关，故有

令非基变量x 2=x4=0，解得因为P 1、P 4线性无关，故有

令非基变量x 2=x3=0，解得因为P 2、P 3线性无关，故有

令非基变量x 1=x4=0，解得因为P 2、P 4线性无关，故有

故不是可行解。 故有基可行解。 故有基可行解