运筹学基础-目标规划.ppt

《运筹学基础-目标规划.ppt》由会员分享，可在线阅读，更多相关《运筹学基础-目标规划.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、上节小结：目标规划的基本概念1.1.目标值和正、负偏差变量目标值和正、负偏差变量目标值和正、负偏差变量目标值和正、负偏差变量 目标值目标值是预先给定的某个目标的一个期望值。实现值实现值是当决策变量x1、x2、xn选定以后目标函数的对应值。偏差变量：偏差变量：偏差变量：偏差变量：实现值实现值和目标值目标值之间的差异值，用d d和d d表示。d超出目标的差值，称正偏差变量；d未达到目标的差值，称负偏差变量；2.2.绝对约束与目标约束绝对约束与目标约束绝对约束与目标约束绝对约束与目标约束绝对约束绝对约束绝对约束绝对约束又称系统约束，是指必须严格满足的等式和不等式约束。目标约束：目标约束：目标约束：目

2、标约束：对那些不严格限定的约束，连同原线性规划建模时的目标函数目标函数转化为的约束，称为目标约束目标约束目标约束目标约束。由此决策者可根据自己的要求构造一个使总偏差量为最总偏差量为最小的目标函数小的目标函数，称为达成函数达成函数，记为即达成函数是正、负偏变量的函数。有三种形式：3 3 3 3目标规划的目标函数达成函数目标规划的目标函数达成函数目标规划的目标函数达成函数目标规划的目标函数达成函数实际值恰好等于目标值，即正、负偏变量尽可能地小，这时函数是：实际值大于目标值，即负偏变量尽可能地小，这时函数是：实际值小于目标值，即负偏变量尽可能地小，这时函数是：在一个目标规划的模型中，如果两个不同目标

3、重要程度相差悬殊，为达到某一目标可牺牲其它一些目标，称这些目标是属于不同层次的优先级不同层次的优先级不同层次的优先级不同层次的优先级。优先级层次的高低可分别通过优先因子P1，P2，表示，并规定Pk Pk1，符号“”表示“远大于”，表示Pk与Pk1，不是同一各级别的量，即Pk比Pk1有更大的优先权。对属于同一层次优先级同一层次优先级的不同目标，按其重要程度可分别乘上不同的权数权数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。4.4.4.4.目标的优先级与权系数目标的优先级与权系数目标的优先级与权系数目标的优先级与权系数5.5.5.5.满意解满意解满意解满意解 目标规划问题的求解是

4、在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称它为满意解。5.25.2应用举例应用举例 例例例例1111某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外购件外，生产一台录音机需甲车间加工间生产。已知除外购件外，生产一台录音机需甲车间加工2h2h，乙车间装乙车间装配配1h1h；生产一台电视机需甲车间加工生产一台电视机需甲车间加工1h1h，乙车间装配乙车间装配3h3h；两种产品需检两种产品需检验、销售环节，验、销售环节，每台录音机检验销售费用需每台录音机检验销售

5、费用需5050元，每台电视机检验销售元，每台电视机检验销售费用需费用需3030元。元。又又甲车间每月可用工时为甲车间每月可用工时为120h120h，车间管理为车间管理为8080元元/h/h，乙车乙车间每月可用工时为间每月可用工时为150h150h，车间管理为车间管理为2020元元/h/h。估计每台录音机利润估计每台录音机利润100100元，每台电视机利润元，每台电视机利润7575元，又估计元，又估计下一年度内平均每月可销售录音机下一年度内平均每月可销售录音机5050台台，电视机，电视机8080台。台。该厂的月度目标为该厂的月度目标为 P P1 1：检验销售费用每月不超过检验销售费用每月不超过4

6、6004600元；元；P P2 2：每月销售录音机不少于每月销售录音机不少于5050台；台；P P3 3：甲、乙车间每月工时要充分利用（权数按每小时费用比例确定）；甲、乙车间每月工时要充分利用（权数按每小时费用比例确定）；P P4 4：甲车间加班不超过甲车间加班不超过20h20h。P P5 5：每月销售电视机不少于每月销售电视机不少于8080台台P P6 6：两车间加班总时间要控制（权数按每小时两车间加班总时间要控制（权数按每小时管理管理费用比例确定）费用比例确定）解解 设录音机、电视机的产量分别为设录音机、电视机的产量分别为x x1 1,x,x2 2；甲、乙工时比例为甲、乙工时比例为4 4：

7、1 1，于是，于是得到目标规划模型为得到目标规划模型为 检验销售费用每月不超过检验销售费用每月不超过4600元，元，P1min Z=Pmin Z=P1 1d1+x1 +d2-d2+50 x2+d3-d3+8050 x1+30 x2+d1-d1+4600+P P2 2d2-+P P5 5d3-d4+d6-d6+20每月销售录音机不少于每月销售录音机不少于50台，台，P2；每月销售电视机不少于每月销售电视机不少于80台，台，P52x1+x2+d4-d4+120 x1+3x2+d5-d5+150 x1,x2，di-,di+0+P P3 3(4 4d4-+d5-)甲、乙车间每月工时要充分利用，甲、乙车

8、间每月工时要充分利用，P3甲车间加班不超过甲车间加班不超过20h，P4+P P4 4d6+P P6 6(4(4d4+d5+)两车间加班总时间要控制，两车间加班总时间要控制，P6最后得x1=50，x2=40，d d1 1-=900，d d4 4+=20 ，d d5 5+=20，即每月生产录音机50台，电视机40台，利润额可达到8000元 例例例例2222某制药公司有甲、乙两个工厂，现要生产A、B两种药品均需在两个工厂生产A药品在甲厂加工2h，然后送到乙厂检测包装2.5h才能成品，B药在甲厂加工4h，再到乙厂检测包装1.5h才能成品A、B药在公司内的每月存贮费分别为8元和15元甲厂有12台制造机器

9、，每台每天工作8h，每月正常工作25天，乙厂有7台检测包装机，每天每台工作16h，每月正常工作25天，每台机器每小时运行成本：甲厂为18元，乙厂为15元，单位产品A销售利润为20元，B为23元，依市场预测次月A、B销售量估计分别为1500单位和1000单位该公司依下列次序为目标的优先次序，以实现次月的生产与销售目标P1：厂内的储存成本不超过23000元 P2：A销售量必须完成1500单位 P3：甲、乙两工厂的设备应全力运转，避免有空闲时间，两厂的单位运转成本当作它们的权系数 P4：甲厂的超过作业时间全月份不宜超过30h P5：B药的销量必须完成1000单位 P6：两个工厂的超时工作时间总和要求

10、限制，其限制的比率依各厂每小时运转成本为准 试确定A、B药各生产多少，使目标达到最好，建立目标规划模型并化成标准型解：设解：设x1、x2 分别表示次月份分别表示次月份A A、B B药品的生产量，药品的生产量，di-、di+为相应目标约束为相应目标约束的正、负偏差变量的正、负偏差变量min Z=Pmin Z=P1 1d3+2x1+4x2+d1-d1+2400+P P2 2d4-d1+d6-d6+30 x1,x2，di-,di+0+P P3 3(6 6d1-+5 d2-)+P P4 4d6+P P6 6(6(6d4+5 5d5+)（1 1）甲、乙两厂设备运转时间约束：）甲、乙两厂设备运转时间约束：

11、甲的总时间为甲的总时间为81225=240081225=2400（h h），），乙的总工作时间为乙的总工作时间为16725=280016725=2800（h h），），则：则：2.5x1+1.5x2+d2-d2+2800（2 2）公司内储存成本约束）公司内储存成本约束(厂内的储存成本不超过厂内的储存成本不超过23000)：8x1+15x2+d3-d3+23000（3 3）销售目标约束）销售目标约束(销售量估计分别为销售量估计分别为1500单位和单位和1000单位单位)P1：厂内的储存成本不超过厂内的储存成本不超过23000元元P2：A销售量必须完成销售量必须完成1500单位单位x1+d4-d4

12、+1500 x2+d5-d5+1000（4 4）甲厂超时作业约束）甲厂超时作业约束(甲厂的超过作业时间全月份不宜超过甲厂的超过作业时间全月份不宜超过30h)P3：甲、乙两工厂的设备应全力运转：甲、乙两工厂的设备应全力运转,单位运转成本当作它们的权系数单位运转成本当作它们的权系数P4：甲厂的超过作业时间全月份不宜超过：甲厂的超过作业时间全月份不宜超过30hP5：B药的销量必须完成药的销量必须完成1000单位单位P6：超时工作时间总和要求限制：超时工作时间总和要求限制+P P5 5d5-3 3、用图解法解下列目标规划模型、用图解法解下列目标规划模型x1=400,x2=0,Z=80p3x2 100

13、200 300 400 5000 x1 100 200 300 400最满意解为x1=400,x2=05.45.4目标有优先级的目标规划解法目标有优先级的目标规划解法-加权法加权法产品产品A产品产品B产品产品C条件条件利润（万元利润（万元/吨）吨）941总利润最大化总利润最大化耗用原料（吨耗用原料（吨/吨）吨）425耗用原料总量不超过耗用原料总量不超过38吨吨排放污染（排放污染（m3/吨）吨）213排放污染总量不超过排放污染总量不超过26m3销售价格（万元销售价格（万元/吨）吨）301020销售总额不低于销售总额不低于100万元万元总产量（吨）总产量（吨）111总产量不低于总产量不低于18吨吨

14、如果以利润为目标函数，线性规划模型为：max z=9x1+4x2+x3s.t.4x1+2x2+5x3 38（1）原料总量约束 2x1+x2+3x3 26（2）排放污染约束 30 x1+10 x2+20 x3100（3）销售总额约束 x1+x2+x3 18（4）总产量约束 x1,x2,x3 0例：线性规划解得：x1=1,x2=17,x3=0，maxZ=77目标规划 如果利润期望值为77，将利润、耗用原料等五个因素作为目标，确定各目标的理想值以及偏差变量如下：目目 标标产品产品A产品产品B产品产品C目标的理目标的理想值想值正正偏差偏差变量变量负负偏差偏差变量变量利润（万元利润（万元/吨）吨）941

15、77d1+d1-耗用原料（吨耗用原料（吨/吨）吨）42538d2+d2-排放污染（排放污染（m3/吨）吨）21326d3+d3-销售价格（万元销售价格（万元/吨）吨）301020100d4+d4-总产量（吨）总产量（吨）11118d5+d5-如果目标大于理想值，正偏差变量大于0，小于理想值，负偏差变量大于0。因此，对第i个目标，有 如果各目标无优先级，要使所有的目标总偏差最小，即无优先级的目标规划模型为：无优先级的目标规划模型为：同一个目标的正负偏差变量，不可能两个同时大于0。这一结果的实际意义也是很清楚的：任何一个目标，不可能既大于理想值，又小于理想值。用单纯形法，得到目标规划的最优解、各目

16、标的值以及偏差变量的值产品产品A产品产品B产品产品C目标的目标的理想值理想值正正偏差偏差变量变量负负偏差偏差变量变量产量（吨）产量（吨）0100RHSdi+di-达达 到到 的的 目目 标标 值值利润（万元）利润（万元）4077037耗用原料（吨）耗用原料（吨）3038018排放污染（排放污染（m3）1026016销售价格（万元）销售价格（万元）10010000总产量（吨）总产量（吨）101808最优解实现值偏差变量目标有优先级的目标规划目标有优先级的目标规划产品产品A产品产品B产品产品C目标的目标的理想值理想值正正偏差偏差变量变量负负偏差偏差变量变量产量（吨）产量（吨）0100RHSdi+d

17、i-达达 到到 的的 目目 标标 值值利润（万元）利润（万元）4077037耗用原料（吨）耗用原料（吨）3038018排放污染（排放污染（m3）1026016销售价格（万元）销售价格（万元）10010000总产量（吨）总产量（吨）101808 在上面的例子中，利润、耗用原料、排放污染、销售额、总产量等五个目标是一视同仁的，最优解是使偏离五个目标的总偏差之和最小。在实际问题中，这些目标往往是有轻重缓急的。目目 标标产品产品A产品产品B产品产品C优先级优先级Pi目标的目标的理想值理想值正正偏差偏差变量变量负负偏差偏差变量变量利润（万元利润（万元/吨）吨）941177d1+d1-耗用原料（吨耗用原料

18、（吨/吨）吨）425438d2+d2-排放污染（排放污染（m3/吨）吨）213326d3+d3-销售价格（万元销售价格（万元/吨）吨）3010205100d4+d4-总产量（吨）总产量（吨）111218d5+d5-确定五个目标的优先级Pi（Pi=1，2，3，4，5），数字越小优先级越高目标规划的模型为：目标规划的模型为：优先级Pi14352 目目 标标产品产品A产品产品B产品产品C优先优先级级权重权重理想值理想值正正偏差偏差负负偏差偏差利润（万元利润（万元/吨）吨）941110000077d1+d1-耗用原料（吨耗用原料（吨/吨）吨）425410038d2+d2-排放污染（排放污染（m3/吨）

19、吨）2133100026d3+d3-销售价格（万元销售价格（万元/吨）吨）30102051100d4+d4-总产量（吨）总产量（吨）11121000018d5+d5-目标具有优先级的目标规划解法加权法 产品产品A产品产品B产品产品C理想值理想值正正偏差偏差负负偏差偏差产量产量(吨吨)0100RHSdi+di-无无 优优 先先 级级 利润（万元）利润（万元）4077037耗用原料（吨）耗用原料（吨）3038018排放污染（排放污染（m3）1026016销售价格（万元）销售价格（万元）10010000总产量（吨）总产量（吨）101808产品产品A产品产品B产品产品C理想值理想值正正偏差偏差负负偏差

20、偏差产量（吨）产量（吨）119.250RHSdi+di-有有 优优 先先 级级1利润（万元）利润（万元）7777004耗用原料（吨）耗用原料（吨）3838003排放污染（排放污染（m3）19.252606.755销售价格（万元）销售价格（万元）192.510092.502总产量（吨）总产量（吨）19.25181.250练习练习：1 1、某厂生产、某厂生产A、B、C三种产品，装配工作在同一生产线上三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为完成，三种产品时的工时消耗分别为6 6、8 8、1010小时，生产线每小时，生产线每月正常工作时间为月正常工作时间为200200小时；三种

21、产品销售后，每台可获利分别小时；三种产品销售后，每台可获利分别为为500500、650650和和800800元；每月销售量预计为元；每月销售量预计为1212、1010和和6 6台。台。该厂经营目标如下：该厂经营目标如下：1 1、利润指标为每月、利润指标为每月1600016000元，争取超额元，争取超额完成；完成；2 2、充分利用现有生产能力；、充分利用现有生产能力；3 3、可以适当加班，但加班、可以适当加班，但加班时间不得超过时间不得超过2424小时；小时；4 4、产量以预计销售量为准。试建立目标、产量以预计销售量为准。试建立目标规划模型。规划模型。2 2、用图解法求解下列目标规划问题：、用图

22、解法求解下列目标规划问题：满意解为由满意解为由x1=（3，3）,x2=（3.5，1.5）所连线段。所连线段。4 4、用、用EXCELEXCEL求解下列目标规划问题：求解下列目标规划问题：x=（10，20，10）5、用、用EXCEL解以下目标规划模型解以下目标规划模型 5、x1=12,x2=10,=14,Z=14p4 答案：答案：习习 题：题：1.已知条件如表所示已知条件如表所示工序型号每周最大加工能力AB（小时/台）（小时/台）436215050利润（元/台）300450 如果工厂经营目标的期望值和优先等级如下：如果工厂经营目标的期望值和优先等级如下：p p1 1:每周总利润不得低于每周总利润

23、不得低于1000010000元；元；p p2 2:因合同要求，因合同要求，A A型机每周至少生产型机每周至少生产1010台，台，B B型机每周至型机每周至少生产少生产1515台；台；p p3 3:希望工序希望工序的每周生产时间正好为的每周生产时间正好为150150小时，工序小时，工序的生产时间最好用足，甚至可适当加班。的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。试建立这个问题的目标规划模型。2.在上题中，如果工序在加班时间内生产出来的产品，每台A型机减少利润10元，每台B型机减少利润25元，并且工序的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划

24、模型。设x1,x2分别为在正常时间和加班时间生产A型机台数，x3,x4分别为在正常时间和加班时间生产B型机台数，目标规划数学模型为：3.某纺织厂生产两种布料，一种用来做服装，另一种用来做窗帘。该厂实行两班生产，每周生产时间定为80小时。这两种布料每小时都生产1000米。假定每周窗帘布可销售70000米，每米的利润为2.5元；衣料布可销售45000米，每米的利润为1.5元。该厂在制定生产计划时有以下各级目标：p1：每周必须用足80小时的生产时间；p2：每周加班时数不超过10小时；p3：每周销售窗帘布70000米，衣料布45000米；p4：加班时间尽可能减少。试建立这个问题的目标规划模型。设设x1,x2分别为每周生产窗帘布和医疗布的小分别为每周生产窗帘布和医疗布的小时数，目标规划数学模型为：时数，目标规划数学模型为：