第1章线性规划.ppt

中原工学院机电学院中原工学院机电学院主讲：丁剑飞主讲：丁剑飞第第1章章 线性规划与单纯形法线性规划与单纯形法线性规划（线性规划（线性规划（线性规划（Linear ProgrammingLinear Programming）是运筹学中研究最早、）是运筹学中研究最早、）是运筹学中研究最早、）是运筹学中研究最早、理论较为完善，应用最广泛的一个分支。线性规划出现于理论较为完善，应用最广泛的一个分支。线性规划出现于理论较为完善，应用最广泛的一个分支。线性规划出现于理论较为完善，应用最广泛的一个分支。线性规划出现于2020世纪世纪世纪世纪3030年代，年代，年代，年代，19471947年年年年DantzigDantzig发明了求解线性规划的单纯发明了求解线性规划的单纯发明了求解线性规划的单纯发明了求解线性规划的单纯形法之后，线性规划的应用得到了迅速的发展和推广。随形法之后，线性规划的应用得到了迅速的发展和推广。随形法之后，线性规划的应用得到了迅速的发展和推广。随形法之后，线性规划的应用得到了迅速的发展和推广。随着计算机技术的发展，成千上万个约束和变量的大型线性着计算机技术的发展，成千上万个约束和变量的大型线性着计算机技术的发展，成千上万个约束和变量的大型线性着计算机技术的发展，成千上万个约束和变量的大型线性规划问题得以求解，目前它广泛地应用于工农业生产、交规划问题得以求解，目前它广泛地应用于工农业生产、交规划问题得以求解，目前它广泛地应用于工农业生产、交规划问题得以求解，目前它广泛地应用于工农业生产、交通运输、军事和科学研究的各个方面，为社会节约和创造通运输、军事和科学研究的各个方面，为社会节约和创造通运输、军事和科学研究的各个方面，为社会节约和创造通运输、军事和科学研究的各个方面，为社会节约和创造了巨大的财富。了巨大的财富。了巨大的财富。了巨大的财富。1.1 1.1 线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型1.1.1 1.1.1 问题的提出问题的提出问题的提出问题的提出例例例例1 1 某工厂在计划期内要安排生产某工厂在计划期内要安排生产某工厂在计划期内要安排生产某工厂在计划期内要安排生产I I、IIII两种产品，已知两种产品，已知两种产品，已知两种产品，已知生产单位产品所需的设备台时及生产单位产品所需的设备台时及生产单位产品所需的设备台时及生产单位产品所需的设备台时及A A、B B两种原材料的消耗，两种原材料的消耗，两种原材料的消耗，两种原材料的消耗，如表如表如表如表1-11-1所示。所示。所示。所示。设设设设x x1 1，x x2 2分别表示在计划期内产品分别表示在计划期内产品分别表示在计划期内产品分别表示在计划期内产品I I、IIII的产量。考虑台的产量。考虑台的产量。考虑台的产量。考虑台时限制有：时限制有：时限制有：时限制有：x x1 1+2x+2x2 288同样，考虑材料同样，考虑材料同样，考虑材料同样，考虑材料A A、B B的限量有：的限量有：的限量有：的限量有：4x4x1 1 16 16 4x 4x2 21212设设设设z z表示利润，则表示利润，则表示利润，则表示利润，则z=2xz=2x1 1+3x+3x2 2第第1章章 线性规划与单纯形法线性规划与单纯形法I IIIII设备设备设备设备材料材料材料材料A A材料材料材料材料B B利润利润利润利润1 14 40 02 22 20 04 43 38 8台时台时台时台时16kg16kg12kg12kg第第1章章 线性规划与单纯形法线性规划与单纯形法综上所述，该计划问题可用下面的数学模型表示：综上所述，该计划问题可用下面的数学模型表示：综上所述，该计划问题可用下面的数学模型表示：综上所述，该计划问题可用下面的数学模型表示：例例例例2 2 某钢厂熔炼一种新型不锈钢，需要四种合金某钢厂熔炼一种新型不锈钢，需要四种合金某钢厂熔炼一种新型不锈钢，需要四种合金某钢厂熔炼一种新型不锈钢，需要四种合金T T1 1，T T2 2，T T3 3，T T4 4为原料，经测定这四种原材料关于为原料，经测定这四种原材料关于为原料，经测定这四种原材料关于为原料，经测定这四种原材料关于CrCr、MnMn和和和和NiNi的质量百分比、单价以及这种新型不锈钢需要的质量百分比、单价以及这种新型不锈钢需要的质量百分比、单价以及这种新型不锈钢需要的质量百分比、单价以及这种新型不锈钢需要CrCr、MnMn和和和和NiNi的最低质量百分比如表的最低质量百分比如表的最低质量百分比如表的最低质量百分比如表1-21-2所示。假定在熔炼时质量没有所示。假定在熔炼时质量没有所示。假定在熔炼时质量没有所示。假定在熔炼时质量没有损耗，问要熔炼损耗，问要熔炼损耗，问要熔炼损耗，问要熔炼100100吨这样的不锈钢，应选用原料吨这样的不锈钢，应选用原料吨这样的不锈钢，应选用原料吨这样的不锈钢，应选用原料T T1 1，T T2 2，T T3 3，T T4 4各多少吨能使成本最小？各多少吨能使成本最小？各多少吨能使成本最小？各多少吨能使成本最小？目标函数目标函数满足约束条件满足约束条件第第1章章 线性规划与单纯形法线性规划与单纯形法设选用原材料设选用原材料设选用原材料设选用原材料T T1 1，T T2 2，T T3 3，T T4 4的量分别为的量分别为的量分别为的量分别为x x1 1、x x2 2、x x3 3、x x4 4。由于追求目标是成本最小，故有最小成本表达式：由于追求目标是成本最小，故有最小成本表达式：由于追求目标是成本最小，故有最小成本表达式：由于追求目标是成本最小，故有最小成本表达式：炼制过程中质量没有损耗，熔炼不锈钢炼制过程中质量没有损耗，熔炼不锈钢炼制过程中质量没有损耗，熔炼不锈钢炼制过程中质量没有损耗，熔炼不锈钢100100吨，故有：吨，故有：吨，故有：吨，故有：T T1 1 T T2 2 T T3 3 T T4 4不锈钢所需不锈钢所需不锈钢所需不锈钢所需各各各各元素的元素的元素的元素的最低质最低质最低质最低质量百分比量百分比量百分比量百分比CrCrMnMnNiNi 3.21 4.53 2.19 1.763.21 4.53 2.19 1.76 2.04 1.12 3.57 4.33 2.04 1.12 3.57 4.33 5.82 3.06 4.27 2.73 5.82 3.06 4.27 2.733.203.202.102.104.304.30单价（万元单价（万元单价（万元单价（万元/吨）吨）吨）吨）11.5 9.7 8.2 7.611.5 9.7 8.2 7.6原料原料各元素的各元素的质量百分质量百分比比(%)第第1章章 线性规划与单纯形法线性规划与单纯形法熔炼不锈钢熔炼不锈钢熔炼不锈钢熔炼不锈钢100100吨，吨，吨，吨，CrCr、MnMn和和和和NiNi的质量百分比满足以下的质量百分比满足以下的质量百分比满足以下的质量百分比满足以下的不等式：的不等式：的不等式：的不等式：此外，各种合金的加入量以整吨为单位，即限制此外，各种合金的加入量以整吨为单位，即限制此外，各种合金的加入量以整吨为单位，即限制此外，各种合金的加入量以整吨为单位，即限制x x1 1、x x2 2、x x3 3、x x4 4 0 0，且为整数。，且为整数。，且为整数。，且为整数。综上所述，我们得到该问题的数学模型为：综上所述，我们得到该问题的数学模型为：综上所述，我们得到该问题的数学模型为：综上所述，我们得到该问题的数学模型为：第第1章章 线性规划与单纯形法线性规划与单纯形法这样的例子不胜枚举，这些例子具体内容各不相同，但这样的例子不胜枚举，这些例子具体内容各不相同，但这样的例子不胜枚举，这些例子具体内容各不相同，但这样的例子不胜枚举，这些例子具体内容各不相同，但归结出的数学模型却属于同一类问题。它们的共同特征是：归结出的数学模型却属于同一类问题。它们的共同特征是：归结出的数学模型却属于同一类问题。它们的共同特征是：归结出的数学模型却属于同一类问题。它们的共同特征是：（1 1）每个问题都用一组决策变量（）每个问题都用一组决策变量（）每个问题都用一组决策变量（）每个问题都用一组决策变量（x x1 1,x,x2 2,x xn n）表示某）表示某）表示某）表示某一方案，这组决策变量的值代表一个具体方案。一方案，这组决策变量的值代表一个具体方案。一方案，这组决策变量的值代表一个具体方案。一方案，这组决策变量的值代表一个具体方案。（2 2）存在有关的数据，同决策变量构成互不矛盾的约束）存在有关的数据，同决策变量构成互不矛盾的约束）存在有关的数据，同决策变量构成互不矛盾的约束）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件用一组（不）等式表示。条件，这些约束条件用一组（不）等式表示。条件，这些约束条件用一组（不）等式表示。条件，这些约束条件用一组（不）等式表示。第第1章章 线性规划与单纯形法线性规划与单纯形法（3 3）都有一个要达到的目标，它可以用决策变量的线性）都有一个要达到的目标，它可以用决策变量的线性）都有一个要达到的目标，它可以用决策变量的线性）都有一个要达到的目标，它可以用决策变量的线性函数（称为目标函数）来表示。按问题的不同目标函数实函数（称为目标函数）来表示。按问题的不同目标函数实函数（称为目标函数）来表示。按问题的不同目标函数实函数（称为目标函数）来表示。按问题的不同目标函数实现最大化或最小化。现最大化或最小化。现最大化或最小化。现最大化或最小化。满足上述条件的数学模型称为满足上述条件的数学模型称为满足上述条件的数学模型称为满足上述条件的数学模型称为线性规划的数学模型线性规划的数学模型线性规划的数学模型线性规划的数学模型。一。一。一。一般形式为：般形式为：般形式为：般形式为：目标函数目标函数满足约束条件满足约束条件（1-1）（1-2）（1-3）第第1章章 线性规划与单纯形法线性规划与单纯形法在线性规划的数学模型中，式（在线性规划的数学模型中，式（在线性规划的数学模型中，式（在线性规划的数学模型中，式（1-11-1）称为）称为）称为）称为目标函数目标函数目标函数目标函数，c cj j称为称为称为称为价值系数价值系数价值系数价值系数；式（；式（；式（；式（1-21-2）、式（）、式（）、式（）、式（1-31-3）称为）称为）称为）称为约束条件约束条件约束条件约束条件，a aij ij称为称为称为称为技术系数技术系数技术系数技术系数，b bij ij称为称为称为称为资源系数资源系数资源系数资源系数。1.1.2 1.1.2 图解法图解法图解法图解法图解法简单直观，有助于理解求解线性规划的基本原理。图解法简单直观，有助于理解求解线性规划的基本原理。图解法简单直观，有助于理解求解线性规划的基本原理。图解法简单直观，有助于理解求解线性规划的基本原理。下面以例下面以例下面以例下面以例1 1为例：为例：为例：为例：第第1章章 线性规划与单纯形法线性规划与单纯形法从图中可以看出，当目标函数等值线移到从图中可以看出，当目标函数等值线移到从图中可以看出，当目标函数等值线移到从图中可以看出，当目标函数等值线移到Q Q2 2点时，点时，点时，点时，z z值取值取值取值取得最大值，这样就得到了例得最大值，这样就得到了例得最大值，这样就得到了例得最大值，这样就得到了例1 1的最优解，这时目标函数的的最优解，这时目标函数的的最优解，这时目标函数的的最优解，这时目标函数的最大值是最大值是最大值是最大值是z=14z=14。可行域可行域目标函数目标函数等值线等值线第第1章章 线性规划与单纯形法线性规划与单纯形法上例中问题的最优解是唯一的，但对一般的线性规划问上例中问题的最优解是唯一的，但对一般的线性规划问上例中问题的最优解是唯一的，但对一般的线性规划问上例中问题的最优解是唯一的，但对一般的线性规划问题，求解结果还可能出现以下几种情况：题，求解结果还可能出现以下几种情况：题，求解结果还可能出现以下几种情况：题，求解结果还可能出现以下几种情况：1.1.无穷多最优解无穷多最优解无穷多最优解无穷多最优解将例将例将例将例1 1中目标函数改为中目标函数改为中目标函数改为中目标函数改为max z=2xmax z=2x1 1+4x+4x2 2。第第1章章 线性规划与单纯形法线性规划与单纯形法 2.2.无界解无界解无界解无界解考虑下述线性规划问题考虑下述线性规划问题考虑下述线性规划问题考虑下述线性规划问题3.3.无可行解无可行解无可行解无可行解在例在例在例在例1 1的数学模型中增加一个约束条件的数学模型中增加一个约束条件的数学模型中增加一个约束条件的数学模型中增加一个约束条件-2x1+x24-2x1+x24，该问，该问，该问，该问题的可行域为空集。因此无可行解，更无最优解。题的可行域为空集。因此无可行解，更无最优解。题的可行域为空集。因此无可行解，更无最优解。题的可行域为空集。因此无可行解，更无最优解。情况情况情况情况2 2缺乏必要的约束条件；情况缺乏必要的约束条件；情况缺乏必要的约束条件；情况缺乏必要的约束条件；情况3 3出现了矛盾的约束，出现了矛盾的约束，出现了矛盾的约束，出现了矛盾的约束，在建模时应当注意。在建模时应当注意。在建模时应当注意。在建模时应当注意。从图解法中我们可以直观地看到：从图解法中我们可以直观地看到：从图解法中我们可以直观地看到：从图解法中我们可以直观地看到：1 1、当线性规划问题的可行域非空时，它是有界或无当线性规划问题的可行域非空时，它是有界或无当线性规划问题的可行域非空时，它是有界或无当线性规划问题的可行域非空时，它是有界或无界的凸多边形；界的凸多边形；界的凸多边形；界的凸多边形；2 2、若线性规划存在最优解，它一定是在有界可行域若线性规划存在最优解，它一定是在有界可行域若线性规划存在最优解，它一定是在有界可行域若线性规划存在最优解，它一定是在有界可行域的某个顶点得到；的某个顶点得到；的某个顶点得到；的某个顶点得到；3 3、如果在两个顶点同时得到最优解，则它们连线上如果在两个顶点同时得到最优解，则它们连线上如果在两个顶点同时得到最优解，则它们连线上如果在两个顶点同时得到最优解，则它们连线上的任意一个点都是最优解，即有无穷多个最优点。的任意一个点都是最优解，即有无穷多个最优点。的任意一个点都是最优解，即有无穷多个最优点。的任意一个点都是最优解，即有无穷多个最优点。图解法虽然直观、简便，但是当变量多于三个以上图解法虽然直观、简便，但是当变量多于三个以上图解法虽然直观、简便，但是当变量多于三个以上图解法虽然直观、简便，但是当变量多于三个以上时就无能为力了。因此后面要介绍一种代数法时就无能为力了。因此后面要介绍一种代数法时就无能为力了。因此后面要介绍一种代数法时就无能为力了。因此后面要介绍一种代数法单纯单纯单纯单纯形法形法形法形法。为了便于讨论，先规定线性规划问题的数学模。为了便于讨论，先规定线性规划问题的数学模。为了便于讨论，先规定线性规划问题的数学模。为了便于讨论，先规定线性规划问题的数学模型的标准形式。型的标准形式。型的标准形式。型的标准形式。第第1章章 线性规划与单纯形法线性规划与单纯形法第第1章章 线性规划与单纯形法线性规划与单纯形法1.1.3 1.1.3 线性规划的标准形式线性规划的标准形式线性规划的标准形式线性规划的标准形式线性规划模型模型多种多样，为了讨论和求解方便，人线性规划模型模型多种多样，为了讨论和求解方便，人线性规划模型模型多种多样，为了讨论和求解方便，人线性规划模型模型多种多样，为了讨论和求解方便，人为把它们转化为标准形式。为把它们转化为标准形式。为把它们转化为标准形式。为把它们转化为标准形式。或简写为：或简写为：或简写为：或简写为：第第1章章 线性规划与单纯形法线性规划与单纯形法用矩阵表示为：用矩阵表示为：用矩阵表示为：用矩阵表示为：A A为约束条件的为约束条件的为约束条件的为约束条件的mnmn维系数矩阵，一般维系数矩阵，一般维系数矩阵，一般维系数矩阵，一般mmn n。b b为资源向量；为资源向量；为资源向量；为资源向量；第第1章章 线性规划与单纯形法线性规划与单纯形法C C为价值向量；为价值向量；为价值向量；为价值向量；X X为决策变量。为决策变量。为决策变量。为决策变量。一般线性规划模型转化为标准形式的步骤：一般线性规划模型转化为标准形式的步骤：一般线性规划模型转化为标准形式的步骤：一般线性规划模型转化为标准形式的步骤：（1 1）若）若）若）若min z=CXmin z=CX。令。令。令。令z=-zz=-z，于是得，于是得，于是得，于是得max z=-CXmax z=-CX。（2 2）约束方程为不等式，分两种情况：）约束方程为不等式，分两种情况：）约束方程为不等式，分两种情况：）约束方程为不等式，分两种情况：约束方程为约束方程为约束方程为约束方程为 不等式，可在不等式的左端加入非负松弛变量，把不等式不等式，可在不等式的左端加入非负松弛变量，把不等式不等式，可在不等式的左端加入非负松弛变量，把不等式不等式，可在不等式的左端加入非负松弛变量，把不等式变为等式；变为等式；变为等式；变为等式；如果为如果为如果为如果为 不等式，可在左端减去一个非负剩不等式，可在左端减去一个非负剩不等式，可在左端减去一个非负剩不等式，可在左端减去一个非负剩余变量（也可称为松弛变量）。余变量（也可称为松弛变量）。余变量（也可称为松弛变量）。余变量（也可称为松弛变量）。（3 3）若存在无约束变量）若存在无约束变量）若存在无约束变量）若存在无约束变量x xk k，可令，可令，可令，可令x xk k=x xk k-x-xk k”，其中，其中，其中，其中x xk k，x xk k”00。下面举例说明。下面举例说明。下面举例说明。下面举例说明。第第1章章 线性规划与单纯形法线性规划与单纯形法例例例例4.4.将下述线性规划问题化为标准型将下述线性规划问题化为标准型将下述线性规划问题化为标准型将下述线性规划问题化为标准型该问题的标准型为：该问题的标准型为：该问题的标准型为：该问题的标准型为：第第1章章 线性规划与单纯形法线性规划与单纯形法1.1.4 1.1.4 线性规划问题的解的概念线性规划问题的解的概念线性规划问题的解的概念线性规划问题的解的概念由上节我们知道线性规划的标准形式为：由上节我们知道线性规划的标准形式为：由上节我们知道线性规划的标准形式为：由上节我们知道线性规划的标准形式为：1.1.可行解可行解可行解可行解满足式（满足式（满足式（满足式（1-51-5）、（）、（）、（）、（1-61-6）的解）的解）的解）的解X=(xX=(x1 1,x,x2 2,x xn n)T T称为线性称为线性称为线性称为线性规划的规划的规划的规划的可行解可行解可行解可行解，使目标函数达到最大值的可行解称为，使目标函数达到最大值的可行解称为，使目标函数达到最大值的可行解称为，使目标函数达到最大值的可行解称为最优最优最优最优解解解解。（1-4）（1-5）（1-6）第第1章章 线性规划与单纯形法线性规划与单纯形法2.2.基基基基设设设设A A是约束方程组的是约束方程组的是约束方程组的是约束方程组的mnmn维系数矩阵，其秩为维系数矩阵，其秩为维系数矩阵，其秩为维系数矩阵，其秩为mm。B B是其是其是其是其mmmm阶非奇异子矩阵，称阶非奇异子矩阵，称阶非奇异子矩阵，称阶非奇异子矩阵，称B B是线性规划问题的一个是线性规划问题的一个是线性规划问题的一个是线性规划问题的一个基基基基。不。不。不。不失一般性，设失一般性，设失一般性，设失一般性，设则称则称则称则称P Pj j(j(j=1,2,m)=1,2,m)为为为为基向量基向量基向量基向量，与基向量，与基向量，与基向量，与基向量P Pj j对应的变量对应的变量对应的变量对应的变量x xj j(j(j=1,j=2,m)=1,j=2,m)为为为为基变量基变量基变量基变量，其他的称为，其他的称为，其他的称为，其他的称为非基向量非基向量非基向量非基向量。设。设。设。设A A的的的的秩为秩为秩为秩为mm，因，因，因，因mmn n，所以约束方程组有无穷多个解。假定前，所以约束方程组有无穷多个解。假定前，所以约束方程组有无穷多个解。假定前，所以约束方程组有无穷多个解。假定前mm个基变量的系数列向量是线性独立的。（个基变量的系数列向量是线性独立的。（个基变量的系数列向量是线性独立的。（个基变量的系数列向量是线性独立的。（1-51-5）可写成：）可写成：）可写成：）可写成：第第1章章 线性规划与单纯形法线性规划与单纯形法或或或或方程组（方程组（方程组（方程组（1-71-7）的一个基是）的一个基是）的一个基是）的一个基是（1-）第第1章章 线性规划与单纯形法线性规划与单纯形法对应的基变量是对应的基变量是对应的基变量是对应的基变量是X XB B=(x=(x1 1,x,x2 2,x xmm)T T若令非基变量为若令非基变量为若令非基变量为若令非基变量为0 0，这时变量的个数等于线性方程组的个，这时变量的个数等于线性方程组的个，这时变量的个数等于线性方程组的个，这时变量的个数等于线性方程组的个数，用高斯消元法，求出一个解数，用高斯消元法，求出一个解数，用高斯消元法，求出一个解数，用高斯消元法，求出一个解X=(xX=(x1 1,x,x2 2,x,xmm,0,0),0,0)T T该解的非零分量数不大于方程个数该解的非零分量数不大于方程个数该解的非零分量数不大于方程个数该解的非零分量数不大于方程个数mm，称，称，称，称X X为为为为基解基解基解基解。由此。由此。由此。由此可见，有一个基，就可求出一个基解。图可见，有一个基，就可求出一个基解。图可见，有一个基，就可求出一个基解。图可见，有一个基，就可求出一个基解。图1-21-2中的点中的点中的点中的点o o、Q Q1 1、Q Q2 2、Q Q3 3、Q Q4 4、以及延长各线的交点都代表基解。、以及延长各线的交点都代表基解。、以及延长各线的交点都代表基解。、以及延长各线的交点都代表基解。3.3.基可行解基可行解基可行解基可行解满足非负条件（满足非负条件（满足非负条件（满足非负条件（1-61-6）的基解称为）的基解称为）的基解称为）的基解称为基可行解基可行解基可行解基可行解。4.4.可行基可行基可行基可行基对应于基可行解的称为对应于基可行解的称为对应于基可行解的称为对应于基可行解的称为可行基可行基可行基可行基。约束方程组（。约束方程组（。约束方程组（。约束方程组（1-51-5）的基）的基）的基）的基解数目最多是解数目最多是解数目最多是解数目最多是C Cn nmm。一般基可行解的数目小于基解数目。一般基可行解的数目小于基解数目。一般基可行解的数目小于基解数目。一般基可行解的数目小于基解数目。第第1章章 线性规划与单纯形法线性规划与单纯形法以上提到的几种解的概念可用图以上提到的几种解的概念可用图以上提到的几种解的概念可用图以上提到的几种解的概念可用图1-61-6表示。表示。表示。表示。如果基解中的非零分量的个数小于如果基解中的非零分量的个数小于如果基解中的非零分量的个数小于如果基解中的非零分量的个数小于mm，该解是退化解。，该解是退化解。，该解是退化解。，该解是退化解。在以后的讨论时，假设不出现退化的情况。上面给出的线在以后的讨论时，假设不出现退化的情况。上面给出的线在以后的讨论时，假设不出现退化的情况。上面给出的线在以后的讨论时，假设不出现退化的情况。上面给出的线性规划解的概念和定义有助于用来分析线性规划的求解过性规划解的概念和定义有助于用来分析线性规划的求解过性规划解的概念和定义有助于用来分析线性规划的求解过性规划解的概念和定义有助于用来分析线性规划的求解过程。程。程。程。非可行解非可行解可行解可行解基解基解基基可可行行解解第第1章章 线性规划与单纯形法线性规划与单纯形法1.2 1.2 单纯形法单纯形法单纯形法单纯形法从上一节可以知道，如果线性规划有最优解，必定在可从上一节可以知道，如果线性规划有最优解，必定在可从上一节可以知道，如果线性规划有最优解，必定在可从上一节可以知道，如果线性规划有最优解，必定在可行域的某个顶点，用穷举法计算量非常大。行域的某个顶点，用穷举法计算量非常大。行域的某个顶点，用穷举法计算量非常大。行域的某个顶点，用穷举法计算量非常大。我们可以换一种思路，从某一个基可行解出发，每次总我们可以换一种思路，从某一个基可行解出发，每次总我们可以换一种思路，从某一个基可行解出发，每次总我们可以换一种思路，从某一个基可行解出发，每次总是寻找一个比上一次更好的基可行解，如果不如上一个好是寻找一个比上一次更好的基可行解，如果不如上一个好是寻找一个比上一次更好的基可行解，如果不如上一个好是寻找一个比上一次更好的基可行解，如果不如上一个好就不计算，这样可以大大减少计算量。基本思想是从可行就不计算，这样可以大大减少计算量。基本思想是从可行就不计算，这样可以大大减少计算量。基本思想是从可行就不计算，这样可以大大减少计算量。基本思想是从可行域中某个基可行解（顶点）开始，转换到另一个基可行解，域中某个基可行解（顶点）开始，转换到另一个基可行解，域中某个基可行解（顶点）开始，转换到另一个基可行解，域中某个基可行解（顶点）开始，转换到另一个基可行解，并使目标函数逐步增大，最后得到最优解。这就是单纯形并使目标函数逐步增大，最后得到最优解。这就是单纯形并使目标函数逐步增大，最后得到最优解。这就是单纯形并使目标函数逐步增大，最后得到最优解。这就是单纯形法的求解思路。由美国数学家法的求解思路。由美国数学家法的求解思路。由美国数学家法的求解思路。由美国数学家DantzigDantzig首先提出，是目前求首先提出，是目前求首先提出，是目前求首先提出，是目前求解线性规划最普遍最有效的方法。我们先一个例子来说明。解线性规划最普遍最有效的方法。我们先一个例子来说明。解线性规划最普遍最有效的方法。我们先一个例子来说明。解线性规划最普遍最有效的方法。我们先一个例子来说明。1.2.1 1.2.1 举例举例举例举例以例以例以例以例1 1为例，其标准形式为：为例，其标准形式为：为例，其标准形式为：为例，其标准形式为：第第1章章 线性规划与单纯形法线性规划与单纯形法很容易找到一个基很容易找到一个基很容易找到一个基很容易找到一个基对应于对应于对应于对应于B B的基变量是的基变量是的基变量是的基变量是x x3 3,x,x4 4,x,x5 5，从（，从（，从（，从（1-91-9）可以得到）可以得到）可以得到）可以得到（1-8）（1-9）第第1章章 线性规划与单纯形法线性规划与单纯形法将（将（将（将（1-101-10）带入目标函数（）带入目标函数（）带入目标函数（）带入目标函数（1-81-8）得到）得到）得到）得到z=0+2xz=0+2x1 1+3x+3x2 2 令非基变量等于零，得到令非基变量等于零，得到令非基变量等于零，得到令非基变量等于零，得到z=0z=0，得到一个基可行解，得到一个基可行解，得到一个基可行解，得到一个基可行解X X(0)(0)X X(0)(0)=(0,0,8,16,12)=(0,0,8,16,12)T T从（从（从（从（1-111-11）可知两个非基变量系数都是正数，因此非基）可知两个非基变量系数都是正数，因此非基）可知两个非基变量系数都是正数，因此非基）可知两个非基变量系数都是正数，因此非基变量转化为基变量后目标函数有增大的可能，一般选择正变量转化为基变量后目标函数有增大的可能，一般选择正变量转化为基变量后目标函数有增大的可能，一般选择正变量转化为基变量后目标函数有增大的可能，一般选择正系数最大的那个非基变量为换入变量，同时还要选择一个系数最大的那个非基变量为换入变量，同时还要选择一个系数最大的那个非基变量为换入变量，同时还要选择一个系数最大的那个非基变量为换入变量，同时还要选择一个基变量换出为非基变量，按如下方法确定换出变量。基变量换出为非基变量，按如下方法确定换出变量。基变量换出为非基变量，按如下方法确定换出变量。基变量换出为非基变量，按如下方法确定换出变量。分析（分析（分析（分析（1-101-10），将），将），将），将x x2 2定为换入变量后，必须保证其余的定为换入变量后，必须保证其余的定为换入变量后，必须保证其余的定为换入变量后，必须保证其余的都为非负，即都为非负，即都为非负，即都为非负，即x x3 3,x,x4 4,x,x5 500。（1-10）（1-11）第第1章章 线性规划与单纯形法线性规划与单纯形法当当当当x x1 1=0=0，由（，由（，由（，由（1-101-10）得到：）得到：）得到：）得到：因此只有选择因此只有选择因此只有选择因此只有选择x x2 2=min8/2,-,12/4=3=min8/2,-,12/4=3此时基变量此时基变量此时基变量此时基变量x x5 5=0=0，因此用，因此用，因此用，因此用x x2 2去替换去替换去替换去替换x x5 5。为了求得以。为了求得以。为了求得以。为了求得以x x3 3,x,x4 4,x x2 2为基变量的基可行解，将（为基变量的基可行解，将（为基变量的基可行解，将（为基变量的基可行解，将（1-101-10）中的）中的）中的）中的x x2 2与与与与x x5 5位置对换。位置对换。位置对换。位置对换。得到得到得到得到（1-12）（1-13）第第1章章 线性规划与单纯形法线性规划与单纯形法z=9+2xz=9+2x1 1-3x-3x5 5/4/4令非基变量等于零，得令非基变量等于零，得令非基变量等于零，得令非基变量等于零，得z=9z=9，并得到另一个基可行解，并得到另一个基可行解，并得到另一个基可行解，并得到另一个基可行解X X(1)(1)X X(1)(1)=(0,3,2,16,0)=(0,3,2,16,0)T T从（从（从（从（1-141-14）可以看出，非基变量）可以看出，非基变量）可以看出，非基变量）可以看出，非基变量x x1 1的系数仍是正的。用的系数仍是正的。用的系数仍是正的。用的系数仍是正的。用同样的方法确定换入和换出变量，继续迭代，得到一个基同样的方法确定换入和换出变量，继续迭代，得到一个基同样的方法确定换入和换出变量，继续迭代，得到一个基同样的方法确定换入和换出变量，继续迭代，得到一个基可行解可行解可行解可行解X X(2)(2)X X(2)(2)=(2,3,0,8,0)=(2,3,0,8,0)T T再经过一次迭代，又得到一个基可行解再经过一次迭代，又得到一个基可行解再经过一次迭代，又得到一个基可行解再经过一次迭代，又得到一个基可行解X X(3)(3)X X(3)(3)=(4,2,0,0,4)=(4,2,0,0,4)T T而这时的目标函数表达式是：而这时的目标函数表达式是：而这时的目标函数表达式是：而这时的目标函数表达式是：z=14-1.5xz=14-1.5x3 3-0.125x-0.125x4 4此时非基变量的系数都是负数，说明已经是最优解。此时非基变量的系数都是负数，说明已经是最优解。此时非基变量的系数都是负数，说明已经是最优解。此时非基变量的系数都是负数，说明已经是最优解。（1-14）（1-15）第第1章章 线性规划与单纯形法线性规划与单纯形法1.2.2 1.2.2 初始基可行解的确定初始基可行解的确定初始基可行解的确定初始基可行解的确定（1 1）若线性规划问题）若线性规划问题）若线性规划问题）若线性规划问题从从从从P Pj j(j(j=1,2,n)=1,2,n)中一般能直接观察到一个初始可行基中一般能直接观察到一个初始可行基中一般能直接观察到一个初始可行基中一般能直接观察到一个初始可行基（1-16）（1-17）第第1章章 线性规划与单纯形法线性规划与单纯形法（2 2）对于所有约束条件是）对于所有约束条件是）对于所有约束条件是）对于所有约束条件是“”“”形式的不等式，每个约形式的不等式，每个约形式的不等式，每个约形式的不等式，每个约束条件的左端加一个松弛变量。经整理，重新对束条件的左端加一个松弛变量。经整理，重新对束条件的左端加一个松弛变量。经整理，重新对束条件的左端加一个松弛变量。经整理，重新对x xj j进行编进行编进行编进行编号，可得到下列方程组：号，可得到下列方程组：号，可得到下列方程组：号，可得到下列方程组：显然可以得到一个单位矩阵显然可以得到一个单位矩阵显然可以得到一个单位矩阵显然可以得到一个单位矩阵B B作为初始可行基。作为初始可行基。作为初始可行基。作为初始可行基。将（将（将（将（1-1-1818）等式移项得：）等式移项得：）等式移项得：）等式移项得：（1-18）第第1章章 线性规划与单纯形法线性规划与单纯形法令令令令x xm+1m+1=x=xm+2m+2=x xn n=0=0，由（，由（，由（，由（1-191-19）可得：）可得：）可得：）可得：x xi i=b=bi i（i=1,2,mi=1,2,m）又因又因又因又因b bi i00，所以得到一个初始基可行解，所以得到一个初始基可行解，所以得到一个初始基可行解，所以得到一个初始基可行解（1-19）第第1章章 线性规划与单纯形法线性规划与单纯形法（3 3）对于所有约束条件是）对于所有约束条件是）对于所有约束条件是）对于所有约束条件是“”“”形式的不等式及等式形式的不等式及等式形式的不等式及等式形式的不等式及等式约束情况，化为标准型时候如果不存在单位矩阵，就采用约束情况，化为标准型时候如果不存在单位矩阵，就采用约束情况，化为标准型时候如果不存在单位矩阵，就采用约束情况，化为标准型时候如果不存在单位矩阵，就采用人造基方法。人造基方法。人造基方法。人造基方法。1.2.3 1.2.3 最优解的检验和解的判断最优解的检验和解的判断最优解的检验和解的判断最优解的检验和解的判断线性规划问题的解可能出现唯一最优解、无穷多最优解、线性规划问题的解可能出现唯一最优解、无穷多最优解、线性规划问题的解可能出现唯一最优解、无穷多最优解、线性规划问题的解可能出现唯一最优解、无穷多最优解、无界解和无可行解情况，因此需要建立对解的判别准则。无界解和无可行解情况，因此需要建立对解的判别准则。无界解和无可行解情况，因此需要建立对解的判别准则。无界解和无可行解情况，因此需要建立对解的判别准则。一般情况下，经过迭代后（一般情况下，经过迭代后（一般情况下，经过迭代后（一般情况下，经过迭代后（1-191-19）变成）变成）变成）变成将（将（将（将（1-201-20）代入目标函数（）代入目标函数（）代入目标函数（）代入目标函数（1-161-16）后整理得）后整理得）后整理得）后整理得（1-20）（1-21）第第1章章 线性规划与单纯形法线性规划与单纯形法令令令令于是于是于是于是再令再令再令再令则则则则（1-22）（1-23）第第1章章 线性规划与单纯形法线性规划与单纯形法（1 1）最优解判断定理：若）最优解判断定理：若）最优解判断定理：若）最优解判断定理：若为对应于基为对应于基为对应于基为对应于基B B的一个基可行解，且对于一切的一个基可行解，且对于一切的一个基可行解，且对于一切的一个基可行解，且对于一切j=m+1,nj=m+1,n有有有有 j j00，则，则，则，则X X(0)(0)为最优解。称为最优解。称为最优解。称为最优解。称 j j为检验数为检验数为检验数为检验数。（2 2）无穷多最优解的判别定理：若）无穷多最优解的判别定理：若）无穷多最优解的判别定理：若）无穷多最优解的判别定理：若为一基可行解，且对于一切为一基可行解，且对于一切为一基可行解，且对于一切为一基可行解，且对于一切j=m+1,nj=m+1,n，有，有，有，有 j j00，又存在某，又存在某，又存在某，又存在某个非基变量的检验数个非基变量的检验数个非基变量的检验数个非基变量的检验数 m+km+k=0=0，则线性规划问题有无穷多最，则线性规划问题有无穷多最，则线性规划问题有无穷多最，则线性规划问题有无穷多最优解。优解。优解。优解。（3 3）无界解判别定理：