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

资源描述

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

《4线性规划的基本理论.doc》由会员分享，可在线阅读，更多相关《4线性规划的基本理论.doc（27页珍藏版）》请在冰点文库上搜索。

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

第四章线性规划

本章主要内容：

线性规划的基本理论线性规划的单纯形法线性规划的对偶理

论线性规划的对偶单纯形法

教学目的及要求：

理解线性规划的基本理论；掌握线性规划的单纯形法；理解线

性规划的对偶理论；掌握线性规划的对偶单纯形法。

教学重点：

线性规划的单纯形法．

教学难点：

线性规划的对偶单纯形法．

教学方法：

启发式．

教学手段：

多媒体演示、演讲与板书相结合．

教学时间：

6学时．

教学内容：

§4.1线性规划的基本理论

考虑线性规划问题

（LP）

或

其中

称为约束矩阵，称为约束方程组，称为非负约束．假定：

．

定义在（LP）中，满足约束方程组及非负约束的向量称为可行解或可行点；所有可行解的全体称为可行解集或可行域，记作，即

．

使目标函数在上取到最小值的可行解称为最优解；最优解对应的目标函数值称为最优值．

定义在（LP）中，约束矩阵的任意一个阶满秩子方阵称为基，中个线性无关的列向量称为基向量，中与的列对应的分量称为关于的基变量，其余的变量称为关于的非基变量．

任取（LP）的一个基，记，若令关于的非基变量都取0，则约束方程变为．由于是满秩方阵，因此有唯一解．

记，则由

所构成的维向量是的一个解，称之为（LP）的关于的基本解．

基本解满足约束方程组，但不一定满足非负约束，所以不一定是可行解．若，即基本解也是可行解，则称为（LP）的关于基的基本可行解，相应的基称为（LP）的可行基；当时，称此基本可行解是非退化的，否则，称之为退化的．若一个（LP）的所有基本可行解都是非退化的，则称该（LP）是非退化的，否则，称它是退化的．

例1求下列线性规划问题的所有基本可行解．

解约束矩阵的4个列向量依次为

．

全部基为

对于，和为基变量，和为非基变量．令==0，有

得到关于的基本解，它不是可行解．

对于，和为基变量，和为非基变量．令==0，有

得到关于的基本解，它是一个非退化的基本可行解．

同理，可求得关于的基本解分别为

，

显然，和均是非退化的基本可行解，而不是可行解．因此，该问题的所有基本可行解为．此外，因为这些基本可行解都是非退化的，所以该问题是非退化的．

定理1设为（LP）的可行解，则为（LP）的基本可行解的充要条件是它的非零分量所对应的列向量线性无关．

证明不妨设的前个分量为正分量，即

若是基本可行解，则取正值的变量必定是基变量，而这些基变量对应的列向量是基向量．故必定线性相关．

反之，若线性无关，则必有．当时，就是一个基；当时，一定可以从约束矩阵的后个列向量中选出个，不妨设为，使成为一个基．由于是可行解，因此，从而必有．由此可知是关于的基本可行解．

定理2是（LP）的基本可行解的充要条件是为（LP）的可行域的极点．

证明由定理4.1.1和定理2.2.2知结论成立．

例2求下列线性规划问题的可行域的极点．

解因为约束矩阵的4个列向量依次为

．

全部基为

求得关于基的基本解分别为

显然，均为退化的基本可行解，是非退化的基本可行解．可行域有三个极点：

，，．

定理3若（LP）有可行解，则它必有基本可行解．

证明由定理2.2.1及定理4.1.2知结论成立．

定理4若（LP）的可行域非空有界，则（LP）必存在最优解，且其中至少有一个基本可行解为最优解．

证明根据推论2.2.6，（LP）的任一可行解都可表示为（LP）的全部基本可行解的凸组合，即，其中．

设是使（LP）中目标函数值达到最小的基本可行解，即，则

．

这表明，基本可行解为（LP）的最优解．

定理5设（LP）的可行域无界，则（LP）存在最优解的充要条件是对的任一极方向，均有．

证明根据定理2.2.10，（LP）的任一可行解都可写成，其中为（LP）的全部基本可行解，为的全部极方向，且

．

于是，（LP）等价于下面以为决策变量的线性规划问题

由于可以任意大，因此若存在某个，使，则上述问题的目标函数无下界，从而不存在最优解，从而（LP）不存在最优解．

若，均有，设，则

．

所以基本可行解是（LP）的最优解．

推论6若（LP）的可行域无界，且（LP）存在最优解，则至少存在一个基本可行解为最优解．

证明由定理4.1.5的证明过程可知结论成立．

定理7设在（LP）的全部基本可行解中，使目标函数值最小者为；在的全部极方向中，满足者为．若（LP）存在最优解，则为（LP）的最优解的充要条件是存在

使．（*）

证明因为（LP）存在最优解，所以由定理4.1.4和推论4.1.6及其证明知，基本可行解是（LP）的最优解．

设具有（*）式的形式，则由推论2.2.6和定理2.2.10知，为（LP）的可行解，从而由（*）式知，

因此，为（LP）的最优解．

反之，设为（LP）的任一最优解，则为可行解，于是由推论2.2.6和定理2.2.10知，存在，

使．（**）

根据定理1.1.5，有，

且由为最优解知．

从而由上述两式容易用反证法证明：

若（**）式中某个，则必为（LP）的最优解；若（**）式中某个，则必有。

由此知，最优解必具有（*）式的形式．

（LP）的解有四种可能：

（1）（LP）有唯一最优解（此时，的最优值恰在的一个极点上达到）；

（2）（LP）有无穷多个最优解（此时，的最优值在的一段边界上达到）；

（3）（LP）有可行解，但无最优解（此时，无界且在上无下界）；

（4）（LP）无可行解．

§4.2单纯形法

需解决三个问题：

（1）求（LP）的初始基本可行解的方法；

（2）判别一个基本可行解是否为最优解的准则；

（3）从一个基本可行解转换到使目标函数值下降到另一个基本可行解的方法．

1、最优性条件

设是（LP）的一个基本可行解，为了叙述上的方便，先设对应的基为

，从而为基变量，为非基变量．记

，

于是，即知等价于．由此解得

．（4.2.1）

在（4.2.1）式中，令，即知，从而得基本解．将（4.2.1）式代入目标函数，有

，

即．

以上推导表明，对于给定的一个基，（LP）可化为如下的等价形式：

（4.2.2）

称（4.2.2）式为（LP）关于基（或基本可行解）的典式．

如果对应的基为一般形式，即，则通过类似的推导，可得关于一般基的典式仍具有（4.2.2）式的形式．只是此时，，为非基变量构成的维向量，是非基变量对应的列向量构成的矩阵；，为目标函数中非基变量的系数构成的维向量．

下面把关于一般基的典式（4.2.2）用代数式来表示．

设，它表示非基变量的指标集，并令

，

则（4.2.2）式等价于

（4.2.3）

记，则基变量对应的部分；而非基变量对应的部分，它是由前面所定义的构成的向量．

定理1设是（LP）的关于的基本可行解，若，则是（LP）的最优解；若是（LP）的非退化的最优解，则．

称为变量的检验数．

定理2设是（LP）的一个基，若关于的典式（4.2.3）中存在，使，则存在可行域的一个极方向，使．

定理3设为（LP）的基本可行解，若关于的典式（4.2.3）中有某个检验数，且，则（LP）无最优解．

2、基本可行解的改进

定理4设是（LP）的一个基，且，

则为（LP）的一个基的充要条件是关于的典式（4.2.3）中．

定理5设为（LP）的非退化的基本可行解，若关于的典式（4.2.3）中有，且至少有一个，则必存在另一个基本可行解，使．

3、单纯形法的算法步骤

改进基本可行解的方法：

把对应于正检验数的非基变量变成基变量，称它为进基变量，而从原基变量中按确定变为非基变量，称它为离基变量．

现在来讨论如何从关于基的典式（4.2.3）式导出关于新基的典式．为此将典式（4.2.3）中的系数写成表4.2.1的表格形式．

表4.2.1单纯形表

这个表称为（LP）关于基的单纯形表，记为．于是只要说明怎样从原单纯形表导出新的单纯形表即可．按照解线性方程组的Gauss-Jordan消去法思想，要使变成基变量，必须把中所在的列变成单位向量．因此可得单纯形表的变换规则如下：

（1）把中第行同除以作为新的第行（这样把所在的列中第个元素变成1），即；

（2）把表中新的第行乘以加到第行，得到新的第行（把所在的列中第个元素变成0），即

；

（3）把表中新的第行乘以加到第行，得到新的第行（把的检验数变成0），即．

上述变换称为旋转变换，元素称为主元，主元所在的行和列分别称为主元行和主元列．

算法4-1（单纯形法）

Step1对于一个已知的可行基，求出关于的单纯形表．

Step2如果所有，则关于的基本可行解便是（LP）的最优解，是最优值，此时的称为最优单纯形表，算法结束；否则，转Step3．

Step3如果有，使中所在的列，则（LP）无最优解，算法终止；否则，转Step4．

Step4令为最大正检验数中指标最小者，即

，（4.2.12）

取为进基变量；令为比值最小的行中指标最小者，即

，（4.2.13）

取为离基变量．

Step5以为主元进行旋转变换，得到新的单纯形表．以取代，返回Step2．

从Step2到Step5的每一次循环称为一次单纯形迭代．

式（4.2.12）和（4.2.13）分别称为Dantzig进基规则和离基规则，统称为Dantzig规则．

例3求解线性规划问题

解

-1

2/3*

-1/6

3/2

4/3

1/6

7/2

1/3

1/6

7/2

1/3

-1/3

-7

3/2

-1/4

9/4

-2

1/2

-1/2

1/4

11/4

-1/2

-1/4

-31/4

最优解为，最优值为-31/4．

4、退化情形的处理

Bland规则：

（1）进基规则：

由确定为进基变量；

（2）离基规则：

由确定为离基变量．

5、初始基本可行解的求法

考虑线性规划问题（LP）

且不妨设，但并不要求为行满秩矩阵．

寻找初始基本可行解的方法主要有两阶段法和大法．我们只介绍两阶段法．

在第一阶段先求解如下的线性规划问题

（LP1）

其中称为人工变量．因，故（LP1）有一个现成的基本可行解：

，与之对应的基为单位矩阵，从而目标函数可改写为，于是得到（LP1）的一个单纯形表如表4.2.2．

表4.2.2两阶段法初始单纯形表

由于目标函数，即它在（LP1）的可行域上有下界，因此（LP1）必有最优解．于是从单纯形表4.2.2出发，通过单纯形迭代必可求得（LP1）的最优解．设最优解为，对应的基为，其中，分三种情况讨论．

（1）。

此时（LP）无可行解。

因为假若（LP）存在一个可行解，则为（LP1）的可行解，且对应的目标函数的值为0，这与相矛盾．

（2）且人工变量都是非基变量．这时是（LP）的可行解．又因基变量全在之中，故对应的基必为的子方阵，所以为（LP）的基本可行解．

（3）且基变量中含有人工变量，设为基变量，则（LP1）关于的单纯形表中所在的第行对应的方程为

，（4.2.14）

这里为中非基变量的指标集，为人工变量中非基变量的指标集．

如果（4.2.14）式中所有，则有。

这说明人工变量可由诸人工变量线性表出，从而可知原约束方程组中第个方程可由另外一些方程（即人工变量对应的那些约束方程）的适当线性组合来表示，因此，第个约束方程是多余的，应当删去，这相当于从中删去第行．

如果（4.2.14）中存在，使，则由定理4.2.4知，以为主元进行旋转变换，得到（LP1）的新的单纯形表，它对应的基本可行解仍为（LP1）的最优解，但新的基变量中减少了一个人工变量．若新的基变量中还有人工变量，再重复此法，经过有限次，必能化为

（2）的情形．

综上所述，对于不具有明显可行基的（LP），可先用单纯形法解（LP1），解的结果或者说明（LP）无可行解，或者找到（LP）的一个基本可行解．然后再从这个基本可行解开始应用单纯形法求解（LP），这是两阶段法的第二阶段．

注意，在第一阶段迭代过程中，人工变量一旦离开基，随之也就失去了作用，故可从单纯形表中删去人工变量所在的列．

例4求解线性规划问题

（4.2.15）

解只需引进两个人工变量和，相应的（LP1）如下：

-1

-2

1/3

4/3

-2

2/3

8/3

1/3

4/3

-2

1/3

4/3

1/3

4/3

-1*

-1/2

-1

1/3

1/2

4/3

1/3

4/3

-1

-1/2

-2/3

-3/2

-8/3

1/2

1/3

4/3

1/3

-1/2

4/3

-2/3

-4

－8/3

最优解和最优值分别为，=－8/3．

6、单纯形法的几何解释

定理6设是（LP）关于基的基本可行解，对进行一次单纯形迭代得到新的基本可行解，若是非退化的，则与是（LP）的可行域的相邻极点．

§4.3对偶理论

定义设有线性规划问题（4.3.1）

及（4.3.2）

称问题（4.3.2）为问题（4.3.1）的对偶问题，并称问题（4.3.1）为原问题．

定理1对偶问题的对偶是原问题．

下面给出其它形式的线性规划问题的对偶问题．

标准形式的线性规划问题

（LP）

的对偶问题如下：

（DP）

一般的线性规划问题

（P）

的对偶问题如下：

（D）

原问题与对偶问题的对应关系表

原问题

min

对偶问题

max

变

量

行

约

束

无限制

行

约

束

变

量

无限制

例5求如下线性规划问题的对偶问题．

解先把上述线性规划问题写成如下形式

它的对偶问题为

下面总假设在（P）中，是行满秩矩阵．

定理2设和分别为（P）和（D）的可行解，则．

定理3（P）和（D）都有最优解的充要条件是它们都有可行解．

定理4设和分别是（P）和（D）的可行解，则它们分别为（P）和（D）的最优解的充要条件是．

定理5在（P）和（D）中，若有一个有最优解，则另一个也有最优解，且（P）和（D）的最优值相等．若其中一个有可行解但无最优解，则另一个必无可行解．

定理6设和分别是（P）和（D）的可行解，则它们分别为（P）和（D）的最优解的充要条件是（互补松弛条件）

推论7设和分别为原问题（4.3.1）和对偶问题（4.3.2）的可行解，为行满秩的，则它们分别为问题（4.3.1）和（4.3.2）的最优解的充要条件是

推论8设和分别为（LP）和（DP）的可行解，为行满秩的，则它们分别为（LP）和（DP）的最优解的充要条件是．

定理4.3.6中的互补松弛条件表明：

对于（P）和（D）的最优解，若（P）的第个不等式约束为松约束，则（D）的第个非负约束为紧约束；若（D）的第个非负约束为松约束，则（P）的第个不等式约束为紧约束；若（P）的第个非负约束为松约束，则（D）的第个不等式约束为紧约束；若（D）的第个不等式约束为松约束，则（P）的第个非负约束为紧约束．

§4.4对偶单纯形法

1、对偶单纯形法的算法步骤

设为（LP）中关于基的基本解，令．若和分别是（LP）和（DP）的可行解，则，这等价于

，

即对应的检验数全部非正，故由定理4.2.1知，是（LP）的最优解．而

，

所以由定理4.3.4知，是（DP）的最优解．这不但说明可以由（LP）的最优解得出（DP）的最优解，而且表明：

（LP）中关于基的基本解对应的检验数全部非正当且仅当为（DP）的可行解．因此，我们引入如下的概念．

定义（LP）中检验数全部非正的基本解称为对偶可行解或正则解，相应的基称为对偶可行基或正则基．

算法4-2（对偶单纯形法）

Step1选取（LP）的一个关于正则基的正则解，列出单纯形表．

Step2若，则是最优解，算法结束；否则，按选取为离基变量．

Step3若，则（LP）无可行解，算法终止；否则，按选取为进基变量．

Step4以为主元进行旋转变换，得到新的单纯形表．以取代（亦为正则基），返回Step2．

例6用对偶单纯形法求解线性规划问题

解引进变量将给定的线性规划问题化为标准形式：

-2

-1

-3

-3*

-2

-4

-1

-2

-1

-3

-1

1/3

-1

-2/3*

-1/3

2/3

-1/3

4/3

-4/3

-1/3

1/3

-7/3

-1

-1/3

4/3

-1/2

3/2

-3/2

1/2

-1/2

3/2

-3/2

3/2

-1/2

1/2

-5/2

-1/2

3/2

最优解为最优值为．

2、退化情形的处理

Bland规则：

（1）离基规则：

由确定为离基变量；

（2）进基规则：

由确定为进基变量．

3、初始正则解的求法

设已知（LP）的关于基的基本解，它不是正则解（也不必是可行解），对应的典式为

（4.4.1）

引进一个人工约束，其中表示充分大的正数，为引进的变量．把这个约束添加到（4.4.1）式中得到一个新的线性规划问题

（4.4.2）

问题（4.4.2）称为（LP）关于基的扩充问题．

对于扩充问题（4.4.2），按下述方法处理，即可得出它的一个正则解．设

选取为进基变量，并指定为离基变量，以为主元作旋转变换，得到新的典式，易知新的典式中目标函数的表达式为：

，

其中检验数．所以，经上述迭代所得的新的基本解便是（4.4.2）式的正则解．

扩充问题（4.4.2）有了初始正则解后，便可开始对偶单纯形迭代．迭代结果有且仅有下列三种可能情形：

（1）扩充问题无可行解，则也无可行解；

（2）扩充问题有最优解，且扩充问题的最优值与无关，则是的最优解；

（3）扩充问题有最优解，但扩充问题的最优值与有关，则无最优解．

例7求解线性规划问题：

解显然为一个基，但既不是可行基也不是正则基，因为对应的基本解且检验数增加人工约束．

-1

-3

-1

-+5

-2

-1*

--1

-5

-2

-1

-1*

-1

-2

-1

-3

最优解为，最优值为3．

§4.5MATLAB中线性规划问题求解函数介绍

线性规划问题是最简单的有约束最优化问题，所有的线性规划问题都可由化为下列式子描述：

Matlab中定义的标准型是求最小值，如要求最大值，则将改为即可，如约束条件中某个式子是“”关系式，则在不等式两边同时乘以－1就可转换成“”关系式．

求线性规划，单纯形法是最有效的一种方法，matlab的最优化工具箱中实现了这种算法，提供了求解线性规划问题的linprog（）函数．该函数条用格式如下：

（1）X=LINPROG（f,A,b）用来求解如下线性规划问题:

s．t．

（2）X=LINPROG（f,A,b,Aeq,beq）用来求解如下线性规划问题:

s．t．

（3）X=LINPROG（f,A,b,Aeq,beq,LB,UB,X0）用来求解如下线性规划问题:

s．t．

其中：

X0．为初始搜索点，也可以不写，由计算机自己设定初始搜索点．

各

展开阅读全文