线性规划基础知识.ppt

线性规划线性规划 Linear Programming1 线性规划发展简史线性规划发展简史 线性规划问题最早是前苏联学者康德洛维奇（线性规划问题最早是前苏联学者康德洛维奇（L.V.Kantorovich）于于1939年提出的。年提出的。1952年，美国国家标准局（年，美国国家标准局（NBS）在当时的在当时的SEAC电子计算机上首次实现单纯形算法。电子计算机上首次实现单纯形算法。1976年年IBM研制成功功能十分强大、计算效率极研制成功功能十分强大、计算效率极高的线性规划软件高的线性规划软件MPS，后来又发展成为更为完善的后来又发展成为更为完善的MPSX。线性规划是目前应用最广泛的一种系统优化方法。线性规划是目前应用最广泛的一种系统优化方法。LP研究两类问题研究两类问题 一类是当一项任务确定后，如何统筹安排，一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力资源去完成。尽量做到以最少的人力、物力资源去完成。另一类是已有一定数量的人力、物力资源，另一类是已有一定数量的人力、物力资源，如何安排使用它们，使完成的任务（或创造的如何安排使用它们，使完成的任务（或创造的财富、利润）最多。财富、利润）最多。2 线性规划问题线性规划问题 根据实际问题的要求，可以建根据实际问题的要求，可以建立线性规划问题数学模型。线性立线性规划问题数学模型。线性规划问题由目标函数和约束条件规划问题由目标函数和约束条件两部分组成。两部分组成。2.1 生产计划问题生产计划问题某某工工厂厂拥拥有有A、B、C三三种种类类型型的的设设备备，生生产产甲甲、乙乙、丙丙、丁丁四四种种产产品品。每每件件产产品品在在生生产产中中需需要要占占用用的的设设备备机机时时数数，每每件件产产品品可可以以获获得得的的利利润润以以及及三三种种设设备备可可利利用的时数如下表所示：用的时数如下表所示：用线性规划制订使总利润最大的生产计。用线性规划制订使总利润最大的生产计。设设变变量量xi为为第第i种种产产品品的的生生产产件件数数（i1，2，3，4），目目标标函函数数z为为相相应应的的生生产产计计划划可可以以获获得得的的总总利利润润。在在加加工工时时间间以以及及利利润润与与产产品品产产量量成成线线性关系的假设下，可以建立如下的线性规划模型：性关系的假设下，可以建立如下的线性规划模型：这这是是一一个个典典型型的的利利润润最最大大化化的的生生产产计计划划问问题题。求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1=293.6，x2=1500，x3=0，x4=58.84（件）件）最大利润为：最大利润为：z=12734.41（元）元）请注意最优解中利润率最高的产品丙在最优生产请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。法安排生产计划很难获得满意的结果。2.2 配料问题配料问题某工厂要用四种合金某工厂要用四种合金T1，T2，T3和和T4为原料，经熔炼成为原料，经熔炼成为一种新的不锈钢为一种新的不锈钢G。这四种原料含元素铬（这四种原料含元素铬（Cr），），锰锰（Mn）和镍（和镍（Ni）的含量（的含量（%），这四种原料的单价以），这四种原料的单价以及新的不锈钢材料及新的不锈钢材料G所要求的所要求的Cr，Mn和和Ni的最低含量的最低含量（%）如下表所示：）如下表所示：设设熔熔炼炼时时重重量量没没有有损损耗耗，要要熔熔炼炼成成100公公斤斤不不锈锈钢钢G，应选用原料应选用原料T1，T2，T3和和T4各多少公斤，使成本最小。各多少公斤，使成本最小。设设选选用用原原料料T1，T2，T3和和T4分分别别为为x1，x2，x3，x4公公斤斤，根据条件，可建立相应的线性规划模型如下：根据条件，可建立相应的线性规划模型如下：这这是是一一个个典典型型的的成成本本最最小小化化的的问问题题。这这个个线线性性规规划划问问题题的的最优解是最优解是x1=26.58，x2=31.57，x3=41.84，x4=0（公斤）公斤）最低成本为最低成本为z=9549.87（元）元）2.3 背包问题背包问题 一只背包最大装载重量为一只背包最大装载重量为50公斤。现有三公斤。现有三种物品，每种物品数量无限。每种物品每件种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：的重量、价值如下表所示：要要在在背背包包中中装装入入这这三三种种物物品品各各多多少少件件，使使背背包中的物品价值最高。包中的物品价值最高。设设装装入入物物品品1，物物品品2和和物物品品3各各为为x1，x2，x3件件，由由于于物物品品的的件件数数必必须须是是整整数数，因因此此背背包包问问题题的的线线性性规规划模型是一个整数规划问题：划模型是一个整数规划问题：这这个个问问题题的的最最优优解解是是：x1=1(件件),x2=0(件件),x3=2(件件),最高价值为：最高价值为：z=87（元）（元）2.4 运输问题运输问题 设某种物资从两个供应地设某种物资从两个供应地A1，A2运往三个需求运往三个需求地地B1，B2，B3。各供应地的供应量、各需求地的各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运需求量、每个供应地到每个需求地的单位物资运价如下表所示。价如下表所示。设设xij为从供应地为从供应地 Ai 运往需求地运往需求地 Bj 的物资数量的物资数量（i=1,2；j=1,2,3），），z为总运费，则总运费最小的为总运费，则总运费最小的线性规划模型为：线性规划模型为：xij0 以上约束条件（以上约束条件（1）、（）、（2）称为供应地）称为供应地约束，（约束，（3）、（）、（4）、（）、（5）称为需求地约）称为需求地约束。束。这个问题的最优解为：这个问题的最优解为：x11=0，x12=30，x13=5（吨）；吨）；x21=10,x22=0,x23=15（吨）。吨）。最小运费为：最小运费为：z=275元。元。2.5 指派问题指派问题 有有n项任务由项任务由n个人去完成，每项任务交给一个人去完成，每项任务交给一个人，每个人都有一项任务。由第个人，每个人都有一项任务。由第i个人去做第个人去做第j项任务的成本（或效益）为项任务的成本（或效益）为cij。求使总成本最小求使总成本最小（或效益最大）的分配方案。（或效益最大）的分配方案。设：得到以下的线性规划模型：得到以下的线性规划模型：例如，有张、王、李、赵例如，有张、王、李、赵4位教师被分配教语文、数学、位教师被分配教语文、数学、物理、化学物理、化学4门课程，每位教师教一门课程，每门课程由一位门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：门课程的平均成绩如下表：四位教师每人只能教一门课，每一门课只能由一个教师来四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。为最高。设设xij（i=1,2,3,4；j=1,2,3,4）为第为第i个教师是个教师是否教第否教第j门课，门课，xij只能取值只能取值0或或1，其意义如下：，其意义如下：变量变量xij与教师与教师 i 以及课程以及课程 j 的关系如下：的关系如下：这个指派问题的线性规划模型为：这个指派问题的线性规划模型为：maxz=92x11+68x12+85x13+76x14 +82x21+91x22+77x23+63x24 +83x31+90 x32+74x33+65x34 +93x41+61x42+83x43+75x44 这个指派问题的线性规划模型为：这个指派问题的线性规划模型为：s.t.x11+x12+x13+x14=1 （1）x21+x22+x23+x24=1 （2）x31+x32+x33+x34=1 （3）x41+x42+x43+x44=1 （4）x11+x21+x31+x41=1 （5）x12+x22+x32+x42=1 （6）x13+x23+x33+x43=1 （7）x14+x24+x34+x44=1 （8）xij=0,1 这个问题的最优解为这个问题的最优解为 x14=1，x23=1，x32=1，x41=1，max z=336；即张老师教化学，王老即张老师教化学，王老师教物理，李老师教数学，赵老师教语文，如师教物理，李老师教数学，赵老师教语文，如果这样分配教学任务，四门课的平均总分可以果这样分配教学任务，四门课的平均总分可以达到达到336分。分。在在LPLP问题中，如果所有的变量都只能取值问题中，如果所有的变量都只能取值0或或1。这样的。这样的LPLP问题称为（纯）问题称为（纯）01整数规划整数规划问题。问题。如果一个如果一个LPLP问题中，有的变量是连续变量，问题中，有的变量是连续变量，而另一些变量是而另一些变量是01变量，这样的问题称为变量，这样的问题称为混合混合01规划问题。规划问题。LPLP问题的一般形式：问题的一般形式：记向量和矩阵记向量和矩阵 则则LP问题可由向量和矩阵表示问题可由向量和矩阵表示:max(min)zCTX s.t.AX(,)b X0 3 线性规划问题的规范形式和标准形式线性规划问题的规范形式和标准形式为为了了今今后后讨讨论论的的方方便便，我我们们称称以以下下两两种种形形式式的的线线性性规规划问题为线性规划的规范形式（划问题为线性规划的规范形式（Canonical Form）:minzCTXs.t.AXb X0max zCTXs.t.AXb X0 而而称称以以下下的的形形式式为为标标准准形形式式（Standard Form）：）：min zCTXs.t.AXb X0 对对于于各各种种非非标标准准形形式式的的线线性性规规划划问问题题，我我们们总可以通过以下的变换，将其转化为标准形式。总可以通过以下的变换，将其转化为标准形式。3.1 极大化目标函数的问题极大化目标函数的问题设目标函数为设目标函数为:令令zz，则则以以上上极极大大化化问问题题和和极极小小化化问问题题有有相相同的最优解，即同的最优解，即:但但必必须须注注意意，尽尽管管以以上上两两个个问问题题的的最最优优解解相相同同，但但他们最优解的目标函数值却相差一个符号，即他们最优解的目标函数值却相差一个符号，即:max zmin z3.2 约束条件不是等式的问题约束条件不是等式的问题设约束条件为设约束条件为:可以引进一个新的变量可以引进一个新的变量 ，使它等于约束右使它等于约束右边与左边之差边与左边之差:显显然然 也也具具有有非非负负约约束束，即即 ，这这时时新的约束条件成为新的约束条件成为:当约束条件为当约束条件为:时，类似地令时，类似地令:则同样有则同样有 ，新的约束条件成为新的约束条件成为:为为了了使使约约束束由由不不等等式式成成为为等等式式而而引引进进的的变变量量 称称为为“松松弛弛变变量量”。如如果果原原问问题题中中有有若若干干个个非非等等式式约约束束，则则将将其其转转化化为为标标准准形形式式时时，必必须须对对各各个个约约束束引引进进不不同同的松弛变量。的松弛变量。例：将以下线性规划问题转化为标准形式例：将以下线性规划问题转化为标准形式 将将目目标标函函数数转转换换成成极极小小化化，并并分分别别对对约约束束（1）、（2）引引进进松松弛弛变变量量x4，x5，得得到到以以下下标准形式的线性规划问题：标准形式的线性规划问题：3.3 变量无符号限制的问题变量无符号限制的问题 在标准形式中，每一个变量都有非负约束。当一在标准形式中，每一个变量都有非负约束。当一个变量个变量 没有非负约束时，可以令没有非负约束时，可以令：其中其中 即用两个非负变量之差来表示一个无符号限即用两个非负变量之差来表示一个无符号限制的变量，当制的变量，当 的符号取决于的符号取决于 和和 的大小。的大小。例例:将以下线性规划问题转化为标准形式将以下线性规划问题转化为标准形式 x1,x30,x2无符号限制无符号限制 令令 ，引进松弛变量引进松弛变量x4，x5，并令并令:得到以下等价的标准形式得到以下等价的标准形式:min z =-2x1+3x2-3x2 -x3 s.t.x1-x2+x2 +2x3+x4 =3 2x1+3x2-3x2 -x3 -x5=5 x1+x2-x2 +x3 =4 x1,x2,x2,x3,x4,x5 0 4 线性规划问题的几何解释线性规划问题的几何解释 对于只有两个变量的线性对于只有两个变量的线性规划问题，可以在二维直角规划问题，可以在二维直角坐标平面上表示线性规划问坐标平面上表示线性规划问题。题。例例4.1 其中满足约束其中满足约束(1)的点的点 位于坐标平面上直线位于坐标平面上直线x1+x2=6靠近原点的一侧。同样，满足约束靠近原点的一侧。同样，满足约束(2)的点的点位于坐标平面上直线位于坐标平面上直线x1+2x2=8的靠近原点的一侧。的靠近原点的一侧。而变量而变量x1，x2的非负约束表明满足约束条件的点同的非负约束表明满足约束条件的点同时应位于第一象限内。时应位于第一象限内。称满足线性规划问题所有约束条称满足线性规划问题所有约束条件（包括变量非负约束）的向量。件（包括变量非负约束）的向量。为线性规划的可行解（为线性规划的可行解（Feasible Solution），），称可行解的集合为可称可行解的集合为可行域（行域（Feasible Region）。）。例例4.1的线性规划问题的可行域如图中阴影部的线性规划问题的可行域如图中阴影部分所示。分所示。为了在图上表示目标函数，令为了在图上表示目标函数，令z=z0为某一确定的目标为某一确定的目标函数值，取一组不同的函数值，取一组不同的z0值，在图上得到一组相应的值，在图上得到一组相应的平行线，称为目标函数等值线。在同一条等值线上的平行线，称为目标函数等值线。在同一条等值线上的点，相应的可行解的目标函数值相等。在图中，给出点，相应的可行解的目标函数值相等。在图中，给出了了z=0，z=3，z=6，z=15.3等一组目标函数等值线，等一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线沿对于目标函数极大化问题，这一组目标函数等值线沿目标函数增大而平行移动的方向（即目标函数梯度方目标函数增大而平行移动的方向（即目标函数梯度方向）就是目标函数的系数向量向）就是目标函数的系数向量 ；对于对于极小化问题，目标函数则沿极小化问题，目标函数则沿-C方向平行移动。方向平行移动。目标函数等值线在平行移动过程中与可行域的最目标函数等值线在平行移动过程中与可行域的最后一个交点是后一个交点是B点，这就是线性规划问题的最优解，点，这就是线性规划问题的最优解，这个最优解可以由两直线这个最优解可以由两直线：的交点求得的交点求得 最优解的目标函数值为最优解的目标函数值为 定义定义4.1 在在n n维空间中，满足条件维空间中，满足条件 的点集的点集 超平面。向量超平面。向量 称为该超平面的法向量称为该超平面的法向量称为一个称为一个定义定义4.2 满足条件满足条件 的点集的点集 称为称为n维空间中的一个半空间。维空间中的一个半空间。定义定义4.3 有限个半空间的交集，即同时满足有限个半空间的交集，即同时满足以下条件的非空点集以下条件的非空点集 称为称为n维空间中的一个多面体维空间中的一个多面体 运用矩阵记号，运用矩阵记号，n维空间中的多面体也可记为维空间中的多面体也可记为 AX（或或）b定定义义4.4 设设S是是n维维空空间间中中的的一一个个点点集集。若若对对任任意意n维维向向量量X1 S，X2 S，且且X1 X2，以以及及任任意实数意实数（01），有），有则称则称S为为n维空间中的一个凸集。点维空间中的一个凸集。点X称为点称为点X1和和X2的凸组合。的凸组合。以上定义的几何意义，它表示凸集以上定义的几何意义，它表示凸集S中的任意两个中的任意两个不相同的点连线上的点（包括这两个端点），都位于不相同的点连线上的点（包括这两个端点），都位于凸集凸集S之中。之中。下图表示二维平面中一些凸集和非凸集的例子。下图表示二维平面中一些凸集和非凸集的例子。(a)凸集凸集 (b)凸集凸集 (c)凸集凸集(d)非凸集非凸集(e)非凸集非凸集 (f)非凸集非凸集运用以上的定义，线性规划的可行域以及最优解有以运用以上的定义，线性规划的可行域以及最优解有以下性质：下性质：定义定义4.5 设设S为一凸集，且为一凸集，且X S，X1 S，X2 S。对于对于0 01 1，若，若 则称则称X为为S的一个极点的一个极点。必定有必定有X=X1=X2，1、若线性规划的可行域非空，则可行域必定为一凸、若线性规划的可行域非空，则可行域必定为一凸集集,可行域可能有界可行域可能有界,也可能无界也可能无界,但其顶点（极点）但其顶点（极点）个数为有限个。个数为有限个。2、若线性规划有最优解，则最优解至少位于一个极、若线性规划有最优解，则最优解至少位于一个极点上。点上。求线性规划最优解的问题，从在可行域内无限个求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。上搜索的问题。