简单的线性规划问题-完整版课件

3.32简单的线性规划问题XOYABC回顾知识

上一小节我们已经学过了，现实生活中有很多问题可以转化成解二元一次不等式组.

一个一元二次方程表示的应为直线Ax+By+C=0某一侧所有的点组成的平面区域.如何确定直线定界，特殊点定域想想是怎么具体操作的？新课导入

在现实生产、生活中，经常会遇到资源利用、人力调配、生产安排等问题.利用我们今天所学的知识，可以解决很多现实生活中简单的线性规划问题.

下面我们看一个线型规划知识解决实际问题的一个小例子.引例

某工厂有A、B两种配件生产甲、乙两种产品，每生产一件甲产品使用4个A配件耗时1h,每生产一件乙产品使用4个B配件耗时2h，该厂每天最多可从配件厂获得16个A配件和12个B配件，按每天8h计算，该厂所有可能的日生产安排是什么？（1）用不等式组表示问题中的限制条件；

（2）画出不等式组所表示的平面区域：如上图，图中的阴影部分的整点（坐标为整数的点）就代表所有可能的日生产安排；

（3）提出新问题：

进一步，若生产一件甲产品获利2万元，生产一件乙产品获利3万元，采用哪种生产安排利润最大？（4）尝试解答：

分析：设生产甲产品x件，乙产品y件时，工厂获得的利润为z,则z=2x+3y.这样，上述问题就转化为：当x,y满足上不等式组并且为非负整数时，z的最大值是多少？把z=2x+3y变形为

这是斜率为截距为的直线.当z变化时，可以得到一族互相平行的直线，如图，由于这些直线的斜率是确定的，因此只要给定一个点，（例如（1，2）），就能确定一条直线这说明，截距可以由平面内的一个点的坐标唯一确定.可以看到，直线与不等式组的区域的交点满足这个不等式组，而且当截距

最大时，z取得最大值.因此，问题可以转化为当直线与不等式组确定的平面区域有公共点时，在区域内找一个点P，使直线经过点P时截距最大

.（5）获得结果：由图中可以看出，当实现

x=4与直线x+2y-8=0的交点M（4，2）时，截与直线距的值最大，最大值为这时2x+3y=14.

所以，每天生产甲产品4件，乙产品2件时，工厂可获得最大利润14万元.小结：1、像上题求最大利润的这种问题，可以转化成求二元一次不等式组与一族直线相交点的问题.2、遇到没有学过的问题时，一定要认真思考，看看能不能用平时的知识去解决.概念(1)线性约束条件：在上述问题中，不等式组是一组变量x、y的约束条件，这组约束条件都是关于x、y的一次不等式，故又称线性约束条件．(2)线性目标函数;关于x、y的一次式z=2x+y是欲达到最大值或最小值所涉及的变量x、y的解析式，叫线性目标函数.(3)线性规划问题：一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.(4)可行解、可行域和最优解：满足线性约束条件的解（x,y）叫可行解．由所有可行解组成的集合叫做可行域.

使目标函数取得最大或最小值的可行解叫线性规划问题的最优解．思考：(1)在上述问题中，如果生产一件甲产品获3万元，每生产一件乙产品获利2万元，有应当如何安排生产才能获得最大利润？在换几组数据试试.(2)有上述过程，你能得出最优解与可行域之间的关系吗?相同的思路，留给同学们自己思考！实地演练变量x、y满足下列条件，求z的最大值和最小值.讨论下面的问题，设z=2x+y+50，式中的目标函数（线性目标函数）约束条件（线性约束条件）最优解

求线性目标函数z的最值的步骤：⑴画⑷

求⑶移⑵作l。（3，2）(8,2)解：yX01234567123458

由上图可得当直线z=2x+y+50过点（3，2）时，目标函数取最小值;当直线过点（8，2）时，目标函数取的最大值.

答：目标函数z=2x+y+50的最小值为58，最大值为58.小结：解线性规划问题的步骤：

（1）画：画出线性约束条件所表示的可行域；

（2）移：在线性目标函数所表示的一组平行线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；（3）求：通过解方程组求出最优解；（4）答：作出答案.例：1

若需在长为4000mm的圆钢上，截出长为698mm和518mm两种毛坯，问怎样截取才能使残料最少？

初步分析：

可以先考虑两种“极端”的情况：全部截出长为698mm的甲件，一共可截出5件，残料长为510mm；全部截出长为518mm的乙件，一共可截出7件，残料长为374mm.从而x与y应搭配使用.解：截x个甲件，y个乙件，则截取条件数学化地表示出来就是698x+518y4000同时x与y都是非负整数；目标函数为约束条件为698x+518y4000x≥0，y≥0，x∈N，y∈NXOYL：698x+518y=4000

将目标函数代表的直线族画出，然后寻找使目标函数最大的点即可.x和y都是整数！例：2

要将两种大小不同的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示：规格类型钢板类型A规格B规格C规格第一种钢板211第二种钢板123

今需要A、B、C三种规格的成品分别为15、18、27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少？

分析：本题是给定一项任务，如何合理安排和规划，能以最少的资源来完成该项任务.我们应该搞清各量之间的关系，建立线性规划的模型.第一种钢板x张，第二种钢板y张，所用解：钢板数为z张，则z=x+y

；由题中表格得

作出以上不等式组所表示的平面区域,即可行域.

作直线L:x+y=0,

把直线L向右上方平移至直线经过可行域上的点A，且与原点距离最近，此时z=x+y取最小值.

oxy816248162x+y=15x+2y=18x+2y=18A解方程组得交点A的由于两个坐标都不是整数，所以这个解不是最优解；

将直线向可行域内平移，最先到达的整点为B(3,9)和C(4,8)它们是最优解，此时z取得最小值12.坐标

答：要截得所需规格的三种钢板，且使所截两种钢板的张数最少的方法有两种，第一种截法是截第一种钢板3张、第二种钢板9张；第二种截法是截第一种钢板4张、第二种钢板8张，两种方法都最少要截得两种钢板共12张.2x+y=15oxy81624816x+2y=18x+2y=18A例：3

某工厂生产甲、乙两种产品，生产甲种产品1t需耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需耗A种矿石4t、B种矿石4t、煤9t．每1t甲种产品的利润是600元，每1t乙种产品的利润是1000元．工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过360t．甲、乙两种产品各生产多少（精确到1t），能使利润总额达到最大？

分析：这是线性规划的理论和方法的应用中的第一类问题．即在人力、物力资源一定的条件下，如何使用它们来完成最多任务．解题一般步骤为：①设出所求的未知数；②列出约束条件③建立目标函数；④作出可行域；⑤运用图解法求出最优解．依据题中已知条件，列表如下：

甲产品（1t）乙产品（1t）资源限额（t）A种矿石（t）104300B种矿石（t）54200煤（t）49360利润（元）6001000

资源消耗品产品解：生产甲、乙两种产品分别为xt,

yt,利润总额为z，由题意可得已知变量x与y满足约束条件利用图解法可求出最大值.此时，课堂小结1、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界处取得.2、求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义—在y轴上的截距或其相反数.3、解线性规划问题的步骤：画、移、求、答.课堂练习1、求z=2x+y的最大值，使式中的x、y满足约束条件解：用图形表示出不等式组表示的平面区域；当x=0,y=0时，z=2x+y=0作一组与直线平行的直线:2x+y=t,t∈R.

可知，在经过不等式组所表示的公共区域内的点且平行于的直线中，以经过点A（2，-1）的直线所对应的t最大.2、某公司承担了每天至少搬运280t水泥的任务，已知该公司有6辆A型卡车和B型卡车，已知A型卡车每天每辆的运载量为30t，成本费为0.9千元，B型卡车每天每辆的运载量为40t，成本费为1千元.

（1）假如你是公司的调度员，请你按要求设计出公司每天的派车方案；

（2）设每天派出A型卡车x辆，B型卡车y辆，公司每天所花成本费z千元，写出x、y应满足的条件以及z与x、y之间的函数关系式；(3)如果你是公司的经理，为使公司所花的成本费最小，每天应派出A型卡车、B型卡车各为多少辆？解：由已知条件可知，Z=0.9x+y式中x与y变量应满足：3x+4y≥280≤x≤6