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

实实 验验 报报 告告 实验题目 单纯形法的 matlab 实现 学生姓名 学 号 实验时间 2013 4 15 一 实验名称一 实验名称 单纯形法的 MATLAB 实现 二 实验目的及要求二 实验目的及要求 1 了解单纯形算法的原理及其 matlab 实现 2 运用 MATLAB 编辑单纯形法程序解决线性规划的极小化问题 求出最优解及目标 函数值 三 实验内容三 实验内容 1 单纯形方法原理 单纯形方法的基本思想 是从一个基本可行解出发 求一个使目标函数值有所改善的基 本可行解 通过不断改进基本可行解 力图达到最优基本可行解 对问题 0 A s t def min x bx cxf 其中 A 是一个 m n 矩阵 且秩为 m 为 n 维行向量 为 n 维列向量 为 m 维非负cxb 列向量 符号 def 表示右端的表达式是左端的定义式 即目标函数的具体形式就是f cx 记 n21 pppA 令 B N B 为基矩阵 N 为非基矩阵 设A 0 B 1 0 b x 是基本可行解 在处的目标函数值 0 x bc b cccxf 1 B 1 NB 0 0 B 0 B 其中是中与基变量对应的分量组成的 m 维行向量 是中与非基变量对应的分量组 B cc N cc 成的 n m 维行向量 现由基本可行解出发求解一个改进的基本可行解 0 x 设是任一可行解 则由得到 N B x x xbAx N 1 1 B NBBxbx 在点处的目标函数值x Rj jjj f x x cccxfx cz 0 N B NB 其中 R 是非基变量下标集 jj pc 1 BB z 2 单纯形方法计算步骤 首先给定一个初始基本可行解 设初始基为 B 然后执行下列主要步骤 1 解 求得 令 计算目标函数值 bxB B 1 bbBxB 0 N x BBx cf 2 求单纯形乘子 解 得到 对于所有非基变量 计算判别数w B cwB 1 Bcw B 令 jjjjj cc z pw c zmaxc z jj Rj kk 若 则对于所有非基变量 对应基变量的判别数总是为零 因此0c z kk 0c z jj 停止计算 现行基本可行解是最优解 否则 进行下一步 3 解 得到 若 即的每个分量均非正数 则停止计算 kk pBy k 1 k pBy 0 k y k y 问题不存在有限最优解 否则进行步骤 4 4 确定下标 r 使 x k 0min ik ik i k y y b y b r r 为离基变量 为进基变量 用替换 得到新的基矩阵 B 返回步骤 1 r B x k x k p r B p 3 单纯形方法表格形式 表 3 1 1 f B x N x 右 端 B x 0 m I NB 1b 1 B f 10 N 1 B c NBcb 1 BB c 表 3 1 2 3 1 1 略去左端列后的详表 BmBrB1 xxx kj xx m r 1 B B B x x x 100 010 001 mkmj rkrj kj yy yy yy 11 1 m r b b b f000 kkjj c zc z bcB 假设 由上表得 0B 1 bb0 NB xbx 若 则现行基本可行解是最优解 0c NBc N 1 B 若 则用主元消去法求改进的基本可行解 先根据0c NBc N 1 B 选择主列 再根据找主行 主元为 然后 c zmaxc z jj Rj kk 0min ik ik i k y y b y b r r rk y 进行主元消去 得到新单纯形表 表的最后一行是判别数和函数目标值 四 实验流程图及其四 实验流程图及其 MATLAB 实现实现 1 流程图 开始 初始基本可行解 B 解 求得 令 计算目标函数值bxB B 1 bbBxB 0 N x BBx cf 0c z kk 解 得到kk pBy k 1 k pBy 0 k y 赋以正的大值 N ik i y b 求单纯形乘子 解 得到 对于所有非基w B cwB 1 Bcw B 变量 计算判别数 令 jjjjj cc z pw c zmaxc z jj Rj kk 现行基本可行解是最优解 确定下标 r 使 x k 0min ik ik i k y y b y b r r 为离基变量 为进基变量 用替换 得到新的基矩阵 B r B x k x k p r B p YN NY min N N 问题不存在有限最优解 Y 2 代码及数值算例 1 程序源代码 function x f DCmin c A b AR y0 d x 最优解 f 目标函数最优值 c 目标函数系数向量 A 系数矩阵 b m维列向量 AR 松弛变量系数矩阵 y0 基矩阵初始向量 d 补充向量 非目标系数向量 为一零向量 N 10000 B A AR b m n size B C c d y y0 x zeros 1 length c for k 1 N k z B end 右端 for j 1 n 1 t j y B j C j 检验数 end t f y z 选取主元 选取主列 alpha q max t q W k q x下标矩阵 选取主元 for p 1 m if B p q 0 r p N else r p z p B p q end end beta p min r p y p C q B p B p B p q for i 1 m if i p B i B i B p B i q end end if max t c 1 2 1 A 1 1 2 1 2 1 4 0 1 2 4 0 b 10 8 4 AR 0 0 1 0 0 1 y0 0 0 0 d 0 0 0 x f DCmin c A b AR y0 d ii 运行结果 B 1 1 2 1 0 0 10 2 1 4 0 1 0 8 1 2 4 0 0 1 4 k 1 t 1 2 1 0 0 0 f 0 B 1 5000 0 0 1 0000 0 0 5000 8 0000 1 5000 0 2 0000 0 1 0000 0 5000 10 0000 0 5000 1 0000 2 0000 0 0 0 5000 2 0000 k 2 t 0 0 3 0 0 1 f 4 B 1 5000 0 0 1 0000 0 0 5000 8 0000 0 7500 0 1 0000 0 0 5000 0 2500 5 0000 1 0000 1 0000 0 0 1 0000 1 0000 12 0000 k 3 t 2 2500 0 0 0 1 5000 1 7500 f 19 x 0 12 5 f 19 五 总结五 总结 在单纯形法求解过程中 每一个基本可行