简单的线性规划问题1

1、简单的线性规划问题简单的线性规划问题在约束条件在约束条件 002034104yxyxyx下，如何探求目标函数下，如何探求目标函数P=2x+y的最大值？的最大值？ 这类求线性目标函数在线性约束条件这类求线性目标函数在线性约束条件下的最大值或最小值的问题下的最大值或最小值的问题,通常称为通常称为线性线性规划规划问题问题. 引入引入 设设x,y满足以下条件：满足以下条件： 求求z=2x+y的最大值与最小值。的最大值与最小值。 133065yxyyx线性约束条件 目标函数（线性目标函数）如图，分别作出如图，分别作出 三条三条直线，直线，o5x+6y=30y=1y=3xyy=1,y=3x, 5x+6y=

2、30 再找出不等式组再找出不等式组所表示的平面区域的公所表示的平面区域的公共区域。共区域。可行域可行域x令令z=0,画出直线画出直线l0，即即l0:2x+y=0。o5x+6y=30y=1y=3xyxl0:2x+y=0问题问题:求求z=2x+y的最大值与最小值的最大值与最小值如图，平移直线如图，平移直线l0， 所对应的所对应的z随之增大；随之增大； 所对应的所对应的z随之减小。随之减小。当直线当直线l0向上平移时，向上平移时， 当直线当直线l0向下平向下平移移时时, o5x+6y=30y=1y=3xyl0:2x+y=0l1:2x+y=2l2:2x+y=4l3:2x+y=-3问题问题:求求z=2x

3、+y的最大值与最小值的最大值与最小值(13,1) 此时所对应的此时所对应的Z最小；最小；(245,1)此时所对应的此时所对应的Z最大。最大。从而得到：从而得到：zminzmax=2 +1= =2 +1= 1324553535o5x+6y=30y=1y=3xyxABCl0:2x+y=0如图，在把如图，在把l0向上平移过程中，直线与平面区向上平移过程中，直线与平面区域首先相交于点域首先相交于点A ，当相交于点当相交于点B ，l1l2问题问题:求求z=2x+y的最大值与最小值的最大值与最小值 一般地求线性目标函数在线性约束条件下一般地求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规

4、划问题。的最大值或最小值的问题，统称为线性规划问题。 满足线性约束条件的解满足线性约束条件的解( (x，y) )叫可行解。叫可行解。 由所有可行解组成的集合叫做可行域。由所有可行解组成的集合叫做可行域。 使目标函数取得最大或最小值的可行使目标函数取得最大或最小值的可行解叫线性规划问题的最优解。解叫线性规划问题的最优解。 线性规划：线性规划：可行解可行解 ：可行域可行域 ：最优解最优解 ：目标函数：目标函数： 如果两个变量如果两个变量x,y满足一组一次不等式，满足一组一次不等式，求两个变量的一个线性函数（如求两个变量的一个线性函数（如z=2x+y）的最大值）的最大值或最小值，那么就称这个线性函数

5、为目标函数。或最小值，那么就称这个线性函数为目标函数。解线性规划问题的一般步骤：解线性规划问题的一般步骤：第一步：第一步：写出线性约束条件和目标函数写出线性约束条件和目标函数z=Ax+By,根据线性约束条件在平面直角坐根据线性约束条件在平面直角坐标系中画出可行域标系中画出可行域;第二步：设第二步：设z=0,画出直线画出直线l0，平移直线，平移直线l0 ；第三步：结合图形观察、分析，从而找到最优解；第三步：结合图形观察、分析，从而找到最优解；第四步：最后求得目标函数的最大值或最小值第四步：最后求得目标函数的最大值或最小值,并写出答案并写出答案.画画移移求求答答某工厂生产甲、乙两种产品某工厂生产甲

6、、乙两种产品,生产生产1t甲种产品需甲种产品需要要A种原料种原料4t、B种原料种原料12t,利润利润2万元万元;生产生产1t乙乙种产品需要种产品需要A种原料种原料1t、B种原料种原料9t,利润利润1万元。万元。现有库存现有库存A种原料种原料10t、 B种原料种原料60t，如何安排，如何安排生产才能使利润最大？最大利润是多少？生产才能使利润最大？最大利润是多少？A种原料种原料 (t) B种原料种原料(t)利润利润(万元万元)甲种产品甲种产品(t)4122乙种产品乙种产品(t)191现有库存现有库存(t)1060练习练习:解：设计划生产甲、乙两种产品的吨数分别为解：设计划生产甲、乙两种产品的吨数分

7、别为x,y,利润为利润为z (万元万元)，由题意可得约束条件为：由题意可得约束条件为：4101296000 xyxyxy问题是：求目标函数问题是：求目标函数 的最大值。的最大值。2zxyxOy12x+9y=604x+y=102x+y=05( ,5)4A例例1.投资生产投资生产A产品时，每生产产品时，每生产100t需要资需要资金金200万元，需要场地万元，需要场地200m2,可获利润可获利润300万元万元;投资生产投资生产B产品时，每生产产品时，每生产100t,需要需要资金资金300万元，需要场地万元，需要场地100m2,可获利润可获利润200万元万元.现某单位可使用资金现某单位可使用资金140

8、0万元，万元，场地场地900m2，问：如何安排生产才能使利润，问：如何安排生产才能使利润最大？最大利润是多少？最大？最大利润是多少？资金资金 (百万元百万元) 场地场地(百百m2)利润利润(百万元百万元)A产品产品(百吨百吨)223B产品产品(百吨百吨)312限制条件限制条件149解：设计划生产解：设计划生产A产品产品x百吨，百吨， B产品产品y百吨，百吨，利润为利润为S (百万元百万元)，由题意可得约束条件为：由题意可得约束条件为：23142900 xyxyxy目标函数是目标函数是 .32Sxy作出可行域（如图），将目标函数作出可行域（如图），将目标函数 yxS23 变形为变形为 223Sx

9、y 这是斜率为这是斜率为 23 随随 变化的变化的S一族直线一族直线 . 是直线在轴上的截距，是直线在轴上的截距，2Sy2S当最大时最大当最大时最大. 但直线要和可行域相交但直线要和可行域相交. xOy2x+3y=142x+y=913 5(, )42A322Syx 由图可知，使由图可知，使3x+2y取得最大值的取得最大值的(x,y)是是两直线两直线2x+y=9与与2x+3y=14的交点的交点(3.25,2.5).此此时时 75.145 . 2225. 33 S 答：生产答：生产A产品产品325t，生产，生产B产品产品250t时，时，获利最大，且最大利润为获利最大，且最大利润为1475万元万元.

10、例例2. 某运输公司向某地区运送物资，每天至某运输公司向某地区运送物资，每天至少运送少运送180t.该公司有该公司有8辆载重为辆载重为6t的的A型卡车型卡车与与4辆载重为辆载重为10t的的B型卡车，有型卡车，有10名驾驶员名驾驶员.每辆卡车每天往返次数为每辆卡车每天往返次数为A型卡车型卡车4次，次，B型型卡车卡车3次次.每辆卡车每天往返的成本费每辆卡车每天往返的成本费A型车型车为为320元，元，B型车为型车为504元元.试为该公司设计调试为该公司设计调配车辆方案，使公司花费的成本最低配车辆方案，使公司花费的成本最低? 运用运用 解：设每天调出解：设每天调出A型车型车x 辆，辆，B型车型车y 辆

11、，公辆，公司司 花费成本花费成本z元，则约束条件为元，则约束条件为*10463101800804,xyxyxxx yN 即即*1045300804,xyxyxxx yN 目标函数为目标函数为 yxz504320 xOyx+y=104x+5y=30 x=8y=4320 x+504y=0*104 6 3 10 1800804,x yxyxyx y N 320504zxy 作出可行域，当直线作出可行域，当直线z=320 x+504y经过直线经过直线4x+5y=30与与x轴的交点轴的交点(7.5,0) 时，时，z有最小值有最小值.由由于不是整点，有图可知，经过可行域内的整点，于不是整点，有图可知，经过可行域内的整点，且与原点距离最近的直线是且与原点距离最近的直线是320 x+504y=2560,经经过的整点是过的整点是(8,0) ，它是最优解，