文档介绍：§·19世纪末,,但其工作长期未被人们所知。由于战争的需要,。·1947年,,应用于与国防有关的问题。该法实用而有效。单纯形法被认为是20世纪10大算法之一(其中还有快速Fourier变换算法等)。·但1972年,,用单纯形法求解可能要检查遍所有的顶点才能得到最优解,。·1979年,前苏联数学家提出了一种求解LP的椭球算法,计算复杂性为(为输入长度)。该算法在理论上很重要,但计算效率远不如单纯形法有效。·能否找到有效的多项式时间算法?在此背景下,1984年,在美国贝尔实验室工作的印度数学家Karmarkar给出了一个求解线性规划的新的多项式时间算法,计算复杂性为。通过例题试算,收敛到较好效果,人们希望借助这种算法解决一些领域中的大规模问题的计算。·对于现实生活中的大多数实际问题,,而基于对偶理论可以设计求解LP的对偶单纯形法和原始-对偶算法及其它算法,因此单纯形法是目前应用最广泛的算法之一。·LP之所以重要有以下方面的原因:■理论算法发展较完善■现实生活中许多问题可用LP近似建模■在非线性规划的求解中,:::为决策变量,为费用(价格)系数,为目标函数,为技术系数,:(i)®(ii)®(引入松弛变量)(iii)®(引入剩余变量)(iv)无非负限制,令(v),令(平移变换):.,。。,,从而无最优解。由以上几个例子可以看出以下几个结论:(i)可行域为空集,原问题无可行解;(不可行,无最优解)(ii)目标函数可行域上无界;(可行,无有限最优解)(iii)有唯一最优解;(有最优解,可在顶点达到)(iv)有无穷多最优解;(有最优解,可在顶点达到)猜想:求解一个LP问题可能有三种情况:不可行、无界和有最优解;线性规划若有最优解,则一定可以在可行域的某个“顶点”达到。线性规划的基本定理设可行域的极点为,,任何可行点可表示为:将x代入LP标准型,得到以为变量的等价LP:.(i)可任意大,因此若对某个j有,则随的增大无限减小,,称该问题是无界的,或不存在有限最优解.(ii)如果对于所有的j有,这时为极小化目标函数,令,.,令,显然当及时,(基于标准型的线性规划基本定理):.,的可行域非空,则有下列结论:,,,,则,,得称其为(LP)的基本解,对应的矩阵称为基矩阵,简称基。的各分量称为基变量,的各分量称为非基变量。注:基本解的个数最多为:,得则(最多有个基,而线性相关,故共有5个基)(i)令,则得(ii)令,则;(iii)令,则;(iv)令,则;(v)令,则;若,称其为(LP)的基本可行解,对应的矩阵称为可行基矩阵,简称可行基。5个基本解,除外,都是基本可行解。称为与基本可行解(与基)对应的单纯形乘子。对于LP,可行域的基本可行解与极点是等价的。引理:设为的极点的充要条件是中与的所有正分量对应的列线性无关。定理:在(LP)的标准形中,若,则的极点集与(LP)的基本可行解集相同。可行域的极点与基本可行解是一一对应的:(LP)的最优解可在某极点达到Û(LP)的最优解可在某基本可行解处达到若,则有极点Û若,则有基本可行解.§:若(LP)的可行域非空,即,且,则(i)(LP)有基本可行解;(ii)(LP)存在有限最优解的充分必要条件是(LP)的价格系数与可行集的所有极方向的夹角小于90度,即对的所有极方向成立;(iii)若(LP)有有限最优解,则其最优值可在某个基本可行解上达到。线性规划解的代数特征的一个重要应用就是单纯形算法的提出。单纯形法的基本思路:用迭代法从一个基本可行解(极点)转换到另一个基本可行解(另一极点),每一步转换只将一个非基变量(指一个分量)变为基变量,称为进基,同时将一个基变量变为非基变量,称为