实验报告(单纯形法的matlab程序).doc
需积分: 5 37 浏览量
2022-10-19
23:18:47
上传
评论 1
收藏 126KB DOC 举报
实验报告(单纯形法的 matlab 程序)
第 0 页
实验一:线性规划单纯形算法
一、实验目的
通过实验熟悉单纯形法的原理,掌握 Matlab 循环语句的应用,提高编程的
能力和技巧。
二、算法
对于一般的标准形式线性规划问题（求极小问题）,首先给定一个初始基
本可行解.设初始基为 B，然后执行如下步骤：
(1)。解
B
Bx b=
，求得
1
B
x B b
-
=
,
0,
N B B
x f c x= =令 计算目标函数值
1
( 1, 2,..., )i m B b i
-
=
i
以b 记 的第 个分量
（2)。计算单纯形乘子
w
，
B
wB C=
，得到
1
B
w C B
-
=
,对于非基变量，计算判别数
1
i i i B i i
z c c B p c
s
-
= - = -
，令
max{ }
k i i
i R
z c
s
Î
= -
,R 为非基变量集合
若判别数
0
k
s
£
，则得到一个最优基本可行解，运算结束;否则，转到下一步
（3）.解
k k
By p=
，得到
1
k k
y B p
-
=
；若
0
k
y £
，即
k
y
的每个分量均非正数，则停止计
算，问题不存在有限最优解，否则，进行步骤（4).
（4).确定下标 r，使
{ }
: 0
min , 0
t
r
rk tk
tk
b
b
tk
y y
t y
y
>
= >且
r
B
x
为离基变量。
k
x
为进基变量,用
k
p
替
换
r
B
p
,得到新的基矩阵
B
，返回步骤（1）.
对于极大化问题，可以给出完全类似的步骤，只是确定进基变量的准则不同.对
于极大化问题，应令
min{ }
k k j j
z c z c- = -
四、计算框图
开始
评论0