线性规划及其应用线性规划求解方法

1第一页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法2重庆大学经济与工商管理学院肖智4、作用：线性规划理论的几何意义，并说明线性规划解的四种情况（唯一最优解、无穷最优解、有可行解而无最优解、无可行解）。5、举例说明。三、单纯形法

1、单纯形法的概述1）适用范围：线性规划标准形问题。2）基本原理：（1）目标：使Z=CX最大，在AX=b,X≥0条件下；（2）理论：线性规划基本理论（3）结论：第二页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法3重庆大学经济与工商管理学院肖智

（3.3-1)

(3.3-2)

(3.3-3)第三页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法4重庆大学经济与工商管理学院肖智要使Z=CX达到最大，由(3.3-3)知只需去寻找一恰当的基B使得(称为检验数向量)3）基本思路：基于线性规划问题的标准形，先确定一初始基可行解X0，并由此开始在保证目标函数值不下降的情况下逐次施行从一个基可行解到另一个基可行解的转换。如此进行下去，直到取得最优解或判明问题无最优解为止。4）基本步骤：（1）对一般线性规划问题标准化；（2）确定一初始基可行解X0；（3）若所有检验数σj≤0（σj为的第j个分量）,则X0是线性规划问题的最优解，停止计算；否则转(4)第四页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法5重庆大学经济与工商管理学院肖智（4）若存在σt＜0所对应的系数列向量pt≤O，则线性规划问题无最优解，停止计算；否则转（5）。（5）按最大检验数规则：确定进基变量xk和主列pk；再按最小比值规则：确定出基变量xl和主元alk。（6）以主元alk进行换基迭代得一新的基可行解x1,将x1记为x0返回到（3）。5）基本工具：计算机或单纯形表。第五页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法6重庆大学经济与工商管理学院肖智2、单纯形法应用举例：

(3.3-4)第六页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法7重庆大学经济与工商管理学院肖智第一步标准化

(3.3-5)

第二步建立初始单纯形表第七页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法8重庆大学经济与工商管理学院肖智

目标函数系数2510000资源拥有量

决策变量x1x2x3x4x50(x3的目标系数）x30.60.5100120000(x4的目标系数）x40.40.101040000(x5的目标系数）x50.00.40016000最优性检验数25100000表3.3-1第八页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法9重庆大学经济与工商管理学院肖智此表对应一个可行方案和该方案最优检验结果。可行方案：x1=x2=0,x3=12000,x4=4000,x5=6000.最优性检验结果：检验值全部非负（若全部非正，则可行方案是最优方案）第九页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法10重庆大学经济与工商管理学院肖智

目标函数系数2510000可行方案决策变量x1x2x3x4x50x300.351-1.50600025x110.2502.50100000x500.40016000最优性检验数03.750-62.50250000第三步：改进当前可行方案，计算下一张单纯形表。表3.3-2第十页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法11重庆大学经济与工商管理学院肖智

目标函数系数2510000可行方案决策变量x1x2x3x4x50x3001-1.5-0.87575025x11002.5-0.625625010x201002.515000最优性检验数000-62.5-9.375306250第四步：改进当前可行方案，计算下一张单纯形表。表3.3-3第十一页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法12重庆大学经济与工商管理学院肖智最优性检验结果：检验值全部为非正

最优方案:

x1=6250(件),x2=15000(件),

x3=x4=x5=0(件).

最大效益为:306250(美元)

第十二页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法13重庆大学经济与工商管理学院肖智3、初始基可行解的求法：

在前边的讨论中我们总假定当问题化为标准型后，系数矩阵中有一个全部由松弛变量列向量构成的单位矩阵，如果右边项系数全都大于或等于零，只要取该单位矩阵为初始基就可以得到一个初始基本可行解。但在一般情况下，化为标准型的矩阵中不一定含有单位短阵。例如，当线性规划问题有等式约束时就无法引入松弛变量；如果约束的右边项系数出现负值时也无法直接得到一个初始可行解。在这种情况下，可引入人工变量来构造一个初始基。

具体做法是：

1)将所有约束的右边项值调整为大于或等于零：对右边项第十三页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法14重庆大学经济与工商管理学院肖智为负的约束，约束两边同乘一l。

2)对小于等于型约束(≤)，仍引入一个松弛变量。

3)对大于等于型约束(≥)，引入一个剩余变量和一个人工变

量。

4)对等于型约束(＝)，引入一个人工变量。

通过以上调整后，每一个约束或者有一个松弛变量，或者有一个人工变量，它们构成的单位矩阵可以作为一个初始基，可见，调整后的问题一定有可行解。然而，对原问题来说，新引入的人工变量是多余的，如果人工变量在最后的结果中取正值，则表明该解不满足原问题约束条件。因此，尽管引入人工变量后我们可以很容易找到一个初始第十四页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法15重庆大学经济与工商管理学院肖智基，然而该基不一定是原问题的可行基，只有当人工变量都变为非基变量或都为零时，引入人工变量的问题才与原问题等价。因此，应通过某种方法把所有的人工变量从基中赶出去才能得到原问题的一个可行基。常用的方法有以下两种：

（1）大M法

大M法实质上是一种罚函数法，它在目标函数中赋予人工变量一个很大的负系数(一M)。由于人工变量对目标函数

有很大的负影响，单纯形方法的寻优机制会自动将人工变量赶到基外，从而找到一个原问题的可行基。

用单纯形表计算时，可直接在目标函数中使用M参数，第十五页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法16重庆大学经济与工商管理学院肖智通过人的计算和判断进行单纯形迭代。用计算机计算时，由于计算机无法直接使用参数计算，M必须赋予一个较大的值，并视求解的情况对M值进行调整。如果给定M后，计算所得的最优基已不含人工变量，该解即为最优可行解。当给定的M足够大时，最优解中仍含有人工变量，则可判断原问题无可行解。下面举例说明如何使用大M法。

例：用大M法求解下列线性规划问题：

(3.3-6)第十六页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法17重庆大学经济与工商管理学院肖智具体解题步骤见下表3.3-4cj2300-M-MbxBCBx1x2x3x4x5x6x3021100016x5-M130-11020x6-M11000110σj2+2M3+4M0-M00-30Mx305/3011/3-1/3028/3x231/310-1/31/3020/3x6-M2/3001/3-1/3110/3σj1+2M/3001+M/3-1-4M/3020-10M/3第十七页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法18重庆大学经济与工商管理学院肖智表3.3-4续cj2300-M-MbxBCBx1x2x3x4x5x6x30001-1/21/2-5/21x23010-1/21/2-1/25x121001/2-1/23/25σj0001/2-1/2-M-3/2-M25x3010100-16x2311000110x402001-1310σj-1000-M-3-M30第十八页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法19重庆大学经济与工商管理学院肖智该问题的最优解为：X*=(0，10)T；

最优值为:Z*=30

与计算机计算结果相同。

大M法的优点是方法比较直观，易于理解和手工计算，缺点是当使用计算机计算时，由于M值较大容易引起数值计算上的困难，所以几乎所有商业线性规划软件都不使用大M法而使用另外一种方法—两阶段法。

（2）两阶段法

顾名思义，两阶段法是将线性规划求解过程分为两个阶段。第一阶段只是寻找一个初始可行基，第二阶段再按正常方法寻找最优解。第十九页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法20重庆大学经济与工商管理学院肖智第一阶段：在原问题中引入人工变量并找到一个初始基。另构造一个新的求极小值的目标函数，该目标函数除人工变量的系数为1以外，其余变量的目标函数系数都为零。求解该线性规划问题，在不退化的前提下，如果得到的最优解值为零，表明所有的人工变量已经不在基中。第一阶段的最优解即是原问题的一个基可行解。

第二阶段：将原目标函数换回，以第一阶段得到的可行基为初始基进行迭代，直到找到最优基为止。在第二阶段的迭代中可以删去所有人工变量，保留它们只会增加不必要的计算。下面举例说明两阶段法求解过程。第二十页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法21重庆大学经济与工商管理学院肖智例：用两阶段法求解下列线性规划问题：

(3.3-7)

第一阶段模型：

(3.3-8)

第二十一页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法22重庆大学经济与工商管理学院肖智具体解题步骤见下表3.3-5cj0000-1-1bxBCBx1x2x3x4x5x6x3021100016x5-1130-11020x6-111000110σj240-100-30x305/3011/3-1/3028/3x201/310-1/31/3020/3x6-12/3001/3-1/3110/3σj2/3001/3-4/30-10/3第二十二页，共二十六页，编辑于2023年，星期三§3.3线性规划求解方法23重庆大学经济与工商管理学院肖智表3.3-5续

第二阶段模型：

(3.3-9)