伊永强.doc

单纯性方法 一 线性规划的模型 线性规划是数学规划中基本的、发展较线早的分支之一。线性规划一般有三种模型。 1 线性规划的一般形式  其中A矩阵称为约束矩阵。为目标函数。向量称为价值向量。称为价值系数。向量称右端向量。称为非负约束，称为自由变量。 2 线性规划的规范形式 3 线性规划的标准形式 二 基本可行解 标准形式的线性规划问题，假设秩（A）=m,故A中有m个线性无关的列向量。它们构成满秩方阵B，把A中其余各列组成的子阵记为N，即A=（B，N）。再把的分量也相应地分为两部分，记为和，则AX=b可记作 由于B是满秩方阵，存在，上式两边同左乘，移项后得 。 设B是秩为m的约束矩阵中的一个m阶满秩子方阵，则称B为一个基（或基阵）。B中m个线性无关的列向量称为基向量。变量x中与之对应的m个分量称为基变量，其余的分量称为非基变量。令所有的非基变量取值为零。得到的解称为相对应于B的基本解。当时称基本解X为基本可行解。这是对应的基B称为可行基。一个基本可行解X，如果它的所有的基变量都取正值。称它是非退化的；如果有的基变量也取零值，称她为退化的。 三 单纯形表的形成 当线性规划问题的变量和约束条件比较少时，可以通过解线性方程组来解。当变量和约束条件很多时。它的可行基就有个。要通过解线性方程组来解会相当复杂。用单纯性方法解就会简单很多。 对于标准形式的线性规划问题。 （1） 设B是约束矩阵A的一个基阵，与之相对应的基向量为，由上面已得 （2） 对目标函数也作相应的变换，有 (3) 式中是由f(x)中全部基变量的系数组成的列向量，而是由f(x)中全部非基变量的系数组成的列向量。 将（2）（3）代入线性规划问题（1），并移项，目标函数f=f(x)可以写成 (4) 其中就是与此基本解相对应的目标函数值。 线性规划问题的等式约束可以写成 （5） 右端的各分量就是由基阵B所确定的基本解中各基变量之值。 由式（4）和（5）所表示的m+1个方程称为对应于基阵B的典则方程组，简称典式。 对式（4）和（5）组成的方程进行改写。容易推出 (6) 则（4）可写成 （7） 而式（5）实际为 （8） 式（5）式（6）是关于f, 的线性方程组。 可得矩阵形式的单纯形表 X 右端 把（5）式和（6）式各项详细展开可得 (9) (10) (7)式中。其中称为检验数。 （11） （12） 矩阵形式的单纯形表也可详细的表（13）。表（13）为基阵B所对应的单纯形表。 右端 f 四 单纯形方法的计算 在求出于基阵B的单纯形表对应的基本可行解x之后，还必须判断x是否为最优解。通过检验数来进行最优解判断与换基迭代。 1．若单纯形表中所有检验数，则对应的基本可解x为最优解。 2．若某个检验数，并且它所对应的列向量，则所给的线性规划问题无下界，因此无最优解。 3．若基本可行解x对应的检验数中有正数，且这些检验数所对应的列向量都至少有一个正分量，则通过换基后可得另一个基本可行解。使得。 所以可得单纯形方法的基本算法。 （1） 将所给的线性规划问题化为标志形式 （2） 找出一个初始可行基B并作出其单纯形表。 （3） 若所有的检验数，则对应的基本可行解x为最优解，计算终止，否则转至（4）。 （4） 观察那些正检验数，若有某个检验数，而其所对应的列向量的全部元素，则该线性规划问题无最优解，计算终止，否则转至（5）。 （5） 求出若 则取为转轴元，为进基变量，为离基变量，进行换基。 （6） 对B的单纯形表进行单纯形变换，获得的单纯形表，转至（3）。 五 用单纯形法解决问题 线性规划问题 解 这里是一个单位矩阵，且，故基B是可行基，为基变量，为非基变量，故B对应的基本可行解为，其目标函数值。方程组已是典式，得到第一张单纯形表如下表。 第零行的元素应是将目标函数化成等价的方程后的相应元素。 检验数，故当前解不是最优解，列中有两个元素均为正数，取 故转轴元为，为进基变量，为出基变量。进行旋转变换后的下表。 它应得基本可行解为,其目标函数值为。但，仍不是最优解，此时为转轴元，进行旋转变换得下表。 它对应的基本可行解为，其目标函数值为，此时检验数向量，故为最优解。 六 初始解 如果一个LP问题 （14） 在