、辨析题（本题共5小题，每小题3分，共15分）

1、线性规划模型中，设系数矩阵A＝，则X＝（0，0，2，3，4，0）T有无可能是A的基可行解？

有可能（1分）。基可行解中非零值的个数不超过m，（题中m＝3），给定解中X有3个非零值分量。（2分）

2、m个发点和n个收点的运输问题中，有m+n个相互独立的约束条件。

错（1分）。相互独立的约束条件有m+n-1（2分）。

3、一个赋权图的最小生成树是否唯一？为什么？

不是唯一的。（1分）因为可以该赋权图中边的所赋权可能是相同的，在这种情况下得到的最小生成树可能就不唯一的。（2分）

4、用单纯形法求解极大化问题的线性规划问题时，与对应的变量都可以被选为换入变量吗？为什么？

答：可以。（1分）因为检验数大于零，把作为换入变量，仍然可以改进目标函数值。（2分）

5、已知网络上某条链如下图，问：x为何值时，该链是增流链，为什么？     

答：x＝0（1分）。此时后向边不为零边，不符合增流链定义（2分）。

二、某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。（15分）

（1）写出问题的数学模型

（2）求获最大利润的方案。

	甲	乙	设备能力
设备A	3	2	65
设备B	2	1	40
设备C	0	3	75
利润（元/件）	1500	2500

解：设甲、乙产品分别生产x1,x2件，线性规划模型为

      

利用单纯形法进行求解为

	Cj	1500	2500	0	0	0
CB	xB	x1	x2	x3	x4	x5	b
0	x3	3	2	1	0	0	65	32.5
0	x4	2	1	0	1	0	40	40
0	x5	0	(3)	0	0	1	75	25
	r	1500	2500	0	0	0	0
0	x3	(3)	0	1	0	-2/3	15	5
0	X4	2	0	0	1	-1/3	15	7.5
2500	X2	0	1	0	0	1/3	25
	r	1500	0	0	0	-833.3	8
1500	X1	1	0	1/3	0	-0.2222	5
0	X4	0	0	-2/3	1	0.1111	5
2500	x2	0	1	0	0	1/4	25
	r	0	0	-500	0	-500

最优解为:X*=(5, 25, 0, 5, 0)T, 目标函数最优值70000.

三、用图解法找出以下目标规划问题的满意解。（10分）

                  

满意解为（50，0） d1+=0,d1-=0,d2+=130,d2-=0，d3+=300,d3-=0

四、对于线性规划模型：（10分）

max f =x1+2x2+3x3+4x4

s.t. x1+2x2+2x3+3x420

  2x1+x2+3x3+2x420

x10，x20，x30，x40

已知其对偶问题的最优解U*＝（6/5，1/5），利用互补松弛性求解原问题的解。

解：原问题的对偶问题为

min z =20u1+20u2

s.t. u1+2u21  （1）

2u1+u22     （2）

2u1+3u23    （3）

3u1+2u24    （4）

            u10，u20            （5分）

将U*＝（6/5，1/5）代入对偶问题，（1）、（2）式为严格不等式，则有，

因为，，所以有

2x3+3x4＝20

3x3+2x4＝20

解得，。（5分）