运筹学复习参考知识点及习题.docx

第一部分线性规划问题的求解
一、两个变量的线性规划问题的图解法：
㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可
行（解）域。
定义：达到目标的可行解为最优解。
㈡图解法：
图解法采用直角坐标求解：X1——横axz=0x1+ax2+・+nxn
.
a11x1a12x2a21x1a22x2
am1x1am2x2
xj0，j
对第i个方程加入松弛变量
a11x1a12x2
a21x1a22x2
am1x1am2x2
xj0，j
a1nxn
a2nxn
amnxn
列表计算，格式、算法如下：
2，
xn+i，i=1
a1nxn
a2nxn
amnxn
2，
b2
bm
2，
m，
得到
xn1
b1
xn2
b2
xnm
bm
Cb
Xb
b
C1C2
Cn+m
Xn+m
el
Xi
X2
Cn+1
xn+1
b1
an
a12
a〔n+m
Cn+2.
xn+2.
b2.
a21
a22
a2n+m
.
.
Cn+m
.
.
xn+m
.
.
bn
am1
am2
amn+m
Z1
Z2
Zn+m
a1
(T2•
,(Xn+m
m
注①：Z=Cn+1aij+Cn+2a2j+•..+Cn+mamj=cniaij,(j=1,2,,…,n+m)
i1
(Tj=Cj-Zj，当(TjW0时，当前解最优。
注②：由max{bj}确定所对应的行的变量为“入基变量”；
由eL=min旦鼠0确定所对应的行的变量为“出基变量”，行、列交iaik
叉处为主元素，迭代时要求将主元素变为1,此列其余元素变为0。
例1：用单纯形法求解(本题即是本资料P2“图解法”例1的单纯形解法；也可化”对
偶问题”求解)
maxz=70x+30x2
3x19x2540
5x15x2450
9x13x2720
x1,x20
解：加入松弛变量x3,x4,x5,得到等效的标准模型:
maxz=70x+30x2+0x3+0%+0月
3xi9x2X3540
5x15x2x4450
9x13x2x5720
Xj0,j1,2,…,5
列表计算如下
*
*
70
30
0
0
0
Cb
Xb
b
x1
x2
x3
x4
x5
e
L
0
x3
540
3
9
1
0
0
540/3
=180
0
x4
450
5
5
0
1
0
450/5
=90
0
x5
720
(9)
3
0
0
1
720/9
=80
0
0
0
0
0
70T
30
0
0
0
0
x3
300
0
8
1
0
-1/3
300/8
=
0
x4
50
0
(10/3)
0
1
-39
50/10/3
=15
70
x1
80
1
1/3
0
0
1/9
80/1/3
=240
70
70/3
0
0
70/9
0
20/3T
0
0
—70/9
0
x3
180
0
0
1
-12/5
1
30
x2
15
0
1
0
3/10
-1/6
70
x1
75
1
0
0
-1/10
1/6
5700
700
300
0
0
2
-2
20/3
—20/3
X*=(75,15,180,0,0)T
・•.maxz=70X75+30X15=5700
例2：用单纯形法求解
maxz=7x1+12x2
9x14x2360
4x15x2200
3x110x2300
x1，x20
解：加入松弛变量x3，x4，x5，得到等效的标准模型：
maxz=7x1+12x2+0x3+0x4+0x5
9x14x2x3360
4x15x2x4200
3x110x2x5300
xj0,j1,2,...,5
列表计算如下：
7
12
0
0
0
X