线性规划模型最新课件

《线性规划模型最新课件》由会员分享，可在线阅读，更多相关《线性规划模型最新课件（31页珍藏版）》请在装配图网上搜索。

1、线性规划模型最新课件线性规划模型最新课件1 线性规划问题线性规划问题 例例1. 运输问题运输问题 要把某种货物从要把某种货物从m个个 工厂工厂 A1,A2, ,Am 运到运到n个商店个商店 B1,B2, ,Bn去，其中各工厂的库存量为去，其中各工厂的库存量为a1,a2, , am，各商，各商店的需求量为店的需求量为b1,b2, ,bn ，这里，这里 。已知从工厂。已知从工厂Ai到商店到商店Bj的运费（每一单位货物）的运费（每一单位货物）Cij。现在要确定一个。现在要确定一个运输方案，即确定从运输方案，即确定从Ai到到Bj的运量的运量xij(i=1,2, ,m，j=1,2, ,n), 使在满足供

2、求的条件下总的运费最小。使在满足供求的条件下总的运费最小。 njjmiiba11数数学学模模型型 minjijijxcs11 minnjbxtsjmiij, 2 , 1,1miaxinjij, 2 , 1,1), 2 , 1;, 2 , 1( , 0njmixij线性规划模型最新课件例例2营养问题营养问题 某饲养场所用的混合饲料由某饲养场所用的混合饲料由n种配料组成，要求这种种配料组成，要求这种混合饲料必须含混合饲料必须含m种不同营养成分，并且每一份混合饲料种不同营养成分，并且每一份混合饲料中第中第i种营养成分的含量不低于种营养成分的含量不低于bi，已知每单位第，已知每单位第j种配料种配料中所

3、含第中所含第i种营养成分的量为种营养成分的量为aij，每单位第，每单位第j种配料的价格种配料的价格为为cj。现在的问题是在保证营养的条件下，如何配方使混。现在的问题是在保证营养的条件下，如何配方使混合饲料的费用最小？合饲料的费用最小？数数学学模模型型 以以xj表示一份混合饲料中第表示一份混合饲料中第j种配料的含量种配料的含量 ,则则njjjxcz1 minmibxatsijnjij, 2 , 1,1), 2 , 1( , 0njxj线性规划模型最新课件2 线性规划的标准形式线性规划的标准形式niiixcz1 min), 2 , 1( 1mibxatsijnjij0,21nxxx目标函数目标函数

4、约束条件约束条件一般形式一般形式矩阵形式矩阵形式 xCzT minbAxts0 x0,),(,),(,),()(212121bbbbbcccCxxxxaATmTnTnnmij且，其中，线性规划模型最新课件标准形式标准形式xCzLPT min )(bAxts0 x0,),(,),(,),(,)()(212121bbbbbcccCxxxxnmARaATmTnTnnmij且且，其中，化一般形式为标准形式化一般形式为标准形式目标函数的转化目标函数的转化)min( maxzzinjnjijijnjijbxxabxa111)( 或0,jjjjjjvuvuxx 自由变化约束条件的转化约束条件的转化变量的非负

5、约束的转化变量的非负约束的转化线性规划模型最新课件xy03 线性规划的一般理论线性规划的一般理论 线性规划的图解法线性规划的图解法0, 0 300103 20054 36049127 max2121212121xxxxxxxxtsxxs可行域sxx211273604921 xx20054 21 xx300103 21xxABCD, 2 , 1 , 0 , 12,s最优解最优解B(x1,x2)20054 21 xx300103 21xx24,20 21xx线性规划模型最新课件可行解可行解 一个向量一个向量x=(x1,x2, ,xn)如果满足所有的约束条如果满足所有的约束条件，则称之为线性规划的一

6、个可行解。件，则称之为线性规划的一个可行解。全部可行解所构成的集合称为可行解集全部可行解所构成的集合称为可行解集使目标函数达到极小的可行解称为最优解。使目标函数达到极小的可行解称为最优解。可行域可行域 最优解最优解 线性线性规划规划可能可能发生发生的三的三种情种情况况 （1）约束条件彼此不相容，可行解集是空的，）约束条件彼此不相容，可行解集是空的，因而（因而（LP）问题无解；）问题无解； （2）可行域是无界的，而且随着）可行域是无界的，而且随着x趋向无穷，目趋向无穷，目标函数取任意小的值，此时不存在有限的最优解；标函数取任意小的值，此时不存在有限的最优解； （3）至少存在一个最优解。以后仅研究

7、情况（）至少存在一个最优解。以后仅研究情况（3） 上例中可行上例中可行域与最优解域与最优解的特点：的特点：可行域是凸多边形（凸多胞形）可行域是凸多边形（凸多胞形）最优解是凸多边形的一个顶点最优解是凸多边形的一个顶点线性规划模型最新课件1凸集凸集 1 , 0t定义定义1 设设S是是Rn中的一个向量集，若对任意中的一个向量集，若对任意 及及任意任意 ，有，有 则称则称S是一个凸集。是一个凸集。Syx,Syttxz)1 (定义定义2 若若S是一个凸集，是一个凸集， ，但对任意，但对任意 ，均有，均有 ，则称，则称z是凸集是凸集S的一个顶点。的一个顶点。 Sz,zxSyx)(21yxzzy 容易证明，

8、线性规划问题（容易证明，线性规划问题（LP）的可行域是一个凸集）的可行域是一个凸集 2基本可行解基本可行解 个列线性无关的前不妨设中设在mAnmARLP,)()(mjaaaaTmjjjj, 2 , 1),(21，记NBTnmxxxxxxNBAaaaB),(),(),(2121线性规划模型最新课件2基本可行解基本可行解 , 2 , 1),(21mjaaaaTmjjjj，记个列线性无关的前不妨设中设在mAnmARLP,)()(NBTnmxxxxxxNBAaaaB),(),(),(2121bNxBxNBNBNxBbBx11 把把 看作一组自由变量看作一组自由变量,任意一组值任意一组值 ，则可得到对应

9、，则可得到对应的的 的一组值，于是的一组值，于是 便是约束方程便是约束方程 的的一个解一个解 。令。令 =0，则，则 ，我们把约束方程这，我们把约束方程这种特殊形式的解种特殊形式的解 称为基本解。称为基本解。 NxbBxB1NBxxxbAx Bx01bBxNxNx线性规划模型最新课件 定义定义3 设设B是矩阵是矩阵A中的一个中的一个m阶满秩方阵，则称阶满秩方阵，则称B为一个为一个基；基；B中的中的m个线性无关的列向量称为基向量；个线性无关的列向量称为基向量；x中与之对中与之对应的应的m个分量称为基本变量，其余变量称为非基本变量；个分量称为基本变量，其余变量称为非基本变量；令所有的非基本变量取值

10、为零，得到的解称为对应于令所有的非基本变量取值为零，得到的解称为对应于B的的基本解。基本解。 01bBxxxNB定义定义4 如果一个基本解满足非负条件如果一个基本解满足非负条件 ，即它也是，即它也是可行的，则称为基本可行解，对应的基可行的，则称为基本可行解，对应的基B称为可行基。称为可行基。 0 x的一个基本可行解。为条件是的一个顶点的充分必要是可行域，则，且设定理0, 0,| ),(,),(,),(,)()( 1212121xbAxxxbAxxRRxbbbbcccCxxxxnmARaAnTmTnTnnmij线性规划模型最新课件3基本性质（几个结论）基本性质（几个结论） 定义定义5 如果一个线

11、性规划问题（如果一个线性规划问题（LP）的基本变量数是）的基本变量数是m，而两个基本可行解有而两个基本可行解有m1个相同的基本变量，则称它们个相同的基本变量，则称它们所代表的顶点是相邻的。所代表的顶点是相邻的。 （1）标准线性规划问题的可行域（若存在可行域）是一）标准线性规划问题的可行域（若存在可行域）是一个闭凸集（凸多面体），这一点容易从闭凸集和约束的线个闭凸集（凸多面体），这一点容易从闭凸集和约束的线性性得到。性性得到。（2）如果可行解集是非空和有界的，那么目标函数的极）如果可行解集是非空和有界的，那么目标函数的极值一定在可行解集的一个顶点处取得。值一定在可行解集的一个顶点处取得。（3）如

12、果可行域是无界的，那么目标函数可能无极值，）如果可行域是无界的，那么目标函数可能无极值，也可能有极值。如果有极值，这一极值一定在可行域的一也可能有极值。如果有极值，这一极值一定在可行域的一个顶点处取得。个顶点处取得。 （4）基本可行解对应可行域的顶点。）基本可行解对应可行域的顶点。 穷举穷举法：法： 求出全部顶点处函数值（至多求出全部顶点处函数值（至多 ），再进行比较），再进行比较mnC线性规划模型最新课件可行域可行域 4 单纯形法单纯形法 单纯形法的基本思想：单纯形法的基本思想： 从可行域的一个顶点出发，转从可行域的一个顶点出发，转移到与它相邻的另一个顶点，移到与它相邻的另一个顶点，使目标函

13、数值下降，不断重复使目标函数值下降，不断重复这一步骤，最终可得到最优解。这一步骤，最终可得到最优解。 需要解决以下几个问题：需要解决以下几个问题： （1）转移规则）转移规则 （2）如何判断一个顶点是否是最优解）如何判断一个顶点是否是最优解判别准则。判别准则。 （3） 如何寻找初始顶点。如何寻找初始顶点。 （4） 计算最优解和最优值。计算最优解和最优值。 线性规划模型最新课件1.转移规则转移规则 NBxxBbBx非基变量为基变量为，对应的基为设已有基可行解,01在基本变量中找出一个变量（离基变量），在基本变量中找出一个变量（离基变量）， 使之变为非基本变量。使之变为非基本变量。从非基本变量中选取

14、一个变量，代替离基变量，使之成为基本变量，从非基本变量中选取一个变量，代替离基变量，使之成为基本变量，我们称为进基变量。我们称为进基变量。 bNxBxmABbAxNB ,则列）的前（不妨设为设所找到的基为对约束方程bBNxBxNB11mnmmmmnmmnmmyyyyyyyyyNBN2,1,22, 21, 212, 11, 110101myybBb), 2 , 1( , 00mibiTmTTTByyyxx)0 , 0 ,()0 ,(01010线性规划模型最新课件NBTNTBTxxCCxCz),(在基本可行解在基本可行解 处的函数值为处的函数值为xbBCbCzTBTB1在一般可行解处的函数值为在一

15、般可行解处的函数值为NTBTNTBNNTNTBxNCCbCxxNbCCz)(),(NTBTNTBxNBCCbBC)(11当且仅当当且仅当 时目标函数减少，即时目标函数减少，即0)(1NTBTNxNBCC 中至少有一个分量小于零中至少有一个分量小于零 NBCCTBTN1 nmmjyccrmkkjkjj1记：rj称为检验数称为检验数NnmmTBxrrrbBCz),(211线性规划模型最新课件(1)进基变量的选择进基变量的选择 kjjrrr 0|min设则取则取xk为进基变量（或为进基变量（或ak为进基向量）为进基向量）(2)离基变量的选择离基变量的选择 设设xr为离基变量为离基变量0,11,0,1

16、1,202, 211, 22101, 111, 11 mnmnkkmmmmmrnrnkkrmmrrnnkkmmnnkkmmyxyxyxyxyxyxyxyxyxyxyxyxyxyxyxyx基变量基变量非基变量非基变量基可行解基可行解离基变量离基变量进基变量进基变量主元素主元素 0,kry线性规划模型最新课件011,011,20211, 22r210111, 1110 y 0 0 mnmnmmmmrmrrnrnkmmrrrrnnmmrnnmmrryxyxyxxyxyxxyxyyxyxyxyxyxyxyxyx ,rkrjrjikrkrjijijyyyriyyyyy ,00000rkrrikrkrii

17、yyyriyyyyy转换公式转换公式 离基变量的选择离基变量的选择 0min00ikikirkryyyyy 00,0krryyxr为离基变量为离基变量 只要取,0iy线性规划模型最新课件2.最优解的判定最优解的判定 对于某个基本可行解，若所有的检验数对于某个基本可行解，若所有的检验数 则此基本可行解为最优解。则此基本可行解为最优解。 , 1, 0mjrj, 2nmTmTTTByyyxx)0 , 0 ,()0 ,(01010bBCbCzTBTB1NnmmTBxrrrbBCz),(2110jrzz3.初始基本可行解的寻找方法初始基本可行解的寻找方法寻找初始基本可行解的方法有：（寻找初始基本可行解的

18、方法有：（a）大）大M法，（法，（b）二阶）二阶段法。这里仅介绍二阶段法。段法。这里仅介绍二阶段法。 构造辅构造辅助线性助线性规划：规划： imiyzLP11 min )(byAxts0, 0yx线性规划模型最新课件若问题（若问题（LP1）的最优基本可行解为）的最优基本可行解为 ，则，则 为原为原问题的一个基本可行解；问题的一个基本可行解； 0)0(x)0(x若问题（若问题（LP1）的最优基本可行解为）的最优基本可行解为 且且 ，则原问题无可行解。则原问题无可行解。 ,)0()0(yx0)0(y4.单纯形表单纯形表检验数检验数 b基本变量基本变量Bxnmmxxxxx 121nmyy, 11,

19、1 1nmyy, 21, 2 1 nmmmyy,1, 1 1x2xmx10b20b0mbnr r 0 0 01mz线性规划模型最新课件5.单纯形法的计算步骤单纯形法的计算步骤（1）把一般线性规划问题转化为标准型；）把一般线性规划问题转化为标准型； （2）建立初始单纯形表；）建立初始单纯形表； （3）若所有检验数）若所有检验数 ，就得到一个最优解；，就得到一个最优解； 0jrkx（4）若对某个）若对某个j有有 ，取，取 ，对应，对应的的 为进基变量。为进基变量。0jrkjjrr 0r min）无最优解。（则可行域无界，且此时为离基变量。若所有则主元素为，设计算对所有的LPyxyyyyyyyyyi

20、krrkrkrikikiikiik, 0 , 0min, 0) 5(000（6）以）以 为主元素，进行一次为主元素，进行一次Gauss消元，得到一个新消元，得到一个新的基本可行解。返回（的基本可行解。返回（3）。）。 rky线性规划模型最新课件6.单纯形法的矩阵形式单纯形法的矩阵形式0010(bBxxB）NCNBCCrTTNTBTNTN11BCTBT检验向量检验向量 0,BNBrrrr其中单纯形法的矩阵形式单纯形法的矩阵形式bBCNBCCbBNBIBTTBTBTNm11110 )(),(11NBIABm), 0(11NBCCABCCTBTNTBTbBCABCCbBABBTTBTBT1111)(

21、ACABCCrTTTBTT1线性规划模型最新课件7.应用举例应用举例 例例3一家具公司生产桌子和椅子，用于生产的全部劳动一家具公司生产桌子和椅子，用于生产的全部劳动力共计力共计450个工时。原料是个工时。原料是400个单位的木材。每张桌子要个单位的木材。每张桌子要使用使用15个工时的劳动力，个工时的劳动力，20个单位的木材，售价为个单位的木材，售价为80元。元。每张椅子要使用每张椅子要使用10个工时，个工时，5个单位木材，售价个单位木材，售价45元。问元。问为达到最大收益应怎样安排生产？为达到最大收益应怎样安排生产？ 解解 设设 分别表示应生产的桌子和椅子数，则分别表示应生产的桌子和椅子数，则

22、 21,xx0, 045010154005204580max21212121xxxxxxtsxxw0, 0, 0, 04501015400520004580min43214213214321xxxxxxxxxxtsxxxxz线性规划模型最新课件检验数 bBx3x4x04004500 1 5 201 0 10 150 0 45 80 4321 xxxx80)(21411311ycyccr45)(224123212ycyccr043 rr80,min121 rrr2015450,20400minX1为进基变量，为进基变量，x3为离基变量为离基变量160201500 20/1 1/4 11 3/4

23、4/25 00 4 25 01x检验数 bBx4x4321 xxxxX2为进基变量为进基变量02r24425150,4120minx4为离基变量为离基变量线性规划模型最新课件2200142425/1 2/25 0 14/25 25/3 1 04 1 0 02x检验数 bBx1x4321 xxxx160201500 20/1 1/4 11 3/4 4/25 00 4 25 01x检验数 bBx4x4321 xxxx最优解最优解X1=14 , x2=24最优解值最优解值W=2200线性规划模型最新课件用两阶段法求解线性规划用两阶段法求解线性规划 0,42634334min4321421321212

24、1xxxxxxxxxxxxtsxxz输入：输入：ne=3c=4,1,0,0A = 3 , 1 , 0 , 0 ; 4 , 3 , -1,0;1,2,0,1b=3,6,4v1=0,0,0,0 x=lp(c,A,b,v1,ne)z=c*x结果：结果：x = 0.4000 1.8000 1.0000 0z = 3.4000线性规划模型最新课件化为标准形化为标准形 0,42634334max43214213212121xxxxxxxxxxxxtsxxz引入人工变量引入人工变量 0,42634334max654321421632152121xxxxxxxxxxxxxxxxtsxxz线性规划模型最新课件考

25、虑辅助问题考虑辅助问题 0,4263433min654321421632152165xxxxxxxxxxxxxxxxtsxxwcZ410000CW000011CBxBbx1x2x3x4x5x6110 x5x6x4364341132010001100010cjzj410000cjwj741000线性规划模型最新课件cZ410000CW000011CBxBbx1x2x3x4x5x6010 x1x6x41231001/35/35/30100011/34/31/3010cjzj01/3004/30cjwj05/3107/30线性规划模型最新课件cZ410000CW000011CBxBbx1x2x3x4

26、x5x6000 x1x2x43/56/511000101/53/510013/54/511/53/51cjzj001/508/51/5cjwj000011线性规划模型最新课件cZ4100CBxBbx1x2x3x4410 x1x2x43/56/511000101/53/51001cjzj001/50cZ4100CBxBbx1x2x3x4410 x1x2x32/59/511000100011/53/51cjzj0001/5最优解：最优解：x1=2/5, x2=9/5, x3=1, x4=0最优化：最优化：Z*=3.4线性规划模型最新课件作业（食谱问题）作业（食谱问题） 某公司饲养实验用的动物一供出

27、售。已知这些动物的某公司饲养实验用的动物一供出售。已知这些动物的生长对饲料中三种营养成分：蛋白质、矿物质、维生素特生长对饲料中三种营养成分：蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质别敏感，每个动物每天至少需要蛋白质70g，矿物质，矿物质3g,维维生素生素10g,该公司能买到该公司能买到5种不同的饲料，每种饲料种不同的饲料，每种饲料1 kg所含所含的营养成分及成本如表：的营养成分及成本如表：饲料饲料蛋白质（蛋白质（g）矿物质（矿物质（g）维生素（维生素（g）A10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08饲料饲料蛋白质（蛋白质（g）矿物质（矿物质（g）维生素（维生素（g）A10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08线性规划模型最新课件饲料饲料A1A2A3A4A5成本（元）成本（元）0.20.70.40.30.5 五种饲料单位重量（五种饲料单位重量（1kg）成本）成本