2016年山西财经大学运筹学基础(同等学力加试)复试笔试最后押题五套卷
● 摘要
一、计算题
1． 6有九个城市v l ，v 2，…，v 8，v 9，其公路网如下图所示，弧旁数字是该公路的长度。有一批货物从v l 运 到v 9，问走哪条路最短?
图
【答案】用Dijkstra 算法进行求解。
（l ）对起点v l 进行P 标号，即P （v l ）=0; 对其余点进行T 标号，即
，T （v 4）}=T（v 2）=3，将v 2进行P 标号，且P （v 2）=3。 依据而min{T（v 2）
，，（2）v 2己进行了P 标号，（v 2，v 3）（v 2，v 5）（v 2，v 6
）行改写:
，T （v 4），T （v 5），T （v 6）}=T（v 4）=4，故将v 4进行P 标号.P （v 4）=4. 因为min{T（v 3）
（3）v 4已进行了P 标号，而
，修改v7的T 标号为
，T （v 5），T （v 6），T （v 7）}=5=T（v 5），故对v 5进行P 标号P （v 5）=5. 因为min{T（v 3）
（4）已对v 5进行了P 标号，而（v 5，v 6
）
A ，修改v 6的T 标号为
，T （v 6），T （v 7）}=6=T（v 3），故对v 3进行P 标号P （v 3）=6. 因为min{T（v 3）
（5））已对v 3进行了P 标号，而（v 3，v 9
）
A ，修改v 9的T 标号为
，T （v 7），T （v 9）}=6=T（v 6），故对v 6进行P 标号P （v 6）=6. 因为min{T（v 6）
，（6）已对v 6进行了P 标号，而（v 6，v 7）（v 6，v 9
）
A ，修改v 7，v 9的T 标号为
A ，所以应对v 3，v 5，v 6的T 标号进
。因为
，T （v 9）}=7=T（v 7），故对v 7进行P 标号P （v 7）=7. 因为min{T（v 7）
，（7）已对v 7进行了P 标号，而（v 7，v 8）（v 7，v 9
）
A ，修改v 8，v 9的T 标号为
，T （v 9）}=8.5=T（v 9），故对v 9进行P 标号P （v 9）=8.5。于是得到从v l 到v 9因为min{T（v 8）
的最短路程为8.5。 应用反向跟踪的方法可以得到，从v l 到v 9的最短路线为v 1→v 2→v 6→v 9。
2． 某电视机厂为生产电视机而需生产喇叭，生产以万只为单位，据以往记录，一年的四个季度需要喇叭分别为3万只，2万只，3万只，2万只。设每万只存放在仓库内一个季度的存储费为0.2万元，每生产一批的装配费为2万元，每万只的生产成本费为1万元，问应该怎样安排四个季度的生产，才能使总的费用最小。
【答案】生产成本函数与库存费用函数分别为:
用再生产点解此问题。
（2）
或3
所以，最小总费用为14.8万元，最优生产决策为: ①当②当
时，时，由
得m=2，则
3． 如表是某线规划问题计算过程中的一个单纯形表，目标函数为max z =5xl +3 x2，变量均≥0，约束条件为“≤”类型，x 3，x 4为松弛变量。
表
要求: （1）求出表中的a 、b 、e 、d 、e 、f 和g ; （2）完整写出该线性规划问题的数学模型; （3）写出此问题的对偶问题;
（4）表中的解是线性规划问题的最优解吗? 对偶问题的最优解是什么?
【答案】（l ）该过程中，x3，xl 为基变量，因此可得出:e=0，d=1，b=f=0；
a= -10/5= -2
×1= -5
（2）由（l ）可知表为
表
1
第一步中x 3，x 4为基变量，
知表1是经过一步变化得出
由该方程变化出以x 3，x 4为基变量的方程为:
可得该问题的数学模型为:
（3）该问题的对偶问题如下:
（4）由于表1中所有变量的检验数均不大于0，但是x 1= -2不符合约束条件，故不是最优解。由表1可得出对偶问题的最优解为y l =0，y 2=5。
但