单纯形法的matlab实现(极小化问题)

实 验 报 告 实验题目: 单纯形法的 matlab 实现 学生姓名: 学 号: 实验时间: 2013-4-15 一．实验名称: 单纯形法的MATLAB 实现 二．实验目的及要求: 1. 了解单纯形算法的原理及其matlab 实现. 2. 运用MATLAB 编辑单纯形法程序解决线性规划的极小化问题, 求出最优解及目标函数值. 三．实验内容: 1. 单纯形方法原理: 单纯形方法的基本思想, 是从一个基本可行解出发, 求一个使目标函数值有所改善的基本可行解; 通过不断改进基本可行解, 力图达到最优基本可行解. 对问题 .0 ,A s.t. def min xbxcxf 其中A 是一个m×n 矩阵, 且秩为 m, c 为 n 维行向量, x为 n 维列向量, b 为 m 维非负列向量. 符号“def ”表示右端的表达式是左端的定义式, 即目标函数f 的具体形式就是cx. 记 ),...,,(n21pppA  令 A =(B,N), B 为基矩阵, N 为非基矩阵, 设 0B 1-)0(bx 是基本可行解, 在)0(x处的目标函数值 bcbcccxf1-B1-NB)0(0B0B),(, 其中Bc 是c 中与基变量对应的分量组成的m 维行向量; Nc 是c 中与非基变量对应的分量组成的n-m 维行向量. 现由基本可行解)0(x出发求解一个改进的基本可行解. 设NBxxx是任一可行解, 则由bAx得到 N1-1-BNBBxbx, 在点 x处的目标函数值 Rjjjjfxxcccxfx)cz(),(0NBNB, 其中R 是非基变量下标集, jjpc1-BBz . 2. 单纯形方法计算步骤: 首先给定一个初始基本可行解, 设初始基为 B, 然后执行下列主要步骤: （1）解 bxB B, 求得_1bbBxB, 令0Nx, 计算目标函数值BBxcf . （2）求单纯形乘子 w , 解BcwB , 得到1BcwB. 对于所有非基变量, 计算判别数jjjjjcc-zpw. 令 }c-{zmaxc-zjjRjkk. 若0c-zkk, 则对于所有非基变量 0c-zjj, 对应基变量的判别数总是为零, 因此停止计算, 现行基本可行解是最优解. 否则, 进行下一步. （3）解kkpBy , 得到k1kpBy, 若0k y, 即ky 的每个分量均非正数, 则停止计算, 问题不存在有限最优解. 否则进行步骤（4）. （4）确定下标 r, 使 xk =0minikikikyybybrr, rBx为离基变量, kx 为进基变量. 用kp 替换rBp, 得到新的基矩阵B, 返回步骤（1）. 3. 单纯形方法表格形式: 表 3.1.1 f Bx Nx 右 端 Bx 0 mI NB...