线性规划及单纯型法

关于线性规划及单纯型法第一页，共二百九十页，2022年，8月28日

线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回1.1线性规划问题及其数学模型第二页，共二百九十页，2022年，8月28日问题的提出例:生产计划问题第三页，共二百九十页，2022年，8月28日产品I产品2如何安排生产使利润最大？第四页，共二百九十页，2022年，8月28日决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值第五页，共二百九十页，2022年，8月28日是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——I的产量——II的产量——利润第六页，共二百九十页，2022年，8月28日第2步--定义目标函数MaxZ=x1+x2决策变量第七页，共二百九十页，2022年，8月28日

MaxZ=2x1+3x2系数第2步--定义目标函数第八页，共二百九十页，2022年，8月28日对我们有何限制?第九页，共二百九十页，2022年，8月28日第3步--表示约束条件

x1+2x2

84x1

164x2

12x1、x2

0第十页，共二百九十页，2022年，8月28日该计划的数学模型

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第十一页，共二百九十页，2022年，8月28日线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的。求目标函数最大化或最小化第十二页，共二百九十页，2022年，8月28日

线性规划模型的一般形式第十三页，共二百九十页，2022年，8月28日线性规划问题的标准形式标准形式为:目标函数最大约束条件等式决策变量非负第十四页，共二百九十页，2022年，8月28日

简写为第十五页，共二百九十页，2022年，8月28日

用向量表示第十六页，共二百九十页，2022年，8月28日

用矩阵表示C—价值向量b—资源向量X—决策变量向量第十七页，共二百九十页，2022年，8月28日

minZ=CX等价于maxZ’=-CX“”约束：加入非负松驰变量一般线性规划问题的标准形化例：

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0第十八页，共二百九十页，2022年，8月28日

minZ=CX等价于maxZ’=-CX“”约束：加入非负松驰变量一般线性规划问题的标准形化例：第十九页，共二百九十页，2022年，8月28日

“”约束：减去非负剩余变量；

Max例：可正可负（即无约束）；第二十页，共二百九十页，2022年，8月28日

解：标准形为第二十一页，共二百九十页，2022年，8月28日线性规划问题的数学模型例将下列线性规划问题化为标准形式用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以第二十二页，共二百九十页，2022年，8月28日线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;第二十三页，共二百九十页，2022年，8月28日线性规划问题的数学模型标准形式如下：第二十四页，共二百九十页，2022年，8月28日图解法线性规划问题求解的几种可能结果由图解法得到的启示1.2.1线性规划的图解法继续返回第二十五页，共二百九十页，2022年，8月28日例1的数学模型

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1

x2第二十六页，共二百九十页，2022年，8月28日9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2x1+2x2

8(0,4)(8,0)

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

04x1

164x2

16图解法第二十七页，共二百九十页，2022年，8月28日9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域图解法第二十八页，共二百九十页，2022年，8月28日9—8—7—6—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1+2x2

84x1

164x2

16可行域BCDEA图解法第二十九页，共二百九十页，2022年，8月28日9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16BCDEA2x1+3x2=6图解法第三十页，共二百九十页，2022年，8月28日9—8—7—6—5—4—3—2—1—0x2

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16BCDEAx1+2x2=84x1=16最优解(4,2)图解法第三十一页，共二百九十页，2022年，8月28日例1.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，x2=250

最优目标值z=27500图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第三十二页，共二百九十页，2022年，8月28日图解法

(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第三十三页，共二百九十页，2022年，8月28日图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第三十四页，共二百九十页，2022年，8月28日图解法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1第三十五页，共二百九十页，2022年，8月28日图解法（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第三十六页，共二百九十页，2022年，8月28日图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。第三十七页，共二百九十页，2022年，8月28日线性规划问题求解的

几种可能结果(a)唯一最优解

x26—5—4—3—2—1—0| | | | | | | | |1 2 3 4 5 6 7 8 9x1第三十八页，共二百九十页，2022年，8月28日(b)无穷多最优解6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1线性规划问题求解的

几种可能结果第三十九页，共二百九十页，2022年，8月28日(c)无界解

MaxZ=x1+x2

-2x1+x2

4

x1-x2

2

x1、x2

0

x2x1线性规划问题求解的

几种可能结果第四十页，共二百九十页，2022年，8月28日(d)无可行解

MaxZ=2x1+3x2x1+2x2

84x1

164x2

12

-2x1+x24x1、x2

0可行域为空集线性规划问题求解的

几种可能结果第四十一页，共二百九十页，2022年，8月28日图解法的几点结论:

（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。第四十二页，共二百九十页，2022年，8月28日练习：

用图解法求解LP问题

MaxZ=34x1+40x24x1+6x2

482x1+2x2

182x1+x2

16x1、x2

0第四十三页，共二百九十页，2022年，8月28日图解法—（练习）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16第四十四页，共二百九十页，2022年，8月28日图解法—（练习）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16可行域ABCDE第四十五页，共二百九十页，2022年，8月28日图解法—（练习）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)34x1+40x2=272第四十六页，共二百九十页，2022年，8月28日图解法—（练习）

18—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x1x24x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)第四十七页，共二百九十页，2022年，8月28日图解法—（练习）

x218—16—14—12—10—8—6—4—2—0| | | | | | | | |2 4 6 8 10 12 14 16 18x14x1+6x2

482x1+2x2

182x1+x2

16ABCDE(8,0)(0,6.8)最优解(3,6)4x1+6x2=482x1+2x2=18第四十八页，共二百九十页，2022年，8月28日1.2.1线性规划的图解法结束返回第四十九页，共二百九十页，2022年，8月28日1.2.2线性规划解的性质线性规划解的概念线性规划问题的几何意义（单纯形法原理）继续返回第五十页，共二百九十页，2022年，8月28日线性规划问题解的概念标准型可行解:满足AX=b,X>=0的解X称为线性规划问题的可行解。最优解：使Z=CX达到最大值的可行解称为最优解。第五十一页，共二百九十页，2022年，8月28日

基：若B是矩阵A中m×m阶非奇异子矩阵（B≠0），则B是线性规划问题的一个基。不妨设：,j=1，2，…,m——基向量。，j=1，2，…,m——基变量。,j=m+1,…,n——非基变量。线性规划问题解的概念第五十二页，共二百九十页，2022年，8月28日例求线性规划问题的所有基矩阵。解:约束方程的系数矩阵为2×5矩阵r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即第五十三页，共二百九十页，2022年，8月28日

求解线性规划问题解的概念第五十四页，共二百九十页，2022年，8月28日基解：称上面求出的X解为基解。基可行解：非负的基解X称为基可行解可行基：对应基可行解的基称为可行基线性规划问题解的概念T基变量令可求出：第五十五页，共二百九十页，2022年，8月28日线性规划解的关系图非可行解可行解

基可行解

基解线性规划问题解的概念

最优解？第五十六页，共二百九十页，2022年，8月28日

例：求基解、基可行解、最优解。线性规划问题解的概念第五十七页，共二百九十页，2022年，8月28日10051045Y

20452017Y

35005410Y

40550-120N5100-50415N652.5001.517.5Y

7540-3022N82430019

Y

是否基可行解最优解线性规划问题解的概念解：第五十八页，共二百九十页，2022年，8月28日

：求基解、基可行解、最优解。练习：线性规划问题解的概念第五十九页，共二百九十页，2022年，8月28日线性规划问题的几何意义基本概念凸集：线性规划问题的几何意义第六十页，共二百九十页，2022年，8月28日

顶点:若K是凸集，X∈K；若X不能用不同的两点的线性组合表示为：则X为顶点.凸集线性规划问题的几何意义第六十一页，共二百九十页，2022年，8月28日

凸组合：

Xn=2，k=3线性规划问题的几何意义第六十二页，共二百九十页，2022年，8月28日定理1:若线性规划问题存在可行域,则其可行域:是凸集.基本定理证明:线性规划问题的几何意义第六十三页，共二百九十页，2022年，8月28日

只要验证X在D中即可第六十四页，共二百九十页，2022年，8月28日

引理：可行解X为基可行解

X的正分量对应的列向量线性无关定理3：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。定理2：线性规划问题的基可行解X对应于可行域D的顶点。证明：反证法。分两步。第六十五页，共二百九十页，2022年，8月28日几点结论：线性规划问题的可行域是凸集。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。第六十六页，共二百九十页，2022年，8月28日图解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生

目标函数等值线的斜率最优解第六十七页，共二百九十页，2022年，8月28日图解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生

目标函数等值线的斜率最优解第六十八页，共二百九十页，2022年，8月28日图解法9—8—7—6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1x1+2x2

84x1

164x2

16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生

目标函数等值线的斜率最优解第六十九页，共二百九十页，2022年，8月28日求解LP的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。第七十页，共二百九十页，2022年，8月28日1.2.2线性规划解的性质结束返回第七十一页，共二百九十页，2022年，8月28日1.3单纯形法原理

本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。第七十二页，共二百九十页，2022年，8月28日引例（上一章例）第七十三页，共二百九十页，2022年，8月28日求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。第七十四页，共二百九十页，2022年，8月28日第1步确定初始基可行解

根据显然，可构成初等可行基B。

为基变量第七十五页，共二百九十页，2022年，8月28日

第2步求出基可行解

基变量用非基变量表示，并令非基变量为0时对应的解是否是最优解？第七十六页，共二百九十页，2022年，8月28日第3步最优性检验分析目标函数检验数<=0时，最优解>0时，无解换基，继续只要取或的值可能增大。换入？基变量换出？基变量考虑将或换入为基变量第七十七页，共二百九十页，2022年，8月28日第4步基变换换入基变量：换入变量X2

（即选最大非负检验数对应的变量）一般选取对应的变量均可换入。第七十八页，共二百九十页，2022年，8月28日换出变量使换入的变量越大越好同时，新的解要可行。选非负的最小者对应的变量换出为换入变量，应换出？变量。思考：当时会怎样？第七十九页，共二百九十页，2022年，8月28日因此，基由变为转第2步：基变量用非基变量表示。

第3步：最优性判断检验数存在正，按第4步换基继续迭代均非正，停止（这时的解即是最优解）为换入变量，应换出

变量。第八十页，共二百九十页，2022年，8月28日

转第2步第八十一页，共二百九十页，2022年，8月28日

继续迭代,可得到:最优值Ｚ＝１４最优解第八十二页，共二百九十页，2022年，8月28日结合图形法分析（单纯形法的几何意义）6—5—4—3—2—1—0x2| | | | | | | | |1 2 3 4 5 6 7 8 9x1A(0,3)B(2,3)C(4,2)D(4,0)第八十三页，共二百九十页，2022年，8月28日单纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法——单纯形法迭代原理。第八十四页，共二百九十页，2022年，8月28日观察法:直接观察得到初始可行基≤约束条件:加入松弛变量即形成可行基。（下页）≥约束条件:加入非负人工变量,以后讨论.1、初始基可行解的确定第八十五页，共二百九十页，2022年，8月28日1、初始基可行解的确定

不妨设为松弛变量，则约束方程组可表示为第八十六页，共二百九十页，2022年，8月28日

1、初始基可行解的确定第八十七页，共二百九十页，2022年，8月28日2、最优性检验与解的判别第八十八页，共二百九十页，2022年，8月28日

2、最优性检验与解的判别第八十九页，共二百九十页，2022年，8月28日

2、最优性检验与解的判别jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZåååå+=+===+=-=-+===10101'1'0

)()(

ss检验数令：令：第九十页，共二百九十页，2022年，8月28日

(1)最优解判别定理：若：为基可行解，且全部则为最优解。（2）唯一最优解判别定理：若所有则存在唯一最有解。2、最优性检验与解的判别第九十一页，共二百九十页，2022年，8月28日

（3）无穷多最优解判定定理：若：且存在某一个非基变量则存在无穷多最优解。（4）无界解判定定理：若有某一个非基变量并且对应的非基变量的系数

则具有无界解。

2、最优性检验与解的判别第九十二页，共二百九十页，2022年，8月28日

（4）之证明：2、最优性检验与解的判别第九十三页，共二百九十页，2022年，8月28日最优解判断小结

（用非基变量的检验数）所有基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一有

换基继续YYYYNNN无界解N以后讨论第九十四页，共二百九十页，2022年，8月28日3、基变换换入变量确定

对应的为换入变量.(一般)注意：只要对应的变量均可作为换入变量此时，目标函数第九十五页，共二百九十页，2022年，8月28日

换出变量确定3、基变换Z

大大（在可行的范围内）则对应的为换出变量.第九十六页，共二百九十页，2022年，8月28日4、迭代运算

写成增广矩阵的形式,进行迭代.第九十七页，共二百九十页，2022年，8月28日例：

4、迭代运算非基变量基变量001通过初等行变换化主列为主元第九十八页，共二百九十页，2022年，8月28日

4、迭代运算每次迭代的信息都在增广矩阵及目标函数中。检验数第九十九页，共二百九十页，2022年，8月28日1.3单纯形法迭代原理结束第一百页，共二百九十页，2022年，8月28日1.4单纯形法的计算步骤

为书写规范和便于计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。第一百零一页，共二百九十页，2022年，8月28日

在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。单纯形表第一百零二页，共二百九十页，2022年，8月28日E单位阵N非基阵基变量XB非基变量XN0单纯形表第一百零三页，共二百九十页，2022年，8月28日

21000

检验数单纯形表结构单纯形表

—24/65/1C已知第一百零四页，共二百九十页，2022年，8月28日

21000

—24/65/1C检验数单纯形表结构单纯形表基可行解：第一百零五页，共二百九十页，2022年，8月28日单纯形表结构单纯形表

21000

—24/65/1C检验数有时不写此项求第一百零六页，共二百九十页，2022年，8月28日单纯形表结构单纯形表

21000

—24/65/1C检验数求第一百零七页，共二百九十页，2022年，8月28日单纯形表结构单纯形表

21000

—24/65/1C检验数求不妨设此为主列主行第一百零八页，共二百九十页，2022年，8月28日单纯形表结构单纯形表

21000

—24/65/1C检验数主元第一百零九页，共二百九十页，2022年，8月28日用单纯形表求解LP问题例、用单纯形表求解LP问题第一百一十页，共二百九十页，2022年，8月28日解：化标准型第一百一十一页，共二百九十页，2022年，8月28日

21000

01505100

0

24620100511001

21000

—24/65/1主元化为1主列单位向量换出换入表1：列初始单纯形表（单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值对应的行为主行第一百一十二页，共二百九十页，2022年，8月28日

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=表2：换基

（初等行变换，主列化为单位向量，主元为1）检验数>0确定主列最小确定主列主元第一百一十三页，共二百九十页，2022年，8月28日

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

检验数<=0最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5

2*7/21*3/2+0*15/28.5表3：换基

（初等行变换，主列化为单位向量，主元为1）第一百一十四页，共二百九十页，2022年，8月28日单纯形法的表格形式上面假设x1,x2,…xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为则其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解下例。

max50x1+100x2+0·s1+0·s2+0·s3.x1+x2+s1=300，

2x1+x2+s2=400，

x2+s3=250，

x1,x2,s1,s2,s3≥0.把上面的数据填入如下的单纯形表格第一百一十五页，共二百九十页，2022年，8月28日单纯形法的表格形式按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0，所在zi行中的第2位数填入0；在行中填入cj-zj所得的值，如；z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此确定s3为出基变量；由于，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。第一百一十六页，共二百九十页，2022年，8月28日单纯形法的表格形式以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向量，由于主元在p2的第3分量上，所以这个单位向量是也就是主元素变成1。这样我们又得到的第1次迭代的单纯表如下所示。在上表中第3个基变量s1已被x2代替，故基变量列中的第3个基变量应变为x2。由于第0次迭代表中的主元a32已经为1，因此第3行不变。为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。同样可以求得第2行。求得第1次迭代的基本可行解为s1=50,s2=150,x2=250,x1=0,s3=0,z=25000.第一百一十七页，共二百九十页，2022年，8月28日单纯形法的表格形式从上表可以看出，第一次迭代的，因此不是最优解。设x1为入基变量，从此值可知b1/a11=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50,s3=0,这时z=27500。由于检验数都<0，因此所求得的基本可行解为最优解，z=27500为最优目标函数值。实际上，我们可以连续地使用一个单纯形表，不必一次迭代重画一个表头。第一百一十八页，共二百九十页，2022年，8月28日

单纯形法的计算及示例单纯形法几何解释---顶点寻优例：maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4 s.tx1+x23标准化s.tx1+x2+x3=3 x1+2x24 x1+2x2+x4=4 x10,x20 xj0,(j=1,2,3,4) （1）初始基本可行解的选择：-----坐标原点处 令x1=x2=0,由

x1+x2+x3=3

x1+2x2+x4=4

（2）是否为最优解的判定:-----计算检验数 若

x1↑1,则

x3↓1,x4↓1,

σ1=2-（01+01）=2 σj=△z=cj-zj=cj-ciaij，称σj为检验数。x3=3-(x1+x2)x4=4-(x1+2x2)

解得X=(0,0,3,4)T第一百一十九页，共二百九十页，2022年，8月28日若

x2↑1,则

x3↓1,x4↓2,

σ2=3-(01+02)=3 ****当所有检验数均有σj

0时，则为最优解。****（3）找新的顶点（基本可行解）： 直观看，x2↑1,则z↑3，∴应找A点，即增加x2。x2可增加多少？需要保证x3=3-(x1+x2)0

x4=4-(x1+2x2)0， ∴

x2=min（3/1，4/2），从而 x3=1-(x1/2-x4

/2）

x2=2-(x1/2+x4/2)

令x1=x4=0，则新的基本可行解为X=(0，2，1，0)T重复上述过程，直至所有检验数

σj

0。第一百二十页，共二百九十页，2022年，8月28日继续迭代：找新的顶点（基本可行解）： 若x1↑1,则z↑1/2，∴应找B点，即增加x1。

x1可增加多少？需要保证x3=1-(x1/2-x4/2)0

x2=2-(x1/2+x4/2)0， ∴

x1=min（2，4），从而 x1=2-(2x3-x4)

x2=1-(-x3+x4), 则新的基本可行解为X=(2，1，0，0)T若

x1↑1,则

x3↓1/2,x2↓1/2,

σ1=2-（01/2+31/2）=1/2若

x4↑1,则

x3↓-1/2,x2↓1/2,

σ4=0-（0(-1/2)+31/2）=-3/2σ3=-1, σ4=-1, zmax=7第一百二十一页，共二百九十页，2022年，8月28日①②O

C

A

BX1X2(0,2)(3,0)(2,1)34第一百二十二页，共二百九十页，2022年，8月28日Cj→x1x2x3x4XBbCB1 1 1 01 2 012 3 0 034x3x400cj-zj23003/1=34/2=21/2 0 1 -1/21/2 1 01/2x3x212cj-zj1/2 00-3/203241 0 2 -10 1 -11x1x221cj-zj0 0 -1 -1231.4.2单纯形法计算：θi第一百二十三页，共二百九十页，2022年，8月28日单纯形法计算过程总结：（1）化标准形，列初始单纯形表；（2）计算检验数：σj=△z=cj-zj=cj-ciaij（3）最优性判断：当所有检验数均有σj

0时，则为最优解。否则 迭代求新的基本可行解。（4）迭代： 入基变量：取max{σj0}=

σk→xk 出基变量：取min{θi=bi/aikaik>0}=θl

→x(l)

主元素：[alk] 新单纯表：pk=单位向量注：当所有检验数σj

0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。i=1m第一百二十四页，共二百九十页，2022年，8月28日单纯形法的计算步骤例用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。第一百二十五页，共二百九十页，2022年，8月28日单纯形法的计算步骤20－x221/3150120753017131/30－90－22560x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第一百二十六页，共二百九十页，2022年，8月28日

21000

01505100

0

24620100511001

21000练习:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列第一百二十七页，共二百九十页，2022年，8月28日结束2.4单纯形法的计算步骤第一百二十八页，共二百九十页，2022年，8月28日2.5.1单纯形法的进一步讨论一、大M法二、两阶段法----人工变量法第一百二十九页，共二百九十页，2022年，8月28日人工变量法问题：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？

第一百三十页，共二百九十页，2022年，8月28日人工变量法加入人工变量设线性规划问题的标准型为：第一百三十一页，共二百九十页，2022年，8月28日

加入人工变量,构造初始可行基.人工变量法系数矩阵为单位矩阵，可构成初始可行基。第一百三十二页，共二百九十页，2022年，8月28日

约束条件已改变，目标函数如何调整？人工变量法第一百三十三页，共二百九十页，2022年，8月28日“惩罚”人工变量！（1）大M法（2）两阶段法第一百三十四页，共二百九十页，2022年，8月28日一、大M法人工变量在目标函数中的系数为-M,其中，M为任意大的正数。目标函数中添加“罚因子”-M（M是任意大的正数）为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。第一百三十五页，共二百九十页，2022年，8月28日例:求解线性规划问题一、大M法第一百三十六页，共二百九十页，2022年，8月28日

一、大M法解:加入松弛变量和剩余变量进行标准化,加入人工变量构造初始可行基.

第一百三十七页，共二百九十页，2022年，8月28日求解结果出现检验数非正若基变量中含非零的人工变量，则无可行解；否则，有最优解。一、大M法用单纯形法求解（见下页）。目标函数中添加“罚因子”-M为人工变量系数，只要人工变量>0，则目标函数不可能实现最优。第一百三十八页，共二百九十页，2022年，8月28日1-21-412-2013-6MM-13M-13

-1-1

x1

x2

x3

0

x411-M

x63-M

x71Cj-ZjCj

CBXBb100-1000-M

00

x4

x5

113/21

00100100

-

M

-M

x6

x7

表1（初始单纯形表）一、大M法（单纯形法求解）第一百三十九页，共二百九十页，2022年，8月28日3-20010

-201

1M-103

-1-1x1

x2

x30x410-M

x61-1x31Cj-ZjCjCBXBb100-1000-M

00

x4

x5

1

0-11-201

01-3M

-

M-M

x6

x7

一、大M法（单纯形法求解）表2第一百四十页，共二百九十页，2022年，8月28日300010-2011003

-1-1

x1

x2

x30x412-1x21-1x31Cj-ZjCjCBXBb1-20-1000-1

00

x4

x5

4

i

2-51-2011-M-1

-M

-

M-M

x6

x7

表3一、大M法（单纯形法求解）第一百四十一页，共二百九十页，2022年，8月28日1000100010003

-1-1

x1

x2

x33x14-1x21-1x392Cj

CBXB

b1/3-2/3

0-12/3-4/3

-1/3-1/3

00

x4

x5

2/3-5/3

1-24/3-7/3

1/3-M2/3-M

-

M-M

x6

x7

表4一、大M法（单纯形法求解）最优解为目标函数值z=2检验数均非正，此为最终单纯形表第一百四十二页，共二百九十页，2022年，8月28日在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。【例1-20】用大M法解下列线性规划1.大M单纯形法大M和两阶段单纯形法1.5单纯形法

SimplexMethod第一百四十三页，共二百九十页，2022年，8月28日【解】首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入―Mx6―Mx7一项，得到人工变量单纯形法数学模型用前面介绍的单纯形法求解，见下表。1.5单纯形法

SimplexMethod第一百四十四页，共二百九十页，2022年，8月28日Cj32－100－M－MbCBXBx1x2x3x4x5x6x7－M

0－Mx6x5x7－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1x6x5x3－6－32[5]3－2001－1000101003→81λj5