文档介绍：单纯形法 迭代原理
三. 单纯形法的基本思想 1、顶点的逐步转移
即从可行域的一个顶点(基本可行解)开始,转移到另一个顶点(另一个基本可行解)的迭代过程,转移的条件是使目标函数值得到改善(逐步变优),当目标函数达到最优值时,问题也就得到了最优解。
根据线性规划问题的可行域是凸多边形或凸多面体,一个线性规划问题有最优解,就一定可以在可行域的顶点上找到。
于是,若某线性规划只有唯一的一个最优解,这个最优解所对应的点一定是可行域的一个顶点;若该线性规划有多个最优解,那么肯定在可行域的顶点中可以找到至少一个最优解。
顶点转移的依据?
转移条件? 转移结果?
使目标函数值得到改善
得到LP最优解,目标函数达到最优值
:
(1)为了使目标函数逐步变优,怎么转移?
(2)目标函数何时达到最优——
判断标准是什么?
解LP问题单纯形法的基本思路:
初始可行基:设法在约束矩阵中构造出一个m阶单位阵
初始基本可行解
检验数
进基变量:检验数
离基变量:最小比值准则
LP:
?
希望在化LP的标准形式时,A中都含有一个m阶单位阵。
观察法
——观察系数矩阵中是否含有现成的单位阵?
LP限制条件中全部是“≤”类型的约束
——将新增的松弛变量(+)作为初始基变量,对应的系数列向量构成单位阵;
LP限制条件有“≥”类型的约束
——左端新增剩余变量(-)后,再加上一个非负的新变量—人工变量。
LP限制条件有“=”类型的约束
——直接在左端加上人工变量。
在引入人工变量后,与原先的约束方程不完全等价,为此,需要在目标函数上做些“修正”——大M法或两阶段法
非基变量取0,算出基变量,搭配在一起构成
初始基本可行解:
判断:初始基本可行解或经过若干次迭代后得到的新基本可行解—当前解—是否为最优解?
一般(经过若干次迭代),对于基B,用非基变量表出基变量的表达式为:
典式
若
用非基变量表示目标函数的表达式:
典式
检验数