ch1-1线性规划的数学模型.ppt

运筹学运筹学Operations ResearchChapter 1 线性规划线性规划Linear Programming1.LP的数学模型 Mathematical Model of LP2.图解法 Graphical Method3.标准型 Normalized Form of LP4.基本概念 Basic Concepts5.单纯形法 Simplex Method6.人工变量法 Artificial Variable Method7.计算公式 Calculate Formula 5/23/2024线性规划线性规划（Linear Programming缩写为LP）是运筹是运筹学的重要分支之一，在实际中应用得较广泛，其方学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。领域更广泛和深入。线性规划通常解决下列两类问题线性规划通常解决下列两类问题（1）当任务或目标确定后，如何统筹兼顾，合理）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源安排，用最少的资源（如资金、设备、原标材料、（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；人工、时间等）去完成确定的任务或目标；（2）在一定的资源条件限制下，如何组织安排生）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多产获得最好的经济效益（如产品量最多、利润最、利润最大大.5/23/2024 产品产品设备设备 甲甲 乙乙 丙丙设备能力设备能力（小时）（小时）A A 3 1 2 3 1 22020B B 2 2 4 2 2 41515C C 4 0 1 4 0 11616D D 0 3 5 0 3 51212 利润（元利润（元利润（元利润（元/件）件）件）件）4 3 5 4 3 5【例例例例1.11.1】某某某某企企企企业业业业计计计计划划划划生生生生产产产产甲甲甲甲、乙乙乙乙、丙丙丙丙三三三三种种种种产产产产品品品品。这这这这些些些些产产产产品品品品分分分分别别别别要要要要在在在在A A、B B、C C、D D、四四四四种种种种不不不不同同同同的的的的设设设设备备备备上上上上加加加加工工工工。按按按按工工工工艺艺艺艺资资资资料料料料规规规规定定定定，单单单单件件件件产产产产品品品品在在在在不不不不同同同同设设设设备备备备上上上上加加加加工工工工所所所所需需需需要要要要的的的的台台台台时时时时如如如如表表表表1-11-1所所所所示示示示 ，已已已已知知知知各各各各设设设设备备备备在在在在计计计计划划划划期期期期内内内内的的的的能能能能力力力力分分分分别别别别为为为为2020、1515、1616、1212小小小小时时时时；每每每每生生生生产产产产一一一一件件件件甲甲甲甲、乙乙乙乙、丙丙丙丙三三三三种种种种产产产产品品品品，企企企企业业业业可可可可获获获获得得得得利利利利润润润润分分分分别别别别为为为为4 4、3 3、5 5元元元元。企企企企业业业业决决决决策策策策者者者者应应应应如如如如何何何何安安安安排排排排生生生生产产产产计计计计划划划划，使使使使企企企企业业业业在计划期内总的利润收入最大？在计划期内总的利润收入最大？在计划期内总的利润收入最大？在计划期内总的利润收入最大？5/23/2024【解】设【解】设【解】设【解】设x x1 1、x x2 2、x x3 3 分别为甲、乙、丙三种产品的产分别为甲、乙、丙三种产品的产分别为甲、乙、丙三种产品的产分别为甲、乙、丙三种产品的产量数学模型为：量数学模型为：量数学模型为：量数学模型为：5/23/2024线性规划的数学模型由线性规划的数学模型由决策变量决策变量 Decision variables 目标函数目标函数Objective function及约束条件及约束条件Constraints构成。构成。称为三个要素称为三个要素。n n其特征是：其特征是：其特征是：其特征是：n n1 1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；最小值；最小值；n n2 2解决问题的约束条件是一组多个决策变量解决问题的约束条件是一组多个决策变量解决问题的约束条件是一组多个决策变量解决问题的约束条件是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？怎样辨别一个模型是线性规划模型？5/23/2024 200万万mm3 3500500万万mm3 3工厂2：【例【例1.2】河流河流1：每天流量：每天流量500万万m3；河流；河流2：每天流量：每天流量200万万m3,水质要求：污水含量水质要求：污水含量0.2%2 2万万mm3 31.41.4万万mm3 3污水从工厂污水从工厂1流向工厂流向工厂2有有20%可以净化可以净化处理污水成本：工厂处理污水成本：工厂1 1000元元/万万m3；工厂工厂2 800元元/万万m3 问两个工厂每天各处理多少污水总成本最少？问两个工厂每天各处理多少污水总成本最少？工厂1：【解】设【解】设x1、x2分别为工厂分别为工厂1、2每天处理的污水量（万每天处理的污水量（万m3），则），则5/23/2024数学模型为：5/23/2024【例例1.3】下料问题，某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9，2.1，1.5（m），这些轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少圆钢来生产这些轴？【解】第一步：设一根圆钢切割成甲、乙、丙三种轴的解】第一步：设一根圆钢切割成甲、乙、丙三种轴的根数分别为根数分别为y y1 1,y y2 2,y y3 3,则切割方式可用不等式则切割方式可用不等式2.92.9y y1 1+2.1+2.1y y2 2+1.5+1.5y y3 37.47.4表示，求这个不等式关于表示，求这个不等式关于y y1 1，y y2 2，y y3 3的非负整数解。例如的非负整数解。例如y y1 1=2,=2,y y2 2=0=0则则y y3 3只能为只能为1 1，余料为，余料为0.10.1。象这样的非负整数解共有象这样的非负整数解共有8 8组，也就是有组，也就是有8 8种下料方式，种下料方式，如表如表1-21-2所示。所示。n n第二步：建立线性规划数学模型。设第二步：建立线性规划数学模型。设x xj j(j j=1,2,8)=1,2,8)为第为第j j种下料方案所用圆钢的根数。则种下料方案所用圆钢的根数。则数学模型为数学模型为 5/23/2024 方案方案规格规格1 12 23 34 45 56 67 78 8需求量需求量y y1 1(2.9m)(2.9m)2 21 11 11 10 00 00 00 0100100y y2 2(2.1m)(2.1m)0 02 21 10 03 32 21 10 0100100y y3 3(1.5m)(1.5m)1 10 01 13 30 02 23 34 41001000.10.10.30.30.90.90 01.11.10.20.20.80.81.41.42.9y1+2.1y2+1.5y37.4 表12min z=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4 1002x2+x3+3x5+2x6+x7 100 x1+x3+3x4+2x6+3x7+4x8 100 xj 0,j=1,2,85/23/2024最优下料方案为：第一种方案用料10根，第二种方案50根，第四种方案30根，总余料为 16m。用1.5的单纯形法求得最优解为x1=10,x2=50,x4=30，其余x为零，即第一种方案用料10根，第二种方案用50根，第四种方案用30根，共计用料90根。如果要求余料最少，则目标函数及约束条件为：如果要求余料最少，则目标函数及约束条件为：min z=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x82x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100 x1+x3+3x4+2x6+3x7+4x8=100 xj 0,j=1,2,85/23/2024注意注意：1.余料不能超过最短毛坯的长度；2.最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的；不能遗漏了方案。3.在实际中，如果毛坯规格较多，毛坯的长度又很短的方案可能很多，甚至有几千个方案，这时用人工计算几乎是不可能的，即使计算机也有可能溢出。当碰到这种情况时，可以给余料确定一个临界值，当某方案的余料大于时马上舍去这种方案，从而减少占用计算机内存，也简化了后面的数学模型。5/23/2024【例例1.4】配料问题。某一合金公司同一科研单位签订一项包含有四种金属的合金订购单，要求的成分规格是：金属A不少于23%，金属B不多于15%，金属C不多于4%，金属D要界于35%65%之间，不允许有其他成分。合金公司拟从六种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1-3所示。矿石杂质在治炼过程中废弃，现要求也每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，金属含量没有发生变化。5/23/2024金属金属矿石矿石 A%A%B%B%C%C%D%D%杂质杂质 费用费用（元（元/t/t）1 12525101010102525303023232 240400 00 03030303020203 3202010100 03030404018184 40 015155 52020606010105 5202020200 04040202027276 68 85 51515171755551212表135/23/2024【解解】设xj（j=1,2，6）是第j 种矿石数量，目标函数是 总成本最少，得到下列线性规划模型minZ=23x1+20 x2+18x3+10 x4+27x5+12x65/23/2024解：设解：设x x1 1为第一年的投资为第一年的投资;x x2 2为 第一年的保留资金第一年的保留资金x x1 1+x x2 2=100=100【例例1.5】投资问题。某投资公司在第一年有100万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍金额。”投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。第二年：第二年：x x3 3为第二年新的投资；为第二年新的投资；x x4 4：第二年的保留：第二年的保留资金；资金；5/23/2024n n第三年：第三年：x x5 5为新的投资；为新的投资；x x6 6：第三年的保留资金；第三年的保留资金；n n第四年：新的投资第四年：新的投资 x x7 7 ；第四年的保留资金第四年的保留资金x x8 8 ；第五年第五年：x x9 9为第五年的保留资金：第五年不再进行新的投资，为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。因为这笔投资要到第七年才能回收。约束条件保证每年满足如下的关系：追加投资约束条件保证每年满足如下的关系：追加投资金额金额+新投资金额新投资金额+保留资金保留资金=可利用的资金总额可利用的资金总额5/23/2024n n用单纯形法解得：用单纯形法解得：X X（22.6422.64，72.3672.36，58.5458.54，0 0，26.0226.02，0 0，104.06104.06，0 0，0 0）。Z Z208.12208.12。n n到第六年实有资金总额为到第六年实有资金总额为x x9 9+2+2x x7 7，整理后得到下列线性整理后得到下列线性规划模型规划模型 max Z=2max Z=2x x7+x x9 5/23/2024即：第一年投资即：第一年投资22.6422.64元元;第二年新投资第二年新投资58.5458.54元元;第三年新投资第三年新投资26.0226.02元元;第四年新投资第四年新投资104.06104.06元元;第六年末有资金第六年末有资金208.12208.12万元。万元。一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2,n，目标函数的变量系数用cj表示,cj称为价值系数价值系数。约束条件的变量系数用aij表示，aij称为工艺系数工艺系数。约束条件右端的常数用bi表示,bi称为资源限量资源限量。5/23/2024则线性规划数学模型的一般表达式可写成：则线性规划数学模型的一般表达式可写成：5/23/2024在实际中一般在实际中一般x xj j0,0,但有时但有时x xj j00或或x xj j无符号限制。无符号限制。为了书写方便，上式也可写成5/23/20241.什么是线性规划，掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。作业：教材P46 T1.8、1.9、1.10案例：案例1、2、35/23/2024