.
实 验 报 告
实验题目: 单纯形法的matlab实现 学生: 学 号: 实验时间: 2013-4-15
.
.
一．实验名称: 单纯形法的MATLAB实现
二．实验目的及要求:
1. 了解单纯形算法的原理及其matlab实现.
2. 运用MATLAB编辑单纯形法程序解决线性规划的极小化问题, 求出最优解及目标函数值.
三．实验容:
1. 单纯形方法原理:
单纯形方法的基本思想, 是从一个基本可行解出发, 求一个使目标函数值有所改善的基本可行解; 通过不断改进基本可行解, 力图达到最优基本可行解. 对问题
min f def cxs.t. Ax?b, x?0. 其中A是一个m×n矩阵, 且秩为m, c为n维行向量, x为n维列向量, b为m维非负列向量. 符号“记
def”表示右端的表达式是左端的定义式, 即目标函数f的具体形式就是cx.
A?(p1,p2,...,pn)
令A=(B,N), B为基矩阵, N为非基矩阵, 设
x是基本可行解, 在x(0)(0)?B-1b????
0??处的目标函数值
f0?cx(0)?B-1b?-1?(cB,cN)???cBBb,
?0? .
.
其中cB是c中与基变量对应的分量组成的m维行向量; cN是c中与非基变量对应的分量组成的n-m维行向量. 现由基本可行解x(0)出发求解一个改进的基本可行解.
?xB?设x???是任一可行解, 则由Ax?b得到
?xN?xB?B-1b?B-1NxN,
在点x处的目标函数值
?xB?f?cx?(cB,cN)???f0??(zj?cj)xj,
j?R?xN?其中R是非基变量下标集,
zj?cBB-1pj.
2. 单纯形方法计算步骤:
首先给定一个初始基本可行解, 设初始基为B, 然后执行下列主要步骤: （1）解BxB?b, 求得xB?Bb?b, 令xN?0, 计算目标函数值f?cBxB. （2）求单纯形乘子w, 解wB?cB, 得到w?cBB?1?1_. 对于所有非基变量, 计算判别数
zj-cj?wjpj?cj. 令
zk-ck?max{zj-cj}.
j?R 若zk-ck?0, 则对于所有非基变量zj-cj?0, 对应基变量的判别数总是为零, 因此停止计算, 现行基本可行解是最优解. 否则, 进行下一步.
?1（3）解Byk?pk, 得到yk?Bpk, 若yk?0, 即yk的每个分量均非正数, 则停止计算,
问题不存在有限最优解. 否则进行步骤（4）. （4）确定下标r, 使
??br?bi??min?yik?0?, xk=yrk???yik? .
.
xBr为离基变量, xk为进基变量. 用pk替换pB, 得到新的基矩阵B, 返回步骤（1）.
r
3. 单纯形方法表格形式:
表 3.1.1
f 0 1 xB Im 0 xN 右 端 xB B-1N B-1b f cBB-1N-cN cBB-1b 表 3.1.2（3.1.1略去左端列后的详表） xB1?xBr?xBm ?xj?xk _xB1?xBr?xBm f 1?0?0???0?1?0 ???0?0?10?0?0 ??y1j?yrj???y1k?yrk??? b1?br ?bm__?ymj?ymk??zj-cj?zk-ck? cBb -1 假设b?Bb?0, 由上表得xB?b,xN?0. -1 若cBBN-cN?0, 则现行基本可行解是最优解.
-1若cBBN-cN?0, 则用主元消去法求改进的基本可行解. 先根据
??bi?zk-ck?max{zj-cj}选择主列, 再根据br?min?y?0??找主行, 主元为yrk, 然后j?Rikyrk???yik?进行主元消去, 得到新单纯形表. 表的最后一行是判别数和函数目标值.
四．实验流程图及其MATLAB实现:
.
.
1. 流程图:
开始 ?1_初始基本可行解B 解BxB?b, 求得xB?Bb?b, 令xN?0, 计算目标函数值f?cBxB N Y ?1解Byk?pk, 得到yk?Bpk 求单纯形乘子w, 解wB?cB, 得到w?cBB. 对于所有非基变量, 计算判别数zj-cj?wjpj?cj. 令?1zk-ck?max{zj-cj} j?RN zk-ck?0 Y 现行基本可行解是最优解 yk?0 ??br?bi??min?yik?0? 确定下标r, 使xk=yrk???yik? . 赋bi以正的大值N yik
单纯形法的matlab实现（极小化问题）
