广东外语外贸大学
《运筹学》20072008学年上学期期末考试试卷（B）
考试时间：2小时班级：
题次分数得分一10二30
学号：
三10四10
姓名：
五24六16总
成绩：
分
100
一、判断题认为对的写“T”，错的写“F”并改正。每小题2分，共10分（）1、如果一个线性规划问题有最优解，则其最优值只能在可行域的某个顶
点上获得。
（
）2、如果要使目标规划的实际实现值不大于目标值，则相应的偏离变量应满足d0。
（
）3、求解最短路问题的Dijkstra算法只适用于求解网络图中所有点间连
线上的权都非负的情形。
（
）4、如果在无圈图G＝（V，A）中，任意两顶点之间都有一条链相连接，
则G是一棵树。
（
）5、在网络计划图中，关键工序的时间缩短a天，则整个工程的完工期
相应缩短a天。
1
f二、填空题（每小题6分，共30分）1、考虑一运输问题，有关产品的单位运价（元吨）如下表所示：销地产地A1A2A3需求量（吨）1121274023333175206560B1B2供应量（吨）
假设A1、A3处产品要求全部运走A2处产品就地储存的费用为每吨18元。则该问题的产销平衡表为：销地产地供应量（吨）
需求量（吨）
2、三年内有五项工程可以考虑施工，每项工程的年度费用和纯收入如下表：
工程费第一年第二年用第三年纯收入15132024710403392204741155861030可用资金（万元）252525
则要确定施工工程使总收入达到最大，可以建立如下数学模型：
；
其中决策变量表示：
。
2
f3、考虑下面的收益矩阵表中数据为收益值：
状态方案A1A2A3A41333198917212211121310E1E2E3
（1）用悲观值准则求得最优方案为（2）其后悔矩阵为：
用后悔值准则求得最优方案为
。
4、下图给出了一个从V1到V6的可行流ffij，弧旁数据是（cijfij）（弧容量，弧流量）。则该可行流的流量为f已是最大流，请说明理由：如果你认为f不是最大流，请找一条增广链：，并指出这条增广链的调整量为：。；如果你认为该可行流。
V2
（99）
（107）30V5
771313
（42）V1
881210
V31010
63
V6
V4
5、以下是某个最大化线性规划问题上机求解后输出结果中的一部分，请填写划线部分：（其中约束1、约束2均为“≤”约束。）约束1211松弛变量对偶价格（元）60常数项下限5539当前值7048上限22066。
如果约束1右端常数增大10，则最优目标函数值将增大
3
f三、（10分）设有一份特快专递要从新市邮局（V1）送到永兴小区（V7），试根据下图用Dijkstra算法求邮递员的最短r