1、1第一章第一章线性规划理论及应用线性规划理论及应用线性规划线性规划 Linear Programming（LP）2n引引 言言n解决有限资源在有竞争的使用方向中如何进行最佳分配。解决有限资源在有竞争的使用方向中如何进行最佳分配。n线性规划是运筹学的一个重要分支，也是运筹学中应用最广线性规划是运筹学的一个重要分支，也是运筹学中应用最广泛的方法之一。自泛的方法之一。自1947年旦茨基（年旦茨基（G.B.Dantzig）提出了一）提出了一般线性规划问题求解的方法般线性规划问题求解的方法单纯形法（单纯形法（simplex method）之后，线性规划已被广泛应用于解决经济管理和）之后，线性规划已被广泛
2、应用于解决经济管理和工业生产中遇到的实际问题。调查表明，在世界工业生产中遇到的实际问题。调查表明，在世界500家最大家最大的企业中，有的企业中，有85%的企业都曾使用过线性规划解决经营管理的企业都曾使用过线性规划解决经营管理中遇到的复杂问题。线性规划的使用为应用者节约了数以亿中遇到的复杂问题。线性规划的使用为应用者节约了数以亿万计的资金。万计的资金。线性规划线性规划 Linear Programming（LP）3n本章中我们将讨论什么是线性规划问题，线性本章中我们将讨论什么是线性规划问题，线性规划问题的数学表示，基本理论、概念和求解规划问题的数学表示，基本理论、概念和求解方法。方法。n线性规划
3、问题是什么样的一类问题呢？线性规划问题是什么样的一类问题呢？线性规划线性规划 Linear Programming（LP）4线性规划线性规划 Linear Programming（LP）1.1.线性规划模型线性规划模型 Linear Programming Model Linear Programming Model或或 Linear Optimization ModelLinear Optimization Model 用线性规划方法解决实际问题的第一步是用线性规划方法解决实际问题的第一步是建立能够完整描述和反映实际问题的线性规划建立能够完整描述和反映实际问题的线性规划模型。模型。5线性规划
4、线性规划 Linear Programming（LP）通常建立通常建立LP模型有以下几个步骤：模型有以下几个步骤：1.确定决策变量：确定决策变量：决策变量是模型要确定的未知变量，也是模型最重要决策变量是模型要确定的未知变量，也是模型最重要的参数，是决策者解决实际问题的控制变量。的参数，是决策者解决实际问题的控制变量。2.确定目标函数：确定目标函数：目标函数决定线性规划问题的优化方向，是模型的重目标函数决定线性规划问题的优化方向，是模型的重要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并要组成部分。实际问题的目标可表示为决策变量的一个线性函数，并根据实际问题的优化方向求其最大化（根据
5、实际问题的优化方向求其最大化（max）或最小化（）或最小化（min）。）。3.确定约束方程：确定约束方程：一个正确的线性规划模型应能通过约束方程来描述和反一个正确的线性规划模型应能通过约束方程来描述和反映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不映一系列客观条件或环境的限制，这些限制通过一系列线性等式或不等式方程组来描述。等式方程组来描述。4.变量取值限制：变量取值限制：一般情况下，决策变量取正值（非负值）。因此，模型一般情况下，决策变量取正值（非负值）。因此，模型中应有变量的非负约束即中应有变量的非负约束即Xj0，但也存在例外。，但也存在例外。6线性规划线性规划 Linear
6、 Programming（LP）n例例1 某工厂可生产甲、乙两种产品，需消耗煤、某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下，试拟电、油三种资源。现将有关数据列表如下，试拟订使总收入最大的生产计划方案。订使总收入最大的生产计划方案。资源单耗资源单耗 产品产品资源资源 甲甲 乙乙 资源限量资源限量 煤煤 电电 油油 9 4 4 5 3 10 360 200 300单位产品价格单位产品价格 7 127n线性规划模型三要素：线性规划模型三要素：1.决策变量：需决策的量，即待求的未知决策变量：需决策的量，即待求的未知数；数；2.目标函数：需优化的量，即欲达的目标，目标函数
7、：需优化的量，即欲达的目标，用决策变量的表达式表示；用决策变量的表达式表示；3.约束条件：为实现优化目标需受到的限约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。制，用决策变量的等式或不等式表示。8n在本例中在本例中 决策变量：甲、乙产品的计划产量，记为决策变量：甲、乙产品的计划产量，记为x1,x2；目标函数：总收入，记为目标函数：总收入，记为z,则则z=7x1+12x2，为体现对其追求极大化，在为体现对其追求极大化，在z的前面冠以极的前面冠以极大号大号Max；约束条件：分别来自资源煤、电、油限量的约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为约束，和
8、产量非负的约束，表示为9s.t.9x1+4x2 360 4x1+5x2 200 3x1+10 x2 300 x1，x2 010线性规划模型的一个基本特点：目标和约束均为变量的线性表达式如果模型中出现如x12+2lnx2-1/x3的非线性表达式，则不属于线性规划。11例2 某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：资源资源 住宅体系住宅体系 造价造价（元（元/M)钢材钢材（公斤（公斤/M)水泥水泥（公斤（公斤/M)砖砖（块（块/M)人工人工（工日（工日/M)砖混住宅砖混住宅105121102104.5壁板住宅壁板住宅13530190-3.0大模住宅
9、大模住宅12025180-3.5资源限量资源限量11000（千元）（千元）20000（吨）（吨）150000（吨）（吨）147000（千块）（千块）4000(千工日）千工日）要求在充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。12 解:设今年计划修建砖混、壁板、大模住宅各为 x1,x2,x3,为总面积,则本问题的数学模型为:s.t.0.105x1+0.135x2+0.120 x3 110000 0.012x1+0.030 x2+0.025x3 20000 0.110 x1+0.190 x2+0.180 x3 150000 0.210 x1 147000 0.0045x1+0.00
10、3x2+0.0035x3 4000 x1,x2,x3 0Max z=x1+x2+x3前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。13练习：某畜牧厂每日要为牲畜购买饲料以使其获取某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有四种养分。市场上可选择的饲料有M、N两种。有关数据如下：试决定买两种。有关数据如下：试决定买M与与N二种饲料各二种饲料各多少公斤而使支出的总费用为最少？多少公斤而使支出的总费用为最少？售价售价 （元（元/公斤）公斤）每公斤含营养成分每公斤含营养成分 A B C DM10 0.1 0 0.1 0.2N
11、4 0 0.1 0.2 0.1牲畜每日每头需要量牲畜每日每头需要量 0.4 0.6 2.0 1.714解：设购买解：设购买M、N饲料各为饲料各为x1,x2 ，则，则Min z=10 x1+4x2s.t.0.1x1+0 x2 0.4 0 x1+0.1x2 0.6 0.1x1+0.2x2 2 0.2x1+0.1x2 1.7 x1,x2,0152.线性规划的数学模型线性规划的数学模型线性规划模型的一般形式：以MAX型、约束为例决策变量决策变量:x1,xn目标函数：目标函数：Max z=Max z=c1x1+cn xn约束条件约束条件：s.t.a11x1+a1n xn b1 am1x1+amn xn
12、bm x1,xn 016模型一般式的矩阵形式X=(x1,xn)T,C=(c1,cn),A=(aij)mxn,b=(b1,bn)T则模型可表示为则模型可表示为 Max z=CXMax z=CX s.t.AX s.t.AX b X X 0以例以例1为例，写出其矩阵形式。为例，写出其矩阵形式。17 一般地 Max z=CXMax z=CX s.t.AX s.t.AX b X X 0中 X 称为决策变量向量，C 称为价格系数向量，A 称为技术系数矩阵，b 称为资源限制向量。18线性规划线性规划 Linear Programming（LP）2.2.线性规划问题的求解：（图解法）线性规划问题的求解：（图解
13、法）如何求解一般的线性规划呢？如何求解一般的线性规划呢？下面我们分析一下简单的情况下面我们分析一下简单的情况 只有两只有两个决策变量的线性规划问题，这时可以通过图个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等于初学者窥探线性规划基本原理和几何意义等优点。优点。19n图解法是用画图的方式求解线性规划的图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在个变量）的问题，但其主要作用并不在于求解，而是在于
14、能够直观地说明线性于求解，而是在于能够直观地说明线性规划解的一些重要性质。规划解的一些重要性质。20线性规划线性规划 Linear Programming（LP）例例1max z=2x1+x2 5x2 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 021n1.做约束的图形做约束的图形 先做非负约束的图形；再做资源约束的先做非负约束的图形；再做资源约束的图形；最后找出公共部分。图形；最后找出公共部分。n2.做目标的图形做目标的图形对于目标函数：对于目标函数：Max z=c1x1+cn xn任给任给z二不同的值，便可做出相应的二直线，二不同的值，便可做出相应的二直线，用虚线表示。用
15、虚线表示。n3.求出最优解求出最优解22 将目标直线向使目标将目标直线向使目标z优化的方向移，直优化的方向移，直至可行域的边界为止，这时其与可行域至可行域的边界为止，这时其与可行域的的“切切”点点X*即最优解。即最优解。如在例如在例1中，中，X*是可行域的一个角点，经是可行域的一个角点，经求解交出的二约束直线联立的方程可解求解交出的二约束直线联立的方程可解得得X*=(3.5,1.5)由图解法的结果得到例由图解法的结果得到例1的最优解，还可的最优解，还可将其代入目标函数求得相应的最优目标将其代入目标函数求得相应的最优目标值值z=8.523线性规划线性规划 Linear Programming（L
16、P）max z=2x1+x2 5x2 15s.t.6x1+2x2 24 x1+x2 5 x1，x2 024线性规划线性规划 Linear Programming（LP）例例2 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 025线性规划线性规划 Linear Programming（LP）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=2
17、X1+X2 11=2X1+X2 Lo：0=2X1+X2（7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域26线性规划线性规划 Linear Programming（LP）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 绿色线段上的所有点都是最绿色线段上的所有点都是最优解这种情形为有无穷多最优
18、解这种情形为有无穷多最优解，但是最优目标函数值优解，但是最优目标函数值max Z=34.2是唯一的。是唯一的。可行域可行域27线性规划线性规划 Linear Programming（LP）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练习：用图解法求解下面的线性规划。练习：用图解法求解下面的线性规划。min z=6x1+4 x2 s.t.2x
19、1+x2 1 3x1+4x2 1.5 x1，x2 029n二维线性规划的可行域是一个什么形状？二维线性规划的可行域是一个什么形状？多边形，而且是多边形，而且是“凸凸”形的多边形。形的多边形。n最优解在什么位置获得？最优解在什么位置获得？在边界，而且是在某个顶点获得。在边界，而且是在某个顶点获得。30线性规划线性规划 Linear Programming（LP）图解法的启示图解法的启示1.线性规划问题解的可能情况线性规划问题解的可能情况 a.a.唯一最优解唯一最优解 b.b.无穷多最优解无穷多最优解 c.c.无解（没有有界最优解，无可行解）无解（没有有界最优解，无可行解）2.若线性规划问题的可行
20、域非空，则可行域是一个若线性规划问题的可行域非空，则可行域是一个凸集；凸集；3.若线性规划问题的最优解存在，则一定可以在可若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。（为什么？）行域的凸集的某个顶点上达到。（为什么？）31线性规划线性规划 Linear Programming（LP）凸集凸集凹集凹集凸多面体是凸集的一种。所谓凸集是指：集中凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。凸集中的任两点的连线仍属此集。凸集中的“极点极点”，又称顶点或角点，是指它属于凸集，但不能表又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点
21、。示成集中某二点连线的内点。如多边形的顶点。32线性规划线性规划 Linear Programming（LP）3.3.单纯形法单纯形法单纯形方法是单纯形方法是G.B.Danzig于于1947年首先发年首先发明的。近明的。近50年来，一直是求解线性规划的最年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划有效的方法之一，被广泛应用于各种线性规划问题的求解。问题的求解。尽管在其后的几十年中，又有一尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的始终保持着绝对的“市场市场”占有率。占有率。本节讨论本节讨论单
22、纯形法的基本概念、原理及算法。单纯形法的基本概念、原理及算法。33线性规划线性规划 Linear Programming（LP）线性规划问题的标准形式（预备知识一）线性规划问题的标准形式（预备知识一）1 1、目标函数极大化、目标函数极大化“max”“max”2 2、等式约束条件、等式约束条件“=”“=”3 3、变量非负、变量非负“x xj j 0 0”max z=c c1 1x x1 1 +c+c2 2x x2 2+c+cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n =b=b1 1 a a2121x x1 1+a+a2222x x2 2
23、+a+a2n2nx xn n =b =b2 2 s.t.s.t.a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n =b=bm m x xj j 0 0 （j=1j=1，2 2，n n）34线性规划线性规划 Linear Programming（LP）化标准形式的一般步骤化标准形式的一般步骤1 1、目标函数极小化、目标函数极小化“极大化极大化”2 2、约束条件的右端项、约束条件的右端项 bi0 bi0 “bi0”bi0”3 3、约束条件为不等式、约束条件为不等式 或或 “=”=”4 4、取值无约束（自由）变量、取值无约束（自由）变量“非负变量非负变量”5 5、取
24、值非正变量、取值非正变量“非负变量非负变量”35线性规划线性规划 Linear Programming（LP）给定线性规划问题（标准形式）给定线性规划问题（标准形式）max z=c c1 1x x1 1 +c+c2 2x x2 2+c+cn nx xn n a a1111x x1 1+a+a1212x x2 2+a+a1n1nx xn n =b=b1 1 a a2121x x1 1+a+a2222x x2 2+a+a2n2nx xn n=b=b2 2s.t.s.t.a am1m1x x1 1+a+am2m2x x2 2+a+amnmnx xn n =b=bm m x xj j 0 0 （j=1
25、j=1，2 2 n n）标准型的特征：标准型的特征：max型；等式约束；非负约束型；等式约束；非负约束36n练习：将例练习：将例1的约束化为标准型的约束化为标准型s.t.9x1+4x2 360 4x1+5x2 200 3x1+10 x2 300 x1，x2 037一般地，记松弛变量的向量为一般地，记松弛变量的向量为Xs，则，则s.ts.t.AX.AX b X 0s.t.AX+IXs.t.AX+IXs s=b X,Xs 0s.ts.t.AX.AX b X 0s.t.AX-Is.t.AX-IXs=b X,Xs 038线性规划线性规划 Linear Programming（LP）线性规划问题的解的概
26、念线性规划问题的解的概念（预备知识二）（预备知识二）可行解可行解 最优解最优解 基矩阵、基变量基矩阵、基变量 基解（基本解）基解（基本解）基可行解基可行解 39（1）可行解与最优解）可行解与最优解可行解可行解：满足全体约束的解，记为：满足全体约束的解，记为X；最优解最优解：可行解中最优的，记为：可行解中最优的，记为X*，则对，则对任可行解任可行解X，有，有CXCX*.直观上，可行解是可行域中的点，是一直观上，可行解是可行域中的点，是一个可行的方案；最优解是可行域中的顶个可行的方案；最优解是可行域中的顶点，是一个最优的方案。点，是一个最优的方案。40（2）基矩阵和基变量）基矩阵和基变量基矩阵基矩
27、阵(简称基简称基)：系数阵：系数阵A中的中的m阶可逆子阶可逆子阵，记为阵，记为B；其余部分称为非基矩阵，记；其余部分称为非基矩阵，记为为N。基向量基向量：基：基B中的列；其余称非基向量。中的列；其余称非基向量。基变量基变量：与基向量：与基向量Pj对应的决策变量对应的决策变量xj，记，记其组成的向量为其组成的向量为XB；与非基向量对应的；与非基向量对应的变量称非基变量，记其组成的向量为变量称非基变量，记其组成的向量为XN。41例例3 下面为某线性规划的约束下面为某线性规划的约束s.t.x1+2x2+x3=1 2x1-x2 +x4=3 x1，x2，x3，x4 0请例举出其基矩阵和相应的基向量、请例
28、举出其基矩阵和相应的基向量、基变量。基变量。42解：本例中，解：本例中，A=12 1 02 -1 0 1A中的中的2阶可逆子阵有阶可逆子阵有B1=100 1其相应的基向量为其相应的基向量为P3,P4基变量为基变量为x3,x4，XB1=x3x443其相应的基向量为其相应的基向量为P1,P2基变量为基变量为x1,x2，XB2=x1x2B2=122 -1问题：本例的问题：本例的A中一共有几个基？中一共有几个基？一般地，一般地，mn 阶矩阵阶矩阵A中基的个中基的个数最多有多少个？数最多有多少个？44（3）基本解与基本可行解）基本解与基本可行解当当A A中的基中的基B B取定后，不妨设取定后，不妨设B
29、B表示表示A A中的前中的前m m列列,则可记则可记A=(B N),A=(B N),相应地相应地X=(xX=(xB B x xN N)T T,约约束中的束中的AX=bAX=b可表示为（可表示为（B N)=b B N)=b，即即 X XB B=B=B-1-1b-Bb-B-1-1NXNXN N,当取当取X XN N=0=0时，有时，有X XB B=B=B-1-1b b，X=X=B B-1b b 0 xBxN称称AX=bAX=b的解的解X=X=为线性规划的一为线性规划的一个基本解；个基本解；B B-1b b 045 可见：一个基本解是由一个基决定的。可见：一个基本解是由一个基决定的。注意：基本解仅是
30、资源约束的解，并未注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。要求其非负，因此其未必可行。称非负的基本解为基本可行解（简称基称非负的基本解为基本可行解（简称基可行解）。可行解）。46在上例中在上例中求相应于基求相应于基B1和和B2的可行解，它们是否基本可行解？的可行解，它们是否基本可行解？解：解：B1=100 1B2-1=1/5 2/52/5 -1/5B1-1b=13 相应于基相应于基B1的基本解为的基本解为X=（0，0，1，3）T，是基本可行解。，是基本可行解。B2=122 -1B1-1=100 1B2-1b=7/5-1/5 相应于基相应于基B2的基本解为的基本解为X=（7
31、/5，-1/5，0，0）T，不是基本可行，不是基本可行解。解。47上二组概念间的联系：上二组概念间的联系：系数阵系数阵A中可找出若干个基中可找出若干个基B每个基每个基B都对应于一个基本解都对应于一个基本解非负的基本解就是基本可行解非负的基本解就是基本可行解问题问题1：几种解之间的关系是什么？：几种解之间的关系是什么？问题问题2：基本可行解是可行域中的哪些点？：基本可行解是可行域中的哪些点？48线性规划线性规划 Linear Programming（LP）线性规划基本定理线性规划基本定理基本定理基本定理 1 线性规划所有可行解组成的集合线性规划所有可行解组成的集合S=X|AX=b，X 0 是凸集
32、。是凸集。基本定理基本定理 2 X是线性规划问题的是线性规划问题的基本可行解的充要条件为是基本可行解的充要条件为是 X 是凸集是凸集S=X|AX=b，X 0 的极点。的极点。基本定理基本定理 3 给定线性规划问题，给定线性规划问题，A是秩为是秩为 m 的的 mn 矩阵，矩阵，（i）若线性规划问题存在若线性规划问题存在可行解，则必可行解，则必存在存在基本可基本可行行性性解解 （ii）若线性规划问题存在有界最优解若线性规划问题存在有界最优解，则必，则必存在有界存在有界最优最优基本可行解。基本可行解。49n（1）线性规划的可行域是一个凸多面体。）线性规划的可行域是一个凸多面体。n（2）线性规划可行域
33、的顶点与基本可行）线性规划可行域的顶点与基本可行解一一对应。解一一对应。n（3）线性规划的最优解（若存在的话）线性规划的最优解（若存在的话）必能在可行域的顶点获得。必能在可行域的顶点获得。50单纯形法的步骤单纯形法的步骤确定初始基可行解确定初始基可行解检验其是否最优检验其是否最优是是stop寻找更好的基本可行解寻找更好的基本可行解否否单纯形法是一种迭代单纯形法是一种迭代的算法，它的思想是的算法，它的思想是在可行域的顶点在可行域的顶点基本可行解中寻优。基本可行解中寻优。由于顶点是有限个由于顶点是有限个,因此，算法经有限步因此，算法经有限步可终止。可终止。方法前提：模型方法前提：模型化为标准型化为
34、标准型51线性规划线性规划 Linear Programming（LP）1 确定初始基可行解确定初始基可行解由于基可行解是由一个可行基决定的，因此，确由于基可行解是由一个可行基决定的，因此，确定初始基可行解定初始基可行解X0相当于确定一个初始可行基相当于确定一个初始可行基B0。方法：若方法：若A中含中含I，则，则B0=I；若；若A中不含中不含I，则可用，则可用人工变量法构造一个人工变量法构造一个I。问题：若问题：若B0=I，则，则X0=？52线性规划线性规划 Linear Programming（LP）2 最优性检验最优性检验把目标函数用非基变量表示：把目标函数用非基变量表示：AX=b XAX
35、=b XB B=B=B-1-1b-Bb-B-1-1NXNXN NZ=CX=CZ=CX=CB BB B-1-1b+(Cb+(CN N-C-CB BB B-1-1N)XN)XN N矩阵矩阵分块分块检验数向量，记为检验数向量，记为。当。当0时，当前解为时，当前解为最优解。最优解。53线性规划线性规划 Linear Programming（LP）方法：（方法：（1）计算每个）计算每个xj的检验数的检验数=c cj j-C-CB BB B-1 1p pj j（2）若所有）若所有j0，则当前解为最优；否则，则当前解为最优；否则，至少有至少有k0，转，转3。54线性规划线性规划 Linear Program
36、ming（LP）3 寻找更好的基可行解寻找更好的基可行解由于基可行解与基对应，即寻找一个新的由于基可行解与基对应，即寻找一个新的基可行解，相当于从上一个基基可行解，相当于从上一个基B0变换为下变换为下一个新的基一个新的基B1，因此，本步骤也称为基变，因此，本步骤也称为基变换。换。基变换的原则基变换的原则改善改善:z1 z0 可行可行:B-1b0变换的方法：（变换的方法：（P1,Pl,Pk,Pn）55线性规划线性规划 Linear Programming（LP）进基：保证进基：保证“改善改善”，令，令0对应的对应的Pk进进基基出基：保证出基：保证“可行可行”，令，令X XB B=B=B-1-1b
37、-Bb-B-1-1NXNXN N0可决定出基可决定出基方法：令方法：令k=max j0 对应的对应的Pk进进基；令基；令l=min i=（B-1b）i/(B-1Pk)i|(B-1Pk)i 0 对应的对应的Pl出基；出基；i称作检称作检验比。验比。56 以例以例1为例，可按上述单纯形法的步骤为例，可按上述单纯形法的步骤求出其最优解，其大致的过程如下。求出其最优解，其大致的过程如下。（1 1）先将模型化为标准型）先将模型化为标准型s.t.9x1+4x2+x3=360 4x1+5x2 +x4=200 3x1+10 x2 +x5=300 x1，x2，x3，x4，x5 0max z=7X1+12X257
38、(2)(2)确定初始基可行解、检验确定初始基可行解、检验1 1 1B0=,B0-1-1b b=(360,200,300)T T,X0=(0,0,360,200,300)T T 计算检验数确定进基向量为计算检验数确定进基向量为P2,再计再计算检验比确定出基向量为算检验比确定出基向量为P5；58（3）换基、计算下一个基可行解、再检）换基、计算下一个基可行解、再检验，直至最优验，直至最优1 4 1 5 10B1=,B1-1-1b b=(240,50,30)T T,X1=(0,30,240,50,0)T T;计算检验数确定进基向量为计算检验数确定进基向量为P1,再计再计算检验比确定出基向量为算检验比确
39、定出基向量为P4；5919 4 0 4 50 3 10B2=,B2-1-1b b=(84,20,24)T T,X2=(20,24,84,0,0)T T;计算检验数均非正，当前解为最优。计算检验数均非正，当前解为最优。问题：当模型规模较大时，计算量很大。问题：当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形事实上，单纯形法的实现是在单纯形表上完成的。表上完成的。60三、单纯形表单纯形表是基于单纯形法的步骤设计的计算格式，是单纯形法的具体实现。回顾单纯形法步骤B0 X0=B0-1-1b b 0 0j=cj CB0 B0-1-1 Pj i=min(B0-1-1b)b)i(B011P P
40、k)iB1需计算B-1-1b b需计算B 11A A因此，单纯形表的主体内容是因此，单纯形表的主体内容是B 11(b A)(b A)61 而相邻两个而相邻两个B B只有一列不同，故相邻只有一列不同，故相邻两个两个B 11也可通过初等行变换求得。由此也可通过初等行变换求得。由此设计了基于初等行变换迭代计算的单纯设计了基于初等行变换迭代计算的单纯形表。形表。即 B0 11(b A)(b A)B1 11(b A)(b A)B2 11(b A)(b A).62单纯形表的主要结构：单纯形表的主要结构：C XB-1-1b bB-1-1A A问题：第一张表的问题：第一张表的B-1-1=？单位阵单位阵I。检验
41、数的公式是什么？检验数的公式是什么？j=cj CB B-1-1 Pj B-1-1 Pj在哪里？在哪里？B-1-1A A中的第中的第j列列63例1max z=7X1+12X2s.t.9x1+4x2 360 4x1+5x2 200 3x1+10 x2 300 x1，x2 0s.t.9x1+4x2+x3=360 4x1+5x2 +x4=200 3x1+10 x2 +x5=300 x1，x2，x3，x4，x5 0化为标准型化为标准型max z=7X1+12X264XB CB B-1-1b b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 300 9 4
42、 1 0 0 4 5 0 1 0 3 10 0 0 1 7 12 0 0 0的计算:1=c1 CBB-1-1 P=7-0,0,0 =7943单纯形表：单纯形表：65单纯形表单纯形表:XB CB B-1-1b b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1904030 7 12 0 0 0主元素66单纯形表:XB CB B-1-1b b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 300 9 4 1 0 0 4 5 0 1
43、0 3 10 0 0 1904030 7 12 0 0 0 X3 0 240 X4 0 50 X2 12 307.8 0 1 0 -0.42.5 0 0 1 -0.50.3 1 0 0 0.13.4 0 0 0 -1.2或或1=c1 CBB-1-1 P1=7-0,0,12 =3.47.82.5 0.3以以10为为主主元元进进行行初初等等行行变变换换67单纯形表:XB CB B-1-1b b 7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 360X4 0 200 X5 0 3009 4 1 0 04 5 0 1 03 10 0 0 19040307 12 0 0 0 X3 0 24
44、0X4 0 50 X2 12 307.8 0 1 0 -0.42.5 0 0 1 -0.50.3 1 0 0 0.130.8201003.4 0 0 0 -1.2或或5=c5 CBB-1-1 P5=0-0,0,12 =-1.2-0.4-0.5 0.1以以10为为主主元元进进行行初初等等行行变变换换68XB CB B-1-1b b7 12 0 0 0 X1 X2 X3 X4 X5 X3 0 240 X4 0 50 X2 12 307.8 0 1 0 -0.42.5 0 0 1 -0.50.3 1 0 0 0.130.8201003.4 0 0 0 -1.2 X3 0 84 X1 7 20 X2
45、12 240 0 1 -3.12 1.161 0 0 0.4 -0.20 1 0 0.12 0.160 0 0-1.36-0.52以以2.5为为主主元元进进行行初初等等行行变变换换69X*=(20,24,84,0,0)T T;z*=428注：注：每一列的含义：每一列的含义：B-1(bA)=(B-1b,B-1P1,，B-1Pn)每个表中的每个表中的B和和B-1的查找的查找:B从初表从初表中找；中找；B-1从当前表中找，对应于初表从当前表中找，对应于初表中的中的I的位置。的位置。终表分析终表分析最优解和最优解和(B*)-1的查找。的查找。70n练习：用单纯形法求解下面的线性规划练习：用单纯形法求解
46、下面的线性规划s.t.3x1+5x215 5x1+2x210 x1，x2 0max z=2.5X1+X2问题：本题的单纯形终表检验数有何问题：本题的单纯形终表检验数有何特点？特点？非基变量非基变量x x2 2的检验数等于零。的检验数等于零。71注：（注：（1）解的几种情况在单纯形表上的体）解的几种情况在单纯形表上的体现（现（Max型）：型）：唯一最优解：终表非基变量检验数均小于唯一最优解：终表非基变量检验数均小于零；多重最优解：终表非基变量检验数中零；多重最优解：终表非基变量检验数中有等于零的；无界解：任意表有正检验数有等于零的；无界解：任意表有正检验数相应的列均非正；无解：最优解的基变量相应
47、的列均非正；无解：最优解的基变量中含有人工变量。中含有人工变量。（2）Min型单纯形表与型单纯形表与Max型的区别仅在型的区别仅在于：检验数反号，即令负检验数中最小的于：检验数反号，即令负检验数中最小的对应的变量进基；当检验数均大于等于零对应的变量进基；当检验数均大于等于零时为最优。时为最优。72线性规划线性规划 Linear Programming（LP）单纯形法的进一步讨论单纯形法的进一步讨论人工变量法：人工变量法：当一般线性规划问题标准化之后，我们可得到一个显然的当一般线性规划问题标准化之后，我们可得到一个显然的基本可行解（如基本可行解（如松弛变量松弛变量作为作为基变量的一个基变量的一个
48、初始初始基本可行解），基本可行解），这样我们就可以马上进入这样我们就可以马上进入单纯形表的运算步骤。然而，并非所单纯形表的运算步骤。然而，并非所有有问题标准化之后我们都可得到一个显然的问题标准化之后我们都可得到一个显然的初始初始基本可行解，基本可行解，这时就需要我们首先确定出一个这时就需要我们首先确定出一个基本可行解作为基本可行解作为初始初始基本可行基本可行解。通常采用的是人工变量法来确定这样的解。通常采用的是人工变量法来确定这样的初始初始基本可行解。基本可行解。这种情况下一般有两种方法：这种情况下一般有两种方法：1 1、大、大M M法（罚因子法）；法（罚因子法）；2 2、两阶段法、两阶段法7
49、3线性规划线性规划 Linear Programming（LP）1、大、大 M 法（罚函数法）法（罚函数法）max z=-3X1+X3 x1+x2+x3 4s.t.-2x1+x2 x3 1 3x2+x3=9 x1，x2，x3 0 max z=-3x1+x3+0 x4+0 x5 Mx6 Mx7 x1+x2+x3+x4 =4 s.t.-2x1+x2 x3 -x5+x6 =1 3x2+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 074线性规划线性规划 Linear Programming（LP）LPM max z=-3x1+x3+0 x4+0 x5 Mx6 Mx7 x1+x2+x3
50、+x4 =4 -2x1+x2 x3 -x5+x6 =1 3x2+x3 +x7 =9 x1，x2，x3，x4，x5，x6，x7 0基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j75线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4X5X6X7 X441111000X61-21-10-110X790310001检验数检验数 j-3-2M4M10-M0076线性规划线性规划 Linear Programming（LP）基基XB解解B-1bX1X2X3X4X5X6X7
