运筹学试卷1（60学时）答案

------------------ - -- - -- - -- - -- - -- - -- - -- - -- - -- - -- - -- - -名---姓-- 线 -- - -- - -- - -- - -- - -- - 封 -- - -- - -- - -- - -- - -号---学---- 密 - -- - -- - -- 队---区---- -- - -- - -- 队---- -- - -- - -- - -- - -- - -- - -- - -- - -- - -- - -- - -- - -- -军事交通学院《军事运筹学（60学时）》试卷1

题号 一 二 三 四 五 六 七 总分 得分 一、判断题（共10小题，共30分）

得分

判断下面的说法，正确的在下面表格对应位置画√，错误的

评卷人 在下面表格对应位置画×

题号 1 2 3 4 5 6 7 8 9 10 判断 √ √ √ √ × × × × × × 1、 求网络最大流的问题可归结为求解一个线性规划模型。

2、 若Q为关于流f的一条增广链，则Q中所有前向弧都为f的不饱和弧。 3、 在一个目标规划模型中，若不含有刚性约束，则一定有解。

4、 用大M法处理人工变量时，若最终表上基变量中仍含有人工变量，则原问题

无可行解。

5、 在决策问题中，无论决策环境等条件是否变化，一个人的效用曲线总是不变

的。 6、 若原问题是

maxz?CX，

s.t.??AX?b?X?0则其对偶问题的最优解值等于原问题最优表中对应松弛变量的检验数值。 7、 在非确定型决策中，一般说来，等可能型决策准则的决策结果较其他决策准

则的决策结果为优。

8、 若某种资源的影子价格等于5，在其他条件不变的情况下，当该种资源增加5

个单位时，相应的目标函数值将增大25。

9、 图论中的图不仅反映了研究对象之间的关系,而且是真实图形的写照,因而对

图中点与点的相对位置,点与点连线的长短曲直等都要严格注意。 10、 工作的最早开始时间等于该工作箭头结点最早实现时间。

第 1 页 共8页

二、（共6分） 得分 评卷人 用对偶单纯形法求解线性规划，下表为计算过程中的一张表，请判断线性规划原问题及其对偶问题解的情况。

2 3 0 0 0 CB XB b 2 0 3

x1 1 0 0 0 x2 0 0 1 0 x3 0 1 0 0 x4 1/4 -1/2 0 -1/2 x5 0 -2/5 1/5 -3/5 x1 x3 x2 cj?zj 4 8 -2 【解】补齐数据得

从表中观察对偶问题为无界解，∴原问题无可行解。

―――――――（6分）

第 2 页 共8页

------------------------------------------------------ 题---- 线 -- 答---- -- - -- 止---- -- - 禁封 -- - -- 内---- -- - -- 线---- -- - -- 封 密 - -- - -密------------------------------------------------------------- -三、（12分） 得分 用匈牙利法求解下列指派问题，已??791012?知效率矩阵如下： ?13121617?评卷人

?? ?15161415??

?11121516??? 【解】 123?√-2 ? ?0234?√-1 ?044?√-2

?1044??0??2 ??200?? ?1200???2 ?0144?√-1 ???0033??√-2

√+1 √+2 √+2

??0101? ?2022? ? ???4400? ?0011??

――――――（10分）最优指派为： ?010?

100? ?ij??0x??0 ?001?? ?0? ?1000???――――――（2分）

第 3 页 共8页

四、运输问题（14分）

某一运输问题中产地和销地的供需情况和单位运价如下表， 得分 允许在产地存储，但有费用发生，求其总费用最小的调运方

评卷人 案。

销地 甲 乙 丙 可供量 单位存储费 产地 A 5 6 9 45 3 B 需求量 6 25 1 20 4 30 40 2 【解】 经分析此问题为一产销不平衡问题 产量： 45+40=85 销量： 25+20+30=75 ∴ 需要增加一个虚拟销地 丁 如表所示。

―――――――（3分）

（位势法+伏格尔法）  销地 产地 甲 5 256 0 乙 6 丙 9 10丁 10可供量 3 45 2 40 行差 ui A × 6 201 20 4 30 5 5 2 2 0 2 1 1 -5 2 4 B 需求量 列差 vj × 25 1 1 5 5 × 10 1 1 3 9 3 20 5 6 调运方案如表所示， 由于存在某个非基变量的检验数为0，所以该问题有无穷调运方案。

最小运费：

z?5?25?9?10?3?10?1?20?4?20

?125?90?30?20?80

?345（元）

（给出初始调运方案）――――――――（4分）

（计算检验数并判断是否最优）――――――――（4分）

（调整并给出最优调运方案）――――――――（3分）

第 4 页 共8页

------------------------------------------------------ 题---- 线 -- 答---- -- - -- 止---- -- - 禁封 -- - -- 内---- -- - -- 线---- -- - -- 封 密 - -- - -密------------------------------------------------------------- -五、（共18分） 得分 已知用单纯形法求解线性规划问题

评卷人 maxz?3x1?2x2??x1?2x2?6?1?2x1?x2?8?2?s.t.????x?3? ?1?x2?1?x2?2?4???x1,x2?0得最终单纯形表如下： xxx3 x2 4/3 1 2 x4 5 x6 x2 1 2/3 -1/3 0 0 3 x1 10/3 0 -1/3 2/3 0 0 0 x5 1 0 -1 1 1 0 0 x6 0 -2/3 1/3 0 1 －z 0 -4/3 0 0 （a） 将表中空白处填上数字； （b） 给出该线性规划的最优解；

（c） 目标函数中x1的系数在什么范围内变化，问题最优解不变？ （d） 第二个约束的右端项在什么范围变化，问题最优基不变？

【解】 （a） x1 x2 x3 x4 x5 x6 2 x2 4/3 0 1 2/3 -1/3 0 0 3 x1 10/3 1 0 -1/3 2/3 0 0 0 x5 3 0 0 -1 1 1 0 0 x6 10/3 0 0 -2/3 1/3 0 1 －z －38/3 0 0 -1/3 -4/3 0 0

―――――――（8分）

(b) 由上表有, 最优解, X*???10?3,43,0,0,3,2?3??, 最优值,

z*?2?410383?3?3?3

―――――――（2分）

(c) ∵ x1为基变量， ∴需要重新计算非基变量的检验数 ?3?0?2?23?13?(3??x)??4?x3?1?3 第 5 页 共8页

本文来源：https://www.bwwdw.com/article/p4l2.html