线性规划以及单纯型法

1、关于线性规划及单纯型法第一张，PPT共二百九十页，创作于2022年6月 线性规划问题的提出 线性规划的基本概念 线性规划的数学模型 线性规划问题的标准形式继续返回1.1 线性规划问题及其数学模型第二张，PPT共二百九十页，创作于2022年6月问题的提出例: 生产计划问题第三张，PPT共二百九十页，创作于2022年6月产品I产品2如何安排生产使利润最大？第四张，PPT共二百九十页，创作于2022年6月决策变量（Decision variables）目标函数（Objective function）约束条件（Constraint conditions）可行域（Feasible region)最优解（

2、Optimal solution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值第五张，PPT共二百九十页，创作于2022年6月是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步 -确定决策变量设 I的产量 II的产量 利润第六张，PPT共二百九十页，创作于2022年6月第2步 -定义目标函数Max Z = x1 + x2决策变量第七张，PPT共二百

3、九十页，创作于2022年6月 Max Z = 2 x1 + 3 x2系数第2步 -定义目标函数第八张，PPT共二百九十页，创作于2022年6月对我们有何限制?第九张，PPT共二百九十页，创作于2022年6月第3步 -表示约束条件 x1 + 2 x2 8 4 x1 16 4 x2 12 x1、 x2 0第十张，PPT共二百九十页，创作于2022年6月该计划的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 x2第十一张，PPT共二百九十页，创作于2022年6月线性规划问题的共同特征一组决策变量X表示一个方案

4、,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的。 求目标函数最大化或最小化第十二张，PPT共二百九十页，创作于2022年6月 线性规划模型的一般形式 第十三张，PPT共二百九十页，创作于2022年6月线性规划问题的标准形式标准形式为:目标函数最大约束条件等式决策变量非负第十四张，PPT共二百九十页，创作于2022年6月 简写为第十五张，PPT共二百九十页，创作于2022年6月 用向量表示第十六张，PPT共二百九十页，创作于2022年6月 用矩阵表示C价值向量b资源向量X决策变量向量第十七张，PPT共二百九十页，创作于2022年6月 min Z=CX 等价于 max Z = -

5、CX“” 约束：加入非负松驰变量一般线性规划问题的标准形化例： 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0第十八张，PPT共二百九十页，创作于2022年6月 min Z=CX 等价于 max Z = -CX“” 约束：加入非负松驰变量一般线性规划问题的标准形化例：第十九张，PPT共二百九十页，创作于2022年6月 “” 约束： 减去非负剩余变量； Max 例 ： 可正可负（即无约束）；第二十张，PPT共二百九十页，创作于2022年6月 解 ：标准形为第二十一张，PPT共二百九十页，创作于2022年6月线性规划问题的

6、数学模型例 将下列线性规划问题化为标准形式用 替换 ，且 解:（）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以第二十二张，PPT共二百九十页，创作于2022年6月线性规划问题的数学模型(2) 第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3) 第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然;第二十三张，PPT共二百九十页，创

7、作于2022年6月线性规划问题的数学模型标准形式如下：第二十四张，PPT共二百九十页，创作于2022年6月 图解法 线性规划问题求解的 几种可能结果 由图解法得到的启示1.2.1 线性规划的图解法继续返回第二十五张，PPT共二百九十页，创作于2022年6月例1的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 x2第二十六张，PPT共二百九十页，创作于2022年6月9 8 7 6 5 4 3 2 1 0 |123456789x1x2x1 + 2x2 8(0, 4)(8, 0) 目标函数 Max Z = 2

8、x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 04x1 164 x2 16图解法第二十七张，PPT共二百九十页，创作于2022年6月9 8 7 6 5 4 3 2 1 0 x2 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 16可行域图解法第二十八张，PPT共二百九十页，创作于2022年6月9 8 7 6 5 4 3 2 1 0 |123456789x1x2 目标函数 Max Z = 2x1 + 3x2 约束

9、条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0 x1 + 2x2 84x1 164 x2 16可行域BCDEA图解法第二十九张，PPT共二百九十页，创作于2022年6月9 8 7 6 5 4 3 2 1 0 x2 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 16BCDEA2x1 + 3x2 = 6图解法第三十张，PPT共二百九十页，创作于2022年6月9 8 7 6 5 4 3 2 1 0 x2 目标函数 Max Z = 2x

10、1 + 3x2 约束条件 x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0|123456789x1x1 + 2x2 84x1 164 x2 16BCDEAx1+ 2x2=8 4x1 =16最优解 (4, 2)图解法第三十一张，PPT共二百九十页，创作于2022年6月例1.目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 300 (A) 2 x1 + x2 400 (B) x2 250 (C) x1 0 (D) x2 0 (E)得到最优解： x1 = 50， x2 = 250 最优目标值 z = 27500图 解 法 对于只有两个决

11、策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。 下面通过例1详细讲解其方法：第三十二张，PPT共二百九十页，创作于2022年6月图 解 法 (1)分别取决策变量X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0第三十三张，PPT共二百九十页，创作于2022年6月图 解 法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=

12、3001001002002x1+x24002x1+x2=400300200300400第三十四张，PPT共二百九十页，创作于2022年6月图 解 法（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图2-1第三十五张，PPT共二百九十页，创作于2022年6月图 解 法（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可

13、行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图2-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE第三十六张，PPT共二百九十页，创作于2022年6月图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。第三十七张，PPT共二百九十页，创作于2022年6月线性规划问题求解的 几种可能结果(a) 唯一最优解 x26 5 4 3 2 1 0

14、 |123456789x1第三十八张，PPT共二百九十页，创作于2022年6月(b)无穷多最优解6 5 4 3 2 1 0 x2|123456789x1线性规划问题求解的 几种可能结果第三十九张，PPT共二百九十页，创作于2022年6月 (c)无界解 Max Z = x1 + x2 -2x1 + x2 4 x1 - x2 2 x1、 x2 0 x2x1线性规划问题求解的 几种可能结果第四十张，PPT共二百九十页，创作于2022年6月(d)无可行解 Max Z = 2x1 + 3x2 x1 +2 x2 8 4 x1 16 4x2 12 -2x1 + x2 4 x1、 x2 0可行域为空集线性规划

15、问题求解的 几种可能结果第四十一张，PPT共二百九十页，创作于2022年6月图解法的几点结论:（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。第四十二张，PPT共二百九十页，创作于2022年6月练习：用图解法求解LP问题 Max Z = 34 x1 + 40 x24 x1 + 6 x2 48 2 x1 + 2 x2 182 x1 + x2 16x1、 x2 0第四十三张，PPT共二百九十页，创作于2022年6月图解法 （练习）

16、 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16第四十四张，PPT共二百九十页，创作于2022年6月图解法 （练习） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16可行域ABCDE第四十五张，PPT共二百九十页，创作于2022年6月图解法 （练习） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2

17、x2 182x1 + x2 16ABCDE (8,0)(0,6.8)34x1 + 40 x2 = 272第四十六张，PPT共二百九十页，创作于2022年6月图解法 （练习） 18 16 14 12 10 8 6 4 2 0 |24681012141618x1x24x1 + 6x2 482x1 + 2x2 182x1 + x2 16ABCDE (8,0)(0,6.8)第四十七张，PPT共二百九十页，创作于2022年6月图解法 （练习） x218 16 14 12 10 8 6 4 2 0 |24681012141618x14x1 + 6x2 482x1 + 2x2 182x1 + x2 16AB

18、CDE (8,0)(0,6.8)最优解 (3,6)4x1+ 6x2=48 2x1+ 2x2 =18第四十八张，PPT共二百九十页，创作于2022年6月1.2.1 线性规划的图解法结束返回第四十九张，PPT共二百九十页，创作于2022年6月1.2.2 线性规划解的性质线性规划解的概念线性规划问题的几何意义 （单纯形法原理）继续返回第五十张，PPT共二百九十页，创作于2022年6月线性规划问题解的概念标准型可行解:满足AX=b, X=0的解X称为线性规划问题的可行解。最优解：使Z=CX达到最大值的可行解称为最优解。第五十一张，PPT共二百九十页，创作于2022年6月 基：若B是矩阵A中mm阶非奇异

19、子矩阵（B0），则B是线性规划问题的一个基。不妨设： , j=1，2，,m 基向量。 ，j=1，2，,m 基变量。 , j=m+1,n 非基变量。线性规划问题解的概念第五十二张，PPT共二百九十页，创作于2022年6月例 求线性规划问题的所有基矩阵。解: 约束方程的系数矩阵为25矩阵 r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即第五十三张，PPT共二百九十页，创作于2022年6月 求解 线性规划问题解的概念第五十四张，PPT共二百九十页，创作于2022年6月基解：称上面求出的X解为基解。基可行解：非负的基解X称为基可行解可行基：对应基可行解的基称为可行基线性规划问题解的概念T基变量

20、令 可求出：第五十五张，PPT共二百九十页，创作于2022年6月 线性规划解的关系图 非可行解可行解 基可行解 基解线性规划问题解的概念 最优解？第五十六张，PPT共二百九十页，创作于2022年6月 例：求基解、基可行解、最优解。线性规划问题解的概念第五十七张，PPT共二百九十页，创作于2022年6月1 0 0 5 10 4 5 Y 2 0 4 5 2 0 17 Y 3 5 0 0 5 4 10 Y 4 0 5 5 0 -1 20 N5 10 0 -5 0 4 15 N6 5 2.5 0 0 1.5 17.5 Y 7 5 4 0 -3 0 22 N8 2 4 3 0 0 19 Y 是否基可行解

21、最优解线性规划问题解的概念解：第五十八张，PPT共二百九十页，创作于2022年6月 ：求基解、基可行解、最优解。练习：线性规划问题解的概念第五十九张，PPT共二百九十页，创作于2022年6月线性规划问题的几何意义 基本概念凸集：线性规划问题的几何意义第六十张，PPT共二百九十页，创作于2022年6月 顶点:若K是凸集，XK；若X不能用不同的两点 的线性组合表示为： 则X为顶点. 凸集线性规划问题的几何意义第六十一张，PPT共二百九十页，创作于2022年6月 凸组合： X n=2，k=3线性规划问题的几何意义第六十二张，PPT共二百九十页，创作于2022年6月定理1: 若线性规划问题存在可行域,

22、 则其可行域: 是凸集. 基本定理证明:线性规划问题的几何意义第六十三张，PPT共二百九十页，创作于2022年6月 只要验证X在D中即可第六十四张，PPT共二百九十页，创作于2022年6月 引理：可行解X为基可行解 X的正分量对应的列向量线性无关定理3：若可行域有界，线性规划 问题的目标函数一定可以在 其可行域的顶点上达到最优。定理2：线性规划问题的基可行解X 对应于可行域D的顶点。 证明：反证法。分两步。第六十五张，PPT共二百九十页，创作于2022年6月几点结论：线性规划问题的可行域是凸集。基可行解与可行域的顶点一一对应，可行域有有限多个顶点。最优解必在顶点上得到。第六十六张，PPT共二百

23、九十页，创作于2022年6月图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生 目标函数等值线的斜率最优解第六十七张，PPT共二百九十页，创作于2022年6月图解法9 8 7 6 5 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生 目标函数等值线的斜率最优解第六十八张，PPT共二百九十页，创作于2022年6月图解法9 8 7 6 5

24、 4 3 2 1 0 x2|123456789x1x1 + 2x2 84x1 164 x2 16可行域BCDEA可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生 目标函数等值线的斜率最优解第六十九张，PPT共二百九十页，创作于2022年6月求解LP的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比 原来更优。第七十张，PPT共二百九十页，创作于2022年6月1.2.2 线性规划解的性质结束返回第七十一张，PPT共二百九十页，创作于2022年6月1.3 单纯形法原理 本节通过一个引例，可以了解利用单纯形法求解线

25、性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。第七十二张，PPT共二百九十页，创作于2022年6月引例（上一章例）第七十三张，PPT共二百九十页，创作于2022年6月求解线性规划问题的基本思路1、构造初始可行基；2、求出一个基可行解（顶点）3、最优性检验：判断是否最优解；4、基变化，转2。要保证目标函数值比 原来更优。从线性规划解的性质可知求解线性规划问题的基本思路。第七十四张，PPT共二百九十页，创作于2022年6月第1步 确定初始基可行解 根据显然 ， 可构成初等可行基B 。 为基变量第七十五张，PPT共二百九十页，创作于2022年6月 第2步 求出基可行解 基变

26、量用非基变量表示，并令非基变量为 0时对应的解是否是最优解？第七十六张，PPT共二百九十页，创作于2022年6月第3步 最优性检验分析目标函数检验数0 时， 无解换基，继续只要取 或 的 值可能增大。换入？基变量换出？基变量考虑将 或 换入为基变量第七十七张，PPT共二百九十页，创作于2022年6月第4步 基变换换入基变量：换入变量X2 （即选最大非负检验数对应的变量）一般选取 对应的变量均可换入。第七十八张，PPT共二百九十页，创作于2022年6月换出变量使换入的变量越大越好同时，新的解要可行。选非负 的最小者对应的变量换出为换入变量，应换出 ？ 变量。思考：当 时会怎样？第七十九张，PPT

27、共二百九十页，创作于2022年6月因此，基由 变为 转第2步：基变量用非基变量表示。 第3步：最优性判断 检验数 存在正，按第4步换基继续迭代 均非正，停止 （这时的解即是最优解）为换入变量，应换出 变量。第八十张，PPT共二百九十页，创作于2022年6月 转 第2步第八十一张，PPT共二百九十页，创作于2022年6月 继续迭代, 可得到:最优值最优解第八十二张，PPT共二百九十页，创作于2022年6月结合图形法分析（单纯形法的几何意义）6 5 4 3 2 1 0 x2|123456789x1A(0,3)B(2,3)C(4,2)D(4,0)第八十三张，PPT共二百九十页，创作于2022年6月单

28、纯形法迭代原理从引例中了解了线性规划的求解过程，将按上述思路介绍一般的线性规划模型的求解方法单纯形法迭代原理。第八十四张，PPT共二百九十页，创作于2022年6月观察法:直接观察得到初始可行基约束条件: 加入松弛变量即形成可行基。（下页）约束条件: 加入非负人工变量, 以后讨论. 1、初始基可行解的确定第八十五张，PPT共二百九十页，创作于2022年6月1、初始基可行解的确定 不妨设 为松弛变量，则约束方程组可表示为第八十六张，PPT共二百九十页，创作于2022年6月 1、初始基可行解的确定第八十七张，PPT共二百九十页，创作于2022年6月2、最优性检验与解的判别第八十八张，PPT共二百九十

29、页，创作于2022年6月 2、最优性检验与解的判别第八十九张，PPT共二百九十页，创作于2022年6月 2、最优性检验与解的判别jnmjjjjjjnmjjjmiijijmiiixZZZcxZcZZacZbcZ+=+=+=-=-+=1010110 )()( ss检验数令：令：第九十张，PPT共二百九十页，创作于2022年6月 (1) 最优解判别定理：若： 为基可行解，且全部 则 为最优解。（2）唯一最优解判别定理：若所有 则存在唯一最有解。 2、最优性检验与解的判别第九十一张，PPT共二百九十页，创作于2022年6月 （3）无穷多最优解判定定理：若： 且存在某一个非基变量 则存在无穷多最优解。（

30、4）无界解判定定理：若有某一个非基 变量 并且对应的非基变量的系数 则具有无界解。 2、最优性检验与解的判别第九十二张，PPT共二百九十页，创作于2022年6月 （4）之证明：2、最优性检验与解的判别第九十三张，PPT共二百九十页，创作于2022年6月最优解判断小结 （用非基变量的检验数）所有 基变量中有非零人工变量某非基变量检验数为零唯一最优解无穷多最优解无可行解对任一 有 换基继续YYYYNNN无界解N以后讨论第九十四张，PPT共二百九十页，创作于2022年6月3、基变换换入变量确定 对应的 为换入变量. (一般)注意：只要 对应的变量 均可作为换入变量此时，目标函数第九十五张，PPT共二

31、百九十页，创作于2022年6月 换出变量确定3、基变换Z 大大（在可行的范围内）则对应的 为换出变量.第九十六张，PPT共二百九十页，创作于2022年6月4、迭代运算 写成增广矩阵的形式,进行迭代.第九十七张，PPT共二百九十页，创作于2022年6月例： 4、迭代运算非基变量基变量001通过初等行变换化主列为主元第九十八张，PPT共二百九十页，创作于2022年6月 4、迭代运算每次迭代的信息都在增广矩阵及目标函数中。检验数第九十九张，PPT共二百九十页，创作于2022年6月1.3 单纯形法迭代原理结束第一百张，PPT共二百九十页，创作于2022年6月1.4 单纯形法的计算步骤 为书写规范和便于

32、计算，对单纯形法的计算设计了单纯形表。每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。本节介绍用单纯形表计算线性规划问题的步骤。第一百零一张，PPT共二百九十页，创作于2022年6月 在上一节单纯形法迭代原理中可知，每一次迭代计算只要表示出当前的约束方程组及目标函数即可。 单纯形表第一百零二张，PPT共二百九十页，创作于2022年6月E单位阵N非基阵基变量XB非基变量XN0 单纯形表第一百零三张，PPT共二百九十页，创作于2022年6月 2 1 0 0 0 检验数单纯形表结构 单纯形表 24/65/1C已知第一百零四张，PPT共二百九十

33、页，创作于2022年6月 2 1 0 0 0 24/65/1C检验数单纯形表结构 单纯形表基可行解：第一百零五张，PPT共二百九十页，创作于2022年6月单纯形表结构 单纯形表 2 1 0 0 0 24/65/1C检验数有时不写此项求第一百零六张，PPT共二百九十页，创作于2022年6月单纯形表结构 单纯形表 2 1 0 0 0 24/65/1C检验数求第一百零七张，PPT共二百九十页，创作于2022年6月单纯形表结构 单纯形表 2 1 0 0 0 24/65/1C检验数求不妨设此为主列主行第一百零八张，PPT共二百九十页，创作于2022年6月单纯形表结构 单纯形表 2 1 0 0 0 24/

34、65/1C检验数主元第一百零九张，PPT共二百九十页，创作于2022年6月用单纯形表求解LP问题例、用单纯形表求解LP问题第一百一十张，PPT共二百九十页，创作于2022年6月解：化标准型第一百一十一张，PPT共二百九十页，创作于2022年6月 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 24/65/1主元化为1主列单位向量 换出 换入表1：列初始单纯形表 （单位矩阵对应的变量为基变量）正检验数中最大者对应的列为主列最小的值对应的行为主行第一百一十二张，PPT共二百九十页，创作于2022年6月 2 1 0 0

35、0 0 15 0 5 1 0 0 2 4 1 2/6 0 1 /6 0 0 1 0 4/6 0 -1/6 1 0 1/3 0 -1/3 0 15/524/26/4 0*5 2*2/6 +0*4/61- 2/3=表2：换基 （初等行变换，主列化为单位向量，主元为1）检验数0确定主列 最小确定主列主元第一百一十三张，PPT共二百九十页，创作于2022年6月 2 1 0 0 0 0 15/2 0 0 1 5/4 -15/2 2 7/2 1 0 0 1/4 -1/2 1 3/2 0 1 0 -1/4 3/2 0 0 0 -1/4 -1/2 检验数=0最优解为X=(7/2,3/2,15/2,0,0)目标

36、函数值Z=8.5 2*7/2 1*3/2+0*15/28.5表3：换基 （初等行变换，主列化为单位向量，主元为1）第一百一十四张，PPT共二百九十页，创作于2022年6月单纯形法的表格形式 上面假设x1,x2,xm是基变量，即第i行约束方程的基变量正好是xi，而经过迭代后，基将发生变化，计算zj的式子也会发生变化。如果迭代后的第i行约束方程中的基变量为xBi，与xBi相应的目标函数系数为cBi，系数列向量为 则 其中，(cB)是由第1列第m行各约束方程中的基变量相应的目标函数依次组成的有序行向量。 单纯形法的表格形式是把用单纯形法求出基本可行解、检验其最优性、迭代某步骤都用表格的方式来计算求出

37、，其表格的形式有些像增广矩阵，而其计算的方法也大体上使用矩阵的行的初等变换。以下用单纯形表格来求解下例。 max 50 x1+100 x2+0s1+0s2+0s3. x1+x2+s1=300， 2x1+x2+s2=400， x2+s3=250， x1, x2, s1, s2, s30. 把上面的数据填入如下的单纯形表格第一百一十五张，PPT共二百九十页，创作于2022年6月单纯形法的表格形式按照线性规划模型在表中填入相对应的值，如上表所示；在上表中有一个m*m的单位矩阵，对应的基变量为s1,s2,s3；在zj行中填入第j列与cB列中对应的元素相乘相加所得的值，如z2=0*1+0*1+0*1=0

38、，所在zi行中的第2位数填入0；在 行中填入cj-zj所得的值，如 ；z表示把初始基本可行解代入目标函数求得的目标函数值，即b列*cB列；初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;由于250/1最小，因此确定s3为出基变量；由于 ，因此确定x2为入基变量。出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别。第一百一十六张，PPT共二百九十页，创作于2022年6月单纯形法的表格形式以下进行第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解，具体的做法用行的初等变换使得x2的系数向量p2变换成单位向

39、量，由于主元在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.第一百一十七张，PPT共二百九十页，创作于2022年6月单纯形法的表格形式从上表可以看出，第一次迭代的 ，因此不是最优解。设x1为入基变量，从此值可知b1/a11

40、=50为最小正数，因此，s1为出基变量，a11为主元，继续迭代如下表所示。从上表中可知第二次迭代得到的基本可行解为x1=50,x2=250,s1=0,s2=50, s3=0,这时z=27500。由于检验数都0= l x(l)主元素： alk 新单纯表：pk=单位向量注：当所有检验数j 0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。i=1m第一百二十四张，PPT共二百九十页，创作于2022年6月单纯形法的计算步骤例 用单纯形法求解解：将数学模型化为标准形式：不难看出x4、x5可作为初始基变量，列单纯形表计算。第一百二十五张，PPT共二百九十页，创作于2022年6月单纯形法的

41、计算步骤20 x221/3150120753017131/309022560 x111017/31/31250128/9-1/92/335/300-98/9-1/9-7/3第一百二十六张，PPT共二百九十页，创作于2022年6月 2 1 0 0 0 0 15 0 5 1 0 0 0 24 6 2 0 1 0 0 5 1 1 0 0 1 2 1 0 0 0 练习:一般主列选择正检验数中最大者对应的列,也可选择其它正检验数的列.以第2列为主列,用单纯形法求解。正检验数对应的列为主列第一百二十七张，PPT共二百九十页，创作于2022年6月结束2.4 单纯形法的计算步骤第一百二十八张，PPT共二百九十

42、页，创作于2022年6月2.5.1 单纯形法的进一步讨论一、大M法二、两阶段法-人工变量法第一百二十九张，PPT共二百九十页，创作于2022年6月人工变量法问题：线性规划问题化为标准形时，若约束条件的系数矩阵中不存在单位矩阵，如何构造初始可行基？ 第一百三十张，PPT共二百九十页，创作于2022年6月人工变量法加入人工变量设线性规划问题的标准型为：第一百三十一张，PPT共二百九十页，创作于2022年6月 加入人工变量,构造初始可行基. 人工变量法系数矩阵为单位矩阵，可构成初始可行基。第一百三十二张，PPT共二百九十页，创作于2022年6月 约束条件已改变，目标函数如何调整？人工变量法第一百三十

43、三张，PPT共二百九十页，创作于2022年6月“惩罚” 人工变量！（1）大M法（2）两阶段法第一百三十四张，PPT共二百九十页，创作于2022年6月一、大 M 法人工变量在目标函数中的系数为 -M, 其中，M 为任意大的正数。目标函数中添加“罚因子”-M（M是任意大的正数）为人工变量系数，只要人工变量0，则目标函数不可能实现最优。第一百三十五张，PPT共二百九十页，创作于2022年6月例: 求解线性规划问题一、大 M 法第一百三十六张，PPT共二百九十页，创作于2022年6月 一、大 M 法解:加入松弛变量和剩余变量进行标准 化, 加入人工变量构造初始可行基. 第一百三十七张，PPT共二百九十

44、页，创作于2022年6月求解结果出现检验数非正若基变量中含非零的人工变量， 则无可行解； 否则，有最优解。一、大 M 法用单纯形法求解（见下页）。目标函数中添加“罚因子”-M为人工变量系数，只要人工变量0，则目标函数不可能实现最优。第一百三十八张，PPT共二百九十页，创作于2022年6月 1 -2 1 -4 1 2 -2 0 1 3-6M M -1 3M-1 3 -1 -1 x1 x2 x3 0 x4 11 -M x6 3 -M x7 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 11 3/2 1 0 0 1 0 0 1 0 0 - M

45、- M x6 x7 表1（初始单纯形表）一、大 M 法（单纯形法求解）第一百三十九张，PPT共二百九十页，创作于2022年6月 3 -2 0 0 1 0 -2 0 1 1 M-1 0 3 -1 -1x1 x2 x3 0 x4 10 -M x6 1 -1 x3 1C j - Z j C j CB XB b 1 0 0 -1 0 0 0 -M 0 0 x4 x5 1 0 -1 1 -2 0 1 0 1-3M - M - M x6 x7 一、大 M 法（单纯形法求解）表2第一百四十张，PPT共二百九十页，创作于2022年6月 3 0 0 0 1 0 -2 0 1 1 0 0 3 -1 -1 x1 x

46、2 x3 0 x4 12 -1 x2 1 -1 x3 1C j - Z j C j CB XB b 1 -2 0 -1 0 0 0 -1 0 0 x4 x5 4 i 2 -5 1 -2 0 1 1-M -1 -M - M - M x6 x7 表3一、大 M 法（单纯形法求解）第一百四十一张，PPT共二百九十页，创作于2022年6月 1 0 0 0 1 0 0 0 1 0 0 0 3 -1 -1 x1 x2 x3 3 x1 4 -1 x2 1 -1 x3 9 2 C j CB XB b1/3 -2/3 0 -1 2/3 -4/3 -1/3 -1/3 0 0 x4 x5 2/3 -5/3 1 -2

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

48、一百四十三张，PPT共二百九十页，创作于2022年6月【解】首先将数学模型化为标准形式式中x4，x5为松弛变量，x5可作为一个基变量，第一、三约束中分别加入人工变量x6、x7，目标函数中加入Mx6Mx7一项，得到人工变量单纯形法数学模型用前面介绍的单纯形法求解，见下表。 1.5 单纯形法 Simplex Method第一百四十四张，PPT共二百九十页，创作于2022年6月Cj32100MMbCBXBx1x2x3x4x5x6x7M0Mx6x5x74123121211000101000014101j3-2M2+M-1+2MM000M01x6x5x3632532001100010100381j5-6

49、M5M0M00201x2x5x36/53/52/51000011/53/52/50103/531/511/5j50000231x2x1x301010000111025/32/31331/319/3j0005-25/3第一百四十五张，PPT共二百九十页，创作于2022年6月（2）初始表中的检验数有两种算法，第一种算法是利用第一、三约束将x6、x7的表达式代入目标涵数消去x6和x7，得到用非基变量表达的目标函数，其系数就是检验数；第二种算法是利用公式计算，如最优解X（31/3，13，19/3，0，0)T；最优值Z152/3注意：1.5 单纯形法 Simplex Method(1) M是一个很大的抽

50、象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值第一百四十六张，PPT共二百九十页，创作于2022年6月【例1-21】求解线性规划 【解】加入松驰变量x3、x4化为标准型在第二个方程中加入人工变量x5，目标函数中加上M x5一项，得到 1.5 单纯形法 Simplex Method第一百四十七张，PPT共二百九十页，创作于2022年6月用单纯形法计算如下表所示。 Cj5800MbCBXBx1x2x3x4x50Mx3x5311210010164j5M8+2M0M05Mx1x5101/37/31/31/3010122j029/3+7/3M5/3+1/3MM01.5 单纯形法

51、Simplex Method第一百四十八张，PPT共二百九十页，创作于2022年6月表中j0，j=1，2，5，从而得到最优解X=（2，0，0，0，2）， Z=10+2M。但最优解中含有人工变量x50说明这个解是伪最优解，是不可行的，因此原问题无可行解。1.5 单纯形法 Simplex Method第一百四十九张，PPT共二百九十页，创作于2022年6月M在计算机上处理困难。分阶段处理先求初始基，再求解。二、两阶段法第一百五十张，PPT共二百九十页，创作于2022年6月二、两阶段法第一阶段: 构造如下的线性规划问题人工变量的系数矩阵为单位矩阵，可构成初始可行基。 目标函数仅含人工变量，并要求实现

52、最小化。 若其最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。第一百五十一张，PPT共二百九十页，创作于2022年6月 用单纯形法求解上述问题,若=0,进入第二阶段,否则,原问题无可行解。第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。 用单纯形法求解即可。二、两阶段法下面举例说明，仍用大M法的例。第一百五十二张，PPT共二百九十页，创作于2022年6月例：二、两阶段法第一百五十三张，PPT共二百九十页，创作于2022年6月 二、两阶段法构造第一阶段问题并求解解：用单纯形法求解第一百五十四张，PPT共二百九十页，创作于2022年6月二、两

53、阶段法（第一阶段、求min ） 1 -2 1 -4 1 2 -2 0 1 -6 1 3 0 0 0 x1 x2 x3 0 x4 11 -1 x6 3 -1 x7 1 C i CB XB b 1 0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 - 1 x4 x5 x6 0 11 0 3/2 1 1 0 - 1 x7 i 表1第一百五十五张，PPT共二百九十页，创作于2022年6月 -1 - -2 1 1 - -3 - 1 x7 3 -2 0 0 1 0 -2 0 1 0 1 0 0 0 0 x1 x2 x3 0 x4 10 -1 x6 1 0 x3 1 C i CB XB b 1

54、0 0 0 -1 1 0 0 0 0 -1 0 0 0 -1 x4 x5 x6二、两阶段法（第一阶段、求min ）表2第一百五十六张，PPT共二百九十页，创作于2022年6月 -5 4 -2 - 1 - -1 - 1 x7 3 0 0 0 1 0 -2 0 1 0 0 0 0 0 0 x1 x2 x3 0 x4 12 0 x2 1 0 x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 -1 0 0 -1 x4 x5 x6二、两阶段法（第一阶段、求min ）表3：最终单纯形表第二阶段不含人工变量且=0第一百五十七张，PPT共二百九十页，创作于2022年6月二、两阶

55、段法第二阶段 将去掉人工变量，还原目标函数系数，做出初始单纯形表。 3 0 0 0 1 0 -2 0 1 3 -1 -1 x1 x2 x3 0 x4 12 -1 x2 1 -1 x3 1 C i CB XB b 1 -2 2 0 -1 1 0 0 0 0 0 x4 x5 1 0 0 0 -1第一百五十八张，PPT共二百九十页，创作于2022年6月二、两阶段法 1 0 0 0 1 0 0 0 1 3 -1 -1 x1 x2 x3 3 x1 4 -1 x2 1 -1 x3 9 C i CB XB b 1/3 -2/3 0 -1 2/3 -4/3 0 0 x4 x5 第二阶段 0 0 0 -1/3

56、-1/3最优解为目标函数值 z=2第一百五十九张，PPT共二百九十页，创作于2022年6月【例1-22】用两阶段单纯形法求解例19的线性规划。【解】标准型为在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为用单纯形法求解，得到第一阶段问题的计算表如下：1.5 单纯形法 Simplex Method第一百六十张，PPT共二百九十页，创作于2022年6月Cj0000011 bCBXBx1x2x3x4x5x6x7101x6x5x74123121211000101000014101j2121000100 x6x5x3632532001100010100381j650100000 x2x5x3

57、6/53/52/51000011/53/52/50103/531/511/5j000001.5 单纯形法 Simplex Method第一百六十一张，PPT共二百九十页，创作于2022年6月最优解为 最优值w=0。第一阶段最后一张最优表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为1.5 单纯形法 Simplex Method第一百六十二张，PPT共二百九十页，创作于2022年6月Cj32-100bCBXBx1x2x3x4x5201x2x5x3100001010j50000231x2x1x3010100001110213j0005Cj32100bCBX

58、Bx1x2x3x4x5201x2x5x36/53/52/51000011/53/52/50103/531/5 11/5j5 0000231x2x1x301010000111025/32/31331/319/3j000525/3用单纯形法计算得到下表最优解X（31/3，13，19/3，0，0)T；最优值Z152/31.5 单纯形法 Simplex Method第一百六十三张，PPT共二百九十页，创作于2022年6月【例1-23】用两阶段法求解例1-21的线性规划。【解】例1-21的第一阶段问题为用单纯形法计算如下表：1.5 单纯形法 Simplex Method第一百六十四张，PPT共二百九十页

59、，创作于2022年6月Cj00001bCBXBx1x2x3x4x501x3x5311210010164j1201001x1x5101/37/31/31/3010122j07/31/310j0,得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值w=20,x5仍在基变量中,从而原问题无可行解。1.5 单纯形法 Simplex Method第一百六十五张，PPT共二百九十页，创作于2022年6月解的判断唯一最优解的判断：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解 多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解。 无界解的判断: 某个k0且ai

60、k（i=1，2,m）则线性规划具有无界解退化基本可行解的判断:存在某个基变量为零的基本可行解。无可行解的判断：(1)当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。(2) 当第一阶段的最优值w0时，则原问题无可行解。1.5 单纯形法 Simplex Method第一百六十六张，PPT共二百九十页，创作于2022年6月单纯形法计算中的几个问题1、目标函数极小化时解的最优性判断 只需用检验数 作为最优性的标志。2、无可行解的判断 当求解结果出现所有 时，如基变量仍 含有非零的人工变量（两阶段法求解时第一阶 段目标函数值不等于0），则问题无可行解。第一百六十七张，PPT共二