《4线性规划的基本理论.doc》由会员分享，可在线阅读，更多相关《4线性规划的基本理论.doc（25页珍藏版）》请在金锄头文库上搜索。
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)有一个现成的基本可行解：，与之对应的基为单位矩阵，从而目标函数可改写为 ，于是得到(LP1)的一个单纯形表如表4.2.2表4.2.2 两阶段法初始单纯形表10
