线性规划线性规划问题单纯形法幻灯片.ppt

线性规划线性规划问题单纯形法1第1页，共112页，编辑于2022年，星期二第一讲第一讲第一讲第一讲第二章第二章 线性规划及图解法线性规划及图解法第2页，共112页，编辑于2022年，星期二问题的提出问题的提出n解决有限资源在有竞争的使用方向中如何进行最佳分配。解决有限资源在有竞争的使用方向中如何进行最佳分配。n线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自之一。自1947年旦茨基（年旦茨基（G.B.Dantzig）提出了一般线性规划问题求）提出了一般线性规划问题求解的方法解的方法单纯形法（单纯形法（simplex method）之后，线性规划已）之后，线性规划已被广泛应用于解决经济管理和工业生产中遇到的实际问题。被广泛应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界调查表明，在世界500家最大的企业中，有家最大的企业中，有85%的企业都曾使的企业都曾使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。用为应用者节约了数以亿万计的资金。线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）第3页，共112页，编辑于2022年，星期二q本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，本讲中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本概念和图解方法。基本概念和图解方法。q线性规划问题是什么样的一类问题呢？线性规划问题是什么样的一类问题呢？请看案例请看案例-线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）第4页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。案案 例例 河流污染治理规划问题河流污染治理规划问题第5页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。工厂工厂2 2工厂工厂3 3工厂工厂1 1工厂工厂4 4工厂工厂5 5工厂工厂6 6工厂工厂9 9工厂工厂8 8工厂工厂7 7案案 例例 河流污染治理规划问题河流污染治理规划问题第6页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。今日认识未为晚，今日认识未为晚，吾辈齐心治环境吾辈齐心治环境;线性规划大有用，线性规划大有用，定让江水绿如蓝。定让江水绿如蓝。工厂工厂2 2工厂工厂3 3工厂工厂1 1工厂工厂4 4工厂工厂5 5工厂工厂6 6工厂工厂9 9工厂工厂8 8工厂工厂7 7案案 例例 河流污染治理规划问题河流污染治理规划问题第7页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）今日认识未为晚，今日认识未为晚，吾辈齐心治环境吾辈齐心治环境;线性规划大有用，线性规划大有用，定让江水绿如蓝。定让江水绿如蓝。曾几何时长江水，曾几何时长江水，哺育华夏代代人哺育华夏代代人;谁知后代疏珍惜，谁知后代疏珍惜，清清江水黑如泥。清清江水黑如泥。工厂工厂2 2工厂工厂3 3工厂工厂1 1工厂工厂4 4工厂工厂5 5工厂工厂6 6工厂工厂9 9工厂工厂8 8工厂工厂7 7案案 例例 河流污染治理规划问题河流污染治理规划问题第8页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）案案 例例 河流污染治理规划问题河流污染治理规划问题n背景资料背景资料:n长江流域某区域内有长江流域某区域内有9化工厂，各厂每月产生的工业污水量如表化工厂，各厂每月产生的工业污水量如表-1，流，流经各化工厂的河流流量如表经各化工厂的河流流量如表-2，各化工厂治理工业污水的成本如表，各化工厂治理工业污水的成本如表-3。上游厂排放的污水流到相邻下游厂以前，有上游厂排放的污水流到相邻下游厂以前，有20%可自然净化。可自然净化。根据环根据环保标准河流中此种工业污水的含量不应超过保标准河流中此种工业污水的含量不应超过0.2%。从该区域整体考虑，。从该区域整体考虑，各化工厂应该分别处理多少工业污水才能既满足环保要求，又使各化工厂应该分别处理多少工业污水才能既满足环保要求，又使9化工化工厂治理工业污水的总费用最少。厂治理工业污水的总费用最少。第9页，共112页，编辑于2022年，星期二q背景资料背景资料:线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）化工厂化工厂1 11.2化工厂化工厂4 42化工厂化工厂7 72化工厂化工厂2 21化工厂化工厂5 51化工厂化工厂8 80.8化工厂化工厂3 33化工厂化工厂6 61化工厂化工厂9 91.5表表-1 -1 污水产生量污水产生量 单位：万单位：万m m3 3表表-2 -2 流经各化工厂的河流流量流经各化工厂的河流流量 单位：万单位：万m m3 3表表-3 -3 治理工业污水的成本治理工业污水的成本 单位：百万元单位：百万元/万万m m3 3化工厂化工厂1 1500化工厂化工厂4 41200化工厂化工厂7 71200化工厂化工厂2 2300化工厂化工厂5 5600化工厂化工厂8 8200化工厂化工厂3 31800化工厂化工厂6 6400化工厂化工厂9 9700化工厂化工厂1 13化工厂化工厂4 44化工厂化工厂7 71化工厂化工厂2 25化工厂化工厂5 55化工厂化工厂8 82化工厂化工厂3 32化工厂化工厂6 66化工厂化工厂9 93第10页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）194582637q问题分析：问题分析：q区域污染治理的决策区域污染治理的决策各个化工厂应处理的工业污水量（或应排各个化工厂应处理的工业污水量（或应排放的工业污水量）。放的工业污水量）。q区域污染治理的约束区域污染治理的约束即满足环保要求排放工业污水（区域内河即满足环保要求排放工业污水（区域内河流中任何点检测都应符合环保标准）。流中任何点检测都应符合环保标准）。q区域污染治理的目标区域污染治理的目标总治理成本最少。总治理成本最少。第11页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）194582637q模型描述：模型描述：q设第设第i个化工厂应处理的工业污水量为个化工厂应处理的工业污水量为Xi万万m3，则根据问题描述的情，则根据问题描述的情况以化工厂况以化工厂1、2、9 加以分析则可得如下近似关系式加以分析则可得如下近似关系式q对化工厂对化工厂2应有应有-（1-X2）/300 0.2%q对化工厂对化工厂8应有应有-（0.8-X8）/200 0.2%q对化工厂对化工厂1应有应有-（1.2-X1）+0.8（1-X2）+（0.8-X8）/500 0.2%第12页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）194582637q对对化工厂化工厂9应有应有 （1.5-X9）/700 0.2%q对对化工厂化工厂7应有应有 （2-X7）+0.8（1.5-X9）/1200 0.2%q此外显然还应有此外显然还应有 Xi 0（i=1，2，3 8，9）q综上所述决策者所需考虑的区域内各个化工厂应处理的工业污综上所述决策者所需考虑的区域内各个化工厂应处理的工业污水量水量 Xi应满足上述所有不等式方程。我们将这些不等式方程构成应满足上述所有不等式方程。我们将这些不等式方程构成的方程组称为污水治理的约束条件。的方程组称为污水治理的约束条件。第13页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）194582637另一方面污水治理的总成本可表示为另一方面污水治理的总成本可表示为Z（单位：百万元）（单位：百万元）Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9 而决策者的目标是：而决策者的目标是：确定满足约束条件的确定满足约束条件的Xi使得使得Z取得最小值。取得最小值。将上述分析归纳后即可得如下数学符合模型：将上述分析归纳后即可得如下数学符合模型：第14页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）河流污染治理规划问题河流污染治理规划问题数学模型（整理之后）数学模型（整理之后）194582637Min Z=3X1+5X2+2X3+4X4+5X5+6X6+1X7+2X8+3X9 X2 0.4 X8 1.6 X1+0.8X2 +0.8X8 4.4 X9 0.1 X7 +0.8 X9 0.8 X4 +0.8X7 +0.64X9 2.16 X6 0.2 X5 +0.8X6 0.6 X3+0.8X4 +0.8X5 +0.64X6+0.64X7 +5.12X9 9.4 Xi 0（i=1，2，3，4，5，6，7，8，9）s.t.第15页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）线性规划模型线性规划模型 Linear Programming Model 或或 Linear Optimization Model 用线性规划方法解决实际经济与管理问题的第一步是分析用线性规划方法解决实际经济与管理问题的第一步是分析建立能够完整描述和反映实际问题的线性规划模型。建立能够完整描述和反映实际问题的线性规划模型。第16页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）通常建立通常建立LP模型有以下几个基本步骤：模型有以下几个基本步骤：1)确定决策变量：确定决策变量：决策变量是模型要确定的未知变量，决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制也是模型最重要的参数，是决策者解决实际问题的控制变量。变量。2)确定目标函数：确定目标函数：目标函数决定线性规划问题的优化方向，目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据目标函数的实质确定优化方向，量的一个线性函数，并根据目标函数的实质确定优化方向，一般可为最大化（一般可为最大化（max）或最小化（）或最小化（min）。）。第17页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）通常建立通常建立LP模型有以下几个步骤：模型有以下几个步骤：3)确定约束方程：确定约束方程：一个正确的线性规划模型应能通过一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组制，这些限制通过一系列线性等式或不等式方程组来描述。来描述。4)变量取值限制：变量取值限制：一般情况下，决策变量取正值（非一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即负值）。因此，模型中应有变量的非负约束即Xj0，但要注意也存在例外的情形。但要注意也存在例外的情形。第18页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）线性规划的一般形式线性规划的一般形式:max（或（或min）z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn（=）b1 a21x1+a22x2+a2nxn（=）b2 s.t.am1x1+am2x2+amnxn（=）bm xj 0 （j=1，2 n）第19页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）线性规划问题的标准形式线性规划问题的标准形式1、目标函数极大化、目标函数极大化“max”2、等式约束条件、等式约束条件“=”且右端常数且右端常数bi非负非负3、变量非负、变量非负“xj 0”max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn =b1 a21x1+a22x2+a2nxn =b2 s.t.am1x1+am2x2+amnxn =bm xj 0 （j=1，2 n）第20页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）化标准形式的一般步骤化标准形式的一般步骤1)目标函数极小化目标函数极小化“极大化极大化”2)约束条件的右端项约束条件的右端项 bi0 “bi0”3)约束条件为不等式约束条件为不等式 或或 “=”4)取值无约束（自由）变量取值无约束（自由）变量“非负变量非负变量”5)取值非正变量取值非正变量“非负变量非负变量”线性规划问题的标准形式的作用线性规划问题的标准形式的作用为单纯形法求解作准备！为单纯形法求解作准备！第21页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）线性规划问题的求解：（图解）线性规划问题的求解：（图解）如何求解一般的线性规划呢？如何求解一般的线性规划呢？下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两个决策变量的线性规划只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。初学者窥探线性规划基本原理和几何意义等优点。第22页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念例例1（page 11）max z=2x1+x2 5x2 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 0第23页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念max z=2x1+x2 5x2 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 0唯一最优解唯一最优解 X=（9/2，3/2）第24页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念例例 max Z=2X1+X2 X1+1.9X2 3.8 X1 -1.9X2 3.8 s.t.X1+1.9X2 10.2 X1 -1.9X2 -3.8 X1 ，X2 0第25页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念max Z=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）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域第26页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念max Z=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 max Z min Z（3.8，4）34.2=3X1+5.7X2 绿色线段上的所有点都是最绿色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域第27页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念min Z=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 max Z min Z 8=5X1+4X2 43=5X1+4X2（0，2）可行域可行域此点是唯一最优解此点是唯一最优解第28页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念min Z=5X1+4X2x1x2oD可行域可行域第29页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念max Z=5X1+4X2x1x2oD可行域可行域 max Z min Z最优解目标值最优解目标值Z趋于无穷趋于无穷第30页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念max Z=5X1+4X2x1x2o可行解域为空可行解域为空第31页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）基本概念基本概念图解法的启示图解法的启示1)线性规划问题解的可能情况线性规划问题解的可能情况 a.唯一最优解唯一最优解 b.无穷多最优解无穷多最优解 c.无解（没有有界最优解，无可行解）无解（没有有界最优解，无可行解）2)若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题的可行域非空，则可行域是一个凸集；3)若线性规划问题的最优解存在，则一定可以在可行域的凸集的某若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。个顶点上达到。第32页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法 单纯形方法是单纯形方法是G.B.Danzig于于1947年首先发明的。近年首先发明的。近50年来，一直是年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。解。本节讨论单纯形法的基本概念、原理及算法。第33页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法给定线性规划问题（标准形式）给定线性规划问题（标准形式）max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn =b1 a21x1+a22x2+a2nxn=b2 s.t.am1x1+am2x2+amnxn =bm xj 0 （j=1，2 n）第34页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法一、线性规划问题的解的概念一、线性规划问题的解的概念 可行解可行解 最优解最优解 基基 基解（基本解）基解（基本解）基可行解基可行解 可行基可行基第35页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法二、凸集及其顶点二、凸集及其顶点 凸集凸集 顶点（极点）顶点（极点）凸集凸集凹集凹集第36页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）12345678基解（基解（可行可行）基解（基解（不可行不可行）第37页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法三、线性规划基本定理三、线性规划基本定理基本定理基本定理 1 线性规划所有可行解组成的集合线性规划所有可行解组成的集合S=X|AX=b，X 0 是是凸集凸集。基本定理基本定理 2 X是线性规划问题的基本可行解的充要条件为是是线性规划问题的基本可行解的充要条件为是 X 是凸集是凸集S=X|AX=b，X 0 的的极点极点。基本定理基本定理 3 给定线性规划问题，给定线性规划问题，A是秩为是秩为 m 的的 mn 矩阵，矩阵，（i）若线性规划问题存在可行解，则必存在基本可行解若线性规划问题存在可行解，则必存在基本可行解 （ii）若线性规划问题存在有界最优解，则必存在有界最优若线性规划问题存在有界最优解，则必存在有界最优基本可行解。基本可行解。第38页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法单纯形法迭代原理及其思路单纯形法迭代原理及其思路单纯形法的初步讨论单纯形法的初步讨论例例1.8 求解求解LP问题问题 化为化为标准型标准型Max Z=50X1+30X2s.t.4X1+3X2 120 2X1+X2 50 X1，X2 0Max Z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2+X4=50 X1，X2，X3，X4 0（1.18）第39页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法 此线性规划问题此线性规划问题转化为了一个含有四个变量的标准形线性规划转化为了一个含有四个变量的标准形线性规划问题，问题，X3，X4为松弛变量。为求解上面的为松弛变量。为求解上面的LP问题，我们要考虑满足问题，我们要考虑满足约束条件约束条件s.t.并使并使 Z 取得取得Max的的X1，X2，X3，X4的值，由此分析如下的值，由此分析如下-第40页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法确定初始基可行解：确定初始基可行解：通过观察可以发现，松弛变量通过观察可以发现，松弛变量X3和和X4对应的等式对应的等式约束条件中的约束条件中的系数矩阵为单位矩阵可以作为系数矩阵为单位矩阵可以作为初始初始可行基可行基矩阵矩阵。因此。因此取取 X3，X4为基变量；为基变量；X1，X2为非基变量。则（为非基变量。则（1.181.18）可变为：）可变为：Max Z=50X1+30X2 s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 （1.191.19）X1，X2，X3，X40第41页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法典式典式（1.191.19）或）或（1.181.18）称为关于基的称为关于基的典式典式 1、等式等式约束条件中显含约束条件中显含基可行解基可行解 2、目标函数中不、目标函数中不含含基基变量变量Max Z=50X1+30X2s.t.4X1+3X2+X3 =120 2X1+X2+X4=50 (1.18)X1，X2，X3，X4 0Max Z=50X1+30X2s.t.X3 =120-4X1-3X2 X4=50-2X1 -X2 （1.19）X1，X2，X3，X40第42页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法 在典式在典式（1.19）中令：中令：X1=X2=0，我们得到一个我们得到一个基本可行解基本可行解 X1=（X1，X2，X3，X4）T=（0，0，120，50）T，其对应的目标函数值其对应的目标函数值 Z1=50X1+30X2=0第43页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法最优性检验：最优性检验：基本可行解基本可行解 X1 是最优解吗？显然不是。应寻找更好的解。是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式从问题的数学角度分析，在典式（1.191.19）的目标函数中，的目标函数中，非基变量非基变量X1，X2前的系数都为正，而此时的前的系数都为正，而此时的X1，X2均取零值，表明只要增加均取零值，表明只要增加其值，则其值，则目标函数值有增加的可能。因此，将目标函数中目标函数值有增加的可能。因此，将目标函数中系数为正的系数为正的某一某一非基变量非基变量与某一与某一基变量基变量地位地位对换对换。第44页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法换基迭代：换基迭代：进行换基就是要从非基变量中选一个变量进行换基就是要从非基变量中选一个变量入基入基，再从基变量中选，再从基变量中选一个变量一个变量出基出基。并且换基后仍需满足：。并且换基后仍需满足：1)新的解仍是基本可行解；新的解仍是基本可行解；2)目标函数值将得到改善。目标函数值将得到改善。第45页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法选择入基变量：选择入基变量：由于在目标函数由于在目标函数 Z1=50X1+30X2 中中X1，X2的系数都为的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。入基。选择出基变量：选择出基变量：X1入基后，其值从零增加并由于约束条件的原因会引入基后，其值从零增加并由于约束条件的原因会引起其他变量的变化。由起其他变量的变化。由典式典式（1.19）以及变量必须取正值（可行）的条）以及变量必须取正值（可行）的条件，我们可以得到下列不等式关系：件，我们可以得到下列不等式关系：X3 =120-4X1-3X2 0 X4=50-2X1-X2 0第46页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法 因为迭代后因为迭代后X2仍为非基变量（仍会令其取值为零），则上式可简仍为非基变量（仍会令其取值为零），则上式可简化为：化为：120-4X1 0，且，且 50-2X1 0，由此可以看出，虽然我们希望由此可以看出，虽然我们希望X1入基后取正值，取值越大目标值增入基后取正值，取值越大目标值增加越大，但是加越大，但是 X1又得受到以上约束（保证其可行）。又得受到以上约束（保证其可行）。显然，当取显然，当取 X1=min（120/4，50/2）=25时，才能使上述不等时，才能使上述不等式成立，且此时恰使基变量式成立，且此时恰使基变量X4变为零，这正好满足非基变量必须取变为零，这正好满足非基变量必须取值零的条件，所以可令值零的条件，所以可令X4 出基，这样，新的基变量变为出基，这样，新的基变量变为X3，X1，而而 X2，X4 成了非基变量，则成了非基变量，则第47页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法约束方程变为：约束方程变为：4X1+X3 =120-3X2 2X1 =50-X2 -X4化简后得：新的化简后得：新的典式典式方程方程 X3 =20-X2 +2X4 X1 =25-0.5X2 -0.5X4第48页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法代入目标函数可得：代入目标函数可得：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.5X4 X2 =20-X3+2X4 Z3=1350-5X3-15X4第49页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法单纯形法第三个第三个基本可行解基本可行解 X3=（15，20，0，0）T，其对应的目标函数值，其对应的目标函数值 Z3=1350。此时松弛变量。此时松弛变量 都是都是非基变量（取值为零），这表非基变量（取值为零），这表明资源已用明资源已用尽；并且目标函数值尽；并且目标函数值 Z3 =1350-5X3-15X4中中非基变量非基变量X3，X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。是最优解。第50页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形法小结：单纯形法小结：单纯形法是这样一种单纯形法是这样一种迭代算法迭代算法如下图如下图当当 Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系数全为负值时，这时的基本可行解基本可行解 Xk 即是即是 线性规划问题的最优解，线性规划问题的最优解，迭代结束。迭代结束。X1Z1保持保持单调增单调增保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持可行可行性性保持保持单调增单调增保持保持单调增单调增保持保持单调增单调增X2X3.XkZ2Z3.Zk 当当 Zk 中中非基变量非基变量的系数的系数全为负值时，这时的的系数的系数全为负值时，这时的基本可行解基本可行解 Xk 即是线性规划问题的最优解，即是线性规划问题的最优解，迭代结束。迭代结束。第51页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形表单纯形表对于给定的线性规划问题：对于给定的线性规划问题：max Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2s.t.am1x1+am2x2+amnxn bm xj 0 （j=1，2 n）对此问题添加对此问题添加m个松弛变量后，可得下面线性规划问题并且是典式个松弛变量后，可得下面线性规划问题并且是典式的形式。的形式。第52页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形表单纯形表线性规划的典式线性规划的典式max Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn+xn+1 =b1 a21x1+a22x2+a2nxn +xn+2 =b2s.t.am1x1+am2x2+amnxn +xn+m =bm xj 0 （j=1，2 n，n+1，n+2，n+m）第53页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形表：单纯形表：将上面将上面典式中各变量及系数填写在一张表格中就形成下面的典式中各变量及系数填写在一张表格中就形成下面的单纯形表单纯形表cj c1 c2 cn cn+1 cn+2 cn+m CB基基解解 x1 x2 xn xn+1 xn+2 xn+m0000 xn+1xn+2xn+m b1 b2 bm a11 a12 a1n 1 a21 a22 a2n 1 am1 am2 amn 1 1 2 m j=cj zj c1 c2 cn 0 0 0 j=cj zj 1 2 n n+1 n+2 n+m 第54页，共112页，编辑于2022年，星期二线性规划线性规划线性规划线性规划 Linear ProgrammingLinear Programming（LPLP）单纯形表：单纯形表：上面上面的的单纯形表还可以表示成矩阵的形式单纯形表还可以表示成矩阵的形式基基解解 X XS