《运筹学》样卷参考答案（48课时）
一、判断题（对的记√，错的记×，共10分，每小题2分）
1. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可
行域的范围一般将扩大； （ ）
**2. 已知y为线性规划的对偶问题的最优解，若yi?0说明在最优生产计划中第i种资源
已完全耗尽； ( ) 3. 运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有
惟一最优解、有无穷多最优解、无界解和无可行解； （ ） 4. 求解整数规划是可以先不考虑变量的整数约束，而是先求解相应的线性规划问题，然后
对求解结果中的非整数的变量凑整即得最优解。 （ ）
5. 11个公司之间可能只有4个公司与偶数个公司有业务联系； （ ） 答案： 1. T； 2. T； 3. F； 4. F； 5. F
二、选择题（共15分，每小题3分）
1. 在利用图解法求解最大利润问题中中，通过各极点作与目标函数直线斜率相同的平行线，
这些平行线称之为 。 ( )
A.可行解 B.可行域 C.等利润线 D.等成本线
2. 用单纯形法求解线性规划问题时引入的松弛变量在目标函数中的系数为 。
( )
A.0 B.很大的正数 C.很大的负数 D.1 3. 以下关系中，不是线性规划与其对偶问题的对应关系的是 。 ( )
A．约束条件组的系数矩阵互为转置矩阵
B．一个约束条件组的常数列为另一个目标函数的系数行向量 C．两个约束条件组中的方程个数相等 D．约束条件组的不等式反向
4. 需求量大于供应量的运输问题需要做的是 。 ( )
A.虚设一个需求点 B.删去一个供应点 C.虚设一个供应点，取虚设供应量为恰当值 D.令供应点到虚设的需求点的单位运费为0
5. 对一个求目标函数最大的混合整数规划问题，以下命题中不正确的是 。 （ ）
A.其线性规划松弛问题的最优解可能是该整数规划问题的最优解。 B.该问题可行解的个数一定是有限的；
C.任一可行解的目标函数值不可能大于其线性规划松弛问题的目标函数值； D.该问题可行解中可能存在不取整数值的变量。 答案：6.C
7.A 8.C 9.C 10.B
三、简答题（每题5分，共15分）
1. 线性规划问题的三个要素是什么？线性规划模型有哪些特征？
答案：线性规划问题的三个要素是决策变量、目标函数和约束条件。线性规划模型的特征有：（1）目标函数是决策变量的线性函数；（2）约束条件是决策变量的线性（不）等
式；（3）决策变量连续变化。
2. 利用0-1变量表示下列约束条件（要求说明0-1变量的意义）：
x取值0，2，4，6，8中的一个
答案：设yj=1为取第j个数，否则,yj=0.则
?x?0y1?2y2?4y3?6y4?8y5? ?y1?y2?y3?y4?y5?1?y?0?or?1,?j?1,2,,5?j3. 写出求极大值的运输问题的产销平衡表
A1 A2 A3 销量
B1 7 17 5 15 B2 8 16 3 10 B3 9 15 4 15 B4 10 14 6 20 产量 30 20 15 ??17?Cij,总产量=65>60=总销量，增加一个虚拟的销地，销答案：令新表中单位运价为Cij量为5. A1 A2 A3 销量 B1 10 0 12 15 B2 9 1 14 10 B3 8 2 13 15 B4 7 3 11 20 B5 0 0 0 5 产量 30 20 15 (10分=5分+5分) 某产品有三个产地、四个销地，各产地的产量、各销地的销量以及产地到销地之间的单位运价见下表，用表上作业法求该运输问题的最优调运方案。 销地 产地 A1 A2 A3 销量 B1 4 2 8 8 B2 12 10 5 14 B3 4 3 11 12 B4 11 9 6 14 产量 16 10 22 答案：为了简便,表中[]中的数为运行方案，()中的数为检验数。 最小元素法：
销地 产地 A1 A2 A3 销量 B1 4(1) 2[8] 8(10) 8 B2 12(2) 10(1) 5[14] 14 B3 4[10] 3[2] 11(12) 12 B4 11[6] 9(-1) 6[8] 14 产量 16 10 22 48 检验数?24??1?0，当前方案不是最优，调整如下：
销地 B1 B2 B3 B4 产量 产地 A1 A2 A3 销量 4(0) 2[8] 8(9) 8 12(2) 10(2) 5[14] 14 4[12] 3(1) 11(12) 12 11[4] 9[2] 6[8] 14 16 10 22 48 所有检验数非负，当前方案为最优方案.有非基变量检验数为0，有无穷多最优解。 （4）用图解法求下列目标规划的满意解：
－＋?minz?P1d1＋?P（d?d)?Pd22233
2x1?x2????x?x?d?d1211?????x1?2x2?d2?d2?8x?10x?d??d?233?1x1,x2,di?,di????11(a)?0(b)?10(c)?56(d)?0(i?1,2,3)
图略，满意解是线段GD上任意点，其中G点(2,4),D点(10/3,10/3)，因为GD上任意点对应
?的d3?0
（5）设图中各弧上数为距离，求该网络（看作无向图）的最小生成树。
13. 解： （1）破圈法或加边法，过程略
如上图，为该网络（看作无向图）的最小生成树，总的权重为18
三 、解答题（共50分）
1. （10分）某企业生产甲、乙两种产品，从工艺资料知道：每生产一吨产品甲需用资源A
3个单位，资源B 5个单位，每生产一吨产品乙需用资源A 4个单位，资源B 2个单位。若一吨产品的甲和乙的经济价值分别为10千元和6千元，每天原料供应的能力分别为10，12单位，企业应该如何安排生产计划，使得一天的总利润最大？ 解：设每天生产甲、乙各x1,x2 吨，则
max?z?10x1?6x2
?3x1?4x2?10 ?s..t?5x1?2x2?12?x,x?0?12图解法求解：略
最优解为：X=(2, 1 )， 最优目标值为z=26.
答：每天生产甲、乙各2 吨和1吨，使得一天的总利润最大
2. 下面三题选一：
（1）已知线性规划问题（P）
maxs..tz?2x1?3x2?3x3?x1?x2?x3?3 ??x1?4x2?7x3?9?x?0,j?1,2,3?j2 XB X1 X2 b 1 2 X1 1 0 3 X2 0 1 3 X3 -1 2 0 X4 4/3 -1/3 0 X5 -1/3 1/3 的一个单纯形表如下。 Cj? cB 2 3 0 0 -1 -5/3 -1/3 ?j （a） 写出(P)此时的基本可行解，并判断该解是否为最优解； （b） 写出(P)的对偶模型及其最优解。 答案：（1）基变量为X1,X2，故当前基本可行解为（1，2，0，0，0），因为所有检验数非正，故为最优解。
（2）(P)的对偶模型为
min?w?3y1?9y2?y1?y2?2?y?4y?3?12??y1?7y2?3??y1,y2?0
其最优解为原问题最优单纯表中检验数的相反数，即（5/3, 1/3）
max?z?2x1?4x2?x3?x4?x4?x1?3x2?2x?x21（2）已知线性规划问题： ??x2?x3?x4??x?x2?x3?1(j?1,,4)??xj?0的最优解为X*=(2,2,4,0)，根据对偶理论求出对偶问题最优解。
?8?6 ?6?9min?w?8y1?6y2?6y3?9y4?y1?2y2??????????y4?2?3y??y??y??y?31234解：对偶模型为????????????????????y3??y4?1??y???????????????????y?14?1??y1,y2,y3,y4?0
设对偶问题最优解为Y*?(y1,y2,y3,y4)。因为原问题最优解为X*=(2,2,4,0)，故
?y1?2y2??????????y4?2??3y1??y2??y3??y4?3 ?????????????????y??y?134?又因为xs4?9?2?2?4?1?0，故y4?0，从而y3?1,y1?2/5,??y2?4/5，所以对偶问题的最优解为(2/5,4/5,1,0)
3. 下面三题选一：
（1）用分枝定界法求解整数规划问题：
maxz?3x1?2x2
?2x1?3x2?14 ?x?0.5x?4.5?12?x,x?0且x为整数?122解：该问题的松弛问题(L)为
maxz?3x1?2x2
?2x1?3x2?14 ??x1?0.5x2?4.5?x,x?0?12对(L)分别增加条件x2?2和x2?3，得两个子问题(L1)和(L2)，用图解法（略）得子问
用图解法（略）得松弛问题(L)的最优解为(3.25,2.5)，最优目标值为14.75.
题(L1)的最优解为(3.5,2)，最优目标值为14.5，子问题(L2)的最优解为(2.5,3)，最优目标值为13.5.
运筹学2020最新试卷带答案
