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

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