一、判断题(判断正误，共5道小题)
1. 线性规划问题的一般模型中不能出现等式约束
正确答案：说法错误
2. 在线性规划模型的标准型中,bj （j=1，2，…m）一定是非负的
正确答案：说法正确
3. 线性规划一般模型中的变量不一定是非负的
正确答案：说法正确
4. 用图解法求最优解时，只需求出可行域顶点对应的目标值，通过比较大小，就能找
出最优解
正确答案：说法正确
5. 一般情况下，松弛变量和多余变量的目标函数系数为零
正确答案：说法正确
二、主观题(共6道小题)
6. 简述线性规划问题数学模型的组成部分及其特征
参：
7. 简述建立线性规划问题数学模型的步骤
参：1.确定决策变量2.确定目标函数3.确定约束条件方程
8. 简述化一般线性规划模型为标准型的方法
参：
9.
参：
10.
参：（1）（1，3/2），Z=35/2；（2）（5，0），Z=-5；（3）无限解；（4）（-2，3），Z=7
11.
参：
| 本次作业是本门课程本学期的第2次作业，注释如下：“用单纯形法求解下列线性规划”只做第（4）题；“分别用大M法和两阶段法求解下列线性规划”只做第（1）题。 |
1. X是线性规划的基本可行解则有（ ）
(A) X中的基变量非零，非基变量为零 (B) X不一定满足约束条件
(C) X中的基变量非负，非基变量为零 (D) X是最优解
正确答案：C
(A) 非基变量的检验数为零 (B) 最小比值为零
(C) 基可行解中存在为零的基变量 (D) 非基变量为零
正确答案：C
(A) 包含原点X=(0,0,…,0) (B) 有界
(C) 无界 (D) 是凸集
正确答案：D
二、判断题(判断正误，共6道小题)
4. 线性规划问题的基本解一定是基本可行解
正确答案：说法错误
5. 线性规划问题的最优解只能在可行域的顶点上达到
正确答案：说法错误
6. 图解法与单纯形法求解的形式不同，但从几何上理解，两者是一致的
正确答案：说法正确
7. 单纯形法计算中，选取最大正检验数对应的变量作为换入变量，将使目标函数的值增加更快
正确答案：说法错误
8. 同一问题的线性规划模型是唯一的
正确答案：说法错误
9. 由应用问题建立的线性规划模型中，其约束方程有多种形式
正确答案：说法正确
三、主观题(共14道小题)
| 10. 针对不同形式的约束（≥，=，≤）简述初始基本可行解的选取方法 |
| 参：对于≥和=形式的约束，一般将引入的人工变量作为初始基变量；≤形式的约束，一般将引入的松弛变量作为初始基变量。 |
| 11. 简述如何在单纯型表上判别问题是否具有唯一解、无穷多解、无界解或无可行解 |
| 参：最优单纯形表中，有且仅有基变量的检验数为零，则可判断该解为唯一最优解；最优单纯形表中，除基变量的检验数为零外，又存在某个非基变量的检验数为零，则可判断该问题有无穷多最优解；若单纯形表中存在检验数大于零的变量，该变量对应的系数全都小于等于零，那么该线性规划问题具有无界解；最优单纯形表中，若人工变量不为零，则该线性规划问题无可行解。 |
| 12. 简述若标准型变为求目标函数最小，则用单纯形法计算时，如何判别问题已取得最优解 |
| 参： |
参：1，4不可行；2，3可行
14、
参： （1）生产方案是：不生产1、3两种产品，只生产第2种产品100/3个单位，不是最优方案。
（2）30，45，15. （3）最优生产方案：不生产第3种产品，1、2两种产品各生产20个单位，最大利润1700
15、
.
参：（1）不可行。 （2）多重解。 （3）若a12、a22、a32全是0或负数时
16、
参：
（1）a =2，b =0，c =0，d =1，e =4/5，f =0， g =-5；最优解。
（2）a =7，b =-6，c =0，d =1，e =0，f =1/3， g =0；最优解
17.
参：
（1）X =（12/7，15/7），Z =-120/7；
（2）X =（5/6，0，17/5，0，0），Z =81/5；
（3）X =（2，6），Z =36；
（4）X =（-3，0），Z =-9
18、
参：（1）X =（4，2），Z =28； （2）无限界解
| 19. 若基本可行解中非0变量的个数( )于约束条件的个数时，就会出现退化解 |
| 参：小 |
| 20. 线性规划问题若有最优解，一定可以在可行域的( )达到 |
| 参：顶点 |
| 21. 确定初始基本可行解时，对大于型的约束，应当引入( )变量 |
| 参：人工 |
| 22. 目标函数中人工变量前面的系数±M（M是充分大的正数）的作用是 |
| 参：使人工变量不可能进入最优解 |
| 23. 解包含人工变量线性规划问题的单纯形法有( )有( ) |
| 参：大M法、两阶段法 |
| 本次作业是本门课程本学期的第3次作业，注释如下： | |
1. 任何线性规划问题存在并具有唯一的对偶问题
正确答案：说法正确
2. 对偶问题的对偶不一定是原问题
正确答案：说法错误
3. 若原问题可行，而对偶问题不可行，则原问题无界
正确答案：说法正确
4. 若原问题有无穷多最优解，则其对偶问题也一定有无穷多最优解
正确答案：说法正确
5. yi为对偶问题的最优解，若yi>0，说明在最优生产计划中第i种资源已完全耗尽
正确答案：说法正确
| 6. 简述对偶单纯形法的计算过程及它的优点 |
| 参： |
| 7. 怎样根据最优单纯形表找出原问题与对偶问题的变量、最优解及检验数之间的对应关系 |
| 参： |
| 8. |
| 参：依次为q4，q5，q1，q2，q3，对偶问题的解为（0，1/4，1/2） |
| 9. |
| 参：不是最优解，因为x6=-5不可行。最优解为（15，65/3，5），对偶问题的最优解为（6，9，1） |
| 10. 对偶单纯形法与单纯形法的主要区别是每次迭代的基变量都满足最优检验但不完全满足 约束 |
| 参：非负 |
| 11. 若原问题有最优解，那么对偶问题 有最优解，且原问题与对偶问题的最优 相等 |
| 参：一定 ，目标值 |
| 12. 原问题可行，而对偶问题不可行，则原问题 界 |
| 参：无 |
| 13. 对偶问题的对偶问题是 问题 |
| 参：原 |
| 14. 若原问题中第i个约束条件是“=”型约束，那么对偶问题的变量qi应是 变量 |
| 参：自由 |
| 本次作业是本门课程本学期的第4次作业，注释如下：“分别用西北角法、最小元素法、差值法确定下列运输问题作业表中的一组初始可行解，并求出（1），（2），（3）的最优解”只做第（1）小题。 | |
| 一、单项选择题(只有一个选项正确，共1道小题) |
(A) 有11个变量
(B) 有10个约束
(C) 有30约束
(D) 有10个基变量
正确答案：D
2. 运输问题的求解结果可能出现下列4种情况之一：有唯一解；有无穷多最优解；无界解；可行解
正确答案：说法错误
3. 在运输问题中，只要给出一组含有（m + n -1）个非零的xij且满足全部约束，就可以作为基本可行解
正确答案：说法错误
4. 按最小元素法给出的初始基本可行解，从每一个空格出发仅能找出唯一的闭回路
正确答案：说法正确
5. 表上作业法中，任何一种确定初始基本可行解的方法都必须保证有（m + n -1）个变量
正确答案：说法正确
6. 当所有产量和销量均为整数值时，运输问题的最优解也为整数解
正确答案：说法错误
| 三、主观题(共6道小题) |
参：
西北角法的基本思想是优先满足西北角位置的供销需求，逐步给出初始基可行解为止。最小元素法基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小。一直到给出初始基可行解为止。差值法基本思想是优先满足运费差值最大的供销需求，逐步给出初始基可行解。三种方法比较，差值法得出的解较优。
| 8. 简述把产销不平衡化为产销平衡问题的基本过程 |
| 参： |
| 9. 简述运输方案的调整过程 |
| 参：当在表中空格处出现负检验数时，表明未得最优解。同单纯形法一样，调整的关键在于确定换入变量，换出变量以及调整值。对表上作业法而言，若有两个和两个以上的负检验数时，一般选其中最小的负检验数，以它对应的空格为调入格。即以它对应的非基变量为换入变量。在换入变量空格的闭回路中，取标负号且运输量最小的数字格所对应的基变量为换出变量，以保证所有变量非负的约束。调整值即为换出变量的值。 |
参：（1）可以 （2）不能，非零元素少于9个。（3）不能，有闭回路。（4）可以
11. 根据表判断是否已取得了最优解，为什么？
| 参：（1）不是最优解。（2）是。 （3）不是 |
参：
（1）最优解：A1 →B1，35；A1 →B2，15；A2 →B2，25；A2 →B3，20； A2 →B4，15； A3 →B1，25；
（2）增加一个销售点，最优解：A1 →B4，10；A1→虚售点，90；A2 →B1，50；A2 →B3，50；A3 →B2，70；A3 →B3，10；A3 →B4，70；
（3）增加一个产地，最优解：A1 →B1，5；A1 →B2，15；A1 →B3，5；A1 →B4，15； A2 →B4，30；A3 →B3，30；虚产地 →B4，5；
一、单项选择题(只有一个选项正确，共3道小题)
1. 在图论中，图与网络的区别是( )
(A) 图中含有点，网络中没有点. (B) 图中含有边，网络中没有边.
(C) 在图的边上赋权就成了网络. (D) 图中含有链，网络中没有链.
正确答案：C
(A) 源即接收流量也发出流量 (B) 汇即接收流量也发出流量
(C) 中间点即接收流量也发出流量 (D) 以上说法都不正确
正确答案：C
3. 流f为网络G的最大流的充要条件是（ ）
(A) 网络G中不含有流f的增流链 (B) 网络G中不含有流f的不饱和链
(C) 网络G中所有的链都是饱和链 (D) 以上答案都不对
正确答案：A
4. 任一图G中，当点集确定之后，树图是G中边数最少的连通图。
正确答案：说法正确
5.
正确答案：说法错误
6. 第一个顶点和最后一个顶点相同的闭链叫回路
正确答案：说法错误
7. 第一个顶点和最后一个顶点相同的闭链叫回路
正确答案：说法错误
8. 数T的任两顶点间恰有一条初等链
正确答案：说法正确
9. Djisktra算法可求出非负赋权图中一顶点到任一顶点的最短距离
正确答案：说法正确
10. 标号法每迭代一步，没有取得永久性标号顶点的标号都会被改变一次
正确答案：说法正确
11. 简述G=（V，E）来表示图时，符号V，E的意义
参：
V 表示图 G 的点集合，E 表示图 G 的边集合。
12. 网络的最小费用流与最小费用最大流是什么关系
参：答：网络的最小费用流是指网络的流值等于某一目标流的流值时，在这所有的流中费用最小的流；也就是在满足某一目标运输量下，所有的运输方案中，运输费用最小的运输方案。而网络的最小费用最大流是指在网络流值达到最大时，所有流中费用最小的流；也就是达到运输网络最大运输量的所有运输方案中，运输费用最小的运输方案。可以看出，网络的最小费用最大流是网络的最小费用流的一种特殊情况，即目标流的流值等于最大流的的流值的情况
13.
参：（1）路线：（1）—（4）—（3）—（5）（2）路径：（1）→（3）→（2）→（4）→（5）下载本文
