第三章第三章 线性规划的一般求解方法线性规划的一般求解方法 单纯形法单纯形法它的一般形式为：它的一般形式为：其中，其中， , ， 是已知数，是已知数， 是待决策的变量。是待决策的变量。一、线性规划问题的一般形式一、线性规划问题的一般形式一般情况下一般情况下 m m n n , , m m , , n n 为正整数为正整数, ,分别表示约束条件的个数和决策变量的个数分别表示约束条件的个数和决策变量的个数, , 称为约束条件称为约束条件( (Subject to)Subject to)。 称为变量的非负约束条件。其余称为变量的非负约束条件。其余的变量可取正值、负值、或零值，称这样的变量的变量可取正值、负值、或零值，称这样的变量为符号无限制变量或自由变量。为符号无限制变量或自由变量。线性规划模型的特征是：一组决策变量线性规划模型的特征是：一组决策变量 ，一组，一组约束条件。一个目标函数。目标函数和约束条件约束条件。一个目标函数。目标函数和约束条件都是线性的。都是线性的。由前面一般形式可知由前面一般形式可知, ,线性规划问题可能有各种线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现不同的形式。目标函数有实现最大化也有实现最小化的最小化的; ;约束条件可以是约束条件可以是“ ” ”形式、形式、“ ”形式不等式形式不等式, ,有的是等式有的是等式 决策变量有时有非负限制有时没有。这决策变量有时有非负限制有时没有。这种多样性给讨论问题代来了不便。为了便种多样性给讨论问题代来了不便。为了便于今后讨论，我们就要规定线性规划问题于今后讨论，我们就要规定线性规划问题的标准型的标准型二、线性规划问题的标准行式是什么？二、线性规划问题的标准行式是什么？如何将一个如何将一个LPLP问题的一般形式转换为问题的一般形式转换为标准形式标准形式？(1)(1)、这里规定的标准形式为：这里规定的标准形式为： 这里我们假设这里我们假设 b bi i 0 ( 0 ( i i = = 1,2,1,2,m m),),否则两端同时乘以否则两端同时乘以“-1”“-1”。简记为简记为：用矩阵表示为用矩阵表示为：用列向量表示为：用列向量表示为：（2 2）为了把一般形式的）为了把一般形式的LPLP变换为标准变换为标准形式，必须消除其不等式约束和符号形式，必须消除其不等式约束和符号无限制变量。无限制变量。 目标函数的转换目标函数的转换 约束条件的转换约束条件的转换 变量的非负约束的转换变量的非负约束的转换 任何形式的线性规划数学模型都可以转任何形式的线性规划数学模型都可以转换成标准型的线性规划换成标准型的线性规划 例例4: 4: 试将如下线性规划问题化成标准型试将如下线性规划问题化成标准型解：令解：令 x x3 3 = = x x4 4 - - x x5 5 , , x x4 4 , , x x5 5 0 , (1) 0 , (1)式左式左端加上非负松弛变量端加上非负松弛变量 x x6 6 , (2) , (2)式左端减去非负剩余变式左端减去非负剩余变量量 x x7 7 , , 则可将上述线性规划问题化成如下的标准型则可将上述线性规划问题化成如下的标准型: :三、什么是可行解、可行域，三、什么是可行解、可行域，可行域的几何结构？可行域的几何结构？ 满足所有约束条件的决策变量，称为可满足所有约束条件的决策变量，称为可行解或可行点行解或可行点( (feasible point)feasible point)。使目标函数值最大的可行解使目标函数值最大的可行解称称为最优解为最优解所所有有可可行行点点组组成成的的集集合合称称为为可可行行域域（feasible regionfeasible region），），记为记为D.D.给定一个给定一个LPLP问题问题可行域可行域D,D,下列三种情况下列三种情况必居其一必居其一 D = D = 称该问题无解或不可行。称该问题无解或不可行。D D 且可行域有界。则线性规划问题一且可行域有界。则线性规划问题一定存在最优解。这时最优解唯一，也可能有定存在最优解。这时最优解唯一，也可能有无穷多。无穷多。D D ， 且可行域为无界，则线性规划问题且可行域为无界，则线性规划问题或者有最优解（唯一或无穷多）也可能没有或者有最优解（唯一或无穷多）也可能没有有限的最优解。有限的最优解。当可行域非空时，可行域的几何结构为当可行域非空时，可行域的几何结构为( (多多面面) )凸集凸集 四、基本解、基本可行解四、基本解、基本可行解 (basic solution、basic feasible solution)秩（秩（A A）=m=m，则矩阵则矩阵A A中存在一个中存在一个m m阶满秩阶满秩子方阵子方阵B B。称称B B矩阵为线性规划问题的一个基。矩阵为线性规划问题的一个基。解之间的关系解之间的关系可行解：满足约束条件可行解：满足约束条件最优解：满足约束条件，同时使目标函数值最优。最优解：满足约束条件，同时使目标函数值最优。基础解：满足基础解：满足 且非零分量的数目不大且非零分量的数目不大于方程的个数于方程的个数m m。基可行解：是基础解又是可行解。基可行解：是基础解又是可行解。基最优解：满足约束条件，且无非零分量，或非基最优解：满足约束条件，且无非零分量，或非零分量对应的列向量现性无关，同时使目标函数值零分量对应的列向量现性无关，同时使目标函数值最优。最优。五、五、 LP问题的几何意义（单问题的几何意义（单纯形表的数学原理）纯形表的数学原理） 若线性规划问题存在可行域，则其可行域若线性规划问题存在可行域，则其可行域D D是凸集是凸集线性规划问题的可行解为基可行解的充要条件是的正线性规划问题的可行解为基可行解的充要条件是的正分量所对应的系数列向量线性无关分量所对应的系数列向量线性无关。X X是基本可行解的充分必要条件是是基本可行解的充分必要条件是X X是可行域是可行域D D的顶点的顶点 一个标准的一个标准的LPLP问题，若有可行解，则至少有一个基本问题，若有可行解，则至少有一个基本可行解可行解 一个标准的一个标准的LPLP问题，若有有限的最优值，则一定存在问题，若有有限的最优值，则一定存在一个基本可行解是最优解。一个基本可行解是最优解。 若线性规划问题存在可行域，则其可行域若线性规划问题存在可行域，则其可行域D D是凸集是凸集线性规划问题的可行解线性规划问题的可行解X X为基可行解的充要条件是为基可行解的充要条件是X X的正分量所对应的系数列向量线性无关的正分量所对应的系数列向量线性无关。X X是基本可行解的充分必要条件是是基本可行解的充分必要条件是X X是可行域是可行域D D的顶点的顶点 由以上定理可知，最优解一定在某一由以上定理可知，最优解一定在某一基本可行解处达到。因此单纯形法的基本可行解处达到。因此单纯形法的基本思想是：先找一个基本可行解，基本思想是：先找一个基本可行解，然后判断它是否为最优解，如不是，然后判断它是否为最优解，如不是，就找一个更好的基本可行解，再进行就找一个更好的基本可行解，再进行判断，如此迭代进行，直到找到最优判断，如此迭代进行，直到找到最优解或者判断该问题无界。解或者判断该问题无界。六、单纯形法六、单纯形法( (Simplex method)Simplex method)1 1单纯形表单纯形表为了计算的方便，我们可以将单纯形法的全部计为了计算的方便，我们可以将单纯形法的全部计算过程在一个类似增广矩阵的数表上进行，这种算过程在一个类似增广矩阵的数表上进行，这种表格称单纯形表，不同的教材设计表格稍有不同，表格称单纯形表，不同的教材设计表格稍有不同，这里设计如下：这里设计如下：2 单纯形方法步骤Step1Step1转换一般的转换一般的LPLP模型为标准型。模型为标准型。Step2 Step2 找一个初始可行基。找一个初始可行基。Step3 Step3 计算单纯形表中的各矩阵。计算单纯形表中的各矩阵。Step4 Step4 构造单纯形表。构造单纯形表。Step5 Step5 判断最优解，是，则结束。否判断最优解，是，则结束。否 则，转入下一步。则，转入下一步。Step6 Step6 换基迭代，返回换基迭代，返回Step5Step5。q 如何得到第一个基本可行解？如何得到第一个基本可行解？ 为了得到初始基本可行解，要首先找到初始基本可为了得到初始基本可行解，要首先找到初始基本可行基，设行基，设B B为约束矩阵的一个为约束矩阵的一个m m阶子式，如果阶子式，如果B B非奇非奇异，则矩阵异，则矩阵B B是一个基，是一个基，进一步，若进一步，若 ，那么，那么B B是初始基本可行基。是初始基本可行基。 就是初始基本可行解。找初始基本可行基就是初始基本可行解。找初始基本可行基的方法如下的方法如下1 1观察法与试验法。观察法与试验法。2.2.大大M M法。法。3.3.两阶段法两阶段法q如何判断基本可行解是最优解如何判断基本可行解是最优解？对线性规划问题的求解结果可能出现唯对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无一最优解、无穷多最优解、无界解和无可行解四种情况，可行解四种情况， 找入基变量找入基变量 找出基变量找出基变量 定轴心项定轴心项 作行变换作行变换 交换变量交换变量 q如何进行换基迭代如何进行换基迭代掌握线性规划问题的数学原理及代数掌握线性规划问题的数学原理及代数的单纯形解法是学习的单纯形解法是学习LPLP的最高境界。的最高境界。掌握这一方法对于以后的学习大有裨掌握这一方法对于以后的学习大有裨益，希望同学们发扬十二分的耐心和钻研益，希望同学们发扬十二分的耐心和钻研精神。精神。例题、用单纯形法求解例题、用单纯形法求解化为满秩标准形化为满秩标准形 2、写出初始单纯形表写出初始单纯形表 3、判断基本可行解是最优解判断基本可行解是最优解由于检验数有正数，且对应的由于检验数有正数，且对应的列向量不全为负，故进行换基列向量不全为负，故进行换基迭代，迭代，4、换基迭代、换基迭代 选上表中的为轴心项选上表中的为轴心项 5、判断、判断、由于检验数有正数且对应的由于检验数有正数且对应的列向量不全为负，故进行换基迭代，选上列向量不全为负，故进行换基迭代，选上表中的为轴心项表中的为轴心项 由单纯形表得一基最优解，由单纯形表得一基最优解，由于有非基变量的检验数为零，则此线性由于有非基变量的检验数为零，则此线性规划有无穷解。选上表中的规划有无穷解。选上表中的 为轴心项为轴心项. .原线性规划所有最优解为：原线性规划所有最优解为： 由此表的另一最优解由此表的另一最优解所有最优解为：所有最优解为：如何用如何用QMQM软件求解软件求解LPLP问题问题 三角洲航空公司的航班配置问三角洲航空公司的航班配置问题（怎样为各条航线分配班机和为乘题（怎样为各条航线分配班机和为乘客分配座位）。用客分配座位）。用LPLP模型解决，用到模型解决，用到6000060000个变量，个变量，4000040000个约束条件。个约束条件。课堂练习课堂练习A、用单纯形法求解两个变量的用单纯形法求解两个变量的LP问题。问题。B、用用QM软件求解软件求解LP问题问题谢谢谢谢