高等教育1172线性规划问题及其数学模型.pptx

第第 一一 章章 线性规划与单纯形法线性规划与单纯形法第一章第一章 线性规划与单纯形法线性规划与单纯形法第第1 1节节 线性规划问题及其数学模型线性规划问题及其数学模型第第2 2节节 线性规划问题的几何意义线性规划问题的几何意义第第3 3节节 单纯形法单纯形法第第4 4节节 单纯形法的计算步骤单纯形法的计算步骤第第5 5节节 单纯形法的进一步讨论单纯形法的进一步讨论第第6 6节节 应用举例应用举例 【例例例例1 1 1 1】最优生产计划问题。最优生产计划问题。最优生产计划问题。最优生产计划问题。某某工工厂厂在在计计划划期期内内要要安安排排生生产产、两两种种产产品品，已已知知生生产产单单位位产产品品所所需需的的设设备备台台时时及及A A、B B两两种种原材料的消耗，如表原材料的消耗，如表1-11-1所示。所示。该工厂每生产一件产品该工厂每生产一件产品可获利可获利2 2元，元，每生产一件产品每生产一件产品可获利可获利3 3元，元，问应如何安排计划使该工厂问应如何安排计划使该工厂获利最多获利最多?1.1 1.1 问题的提出问题的提出预备知识：预备知识：1 1、融会贯通地理解要解决的问题，融会贯通地理解要解决的问题，搞清搞清在什么条件下在什么条件下，要，要追求什么目标追求什么目标？2 2、这个要实现的目标是由一组这个要实现的目标是由一组变量变量变量变量决定的决定的决策变量决策变量决策变量决策变量。定义决策变量，每一个问题用一组决策变量定义决策变量，每一个问题用一组决策变量（x x1 1,x,x2 2,x,x3 3 ,x,xn n）来表示某一方案，）来表示某一方案，每组决策变量的值就代表一个具体方案；每组决策变量的值就代表一个具体方案；3 3、用用决决策策变变量量的的线线性性函函数数来来表表示示写写出出所所要要追追求求的的目标，我们称之为目标，我们称之为目标函数目标函数。按按问问题题的的不不同同，可可能能要要求求这这目目标标函函数数实实现现最最大大化化或最小化。或最小化。4 4、这这些些决决策策变变量量需需要要一一定定的的限限制制和和约约束束，这这些些约约束条件可以用一组束条件可以用一组线性等式或线性不等式线性等式或线性不等式来表示。来表示。解：解：将一个实际问题转化为线性规划模型有将一个实际问题转化为线性规划模型有 以下几个步骤以下几个步骤：1 1确定决策变量：确定决策变量：x x1 1=产品产品的产量的产量 x x2 2=产品产品的产量的产量 2 2确定目标函数：确定目标函数：目标是使工厂获得的利润最大目标是使工厂获得的利润最大 max z=2xmax z=2x1 1+3x+3x2 2 3 3确定约束条件：确定约束条件：x x1 1+2x+2x2 2 8 8 （设备的有效台时的限制）（设备的有效台时的限制）4x4x1 1 16 16（原材料（原材料A A的消耗限制）的消耗限制）4x4x2 2 12（原材料（原材料B B的消耗限制）的消耗限制）4 4变量取值限制：变量取值限制：一般情况，决策变量取非负值一般情况，决策变量取非负值 x x1 1 0,x 0,x2 2 0 0 数学模型数学模型 max z=2xmax z=2x1 1+3x+3x2 2 s.t.x s.t.x1 1+2x+2x2 2 120 120 4x 4x1 1 50 50 4x 4x2 21212 x x1 1,x,x2 2 0 0线性规划数学模型三要素：线性规划数学模型三要素：决策变量、约束条件、目标函数决策变量、约束条件、目标函数 【例例例例2 2 2 2】.简化的环境保护问题简化的环境保护问题简化的环境保护问题简化的环境保护问题靠近某河流有两个化工厂靠近某河流有两个化工厂靠近某河流有两个化工厂靠近某河流有两个化工厂(见图见图见图见图1-1-1-1-1)1)1)1)，流经第一化工厂的河流流量，流经第一化工厂的河流流量，流经第一化工厂的河流流量，流经第一化工厂的河流流量为每天为每天为每天为每天500500500500万立方米，在两个工万立方米，在两个工万立方米，在两个工万立方米，在两个工厂之间有一条流量为每天厂之间有一条流量为每天厂之间有一条流量为每天厂之间有一条流量为每天200200200200万万万万立方米的支流。立方米的支流。立方米的支流。立方米的支流。第一化工厂每天排放污水第一化工厂每天排放污水2 2万万mm3 3，第二化工厂每天排放污水第二化工厂每天排放污水 1.41.4万万mm3 3。污水从工厂污水从工厂1 1流到工厂流到工厂2 2前会有前会有20%20%自然净化。自然净化。根据环保要求，河水中污水的含量应不大于根据环保要求，河水中污水的含量应不大于0.2%0.2%。而工厂而工厂1 1和工厂和工厂2 2处理污水的成本分别为处理污水的成本分别为 10001000元元/万万mm3 3和和800800元元/万万mm3 3。问两工厂各应处理多少污水才能使处理污水的问两工厂各应处理多少污水才能使处理污水的总费用最低？总费用最低？图图1-11-1解：解：解：解：将此实际问题转化为线性规划模型步骤如下：将此实际问题转化为线性规划模型步骤如下：将此实际问题转化为线性规划模型步骤如下：将此实际问题转化为线性规划模型步骤如下：1.1.1.1.明确问题，确定决策变量明确问题，确定决策变量明确问题，确定决策变量明确问题，确定决策变量 设工厂设工厂1 1和工厂和工厂2 2每天分别处理污水每天分别处理污水x x1 1万万mm3 3和和x x2 2万万mm3 3Min Z=1000Min Z=1000 x x1 1+800+800 x x2 2(2-(2-x x1 1)/)/（500+2500+2）0.0020.002 x x2 2 1.41.4（非负值约束）（非负值约束）（非负值约束）（非负值约束）x x1 1,x,x2 2002.2.确定约束条件：确定约束条件：确定约束条件：确定约束条件：工厂工厂工厂工厂1 1 1 1的排污口污水含量：的排污口污水含量：的排污口污水含量：的排污口污水含量：3.3.确定目标函数：确定目标函数：确定目标函数：确定目标函数：4.4.确定决策变量的约束确定决策变量的约束确定决策变量的约束确定决策变量的约束：工厂工厂工厂工厂2 2 2 2的排污口：的排污口：的排污口：的排污口：其他约束其他约束其他约束其他约束：x x x x1 1 1 1 1 1 1 11.4-1.4-x x2 2+0.8(2-+0.8(2-x x 1 1)/)/（500+2+200+1.4500+2+200+1.4）0.0020.0020.8(2-0.8(2-x x1 1)+1.4-)+1.4-x x2 2 /700 0.002/700 0.002 x x1 1 2 20.80.80.80.8x x x x1 1 1 1+x x x x2 2 2 2 16161616(2-(2-x x1 1)/5000.002)/5000.002数学模型数学模型其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题投资证券组合问题投资证券组合问题分派问题分派问题生产工艺优化问题生产工艺优化问题设置决策变量，它们体现解决问题的方案。设置决策变量，它们体现解决问题的方案。小结小结1 1：建模的基本步骤：建模的基本步骤确定目标函数，它是决策变量的函数。确定目标函数，它是决策变量的函数。确定决策变量的取值范围，给出优化方向确定决策变量的取值范围，给出优化方向。确定约束条件，它们是含有决策变量的不确定约束条件，它们是含有决策变量的不等式或等式。等式或等式。小结小结2 2：数学模型的共同特征：数学模型的共同特征 （1 1）每一个线性规划问题都用一组）每一个线性规划问题都用一组决策变量决策变量 ,每组决策变量的值就代表一个具体方案。每组决策变量的值就代表一个具体方案。一般这些变量一般这些变量取值是非负且连续的；取值是非负且连续的；(2)(2)要要有有各各种种资资源源和和使使用用有有关关资资源源的的技技术术数数据据创造新创造新价值的数据；资源的数据价值的数据；资源的数据:(3)3)存在可以量化的存在可以量化的约束条件约束条件，这这些些约约束束条条件件可可以以用用一一组组线线性性等等式式或或线线性性不不等式等式来表示来表示;(4)(4)要有一个达到目标的要求，要有一个达到目标的要求，它它可可用用决决策策变变量量的的线线性性函函数数(称称为为目目标标函函数数)来来表示。表示。按按问问题题的的不不同同，要要求求目目标标函函数数实实现现最最大大化化或或最小化。最小化。具有上述特征的数学模型称为具有上述特征的数学模型称为线性规划模型线性规划模型一类是在有限的人力、物力、财力的条件下，一类是在有限的人力、物力、财力的条件下，研究如何合理地计划和安排，使得某一目标达到研究如何合理地计划和安排，使得某一目标达到最大（产量最大、利润最大）。最大（产量最大、利润最大）。另一类是任务确定后，如何计划和安排，用最另一类是任务确定后，如何计划和安排，用最少的人力、物力和财力，去实现该任务，使得成少的人力、物力和财力，去实现该任务，使得成本最小。本最小。线性规划研究对象：线性规划研究对象：n决策变量决策变量n目标函数目标函数n约束条件约束条件线性规划的一般模型形式线性规划的一般模型形式 目标函数目标函数约束条件约束条件Subject toSubject to 资源系数资源系数(右边项右边项)价值系数价值系数工艺系数工艺系数目标函数目标函数价值系数价值系数工艺系数工艺系数资源系数资源系数决策变量决策变量它们的对应关系可用表格表示：它们的对应关系可用表格表示：1.2 1.2 二维线性规划问题的图解法二维线性规划问题的图解法 对于只有两个决策变量的对于只有两个决策变量的LPLP，可以在平，可以在平面直角坐标系上作图表示其有关概念，面直角坐标系上作图表示其有关概念，并进行求解。并进行求解。因存在因存在 ，所以必须在直角坐，所以必须在直角坐标系的第标系的第1 1象限内作图，求解。象限内作图，求解。定义定义1 1 在在LP LP 问题中，凡满足约束条件的解问题中，凡满足约束条件的解 称为称为LP LP 问题的问题的可行解可行解，所有可行解的集合，所有可行解的集合称为可行解集（或称为可行解集（或可行域可行域）。）。定义定义2 使目标函数取得最优值的可行解，称使目标函数取得最优值的可行解，称 为为最优解最优解。相应的目标函数值称为相应的目标函数值称为最优值最优值.图解法的步骤：图解法的步骤：建立平建立平面直角面直角坐标系坐标系根据约根据约束条件束条件找出可找出可行域行域图示图示目标目标函数函数确定确定最优最优解解【例例1 1】x2=-(2/3)x1+z/3目标函数目标函数等值线等值线定义定义3 3 当当z z取某一取某一固定值时得到一条固定值时得到一条直线，直线上的每直线，直线上的每一点都具有相同的一点都具有相同的目标函数值，称之目标函数值，称之为为“等值线等值线等值线等值线”。max z=2x1+3x2s.t.x1+2x28 4x1 16 4x212 x1 0,x20最优解最优解840 x1x2最优解为最优解为x=(4,2)x=(4,2)T T最优值最优值z=14z=1443Q4（3，0）Q2（4，2）Q1（4，0）可行域可行域目标函数等值线目标函数等值线:x x2 2=-(2/3)=-(2/3)x x1 1+z/3+z/3目标函数目标函数目标函数目标函数Z Z Z Z增加最快的方向就是函数增加最快的方向就是函数增加最快的方向就是函数增加最快的方向就是函数的梯度方向的梯度方向的梯度方向的梯度方向Q3（2，3）LPLP图解法的基本步骤：图解法的基本步骤：1 1、在平面上建立直角坐标系；在平面上建立直角坐标系；2 2、图示约束条件，确定可行域和顶点坐标；图示约束条件，确定可行域和顶点坐标；3 3、图示目标函数（等值线）和其移动方向；图示目标函数（等值线）和其移动方向；4 4、寻找最优解。寻找最优解。64-860 x1x2 m maxax z=x z=x1 1+3x+3x2 2 s.t.s.t.x x1 1+x+x2 266 -x -x1 1+2x+2x2 288 x x1 1 0,x0,x2 200可行域可行域目标函数等值线目标函数等值线x x2 2=-x=-x1 1/3+z/3/3+z/3最优解最优解最优解最优解必落在必落在可行域可行域的的顶点顶点上上max max z z=15=15x x1 1+25+25x x2 2s.t.s.t.x x1 1+3+3x x2 2 60 60 x x1 1 +x x2 2 40 40 x x1 1，x x2 2 0 0 (40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数的等值线：目标函数的等值线：x2=-3/5 x1+z/25x2x1最优解最优解：x x1 1=30 x=30 x2 2=10=10最优值最优值：z zmaxmax=700=700B B点是使点是使z z达到达到最大的唯一可最大的唯一可行点行点LP LP 问题从解的角度可有两种分类方式：问题从解的角度可有两种分类方式：有可行解有可行解 无可行解无可行解a.a.有唯一最优解有唯一最优解b.b.有无穷优多最解有无穷优多最解线性规划问题解的几种情况：线性规划问题解的几种情况：唯一最优解唯一最优解 无穷多最优解无穷多最优解 无界解无界解 无可行解无可行解 （1）有最优解）有最优解（2）无最优解）无最优解第第第第一一一一种种种种分分分分类类类类第第第第二二二二种种种种分分分分类类类类有最优解有最优解无最优解无最优解（无界解）（无界解）【例例例例1 1 1 1 】max z=2x1+3 x2 s.t.x1+2x28 4x1 16 4x212 x1 0,x20目标函数等值线目标函数等值线最优解最优解8x1x24 40 03 34 42 23 3可行域可行域无穷多最优解无穷多最优解(多重最优解多重最优解)4结论：结论：LP LP 若有最优解，必在可行若有最优解，必在可行域的某个顶点上取到；域的某个顶点上取到；若在两个顶点上同时取到，若在两个顶点上同时取到，则这两点的连线上则这两点的连线上 任一点任一点都是最优解。都是最优解。例：例：例：例：maxmaxz=xz=x1 1+x+x2 2s.t.s.t.-2x-2x1 1+x+x2 244 x x1 1-x-x2 2 2 2 x x1 1 0,x0,x2 200目标函数等值线目标函数等值线4x1x202无界解无界解即可行域的范围延伸到无即可行域的范围延伸到无穷远，目标函数值可以无穷远，目标函数值可以无穷大或无穷小。穷大或无穷小。一般来说，这说明模型有一般来说，这说明模型有错，忽略了一些必要的约错，忽略了一些必要的约束条件。束条件。无可行解无可行解增加的约束条件增加的约束条件增加的约束条件增加的约束条件当存在矛盾的约束条件当存在矛盾的约束条件时，为无可行域。时，为无可行域。在例在例1的数学模型中的数学模型中增加一个约束条件增加一个约束条件:则可行域为空域，不存则可行域为空域，不存在满足约束条件的解，在满足约束条件的解，当然也就不存在最优解当然也就不存在最优解唯一最优解唯一最优解无穷多最优解无穷多最优解无界解无界解无可行解无可行解小结小结:v线性规划的可行域和最优解的情况线性规划的可行域和最优解的情况I.I.可行域为封闭的可行域为封闭的有界有界区域区域有有唯一唯一的最优解的最优解有有无穷多无穷多个最优解个最优解II.II.可行域为非可行域为非 封闭的封闭的无界无界区域区域有有唯一唯一的最优解的最优解有有无穷多无穷多个最优解个最优解目标函数目标函数无界无界III.III.可行域为可行域为空集空集没有可行解，原问题没有可行解，原问题无最优解无最优解 1 1、可行域为可行域为封闭封闭的的有界有界区域区域 唯一最优解唯一最优解 无穷无穷 多个最优解多个最优解 2.2.可行域为可行域为非封闭非封闭的的无界无界区域区域 唯一最优解唯一最优解 无穷多个最优解无穷多个最优解 无界解无界解3 3、可行域为可行域为空集空集 无可行解无可行解两个变量的两个变量的LPLP问题的解的启示：问题的解的启示：(1)(1)可行域非空时，它是有界或无界凸多边形可行域非空时，它是有界或无界凸多边形（凸集）（凸集），顶点个数只有有限个。，顶点个数只有有限个。(4)(4)若最优解存在，则最优解或最优解之一一定是可若最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点。行域的凸集的某个顶点。(5)(5)若在两个顶点上同时取到最优解，则这两点的若在两个顶点上同时取到最优解，则这两点的连线上连线上 任一点都是最优解任一点都是最优解(2)(2)求解求解LPLP问题时，解的情况有：问题时，解的情况有：唯一最优解；无穷多最优解；无界解；无可行解唯一最优解；无穷多最优解；无界解；无可行解。(3)(3)若可行域非空且有界则必有最优解，若可行域非空且有界则必有最优解，若可行域无界，则可能有最优解，也可能无最优解。若可行域无界，则可能有最优解，也可能无最优解。v求解线性规划问题最优解的方法：求解线性规划问题最优解的方法：确定确定可行域可行域 =凸集凸集(凸多边形凸多边形)确定可行域确定可行域顶点顶点 =求求基可行解基可行解 寻找寻找最优解，最优解，如果最优解存在，则如果最优解存在，则必在可行域必在可行域的某一的某一顶点顶点 =在基可行解中寻找在基可行解中寻找由图解法得到的结论：由图解法得到的结论：图解法优点：图解法优点：直观、易掌握。有助于了解解的结构。直观、易掌握。有助于了解解的结构。图解法缺点：图解法缺点：只能解决低维问题，对高维无能为力。只能解决低维问题，对高维无能为力。1.3 1.3 线性规划问题的标准型式线性规划问题的标准型式 一般式一般式 矩阵式矩阵式 向量式向量式 化标准形式化标准形式其中其中 b bi i 0(0(i i=1,2,1,2,m,m)一般标准式：一般标准式：目标函数目标函数目标函数目标函数约束条件约束条件约束条件约束条件其中其中 b bi i 0(0(i i=1,2,1,2,m,m)向量式向量式：矩阵式：矩阵式：化标准式：化标准式：2.2.约束条件约束条件 3.3.变量变量 1.1.目标函数目标函数 4.4.右端项系数右端项系数(1)(1)目标函数目标函数 若目标函数是求最小值，即若目标函数是求最小值，即min z=CXmin z=CX。因为求因为求 min z min z 等价于求等价于求 max(-z)max(-z)，故令故令 z z=-z=-z，于是得到于是得到max z=-CXmax z=-CX。这就同标准型的目标函数的形式一致了。这就同标准型的目标函数的形式一致了。化标准式：化标准式：令令Z=-ZxoZZ=-ZminZ=2X1+5X2+6X3+8X4maxZ=-2X1-5X2-6X3-8X4(2)(2)约束条件约束条件 若若约束方程为不等式，则有两种情况：约束方程为不等式，则有两种情况：一一种种是是约约束束方方程程为为“”不不等等式式，则则可可在在“”不不等等式式的的左左端端加加入入非非负负松松弛弛变变量量，把原把原“”不等式变为等式；不等式变为等式；另另一一种种是是约约束束方方程程为为“”不不等等式式，则则可可在在“”不不等等式式的的左左端端减减去去非非负负剩剩余余变变量量(也也可可称称松松弛弛变变量量)，把把不不等等式式约约束束条条件件变变为为等等式约束条件。式约束条件。下面举例说明下面举例说明:例：例：maxZ=2x1+x2+0+0X X3 3 +0+0X X4 4+0+0X X5 5 5x2 15 6x1+2x2 24 x1+x2 5 xi 0+X X3 =15 +X X4 4 =24 +X X5 5 =5 松弛变量松弛变量例：例：minZ=2x1+5x2+6x3+8x4 4x1+6x2+x3+2x4 12 x1+x2+7x3+5x4 14 2x2+x3+3x4 8 xi 0(i=1,4)-X5 =12 -X6 =14 -X7=8 剩余变量剩余变量 7）+0X0X5 5+0X+0X6 6+0X+0X7 7例例3 3：将例将例1 1的数学模型化为标准型。的数学模型化为标准型。例例1 1的数学模型的数学模型,加松驰变量后加松驰变量后例：例：令令X1=X1-X1(3)(3)变量变量其中其中若若若若 x x x xk k k k 为自由变量，即为自由变量，即为自由变量，即为自由变量，即 x x x xk k k k 可为任意实数，可为任意实数，可为任意实数，可为任意实数，,可令可令可令可令 设设 x xk k没有非负约束，没有非负约束，若若 x xk k00，可令，可令 x xk k，=-=-x xk k ，则则 x xk k 0 0；3X1+2X2 8 X1-4X2 14 X2 0 03 X1-3 X1 +2X2 8 X1-X1 -4X2 14X1,X1,X2 0 0处理的步骤：处理的步骤：例例4 4：将下述线性规划问题化为标准型将下述线性规划问题化为标准型(1)(1)令令x x4 4x x5 5x x3 3，其中，其中x x4 4，x x5 500；(2)(2)在第一个约束不等式在第一个约束不等式号的左端号的左端加入加入加入加入松弛变量松弛变量x x6 6；(3)(3)在第二个约束不等式在第二个约束不等式号的左端号的左端减去减去减去减去剩余变量剩余变量x x7 7；(4)(4)令令z=-zz=-z，把求，把求min z min z 改为求改为求max zmax z，即可得到，即可得到该问题的标准型该问题的标准型标准式标准式（4 4）右端项系数右端项系数右端项右端项b bi i 0 0时，只需将等式两端同乘（时，只需将等式两端同乘（-1-1）则右端项必大于零则右端项必大于零 例：例：将将 LP LP 问题问题min z=-xmin z=-x1 1+2x+2x2 2-3x-3x3 3 s.t.xs.t.x1 1+x+x2 2+x+x3 3 77 x x1 1-x-x2 2+x+x3 3 2 2 -3x -3x1 1+x+x2 2+2x+2x3 3=-5=-5 x x1 1,x,x2 2 0 0 化为标准形式化为标准形式。解解：令令 x x3 3=x=x4 4-x-x5 5 其中其中x x4 4、x x5 5 00；对第一个约束条件加上松弛变量对第一个约束条件加上松弛变量 x x6 6 ；对第二个约束条件减去松弛变量对第二个约束条件减去松弛变量 x x7 7 ；对第三个约束条件两边乘以对第三个约束条件两边乘以“-1-1”；令令 z z=-z=-z 把求把求 min zmin z 改为求改为求 max zmax zmax z=x1-2x2+3x4-3x5 s.t.x1+x2+x4-x5+x6=7 x1-x2+x4-x5-x7=2 3x1-x2-2x4+2x5=5 x1,x2,x4,x5,x6,x70 1.4 1.4 线性规划问题的解的概念线性规划问题的解的概念v1.1.可行解、可行解集（可行域）可行解、可行解集（可行域）最优解、最优值最优解、最优值v2.2.基、基变量、非基变量基、基变量、非基变量v3.3.基本解，基本可行解基本解，基本可行解v4.4.可行基、最优基可行基、最优基 1.1.可行解，可行域，最优解可行解，可行域，最优解满满足足约约束束条条件件(1-5)(1-5)，(1-6)(1-6)式式的的解解X=(xX=(x1 1,x,x2 2，x xn n)T T，称为线性规划问题的，称为线性规划问题的可行解可行解可行解可行解；其中使目标函数达到最大值的可行解称为其中使目标函数达到最大值的可行解称为最优解最优解最优解最优解最大的目标函数值称为最大的目标函数值称为最优值最优值最优值最优值；全部可行解的集合称为全部可行解的集合称为可行域可行域可行域可行域。对于标准的对于标准的LPLP来说来说满足这两个条件的满足这两个条件的满足这两个条件的满足这两个条件的x x x x是可行解或者可行点是可行解或者可行点是可行解或者可行点是可行解或者可行点三者皆满足是最优解三者皆满足是最优解三者皆满足是最优解三者皆满足是最优解2.2.基，基向量，基变量，非基变量基，基向量，基变量，非基变量设设A A是约束方程组是约束方程组mnmn维的系数矩阵，其维的系数矩阵，其秩为秩为mm，B B是矩阵是矩阵A A中中mmmm阶非奇异子矩阵（阶非奇异子矩阵（B B的行列式的行列式B0B0），），则称则称B B是线性规划问题的一个基阵或是线性规划问题的一个基阵或基基基基。此标准型最多有此标准型最多有 个基个基（1 1）基）基max z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2 0LPLP的基有：的基有：B B1 1，B B2 2 ，B B3 3B B4 4不是不是LPLP的基的基 1 0 0 0 1 0 0 0 1B1=系数矩阵系数矩阵:1 2 1 0 0 1 2 1 0 0 4 0 0 1 0 4 0 0 1 0 0 4 0 0 1 0 4 0 0 1A=1 2 1 4 0 0 0 4 0B2=1 2 0 4 0 1 0 4 0B3=2 1 0 0 0 0 4 0 1B4=（2 2）基向量，基变量，非基向量）基向量，基变量，非基向量（a)a)称称 p pi i(i=1,2,(i=1,2,m),m)为为基向量基向量基向量基向量，它们是一组它们是一组 线性无关线性无关线性无关线性无关的向量组；的向量组；(b)(b)对应的向量对应的向量x xi i(i=1,2,(i=1,2,m),m)为为基变量基变量基变量基变量；(d)(d)对应的变量对应的变量x xj j(j=m+1,(j=m+1,n),n)为为非基变量非基变量非基变量非基变量，非基变量也称为非基变量也称为自由变量或独立变量自由变量或独立变量，可自由取值可自由取值。(c)(c)其他向量其他向量p pj j(j=m+1,(j=m+1,n),n)为为非基向量非基向量非基向量非基向量，有，有n-mn-mn-mn-m个，个，上述基上述基B B 中中（B0B0）2.2.基，基向量，基变量，非基向量基，基向量，基变量，非基向量基变量基变量 在有在有n n个变量、个变量、mm个约束方程的标准个约束方程的标准型线性规划问题中，型线性规划问题中，若取其中的若取其中的mm个变量，且这些变量在约束方个变量，且这些变量在约束方程中对应的程中对应的mm个系数列向量是个系数列向量是线性无关线性无关的的，则它们组成一组基变量。则它们组成一组基变量。确定了一组基变量后，其它确定了一组基变量后，其它n-mn-m个变量称为个变量称为非基变量。非基变量。约束方程可改写为：约束方程可改写为：X1 X2 Xm Xm1 Xn用向量的形式表示为：用向量的形式表示为：1-7B B B B1 1 1 1中中中中P3=（1，0，0）T，P4=（0，1，0）T P5=（0，0，1）T是基向量是基向量是基向量是基向量对应基变量为：对应基变量为：x3，x4，x5非基变量为：非基变量为：x1，x2=（P P3 3，P P4 4，P P5 5）系数矩阵系数矩阵:1 2 1 0 0 1 2 1 0 0 4 0 0 1 0 4 0 0 1 0 0 4 0 0 1 0 4 0 0 1A=1 0 0 0 1 0 0 0 1B1=max z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =8 4x1 +x4 =16 4x2 +x5=12 x1,x2 0令方程组（令方程组（1-5)1-5)的基是的基是B B，设，设X XB B是对应于这个基是对应于这个基B B的的基变量，记基变量，记X XB B=（X X1 1，X X2 2，X Xmm）T T,若令上式的非基变量若令上式的非基变量X Xmm1 1X Xmm2 2X Xn n0 0，约束方程变成约束方程变成mm元一次方程，利用元一次方程，利用=BjBB0B0 X=X=（X X1 1，X X2 2，X Xmm，0 0，0 0）T T，称称X X为为基解基解基解基解。n-m该基解所得非零分量的个数该基解所得非零分量的个数不大于不大于不大于不大于方程的个数方程的个数mm3.基解基解,基可行解基可行解 (1)基解基解可以求出一个解：可以求出一个解：满足非负约束条件满足非负约束条件(1-6)(1-6)的基解。称为的基解。称为基可行解基可行解基可行解基可行解。(2)基本可行解基本可行解 一个一个基可行解基可行解基可行解基可行解的非零分量个数也不超过的非零分量个数也不超过mm个，个，并且并且都是非负的都是非负的都是非负的都是非负的。一个一个基解基解基解基解的非零分量个数不超过的非零分量个数不超过mm个，个，其分量其分量可以有负的可以有负的可以有负的可以有负的；基可行解和基解的数目最多是基可行解和基解的数目最多是 个。个。一般基可行解的数目要一般基可行解的数目要小于小于小于小于基解的数目。基解的数目。4.4.可行基可行基对应于基可行解的基，称为对应于基可行解的基，称为可行基可行基可行基可行基。当基可行解为最优解时当基可行解为最优解时,对应的基称对应的基称最优基最优基最优基最优基。基可行解基可行解的非零分量个数的非零分量个数 m m 时，此时的时，此时的基可行解基可行解称为称为退化退化退化退化解。解。解。解。关于标准型解的若干基本概念小结：关于标准型解的若干基本概念小结：关于标准型解的若干基本概念小结：关于标准型解的若干基本概念小结：可行解与非可行解可行解与非可行解可行解与非可行解可行解与非可行解 满足约束条件和非负条件的解满足约束条件和非负条件的解 X X 称为可行解，满足称为可行解，满足约束条件但不满足非负条件的解约束条件但不满足非负条件的解 X X 称为非可行解。称为非可行解。基解基解基解基解令非基变量令非基变量 X XN N=0 0，求得基变量，求得基变量 X XB B ,则则(X(XB B,X,XNN)称为基解，其中称为基解，其中 X XB B=B B 1 1 b ,Xb ,XN N =0 =0 。(X(X(X(XB B B B ,X,X,X,XN N N N )是是是是基解基解基解基解的的的的必要条件必要条件必要条件必要条件为为为为X X X XB B B B 的非零分量的个的非零分量的个的非零分量的个的非零分量的个数数数数 m m m m。基可行解基可行解基可行解基可行解基解基解 中中,X XB B 的非零分量都的非零分量都 0 0 时，称为时，称为基可行解，基可行解，否则为基非可行解。否则为基非可行解。基可行解基可行解的非零分量个数的非零分量个数 m m 时，称为退化时，称为退化解。解。可可可可行行行行解解解解不不不不可可可可行行行行解解解解基基基基 解解解解基可行解基可行解基可行解基可行解满足全部约束条件的解，对应可行域内的所有点满足全部约束条件的解，对应可行域内的所有点只满足约束方程，不满足非负条件的解，对应只满足约束方程，不满足非负条件的解，对应所有约束直线的交点所有约束直线的交点满足全部约束条件，且有满足全部约束条件，且有n-mn-m个分个分量为量为0 0的解，对应可行域的顶点的解，对应可行域的顶点以上提到的几种解的概念，它们之间的关系可以上提到的几种解的概念，它们之间的关系可以上提到的几种解的概念，它们之间的关系可以上提到的几种解的概念，它们之间的关系可用下面图表明。用下面图表明。用下面图表明。用下面图表明。是基本解是基本解是基本解是基本解不是可行解不是可行解不是可行解不是可行解可行解示例可行解示例对于对于对于对于LPLPLPLP：基本可行基本可行基本可行基本可行解解解解可行基可行基可行基可行基基基基基 可行解、基础解和基础可行解举例可行解、基础解和基础可行解举例可行解、基础解和基础可行解举例可行解、基础解和基础可行解举例反之，如果有一个基变量也取零值，则称它是反之，如果有一个基变量也取零值，则称它是退化解退化解退化解退化解,即基解中的非零分量的个数小于即基解中的非零分量的个数小于mm个时，个时，则该基解是则该基解是退化解退化解退化解退化解。v在以下讨论时，假设不出现退化的情况。在以下讨论时，假设不出现退化的情况。v以上给出了线性规划问题的解的概念和定义，以上给出了线性规划问题的解的概念和定义，它们将有助于用来分析线性规划问题的求解过程。它们将有助于用来分析线性规划问题的求解过程。在在LPLP的一个基可行解中，如果它的所有的基变的一个基可行解中，如果它的所有的基变量都取正值，则称它量都取正值，则称它是非退化的解是非退化的解是非退化的解是非退化的解；小结小结v1.1.线性规划问题的模型特征线性规划问题的模型特征v2.2.通过图解法了解如何求解线性规划问题通过图解法了解如何求解线性规划问题v3.3.为求解高维线性规划问题，必须建立的为求解高维线性规划问题，必须建立的概念概念练习练习1：X1+2X2+X3=30=30 3X1+2X2 +X4=60 2X2 +X5=24 X1 X5 0 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=X1X2X3X4X5X=b=306024B=(PB=(P3 3 P P4 4 P P5 5)=I )=I 是满秩子矩阵是满秩子矩阵 非基非基 N=(PN=(P1 1 P P2 2)X3=30-(X1+2 X2)X4=60-(3X1+2 X2)X5=24 -2 X2令令X1=X2=0,X3=30,X4=60,X5=24X=XN 0 XB B-1 b00306024练习练习2：给定约束条件：给定约束条件 -X3+X4=0=0 X2+X3+X4=3 -X1+X2+X3+X4=2 Xj 0 0(j=1,2,3,4)求出基变量是求出基变量是X X1 1,X,X3 3,X,X4 4的基本解，是不的基本解，是不是可行解？是可行解？0 -1 1解：解：B=(P1 P3 P4)=0 1 1 -1 1 1 0 1 -1 0B-1=-1/2 1/2 0 3 1/2 1/2 0 2b=X1 X3 =B-1 b X4 XB=0 1 -1 0 1 =-1/2 1/2 0 3 =3/2 1/2 1/2 0 2 3/2X=(1,0,3/2,3/2)T 是是