下载此文档

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


文档分类:高等教育 | 页数:约31页 举报非法文档有奖
1/31
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/31 下载此文档
文档列表 文档介绍
第一部分线性规划问题的求解
一、两个变量的线性规划问题的图解法:
㈠概念准备:定义:满足所有约束条件的解为可行解;可行解的全体称为可
行(解)域。
定义:达到目标的可行解为最优解。
㈡图解法:
图解法采用直角坐标求解: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

内容来自淘豆网www.taodocs.com转载请标明出处.