线性规划的数学模型.pptx

《线性规划的数学模型.pptx》由会员分享，可在线阅读，更多相关《线性规划的数学模型.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、23 二月 2023线性规划（Linear Programming缩写为LP）是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常解决下列两类问题（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.第1页/共21页23 二月 2023 产品产品设备设备 甲甲 乙乙 丙丙设备能力设备能力（小时）（小时）A A 3 1 2 3 1 22020B B 2 2 4 2

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小小时时；每

3、每生生产产一一件件甲甲、乙乙、丙丙三三种种产产品品，企企业业可可获获得得利利润润分分别别为为4 4、3 3、5 5元元。企企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？第2页/共21页23 二月 2023【解解】设设x x1 1、x x2 2、x x3 3 分别为甲、乙、丙三种产品的产分别为甲、乙、丙三种产品的产量数学模型为：量数学模型为：第3页/共21页23 二月 2023线性规划的数学模型由决策变量 Decision variables 目标函数Objective function及约束条件Constraint

4、s构成。称为三个要素。n n其特征是：其特征是：n n1 1解决问题的目标函数是多个决策变量的解决问题的目标函数是多个决策变量的 线性函数，通常是求最大值或线性函数，通常是求最大值或 最小值；最小值；n n2 2解决问题的约束条件是一组多个决策变量解决问题的约束条件是一组多个决策变量 的线性不等式或等式。的线性不等式或等式。怎样辨别一个模型是线性规划模型？第4页/共21页23 二月 2023 200万万mm3 3500500万万mm3 3工厂2：【例1.2】河流1：每天流量500万m3；河流2：每天流量200万m3,水质要求：污水含量0.2%2 2万万mm3 31.41.4万万mm3 3污水从

5、工厂1流向工厂2有20%可以净化处理污水成本：工厂1 1000元/万m3；工厂2 800元/万m3 问两个工厂每天各处理多少污水总成本最少？工厂1：【解】设x1、x2分别为工厂1、2每天处理的污水量（万m3），则第5页/共21页23 二月 2023数学模型为：第6页/共21页23 二月 2023【例1.3】下料问题，某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9，2.1，1.5（m），这些轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少圆钢来生产这些轴？【解解】第一步：设一根圆钢切割成甲、乙、丙三种轴的第一步：设一根圆钢切割成甲、乙、丙三种

6、轴的根数分别为根数分别为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第二步：建立线性规划数学模型。

7、设第二步：建立线性规划数学模型。设x xj j(j j=1,2,8)=1,2,8)为第为第j j种下料方案所用圆钢的根数。则数学模型为种下料方案所用圆钢的根数。则数学模型为 第7页/共21页23 二月 2023 方案方案规格规格1 12 23 34 45 56 67 78 8需求量需求量y y1(2.9m)2 21 11 11 10 00 00 00 0100100y y2(2.1m)0 02 21 10 03 32 21 10 0100100y y3(1.5m)1 10 01 13 30 02 23 34 41001000.10.10.30.30.90.90 01.11.10.20.20.8

8、0.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,8第8页/共21页23 二月 2023最优下料方案为：第一种方案用料10根，第二种方案50根，第四种方案30根，总余料为 16m。用1.5的单纯形法求得最优解为x1=10,x2=50,x4=30，其余x为零，即第一种方案用料10根，第二种方案用50根，第四种方案用30根，共计用料90根。如果要求余料最少，则目标函数及约束条件

9、为：如果要求余料最少，则目标函数及约束条件为：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,8第9页/共21页23 二月 2023注意：1.余料不能超过最短毛坯的长度；2.最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的；不能遗漏了方案。3.在实际中，如果毛坯规格较多，毛坯的长度又很短的方案可能很多，甚至有几千个方案，这时用人工计算几乎是不可能的，即使计算机也有可能

10、溢出。当碰到这种情况时，可以给余料确定一个临界值，当某方案的余料大于时马上舍去这种方案，从而减少占用计算机内存，也简化了后面的数学模型。第10页/共21页23 二月 2023【例1.4】配料问题。某一合金公司同一科研单位签订一项包含有四种金属的合金订购单，要求的成分规格是：金属A不少于23%，金属B不多于15%，金属C不多于4%，金属D要界于35%65%之间，不允许有其他成分。合金公司拟从六种不同级别的矿石中进行冶炼，每种矿物的成分含量和价格如表1-3所示。矿石杂质在治炼过程中废弃，现要求也每吨合金成本最低的矿物数量。假设矿石在冶炼过程中，金属含量没有发生变化。第11页/共21页23 二月 2

11、023金属金属矿石矿石 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表13第12页/共21页23 二月 2023【解】设xj（j=1,2，6）是第j 种矿石数量，目标函数是 总成本最少，得到下列线性规划模型minZ=23x1+20 x2+18x3+10 x4+27x5

12、+12x6第13页/共21页23 二月 2023解：设解：设x x1 1为第一年的投资为第一年的投资;x x2 2为 第一年的保留资金第一年的保留资金x x1 1+x x2 2 =100=100【例1.5】投资问题。某投资公司在第一年有100万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍金额。”投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。第二年：第二年：x x3 3为第二年新的投资；为第二年新的投资；x x4 4：第二年的保：第二年的保留资金；留资金；第14页/共21页23 二月 2

13、023n n第三年：第三年：x x5 5为新的投资；为新的投资；x x6 6：第三年的保留资金；：第三年的保留资金；n n第四年：新的投资第四年：新的投资 x x7 7 ；第四年的保留资金第四年的保留资金x x8 8 ；第五年第五年：x x9 9为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。第七年才能回收。约束条件保证每年满足如下的关系：追加投资约束条件保证每年满足如下的关系：追加投资金额金额+新投资金额新投资金额+保留资金保留资金=可利用的资金总额可利用的资金总额第15页/共21页23 二月 2023n

14、 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 第16页/共21页23 二月 2023即：第一年投资即：第一年投资22.6422.64元元;第二年新投资第二年新投资58.5458.54元元;第三年新投资第三年新投资26.0226.02元

15、元;第四年新投资第四年新投资104.06104.06元元;第六年末有资金第六年末有资金208.12208.12万元。万元。一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示,bi称为资源限量。第17页/共21页23 二月 2023则线性规划数学模型的一般表达式可写成：则线性规划数学模型的一般表达式可写成：第18页/共21页23 二月 2023在实际中一般在实际中一般x xj j0,0,但有时但有时x xj j00或或x xj j无符号限制。无符号限制。为了书写方便，上式也可写成第19页/共21页23 二月 20231.什么是线性规划，掌握线性规划在管理中的几个应用例子2.线性规划数学模型的组成及其特征3.线性规划数学模型的一般表达式。作业：教材P46 T1.8、1.9、1.10案例：案例1、2、3第20页/共21页23 二月 2023感谢您的观看！第21页/共21页