运筹学自学指导书.doc

1
《运筹学》自学指导书
张尚立
第一章 线性规划及单纯形法
重点：线性规划数学模型的标准化。
单纯形法求解线性规划模型。
§１、§３、§４
重点掌握：
　　一、将一般的线性规划模型化为标准的线性规划模型V3 V5
4
V6
V2 V4
2
V1
5
五、
3
1
练习题2：
4
一、将下列线性规划模型化为标准型
1）minz = 2x1 + 3x2 – 5x3
- x1 – x2 – x3 = -7
2x1 - 5x2 + x3 ≥10
x1, x2≥0
x1 + 4x2 + 2x3 ≥8
3x1 + 2x2 ≥6
x1, x2, x3≥0
2）minz = 2x1 + 3x2 + x3
5x1 + 3x2 + x3 ≤9
2x1 + x2 + x3 ≥5
x1, x2,x3 ≥0
3）minz = 5x1 - 2x2 + 3x3
二、用单纯形法求解
1）maxz = 2x1 + 3x2
x1 + 2 x2≤8
4x1≤16
4x2≤12
x1, x2≥0
3x1 + 5 x2≤15
6x1 + 2 x2≤24
x1, x2≥0
2）maxz = 2x1 + x2

三、用对偶单纯形法求解
1）minw = 8x1 + 16x2 + 12x3
x1 + 4 x2≥2
2x1 + 4 x2≥3
x1, x2, x3≥0

2）minw = 2x1 + 3x2 + 3x3
x1 + x2 + 3x3 ≥4
2x1 - x2 + x3 ≥3
x1, x2,x3 ≥0
四、用表上作业法求解运输问题
5
销地
产地
B1
B2
B3
B4
产量
A1
3
7
6
4
5
A2
2
4
3
2
2
A3
4
3
8
5
3
销量
3
3
2
~
五、求解整数规划问题
maxz = 40x1 + 90x2
9x1 + 7x2 ≤56
7x1 + 20x2 ≤70
x1, x2 ≥0
x1, x2整数
六、求解0-1型整数规划问题
maxz = 3x1 - 2x2 + 5x3
x1 + 2x2 - x3 ≤2
x1 + 4x2 + x3 ≤4
x1 + x2 ≤3
4x1 + x3 ≤6
x1, x2,x3 = 0或1
七、求下图的一个最小支撑树
V1 5 V4 2
V5
1
3
4
6
3
V6
V3
4
V2
5
7
3
6
V7
参考答案：
一、1）= -2x1 - 3x2 + 5x4 – 5x5
x1 + x2 + x4 – x5 =7
2 x1 –5x2 + x4 –x5