4线性规划的基本理论

1、第四章 线性规划本章主要内容：线性规划的基本理论 线性规划的单纯形法 线性规划的对偶理论 线性规划的对偶单纯形法教学目的及要求：理解线性规划的基本理论；掌握线性规划的单纯形法；理解线性规划的对偶理论；掌握线性规划的对偶单纯形法。教学重点：线性规划的单纯形法教学难点：线性规划的对偶单纯形法教学方法：启发式教学手段：多媒体演示、演讲与板书相结合教学时间：6学时教学内容：4.1 线性规划的基本理论考虑线性规划问题 (LP)或其中 称为约束矩阵，称为约束方程组，称为非负约束假定： 定义 在（LP）中，满足约束方程组及非负约束的向量称为可行解或可行点；所有可行解的全体称为可行解集或可行域，记作，即使目标

2、函数在上取到最小值的可行解称为最优解；最优解对应的目标函数值称为最优值定义 在（LP）中，约束矩阵的任意一个阶满秩子方阵称为基，中个线性无关的列向量称为基向量，中与的列对应的分量称为关于的基变量，其余的变量称为关于的非基变量任取（LP）的一个基，记，若令关于的非基变量都取0，则约束方程变为由于是满秩方阵，因此有唯一解记，则由所构成的维向量是的一个解，称之为（LP）的关于的基本解基本解满足约束方程组，但不一定满足非负约束，所以不一定是可行解若，即基本解也是可行解，则称为（LP）的关于基的基本可行解，相应的基称为（LP）的可行基；当时，称此基本可行解是非退化的，否则，称之为退化的若一个（LP）的所

3、有基本可行解都是非退化的，则称该（LP）是非退化的，否则，称它是退化的例1 求下列线性规划问题的所有基本可行解解 约束矩阵的4个列向量依次为全部基为对于，和为基变量，和为非基变量令=0，有得到关于的基本解，它不是可行解对于，和为基变量，和为非基变量令=0，有得到关于的基本解，它是一个非退化的基本可行解同理，可求得关于的基本解分别为，显然，和均是非退化的基本可行解，而不是可行解因此，该问题的所有基本可行解为此外，因为这些基本可行解都是非退化的，所以该问题是非退化的定理1 设为（LP）的可行解，则为（LP）的基本可行解的充要条件是它的非零分量所对应的列向量线性无关证明 不妨设的前个分量为正分量，即

4、若是基本可行解，则取正值的变量必定是基变量，而这些基变量对应的列向量是基向量故必定线性相关 反之，若线性无关，则必有当时，就是一个基；当时，一定可以从约束矩阵的后个列向量中选出个，不妨设为，使成为一个基由于是可行解，因此，从而必有由此可知是关于的基本可行解定理2 是（LP）的基本可行解的充要条件是为（LP）的可行域的极点证明 由定理4.1.1和定理2.2.2知结论成立例2 求下列线性规划问题的可行域的极点解 因为约束矩阵的4个列向量依次为全部基为求得关于基的基本解分别为显然，均为退化的基本可行解，是非退化的基本可行解可行域有三个极点：，定理3 若（LP）有可行解，则它必有基本可行解证明 由定理

5、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）等价于下面以为决策变量的线性规划问题由于可以任意大，因此若存在某个，使，

6、则上述问题的目标函数无下界，从而不存在最优解，从而（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）的可行解，从而由

7、（*）式知，因此，为（LP）的最优解反之，设为（LP）的任一最优解，则为可行解，于是由推论2.2.6和定理2.2.10知，存在 ，使 （*）根据定理1.1.5，有 ，且由为最优解知从而由上述两式容易用反证法证明：若（*）式中某个，则必为（LP）的最优解；若（*）式中某个，则必有。由此知，最优解必具有（*）式的形式（LP）的解有四种可能：（1）（LP）有唯一最优解（此时，的最优值恰在的一个极点上达到）；（2）（LP）有无穷多个最优解（此时，的最优值在的一段边界上达到）；（3）（LP）有可行解，但无最优解（此时，无界且在上无下界）；（4）（LP）无可行解4.2 单纯形法需解决三个问题：（1）求(L

8、P)的初始基本可行解的方法；（2）判别一个基本可行解是否为最优解的准则；（3）从一个基本可行解转换到使目标函数值下降到另一个基本可行解的方法1、 最优性条件设是（LP）的一个基本可行解，为了叙述上的方便，先设对应的基为，从而为基变量，为非基变量记，于是 ，即知 等价于由此解得 （4.2.1）在（4.2.1）式中，令，即知，从而得基本解将（4.2.1）式代入目标函数，有，即以上推导表明，对于给定的一个基，(LP)可化为如下的等价形式： （4.2.2）称（4.2.2）式为(LP)关于基（或基本可行解）的典式如果对应的基为一般形式，即，则通过类似的推导，可得关于一般基的典式仍具有（4.2.2）式的形

9、式只是此时，为非基变量构成的维向量，是非基变量对应的列向量构成的矩阵；，为目标函数中非基变量的系数构成的维向量下面把关于一般基的典式（4.2.2）用代数式来表示设，它表示非基变量的指标集，并令，则（4.2.2）式等价于 （4.2.3）记，则基变量对应的部分；而非基变量对应的部分，它是由前面所定义的构成的向量定理1 设是（LP）的关于的基本可行解，若，则是（LP）的最优解；若是（LP）的非退化的最优解，则称为变量的检验数定理2 设是（LP）的一个基，若关于的典式（4.2.3）中存在，使，则存在可行域的一个极方向，使定理3 设为（LP）的基本可行解，若关于的典式（4.2.3）中有某个检验数，且，则

10、（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）关于基的单纯形表，记为于是只要说明怎样从原单

11、纯形表导出新的单纯形表即可按照解线性方程组的Gauss-Jordan消去法思想，要使变成基变量，必须把中所在的列变成单位向量因此可得单纯形表的变换规则如下：（1）把中第行同除以作为新的第行（这样把所在的列中第个元素变成1），即 ；（2）把表中新的第行乘以加到第行，得到新的第行（把所在的列中第个元素变成0），即 ；（3）把表中新的第行乘以加到第行，得到新的第行（把的检验数变成0），即 上述变换称为旋转变换，元素称为主元，主元所在的行和列分别称为主元行和主元列算法4-1（单纯形法）Step1 对于一个已知的可行基，求出关于的单纯形表Step2 如果所有，则关于的基本可行解便是（LP）的最优解，是最

12、优值，此时的称为最优单纯形表，算法结束；否则，转Step3Step3 如果有，使中所在的列，则（LP）无最优解，算法终止；否则，转Step4Step4 令为最大正检验数中指标最小者，即， （4.2.12）取为进基变量；令为比值最小的行中指标最小者，即， （4.2.13）取为离基变量Step5 以为主元进行旋转变换，得到新的单纯形表以取代，返回Step2从Step2到Step5的每一次循环称为一次单纯形迭代式（4.2.12）和（4.2.13）分别称为Dantzig进基规则和离基规则，统称为Dantzig规则例3 求解线性规划问题解111005-1101006*20012121000002/3*1

13、0-1/63/204/3011/67/211/3001/67/201/300-1/3-7013/20-1/49/400-211/21/210-1/201/411/400-1/20-1/4-31/4最优解为，最优值为-31/44、退化情形的处理Bland规则：（1）进基规则：由确定为进基变量；（2）离基规则：由确定为离基变量5、初始基本可行解的求法考虑线性规划问题(LP)且不妨设，但并不要求为行满秩矩阵寻找初始基本可行解的方法主要有两阶段法和大法我们只介绍两阶段法在第一阶段先求解如下的线性规划问题 (LP1)其中称为人工变量因，故(LP1)有一个现成的基本可行解：，与之对应的基为单位矩阵，从而目

14、标函数可改写为 ，于是得到(LP1)的一个单纯形表如表4.2.2表4.2.2 两阶段法初始单纯形表100100由于目标函数，即它在(LP1)的可行域上有下界，因此(LP1)必有最优解于是从单纯形表4.2.2出发，通过单纯形迭代必可求得(LP1)的最优解设最优解为，对应的基为，其中，分三种情况讨论（1）。此时(LP)无可行解。因为假若(LP)存在一个可行解，则为(LP1)的可行解，且对应的目标函数的值为0，这与相矛盾（2）且人工变量都是非基变量这时是(LP)的可行解又因基变量全在之中，故对应的基必为的子方阵，所以为(LP)的基本可行解（3）且基变量中含有人工变量，设为基变量，则(LP1)关于的单

15、纯形表中所在的第行对应的方程为， （4.2.14）这里为中非基变量的指标集，为人工变量中非基变量的指标集如果（4.2.14）式中所有，则有。这说明人工变量可由诸人工变量线性表出，从而可知原约束方程组中第个方程可由另外一些方程（即人工变量对应的那些约束方程）的适当线性组合来表示，因此，第个约束方程是多余的，应当删去，这相当于从中删去第行如果（4.2.14）中存在，使，则由定理4.2.4知，以为主元进行旋转变换，得到(LP1)的新的单纯形表，它对应的基本可行解仍为(LP1)的最优解，但新的基变量中减少了一个人工变量若新的基变量中还有人工变量，再重复此法，经过有限次，必能化为（2）的情形综上所述，对

16、于不具有明显可行基的(LP)，可先用单纯形法解(LP1)，解的结果或者说明(LP)无可行解，或者找到(LP)的一个基本可行解然后再从这个基本可行解开始应用单纯形法求解(LP)，这是两阶段法的第二阶段注意，在第一阶段迭代过程中，人工变量一旦离开基，随之也就失去了作用，故可从单纯形表中删去人工变量所在的列例4 求解线性规划问题 （4.2.15）解 只需引进两个人工变量和，相应的(LP1)如下：01210104-12111004303*100143152000813-100000-2101/3014/3-22*02/3108/31011/3004/3-2101/3004/32301/3004/3-1

17、*000-1/210-1101/31/204/31011/3004/3-1000-1/200500-2/3-3/20-8/310001/200101/314/30011/3-1/24/3000-2/3-48/3最优解和最优值分别为，=8/36、单纯形法的几何解释定理6 设是（LP）关于基的基本可行解，对进行一次单纯形迭代得到新的基本可行解，若是非退化的，则与是（LP）的可行域的相邻极点4.3 对偶理论定义 设有线性规划问题 （4.3.1）及 （4.3.2）称问题（4.3.2）为问题（4.3.1）的对偶问题，并称问题（4.3.1）为原问题定理1 对偶问题的对偶是原问题 下面给出其它形式的线性规划

18、问题的对偶问题标准形式的线性规划问题 （LP）的对偶问题如下： （DP）一般的线性规划问题 （P）的对偶问题如下： （D）原问题与对偶问题的对应关系表原问题min对偶问题max变量行约束无限制=行约束变量=无限制例5 求如下线性规划问题的对偶问题解 先把上述线性规划问题写成如下形式它的对偶问题为下面总假设在(P)中，是行满秩矩阵定理2 设和分别为（P）和（D）的可行解，则定理3 （P）和（D）都有最优解的充要条件是它们都有可行解定理4 设和分别是（P）和（D）的可行解，则它们分别为（P）和（D）的最优解的充要条件是 定理5 在（P）和（D）中，若有一个有最优解，则另一个也有最优解，且（P）和（

19、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）

20、的第个不等式约束为紧约束；若（P）的第个非负约束为松约束，则（D）的第个不等式约束为紧约束；若（D）的第个不等式约束为松约束，则（P）的第个非负约束为紧约束4.4 对偶单纯形法1、 对偶单纯形法的算法步骤设为(LP)中关于基的基本解，令若和分别是(LP)和(DP)的可行解，则，这等价于，即对应的检验数全部非正，故由定理4.2.1知，是(LP)的最优解而，所以由定理4.3.4知，是 (DP)的最优解这不但说明可以由(LP)的最优解得出(DP)的最优解，而且表明：(LP)中关于基的基本解对应的检验数全部非正当且仅当为(DP)的可行解因此，我们引入如下的概念定义 (LP)中检验数全部非正的基本解称为

21、对偶可行解或正则解，相应的基称为对偶可行基或正则基算法4-2（对偶单纯形法）Step1 选取(LP)的一个关于正则基的正则解，列出单纯形表Step2 若，则是最优解，算法结束；否则，按选取为离基变量Step3 若，则(LP)无可行解，算法终止；否则，按选取为进基变量Step4 以为主元进行旋转变换，得到新的单纯形表以取代（亦为正则基），返回Step2例6 用对偶单纯形法求解线性规划问题解 引进变量将给定的线性规划问题化为标准形式：-2-1-1100-3-3*-20010-4-1-21001-1-1-3-1000001/3-11-2/3*0-1/312/300-1/304/30-4/310-1/

22、311/30-7/3-10-1/304/30-1/23/2-3/2101/211/21/2-1/2003/20-3/23/2-1/2011/20-5/2-1/2-1/2003/2最优解为最优值为2、 退化情形的处理Bland规则：（1）离基规则：由确定为离基变量；（2）进基规则：由确定为进基变量3、 初始正则解的求法设已知(LP)的关于基的基本解，它不是正则解（也不必是可行解），对应的典式为 （4.4.1）引进一个人工约束 ，其中表示充分大的正数，为引进的变量把这个约束添加到（4.4.1）式中得到一个新的线性规划问题 （4.4.2）问题（4.4.2）称为(LP)关于基的扩充问题对于扩充问题（4

23、.4.2），按下述方法处理，即可得出它的一个正则解设选取为进基变量，并指定为离基变量，以为主元作旋转变换，得到新的典式，易知新的典式中目标函数的表达式为：，其中检验数 所以，经上述迭代所得的新的基本解便是（4.4.2）式的正则解扩充问题（4.4.2）有了初始正则解后，便可开始对偶单纯形迭代 迭代结果有且仅有下列三种可能情形：（1）扩充问题无可行解，则也无可行解；（2）扩充问题有最优解，且扩充问题的最优值与无关，则是的最优解；（3）扩充问题有最优解，但扩充问题的最优值与有关，则无最优解例7 求解线性规划问题：解 显然为一个基，但既不是可行基也不是正则基，因为对应的基本解且检验数增加人工约束11200501-110-1*01*10102-30001010-1-+500-21-1*-10110100-50-2-2103-106002-11+101-1*10-100-1-20213020302011-10-11-1010-10-303最优解为，最优值为34