运筹学复习题型(推荐).docx

基本要求
一、将线性规划化为标准型和写出相应的对偶规划；
二、用图解法求解具有两个决策变量的线性规划问题；
三、用单纯形方法及人工变量法求解线性规划问题；
四、灵敏度分析；
五、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题3
3y1y32
2%2y24y35
7yi2y2y37
yi0,y20,y30
对偶单纯形法
基本要求：检验数0；资源常数存在负值。
解法：
.列出对偶单纯形表；
.将基变量在目标函数中系数化为零，检验数为新目标函数中系数的相反数；
.判断，若0,b0,则当前解为最优解；
若0,且b中存在负项，则进行迭代，确定出基和进基变量;
出基：记brminbib0,xk为第r行对应的变量；
进基：/dmin^a1ari0,xs为进基变量；
以ars为主元进行迭代。目标：将主元化为1,该列的其余元化为0。
灵敏度分析
灵敏度分析的任务：确定各个变量使得最优解保持不变的变化范围；以及在最优解改变的时候求出相应的最优解。
⑴非基变量x的价值系数c的变化范围，使最优解保持不变。
cii
⑵基变量xi的价值系数ci的变化范围，使最优解保持不变。
ci:maxarj0cminaj0.
arjarj
若最优解改变，则对两种情况有c.
⑶资源常数bk变化范围使最优基不变：
bk ： max
ik
ik
min bi
ik
ik 0 k 1,2,L ,m
⑷非基变量xk的系数向量k的增量k的变化范围使最优解不变：
kkcBB1k0，
⑸增加新的决策变量使最优解保持不变：kCbB1kck0
例：设线性规划
maxz10xi6x24x3
x1x2x3100,10x14x25x3600,2x12x26x3300,xi0,i1,2,3.
求：；
.确定c1,c2,c3的范围，使最优解不变；取C3—，求最优解；
6
.确定b1，b2,b3的范围，使最优基不变，取b1100,求最优解；
T
.引入x7,P71,4,3,c78求最优解；

50
6 3
x
X1
X2
X3
X4
X5
x6
c
10
6
4
0
0
0
X4
1
1
1
1
0
0
100
x5
10
4
5
0
1
0
600
x6
2
2
6
0
0
1
300
10
6
4
0
0
0
3
1
1
X4
0
1
0
40
5
2
10
2
1
1
为
1
0
0
60
5
2
10
x6
0
6
5
0
1
1
180
5
5
0
2
1
0
1
0
600
0
1
5
5
1
0
200
X2
—
——
——
—
6
3
6
3
1
0
1
2
1
0
100
为
—
—
—
—
6
3
6
3
x6
0
0
4
2
0
1
100
81022200
000
3333
T
7100200c2200
即，原问题的最优解为X,——,0,z
，故当C338时，即C320时，最优解不变；
33
X,x2为基变量，由公式，当4c15,2c24,最优解不变，即
6c115,4c210时，最优解不变
现对c3
20
——,最优解改变，此时3
8 13
3 3
5
一,原最优表为
3
x
X1
X2
X3
X4
x5
x6
25
c
10
6
3
0
0
0
0
1
5
5
1
0
200
x2
一
—
——
—
6
3
6
3
1
0
1
2
1
0
100
X1
—
—
—
—
6
3
6
3
x6
0
0
4
2
0
1
100
0
0
5
10
2
0
2200
3
3
3
3
0
1
0
25
1
5
275
X2
——
12
6
24
6
1
0
0
7
1
1
175
X1
12
6
24
6
X3
0
0
1
1
0
1
25