应用高等数学 教学课件 ppt 作者 胡桐春ppt 4.4 线性规划.ppt

《应用高等数学 教学课件 ppt 作者 胡桐春ppt 4.4 线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划§4.4§4.4.1线性规划问题的数学模型§4.4.2线性规划问题的图解法§4.4.3线性规划问题的计算机求解1线性规划是目前应用最为广泛的一种系统优化方法.它是运筹学的一个重要分支.自1947年丹捷格（G.B.Dantzig）提出了一般线性规划的求解方法——单纯形法之后，线性规划在理论上趋向成熟，在实际应用中日益广泛与深入.特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划更为广泛地应用于工业、农业、商业、交通运输业、军事、经济计划和管理决策等各个领域，成为现代科

2、学管理的重要工具之一.简单的线性规划问题大都用图解法或单纯形法求解，而复杂的线性规划问题可以用相应的数学软件包（LINDO或LINGO）求解.引言24.4.1线性规划问题的数学模型在实际问题中，我们会经常遇到在一定条件下使解决的问题达到最优.例如：在有限资源条件下，确定生产产品的品种、数量，使产值或利润最大；用最小的人力、物力耗费来完成某项既定的任务等等.这在数学上我们称之为规划问题.线性规划问题是规划问题中最基本、最重要的一类问题.3单位产品所需原料原料产品AB原料供应量（公斤）甲116乙128丙10

3、5单位利润（元）34求最大值[引例4.5]生产组织与计划问题某工厂计划生产A、B两种产品，要用甲、乙、丙三种不同的原料.每天原料供应的能力及每天生产一件产品A与B所需的原料与获得的利润如表4-6所示.问如何安排生产才能使一天的利润为最大？4[分析]设工厂每天生产A、B两种产品的产量分别为（公斤），可获得的利润为（元），因此我们的目标是最大.但是由于生产受到外界条件的限制：每天甲原料最大供应量为每天乙原料最大供应量为每天丙原料最大供应量为且5综上所述，本问题的数学模型为满足其中，记号“”表示函数的最大值，

4、函数称为目标函数，不等式组称为约束条件.6[引例4.6]合理下料问题某建筑工地，需要直径相同、长度不同的成套钢筋，每套由7根2m长与2根7m长的钢筋组成.今有15m长的钢筋150根，问如何下料，才能使废料最少？[分析]将一根15m长的钢筋切割成长分别是7m和2m的两种规格，有三种比较经济的方法，其结果如下表所示.切割方法7m长2m长废料长方案一140方案二201方案三071设方案一、方案二和方案三的下料的原料根数分别为，则要解决的问题是采用合理的下料方案，使废料的总长最少.7问题中所受的条件限制：钢筋的

5、总根数为根据配套的要求，即每套由7根2m长与2根7m长的钢筋组成：即按方案一、二、三下料的原料根数都必须是非负的：同样，我们将上述实际问题数学模型为满足8上述两个实例的数学模型有共同特征：(1)每个问题都是求一组变量的值，这组变量称为决策变量.它用来表示相应的活动方案，由于实际问题的要求，这些决策变量通常都是非负的.(2)每个问题都存在一定的限制条件，称为约束条件，约束条件是决策变量的线性不等式或等式.(3)每个问题都有一个目标函数，要求目标函数的最大值或最小值，目标函数是决策变量的线性函数.我们将具有

6、这些共同特征数学模型称为线性规划问题的数学模型.9一般的线性规划问题的数学模型可记为：目标函数约束条件()满足约束条件的一组变量的值称为该线性规划问题的可行解.所有可行解构成的集合称为可行域，使目标函数取得最大（或最小）值的可行解，称为最优解.104.4.2线性规划问题的图解法若线性规划问题只含有两个决策变量，则可考虑用几何作图法求解.下面通过例题说明图解法的一般步骤.例1对引例4.5给出的线性规划问题的数学模型试用图解法求解.11解如图直角坐标系中，所有满足约束条件的点必须落在阴影部分(它是可行域,这

7、里的每一个点的坐标值都是可行解).目标函数可以看成是以S为参数，为斜率的一族平行直线：位于同一条直线上的点，具有同样的目标函数值.12直线沿着法线的方向向右上角移动时，的值由小到大.当移动到B点时，S的值最大.即目标函数值在顶点B处取得最大值.(此时,B点坐标就是最优解)而B点就是直线和直线的交点，求得B点坐标为（4，2），即当时，目标函数的最大值.即当该工厂生产4件产品A,2件产品B时，一天能获得的最大利润为20元.结论：若线性规划问题存在最优解，则它一定在可行域的某个顶点处.若在两个顶点同时达到最优

8、值，则这两个顶点连线上的任意一点都是最优解.13例2讨论线性规划问题的解的存在性?解可作图看出,同时满足四个不等式组成的约束条件的点不存在,也就是说,该问题的可行域是空集.因此,无最优点,即没有最优解.14除了以上几种情况外,有时候可行域还可能出现无界区域.该类线性规划问题的最优解是否存在就与目标函数有紧密的联系.因此利用图解法求线性规划问题的最优解时，可以先根据约束条件求出可行域（一般情况下是凸多边形），然后把可行域的每个顶点代入目标函数