运筹学习题集(第二章).doc

运筹学****题集(第二章)
2
判 断 题
判断正误，如果错误请更正
第二章 线形规划的对偶理论
原问题第i个约束是<=约束,则对偶变量yi>=0.
互为对偶问题,或则同时都有最优解,或则同时都无最优解.
0
9
X4
-1
2
0
1
1
0
6
X3
2
-1
1
0
-1
0
9
X6
[-5]
4
0
0
2
1
-10
X1
X2
X3
X4
X5
X6
右端
z
0
-19/5
0
0
-7/5
-1/5
11
X4
0
6/5
0
1
3/5
-1/5
8
X3
0
3/5
1
0
-1/5
2/5
5
X1
1
-4/5
0
0
-2/5
-1/5
2
原始问题的最优解为（X1 X2 X3 X4 X5 X6）=（2，0，5，8，0，0），minz=11
对偶问题的最优解为（y1 y2 y3 y4 y5 y6）=（0，7/5，-1/5，0，19/5，0），maxw=11
对于以下线性规划问题
max z = -x1 - 2x2
. -2x1 + 3x2 12 (1)
-3x1 + x2 6 (2)
x1 + 3x2 3 (3)
x1 0， x2 0
1、写出标准化的线性规划问题；
6
2、用单纯形表求出这个线性规划问题的最优解和最优的目标函数值；
3、 写出这个（极大化）线性规划问题的对偶问题；
4、 求出对偶问题的最优解和最优解的目标函数值；
5、 第（2）个约束右端常数b2=6在什么范围内变化，最优解保持不变。
解答：1、写出标准化的线性规划问题:令x1*=- x1
max z = x1* - 2x2
. 2x1* + 3x2 + x3 = 12 (1)
3x1* + x2 + x4 = 6 (2)
-x1* + 3x2 -x5 = 3 (3)
x1* x2 x3 x4 x5 0
2、（6分）用单纯形表求出这个线性规划问题的最优解和最优的目标函数值

x1*
X2
X3
X4
X5
R
右端
Z’
1-M
3M-2
0
0
-M
0
3M
X3
2
3
1
0
0
0
12
X4
3
1
0
1
0
0
6
R
-1
[3]
0
0
-1
1
3
x1*
X2
X3
X4
X5
R
右端
Z’
1/3
0
0
0
-2/3
2/3-M
2
X3
3
0
1
0
1
-1
9
X4
[10/3]
0
0
1
1/3
-1/3
5
X2
-1/3
1
0
0
-1/3
1/3
1
x1*
X2
X3
X4
X5
R
右端
Z’
0
0
0
-1/10
-7/10
21/30-M
3/2
X3
0
0
1
-9/10
9/2
X1*
1
0
0
3/10
1/10
-1/10
3/2
X2
0
1
0
1/10
3/2
7
此时最优解为（X1、X2、X3、X4 X5）=（-3/2，3/2，9/2，0，0）maxz=-3/2
3、写出这个（极大化）线性规划问题的对偶问题；
min w = 12y1 + 6y2 + 3y3
. -2y1 - 3y2 + y3 -1 (1)
3y1 + y2 + 3 y3 -2 (2)
y1 0、 y2 0、y3 0
4、求出对偶问题的最优解和最优解的目标函数值；
此时最优解为（y1、y2、y3、y4 y5）=（0，1/10,-7/10，0，0）minw =-3/2
5、则有1b211，最优解不变。
已知LP问题：
max z = x1 + 2x2 +3x3 + 4x4
. x1 + 2