运筹学 第3版 课件 02 线性规划原理与解法

第2章线性规划原理与解法主要内容§2-1线性规划求解原理§2-2单纯形方法§2-3人工变量及其处理§2-4单纯形法的矩阵表示形式§2-5

改进单纯形法（选学）§2-1线性规划求解原理一、举例说明二、一般线性规划问题单纯形法求解原理定理：若线性规划问题有最优解，一定存在一个基可行解是最优解。求解思路：从问题的某个基可行解开始，判断其是否最优，若是，则停止；若不是则以此解为基础转换到更好的一个基可行解。如此循环直到找到最优解。步骤1寻找初始基可行解从约束条件的系数矩阵中可以容易地找到一个基：将模型约束条件变换形式为令非基变量为0，则即：为初始基可行解，（2-1）将式（2-1）带入目标函数为对应的XB

为一、举例说明【例2-1】因为x2的系数大于x1的系数，所以选择x2作为进基变量，同时要找出一个出基变量初始基可行解对应的的目标函数为可以将非基变量x1或x2换入基变量中。因为其中非基变量的系数大于0，所以X(0)不是最优解。步骤2判优（例）步骤3基变换（1/4）（1）所有非基变量为0；（2）所有变量均为非负；（3）基变量个数保持不变。式（2-1）中x2为进基变量，x1仍为非基变量，所以，x1=0（满足基变换的第一个要求）基变换过程中，x3,x4,x5均应≥0（满足基变换的第二个要求），根据式（2-1）计算x2的变化范围，得到【基变换要求】（2-1）为了保证基变量个数仍为3个（满足基变换要求的第三个要求），必须有此时，（2-2）（2-3）x2进基，x5出基，式（2-1）移项后得到式（2-2）将式（2-3）代入目标函数maxz=3x1

+4x2，得于是得到新基B1和基变量新的基可行解为步骤3基变换（2/4）利用高斯消去法将式（2-2）左边系数变换为单位矩阵，得到式（2-3）因z(1)=12+3x1-x5中，非基变量x1的系数仍然大于0，以x1为进基变量，继续进行基变换第2次基变换后，得到的基、基可行解、目标函数和z值分别为步骤3基变换（3/4）因z(2)中，非基变量x5的系数仍然大于0，

以x5为进基变量，继续进行基变换第3次基变换后，得到的基、基可行解、目标函数和z值分别为因z(3)中，非基变量系数均小于等于0，此时得到最优解。最优解为:上述求解过程与图解法之间的对应关系2134567812340Q1Q2Q3Q4①③②步骤3基变换（4/4）二、一般线性规划问题单纯形法的求解原理由以上分析可以得出线性规划模型的求解步骤1.确定初始基可行解

2.最优性检验与解的判别3.基变换◆当所有约束条件都是“≤”型的不等式时：◆当某些约束条件都是“≥”型的不等式及等式约束情况时（下一节会有例子）：对大于等于约束，减去一个非负的剩余变量后，再加上一个非负的人工变量；对等式约束直接加上一个非负的人工变量。

松弛变量和人工变量的系数列向量就构成了一个初始可行基。通过化标准型——加上松弛变量，松弛变量对应的系数列向量就构成了一个初始可行基。

1.确定初始基可行解（1/2）则可得初始基可行解

不失一般性，令初始可行基为B=(P1,P2,…,Pm)，将模型约束条件进行下面变换：所有基变量列于等式左边，常数和非基变量列于等式右边（2-4）……1.确定初始基可行解（2/2）由式（2-4）知，基变量＝常数－，由此，基变量可以表示为（2-5）将式（2-5）代入目标函数

得

称为检验数2.最优性检验与解的判别（1/3）（2）无穷多最优解判定定理：对于一个基可行解，如果其所有非基变量检验数σj≤0，j=m+1,…n，同时又存在某个σm+k=0，则该线性规划问题有无穷多最优解。线性规划问题解的三条判定定理（针对标准型而言）由上面两个定理可知，线性规划问题唯一最优解的判定：对于一个基可行解，如果其所有非基变量的检验数σj＜0，则称该解有唯一最优解。（1）最优解判定定理：对于一个基可行解，如果其所有非基变量的检验数σj≤0，则称该解为最优解。2.最优性检验与解的判别（2/3）2.最优性检验与解的判别（3/3）

【举例说明】下面模型有初始基可行解X=(0,0,8,16,12)T，因为非基变量x1和x2的检验数大于0，所以，确定x2为进基变量，保持x1为非基变量（x1=0），请确定出基变量。x2≥－3满足所有变量非负，但x2=－3时才能使x5等于0，与x2非负矛盾，故无法找到出基变量。该问题有解，但无法找到最优解，所以为无界解。3.基变换——确定进基变量当初始可行解不是最优解时，要从非基变量中确定一个进基变量，从基变量中确定一个出基变量，得到一个新的基可行解。

【确定进基变量】当存在多个时，即xk

为进基变量，为使目标函数增长较快，一般选

但不是必须的。原因：按上述原则，本节例必须经过三步迭代才能得到最优解。如果不采用上述原则，经过两步迭代就可以得到最优解。2134567812340Q1Q2Q3Q4①③②借助例【2-1】来寻找规律则x5=0，确定x5为出基变量为了求得新的基可行解，在保证xk=θ和xl=0的前提下，通过高斯消去法得到新的可行基和基可行解。

最小比值规则进基变量取值为θ，出基变量为xl实际上就是右端常数和进基变量系数的比值中取最小值（注意：进基变量的系数必须为正数，或者说分母必须为正）说明：出基变量xl代表第l行的变量出基3.基变换——确定出基变量x2为进基变量※最小比值规则是为了保证所有变量非负（1）所有非基变量为0；（2）所有变量均为非负；（3）基变量个数保持不变。式（2-1）中x2为进基变量，x1仍为非基变量，所以，x1=0（满足基变换的第一个要求）基变换过程中，x3,x4,x5均应≥0（满足基变换的第二个要求），根据式（2-1）计算x2的变化范围，得到【基变换要求】（2-1）单纯形法原理小结1、确定初始基可行解实质是构造单位矩阵2、解的最优性的判断利用目标函数中非基变量的系数来判定三个判优定理3、基变换（进基和出基变量的确定，高斯消去法）进基变量（求极大值时）：非基变量检验数σj

>0时，一般取最大的检验数对应的变量为进基变量出基变量：按最小比值规则（θ）确定（比值θ非负，aik’正数）§2-2单纯形方法一、构造单纯形表

二、计算步骤

一、构造单纯形表最后一行是检验数行XB列填入基变量列填入基变量的价值系数列填入约束方程右端的常数行填入目标函数中各变量的价值系数列是在进基变量确定后，按规则计算后填入一、构造单纯形表单纯形法原理小结1、确定初始基可行解实质是构造单位矩阵2、解的最优性的判断利用目标函数中非基变量的系数来判定三个判优定理3、基变换（进基和出基变量的确定，高斯消去法）进基变量（求极大值时）：非基变量检验数σj

>0时，一般取最大的检验数对应的变量为进基变量出基变量：按最小比值规则（θ）确定（比值θ非负，aik’正数）一、构造单纯形表【例2－2】用单纯形法计算例1-1的最优解。34000816121210004001400104－300008161220420[4]340004分母大于0x2进基x5出基二、计算步骤3400081612121000[4]001400104－30000340001200430400-2-1/402000-301/218300-10103001/4164001001210-1/224－101000-410100－412283-1/221/41/230411/2-200401/400140-1/81/21023最优解为：2163140[1]40283-1/221/4-1/2[2]1/4最优值为：分母大于0分母大于0§2-3人工变量及其处理一、大M法二、两阶段法

当出现“≥”或“＝”的约束条件时，通过化标准型不能直接得到单位矩阵，初始基可行解也无法通过单位矩阵形成的基得到。如例2-3。【例2－3】求解下面线性规划模型化标准型一、大M法(1/5)一、大M法(2/5)构造辅助线性规划模型※约束条件为“≥”时：－剩余变量+人工变量※约束条件为“＝”时：+人工变量※目标函数中，人工变量系数：求max时，为－M；求min时，为＋M。极大值模型极小值模型1-2110001131-4120-110-2010001-31100MM113/210MM113112112[1]-3+6M1-M1-3M0M001-3M利用单纯形法求解利用大M法建立的极小值辅助线性规划模型

一、大M法(3/5)-11－M00M03M－110-21000101010-11-20-2310100-10M1－1－1－M01101010-11-2031201-22-50-2110001-10001M－1M＋14－－14001/3-2/32/3-5/301100-11-209012/3-4/34/3-7/3-3110001/31/3M－1/3M－2/3-2-2[1]010111211-1[3]0-2所以最优解为：目标函数值：

1-2110001131-4120-110-2010001-31100MM113/210MM113112112[1]-3+6M1-M1-3M0M001-3M线性规划模型辅助线性规划模型线性规划模型无可行解的判定标准含有等式约束或大于等于约束的线性规划模型，采用大M法求解，若辅助线性规划模型的最终表中，基变量中仍然含有人工变量，则原线性规划模型无可行解。一、大M法(5/5)第一阶段：判断原问题是否有可行解（借助一个辅助线性规划问题）。

（1）构造辅助线性规划模型：约束条件标准化的基础上引入人工变量，“目标函数仅含人工变量”且“要求目标实现最小化”。

（2）用单纯形法求解上述模型，若目标＝0，原问题有可行解，进入第二阶段，否则，原问题无可行解。

第二阶段：求原问题的最优解。将第一阶段计算得到的最终表除去人工变量，填入原问题目标函数的系数，进行迭代，求最优解。

二、两阶段法第一阶段目标函数为0，原问题有解，进入第二阶段1、第一阶段00000110111-2110001113-4120-1103/211-201000116-1-3010010-21000101010-2310100-10100-100103－1－0-11-2-110100-11-2031201-22-50-21100010000011000113112[1]1011-210-2[1]00-311003001-20100-1-201001211011-100014－－-114001/3-2/301100-109012/3-4/3-3110001/31/3-2所以最优解为：目标函数值：121130-2[3]0-22、第二阶段将第一阶段计算得到的最终表除去人工变量x6和x7，将原问题目标函数minz=-3x1+x2+x3的系数带入单纯形表，继续求解。两阶段法的注意事项第一阶段：目标函数仅含人工变量，且目标函数求极小值，无论原问题求极大还是极小。第二阶段：求极大值还是极小值由原问题来确定。最优性检验与解的判别—总结求解极大值的情况求解极小值的情况最优性检验与解的判别（求解极大值的情况）（4）无可行解判定定理：对于一个含有等式约束或大于等于约束的线性规划问题，若（1）采用大M法求解，辅助线性规划模型最终表中人工变量仍为基变量；或（2）采用两阶段法求解，第一阶段目标函数不为零。则该问题无可行解。

最优性检验与解的判别（求解极小值的情况）（4）无可行解判定定理：对于一个含有等式约束或大于等于约束的线性规划问题，若（1）采用大M法求解，辅助线性规划模型最终表中人工变量仍为基变量；或（2）采用两阶段法求解，第一阶段目标函数不为零。则该问题无可行解。

第一阶段：判断原问题是否有可行解（借助一个辅助线性规划问题）。

（1）构造辅助线性规划模型：约束条件标准化的基础上引入人工变量，“目标函数仅含人工变量”且“要求目标实现最小化”。

（2）用单纯形法求解上述模型，若目标＝0，原问题有可行解，进入第二阶段，否则，原问题无可行解。

第二阶段：求原问题的最优解。将第一阶段计算得到的最终表除去人工变量，填入原问题目标函数的系数，进行迭代，求最优解。

思考：第一阶段的目标函数必须求极小值吗第一阶段：判断原问题是否有可行解（借助一个辅助线性规划问题）。

（1）构造辅助线性规划模型：约束条件标准化的基础上引入人工变量，“目标函数仅含人工变量”且“要求目标实现最小化”。

（2）用单纯形法求解上述模型，若目标＝0，原问题有可行解，进入第二阶段，否则，原问题无可行解。

第二阶段：求原问题的最优解。将第一阶段计算得到的最终表除去人工变量，填入原问题目标函数的系数，进行迭代，求最优解。

思考：为什么第一阶段的目标函数为0，原问题有可行解§2-4单纯形法的矩阵表示形式一、线性规划模型的矩阵描述二、单纯表的矩阵描述三、θ的矩阵表达形式四、例题对照说明+（2-6）AXIXSCX0XSb+一、线性规划模型的矩阵描述（1/3）NXNBXBbCNXNCBXB（2-7）（2-8）将式2-6变换为CX0XSAXIXSb（2-6）一、线性规划模型的矩阵描述（2/3）于是得到不同表示形式之间的对应关系（2-7）（2-8）决策变量松弛变量基变量非基变量一、线性规划模型的矩阵描述（3/3）（2-6）（2-7）（2-8）将式2-8移项上式左乘B-1

令XN=0，则基解为将式2-9代入式2-7（2-10）于是得到，非基变量的检验数为：基变量XB在式2-10中的检验数为0，可表示为：松弛变量Xs的检验数可表示为：于是得到决策变量和松弛变量表示的目标函数：决策变量X中的检验数可表示为：（2-9）二、单纯形表的矩阵描述（1/3）二、单纯形表的矩阵描述（2/3）

基变量的检验数松弛变量的检验数非基变量的检验数令非基变量等于0，则基变量为

令非基变量等于0，则目标函数值为

单纯形表中所有变量的系数矩阵均可由B-1左乘系数矩阵得到，可知，松弛变量的矩阵也可由B-1左乘单位矩阵I得到。

表头b当前表检验数I0

初始表BNbI（2-8）（2-10）（2-11）【结论】每个单纯形表中，松弛变量的系数矩阵对应的是该单纯形表中基矩阵（B）的逆矩阵（B-1）；【结论扩展】因为松弛变量在初始单纯形表中是单位矩阵，因此，可以引申为：初始单纯形表中单位矩阵所在的位置，就是以后各个单纯形表中基矩阵（B）的逆矩阵（B-1）所在的位置。二、单纯形表的矩阵描述（3/3）表头b初始表BNb当前表检验数I0

1I三、θ的矩阵表达形式假定进基变量为xk，根据θ规则用矩阵表示

指b列中的第i

个元素。

指经过迭代变换后的第k列系数向量的第i

个元素表头b初始表BNb当前表检验数I0

1I四、例题对照说明（1/8）【例2-4】以生产计划问题为例说明单纯形表的矩阵表示形式。说明：此处仅列出了初始表和求解过成的部分表格四、例题对照说明（2/8）cj34000CBXBbx1x2x3x4x50x38121000x416400100x512040010340000x321010-1/20x416400104x2301001/4123000-13x121010-1/20x4800-4124x2301001/41800-301/23x141001/400x5400-21/214x22011/2-1/802000-2-1/40最终表-31100MM1/32/3-5/301-22/34/3-7/3100010001【例2-5】以大M法求极小值的单纯形表为例说明单纯形法迭代过程。四、例题对照说明（3/8）最终表1/32/3-5/301-22/34/3-7/3最终表中基变量的系数列向量最终表中的基变量为x1、x2和x3，B和B-1分别为100010001四、例题对照说明（4/8）-3+6M1-M1-3M0M001-2110001131-4120-110-2010001-31100MM0MM初始表1/32/3-5/301-22/34/3-7/3最终表中的x5的系数列向量为100010001-2/3-1-4/3最终表中的右端常数b为419-3110001/31/3M－1/3M－2/3四、例题对照说明（5/8）最终表-3+6M1-M1-3M0M001-2110001131-4120-110-2010001-31100MM0MM初始表四、例题对照说明（6/8）最终表中的检验数的计算

100010001419-3110001/31/3M－1/3M－2/3最终表-3+6M1-M1-3M0M001-2110001131-4120-110-2010001-31100MM0MM初始表1/32/3-5/301-22/34/3-7/3-2/3-1-4/3四、例题对照说明（7/8）（1）同时计算所有非基变量检验数（2）只计算非基变量x4的检验数（3）同时计算非基变量x4、x5的检验数最终表中的

z的计算－31100MM100010001419-3110001/31/3M－1/3M－2/3四、例题对照说明（8/8）-21/32/3-5/301-22/34/3-7/3-2/3-1-4/3-3+6M1-M1-3M0M001-2110001131-4120-110-2010001-31100MM0MM初始表354000b8/32/3101/30014/3-4/305-2/31020/35/304-2/301-1/304-5/30015/418/41-10/41-6/415/414/41-2/41-12/4115/41已知某线性