4.4-线性规划(部编)课件

线性规划§4.4§4.4.1

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

简单的线性规划问题大都用图解法或单纯形法求解，而复杂的线性规划问题可以用相应的数学软件包（LINDO或LINGO）求解.引言24.4.1线性规划问题的数学模型

在实际问题中，我们会经常遇到在一定条件下使解决的问题达到最优.例如：在有限资源条件下，确定生产产品的品种、数量，使产值或利润最大；用最小的人力、物力耗费来完成某项既定的任务等等.这在数学上我们称之为规划问题.线性规划问题是规划问题中最基本、最重要的一类问题.3单位产品所需原料原料产品AB原料供应量（公斤）甲116乙128丙105单位利润（元）34求最大值[引例4.5]

生产组织与计划问题某工厂计划生产A、B两种产品，要用甲、乙、丙三种不同的原料.每天原料供应的能力及每天生产一件产品A与B所需的原料与获得的利润如表4-6所示.问如何安排生产才能使一天的利润为最大？4[分析]

设工厂每天生产A、B两种产品的产量分别为（公斤），可获得的利润为（元），因此我们的目标是最大.但是由于生产受到外界条件的限制：每天甲原料最大供应量为每天乙原料最大供应量为每天丙原料最大供应量为且5综上所述，本问题的数学模型为满足其中，记号“”表示函数的最大值，函数称为目标函数，不等式组称为约束条件.6[引例4.6]合理下料问题某建筑工地，需要直径相同、长度不同的成套钢筋，每套由7根2m长与2根7m长的钢筋组成.今有15m长的钢筋150根，问如何下料，才能使废料最少？[分析]

将一根15m长的钢筋切割成长分别是7m和2m的两种规格，有三种比较经济的方法，其结果如下表所示.切割方法7m长2m长废料长方案一140方案二201方案三071设方案一、方案二和方案三的下料的原料根数分别为，则要解决的问题是采用合理的下料方案，使废料的总长最少.7问题中所受的条件限制：钢筋的总根数为根据配套的要求，即每套由7根2m长与2根7m长的钢筋组成：即按方案一、二、三下料的原料根数都必须是非负的：同样，我们将上述实际问题数学模型为满足8上述两个实例的数学模型有共同特征：

(1)每个问题都是求一组变量的值，这组变量称为决策变量.它用来表示相应的活动方案，由于实际问题的要求，这些决策变量通常都是非负的.(2)每个问题都存在一定的限制条件，称为约束条件，约束条件是决策变量的线性不等式或等式.(3)每个问题都有一个目标函数，要求目标函数的最大值或最小值，目标函数是决策变量的线性函数.

我们将具有这些共同特征数学模型称为线性规划问题的数学模型.9一般的线性规划问题的数学模型可记为：目标函数约束条件()满足约束条件的一组变量的值称为该线性规划问题的可行解.所有可行解构成的集合称为可行域，使目标函数取得最大（或最小）值的可行解，称为最优解.104.4.2线性规划问题的图解法

若线性规划问题只含有两个决策变量，则可考虑用几何作图法求解.下面通过例题说明图解法的一般步骤.例1对引例4.5给出的线性规划问题的数学模型试用图解法求解.11解如图直角坐标系中，所有满足约束条件的点必须落在阴影部分(它是可行域,这里的每一个点的坐标值都是可行解).目标函数可以看成是以S为参数，为斜率的一族平行直线：位于同一条直线上的点，具有同样的目标函数值.12直线沿着法线的方向向右上角移动时，的值由小到大.当移动到B点时，S的值最大.即目标函数值在顶点B处取得最大值.(此时,B点坐标就是最优解)而B点就是直线和直线的交点，求得B点坐标为（4，2），即当时，目标函数的最大值.即当该工厂生产4件产品A,2件产品B时，一天能获得的最大利润为20元.结论：若线性规划问题存在最优解，则它一定在可行域的某个顶点处.若在两个顶点同时达到最优值，则这两个顶点连线上的任意一点都是最优解.

13例2讨论线性规划问题的解的存在性?

解可作图看出,同时满足四个不等式组成的约束条件的点不存在,也就是说,该问题的可行域是空集.因此,无最优点,即没有最优解.14除了以上几种情况外,有时候可行域还可能出现无界区域.该类线性规划问题的最优解是否存在就与目标函数有紧密的联系.

因此利用图解法求线性规划问题的最优解时，可以先根据约束条件求出可行域（一般情况下是凸多边形），然后把可行域的每个顶点代入目标函数，确定出最优解即可.154.4.3线性规划问题的计算机求解

1．线性规划模型例3某公司长期饲养实验用的动物,已知这些动物的生长对饲料中的蛋白质、矿物质、维生素这三种营养成分特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg.该公司能买到五种不同的饲料,每kg饲料所含的营养成分如表4-8所示,每kg饲料的成本如表4-9所示,试为该公司制定相应的饲料配方,以满足动物生长的营养的需要,并使投入的总成本最低.16表4–8每千克饲料所含的营养成分

饲料蛋白质(g)矿物质(g)维生素(mg)123450.3210.61.80.10.050.020.20.050.050.10.020.20.08表4–9每千克饲料的成本饲料12345成本(元)0.20.70.40.30.517解设表示混合饲料中所含的第种饲料的数量(即决策变量),因为每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg,所以应满足的约束条件为因要求配出来的饲料其总成本S最低,故其目标函数为18由于约束条件及目标函数均为线性函数,故饲料配比问题的线性规划模型为该问题可以利用LINGO软件求解.在LINGO软件中打开一个新文件,像书写模型一样,直接输入:min0.2x1+0.7x2+0.4x3+0.3x4+0.5x5st0.3x1+2x2+x3+0.6x4+1.8x5>=700.1x1+0.05x2+0.02x3+0.2x4+0.05x5>=30.05x1+0.1x2+0.02x3+0.2x4+0.08x5>=10end19[注]①LINGO中已规定的所有决策变量均为非负,所以非负条件不需要在程序中体现.②LINGO中乘号省略,式子中不能有括号,右端不能有数学符号.③LINGO程序中符号≤,≥用＜=,＞=形式输入,它们与＜,＞等效④第一为目标函数,其输入时min或max后的变量及等号都不需要输入.⑤在输入约束条件的前一行要输入st表示要满足的约束条件.程序最后要以end语句表示结束.20程序运行输出结果为Globaloptimalsolutionfound.Objectivevalue:24.74359Totalsolveriterations:4VariableValueReducedCostX10.0000000.8846154E-01X20.0000000.1358974X30.0000000.1410256X439.743590.000000X525.641030.000000RowSlackorSurplusDualPrice124.74359-1.00000020.000000-0.243589736.2307690.00000040.000000-0.769230821根据上述输出结果可知最优解为从而最低成本为[注意]在上述问题求解的基础上,我们可以进一步进行以下思考:(1)如果每个动物每天至少所需的蛋白质量增加到80g,则公司的饲料配方要如何调整?(2)如果饲料2每千克的成本降低到0.5元,则公司的饲料配方要如何调整?222．整数规划模型如果一个线性规划的某些决策变量或全部决策变量要求必须取整数，则这样的问题成为整数线性规划问题.例4一汽车厂生产小、中、大三种类型的汽车，已知各类型的每辆车对钢材、劳动时间的需求，利润以及每月工厂钢材、劳动时间的现有量如下表所示.试制定每月生产计划,使工厂的利润最大.小型中型大型现有量钢材(t)1.535600劳动时间(h)28025040060000利润(万元)23423解设每月生产小、中、大型汽车的数量分别为，工厂的月利润为，在题目所给参数均不随生产数量变化的假设下，立即可得线性规划模型.目标函数在LINGO软件求解中，程序最后即end语句后一行输入：“gin3”表示均为整数，求得该问题的最优解最优值S=632，即问题要求的月生产计划为生产小型车64辆，中型车168辆，不生产大型车.243．0-1规划模型在实际的规划问题中常常可以遇到这样的问题:一个决策只用来指明一项可能的行动.究竟是采用()呢？还是采用()呢？这里的决策变量仅取0或1两个值，即二元决策变量.25例5解下列0-1规划问题:由于为0-1变量,用LINGO软件求解时.可在程序最后类似整数规划输入:“int3”.最后求得该问题的最优解，最优值.264.指派问题我们常会遇到这样的问题:有n项任务要完成,恰好有n人且每人可以分别去完成其中一项(即每一人都应分配一项任务,每一任务也只能由一人去完成),但由于任务性质和各人任务的效率(或所花费的时间)有差别,因此提出下述问题:应当指派哪些人去完成哪些任务使总的效率为最高(或花费的总时间为最小)？这类问题称为指派问题，或称分派问题.27例6有一份说明书，要分别译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人完成，每人完成一种，因各人专长不同，他们翻译成不同文字所需要的时间（单位：分钟）如下表所示.问指派哪个人去完成哪项任务可使总的花费时间最少？英日德俄甲215134乙1041415丙9141613丁7811928解设用来表示当不指派第个人去完成第项任务,令:这是个指派问题,从人力资源最佳分配角度,要以花费时间最少为目标:要合理分配资源且正常完成任务受到一些客观条件的制约:(1)由于每个人只能接受一项任务:(2)又因每项任务只能分配给一个人:29所以该规划问题的数学模型为由LINGO软件运行的结果,得最佳分配方案为甲-—俄，乙—-日，丙-—英，丁---德，完成任务最少时间为28分钟.30练习题4.41．用图解法解下列线性规划问题:(1)(2)(3)(4)312．某厂拟用集装箱托运甲、乙两种物资，每箱的体积、重量可获利润及托运所受限制如下表所示．问两种物资各托运多少箱，可使获得利润最大？(请按两种要求分别解题：①可拆箱装运②整箱装运)物资体积（立方米）重量（百公斤/箱）利润（百元/箱）甲乙54252010托运限制2413323.某公司有1亿元资金用于4个工程项目的投资,其投资各项目时所得的净收益如下表所示工程项目ABCD收益(%)1510812由于某种原因,决定用于项目A的投资不大于其他各项投资之和,而用于项目B和C的投资要大