简单的线形规划人教

简单的线形规划,一、复习回顾,1、二元一次方程与不等式的联系：,即：“直线定界，特殊点定域”,特别地,当C不等于0时，取(0,0),3、画不等式组所表示的平面区域,等价于画各个不等式所表示的平面区域的公共部分,4、画一些特殊的复杂不等式所表示的平面区域。,等价于画其几个不等式组的并集比如（x-1）(y+1)0、,简单的说，就是A与不等式的符号相同，则取x轴的正方向区域，即直线一侧的右方区域；B与不等式的符号相同，则取y轴的正方向区域，即直线一侧的上方区域；反之，异号，取负方向区域。,5、特别地，我们在画二元一次不等式的时候，总结的一个规律，“同为正，异为负”,练习:,(1)、二元一次不等式x+2y-60表示的平面区域为D，则：、当A0,B0时，D为的、当A0,B0时，D为的、当A0,B0时，D为的,右上方,右下方,左上方,左下方,左下方,当x=3,y=0时，得出2x+y的最小值为6，但此时x+y=3，点(3,0)不在不等式组的所表示的平面区域内，所以上述解答明显错了,怎么来解决这个问题和这一类问题呢？这就是我们今天要学习的线性规划问题。,要求z的范围，现在就转化为求这一组平行线中,与阴影区域有交点,且在y轴上的截距达到最大和最小的直线.,由图，我们不难看出，这种直线的纵截距的最小值为过A(3,1)的直线，纵截距最大为过C(5,1)的直线。,所以,过A(3,1)时，因为z=2x+y，所以,同理，过B(5,1)时，因为z=2x+y，所以,线性规划里的一些基本概念：,1、线性约束条件：由x,y的一次不等式（或方程）组成的不等式组。,2、目标函数：关于x,y的解析式，如z=2x+y,3、线形目标函数：如果这个解析式是x,y的一次解析式，则目标函数又称为线形目标函数。,7、线性规划问题：求线形目标函数在线形约束条件下的最大值或最小值的问题，统称为线形规划问题。,4、可行解：满足线形约束条件的解（x,y）叫做可行解,6、最优解：分别使目标函数取得最大值和最小值的解，叫做这个问题的最优解。,5、可行域：由所有可行解组成的集合叫做可行域。,y,例求z=2x+y的最大值，和最小值，使式中的变量x,y满足约束条件,解：作线形约束条件所表示的平面区域，即如图所示四边形ABCD。,作直线,所以，,求得A(3,1)B(4,0)C(5,1)D(4,2),1、我们首先根据线形约束条件画出可行域(即画出不等式组所表示的公共区域)；,结论:,1、线形目标函数的最大值、最小值一般在可行域的顶点处取得；,2、线形目标函数的最大值、最小值也可能在可行域的边界上取得，即满足条件的最优解有无数个。,解线形规划问题的基本步骤：,3、代入计算。（直接代入交点坐标，可得最大、最小值）,（令z=0，画出，在可行域内平行移动，得其在y轴有最大、最小截距的两条平行线）,所以，通常我们通过解方程组，求出要用的顶点坐标。,特别地，当B，Z的最大值就是直线最大截距的时候，Z的最小值是直线有最小截距的时候；反之，B，则相反。,例2:某工厂生产甲、乙两种产品已知生产甲种产品1t需耗A种矿石10t、B种矿石5t、煤4t；生产乙种产品1t需耗A种矿石4t、B种矿石4t、煤9t每1t甲种产品的利润是600元，每1t乙种产品的利润是1000元工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t，B种矿石不超过200t，煤不超过360t甲、乙两种产品应各生产多少(精确到0.1t)，能使利润总额达到最大?,分析:将已知数据列成下表:,10,4,300,5,4,200,4,1000,600,360,9,解：设生产甲、乙两种产品分别为xt、yt，利润总额为z元，那么,目标函数Z=600 x+1000y,例3(书p65.4),解：设隔出大房间x间，小房间y间时收益为z元，则x，y满足,且,即,作直线l:200 x+150y=0即直线l:4x+3y=0,把直线l平移至l1时，直线经过可行域上的B点，且与原点距离最大，此时，Z=200 x+150y取最大值。,l,l1,4x+3y-260=0,经验证,要求经过可行域内的整数点，且使z=200 x+150y取得最大值，经过的整数点是D（0，12）和C(3,8),此时Zmax=1800,所以，应隔出小间12间，或大间3间，小间8间，可以获得最大利润.,解方程组,得B点坐标为,由于点B的坐标不是整数点，而最优解(x,y)中x,y必须都是整数，所以，可行域内的点B不是最优解。,例4。某公司承担了每天至少搬运280t水泥的任务，已知该公司有6辆A型卡车和4辆B型卡车，已知A型卡车每天每辆的运载量为30t，成本费为0.9千元，B型卡车每天每辆的运载量为40t，成本费为1千元。（1）假设你是公司的调度员，请你按要求设计出公司每天的排车方案。（2）设每天派出A型卡车x辆，B型卡车y辆，公司每天花费成本为Z千元，写出x、y应满足的条件以及Z与x、y之间的函数关系式。,Z=0.9x+y,3x+4y280x60y4,例5、某公司承担了每天至少搬运280t水泥的任务，已知该公司有6辆A型卡车和4辆B型卡车，已知A型卡车每天每辆的运载量为30t，成本费为0.9千元，B型卡车每天每辆的运载量为40t，成本费为1千元。（1）假设你是公司的调度员，请你按要求设计出公司每天的排车方案。设每天派出A型卡车x辆，B型卡车y辆，（2）若公司每天花费成本为Z千元，写出x、y应满足的条件以及Z与x、y之间的函数关系式。,(3)如果你是公司的经理，为使公司所花的成本费最小，每天应派出A型卡车、B型卡车各为多少辆,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最小,Z=0.9x+y为最