线性规划与单纯形法.ppt

《线性规划与单纯形法.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形法.ppt（129页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数学模型线性规划问题及其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤n单纯形法的进一步讨论单纯形法的进一步讨论n数据包络分析数据包络分析第一节第一节 线性规划问题及其数学模型线性规划问题及其数学模型 线性规划在经营管理中，常常用来解决线性规划在经营管理中，常常用来解决有限资源（人、财、物）的合理分配问题。有限资源（人、财、物）的合理分配问题。在经营管理中，几乎一切问题都与有限资源在经营管理中，几乎一切问题都与有限资源的合理分配利用有关。线性规划为解决有限的合理分配利用有关。线性规

2、划为解决有限资源的合理分配利用提供了一个有效的数学资源的合理分配利用提供了一个有效的数学工具。工具。建立线性规划数学模型是解决线性规划问题的建立线性规划数学模型是解决线性规划问题的一个重要步骤。一个重要步骤。建立的线性规划数学模型是否真正的反映客观建立的线性规划数学模型是否真正的反映客观实际，数学模型本身是否正确，都直接影响求解结实际，数学模型本身是否正确，都直接影响求解结果，从而影响决策结果，所以，建立正确的线性规果，从而影响决策结果，所以，建立正确的线性规划模型尤为重要。下面举例说明线性规划数学模型划模型尤为重要。下面举例说明线性规划数学模型的建立。的建立。一、线性规划数学模型的建立一、线

3、性规划数学模型的建立某厂利用某厂利用A A、B B两种原料，生产甲、乙两种产品，有关数据如下：两种原料，生产甲、乙两种产品，有关数据如下：例例1 1：（产品组合问题）：（产品组合问题）产品名称产品名称甲甲 乙乙单位产品单位产品消耗原料消耗原料原料名称原料名称可供利用的原料可供利用的原料数量（数量（T/T/日）日）6 68 81 21 22 12 1A AB B产品售价产品售价 （千元（千元/T/T）3 2 3 2根据市场调查，有如下资料：根据市场调查，有如下资料：1.1.乙产品的需求量至多乙产品的需求量至多 2 T/2 T/日日;2.2.乙产品的需求量比甲产品的需求量至多大乙产品的需求量比甲产

4、品的需求量至多大 1 T/1 T/日。日。求该厂产值最大的求该厂产值最大的生产方案生产方案。提出三个问题大家考虑：提出三个问题大家考虑：1.1.问题的未知数是什么？问题的未知数是什么？设未知数设未知数2.2.以什么准则进行决策？以什么准则进行决策？目标函数目标函数3.3.约束条件是什么？约束条件是什么？约束方程约束方程这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。这里生产方案指的是如何安排甲、乙产品的产量。显然，产量是未知数。设：甲产品的产量为设：甲产品的产量为 x x1 1 T/T/日日 乙产品的产量为乙产品的产量为 x x2 2 T/T/日日 决策准则是产值最大，用决策准

5、则是产值最大，用 Z Z 代表产值，则有：代表产值，则有：Z=3x Z=3x1 1+2x+2x2 2 Z Z 是是x x1 1、x x2 2 的函数，称为目标函数，目标是求极大值，的函数，称为目标函数，目标是求极大值，即：即：max Z=3xmax Z=3x1 1+2x+2x2 2 约束条件（分三部分：资源限制、市场限制、非负限制）约束条件（分三部分：资源限制、市场限制、非负限制）x x1 1+2x+2x2 266 2x 2x1 1+x+x2 288 x x2 222 x x2 2-x-x1 111 x x1 1，x x2 200约束条件资源限制资源限制市场限制市场限制非负限制非负限制2万m3

6、1.4万m32万m31.4万m3整理得数学模型：整理得数学模型：目标函数：目标函数：min min z z=1000 =1000 x1+800+800 x2约束条件：约束条件：.x1 1 1 x1+x2 x1 2 2 x2 x1 0 0，x2 0 0例例3、配料问题（、配料问题（min,)设设 x1,x2分别代表每粒胶丸分别代表每粒胶丸中甲、乙两种原料的用量中甲、乙两种原料的用量某厂生产一种胶丸，已知如下资料：某厂生产一种胶丸，已知如下资料：例例4、合理下料问题、合理下料问题用长的钢筋，分别截取、各至少用长的钢筋，分别截取、各至少100根，要求用料最少。根，要求用料最少。设设 xj 分别代表采

7、用切割方案分别代表采用切割方案18所需米的所需米的钢筋的数量。钢筋的数量。二、线性规划问题的共同特征二、线性规划问题的共同特征 每一个问题都用一组决策变量每一个问题都用一组决策变量(x x1 1，x x2 2，x xn n)表示某表示某一方案；这组决策变量的值就代表一个具体方案。一般一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。这些变量取值都是非负的。存在一定的约束条件，这些约束条件可以用一组线性存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。等式或线性不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函都有一个要求达到的目标，它可用决策

8、变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化函数实现最大化或最小化。三、线性规划数学模型的一般表示方式三、线性规划数学模型的一般表示方式 求解线性规划问题的任务是：在满求解线性规划问题的任务是：在满足约束条件的所有足约束条件的所有(x x1 1，x x2 2，x xn n)（可（可行解）中求出使目标函数达到最大行解）中求出使目标函数达到最大(小小)z z 值的决策变量值值的决策变量值(x x1 1*，x x2 2*，x xn n*)（最（最优解）。优解）。1.和式和式2.向量式向量式3.矩阵式矩阵式课堂作业：

9、建立线性规划模型课堂作业：建立线性规划模型 某城市在一昼夜间，市内交通需要车辆数如图，对车某城市在一昼夜间，市内交通需要车辆数如图，对车辆的需求在昼夜间是变化的，车辆的工作制度是一天连续辆的需求在昼夜间是变化的，车辆的工作制度是一天连续工作工作8 8小时，派车时间在各时间间隔的端点，一旦派出，就小时，派车时间在各时间间隔的端点，一旦派出，就连续工作连续工作8 8小时。求保证需要的最小车辆数。小时。求保证需要的最小车辆数。车辆数时间04712162024481248121084 派车时间在各时间间隔的端点，一旦派出，就连续工派车时间在各时间间隔的端点，一旦派出，就连续工作作8小时。小时。设：各时

10、间间隔所派车辆数为设：各时间间隔所派车辆数为xj j=1，2，6则有：则有：min Z=x1+x2+x3+x4+x5+x6 x1+x64 x1+x28 x2+x3 10 x3+x47 x4+x512 x5+x6 4 x1，x2，x3，x4，x5，x6 0第二章第二章线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数学模型线性规划问题及其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤n单纯形法的进一步讨论单纯形法的进一步讨论n数据包络分析数据包络分析第二节第二节 图图解法解法 对模型中只含对模型中只含2 2个变量个变量的线性的线性规划问题，可

11、以通过在平面上作规划问题，可以通过在平面上作图的方法求解。图的方法求解。一、图解法的步骤一、图解法的步骤 1.1.等直线法等直线法x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q21.1.建立平面直角坐标系；建立平面直角坐标系；4 4向着目标函数的优化方向平移等值线，直至得到等值线与可行域向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。的最后交点，这种点就对应最优解。2.2.找出表示每个约束的找出表示每个约束的半平面半平面，所有半平面的交集是可行域，所有半平面的交集是可行域（全体可行解的集合）；（全体

12、可行解的集合）；3.3.画出目标函数的画出目标函数的等值线等值线 ；2.2.试算法试算法x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2最优解在顶点达到：最优解在顶点达到：O点：点：X1=0,X2=0,Z=0Q1:X1=4,X2=0,Z=8Q2:X1=4,X2=2,Z=14Q3:X1=2,X2=3,Z=10Q4:X1=0,X2=3,Z=6二、线性规划问题解的存在情况二、线性规划问题解的存在情况1.1.存在唯一最优解存在唯一最优解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例如例12

13、.2.有无穷多最优解有无穷多最优解 若将例若将例1 1目标函数变为目标函数变为 max max z z=2=2x x1 1+4+4x x2 2，则问题，则问题变为存在无穷多最优解。如图变为存在无穷多最优解。如图:x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q2 3.有无界解有无界解z 可可行行域域可可伸伸展展到到无无穷穷，由由此此目目标标函函数数值值也也可可增增大大至至无无穷穷。这这种种情情况况下下问问题题的的最最优优解解无无界界。产产生生无无界界解解的的原原因因是是由由于于在在建建立立实实际际问问题题的的数数学学模模型型时时遗遗漏漏了了某

14、某些必要的资源约束条件些必要的资源约束条件。例如：例如：max Z=2x1+2x2 s.t.-2x1+x24 x1-x2 2 x1，x2 00 x x1 1x x2 2例如：例如：min Z=60 x1+50 x2 2x1+4x2 80 3x1+2x2 60 x1，x2 00 x x1 1x x2 2无界不一定无最有解无界不一定无最有解X X1 1=10,x=10,x2 2=15 Z=1350=15 Z=1350模型的约束条件之间存在矛盾，建模时有错误。模型的约束条件之间存在矛盾，建模时有错误。4.无可行解无可行解（可行域为空集可行域为空集）例如：例如：max Z=x1+2x2 -x-x1 1

15、-x-x2 22 2 2x 2x1 1+x+x2 24 4 x x1 1，x x2 2 000 x x1 1x x2 2三、由图解法得到的启示三、由图解法得到的启示 图图解解法法虽虽只只能能用用来来求求解解只只具具有有两两个个变变量量的的线线性性规规划划问问题题，但但它它的的解解题题思思路路和和几几何何上上直直观观得得到到的的一一些些概概念念判判断断，对对下下面面要要讲讲的的单单纯纯形形法法有很大启示：有很大启示：1 1求求解解线线性性规规划划问问题题时时，解解的的情情况况有有：唯唯一一最最优优解解；无无穷穷多多最最优优解解；无界解无界解；无可行解无可行解。（见下页图示所示）（见下页图示所示）

16、2 2若线性规划问题的可行域存在，则可行域是一个若线性规划问题的可行域存在，则可行域是一个凸集凸集。3 3若若线线性性规规划划问问题题的的最最优优解解存存在在，则则最最优优解解或或最最优优解解之之一一(如如果果有无穷多的话有无穷多的话)一定是可行域的凸集的某个一定是可行域的凸集的某个顶点顶点。4 4解解题题思思路路是是，先先找找出出凸凸集集的的任任一一顶顶点点，计计算算在在顶顶点点处处的的目目标标函函数数值值。比比较较周周围围相相邻邻点点的的目目标标函函数数值值是是否否比比这这个个值值大大，如如果果为为否否，则则该该顶顶点点就就是是最最优优解解的的点点或或最最优优解解的的点点之之一一，否否则则

17、转转到到比比这这个个点点的的目目标标函函数数值值更更大大的的另另一一顶顶点点，重重复复上上述述过过程程，一一直直到到找找出出使使目目标标函函数数值值达达到最大的顶点到最大的顶点为止。为止。(d)可行域无界可行域无界(e)可行域无界可行域无界(f)可行域为空集可行域为空集多个最优解多个最优解目标函数无界目标函数无界无可行解无可行解(a)可行域有界可行域有界(b)可行域有界可行域有界(c)可行域无界可行域无界唯一最优解唯一最优解多个最优解多个最优解唯一最优解唯一最优解四、线性规划问题的标准形式四、线性规划问题的标准形式 （一）线性规划问题标准形式（一）线性规划问题标准形式 为了使线性规划问题的解法

18、标准，就要把为了使线性规划问题的解法标准，就要把一般形式化一般形式化为为标准形式标准形式。其。其一般形式一般形式如下所示：如下所示：线性规划的标准形式线性规划的标准形式：（二）（二）线性规划问题的解法标准线性规划问题的解法标准1、目标函数为求极大值；、目标函数为求极大值；2、xj0 j=1,2,n;3、bi0 i=1,2,m;4、除非负约束外（、除非负约束外（xj0），其余），其余 约束都为等式。约束都为等式。线性规划问题标准形式的要求如下：线性规划问题标准形式的要求如下：（三）标准形式的变换方法（三）标准形式的变换方法n目标函数为目标函数为minmin型，价值系数一律反号。型，价值系数一律反

19、号。令令 Z Z=-=-Z Z=-=-CXCX ，有，有 min min Z Z=-max-=-max-Z Z=-max =-max Z Z n第第i i 个约束的个约束的b bi i 为负值，则该行左右两端系数同时反号，同时不等为负值，则该行左右两端系数同时反号，同时不等号也要反向号也要反向n第第i i 个约束为个约束为 型，在不等式左边增加一个非负的变量型，在不等式左边增加一个非负的变量x xn+in+i ，称为称为松弛变量；同时令松弛变量；同时令 c cn+in+i =0=0，不等式变为等式。，不等式变为等式。n第第i i 个约束为个约束为 型，在不等式左边减去一个非负的变量型，在不等式

20、左边减去一个非负的变量x xn+in+i ，称为称为剩余变量；同时令剩余变量；同时令 c cn+in+i =0=0，不等式变为等式。，不等式变为等式。n若若x xj j 0 0，令，令 x xj j=-=-x xj j ，代入非标准型，则有，代入非标准型，则有x xj j 0 0n若若x xj j 不限，令不限，令 x xj j=x xj j -x xj j，x xj j 0 0，x xj j 0 0，代入非标准型，代入非标准型（四）变换举例（四）变换举例 例例1.1.将下述线性规划问题化为标准型：将下述线性规划问题化为标准型：令令其中其中并按上述规则，该问题的标准形式为：并按上述规则，该问题

21、的标准形式为：例例2.2.将下述线性规划问题化为标准型将下述线性规划问题化为标准型自己做一下练习自己做一下练习注意一下注意一下这几处这几处经过变换化为标准型如下：经过变换化为标准型如下：x1+x2+x3 7 x1 x2+x3 233 x1+x2+2 x3 =5x1，x2 0，x3为无符号约束为无符号约束例例3 3将下述线性规划问题化为标准型将下述线性规划问题化为标准型min min z=x1+2x23x3解：用解：用x4-x5替换替换x3，令，令z =-=-z z x1+x2+(x4-x5)+x6=7 x1 x2+(x4-x5)-x7=233x1+x2+2(x4-x5)=5 x1，x2，x4，

22、x5，x6，x7 0maxz=x12x2+3(x4-x5)+0 x6+0 x7用标准型求最优解后，再回到原变量。用标准型求最优解后，再回到原变量。线性代数基础知识补充与回顾一、克莱姆规则一、克莱姆规则 含有含有n n个未知数个未知数x x1 1,x,x2 2,x,xn n的的n n个线性方程的方程个线性方程的方程组如下式所示：组如下式所示：克莱姆法则克莱姆法则 如果上述线性方程组的系数行列式不等于零，即有：如果上述线性方程组的系数行列式不等于零，即有：那么，上述方程组有唯一解：那么，上述方程组有唯一解：其中其中DjDj（j=1j=1，2 2，nn）是把系数行列式）是把系数行列式D D中的第中的

23、第j j列的元素用方程组的常数项代替后得到的列的元素用方程组的常数项代替后得到的n n阶行列式阶行列式.定理一定理一:如果线性方程组得系数行列式如果线性方程组得系数行列式D D不等于零，则不等于零，则上述方程组一定有解，且解是唯一的。上述方程组一定有解，且解是唯一的。定理二定理二:如果上述方程组无解或有两个不同的解，则如果上述方程组无解或有两个不同的解，则它的系数行列式必为零。它的系数行列式必为零。二、矩阵的秩二、矩阵的秩定义定义1 1 在在矩阵矩阵A A中，任取中，任取k k行与行与k k列列(K=m,k=n)(K=m,k=n)，位于这些行列交叉处的，位于这些行列交叉处的k k的的平方个元素

24、，不改变他们在平方个元素，不改变他们在A A中所处的位置中所处的位置次序而得到的次序而得到的k k阶行列式阶行列式，称为矩阵，称为矩阵A A的的k k阶阶子式。子式。定义二定义二:设在矩阵中有一个不等于设在矩阵中有一个不等于0 0的的r r阶子式阶子式D D，并且所有的，并且所有的r+1r+1阶子式（如果存在）全等于零，那么阶子式（如果存在）全等于零，那么D D称为矩阵称为矩阵A A的最的最高阶非零子式，数高阶非零子式，数r r称为矩阵称为矩阵A A的秩。的秩。有了上述基本知识以后我们来看一下几个有了上述基本知识以后我们来看一下几个非常重要的概念非常重要的概念五、关于标准型解的若干基本概念五、

25、关于标准型解的若干基本概念 线性规划问题线性规划问题 ：可行解：可行解：满足上述约束条件满足上述约束条件(2.2)(2.2)，(2.3)(2.3)的解的解 ，称为线性规划问题的可行解。全部可行解的集合称为称为线性规划问题的可行解。全部可行解的集合称为可行域可行域。非可行解非可行解:满足约束条件（）但不满足非负条件（）的解满足约束条件（）但不满足非负条件（）的解 X X 称为非可行解称为非可行解最优解：最优解：使目标函数使目标函数(2.1)(2.1)达到最大值的可行解称为最优解。达到最大值的可行解称为最优解。基：基：设设 A A 为约束方程组为约束方程组(2.2)(2.2)的的 mn mn 阶系

26、数矩阵，阶系数矩阵，(设设n nm)m)，其秩为其秩为m m，B B是矩阵是矩阵A A中的一个中的一个mmmm阶的满秩子系数矩阵，称阶的满秩子系数矩阵，称B B是线性是线性规划问题的一个基。规划问题的一个基。不失一般性，设：不失一般性，设：B B中的每一个列向量中的每一个列向量P Pj j (j(j1,m)1,m)称为称为基向量基向量，与基向量与基向量P Pj j对应对应的变量的变量x xj j称为称为基变量基变量。线性规划中除基变量以外的变量称为线性规划中除基变量以外的变量称为非基变量非基变量。基解基解:在约束方程组在约束方程组(2.2)(2.2)中，令所有非基变量中，令所有非基变量 x x

27、m+1m+1x xm+2m+2x xn n0 0，又因为有，又因为有 ，根据克莱姆规则，由，根据克莱姆规则，由m m个个约束方程可解出约束方程可解出m m个基变量的唯一解个基变量的唯一解 。将这个解。将这个解加上非基变量取加上非基变量取0 0的值有的值有 ，称，称X X为线性规划为线性规划问题的问题的基解基解。显然在基解中变量取非零值的个数不大于方程数显然在基解中变量取非零值的个数不大于方程数m m，故基解，故基解的总数不超过的总数不超过 个。个。基可行解基可行解:满足变量非负约束条件满足变量非负约束条件(2.3)(2.3)的基解称为基可行解。的基解称为基可行解。可行基可行基:对应于基可行解的

28、基称为可行基。对应于基可行解的基称为可行基。退化解退化解:基础可行解的非零分量个数基础可行解的非零分量个数 m m 时，称为退化解时，称为退化解 例：找出下述线性规划问题的全部基解，指出其例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。中的基可行解，并确定最优解。解解:该线性规划问题的全部基解见表该线性规划问题的全部基解见表l-4l-4中的中的-，打打者为基可行解，注者为基可行解，注*者为最优解，者为最优解，z*z*l9l9。x1x2x3x4x5z是否基可是否基可行解行解00510450452017500541005501201005041552.5001.517.554

29、030222430019 六、线性规划标准型问题解的关系六、线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基础解基础解可行解可行解非可行解非可行解基础基础可行解可行解退化解退化解如如:max:max z z=2=2x x1 1+3+3x x2 2 s.t.s.t.x1+2 x2+x3=84 x1 +x4 =164 x2+x5=12 x1，x2，x3，x4，x5 0 以以(P P3 3、P P4 4、P P5 5)作为基，令作为基，令x x1 1=x x2 2=0=0，得到，得到 X=X=(0(0，0 0，8 8，1616，12)12)T T为一个基可行解，对应图中为一个基可行解，对

30、应图中O O点点；2 x2=8 x4 =164 x2+x5=12以以(P P1 1、P P2 2、P P5 5)为为基基，令令x x3 3=x x4 4 =0=0，可可得得X=X=(4(4，2 2，0 0，0 0，4)4)T T是是基基最最优优解，对应图中解，对应图中Q Q2 2点。点。x1x2O4Q2(4,2)Q1Q3Q43A以以(P P2 2、P P4 4、P P5 5)作为基，令作为基，令x x1 1=x x3 3=0=0，由，由 得得X=X=(0(0，4 4，0 0，1616，-4)4)T T是个基解，不是基可行解，对应图中是个基解，不是基可行解，对应图中A A点点某厂利用某厂利用A

31、A、B B两种原料，生产甲、乙两种产品，有关数据如下：两种原料，生产甲、乙两种产品，有关数据如下：课堂作业：用图解法求解下列问题课堂作业：用图解法求解下列问题产品名称产品名称甲甲 乙乙单位产品单位产品消耗原料消耗原料原料名称原料名称可供利用的原料数可供利用的原料数量（量（T/日）日）681 22 1AB产品售价产品售价（千元（千元/T）3 2根据市场调查，有如下资料：根据市场调查，有如下资料：1.1.乙产品的需求量至多乙产品的需求量至多 2 T/2 T/日日;2.2.乙产品的需求量比甲产品的需求量至多大乙产品的需求量比甲产品的需求量至多大 1 T/1 T/日。日。求该厂产值最大的生产方案。求该

32、厂产值最大的生产方案。max Z=3xmax Z=3x1 1+2x+2x2 2 x x1 1+2x+2x2 266 2x 2x1 1+x+x2 288 x x2 222 x x2 2-x-x1 111 x x1 1，x x2 2000 x x1 1x x2 2X X1 1=10/3,x=10/3,x2 2=4/3=4/3第二章第二章线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数学模型线性规划问题及其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤n单纯形法的进一步讨论单纯形法的进一步讨论n数据包络分析数据包络分析第三节第三节 单纯形法原理

33、单纯形法原理本节重点：本节重点：凸集与顶点凸集与顶点线性规划基本定理线性规划基本定理检验数的概念和计算检验数的概念和计算最优性判别最优性判别基变换（换入变量和换出变量的确定）基变换（换入变量和换出变量的确定）一、线性规划问题的几何意义一、线性规划问题的几何意义凸组合的概念凸组合的概念凸集的概念凸集的概念顶点顶点线性规划基本定理线性规划基本定理二维空间二维空间两点连线上的任何一点都是这两点的凸组合两点连线上的任何一点都是这两点的凸组合1.凸组合凸组合设设 X1，X2，Xm C，若存在，若存在 ，0 1，且，且 ，使，使则称则称X为为X1，X2，Xm的凸组合。的凸组合。X2 X X1令令2.凸集凸

34、集 对简单的几何形体可以直观地判断其凹凸性，但在高对简单的几何形体可以直观地判断其凹凸性，但在高维空间，只能给出点集的解析表达式，因此只能用数学解维空间，只能给出点集的解析表达式，因此只能用数学解析式判断。析式判断。凸集的概念为：如果集合凸集的概念为：如果集合C C中任意两个点中任意两个点X X1 1，X X2 2，其连线上的所有点也都是集合，其连线上的所有点也都是集合C C中的点，称中的点，称C C为凸集为凸集。由由于于X X1 1，X X2 2的连线可表示为的连线可表示为 因此凸集定义用数学解析式可表为：对任何因此凸集定义用数学解析式可表为：对任何 ，有，有 则称则称C C为凸集为凸集.(

35、a)(b)(c)(d)(e)(a)(b)(c)(d)(e)图中图中红粗线红粗线和和红点红点是顶点。是顶点。3.3.顶点顶点 凸集凸集C C中满足下述条件的点中满足下述条件的点X X称为顶点。称为顶点。如果如果C C中不存在任何两个不同的点中不存在任何两个不同的点X X1 1，X X2 2，使，使X X成为这两成为这两个点连线上的一个点，或者：对任何个点连线上的一个点，或者：对任何 ,不不存在存在 ，则称，则称X X是凸集是凸集C C的顶点。的顶点。4.4.线性规划基本定理线性规划基本定理定理定理1 1 若线性规划问题存在若线性规划问题存在可行解，则问题的可行域是凸集。可行解，则问题的可行域是凸

36、集。证证 (方方法法1)1)若若满满足足线线性性规规划划约约束束条条件件 的的所所有有点点组组成成的的几几何何图图形形C C是是凸凸集集，根根据据凸凸集集定定义义，C C内内任任意意两两点点X Xl l，X X2 2连连线线上上的点也必然在的点也必然在C C内内，下面给予证明。，下面给予证明。设设 为为C C内任意两点，内任意两点，即即 ，将，将X X1 1，X X2 2代入约束条件有代入约束条件有 (2.4)(2.4)X X1 1，X X2 2连线上任意一点可以表示为：连线上任意一点可以表示为：(2.5)(2.5)将式（）代入式（）得：将式（）代入式（）得：所以所以 。由于集合中任意两点连线

37、上的点。由于集合中任意两点连线上的点均在集合内，所以均在集合内，所以C C为凸集。为凸集。引理引理 线线性性规规划划问问题题的的可可行行解解X=X=(x(x1 1，x x2 2，x xn n）T T为为基基可可行行解解的的充充分分必必要要条条件件是是X X 的的正正分分量量所所对对应应的的系系数数列列向向量量是是线性无关的。线性无关的。证明：证明：(1)(1)必要性必要性 由基可行解的定义可知，由基可行解的定义可知，X X为基可行解为基可行解 其正其正分量的系数列向量分量的系数列向量线性无关线性无关。(2)(2)充分性充分性 若向量若向量 线性独立，则必有线性独立，则必有kmkm；当当k km

38、 m时，它们恰好构成一个基，时，它们恰好构成一个基，从而从而 为相应的基可行解。当是为相应的基可行解。当是kmk0(m+1 0(m+1 j j n)n)，则有，则有x xj j 0,0,其他非基变量仍为零的可行解其他非基变量仍为零的可行解，其目标函数值为，其目标函数值为这说明这说明当前解不是最优解。若所有当前解不是最优解。若所有 0 0(m+1(m+1 j j n)n)，则，则z z0 0为可行解所为可行解所能取得的目标函数最大值，说明当前解是最优解。故称能取得的目标函数最大值，说明当前解是最优解。故称 为检验数。将基变量的为检验数。将基变量的检验检验数数0 0也视为其检验数，可得：也视为其检

39、验数，可得：,zxzzjj00+=j j 注意：注意：x xj j 的检验数的检验数 是当是当z z 表示为非基变量的函数时表示为非基变量的函数时目标函数中目标函数中x xj j 的系数。基变量的检验数为零。的系数。基变量的检验数为零。最优性判别定理：最优性判别定理：若基可行解对应的检验数若基可行解对应的检验数 0(j=1 0(j=1，2 2，,n),n)则此解是最优解，否则不是最优解。则此解是最优解，否则不是最优解。例例10 10 中中 z z=2=2x x1 1+3+3x x2 2，x x1 1，x x2 2为非基变量，为非基变量，1 1=2020，2 2=3030，X X(0)(0)不是

40、最优解。不是最优解。3.3.基变换基变换 求一个改进的、求一个改进的、“相邻相邻”的可行基，一个基变量的可行基，一个基变量将变成非基变量（换出），一个非基变量将变成将变成非基变量（换出），一个非基变量将变成基变基变量（换入）。量（换入）。(1)(1)换入变量的确定换入变量的确定一般，当一般，当jmaxj|j 0=k，取，取xk为换入变量。为换入变量。例例10中，中，2 1，可取，可取x2为换入变量。为换入变量。第第k列为主元列。列为主元列。第第2列为主元列。列为主元列。(2)换出变量的确定换出变量的确定在在中，中，令令xk0，而而xj=0(m+1 j n，j k)，要保持，要保持xi 0(i=

41、1，2，,m)，即即若所有若所有则则xk可取无穷大，问题无最优解。可取无穷大，问题无最优解。必须必须 Xk于是，当于是，当 为换出变量为换出变量。L L行为主元行，行为主元行，alk lk为主元素为主元素 x2最多取值最多取值 =min8/2,-,12/4=3=x2=3，x5=0，故第，故第3个约束中的个约束中的x5 是换出变量是换出变量.新的基新的基B(1)=(P3 ，P4,P2)，新的解新的解X(1)=(0，3，2，16，0)T(1)最优性判别定理最优性判别定理 若若基基可可行行解解对对应应的的检检验验数数 0(j=1，2，,n),n)，则此解是最优解，否则不是最优解。，则此解是最优解，否

42、则不是最优解。4.结论结论(4)当所有的当所有的 0，又对某个非基变量，又对某个非基变量 ，有有 这表明可以找到另一顶点这表明可以找到另一顶点(基可行基可行解解)目标函数值也达到最大。由于该两点连线上目标函数值也达到最大。由于该两点连线上的点也属可行域内的点，且目标函数值相等，即的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。反之，当所有该线性规划问题有无穷多最优解。反之，当所有非基变量非基变量 的的 O，又，又Pj0，表明线性规划有无界解。，表明线性规划有无界解。1.系统中有系统中有j种活动，它们分享有限的资源种活动，它们分享有限的资源bi；2.进行一个单位的第进行一

43、个单位的第j种活动，需要第种活动，需要第i种资源的量为种资源的量为aij；3.一个单位的第一个单位的第j种活动的产出以种活动的产出以cj表示表示；4.第第j项活动的量用项活动的量用xj表示。表示。5.机会成本机会成本Zj：表示增加一个单位的：表示增加一个单位的xj所引起的目标函数的下降值。所引起的目标函数的下降值。6.价值系数价值系数cj：表示增加一个单位的：表示增加一个单位的xj所引起的目标函数的增加值所引起的目标函数的增加值。7.判别数判别数=cj-zj：表示增加一个单位的：表示增加一个单位的xj所引起的目标函数的净增值。所引起的目标函数的净增值。四、线性规划问题的经济释义四、线性规划问题

44、的经济释义课堂作业：课堂作业：有如下线性规划：有如下线性规划：1.变成标准型；变成标准型；2.确定初始基可行解；确定初始基可行解；3.确定换出变量；确定换出变量；4.确定换入变量；确定换入变量；5.说出主元行、主元列、和主元素说出主元行、主元列、和主元素。1.标准型如下：标准型如下：2.初始基可行解：初始基可行解：X(0)=(0，0，0，100，120)；3.换出变量：换出变量：x24.确定换入变量确定换入变量:x45.说出主元行说出主元行L L=1;主元列主元列k=2;主元素主元素a1212=3。第二章第二章线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数学模型线性规划问题及

45、其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤n单纯形法的进一步讨论单纯形法的进一步讨论n数据包络分析数据包络分析第四节第四节 单纯形法计算步骤单纯形法计算步骤本节重点：本节重点：单纯形表（特别是检验数行）单纯形表（特别是检验数行）单纯形法的计算步骤单纯形法的计算步骤一、单纯形表一、单纯形表 用用单单纯纯形形法法求求解解线线性性规规划划时时，设设计计了了一一种种专专门门表表格格，称称为为单单纯纯形形表表。迭迭代代计计算算中中每每找找出出一一个个新新的的基基可可行行解解时时，就就重重画画一一张张单单纯纯形形表表。含含初初始始基基可可行行解解的的单单纯纯形

46、形表表称称为为初初始始单单纯纯形形表表，含含最最优优解解的单纯形表称为的单纯形表称为最终单纯形表最终单纯形表。考虑系数矩阵中有单位矩阵的情况：考虑系数矩阵中有单位矩阵的情况：单纯形表单纯形表X XB B列列基变量；基变量；C CB B列列基变量的价值系数基变量的价值系数(目标函数系数目标函数系数)；c cj j行行价值系数；价值系数；b b列列方程组右侧常数；方程组右侧常数；列列确定换入变量时的比率计算值；确定换入变量时的比率计算值；底行底行检验数；检验数；中间中间约束方程系数。约束方程系数。|0=kI=二、计算步骤二、计算步骤(1)(1)找出初始可行基找出初始可行基，确定初始基可行解，确定初

47、始基可行解，建立初始单纯形表。建立初始单纯形表。(2)(2)检验检验各非基变量各非基变量xj的检验数，若的检验数，若 j 0，j=m+1，n n；则；则已得到已得到最优解最优解，可停止计算，否则转入下一步。可停止计算，否则转入下一步。(3)(3)在在 j 0，j=m+1，n n中，若有某个中，若有某个 k对应对应xk的系数列向量的系数列向量Pk 0，则此问题是则此问题是无界解无界解，停止计算。否则，转入下一步。停止计算。否则，转入下一步。(4)(4)根据根据max(max(j 0)=k，确定确定xk为换入变量为换入变量，按按 规则计算规则计算 =minb=minbi i/a/aikikaaik

48、ik00可可确定确定第第L行的基变量为行的基变量为换出变量换出变量。转入下一步。转入下一步。23000 121004001004001 02300000081612x3x4x54-3 2300021010-1/292000-3/4003x3x4x224-()301001/4 16 40010X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T，z z0 0=0=0 23000 21010-1/21300-201/4203x1x4x2-412 301001/4 800-412 23000 21010-1/2 92000-3/4003x3x4x224-301001/4 1640

49、010()X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T，z z1 1=9=9 23000 21010-1/21300-201/4203x1x4x2-412 301001/4 800-412()23000 41001/401400-1.5-1/80203x1x5x2 2011/2-1/80 400-21/21 X X(2)(2)=(2=(2，3 3，0 0，8 8，0)0)T T，z z2 2=13=13 X X(3)(3)=(4=(4，2 2，0 0，0,4)0,4)T T，z z3 3=14=14第二章第二章线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问

50、题及其数学模型线性规划问题及其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤n单纯形法的进一步讨论单纯形法的进一步讨论n数据包络分析数据包络分析第五节第五节 单纯单纯形法的形法的进进一步一步讨论讨论本节重点：本节重点：大大M M法法两阶段法两阶段法解的存在情况判别解的存在情况判别 由于所添加的剩余变量的技术系数为由于所添加的剩余变量的技术系数为 1 1，不能作，不能作为初始可行基变量，为此引入一个人为的变量（注意，为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为此时约束条件已为“=”“=”型），以便取得初始基变量，型），以便取得初始基变量