2011运筹学复习题
- 格式：doc
- 大小：476.00 KB
- 文档页数：35
2011运筹学复习题
复习范围：
1. 单纯形法求解线性规划问题
2. 对偶问题及互补松弛性
3. 表上作业法求解运输问题
4. 建立整数规划模型（不求解）
5. 匈牙利法求解指派问题
6. 求网络最大流
专项练习：
一、单纯形法求解线性规划问题
例、用单纯形法求下列线性规划问题：
0,825943510max21212121xxxxxxxxz
解：化为标准型
121231241234max105349528,,,0zxxxxxxxxxxxx 用单纯形表进行计算
Cj 10 5 0 0 i
CB 基 b x1 x2 x3 x4
0
0 x3
x4 9
8 3 4 1 0
[5] 2 0 1 3
8/5
cj - zj 10 5 0 0
0
10 x3
x1 21/58/5 0 [14/5] 1 -3/5
1 2/5 0 1/5 3/2
4
cj - zj 0 1 0 -2
5
10 x2
x1 3/2
1 0 1 5/14 -3/14
1 0 -1/7 2/7
cj - zj 0 0 -5/14 -25/14
所有非基变量的检验数全部小于零，所以此线性规划问题有唯一最优解。
最优解X=（1，3/2，0，0）；最优值Z=35/2.
解题步骤
1.化为标准形
2.列表求解
Key：寻找主元（检验数最大，检验比最小）
主元变为1，其余变为0.
3.结论（最优解和最优值）
练习题：
1.
0,242615532max21212121xxxxxxxxz
2.
0,1823122452max21212121xxxxxxxxz
3.
0,,72342263542max32132132321321xxxxxxxxxxxxxxz
4.
0,,3373431131313132max321321321321xxxxxxxxxxxxz
练习题答案
1. 最优解X=（15/4,3/4,0,0），最优值max z=33/4
2. 最优解X=（2,6,2,0,0），最优值max z=34
3. 最优解X=（1,0,2,7,0,0），最优值max z=12
4. 最优解X=（1,2,0,0,0），最优值max z=8
注意细节
1. 右端项b 用于计算检验比，只有系数大于0时才计算检验比；价值系数cj用于计算检验数。
2. 注意自我检查：基变量一定对应到单位矩阵，其检验数一定等于0；最优表给出对偶问题的最优解，对应的最优值等于原问题的最优值。
3. 对矩阵的某行乘以一个较大的数，总能做到所有检验数小于0，所以不要随便通分，如练习4。
二、对偶问题及互补松弛性
例、给出线性规划问题：
)4,3,2,1(096628342max321432214214321ixxxxxxxxxxxxxxxxzi
要求：(1)写出其对偶问题；
(2)已知原问题的最优解为X*=（2,2,4,0），试根据对偶理论，直接求出对偶问题的最优解。
解：(1) 对偶问题为
123412412343413min86692234110 (1,2,3,4)iyyyyyyyyyyyyyyyyi
(2)将最优解(2,2,4,0)带入原问题的约束条件，986628332143221421xxxxxxxxxxx
根据互补松弛性，40y
另一方面，因为1230,0,0xxx，相应的对偶问题的约束条件应取等号。所以
12123322341yyyyyy
解得
12345351yyy
从而，对偶问题的最优解为Y=（4/5, 3/5, 1, 0）,
最优值为 16
解题步骤
1.写出对偶问题的步骤
最大变最小；
系数矩阵转置；
≤变≥；
价值系数与右端项互换。
2.互补松弛性的应用
Key：约束条件对应决策变量
第一步：把最优解带入约束条件，约束条件取不等号，相应的决策变量等于零；
第二步：最优解不为零，对应的约束条件取等号；
第三步：解方程
练习题：
1. 已知线性规划
0,,162210243max321321321321xxxxxxxxxxxxz
的最优解是X*=（6,2,0），
(1)写出原问题的对偶问题；
(2)根据对偶理论直接求出对偶问题的最优解。
2. 已知线性规划
0,,,1222282652max432143214314321xxxxxxxxxxxxxxxz
其对偶问题的最优解为Y*=（4,1），
(1)写出对偶问题；
(2)应用对偶问题的性质，求原问题的最优解。
3. 已知线性规划
0,33253232234max21212121212121xxxxxxxxxxxxxxz
其最优解为X*=（4/5, 3/5），
(1)写出对偶问题；
(2)应用对偶问题的性质，求对偶问题的最优解。
4. 已知线性规划
0,,,2023220322432max4321432143214321xxxxxxxxxxxxxxxxz
其对偶问题的最优解为Y*=（1.2, 0.2），
(1)写出对偶问题；
(2)应用对偶性质，求原问题的最优解
练习题答案
1.对偶问题最优解Y=（1,1），最优值为26
2.原问题的最优解X=（0,0,4,4），最优值为44
3.对偶问题的最优解Y=（1,0,0,0,1），最优值为5
4.原问题的最优解X=（0,0,4,4），最优值为28
注意细节
写对偶问题时，不要忘了决策变量的非负约束；
注意计算最优值，自我检查最优解应满足所有的约束条件，且原问题的最优值应该等于对偶问题的最优值。 三、表上作业法求解运输问题
1、产销平衡问题
例 下表为各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。
销地产地 B1 B2 B3 B4 产量
A1
A2
A3 4
1
3 1
2
7 4
5
5 6
0
1 8
8
4
销量 6 5 6 3 20
解：先用沃格尔法求初始解
销地产地 B1 B2 B3 B4 产量 行罚数
A1
A2
A3 4
1
3 1
2
7 4
5
5 6
0
1 8
8
4 3 0 2 2
1 1 5
2 2 4 4
销量 6 5 6 3
列罚数 2
2
1
1
1
1
1 1
1
1
5 得初始调运方案：
B1 B2 B3 B4
A1 5 3
A2 6 2
A3 3 1
下面用位势法进行检验：
B1 B2 B3 B4 ui
A1 3 6 0
A2 1 1 0
A3 1 5 1
vi 1 1 4 0
所有检验数≥0，此时问题已达到最优解
总运费 min z =5*1+3*4+6*1+2*0+3*5+1*1=39
解题步骤
1.先用沃格尔法或者最小元素法求出初始解
沃格尔法：优先供应罚数大的运输任务
最小元素法：优先考虑所有任务中的最低运价。
2.再用位势法或者闭回路法进行检验
位势法：令任意一个位势为0（不妨u1=0），计算位势和检验数：数格对应的运价等于位势和；
空格对应的运价减去位势和等于检验数。 3.若不是最优解，用闭回路法调整后回到第2步
检验数全部大于等于零，得到最优解；
调整检验数小于零的空格所对应的闭回路：
以该空格为第一个奇数顶点，找出偶数顶点中最小的运输量为调整量，奇数顶点加上调整量，偶数顶点减去调整量。
练习题：
1. 求最优调运方案（写出min值）
销地产地 B1 B2 B3 B4 产量
A1
A2
A3 10
16
5 6
10
4 7
5
10 12
9
10 4
9
4
销量 5 2 4 6
2. 求最优调运方案（写出min值）
销地产地 B1 B2 B3 B4 产量
A1
A2
A3 3
2
4 7
4
3 6
3
8 4
2
5 5
2
3
销量 3 3 2 2
