线性规划线性规划问题单纯形法

线性规划线性规划问题单纯形法第一页，共一百一十二页，2022年，8月28日1第一讲第二章线性规划及图解法第二页，共一百一十二页，2022年，8月28日问题的提出解决有限资源在有竞争的使用方向中如何进行最佳分配。线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自1947年旦茨基（G.B.Dantzig）提出了一般线性规划问题求解的方法——单纯形法（simplexmethod）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界500家最大的企业中，有85%的企业都曾使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。线性规划LinearProgramming（LP）第三页，共一百一十二页，2022年，8月28日本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本概念和图解方法。线性规划问题是什么样的一类问题呢？请看案例线性规划LinearProgramming（LP）第四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。案例河流污染治理规划问题第五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案例河流污染治理规划问题第六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。今日认识未为晚，吾辈齐心治环境;线性规划大有用，定让江水绿如蓝。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案例河流污染治理规划问题第七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）今日认识未为晚，吾辈齐心治环境;线性规划大有用，定让江水绿如蓝。曾几何时长江水，哺育华夏代代人;谁知后代疏珍惜，清清江水黑如泥。工厂2工厂3工厂1工厂4工厂5工厂6工厂9工厂8工厂7案例河流污染治理规划问题第八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）案例河流污染治理规划问题背景资料:长江流域某区域内有9化工厂，各厂每月产生的工业污水量如表-1，流经各化工厂的河流流量如表-2，各化工厂治理工业污水的成本如表-3。上游厂排放的污水流到相邻下游厂以前，有20%可自然净化。根据环保标准河流中此种工业污水的含量不应超过0.2%。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使9化工厂治理工业污水的总费用最少。第九页，共一百一十二页，2022年，8月28日背景资料:线性规划LinearProgramming（LP）化工厂11.2化工厂42化工厂72化工厂21化工厂51化工厂80.8化工厂33化工厂61化工厂91.5表-1污水产生量单位：万m3表-2流经各化工厂的河流流量单位：万m3表-3治理工业污水的成本单位：百万元/万m3化工厂1500化工厂41200化工厂71200化工厂2300化工厂5600化工厂8200化工厂31800化工厂6400化工厂9700化工厂13化工厂44化工厂71化工厂25化工厂55化工厂82化工厂32化工厂66化工厂93第十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）194582637问题分析：区域污染治理的决策——各个化工厂应处理的工业污水量（或应排放的工业污水量）。区域污染治理的约束——即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。区域污染治理的目标——总治理成本最少。第十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）194582637模型描述：设第i个化工厂应处理的工业污水量为Xi万m3，则根据问题描述的情况以化工厂1、2、…、9加以分析则可得如下近似关系式对化工厂2应有（1-X2）/300≦0.2%对化工厂8应有（0.8-X8）/200≦0.2%对化工厂1应有｛（1.2-X1）+0.8（1-X2）+（0.8-X8）｝/500≦0.2%第十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）194582637对化工厂9应有——（1.5-X9）/700≦0.2%对化工厂7应有——

（2-X7）+0.8（1.5-X9）/1200≦0.2%……此外显然还应有Xi≧0（i=1，2，3…8，9）综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量Xi应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为污水治理的约束条件。第十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）194582637另一方面污水治理的总成本可表示为Z（单位：百万元）Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9而决策者的目标是：确定满足约束条件的Xi使得Z取得最小值。将上述分析归纳后即可得如下数学符合模型：第十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）河流污染治理规划问题数学模型（整理之后）194582637MinZ=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9X2≧0.4X8≧1.6X1+0.8X2+0.8X8≧4.4X9≧0.1X7+0.8X9≧0.8X4+0.8X7+0.64X9≧2.16X6≧0.2X5+0.8X6≧0.6X3+0.8X4+0.8X5+0.64X6+0.64X7+5.12X9≧9.4Xi≧0（i=1，2，3，4，5，6，7，8，9）s.t.第十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）线性规划模型——

LinearProgrammingModel或LinearOptimizationModel用线性规划方法解决实际经济与管理问题的第一步是分析建立能够完整描述和反映实际问题的线性规划模型。第十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）通常建立LP模型有以下几个基本步骤：确定决策变量：决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。确定目标函数：目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据目标函数的实质确定优化方向，一般可为最大化（max）或最小化（min）。第十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）通常建立LP模型有以下几个步骤：确定约束方程：一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。变量取值限制：一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即Xj≥0，但要注意也存在例外的情形。第十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）线性规划的一般形式:max（或min）z=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn（≤=≥）b1a21x1+a22x2+…+a2nxn

（≤=≥）b2s.t.………………am1x1+am2x2+…+amnxn（≤=≥）bm

xj≥0（j=1，2…n）第十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）线性规划问题的标准形式1、目标函数极大化——“max”2、等式约束条件——“=”且右端常数bi非负3、变量非负——“xj≥0”maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）第二十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）化标准形式的一般步骤目标函数极小化“极大化”约束条件的右端项bi≤0“bi≥0”约束条件为不等式≤或≥“=”取值无约束（自由）变量“非负变量”取值非正变量“非负变量”线性规划问题的标准形式的作用——为单纯形法求解作准备！第二十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）线性规划问题的求解：（图解）如何求解一般的线性规划呢？下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。第二十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念例1（page11）maxz=2x1+x25x2

≤15s.t.6x1+2x2

≤24x1+x2

≤5x1，x2

≥0第二十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念maxz=2x1+x25x2≤15s.t.6x1+2x2≤24x1+x2≤5x1，x2≥0唯一最优解X=（9/2，3/2）第二十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念例maxZ=2X1+X2

X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0第二十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念maxZ=2X1+X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X2

20=2X1+X2

17.2=2X1+X2

11=2X1+X2

Lo：0=2X1+X2

（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域第二十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2

maxZminZ（3.8，4）34.2=3X1+5.7X2

绿色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域第二十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2

maxZminZ8=5X1+4X2

43=5X1+4X2

（0，2）可行域此点是唯一最优解第二十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念minZ=5X1+4X2x1x2oD可行域第二十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2oD可行域maxZminZ最优解目标值Z趋于无穷第三十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念maxZ=5X1+4X2x1x2o可行解域为空第三十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）基本概念图解法的启示线性规划问题解的可能情况a.唯一最优解b.无穷多最优解c.无解（没有有界最优解，无可行解）若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。第三十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法

单纯形方法是于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。第三十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法给定线性规划问题（标准形式）maxz=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2s.t.……………am1x1+am2x2+…+amnxn

=bmxj≥0（j=1，2…n）第三十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法一、线性规划问题的解的概念

可行解最优解基基解（基本解）基可行解可行基第三十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法二、凸集及其顶点凸集顶点（极点）凸集凹集第三十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）12345678基解（可行）基解（不可行）第三十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法三、线性规划基本定理基本定理1

线性规划所有可行解组成的集合S={X|AX=b，X≥0}是凸集。基本定理2

X是线性规划问题的基本可行解的充要条件为是X是凸集S={X|AX=b，X≥0}的极点。基本定理3

给定线性规划问题，A是秩为m的mn矩阵，

（i）若线性规划问题存在可行解，则必存在基本可行解（ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解。第三十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法单纯形法迭代原理及其思路单纯形法的初步讨论例1.8求解LP问题

化为标准型MaxZ=50X1+30X2s.t.4X1+3X2≤

1202X1+X2≤50X1，X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2+X4

=50X1，X2，X3，X4

≥0（1.18）第三十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法此线性规划问题转化为了一个含有四个变量的标准形线性规划问题，X3，X4为松弛变量。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下第四十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法确定初始基可行解：通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此取X3，X4为基变量；X1，X2为非基变量。则（1.18）可变为：

Max

Z

=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）X1，X2，X3，X4≥0第四十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法典式（1.19）或（1.18）称为关于基的典式——1、等式约束条件中显含基可行解2、目标函数中不含基变量MaxZ=50X1+30X2s.t.4X1+3X2+X3

=

1202X1+X2+X4

=50(1.18)X1，X2，X3，X4≥0MaxZ

=50X1+30X2s.t.X3

=120-4X1-3X2

X4=50-2X1-X2（1.19）X1，X2，X3，X4≥0第四十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法在典式（1.19）中令：X1=X2

=0，我们得到一个基本可行解

X1=（X1，X2，X3，X4）T=（0，0，120，50）T

，其对应的目标函数值Z1=50X1+30X2=0第四十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法最优性检验：基本可行解X1是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式（1.19）的目标函数中，非基变量X1，X2前的系数都为正，而此时的X1，X2均取零值，表明只要增加其值，则目标函数值有增加的可能。因此，将目标函数中系数为正的某一非基变量与某一基变量地位对换。第四十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法换基迭代：进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足：新的解仍是基本可行解；目标函数值将得到改善。第四十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法选择入基变量：

由于在目标函数Z1

=50X1+30X2中X1，X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。选择出基变量：

X1入基后，其值从零增加并由于约束条件的原因会引起其他变量的变化。由典式（1.19）以及变量必须取正值（可行）的条件，我们可以得到下列不等式关系：X3=120-4X1-3X2≥0X4=50-2X1-X2≥0第四十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法

因为迭代后X2仍为非基变量（仍会令其取值为零），则上式可简化为：120-4X1≥0，且50-2X1≥0，由此可以看出，虽然我们希望X1入基后取正值，取值越大目标值增加越大，但是X1又得受到以上约束（保证其可行）。显然，当取X1=min（120/4，50/2）=25时，才能使上述不等式成立，且此时恰使基变量X4变为零，这正好满足非基变量必须取值零的条件，所以可令X4出基，这样，新的基变量变为X3，X1，而X2，X4成了非基变量，则第四十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法约束方程变为：4X1+X3=120-3X22X1=50-X2-X4化简后得：新的典式方程X3=20-X2+2X4X1=25-0.5X2-0.5X4第四十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法代入目标函数可得：Z2

=1250+5X2-25X4

令非基变量X2=X4=0，即可得一个新的基本可行解X2=（25，0，20，0）T，其对应的目标函数值Z2

=1250，并完成了第一次迭代。由于目标函数Z2=1250+5X2-25X4中X2的系数仍为正，该解X2仍不是最优解。重复上述迭代过程得到：X2入基，X3出基，则新的典式方程变为：X1=15+0.5X3

-1.5X4X2=20-X3+2X4

Z3

=1350-5X3-15X4第四十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法第三个基本可行解X3

=（15，20，0，0）T，其对应的目标函数值Z3

=1350。此时松弛变量都是非基变量（取值为零），这表明资源已用尽；并且目标函数值Z3

=1350-5X3-15X4中非基变量X3，X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。第五十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法小结：

单纯形法是这样一种迭代算法——如下图…当Zk

中非基变量的系数的系数全为负值时，这时的基本可行解Xk

即是线性规划问题的最优解，迭代结束。X1Z1保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增X2X3...XkZ2Z3...Zk当Zk

中非基变量的系数的系数全为负值时，这时的基本可行解Xk

即是线性规划问题的最优解，迭代结束。第五十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形表对于给定的线性规划问题：maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2s.t.………am1x1+am2x2+…+amnxn≤bmxj≥0（j=1，2…n）对此问题添加m个松弛变量后，可得下面线性规划问题并且是典式的形式。第五十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形表线性规划的典式maxZ=c1x1

+c2x2+…+cnxna11x1+a12x2+…+a1nxn+xn+1=b1a21x1+a22x2+…+a2nxn+

xn+2=b2s.t.…am1x1+am2x2+…+amnxn+

xn+m=bmxj≥0（j=1，2…n，n+1，n+2，…n+m）第五十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形表：将上面典式中各变量及系数填写在一张表格中就形成下面的单纯形表cj

c1c2…cncn+1cn+2…cn+mCB基解

x1x2…xnxn+1xn+2…xn+m0000xn+1xn+2…xn+m

b1

b2…

bma11a12…a1n1a21a22…a2n1……………am1am2…amn112…mj=cj–zj

c1c2…cn00…0j=cj–zj

1

2…

nn+1

n+2…n+m第五十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形表：

上面的单纯形表还可以表示成矩阵的形式基解X

XSXSbAIj

C

0基解XB

XN

XSXSbBNIj

CB

CN

0或第五十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法由单纯形表进行迭代步骤：选择Xj入基：当j行中

j=max{

i∣

i0}选择Xi出基：当i

=min{bi/aij∣aij0}换基迭代：当确定了入基变量Xj、出基变量Xi后，以aij作为主元对单纯形表进行取主运算，取主运算——即采用初等行变换将主元aij所在列，除将aii变换为1而外，该列中的其余元素都变换为0。注意这种变换只能采用初等行变换!第五十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法最优解检验：当迭代进行至某一步时，j行中所有检验数均小于等于零，则迭代结束。表中当前所指基本可行解即为最优解。当迭代进行至某一步时，j行中所有检验数均小于等于零，且此时至少有一个非基变量所对应的检验数k等于零，则原线性规划问题有无穷多个最优解。当迭代进行至某一步时，j行中至少有一个检验数k大于零，且该检验数对应的列中a1k，a2k，…amk，均小于等于零，则原线性规划问题最优解无界（maxZ→+∞）。第五十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形方法的矩阵描述：设线性规划问题maxZ=CXmaxZ=CX+0XS

s.t.AX≤bs.t.AX+IXS=b（I式）

X≥0X，XS≥0其中b≥0，I是mm单位矩阵。对上面（I式）经过迭代，并设最终的最优基矩阵为B（不妨设B

为A的首m列，则将（I式）改写后有第五十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形方法的矩阵描述：maxZ=CBXB+CNXN+0XS

s.t.BXB+NXN+IXS=bXB，XN，XS≥0

maxZ=CBB-1+（CN-CBB-1）XN-

CBB-1XS

s.t.XB+B-1NXN+B-1XS=B-1bXB，XN，XS≥0

B式中最优目标函数值Z*=CBB

-1，检验数CN-CBB

-1≤0

，-

CBB

-1≤0单纯形方法迭代（I式）（B式）第五十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形方法的矩阵描述：基解XB

XN

XSXSb

BNIj

CB

CN

0基解XB

XN

XSXBB-1b

IB-1NB-1j

0

CN-CBB

–1N-

CBB

-1对应I式的单纯形表——

I

表对应B

式的单纯形表——B

表迭代第六十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形表计算步骤举例给定线性规划问题maxz=50X1+30X2s.t.4X1+3X2≤

1202X1+X2

≤50X1，X2

≥0maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4

≥0第六十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形表计算步骤举例maxz=50X1+30X2s.t.4X1+3X2+X3=

1202X1+X2+X4=50X1，X2，X3，X4≥0基XB解B-1bX1X2X3X4X31204310X4502101检验数j

5030002120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-15第六十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法的进一步讨论人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显然的基本可行解（如松弛变量作为基变量的一个初始基本可行解），这样我们就可以马上进入单纯形表的运算步骤。然而，并非所有问题标准化之后我们都可得到一个显然的初始基本可行解，这时就需要我们首先确定出一个基本可行解作为初始基本可行解。通常采用的是人工变量法来确定这样的初始基本可行解。这种情况下一般有两种方法：

大M法（罚因子法）两阶段法第六十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法的进一步讨论1、大M法（罚因子法）maxz=-3X1+X3

x1+x2+x3

≤4-2x1+x2–x3

≥13x2+x3=9x1，x2，x3

≥0LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥0第六十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）1、大M法LPMmaxz=-3x1+x3+0x4+0x5–Mx6–Mx7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-30100-M-M第六十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-3-2MM1-M0-M0-M基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-3-2M4M10-M00第六十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013检验数j-3-2M4M10-M00基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31检验数j-3+6M01+4M03M-4M0第六十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311检验数j-3+6M01+4M03M-4M0基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数j00301.5-1.5-M0.5-M第六十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）1、大M法基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/39X11102/301/2-1/21/63/2检验数j00301.5-1.5-M0.5-M基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X25/2-1/2100-1/41/41/4X33/23/20103/4-3/41/4检验数j-9/2000-3/43/4-M-1/4-M第六十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）采用大M法求解线性规划问题时可能出现的几种情况：当采用单纯形法求解LPM得到最优解时，基变量不含任何人工变量，则所得到的最优解就是原问题的最优解；当采用单纯形法求解LPM得到最优解时，基变量至少含有一个人工变量且非零，则原问题无可行解；当采用单纯形法求解LPM得到最优解时，基变量至少含有一个人工变量且人工变量都为零，则通过变换得到原问题最优解；第七十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法maxz=-3X1+X3

x1+x2+x3≤4-2x1+x2–x3≥13x2+x3=9x1，x2，x3≥0I阶段问题maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7

≥0第七十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法I阶段问题maxz=–x6–x7

x1+x2+x3+x4=4-2x1+x2–x3-x5+x6=13x2+x3+x7=9x1，x2，x3，x4，x5，x6，x7≥0基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j00000-1-1第七十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法——第I阶段基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j00000-1-1基XB解B-1bX1X2X3X4X5X6X7X441111000X61-21-10-110X790310001检验数j-2400-100第七十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法——第I阶段基XB解B-1bX1X2X3X4X5X6X7X4411110004X61-21-10-1101X7903100013检验数j-2400-100基XB解B-1bX1X2X3X4X5X6X7X4330211-10X21-21-10-110X7660403-31检验数j60403-40第七十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法——第I阶段基XB解B-1bX1X2X3X4X5X6X7X4330211-101X21-21-10-110X7660403-311检验数j60403-40基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数j00000-1-1第七十五页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法——第II阶段基XB解B-1bX1X2X3X4X5X6X7X400001-1/21/2-1/2X23011/30001/3X11102/301/2-1/21/6检验数j00000-1-1基XB解B-1bX1X2X3X4X5X400001-1/2X23011/300X11102/301/2检验数j00303/2-30100第七十六页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）2、两阶段法——第II阶段基XB解B-1bX1X2X3X4X5X400001-1/2X23011/3009X11102/301/23/2检验数j00303/2基XB解B-1bX1X2X3X4X5X400001-1/2X25/2-1/2100-1/4X33/23/20103/4检验数j-9/2000-3/4第七十七页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）单纯形法中的几个问题目标函数极小化时，解的最优判别：

j≥0退化：一个或几个基变量等于零，一个简单易行的避免退化的方法是1974年由勃兰德（Bland）提出的Bkand法则。无可行解的判别：在采用人工变量求解线性规划问题得到最优解时，如果基变量中仍含有非零人工变量，则原问题无可行解。第七十八页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）数据包络分析DEA（dateenvelopmentanalysis）引言一种基于线性规划的用于评价同类型组织（或项目）工作绩效相对有效性的特殊工具手段。这类组织例如学校、医院、银行的分支机构、超市的各个营业部等，各自具有相同的投入相同的产出。衡量这类组织之间的绩效高低，通常采用投入产出比这个指标，当各自的投入产出均可折算成同一单位计量时，容易计算出各自的投入产出比并按其大小进行绩效排序。但当被衡量的同类型组织有多项投入和多项产出，且不能折算成统一单位时，就无法算出投入产出比的数值，因而，需采用一种全新的方法进行绩效比较。这种方法就是二十世纪七十年代末产生的数据包络分析DEA。第七十九页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）数据包络分析DEA（dateenvelopmentanalysis）引言1978年，著名运筹学家、美国德克萨斯大学教授A.Charnes及W.W.Cooperh和E.Rhodes发表了一篇重要论文：“Measuringtheefficiencyofdecisionmakingunits”（决策单元的有效性度量），刊登在权威的“欧洲运筹学杂志”上。正式提出了运筹学的一个新领域：数据包络分析。其模型简称C2R模型。第八十页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）相对有效性评价问题例子

例1：硕士点教育质量评价某系统工程研究所对我国金属热处理专业的26个硕士点的教育质量，进行了有效性评价。评价采用的指标体系为：输入：导师人数；实验设备；图书资料；学生入学情况。输出：科研成果；论文篇数；学生毕业时的情况。使用DEA进行评价，结果基本合理。第八十一页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）相对有效性评价问题例子

例2：行风（行业作风）建设有效性评价本项目研究人员选定江苏省S市交通客运系统作为对象，包括7家交通客运汽车公司。评价采用的指标基础依据为：1、国际公交组织颁布的“十项基本考核指标”2、国内颁布的公交运营服务的“八项考核指标”。在此基础上，根据该系统实际情况，最终选定了输入指标4项，输出指标4项。分别是：第八十二页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）相对有效性评价问题例子输入指标：1、年末职工总熟（单位：人）；2、单位成本（单位：元/千人公里）；3、燃料单位消耗（单位：升/千人公里）；4、行车责任事故率（单位：次/千人公里）。输出指标：1、劳动生产率（单位：元/人）；2、行车准点率（%）；3、群众满意率（按问卷调查）（%）4、车辆服务合格率（包括：服务态度、服务措施、车辆设施等）（%）第八十三页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）相对有效性评价问题例子

收集到所需数据后，使用DEA方法综合评价，结果为：3家公司为行风建设有效；4家公司在行风建设上存在不同程度（以量化形式给出）的缺点与不足。第八十四页，共一百一十二页，2022年，8月28日线性规划LinearProgramming（LP）相对有效性评价问题举例

4所小学S1，S2，S3，S4，在校学生分别为1200，1000，1600，1400人，按800名标准学生的规模折算各个学校的教职工人数和建筑面积的投入，如下表：

学校投入S1S2S3S4教职工人数建筑面积/m2251800401500351700202500请您评价：就培养800名学生而言，那些学校