多目标规划1、目标规划在实际生产管理问题中,企业有时会希望几个目标都达到最优:如:产量最高,成本最低,质量最好利润最大,环境达标,运输满足同时考虑多个决策目标的决策问题称为多目标规划问题;同时考虑多个决策目标的决策模型。称为多目标规划模型。它是在线性规划基础上,应用一些相关规则建立起来的模型。能够解决线性规划解决不了的问题,弥补线性规划的不足。引例1:需要考虑多种目标•某厂计划在下一个生产周期内生产甲、乙两种产品,已知资料如表所示。试制定生产计划,使获得的利润最大?同时,根据市场预测,甲的销路不是太好,应尽可能少生产;乙的销路较好,可以扩大生产。试建立此问题的数学模型。单位产品消耗资源甲乙资源限制钢材943600煤炭452000设备台时3103000单件利润70120设:生产甲产品为x1,乙产品为x2依题意有:显然,这是一个多目标规划问题,用线性规划方法很难找到最优解。需要用一种方法能够把三个目标分轻重缓急地统一在一个模型中考量。仅考虑利润最大的线性规划模型为:考虑利润最大、尽量少销售甲产品、尽量多销售乙产品的线性规划模型为:03000103200054360049120702121212121xxxxxxxxxxMaxZ,0300010320005436004912070212121212312211xxxxxxxxxMaxZxMinZxxMaxZ,引例2:桌子-椅子•胜利家具厂生产桌子和椅子两种家具。桌子科获得利润50元/个,椅子销售可获得利润30元/个,生产桌子和椅子要求需要木材和油漆两种资源。生产一个桌子需要木材4立方分米,油漆2公斤。生产一个椅子需要木材3立方分米,油漆工1公斤。该厂目前拥有木材120立方分米,油漆50公斤。该厂提出如下目标:(1)利润达到1500元;(2)木材不超过120吨,油漆不超过50小时;(权数之比1:2)问:应该如何安排生产?2、线性规划的不足•(1)线性规划只研究在满足一定条件下,单一目标函数取得最优解。•但是在企业管理中,经常遇到多目标决策问题,如拟订生产计划时,不仅考虑总产值,同时要考虑利润,产品质量和设备利用率等。这些指标之间的重要程度(即优先顺序)也不相同,有些目标之间往往相互发生矛盾。•2、线性规划致力于解决某个目标函数的最优解。•3、线性规划把各个约束条件的重要性都不分主次地等同看待,不符合实际情况。•4、求解线性规划问题,首先要求约束条件必须相容,如果约束条件中,由于人力,设备等资源条件的限制,使约束条件之间出现了矛盾,就得不到问题的可行解。•但是在生产实际中即使出现了这样的情况,生产还得继续进行。这就给人们进一步应用线性规划方法带来困难。使线性规划的应用受到限制。3、目标规划作用•1、目标规划能更好地兼顾统筹处理多种目标的关系,求得更切合实际要求的满意解。•2、目标规划可根据实际情况,分主次地、轻重缓急地考虑各种需求问题问题。•3、目标规划能够解决有限资源和计划指标之间的矛盾,从而使一些线性规划无法解决的问题得到满意的解答。•4、目标规划可以解决约束条件不相容的情况,可以解决一些线性规划无法解决的问题。引例3:目标规划模型建立•胜利家具厂生产桌子和椅子两种家具。桌子科获得利润50元/个,椅子销售可获得利润30元/个,生产桌子和椅子要求需要木材和油漆两种资源。生产一个桌子需要木材4立方分米,油漆2公斤。生产一个椅子需要木材3立方分米,油漆工1公斤。该厂目前拥有木材120立方分米,油漆50公斤。该厂提出如下目标:(1)利润达到1500元;(2)木材不超过120吨,油漆不超过50小时;(权数之比1:2)问:应该如何安排生产?解:设决策变量为生产桌子x1个,生产椅子x2个有二个目标层次,包含三个目标值第一目标P1:第二目标P2:150030501121ddxx11dP120242221ddxx5033321ddxx22dP32dP第二目标有两个要求,其具有相同的优先因子,因此需要确定权系数。权系数比为1:2,故有)2(322ddP解:设决策变量为生产桌子x1个,生产椅子x2个有二个目标层次,包含三个目标值第一目标P1:第二目标P2:150030501121ddxx11dP120242221ddxx5033321ddxx22dP32dP第二目标有两个要求,其具有相同的优先因子,因此需要确定权系数。权系数比为1:2,故有)2(322ddP建立多目标规划数学模型:)3,2,1(0,,05031202x415003050)2(2133212221112132211jddxxddxxddxddxxddPdPMinZjj,4、目标规划模型有关的概念•1、绝对约束和目标约束•2、目标值与偏差变量•3、优先等级与权系数•4、达成函数(目标规划的目标函数)(1)绝对约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束,如线性规划问题的所有约束条件,不能满足这些约束条件的解称为非可行解,所以它们是硬约束。例如:由于钢材紧缺,用量需要严格限制,不能超过3600吨故有硬约束:9x1+4x2≤3600目标约束是目标规划特有的,可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负偏差。因此在这些约束中加入正、负偏差变量,它们是软约束。例如:钢材用量尽量控制在3600吨以内,3600是我们追求的一个目标,钢材用量可能不到3600吨,也可能超过3600吨故有软约束:9x1+4x2+d−-d+=3600其中d−、d+为偏差变量目标约束:是由原线性规划中的目标函数或约束条件通过引入目标值和偏差变量转化而来。目标值:是指预先给定的某个目标的一个期望值。实现值:是指当决策变量xj选定以后,目标函数的对应值。偏差变量:是指实现值和目标值之间的差异,记为d正偏差变量d+表示实现值超过目标值的部分;负偏差变量d−表示实现值未达到目标值的部分。在一次决策中,实现值不可能既超过目标值,同时又未达到目值,即恒有:d+×d−=0。(2)目标值和偏差变量d+,d−例如:在目标约束9x1+4x2+d−-d+=3600中目标值:3600实现值:9x1+4x2未达到部分:d−超过部分:d+(3)优先因子(优先等级)与权系数一个目标规划问题常常有若干目标。通常决策者在要求达到这些目标时,会有主次或轻重缓急的需求。优先因子Pk是将决策目标按其重要程度排序并表示出来。如,要求第一位达到的目标赋予优先因子P1,次位的目标赋予优先因子P2,…,并规定:P1P2…PkPk+1…PK,k=1.2…K它表示Pk比Pk+1有更大的优先权。如在P1级目标实现之前,其它级别的目标都不在考虑之列;也就是说P2级目标仅在实现P1级目标的基础上才会考虑;依此类推。权系数ωk是区别具有相同优先因子的两个目标的差别,其优先级可分别赋予它们不同的权系数wj,决策者可视具体情况而定。几点注意:(1)不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失,任何较低级别的目标上的收获都不可弥补。(2)在判断最优方案时,首先从较高级别目标达到的程度来决策,然后再对其次级目标的判断。(3)同一级别的目标可以是多个。各自之间的重要程度可用数量(权数)来描述。因此,同一级别目标的其中一个的损失,可用其余目标的适当收获来弥补。(4)达成函数目(标规划的目标函数)达成函数:是一个使总偏差量为最小的目标函数,是由各目标约束的正、负偏差变量和赋予的优先因子及权系数构造而成。记为:MinZ=f(d+、d-)。三种形式:•若要求恰好达到目标值,则应要求正、负偏差变量均尽可能地小,这时,目标函数的形式为Minz=f(d++d−)(2)若要求不超过目标值,但若超过了目标值,也希望超过部分(正偏差变量d+)要尽可能地小,这时目标函数的形式为:Minz=f(d+)(3)若要求超过目标值,但若没有超过目标值,也希望未达到部分(负偏差变量d−)要尽可能地小,这时目标函数的形式为:Minz=f(d−)5、多目标规划的数学模型•目标规划的一般数学模型为为权系数。KkddnjxmibxaKkgddxcdwdwPMinZkkjnjjjijnjkkkjkjkKklkklkLll,2,10,,,10,,2,1),(,2,1)(1111lklkww、6、多目标规划解的形式(1)最优解:若多目标规划问题的解能使所有的目标都达到,就称该解为多目标规划的最优解;(2)次优解或满意解:若解只能满足部分目标,就称该解为多目标规划的次优解或满意解;(3)无解:若找不到满足任何一个目标的解,就称该问题为无解。7、建立目标规划的步骤•1、找出所有目标和所有阻碍目标数实现约束条件,如资源、能力等等。•2、确定每个目标的优先级或同级目标的权系数,优先级P1•的目标最重要,P2次之,以此类推•3、定义决策变量•4、以一般的线性规划的形式表示约束条件(确定硬约束)•5、对每一个目标都建立一个含有偏差变量的目标等式(确•定目标约束),•6、写出含有优先系数或权系数的使总偏差量为最小的目标•函数。若在引例中提出下列要求:1、完成或超额完成利润指标50000元;2、产品甲不超过200件,产品乙不低于250件;3、现有钢材3600吨必须用完。试建立目标规划模型。分析:题目有三个目标层次,包含四个目标值。第一目标p1:第二目标p2:有两个要求两个要求具有相同的优先因子,因此需要确定权系数。本题可用单件利润比作为权系数即70:120,化简为7:12。11dP)127(322ddP50000120701121ddxx200221ddx250332ddx22dP-32dP第三目标p3:3600494421ddxx)(443ddP)4,3,2,1(0,,0,30001032000543600492502005000012070)()127(min2121214421332221112144332211jddxxxxxxddxxddxddxddxxddPddPdPZjj故目标规划模型为:练习1某车间有A、B两条生产相同产品的生产线。A生产线每小时可制造2件产品,B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时,要求制定完成下列目标的生产计划:(1)生产量达到210件/周;(2)A生产线加班时间限制在15小时内;(3)充分利用工时指标,并依A、B产量的比例确定重要性。解:设A,B生产线每周工作时间为x1,x2有三个目标层次,包含四个目标值第一目标P1:(生产量达到210件/周)第二目标P2:(A生产线加班时间限制在15小时内)第三目标P3(充分利用A的工时指标)11dP22dP-33dP第三目标有两个要求,其具有相同的优先因子,因此需要确定权系数。权系数比依据产量比确定,A,B的产量比例2:1.5=4:3,故有)34(4-33ddP-43dP(充分利用B的工时指标)60221ddx2105.121121ddxx45331ddx45442ddx多目标规划模型为:)4,3,2,1(0,,04545602105.12)3421442331221112143332211jddxxddxddxddxddxxdPdPdPdPMinZjj,公司计划要求按以下目标制订月生产计划:(1)库存费用不超过4600元;(2)每月销售唱机不少于80台;(3)不使A、B车间停工(权数