线性规划问题及其数学模型
,系统工程,线性规划问题及其数学模型,第一组,1334,线性规划予以解决的实际问题,线性规划解决实际问题,对给定资源予以充分地、合理的运用,使之完成的任务尽可能的多。即:以最大收益扣除定量成本,资源给定,以尽可能少的资源消耗完成给定任务。即:以定量收益扣除最小成本,任务规定,合理地利用有限的人力、物力、财力等资源,以获得最好的经济效果,目的,线性规划的定义,线性规划的定义,当收益和消耗均与计划指标成正比时,一个规划问题所列出的数学表达式都是关于计划指标的线性关系式,称此类型规划问题为线性规划问题,在一组线性约束条件下,求一组非负变量的值,使一个线性目标函数达到最大或者最小,线性规划问题的定义,线性规划问题的内容,线性规划实例讲解,例题: 靠近某河流有两个化工厂,流经第一家工厂的河水流量是每天500万立方米;在两家工厂之间有一条流量为每天200万立方米的支流,第一家工厂每天排放工业污水2万立方米;第二家工厂每天排放工业污水1.4万立方米从第一家工厂排出的污水流到第二家工厂之前,有20%可自然净化根据环保要求,河流中工业污水的含量应不大于0.2%若这两家工厂各自处理一部分污水,第一家工厂处理污水的成本是1000元/万立方米,第二家工厂处理污水的成本是800元/万立方米现在要问在满足环保要求的条件下,每厂各应处理多少污水,才能使两厂总的处理污水费用最小?,污水2w/天,污水1.4w/天,20%自然净化,总流量700w立方米,剩余80%未净化,0.2%(标准),0.2%(标准),支流净化,主流净化,化简得X11,化简得0.8X1+X21.6,由于每个工厂每天处理的污水量不会大于每天的排放量,固有1<=2,X2<=1.4。问题的目标是要求两个工厂用于处理污水总的费用最小。以Z表示费用,这是Z=1000X1+800X2。,污水量不会大于排放量,上述不等式的结果,线性规划模型的三要素: 1)定义决策变量集合:x1,x2, ,xn,这组决策变量的每一 组可能的值就代表问题的一个具体解决方案; 2)定义目标函数:用决策变量的线性函数形势写出所要追求的目标, 称之为目标函数:z=f(x1,x2, ,xn),根据问题的不同,要求目标函数实现最大化或最小化; 3)定义约束条件集合:用一组决策变量的等式或不等式来表示在决策问题过程中所必须遵循的约束条件。线性规划的一般模型目标函数:max(min)f=C1X1+C2X2+···+CnXn;约束条件:,将线性规划模型化为标准形式,例题的目标函数是求最小,,需要变为求最大。对于“>=”形式的不等式,需要在不等式的左边减去非负的剩余变量,使其变为等式;对于“<=”形式的不等式,需在不等式的左边加上非负的松弛变量,使其变为等式;剩余变量和松弛变量在目标函数中的系数为0。求最小值的令 max Z= -min Z,X1 -X3=10.8X1 + X2 -X4=1.6 X1 + X5=2 X2 + X6=1.4 X1,X2,X3+ X4+ X5,X6>=0,标准形式,max Z= -min Z = -1000X1 - 800X2 + 0X3 + 0X4 + 0X5 + 0X6,谢谢观看,