12简单的线性规划(2).ppt
简单的线性规划问题简单的线性规划问题第二讲第二讲 线性规划线性规划线性规划问题：问题：设设z=2x+y，式中变量满足下列条件：，式中变量满足下列条件：求求z的最大值与最小值。的最大值与最小值。线性规划问题：设z=2x+y，式中变量满足下列条件：求z的最大值与最小值。线性目标函数线性目标函数线性约束条线性约束条件件线性规划线性规划：线性规划：求线性目标函数在线性约束条件下的最求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题大值或最小值的问题，统称为线性规划问题 可行解可行解：满足线性约束条满足线性约束条件的解件的解(x，y)叫可行解；叫可行解；可行域可行域：由所有可行解组由所有可行解组成的集合叫做可行域；成的集合叫做可行域；最优解最优解：使目标函数取得使目标函数取得最大或最小值的可行解叫最大或最小值的可行解叫线性规划问题的最优解。线性规划问题的最优解。可行域可行域(1,1)(5,2)将将z=2x+y改为改为y=-2x+z几个结论：几个结论：1、线性目标函数的最大（小）值一般、线性目标函数的最大（小）值一般在可行域的顶点处取得，也可能在边界在可行域的顶点处取得，也可能在边界处取得。处取得。2、求线性目标函数的最优解，要注意、求线性目标函数的最优解，要注意分析线性目标函数所表示的几何意义分析线性目标函数所表示的几何意义在在y轴上的截距或其相反数。轴上的截距或其相反数。线性规划例例1 解下列线性规划问题：求z=2x+y的最大值和最小值，使式中x、y满足下列条件：解线性规划问题的一般步骤：解线性规划问题的一般步骤：第一步：在平面直角坐标系中作出可行域；第一步：在平面直角坐标系中作出可行域；第二步：在可行域内找到最优解所对应的点；第二步：在可行域内找到最优解所对应的点；第三步：解方程得最优解，从而求出目标函数第三步：解方程得最优解，从而求出目标函数的最大值或最小值。的最大值或最小值。答案：当x=-1,y=-1时，z=2x+y有最小值3.当x=2,y=-1时，z=2x+y有最大值3.变：z=x+2y解线性规划问题的步骤：解线性规划问题的步骤：（2 2）移：在线性目标函数所表示的一组平行）移：在线性目标函数所表示的一组平行 线中，利用平移的方法找出与可行域有公共线中，利用平移的方法找出与可行域有公共点且纵截距最大或最小的直线；点且纵截距最大或最小的直线；（3 3）求：通过解方程组求出最优解；）求：通过解方程组求出最优解；（4 4）答：作出答案。）答：作出答案。（1 1）画：画出线性约束条件所表示的可行域；）画：画出线性约束条件所表示的可行域；例例2已知已知满满足足分分别别求求(1)(2)的最的最值值.例例3在如图所示的坐标平面的可行在如图所示的坐标平面的可行域（阴影部分且域（阴影部分且包括包括边边界）内，目界）内，目标标函数函数取得最取得最值值的的最最优优解有无数个，求解有无数个，求实实数数的的值值.例例5:某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品,生产生产1t甲种产甲种产品需要品需要A种原料种原料4t,B种原料种原料12t,产生的利润是产生的利润是2万万元；生产乙种产品需要元；生产乙种产品需要A种原料种原料1t,B种原料种原料9t,产产生的利润是生的利润是1万元万元,现有库存现有库存A种原料种原料10t,B种原料种原料60t,如何安排生产才能使得利润最大如何安排生产才能使得利润最大?设计划生产甲设计划生产甲、乙两种产品的吨数分别是乙两种产品的吨数分别是x,y,利润为利润为P,则则目标函数为目标函数为P=2x+y作出约束条件所表示的平面区域作出约束条件所表示的平面区域将将P=2x+y变为变为y=-2x+P平移直线平移直线y=-2x+P当直线经过两直线当直线经过两直线4x+y=10和和4x+3y=20的交点的交点A(1.25,5)时时,直线直线y=-2x+P在在y轴上的截距轴上的截距P最大最大.所以所以,当当x=1.25,y=5时目标函数取得最大值时目标函数取得最大值7.5,即甲乙分别生产即甲乙分别生产1.25t,5t时获得最大利润时获得最大利润7.5万元万元.例例6:投资生产投资生产 产品时，每生产一百吨需要资金产品时，每生产一百吨需要资金200万万元，需场地元，需场地200，可获利润万元；投资生产，可获利润万元；投资生产 产品时，每生产一百米需要资金产品时，每生产一百米需要资金300万元，需场地万元，需场地100，可获利润，可获利润200万元现某单位可使用资万元现某单位可使用资1400万元，万元，场地场地900，问：应作怎样的组合投资，可使获利最大，问：应作怎样的组合投资，可使获利最大？例例7:某运输公司向某地区运送物资，每天至少运送某运输公司向某地区运送物资，每天至少运送180该公司有辆载重为的该公司有辆载重为的 型卡车与辆载重为型卡车与辆载重为10的的 型卡车，有型卡车，有10名驾驶员每辆卡车每天往返次名驾驶员每辆卡车每天往返次数为数为 型车次，型车次，型车次每辆卡车每天往返的成型车次每辆卡车每天往返的成本费型车为本费型车为320元，元，型车为型车为504元试为该公司设元试为该公司设计调配车辆方案，使公司花费的成本最低计调配车辆方案，使公司花费的成本最低设每天调出设每天调出 型车型车 辆，辆，型车型车 辆，公司花费成本元，辆，公司花费成本元，目标函数为目标函数为z=320 x+504y 作出可行域作出可行域当直线当直线320504=经过直线经过直线4x+5y=30与轴与轴的交点的交点(7.5,0)时，时，z有最小值，由于（有最小值，由于（7.5,0）不是整点）不是整点，故不是最优解，故不是最优解所以所以,当当x=8,y=0,即公司每天调出即公司每天调出A型车型车8辆时辆时,花费的成本最低花费的成本最低.补补充充:1 已知已知满满足足求求的最大的最大值值和最小和最小值值.2 已知已知满满足足,求求的取的取值值范范围围.
