文档介绍：1-3 单纯形法
方便、有效、通用
图解法的局限性
(1)图解法的优点:简单、直观;
(2)局限性: 对仅含有两个至多不超过三个决策变量的线性规划才适于使用图解法,大多数情况下仅对含有两个决策变量的线性规划才使用图解法求解;
(3)对含有三个以及三个以上决策变量的线性规划则应考虑使用更加有效的通用算法——单纯形法来进行求解。
一、单纯形法的基本思想1、顶点的逐步转移
即从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)的迭代过程,转移的条件是使目标函数值得到改善(逐步变优),当目标函数达到最优值时,问题也就得到了最优解。
单纯形算法的基本思路
根据线性规划问题的可行域是凸多边形或凸多面体(),一个线性规划问题有最优解,就一定可以在可行域的顶点上找到()。
于是,若某线性规划只有唯一的一个最优解,这个最优解所对应的点一定是可行域的一个顶点;若该线性规划有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解。
顶点转移的依据?
转移条件? 转移结果?
使目标函数值得到改善
得到LP最优解,目标函数达到最优值
:
(1)如何寻找初始顶点(基本可行解)?
(2)为了使目标函数逐步变优,怎么转移?
即如何找到下一顶点(基本可行解)?
(3)目标函数达到最优的判断标准是什么?
二、单纯形法原理(用代数方法求解LP)
例1-7
第一步:引入非负的松弛变量x4,x5, 将该LP化为标准型
第二步:寻求初始可行基,确定基变量
对应的基变量是 x4,x5;
第三步:写出初始基本可行解和相应的目标函数值
两个关键的基本表达式:
①用非基变量表示基变量的表达式