4线性规划地基本理论.doc

word
word
1 / 29
word
线性规划
本章主要内容：线性规划的根本理论 线性规划的单纯形法 线性规划的对偶理
论 线性规划的对偶单纯形法
教学目的与要求：理解线性规划的根本理论；掌握线性规划的单纯形法；理，如此至少存在一个根本可行解为最优解．
证明 ．
定理7 设在〔LP〕的全部根本可行解中，使目标函数值最小者为；在的全部极方向中，满足者为．假如〔LP〕存在最优解，如此为〔LP〕的最优解的充要条件是存在
word
word
6 / 29
word
使 ． 〔*〕
证明 因为〔LP〕存在最优解，，根本可行解是〔LP〕的最优解．
设具有〔*〕式的形式，，为〔LP〕的可行解，从而由〔*〕式知，
因此，为〔LP〕的最优解．
反之，设为〔LP〕的任一最优解，如此为可行解，，存在 ，
使 ． 〔**〕
，有 ，
且由为最优解知．
从而由上述两式容易用反证法证明：假如〔**〕式中某个，如此必为〔LP〕的最优解；假如〔**〕式中某个，如此必有。由此知，最优解必具有〔*〕式的形式．
〔LP〕的解有四种可能：
〔1〕〔LP〕有唯一最优解〔此时，的最优值恰在的一个极点上达到〕；
〔2〕〔LP〕有无穷多个最优解〔此时，的最优值在的一段边界上达到〕；
word
word
8 / 29
word
〔3〕〔LP〕有可行解，但无最优解〔此时，无界且在上无下界〕；
〔4〕〔LP〕无可行解．
§ 单纯形法
需解决三个问题：
〔1〕求(LP)的初始根本可行解的方法；
〔2〕判别一个根本可行解是否为最优解的准如此；
〔3〕从一个根本可行解转换到使目标函数值下降到另一个根本可行解的方法．
最优性条件
设是〔LP〕的一个根本可行解，为了表示上的方便，先设对应的基为
，从而为基变量，为非基变量．记
，
于是 ，即知 等价于．由此解得
． 〔〕
在〔〕式中，令，即知，从而得根本解．将〔〕式代入目标函数，有
，
即．
以上推导明确，对于给定的一个基，(LP)可化为如下的等价形式：
〔〕
称〔〕式为(LP)关于基〔或根本可行解〕的典式．
如果对应的基为一般形式，即，如此通过类似的推导，可得关于一般基
word
word
8 / 29
word
的典式仍具有〔〕式的形式．只是此时，，为非基变量构成的维向量，是非基变量对应的列向量构成的矩阵；，为目标函数中非基变量的系数构成的维向量．
下面把关于一般基的典式〔〕用代数式来表示．
设，它表示非基变量的指标集，并令
，
，
如此〔〕式等价于
〔〕
记，如此基变量对应的局部；而非基变量对应的局部，它是由前面所定义的构成的向量．
定理1 设是〔LP〕的关于的根本可行解，假如，如此是〔LP〕的最优解；假如是〔LP〕的非退化的最优解，如此．
称为变量的检验数．
定理2 设是〔LP〕的一个基，假如关于的典式〔〕中存在，使，如此存在可行域的一个极方向，使．
定理3 设为〔LP〕的根本可行解，假如关于的典式〔〕中有某个检验数，且，如此〔LP〕无最优解．
根本可行解的改良
word
word
10 / 29
word
定理4 设是〔LP〕的一个基，且，
如此为〔LP〕的一个基的充要条件是关于的典式〔〕中．
定理5 设为〔LP〕的非退化的根本可行解，假如关于的典式〔〕中有，且至少有一个，如此必存在另一个根本可行解，使．
单纯形法的算法步骤
改良根本可行解的方法：把对应于正检验数的非基变量变成基变量，称它为进基变量，而从原基变量中按 确定变为非基变量，称它为离基变量．
现在来讨论如何从关于基的典式〔〕式导出关于新基的典式．为此将典式〔〕．
单纯形表