线性规划详细

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

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 2 T/T/日日; ;2.2.乙产品的需求量比甲产品的需求量至多大乙产品的需求量比甲产品的需求

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

5、决策准则是产值最大，用 Z Z 代表产值，则有：代表产值，则有： Z=3xZ=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约束条件资源限制资源限制市场限制市场限制非负限

6、制非负限制2万m31.4万m32万m31.4万m3整理得数学模型：整理得数学模型：目标函数：目标函数： min min z z = 1000 = 1000 x1 + 800 + 800 x2约束条件：约束条件： s.t. s.t. x1 1 1 0.8 0.8 x1 + + x2 1 1.6.6 x1 2 2 x2 1 1.4.4 x1 0 0， x2 0 0例例3、配料问题（、配料问题（min, ) )设设 x1, x2分别代表每粒胶丸分别代表每粒胶丸中甲、乙两种原料的用量中甲、乙两种原料的用量0 x,x20.2x0.5x1.20.6x0.2x30.3x1.0 x20.5x0.5xs.t.0

7、.5x0.3xminZ(x)212121212121 某厂生产一种胶丸，某厂生产一种胶丸，已知如下资料：已知如下资料：例例4、合理下料问题、合理下料问题 用用7.4m长的钢筋，分别截取长的钢筋，分别截取2.9m、2.1m、1.5m各各至少至少100根，要求用料最少。根，要求用料最少。 设设 xj 分别代表采用切割方案分别代表采用切割方案18所需所需7.4米的钢米的钢筋的数量。筋的数量。0,10043231002321002. .)(min,4 . 78765432187643176532432187654321xxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxZm则有钢筋最少

8、若目标函数为使购买的0,10043231002321002. .4 . 18 . 02 . 01 . 109 . 03 . 01 . 0)(min,8765432187643176532432187654321xxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxZ余料则有最少若目标函数为二、线性规划问题的共同特征二、线性规划问题的共同特征（模型的三要素）（模型的三要素） 每一个问题都用一组决策变量每一个问题都用一组决策变量( (x x1 1，x x2 2，x xn n) )表示某表示某一方案；这组决策变量的值就代表一个具体方案。一一方案；这组决策变量的值就代表一个具体方案。一般

9、这些变量取值都是非负的。般这些变量取值都是非负的。 存在一定的约束条件，这些约束条件可以用一组线性存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。等式或线性不等式来表示。 都有一个要求达到的目标，它可用决策变量的线性函都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化标函数实现最大化或最小化。三、线性规划数学模型的一般表示方式三、线性规划数学模型的一般表示方式nn2211xcxcxcx)max(min)Z(0,),(),(),(.2122112222212111

10、212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats技术系数右端项价值系数线性规划问题的规模约束行数变量个数: ;: ;: ;: ;:ijijabcmnmn 求解线性规划问题的任务是：在满求解线性规划问题的任务是：在满足约束条件的所有足约束条件的所有( (x x1 1，x x2 2，x xn n) )（可可行解）中求出使目标函数达到最大行解）中求出使目标函数达到最大( (小小) )z z 值的决策变量值值的决策变量值( (x x1 1* *，x x2 2* *，x xn n* *) )（最最优解）。优解）。 1.和式和式njxmixatsxcxZijinjji

11、jnjjj, 1, 1. .)(max110b，2.向量式向量式0XbPCXnjjjxtsxZ1.)(maxTnnxxxccc),( );,( 2121XC0000 21210bPmmjjjjbbbaaa3.矩阵式矩阵式0XbAXCX. .)(maxtsxZTmTnnmnmmnnbbbxxxcccaaaaaaaaa),(),();,(212121212222111211bXCA课堂作业：建立课堂作业：建立线性规划模型线性规划模型 某城市在一昼夜间，市内交通需要车辆数如图，对车辆某城市在一昼夜间，市内交通需要车辆数如图，对车辆的需求在昼夜间是变化的，车辆的工作制度是一天连续工作的需求在昼夜间是变

12、化的，车辆的工作制度是一天连续工作8 8小时，派车时间在各时间间隔的端点，一旦派出，就连续小时，派车时间在各时间间隔的端点，一旦派出，就连续工作工作8 8小时。求保证需要的最小车辆数。小时。求保证需要的最小车辆数。车辆数时间04712162024481248121084 派车时间在各时间间隔的端点，一旦派出，就连续工派车时间在各时间间隔的端点，一旦派出，就连续工作作8小时。小时。 设：各时间间隔所派车辆数为设：各时间间隔所派车辆数为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+

13、x6 4 x1，x2，x3，x4，x5，x6 0二、二、 线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数学模型线性规划问题及其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤nMatlab计算线性规划问题计算线性规划问题二、二、 图解法图解法 对模型中只含对模型中只含2 2个变量个变量的线性的线性规划问题，可以通过在平面上作规划问题，可以通过在平面上作图的方法求解。图的方法求解。 一、图解法的步骤一、图解法的步骤 1.1.等直线法等直线法 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03

14、Q21.1.建立平面直角坐标系；建立平面直角坐标系；4 4向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。交点，这种点就对应最优解。 2.2. 找出表示每个约束的找出表示每个约束的半平面半平面，所有半平面的交集是可行域（全体可行，所有半平面的交集是可行域（全体可行解的集合）；解的集合）；3.3. 画出目标函数的画出目标函数的等值线等值线 ；2.2.试算法试算法x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2最优解在顶点达到：最优解在顶点达到

15、：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.2.有无穷多最优解有无穷多最优解 若将例若将例1 1目标函数变为目标函数变为 max max z z = 2 = 2x x1 1+ 4+ 4x x2 2，则问则问题变为存在无穷多最优解。如图题变

16、为存在无穷多最优解。如图: :x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q2 3. 有无界解有无界解z 可行域可伸展到无穷，由此目标函数值也可增大可行域可伸展到无穷，由此目标函数值也可增大至无穷。这种情况下问题的最优解无界。产生无界解至无穷。这种情况下问题的最优解无界。产生无界解的原因是由于在建立实际问题的数学模型时的原因是由于在建立实际问题的数学模型时遗漏了某遗漏了某些必要的资源约束条件些必要的资源约束条件。 例如：例如： max Z=2x1+2x2 s.t. -2x1+x24 x1-x2 2 x1，x2 00 x x1 1x x2 2

17、例如：例如：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-x-x2 22 2 2x 2x1 1+x+x2 24 4 x x1 1，x x2 2 000 x x1 1x x2 2 三、由图解法得到的启示三、由图

18、解法得到的启示 图解法虽只能用来求解只具有两个变量的线性规划问题，但它的解题思图解法虽只能用来求解只具有两个变量的线性规划问题，但它的解题思路和几何上直观得到的一些概念判断，对下面要讲的单纯形法有很大启示：路和几何上直观得到的一些概念判断，对下面要讲的单纯形法有很大启示： 1 1求解线性规划问题时，解的情况有求解线性规划问题时，解的情况有：唯一最优解唯一最优解；无穷多最优解无穷多最优解；无界解无界解；无可行解无可行解。（见下页图示所示）（见下页图示所示） 2 2若线性规划问题的可行域存在，则可行域是一个若线性规划问题的可行域存在，则可行域是一个凸集凸集。 3 3若线性规划问题的最优解存在，则最

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

20、直到找出使目标函数值达到最大的顶点使目标函数值达到最大的顶点为止。为止。 (d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目标函数无界目标函数无界 无可行解无可行解 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界 唯一最优解唯一最优解 多个最优解多个最优解 唯一最优解唯一最优解四、线性规划问题的标准形式四、线性规划问题的标准形式 （一）线性规划问题标准形式（一）线性规划问题标准形式 为了使线性规划问题的解法标准，就要把为了使线性规划问题的解法标准，就要把一般形式一般形式化化为为标准形式标准形式。其

21、。其一般形式一般形式如下所示：如下所示：njxmibxatsxcxzjinjjijnjjj, 2 , 1 ), 0(0, 2 , 1 ,),(. .)(max(min)11不限线性代数基础知识补充与回顾线性代数基础知识补充与回顾一、克莱姆规则一、克莱姆规则 含有含有n n个未知数个未知数x x1 1,x,x2 2,x,xn n的的n n个线性方程的方个线性方程的方程组如下式所示：程组如下式所示：nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111 克莱姆法则克莱姆法则 如果上述线性方程组的系数行列式不等于零，即有：如果上述线性方程组的系数行列

22、式不等于零，即有：01111nnnnaaaaD那么，上述方程组有唯一解：那么，上述方程组有唯一解：DDxDDxDDxnn.,.,2211 其中其中DjDj（j=1j=1，2 2，nn）是把系数行列式）是把系数行列式D D中的第中的第j j列的元素用方程组的常数项代替后得到的列的元素用方程组的常数项代替后得到的n n阶行列式阶行列式. . 定理一定理一: 如果线性方程组得系数行列式如果线性方程组得系数行列式D D不等于零，则不等于零，则上述方程组一定有解，且解是唯一的。上述方程组一定有解，且解是唯一的。定理二定理二: 如果上述方程组无解或有两个不同的解，则如果上述方程组无解或有两个不同的解，则它

23、的系数行列式必为零。它的系数行列式必为零。二、矩阵的秩二、矩阵的秩定义定义1 1 在在矩阵矩阵A A中，任取中，任取k k行与行与k k列列(K=m,k=n)(K=m,k=n)，位于这些行列交叉处的，位于这些行列交叉处的k k的的平方个元素，不改变他们在平方个元素，不改变他们在A A中所处的位置中所处的位置次序而得到的次序而得到的k k阶行列式阶行列式，称为矩阵，称为矩阵A A的的k k阶阶子式。子式。nm 定义二定义二: 设在矩阵中有一个不等于设在矩阵中有一个不等于0 0的的r r阶子式阶子式D D，并且所有的，并且所有的r+1r+1阶子式（如果存在）全等于零，那么阶子式（如果存在）全等于零

24、，那么D D称为矩阵称为矩阵A A的最的最高阶非零子式，数高阶非零子式，数r r称为矩阵称为矩阵A A的秩。的秩。 有了上述基本知识以后我们来看一下几个有了上述基本知识以后我们来看一下几个非常重要的概念非常重要的概念五、关于标准型解的若干基本概念五、关于标准型解的若干基本概念 线性规划问题线性规划问题 ：)1(0)1(bzmax 1i1njxmixaxcjnjjijnjjj，) 3 . 2()2 . 2() 1 . 2(可行解：可行解：满足上述约束条件满足上述约束条件(2.2)(2.2)，(2.3)(2.3)的解的解 ，称为线性，称为线性规划问题的可行解。全部可行解的集合称为规划问题的可行解。

25、全部可行解的集合称为可行域可行域。非可行解非可行解:满足约束条件（满足约束条件（2.22.2）但不满足非负条件（）但不满足非负条件（2.32.3）的解）的解 X X 称为非称为非可行解可行解最优解：最优解：使目标函数使目标函数(2.1)(2.1)达到最大值的可行解称为最优解。达到最大值的可行解称为最优解。 基：基：设设 A A 为约束方程组为约束方程组(2.2)(2.2)的的 m mn n 阶系数矩阵，阶系数矩阵，( (设设n nm)m)，其秩其秩为为m m，B B是矩阵是矩阵A A中的一个中的一个m mm m阶的满秩子系数矩阵，称阶的满秩子系数矩阵，称B B是线性规划问题的是线性规划问题的一

26、个基。一个基。TnxxX),(1不失一般性，设不失一般性，设 ：),(B11111mmmmmPPaaaa B B中的每一个列向量中的每一个列向量P Pj j ( j( j1,m )1,m )称为称为基向量基向量，与基向量与基向量P Pj j对应的对应的变量变量x xj j称为称为基变量基变量。线性规划中除基变量以外的变量称为线性规划中除基变量以外的变量称为非基变量非基变量。 基解基解: : 在约束方程组在约束方程组(2.2)(2.2)中，令所有非基变量中，令所有非基变量 x xm+1m+1x xm+2m+2x xn n0 0，又因为有又因为有 ，根据克莱姆规则，由，根据克莱姆规则，由m m个约

27、个约束方程可解出束方程可解出m m个基变量的唯一解个基变量的唯一解 。将这个解加上非。将这个解加上非基变量取基变量取0 0的值有的值有 ，称，称X X为线性规划问题的为线性规划问题的基基解解。显然在基解中变量取非零值的个数不大于方程数显然在基解中变量取非零值的个数不大于方程数m m，故基解的总数不超故基解的总数不超过过 。 基可行解基可行解: : 满足变量非负约束条件满足变量非负约束条件(2.3)(2.3)的基解称为基可行解。的基解称为基可行解。 可行基可行基: : 对应于基可行解的基称为可行基。对应于基可行解的基称为可行基。退化退化解解: : 基础可行解基础可行解的非零分量个数的非零分量个数

28、 m m 时，称为退化时，称为退化解解 0BTmxxxX) 0 , 0 ,(21TmBxxX),(1mnC例：找出下述线性规划问题的全部基解，指出其中例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。的基可行解，并确定最优解。04102532max515242131321xxxxxxxxxxxz解解: :该线性规划问题的全部基解见表该线性规划问题的全部基解见表l-4l-4中的中的 - -，打，打者为者为基可行解，注基可行解，注* *者为最优解，者为最优解，z z* * l9l9。 x1x2x3x4x5z是否基可行解是否基可行解005104504520175005410055

29、01201005041552.5001.517.554030222430019 六、线性规划标准型问题解的关系六、线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基础解基础解可行解可行解非可行解非可行解基础基础可行解可行解退化解退化解如如: : max max z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t.s.t. x1 + 2 x2 + x3 = 84 x1 + x4 =16 4 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

30、，得到得到 X=X=(0(0，0 0，8 8，1616，12)12)T T为为一个基可行解，对应图中一个基可行解，对应图中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点。点。x1x2O4 Q2(4,2)Q1Q3Q43A以以( (P P2 2、P P4 4、P P5 5) )作为基，令作为基，令x x1 1 = = x x3 3 =0 =0，

31、由由 得得X=X=(0(0，4 4，0 0，1616，- -4)4)T T是个基解，不是基可行解，对应图中是个基解，不是基可行解，对应图中A A点点某厂利用某厂利用A A、B B两种原料，生产甲、乙两种产品，有关数据如下：两种原料，生产甲、乙两种产品，有关数据如下：课堂作业：用图解法求解下列问题课堂作业：用图解法求解下列问题产品名称产品名称甲甲 乙乙单位产品单位产品消耗原料消耗原料原料名称原料名称可供利用的原料数可供利用的原料数量（量（T/日）日）68 22 1AB产品售价产品售价 （千元（千元/T） 3 2根据市场调查，有如下资料：根据市场调查，有如下资料：1.1.乙产品的需求量至多乙产品的

32、需求量至多 2 2 T/T/日日; ;2.2.乙产品的需求量比甲产品的需求量至多大乙产品的需求量比甲产品的需求量至多大 1 1 T/T/日。日。求该厂产值最大的生产方案。求该厂产值最大的生产方案。 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/3Z=12.67Z=12.67线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数

33、学模型线性规划问题及其数学模型 n图解法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤nMatlab计算线性规划问题计算线性规划问题三三 单纯形法原理单纯形法原理本节重点：本节重点：凸集与顶点凸集与顶点线性规划基本定理线性规划基本定理检验数的概念和计算检验数的概念和计算最优性判别最优性判别基变换（换入变量和换出变量的确定）基变换（换入变量和换出变量的确定）一、线性规划问题的几何意义一、线性规划问题的几何意义凸组合的概念凸组合的概念凸集的概念凸集的概念顶点顶点线性规划基本定理线性规划基本定理)10()1 (21XXXm,1mmXXX11i 11mii二维空间二维空间两点连线

34、上的任何一点都是这两点的凸组合两点连线上的任何一点都是这两点的凸组合1.凸组合凸组合设设 X1，X2，XmC，若存在若存在 ，0 1，且，且 ，使，使则称则称X 为为X1，X2，Xm 的凸组合。的凸组合。)10()1 (21XXXX2 X X1令令21221)1()(XXXXXXX1X -XX-X2 12 2 12 X -XX-X2. 凸集凸集 对简单的几何形体可以直观地判断其凹凸性，但在高维对简单的几何形体可以直观地判断其凹凸性，但在高维空间，只能给出点集的解析表达式，因此只能用数学解析式空间，只能给出点集的解析表达式，因此只能用数学解析式判断。判断。凸集的概念为：如果集合凸集的概念为：如果

35、集合C C中任意两个点中任意两个点X X1 1，X X2 2，其连其连线上的所有点也都是集合线上的所有点也都是集合C C中的点，称中的点，称C C为凸集。为凸集。由于由于X X1 1，X X2 2的连线可表示为的连线可表示为 )10()1 (21aXaaX 因此凸集定义用数学解析式可表为：对任何因此凸集定义用数学解析式可表为：对任何 ，有，有 则称则称C C为凸集为凸集. . CXCX21,) 10()1 (21aCXaaX(a)(b)(c)(d)(e)(a)(b)(c)(d)(e)图中图中红粗线红粗线和和红点红点是顶点。是顶点。 3.3.顶点顶点 凸集凸集C C中满足下述条件的点中满足下述条

36、件的点X X称为顶点。称为顶点。 如果如果C C中不存在任何两个不同的点中不存在任何两个不同的点X X1 1，X X2 2，使使X X成为这两成为这两个点连线上的一个点，或者：对任何个点连线上的一个点，或者：对任何 , ,不不存在存在 ，则称，则称X X是凸集是凸集C C的顶点。的顶点。 CXCX21,) 10()1 (21aCXaaX 4. 4. 线性规划基本定理线性规划基本定理定理定理1 1 若线性规划问题存在可若线性规划问题存在可行解，则问题的可行域是凸集。行解，则问题的可行域是凸集。 证证 ( (方法方法1)1) 若若满足线性规划约束条件满足线性规划约束条件 的所有点组成的几的所有点组

37、成的几何图形何图形C C是凸集，根据凸集是凸集，根据凸集定义定义，C C内任意两点内任意两点X Xl l，X X2 2连线上的点也必然在连线上的点也必然在C C内内，下面给予证明。，下面给予证明。 njjjxp1b设设 为为C C内任意两点，内任意两点，即即 ，将，将X X1 1，X X2 2代入约束条件有代入约束条件有 TnxxxX),(112111TnxxxX),(222212CXCX21,;b11njjjxpnjjjxp12b(2.4)(2.4) X X1 1，X X2 2连线上任意一点可以表示为：连线上任意一点可以表示为： )10()1 (21aXaaXX(2.5)(2.5) 将式（将

38、式（2.4）代入式（）代入式（2.5）得：）得：babbabaxpxpaxpxaaxpxpnjnjnjjjjjjjnjnjjjjjj1112211121)1( 所以所以 。由于集合中任意两点连线上的点均在集。由于集合中任意两点连线上的点均在集合内，所以合内，所以C C为凸集。为凸集。 CXaaXX21)1 ( 线性规划问题的可行解线性规划问题的可行解X=(xX=(x1 1，x x2 2，x xn n）T T为为基可行解的充分必要基可行解的充分必要条件是条件是X X 的正分量所对应的系数列向量的正分量所对应的系数列向量是线性无关的。是线性无关的。证明：证明：(1)(1)必要性必要性 由基可行解的

39、定义可知，由基可行解的定义可知，X X为基可行解为基可行解 其正其正分量的系数列向量分量的系数列向量线性无关线性无关。 (2)(2)充分性充分性 若向量若向量 线性独立，则必有线性独立，则必有kmkm；当当k km m时，它们恰好构成一个基，从而时，它们恰好构成一个基，从而 为相应的基可行解。当是为相应的基可行解。当是kmk0 (m+1 0 (m+1 j j n)n) ，则有，则有x xj j 00，其它非其它非基变量仍为零的可行解基变量仍为零的可行解， 其目标函数值其目标函数值这说明这说明当前解不是最优解。若所有当前解不是最优解。若所有 0 0 (m+1 (m+1 j j n)n) ，则，则

40、z z0 0为可行解为可行解所能取得的目标函数最大值，说明当前解是最优解。故称所能取得的目标函数最大值，说明当前解是最优解。故称 为为检验数。将基变量的检验数。将基变量的检验检验数数0 0也视为其检验数，可得：也视为其检验数，可得：,zxzzjj00 s sjs sjs s 注意：注意：x xj j 的检验数的检验数 是当是当z z 表示为非基变量的函数时目标表示为非基变量的函数时目标函数中函数中x xj j 的系数。基变量的检验数为零。的系数。基变量的检验数为零。最优性判别定理：最优性判别定理： 若基可行解对应的检验数若基可行解对应的检验数 0 ( 0 ( j=1j=1，2 2，,n),n)

41、则此则此解是最优解，否则不是最优解。解是最优解，否则不是最优解。js s3.基变换基变换 求一个改进的、求一个改进的、“相邻相邻”的可行基，一个基变量的可行基，一个基变量将变成非基变量（换出），一个非基变量将变成基变将变成非基变量（换出），一个非基变量将变成基变量（换入）。量（换入）。 (1)(1) 换入变量的确定换入变量的确定 一般，当一般，当jmaxjs s|js s0=s sk，取，取xk为换入变量。为换入变量。 例例 10 中，中，s s2s s1，可取，可取x2为换入变量。为换入变量。 第第k列为主元列。列为主元列。 第第2列为主元列。列为主元列。 (2) 换出变量的确定换出变量的确

42、定)m,2, 1i (xabxn1mjjijii在在 中，中，令令xk0 ，而而xj =0(m+1 j n，j k)，要保持要保持xi 0 ( i=1，2，,m)，即即若所有若所有 则则xk 可取无穷大，问题无最优解。可取无穷大，问题无最优解。, 0aiklklikikiiabaab 0min必须必须 Xk于是，当于是，当 为换出变量为换出变量。lllklkXXabX,0,L L行为主元行，行为主元行，alk lk为主元素为主元素 (1) 最优性判别定理最优性判别定理 若基可行解对应的检验数若基可行解对应的检验数 0 ( j=1，2，,n),n)，则此解是最优解，否则不是最优解。则此解是最优解

43、，否则不是最优解。js(2) 换换入入变变量量的的确确定定方方法法 一一般般，当当 jmaxjs s|js s0=s sk，取取 xk为为换换入入变变量量。 (3) (3) 换出变量确定方法换出变量确定方法 一般，计算一般，计算 = = lklikikiiabaabmin 0 ，第，第 l 个约束个约束对应的基变量为换出变量。对应的基变量为换出变量。 (4)当所有的当所有的 0，又对某个非基变量，又对某个非基变量 ， 有有 这表明可以找到另一顶点这表明可以找到另一顶点(基可行解基可行解)目标函数值也达到最大。由于该两点连线上的点也目标函数值也达到最大。由于该两点连线上的点也属可行域内的点，且目

44、标函数值相等，即该线性规属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解。反之，当所有非基变量划问题有无穷多最优解。反之，当所有非基变量 的的 O，又又Pj0，表明线性规划有无界解。表明线性规划有无界解。 js1. 系统中有系统中有j种活动，它们分享有限的资源种活动，它们分享有限的资源bi；2. 进行一个单位的第进行一个单位的第j种活动，需要第种活动，需要第 i 种资源的量为种资源的量为aij；3. 一个单位的第一个单位的第j种活动的产出以种活动的产出以cj表示表示；4. 第第j项活动的量用项活动的量用xj表示。表示。5. 机会成本机会成本Zj：表示增加一个单位的表示增加一个单

45、位的xj所引起的目标函数的下降值。所引起的目标函数的下降值。6. 价值系数价值系数cj：表示增加一个单位的表示增加一个单位的xj所引起的目标函数的增加值所引起的目标函数的增加值。7. 判别数判别数 =cj-zj ： 表示增加一个单位的表示增加一个单位的xj所引起的目标函数的净增值。所引起的目标函数的净增值。js四、线性规划问题的经济释义四、线性规划问题的经济释义课堂作业：课堂作业：0,12023310032. .244540max321321321321xxxxxxxxxtsxxxz有如下线性规划：有如下线性规划：1.变成标准型；变成标准型；2.确定初始基可行解；确定初始基可行解；3.确定换出

46、变量；确定换出变量；4.确定换入变量；确定换入变量；5.说出主元行、主元列、和主元素说出主元行、主元列、和主元素。0,12023310032. .00244540max543215321432154321xxxxxxxxxxxxxtsxxxxxz1.标准型如下：标准型如下：2. 初始基可行解：初始基可行解：X(0)=(0，0，0，100，120)；3.换出变量：换出变量：x24.确定换入变量确定换入变量:x45.说出主元行说出主元行L L=1;主元列主元列k=2;主元素主元素a1212=3。 线性规划问题及单纯形法线性规划问题及单纯形法n线性规划问题及其数学模型线性规划问题及其数学模型 n图解

47、法图解法 n单纯形法原理单纯形法原理n单纯形法计算步骤单纯形法计算步骤nMatlab计算线性规划问题计算线性规划问题第四节第四节 单纯形法计算步骤单纯形法计算步骤本节重点：本节重点：单纯形表（特别是检验数行）单纯形表（特别是检验数行）单纯形法的计算步骤单纯形法的计算步骤一、一、单纯形表单纯形表 用单纯形法求解线性规划时，设计了用单纯形法求解线性规划时，设计了一种专门表格，称为单纯形表。迭代计算一种专门表格，称为单纯形表。迭代计算中每找出一个新的基可行解时，就重画一中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表张单纯形表。含初始基可行解的单纯形表称为称为初始单纯形表初始

48、单纯形表，含最优解的单纯形表含最优解的单纯形表称为称为最终单纯形表最终单纯形表。 )1(0)1(bzmax 11njxmixPxcjnjjjnjjj，考虑系数矩阵中有单位矩阵的情况：考虑系数矩阵中有单位矩阵的情况：单纯形表单纯形表cj c1 cm cm + 1 cn CB XB b x1 xm xm + 1 xn I c1 c2 cm x1 x2 xm b1 b2 bm 1 0 0 0 0 1 a1,m + 1 a2,m + 1 am ,m + 1 a1n a2n am n 1 2 m z z 值 0 0 sm + 1 sn X XB B列列基变量；基变量；C CB B列列基变量的价值系数基变

49、量的价值系数( (目标函数系数目标函数系数) )； c cj j行行价值系数；价值系数； b b列列方程组右侧常数；方程组右侧常数； 列列确定换入变量时的比率计算值；确定换入变量时的比率计算值；底行底行检验数；检验数；中间中间约束方程系数。约束方程系数。lklikikiiabaab 0min | 0 = s sk jmaxjs smiijijmjmjjjjaccacacacc12211)(sjs sI =二、计算步骤二、计算步骤(1)(1)找出初始可行基找出初始可行基，确定初始基可行解确定初始基可行解，建立初始单纯形表。建立初始单纯形表。(2)(2)检验检验各非基变量各非基变量xj的检验数，若

50、的检验数，若s sj 0，j=m+1，n n；则则已得到已得到最优解最优解，可停止计算，否则转入下一步。可停止计算，否则转入下一步。(3)(3)在在s sj 0，j=m+1，n n中，若有某个中，若有某个s sk对应对应xk的系数列向量的系数列向量Pk 0，则则此问题是此问题是无界解无界解，停止计算。否则，转入下一步。停止计算。否则，转入下一步。(4)(4)根据根据max(max(s sj 0) =s sk，确定确定xk为换入变量为换入变量，按按 规则计算规则计算 = =minbminbi i/a/aikikaaikik00可可确定确定第第L行的基变量为行的基变量为换出变量换出变量。转入下一步

51、。转入下一步。cj CB XB b x1 x2 x3 x4 x5 z 2 3 0 0 0 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 0 2 3 0 0 000081612x3x4x54-3例例 1 10 0 的的初初始始单单纯纯形形表表： cj CB XB b x1 x2 x3 x4 x5 z 2 3 0 0 02 1 0 1 0 -1/2 9 2 0 0 0 -3/4003x3x4x224-( ) 3 0 1 0 0 1/4 16 4 0 0 1 0X(0)(0)=(0=(0，0 0，8 8，1616，12)12)T T， z z0 0 =0=0cj CB XB b x1

52、x2 x3 x4 x5 z 2 3 0 0 0 2 1 0 1 0 -1/2 13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 9 2 0 0 0 -3/4003x3x4x224- 3 0 1 0 0 1/4 16 4 0 0 1 0( ) X X(1)(1)=(0=(0，3 3，2 2，1616，0)0)T T， z z1 1 =9=9cjCB XBbx1x2x3x4x5-z 2 3 0 0 0 2 1 0 1 0 -1/2 13 0 0 -2 0 1/4203x1x4x2-412 3 0 1 0 0 1/4 8 0 0 -4 1 2( )cj CB XB b x1 x2 x3 x4 x5 z 2 3 0 0 0 4 1 0 0 1/4 0 14 0 0 -1.