一、填空
1线性规划的约束条件个数与其对偶问题的______相等；而若线性规划的约束条件是方程则对偶问题的_________。
2.一个_________且________的图称为树
3．用表上作业法求解总运输成本最小的运输问题时，当各个空格的改进指数都 0时，已得最优运输方案。
4. 线性规划问题的数学模型中目标函数和约束函数都是 函数。
5. .单纯形法求解线性规划问题时为进行换基迭代，选择基变量转变为非基变量时所依据的原则是保证变量_____________。
6.为求解需要量大于供应量的运输问题，可虚设一个供应点，该点的供应量等于_____________。
7.除图解法外，常用的求解线性规划问题的方法是_______________法。
8. 在线性规划中求极小值时，每当引入一个人工变量，就需要在目标函数中为该变量增加一项，其系数取_________
9. 为求解供应量大于需要量的运输问题，可虚设一个需求点，该点的需求量等于____________。
10. .线性规划的图解法一般只适用于解_______个变量的线性规划问题。 11. 图的组成要素 ； 。
二、单选在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.当线性规划问题的一个基解满足下列哪项要求时称之为一个可行基解？（ ） A.大于0 C.非负
2.下列说法正确的是（ ） A.修正分配法是闭合回路法的基础
B.在判别某个方案是否最优时，修正分配法比闭合回路法简单
C.在判别某个方案是否最优时，修正分配法对所有空格寻求闭合的改进路线 D.所有运输问题都是供需相等的
3.对于总运输费用最小的运输问题，若已得最优运输方案，则其中所有空格的改进指数必
（ ）
A.大于或等于0 C.大于0
B.小于或等于0 D.小于0 B.小于0 D.非正
4.某人要从上海乘飞机到奥地利首都维也纳，他希望选择一条航线，经过转机，使他在空中飞行的时间尽可能短。该问题可转化为（ ） A.最短路线问题求解 C.最小枝杈树问题求解
B.最大流量问题求解 D.树的生成问题求解
5.在下面的数学模型中，属于线性规划模型的为（ ） ?max?A.?s.t.??S?4X?YXY?3 X,Y?0?min?B.?s.t.??S?3X?Y2X?Y??1 X,Y?0?max?C.?s.t.??
S?X2?Y2X?Y?2 X,Y?0?min?D.?s.t.??S?2XYX?Y?3 X,Y?06．下列叙述正确的是( )
A．线性规划问题，若有最优解，则必是一个基变量组的可行基解 B．线性规划问题一定有可行基解
C．线性规划问题的最优解只能在极点上达到
D．单纯形法求解线性规划问题时每换基迭代一次必使目标函数值下降一次 7．对于m个发点、n个收点的运输问题，叙述错误的是( ) A．该问题的系数矩阵有m×n列
B．该问题的系数矩阵有m+n行 D．该问题的最优解必唯一
C．该问题的系数矩阵的秩必为m+n-1
8．对于供需平衡的运输问题和供需不平衡的运输问题，其结构模型是( ) A．相同的
B．不同的 D．无法求解的
C．与线性规划的模型结构一样的
9.n个点的不连通图，其边数（ ） A.必然少于n－1 C.必然多于n－1
B.必然等于n－1 D.可能多于n－1
10.若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ ） A.两个 C.无穷多个
B.零个 D.有限多个
11.求运输问题的解就是求满足要求的（ ） A.各供应点到各需求点的运费 C.各供应点到各需求点的运量
B.总运费 D.总运量
12.某二维线性规划问题的可行域如题6图阴影所示，则该问题的最优解（ ） A.必在正方形的某个顶点达到 B.必在正方形内部达到 C.必在正方形外部达到 D.必在AB边上达到
13.关于运输问题的说法中错误的是（ ） ．．A.最优运输方案未必唯一 B.必有最优运输方案
C.运输方案的任何调整必会引起总运费的下降
D.修正分配法是一种比较简单的计算改进指数的方法
14. 考虑某运输问题，其需求量和供应量相等，且供应点的个数为m，需求点的个数是n。若以西北角法求得其初始运输方案，则该方案中数字格的数目应为（ ） A.（m+n）个 B.（m+n-1）个 C.（m-n）个 D.（m-n+1）个
15.在解运输问题时，若调整路线已确定，则调整运量应为（ ） A.负号格的最小运量 B.负号格的最大运量 C.正号格的最小运量 D.正号格的最大运量
16. 关于线性规划模型的可行解区，叙述正确的为（ ）
A.可行解区必有界 C.可行解区必是凸的
B.可行解区必然包括原点 D.可行解区内必有无穷多个点
三、判断
一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。)
1. 图解法提供了求解线性规划问题的通用方法。
( )
2. 用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的检验数Cj-Zj
≥0，则问题达到最优。
3. 在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。 4. 满足线性规划问题所有约束条件的解称为基本可行解。
5. 在线性规划问题的求解过程中，基变量和非基变量的个数是固定的。 6. 对偶问题的目标函数总是与原问题目标函数相等。 7. 原问题与对偶问题是一一对应的。
8. 运输问题的可行解中基变量的个数一定遵循m＋n－1的规则。 9. 指派问题的解中基变量的个数为m＋n。
10. 网络最短路径是指从网络起点至终点的一条权和最小的路线。 11. 网络最大流量是网络起点至终点的一条增流链上的最大流量。
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )
12. 工程计划网络中的关键路线上事项的最早时间和最迟时间往往不相等。 ( ) 13. 在确定性存贮模型中不许缺货的条件下，当费用项目相同时，生产模型的间隔时间比订购模型的间隔时间长。
14. 单目标决策时，用不同方法确定的最佳方案往往是一致的。
( ) ( )
15. 动态规划中运用图解法的顺推方法和网络最短路径的标号法上是一致的。
( )
四、计算
1.Maximize 成本=15 x1+20 x2 约束条件 约束1：x1+ 2x2?10 约束2：2x1?3x2?6 约束3：x1+x2?6 和 x1?0，x2?0
a) 用图解法求解这个模型。（最优解：（x1, x2）=（2, 4），C=110）
2.某饲料厂用四种含蛋白质、葡萄糖、氨基酸的原料，配制一种新营养保健品，要求含蛋白质不少于20%，葡萄糖不少于35%，氨基酸不少于30%。四种原料中蛋白质、葡萄糖、氨基酸的含量及价格如下表： 原料 成分 蛋白质 % 葡萄糖 % 氨基酸 % 价(元) 30 20 40 30 40 30 25 40 20 25 55 35 15 40 30 50 1 2 3 4
由于技术上的原因，原料2的用量不能少于30%，原料4不能超过40%。试建立一个线性规划模型，以便求得成本最低而又合乎要求的新营养保健品。
3. .用图解法求解下述线性规划问题，并说明在最优解处哪些约束成为等式。 ?max 8X1?6X2?s.t. 2X1?X2?30 (1)??(2) ? 2X1?3X2?36 ? X?0 (3)1??(4)? X2?0 4. ．某厂用A(80)，B(60)两种资源生产甲、乙两种产品，设x1,x2分别为甲、乙的计划产量，
为使该厂获得最大利润，建立了线性规划 max Z=100X1+80X2
?2X1?4X2?80?s.t.?3X1?X2?60 ?X,X?012?用单纯形法求解此问题时得到单纯形表如题33表：
题33表 cj 100 80 0 0 cB 80 100 xB x2 x1 cj-zj b 12 16 x1 0 1 0 x2 1 0 0 x3 3/10 -1/10 x4 -1/5 2/5 (1)试完成该表格，并求出最优生产方案； (2)若按该方案进行生产，哪些资源将用尽?
5. 自来水公司欲在某地区各高层住宅楼间铺设自来水管道并与主管道相连。其位置如题35图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离（单位：百米）。 问：（1）如何铺设才能使所用管道最少？（2）需用管长多少？
6. 城市A到城市B的交通道路如题34图所示，线上标注的数字为两点间距离(单位：万米)。某公司现需从A市紧急运送一批货物到B市。假设各条线路的交通状况相同，请为该公司寻求一条最佳路线。
下列表是线性规划单纯形表（求Zmax），请根据单纯形法原理和算法。
1. 计算该规划的检验数
Ci 3 2
Cj xB x1 x3 z j
→ b
3 x1 1 0 3
2 x2
1 21 3.5
0 x3 0 1 2
0 x4 -1 1/2 -2
0 x5 0 0 0
3 4
c j－z j
运筹学试题
