王家荣运筹学习题解答.docVIP

附录一 习题解答 Appendix 1 Solutions of Exercises 第一章 线性规划 以下集合中，哪些是凸集，哪些不是凸集？ {(x1,x2)| x1+x2≤1} 是凸集 {(x1,x2,x3)| x1+x2≤1,x1-x3≤2} 是凸集 {(x1,x2)| x1-x2=0} 是凸集 {(x1,x2,x3)| x1≥x2,x1+x2+x3≤6} 是凸集 {(x1,x2)| x1=1,|x2|≤4} 是凸集 {(x1,x2,x3)| x3=|x2|, x1≤4} 不是凸集 求出以下不等式组所定义的多面体的所有极点。 （1） x1 +x2 +x3 ≤5 -x1 +x2 +2x3 ≤6 x1, x2, x3 ≥0 解：引进松弛变量x4，x5≥0 x1 +x2 +x3 +x4 =5 -x1 +x2 +2x3 +x5 =6 x1, x2, x3 x4, x5 ≥0 令 ， 在A矩阵中，一共有10个行列式不等于0的方阵，即10个基。 ， ， ， ， ， ， ， ， ， ， 相应的基础解是 X1= （x1，x2，x3，x4，x5）=（-1/2，11/2，0，0，0） X2= （x1，x2，x3，x4，x5）=（4/3，0，11/3，0，0） X3= （x1，x2，x3，x4，x5）=（-6，0，0，11，0） X4= （x1，x2，x3，x4，x5）=（5，0，0，0，11） X5= （x1，x2，x3，x4，x5）=（0，4，1，0，0） X6= （x1，x2，x3，x4，x5）=（0，5，0，-1，0） X7= （x1，x2，x3，x4，x5）=（0，5，0，0，1） X8= （x1，x2，x3，x4，x5）=（0，0，3，2，0） X9= （x1，x2，x3，x4，x5）=（0，0，5，0，-4） X10=（x1，x2，x3，x4，x5）=（0，0，0，5，6） 其中B2、B4、B5、B7、B8、B10是可行基，相应的基础可行解为： X2= （x1，x2，x3，x4，x5）=（4/3，11/3，0，0，0） X4= （x1，x2，x3，x4，x5）=（5，0，0，0，11） X5= （x1，x2，x3，x4，x5）=（0，4，1，0，0） X7= （x1，x2，x3，x4，x5）=（0，5，0，0，1） X8= （x1，x2，x3，x4，x5）=（0，0，3，2，0） X10=（x1，x2，x3，x4，x5）=（0，0，0，5，6） 原问题的极点是： X2= （x1，x2，x3）=（4/3，11/3，0） X4= （x1，x2，x3）=（5，0，0） X5= （x1，x2，x3）=（0，4，1） X7= （x1，x2，x3）=（0，5，0） X8= （x1，x2，x3）=（0，0，3） X10=（x1，x2，x3）=（0，0，0） （2） x1 +x2 +x3 ≤1 -x1 +2x2 ≤4 x1, x2, x3 ≥0 解：引进松弛变量x4，x5≥0 x1 +x2 +x3 +x4 =1 -x1 +2x2 +x5 =4 x1, x2, x3 x4, x5 ≥0 令 ， A矩阵中共有9个基。 x1、x2为基变量，得到： x1 +x2 =1 -x1 +2x2 =4 求解这个方程组，得到x1=-2/3，x2=5/3；（x1,x2,x3,x4,x5）=（-2/3,5/3,0,0,0） x1、x3为基变量，得到： x1 +x3 =1 -x1 =4 求解这个方程组，得到x1=-4，x3=5；（x1,x2,x3,x4,x5）=（-4,0,5,0,0） x1、x4为基变量，得到： x1 +x4 =1 -x1 =4 求解这个方程组，得到x1=-4，x4=5；（x1,x2,x3,x4,x5）=（-4,0,0,5,0） x1、x5为基变量，得到： x1 =1 -x1 +x5 =4 求解这个方程组，得到x1=1，x2=5；（x1,x2,x3,x4,x5）=（1,0,0,0,5） x2、x3为基变量，得到： x2 +x3 =1 2x2 =4 求解这个方程组，得到x2=2，x3=-1；（x1,x2,x3,x4,x5）=（0,2,-1,0,0） x1、x4为基变量，得到： x2 +x4 =1 2x2 =4 求解这个方程组，得到x2=2，x4=-1；（x1,x2,x3,x4,x5）=（0,2,0,-1,0） x2、x5为基变量，得到： x2 =1 2x2 +x5 =4 求解这个方程组，得到x1=1，x5=2；（x1,x2,x3,x4,x5）=（0,1,0,0,2） x3、x5为基变量