线性规划基础知识

1、线性规划线性规划 Linear Programming1 线性规划发展简史线性规划发展简史 线性规划问题最早是前苏联学者康德洛维奇（线性规划问题最早是前苏联学者康德洛维奇（L.V. Kantorovich）于）于1939年提出的。年提出的。 1952年，美国国家标准局（年，美国国家标准局（NBS）在当时的）在当时的SEAC电子计算机上首次实现单纯形算法。电子计算机上首次实现单纯形算法。 1976年年IBM研制成功功能十分强大、计算效率极研制成功功能十分强大、计算效率极高的线性规划软件高的线性规划软件MPS，后来又发展成为更为完善的，后来又发展成为更为完善的MPSX。 线性规划是目前应用最广泛的

2、一种系统优化方法。线性规划是目前应用最广泛的一种系统优化方法。LP研究两类问题研究两类问题 一类是当一项任务确定后，如何统筹安排，一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力资源去完成。尽量做到以最少的人力、物力资源去完成。 另一类是已有一定数量的人力、物力资源，另一类是已有一定数量的人力、物力资源，如何安排使用它们，使完成的任务（或创造的如何安排使用它们，使完成的任务（或创造的财富、利润）最多。财富、利润）最多。2 线性规划问题线性规划问题 根据实际问题的要求，可以建根据实际问题的要求，可以建立线性规划问题数学模型。线性立线性规划问题数学模型。线性规划问题由目标函数和约束

3、条件规划问题由目标函数和约束条件两部分组成。两部分组成。2.1 生产计划问题生产计划问题某工厂拥有某工厂拥有A、B、C三种类型的设备，生产甲、乙、三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：用的时数如下表所示：每件产品占用的 机时数（小时/件） 产品甲 产品乙 产品丙 产品丁 设备能力 （小时） 设备 A 1.5 1.0 2.4 1.0 2000 设备 B 1.0 5.0 1.0 3.5 8000 设备 C

4、1.5 3.0 3.5 1.0 5000 利润（元/件） 5.24 7.30 8.34 4.18 用线性规划制订使总利润最大的生产计。用线性规划制订使总利润最大的生产计。 设变量设变量xi为第为第i种产品的生产件数（种产品的生产件数（i1，2，3，4），目标函数），目标函数z为相应的生产计划可以获得为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：性关系的假设下，可以建立如下的线性规划模型：max z= 5.24x1 +7.30 x2 +8.34x3 +4.18x4 s.t. 1.5x1 +1

5、.0 x2 +2.4x3 +1.0 x4 2000 1.0 x1 +5.0 x2 +1.0 x3 +3.5x4 8000 1.0 x1 +3.0 x2 +3.5x3 +1.0 x4 5000 x1, x2, x3, x4 0 这是一个典型的利润最大化的生产计划问题。这是一个典型的利润最大化的生产计划问题。求解这个线性规划，可以得到最优解为：求解这个线性规划，可以得到最优解为：x1=293.6，x2=1500，x3=0，x4=58.84（件）（件）最大利润为：最大利润为： z=12734.41（元）（元） 请注意最优解中利润率最高的产品丙在最优生产请注意最优解中利润率最高的产品丙在最优生产计划中

6、不安排生产。说明按产品利润率大小为优先计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。法安排生产计划很难获得满意的结果。 2.2 配料问题配料问题某工厂要用四种合金某工厂要用四种合金T1，T2，T3和和T4为原料，经熔炼成为原料，经熔炼成为一种新的不锈钢为一种新的不锈钢G。这四种原料含元素铬（。这四种原料含元素铬（Cr），锰），锰（Mn）和镍（）和镍（Ni）的含量（）的含量（%），这四种原料

7、的单价），这四种原料的单价以及新的不锈钢材料以及新的不锈钢材料G所要求的所要求的Cr，Mn和和Ni的最低含的最低含量（量（%）如下表所示：）如下表所示： T1 T2 T3 T4 G Cr 3.21 4.53 2.19 1.76 3.20 Mn 2.04 1.12 3.57 4.33 2.10 Ni 5.82 3.06 4.27 2.73 4.30 单价(元/公斤) 115 97 82 76 设熔炼时重量没有损耗，要熔炼成设熔炼时重量没有损耗，要熔炼成100公斤不锈钢公斤不锈钢G，应选用原料应选用原料T1，T2，T3和和T4各多少公斤，使成本最小。各多少公斤，使成本最小。设选用原料设选用原料T1

8、，T2，T3和和T4分别为分别为x1，x2，x3，x4公斤，公斤，根据条件，可建立相应的线性规划模型如下：根据条件，可建立相应的线性规划模型如下： min z= 115x1 +97x2 +82x3 +76x4 s.t. 0.0321x1 +0.0453x2 +0.0219x3 +0.0176x4 3.20 0.0204x1 +0.0112x2 +0.0357x3 +0.0433x4 2.10 0.0204x1 +0.0112x2 +0.0357x3 +0.0433x4 4.30 x1 +x2 +x3 +x4 =100 x1, x2, x3, x4 0 这是一个典型的成本最小化的问题。这个线性规

9、划问题的这是一个典型的成本最小化的问题。这个线性规划问题的最优解是最优解是x1=26.58，x2=31.57，x3=41.84，x4=0（公斤）（公斤）最低成本为最低成本为z=9549.87（元）（元）2.3 背包问题背包问题 一只背包最大装载重量为一只背包最大装载重量为50公斤。现有三公斤。现有三种物品，每种物品数量无限。每种物品每件种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：的重量、价值如下表所示： 物品 1 物品 2 物品 3 重量（公斤/件） 10 41 20 价值（元/件） 17 72 35 要在背包中装入这三种物品各多少件，使背要在背包中装入这三种物品各多少件，使

10、背包中的物品价值最高。包中的物品价值最高。 设装入物品设装入物品1，物品，物品2和物品和物品3各为各为x1，x2，x3件，件，由于物品的件数必须是整数，因此背包问题的线性由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：规划模型是一个整数规划问题：max z=17x1 +72x2 +35x3 s.t. 10 x1 +41x2 +35x3 50 x1, x2, x3 0, x1, x2, x3是整数 这个问题的最优解是：这个问题的最优解是：x1=5(件件), x2=0(件件), x3=0(件件), 最高价值为：最高价值为：z=85（元）（元）2.4 运输问题运输问题 设某种

11、物资从两个供应地设某种物资从两个供应地A1，A2运往三个需求运往三个需求地地B1，B2，B3。各供应地的供应量、各需求地的。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运需求量、每个供应地到每个需求地的单位物资运价如下表所示。价如下表所示。 运价（元/吨） B1 B2 B3 供应量（吨） A1 2 3 5 35 A2 4 7 8 25 需求量（吨） 10 30 20 设设xij为从供应地为从供应地 Ai 运往需求地运往需求地 Bj 的物资数量的物资数量（i=1,2；j=1,2,3），），z为总运费，则总运费最小的为总运费，则总运费最小的线性规划模型为：线性规划模型为：

12、min z= 2x11 +3x12 +5x13 +4x21 +7x22 +8x23 s.t. x11 +x12 +x13 =35 (1) x21 +x22 +x23 =25 (2) x11 +x21 =10 (3) x12 +x22 =30 (4) x13 +x23 =20 (5) xij0 以上约束条件（以上约束条件（1）、（）、（2）称为供应地）称为供应地约束，（约束，（3）、（）、（4）、（）、（5）称为需求地约）称为需求地约束。束。这个问题的最优解为：这个问题的最优解为： x11=0，x12=30， x13=5（吨）；（吨）；x21=10,x22=0, x23=15（吨）。（吨）。 最

13、小运费为：最小运费为：z=275元。元。 2.5 指派问题指派问题 有有n项任务由项任务由n个人去完成，每项任务交给一个人去完成，每项任务交给一个人，每个人都有一项任务。由第个人，每个人都有一项任务。由第i个人去做第个人去做第j项任务的成本（或效益）为项任务的成本（或效益）为cij。求使总成本最小。求使总成本最小（或效益最大）的分配方案。（或效益最大）的分配方案。 xijijij01第 个人不从事第 项任务第 个人被指派完成第 项任务设： 得到以下的线性规划模型：得到以下的线性规划模型： min(max). ., , ,zc xs txjnxinxijijjninijinijjnij11111

14、1211201 例如，有张、王、李、赵例如，有张、王、李、赵4位教师被分配教语文、数学、位教师被分配教语文、数学、物理、化学物理、化学4门课程，每位教师教一门课程，每门课程由一位门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：门课程的平均成绩如下表： 语文 数学 物理 化学 张 92 68 85 76 王 82 91 77 63 李 83 90 74 65 赵 93 61 83 75 四位教师每人只能教一门课，每一门课只能由一个教师来四位教师每人只能教一门课，每一门课只能由

15、一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。为最高。 设设xij（i=1, 2, 3, 4；j=1, 2, 3, 4）为第）为第i个教师个教师是否教第是否教第j门课，门课，xij只能取值只能取值0或或1，其意义如下：，其意义如下： xijijij01第 个教师不教第 门课第 个教师教第 门课变量变量xij与教师与教师 i 以及课程以及课程 j 的关系如下：的关系如下： i j 语文 数学 物理 化学 张 x11 x12 x13 x14 王 x21 x22 x23 x24 李 x31 x32 x33 x34 赵 x

16、41 x42 x43 x44 这个指派问题的线性规划模型为：这个指派问题的线性规划模型为： 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

17、+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问题称为（纯）问

18、题称为（纯）01整数规划整数规划问题。问题。 如果一个如果一个LPLP问题中，有的变量是连续变量，问题中，有的变量是连续变量，而另一些变量是而另一些变量是01变量，这样的问题称为变量，这样的问题称为混合混合01规划问题。规划问题。LPLP问题的一般形式：问题的一般形式： max(min)zc xc xc xnn1122s ta xaxaxbaxaxaxbaxaxaxbnnnmmmnnm. .( . )( . )( . )1111221n1211222221122 xxxn110,记向量和矩阵记向量和矩阵 C=cccn12，X=xxxn12，b=bbbn12，A=aaaaaaaaanmmmn11

19、121n2122212 则则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 对于各种非标准形式

20、的线性规划问题，我们对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式。总可以通过以下的变换，将其转化为标准形式。3.1 极大化目标函数的问题极大化目标函数的问题设目标函数为设目标函数为:maxzc xc xc xnn1122 令令zz，则以上极大化问题和极小化问题有相，则以上极大化问题和极小化问题有相同的最优解，即同的最优解，即:min zc xc xc xnn 1122 但必须注意，尽管以上两个问题的最优解相同，但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即但他们最优解的目标函数值却相差一个符号，即:max zmin z3.

21、2 约束条件不是等式的问题约束条件不是等式的问题设约束条件为设约束条件为:a xa xa xbimiiinni112212(, ,) 可以引进一个新的变量可以引进一个新的变量 ，使它等于约束右，使它等于约束右边与左边之差边与左边之差: inxxba xaxa xn iiiiinn()1122 显然显然 也具有非负约束，即也具有非负约束，即 ，这时，这时新的约束条件成为新的约束条件成为:inx0inxa xaxa xxbiiinnn ii1122当约束条件为当约束条件为:a xaxa xbiiinni1122时，类似地令时，类似地令:xa xaxa xbn iiiinni()1122则同样有则同

22、样有 ，新的约束条件成为，新的约束条件成为:0inxa xaxa xxbiiinnn ii1122 为了使约束由不等式成为等式而引进的变量为了使约束由不等式成为等式而引进的变量 称称为为“松弛变量松弛变量”。如果原问题中有若干个非等式约束，。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。的松弛变量。inx例：将以下线性规划问题转化为标准形式例：将以下线性规划问题转化为标准形式max z= 3x1 -2x2 +x3 s.t. x1 +2x2 -x3 5 (1) 4x1 +3x3 8 (2) x1 +x2 +

23、x3 =6 (3) x1, x2, x3 0 将目标函数转换成极小化，并分别对约束将目标函数转换成极小化，并分别对约束（1）、（）、（2）引进松弛变量）引进松弛变量x4，x5，得到以下，得到以下标准形式的线性规划问题：标准形式的线性规划问题：min z= -3x1 +2x2 -x3 s.t. x1 +2x2 -x3 +x4 =5 4x1 +3x3 -x5 =8 x1 +x2 +x3 =6 x1, x2, x3, x4, x5 0 3.3 变量无符号限制的问题变量无符号限制的问题 在标准形式中，每一个变量都有非负约束。当一在标准形式中，每一个变量都有非负约束。当一个变量个变量 没有非负约束时，可

24、以令没有非负约束时，可以令 ：jxjjjxxx其中其中 0, 0 jjxx 即用两个非负变量之差来表示一个无符号限即用两个非负变量之差来表示一个无符号限制的变量，当制的变量，当 的符号取决于的符号取决于 和和 的大小。的大小。 jxjxjx 例例: 将以下线性规划问题转化为标准形式将以下线性规划问题转化为标准形式 max z= 2x1 -3x2 +x3 s.t. x1 -x2 +2x3 3 2x1 +3x2 -x3 5 x1 +x2 +x3 =4 x1,x30,x2无符号限制无符号限制 令令 ，引进松弛变量，引进松弛变量x4，x5，并令，并令:zz222xxx 得到以下等价的标准形式得到以下等

25、价的标准形式 :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 max z= x1 +3x2 s.t. x1 +x2 6 -x1 +2x2 8 x1, x2 0 其中满足约束其中满足约束(

26、1)的点的点 位于坐标平面上直线位于坐标平面上直线x1+x2=6靠近原点的一侧。同样，满足约束靠近原点的一侧。同样，满足约束(2)的点的点位于坐标平面上直线位于坐标平面上直线x1+2x2=8的靠近原点的一侧。的靠近原点的一侧。而变量而变量x1，x2的非负约束表明满足约束条件的点同的非负约束表明满足约束条件的点同时应位于第一象限内。时应位于第一象限内。21xxX 称满足线性规划问题所有约束条称满足线性规划问题所有约束条件（包括变量非负约束）的向量。件（包括变量非负约束）的向量。 TnxxxX),(21 为线性规划的可行解（为线性规划的可行解（Feasible Solution），称可行解的集合为

27、可），称可行解的集合为可行域（行域（Feasible Region）。）。 123456xz=0z=3z=6z=9z=12z=15.3013456约束条件（1）约束条件（2）C-1-8-2-3-4-5-6-7x21 例例4.1的线性规划问题的可行域如图中阴影部的线性规划问题的可行域如图中阴影部分所示。分所示。 126xx1226xx 为了在图上表示目标函数，令为了在图上表示目标函数，令z=z0为某一确定的目为某一确定的目标函数值，取一组不同的标函数值，取一组不同的z0值，在图上得到一组相应值，在图上得到一组相应的平行线，称为目标函数等值线。在同一条等值线上的平行线，称为目标函数等值线。在同一条

28、等值线上的点，相应的可行解的目标函数值相等。在图中，给的点，相应的可行解的目标函数值相等。在图中，给出了出了z=0，z=3，z=6，z=15.3等一组目标函数等值等一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线沿目标函数增大而平行移动的方向（即目标函数梯线沿目标函数增大而平行移动的方向（即目标函数梯度方向）就是目标函数的系数向量度方向）就是目标函数的系数向量 ；对于极小化问题，目标函数则沿对于极小化问题，目标函数则沿-C方向平行移动。方向平行移动。 TncccC),(21 目标函数等值线在平行移动过程中与可行域的最目标函数等值线在

29、平行移动过程中与可行域的最后一个交点是后一个交点是B点，这就是线性规划问题的最优解，点，这就是线性规划问题的最优解，这个最优解可以由两直线这个最优解可以由两直线 ：621 xx8221xx的交点求得的交点求得 314,3421xx最优解的目标函数值为最优解的目标函数值为 346314334321xxz定义定义4.1 在在n n维空间中，满足条件维空间中，满足条件 ininiibxaxaxa2211的点集的点集 TnxxxX),(21超平面。向量超平面。向量 Tiniiaaar),(21称为该超平面的法向量称为该超平面的法向量称为一个称为一个定义定义4.2 满足条件满足条件 ininiibxaxaxa)(2211或的点集的点集 TnxxxX),(21称为称为n维空间中的一个半空间。维空间中的一个半空间。 定义定义4.3 有