运筹学1 线性规划.ppt

《运筹学1 线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、运筹学OperationsResearchChapter1线性规划LinearProgramming1.LP的数学模型MathematicalModelofLP2.图解法GraphicalMethod3.标准型NormalizedFormofLP4.基本概念BasicConcepts5.单纯形法SimplexMethod6.人工变量法ArtificialVariableMethod7.计算公式CalculateFormula7/25/2021线性规划（LinearProgramming缩写为LP）

2、是运筹学的重要分支之一，在实际中应用得较广泛，其方法也较成熟，借助计算机，使得计算更方便，应用领域更广泛和深入。线性规划通常解决下列两类问题（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标；（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.7/25/2021产品设备甲乙丙设备能力（小时）A31220B22415C40116D03512利润（元/件）435【例1.1】某企业计划生产甲、

3、乙、丙三种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如表1-1所示，已知各设备在计划期内的能力分别为20、15、16、12小时；每生产一件甲、乙、丙三种产品，企业可获得利润分别为4、3、5元。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？7/25/2021【解】设x1、x2、x3分别为甲、乙、丙三种产品的产量数学模型为：7/25/2021线性规划的数学模型由决策变量Decisionvariables目标函数Ob

4、jectivefunction及约束条件Constraints构成。称为三个要素。其特征是：1．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；2．解决问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？7/25/2021200万m3500万m3工厂2：【例1.2】河流1：每天流量500万m3；河流2：每天流量200万m3,水质要求：污水含量≤0.2%2万m31.4万m3污水从工厂1流向工厂2有20%可以净化处理污水成本：工厂11000元/万m

5、3；工厂2800元/万m3问两个工厂每天各处理多少污水总成本最少？工厂1：【解】设x1、x2分别为工厂1、2每天处理的污水量（万m3），则7/25/2021数学模型为：7/25/2021【例1.3】下料问题，某一机床需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是2.9，2.1,1.5（m），这些轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少圆钢来生产这些轴？【解】第一步：设一根圆钢切割成甲、乙、丙三种轴的根数分别为y1,y2,y3,则切割方式可用不等式2.

6、9y1+2.1y2+1.5y3≤7.4表示，求这个不等式关于y1，y2，y3的非负整数解。例如y1=2,y2=0则y3只能为1，余料为0.1。象这样的非负整数解共有8组，也就是有8种下料方式，如表1-2所示。第二步：建立线性规划数学模型。设xj(j=1,2…,8)为第j种下料方案所用圆钢的根数。则数学模型为7/25/2021方案规格12345678需求量y1(2.9m)21110000100y2(2.1m)02103210100y3(1.5m)101302341000.10.30.901.10.2

7、0.81.42.9y1+2.1y2+1.5y3≤7.4表1－2minz=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x41002x2+x3+3x5+2x6+x7100x1+x3+3x4+2x6+3x7+4x8100xj0,j=1,2,…,87/25/2021最优下料方案为：第一种方案用料10根，第二种方案50根，第四种方案30根，总余料为16m。用§1.5的单纯形法求得最优解为x1=10,x2=50,x4=30，其余x为零，即第一种方案用料10根，第二种方案用50根，

8、第四种方案用30根，共计用料90根。如果要求余料最少，则目标函数及约束条件为：minz=0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x82x1+x2+x3+x4=1002x2+x3+3x5+2x6+x7=100x1+x3+3x4+2x6+3x7+4x8=100xj0,j=1,2,…,87/25/2021注意：1.余料不能超过最短毛坯的长度；2.最好将毛坯长度按降的次序排列，即先切割长度最长的毛坯，再切割次长的，最后切割最短的；不能遗漏了方案。3.