单纯形法

nullnull单纯形法(Simplex Method)一、单纯形法的基本思想将顶点逐点转移。 根据LP的形，从可行域中一个基本可行解（一个顶点）开始，转移到另一个基本可行解，同时使目标函数值逐步优化（减小）；当目标函数值达到最优值时，问题就得到了最优解。null 最简单方法：基本解即解中取零的变量个数不少于n-m个，令非基变量取值为零相应得到的解 。 r(A)=m，解出m个基本变量，剩下的n-m个变量为自由取值的变量，故也可称为自由变量。问题：如何找到第一个基本可行解？如何判断是否为最优解？如何从一个基本可行解→另一个尚未检查到的基本可行解？null二、单纯形法nullnull利用施行运算null转化为对于等价的LP：null写成表格形式：底线null欲求解LP，采用如下运算：⒈ 底线以上部分进行行交换；⒉ 底线以上某一行乘一非零常数；⒊ 底线以上的行进行倍加运算；⒋ 把底线以上行乘常数后加至底行（包括右下端）上。当表格具有如下特点：⒈ 中心部位具有单位子块；⒉ 右列元素非负；⒊ 底行相应于单位子块位置的元素为0；⒋ 底行其它元素非负。null最优解的读法： 单位子块中1所对应的变量取相应右列的值，不在单位子块位置中的变量取值为0。而右下端元素变号即为LP的最优值。单纯形法的步骤：⒊ 旋转运算；⒋ 若底行元素均非负，算法终止，否则回⒈null定理2.2 在已知一个基本可行解（初始基本可行解）的前提下，使用单纯形法求解线性时，若每次迭代得出的基本可行解的基变量均大于零（称为非退化），则算法必有限步终止。P22null例2.2：用单纯形法求解（P26)nullnullnull 从表中知（4，3，3，0，0）T为最优解，略去松弛变量，得：null§2.5 大M法 引入：问题提出，当初始基本可行解不知道时，如何求解？ 先利用容许的运算使右列为非负，然后在中心部位人工地添加一个单位子块。nullnull列成表格：nullnullnull△最优解是否存在：