王家荣运筹学习题解答.doc
文本预览下载声明
附录一 习题解答
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为基变量
显示全部