目标规划 胡运权 第四版 运筹学.ppt

第一节第一节 目标规划模型目标规划模型 1.1 目标规划的基本概念目标规划的基本概念 1.2 目标规划的数学模型目标规划的数学模型 精品课程运筹学LPLP：单一目标函数单一目标函数 追求目标的极端值追求目标的极端值DPDP：多个目标函数多个目标函数 完成额定的总产值完成额定的总产值多目标多目标(DP)(DP)与与单目标规划（单目标规划（LP)LP)的区别是：的区别是：精品课程运筹学 目标规划是在线性规划的基础上，为适应经济管理目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。中多目标决策的需要而逐步发展起来的一个分支。2 2、线性规划求最优解；目标规划是找到一个满意解。、线性规划求最优解；目标规划是找到一个满意解。1 1、线性规划只讨论一个线性目标函数在一组线性约、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。求得更切合实际的解。1.1 目标规划的基本概念目标规划的基本概念（一）、目标规划与线性规划的比较（一）、目标规划与线性规划的比较精品课程运筹学 4 4、线性规划的最优解是绝对意义下的最优，但需花、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。只要求得满意解，就能满足需要（或更能满足需要）。3 3、线性规划中的约束条件是同等重要的；而目标规划、线性规划中的约束条件是同等重要的；而目标规划中有轻重缓急和主次之分，即有优先权。中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。分析、财务管理等方面得到了广泛的应用。精品课程运筹学 例一、某厂计划在下一个生产周期内生产甲、乙两例一、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。产。试建立此问题的数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲单位单位产产品品资源资源消耗消耗（二）、目标规划的基本概念（二）、目标规划的基本概念精品课程运筹学设：甲产品设：甲产品 x1，乙产品乙产品 x2 一般有：一般有：maxZ=70 x1+120 x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0同时：同时：maxZ1=70 x1+120 x2 minZ2=x1 maxZ3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0 显然，这是一个多目标规划问题，用线性规划方法显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。很难找到最优解。精品课程运筹学 目标规划通过引入目标值和偏差变量，可以将目标目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量实现值或决策值：是指当决策变量x xj j 选定以后，目选定以后，目标函数的对应值。标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异和目标值之间的差异,记为记为 d d。正偏差变量：表示实现值超过目标值的部分，记为正偏差变量：表示实现值超过目标值的部分，记为 d d。负偏差变量：表示实现值未达到目标值的部分，记负偏差变量：表示实现值未达到目标值的部分，记为为 d d。1 1、目标值和偏差变量、目标值和偏差变量精品课程运筹学 当完成或超额完成规定的指标则表示：当完成或超额完成规定的指标则表示：d d0,d d0 当未完成规定的指标则表示：当未完成规定的指标则表示：d d0,d d0 当恰好完成指标时则表示：当恰好完成指标时则表示：d d0,d d0 d d d d 0 0 成立。成立。引入了目标值和正、负偏差变量后，就对某一问引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束目标约束即可对原目标函数起作用，也可对原约束起作用。起作用。目标约束是目标规划中特有的，是软约束。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未达到在一次决策中，实现值不可能既超过目标值又未达到目标值，故有目标值，故有 d d d d 0,0,并规定并规定d d0,d d02 2、目标约束和绝对约束、目标约束和绝对约束精品课程运筹学 绝对约束（系统约束）是指必须严格满足的等式或绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。约束，否则无可行解。所以，绝对约束是硬约束。例如：在例一中，规定例如：在例一中，规定Z1 的的目标值为目标值为 50000,正、负正、负偏差为偏差为d、d,则则目标函数可以转换为目标约束，既目标函数可以转换为目标约束，既70 x1+120 x2 50000，同样，若规定同样，若规定 Z2200，Z3250 则有则有 若规定若规定36003600的钢材必须用完，原式的钢材必须用完，原式9 x1+4 x2 3600则则变为变为精品课程运筹学 达成函数是一个使总偏差量为最小的目标函数，记为达成函数是一个使总偏差量为最小的目标函数，记为 minZ=f（d、d）。）。一般说来，有以下三种情况，但只能出现其中之一：一般说来，有以下三种情况，但只能出现其中之一：.要求恰好达到规定的目标值，即正、负偏差变量要要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则尽可能小，则minZ=f（d d）。）。.要求不超过目标值，即允许达不到目标值，也就是要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则正偏差变量尽可能小，则minZ=f（d）。）。.要求超过目标值，即超过量不限，但不低于目标值，要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则也就是负偏差变量尽可能小，则minZ=f（d）。）。对于由绝对约束转化而来的目标函数，也照上述处理即对于由绝对约束转化而来的目标函数，也照上述处理即可。可。3 3、达成函数（即目标规划中的目标函数）、达成函数（即目标规划中的目标函数）精品课程运筹学 优先因子优先因子Pk 是将决策目标按其重要程度排序并表示是将决策目标按其重要程度排序并表示出来。出来。P1P2PkPk+1PK，k=1.2K。权系数权系数k 区别具有相同优先因子的两个目标的差区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。别，决策者可视具体情况而定。对于这种解来说，前面的目标可以保证实现或部分对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。有些可能就不能实现。4 4、优先因子（优先等级）与优先权系数、优先因子（优先等级）与优先权系数 5 5、满意解（具有层次意义的解）、满意解（具有层次意义的解）精品课程运筹学小结：小结：1、约束条件：、约束条件：硬约束硬约束(绝对约束绝对约束)软约束软约束(目标约束目标约束)，引入，引入d-,d+2 2、目标优先级：、目标优先级：P1 P2 PL 同一级中可以有若干个目标：同一级中可以有若干个目标：P21,P22,P23 其重要程度用权重系数其重要程度用权重系数W21,W22,W23 表示表示精品课程运筹学3 3、目标函数：、目标函数：(1)(1)、恰好达到目标：、恰好达到目标：minZ=f(d-+d+)(2)(2)、超过目标：超过目标：minZ=f(d-)(3)(3)、不超过目标：不超过目标：minZ=f(d+)精品课程运筹学 若在例一中提出下列要求：若在例一中提出下列要求：1、完成或超额完成利润指标、完成或超额完成利润指标 50000元；元；2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；3、现有钢材、现有钢材 3600吨必须用完。吨必须用完。试建立目标规划模型。试建立目标规划模型。分析：题目有三个目标层次，包含四个目标值。分析：题目有三个目标层次，包含四个目标值。第一目标：第一目标：第二目标：有两个要求即甲第二目标：有两个要求即甲 ，乙，乙 ，但两个，但两个具有相同的优先因子，因此需要确定权系数。本题可具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即用单件利润比作为权系数即 70:120，化简为，化简为7:12。例二、例二、精品课程运筹学第三目标：第三目标：目标规划模型为：目标规划模型为：精品课程运筹学 某厂生产某厂生产、两两种产品，有关数据如表种产品，有关数据如表所示。试求获利最大的所示。试求获利最大的生产方案？生产方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。解解:分析分析 第一目标：第一目标：即产品即产品的产量不大于的产量不大于的产量。的产量。第二目标：第二目标：例三：例三：精品课程运筹学第三目标：第三目标：规划模型：规划模型：精品课程运筹学（一）、模型的一般形式（一）、模型的一般形式1.2 目标规划的数学模型目标规划的数学模型精品课程运筹学（二）、建模的步骤（二）、建模的步骤 1 1、根据要研究的问题所提出的各目标与条件，确定、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；目标值，列出目标约束与绝对约束；4 4、对同一优先等级中的各偏差变量，若需要可按其对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数重要程度的不同，赋予相应的权系数 。3 3、给各目标赋予相应的优先因子、给各目标赋予相应的优先因子 P Pk k（k=1.2Kk=1.2K）。）。2 2、可根据决策者的需要，将某些或全部绝对约束、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。变量和减去正偏差变量即可。精品课程运筹学 5 5、根据决策者的要求，按下列情况之一构造一个由、根据决策者的要求，按下列情况之一构造一个由 优先因子和权系数相对应的偏差变量组成的，要求实优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。现极小化的目标函数，即达成函数。.恰好达到目标值，取恰好达到目标值，取 。.允许超过目标值，取允许超过目标值，取 。.不允许超过目标值，取不允许超过目标值，取 。精品课程运筹学（三）、小结三）、小结线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min,max系数可正负系数可正负min,偏差变量偏差变量系数系数0 0变量变量x xi,i,x xs s x xa a x xi i x xs s x xa a d d约束条件约束条件系统约束系统约束（绝对约束）（绝对约束）目标约束目标约束系统约束系统约束解解最优最优最满意最满意精品课程运筹学例例某某公公司司分分厂厂用用一一条条生生产产线线生生产产两两种种产产品品A A和和B B，每每周周生生产产线线运运行行时时间间为为6060小小时时，生生产产一一台台A A产产品品需需要要4 4小小时时，生生产产一一台台B B产产品品需需要要6 6小小时时根根据据市市场场预预测测，A A、B B产产品品平平均均销销售售量量分分别别为为每每周周9 9、8 8台台，它它们们销销售售利利润润分分别别为为1212、1818万万元元。在在制制定定生生产产计计划划时时，经经理理考考虑虑下下述述4 4项项目目标：首先，产量不能超过市场预测的销售量；标：首先，产量不能超过市场预测的销售量；其次，工人加班时间最少；其次，工人加班时间最少；第三，希望总利润最大；第三，希望总利润最大；最后，要尽可能满足市场需求最后，要尽可能满足市场需求,当不能满足当不能满足时时,市场认为市场认为B B产品的重要性是产品的重要性是A A产品的产品的2 2倍倍 试建立这个问题的数学模型试建立这个问题的数学模型精品课程运筹学讨论：讨论：若把总利润最大看作目标，而把产量不能超过市若把总利润最大看作目标，而把产量不能超过市场预测的销售量、工人加班时间最少和要尽可能满足场预测的销售量、工人加班时间最少和要尽可能满足市场需求的目标看作约束，则可建立一个单目标线性市场需求的目标看作约束，则可建立一个单目标线性规划模型：规划模型：设决策变量设决策变量 x1x1，x2 x2 分别为产品分别为产品A A，B B的产量的产量 MaxZ=12x1+18x2 s.t.4x1+6x2 60 x1 9 x2 8 x1,x2 0 精品课程运筹学 容易求得上述线性规划的最优解为容易求得上述线性规划的最优解为(9,4)(9,4)T T 到到 (3,8)(3,8)T T 所在线段上的点所在线段上的点,最优目标值为最优目标值为Z*=180,Z*=180,即可选方案有多种即可选方案有多种.在实际上在实际上,这个结果并非完全符合决策者的要这个结果并非完全符合决策者的要求求,它只实现了经理的第一、二、三条目标，而没它只实现了经理的第一、二、三条目标，而没有达到最后的一个目标。有达到最后的一个目标。精品课程运筹学 把把4 4个目标表示为不等式个目标表示为不等式.仍设决策变量仍设决策变量 x x1 1，x x2 2 分别为产品分别为产品A A，B B的产量的产量.那么那么,第一个目标为第一个目标为:x x1 1 9 9，x x2 2 8 8 ；第二个目标为第二个目标为:4 4x x1 1+6x+6x2 2 60 60 ；第第三三个个目目标标为为:希希望望总总利利润润最最大大，要要表表示示成成不不等等式式需需要要找找到到一一个个目目标标上上界界，这这里里可可以以估计为估计为252252（=12=12 9+189+18 8 8），于是有），于是有 12 12x x1 1+18+18x x2 2 252 252；第四个目标为第四个目标为:x x1 1 9 9，x x2 2 8 8；精品课程运筹学有如下目标约束有如下目标约束 x x1 1 +d d1 1-d d1 1+=9 =9 x x2 2+d d2 2-d d2 2+=8 =8 4x4x1 1+6x+6x2 2 +d d3 3-d d3 3+=60 =60 12x12x1 1+18x+18x2 2 +d d4 4-d d4 4+=252=252首先，产量不能超过市场预测的销售量；首先，产量不能超过市场预测的销售量；其次，工人加班时间最少；其次，工人加班时间最少；第三，希望总利润最大；第三，希望总利润最大；最后，要尽可能满足市场需求最后，要尽可能满足市场需求,当不能满足时当不能满足时,市场认为市场认为B B产品的重要性是产品的重要性是A A产品的产品的2 2倍倍精品课程运筹学 第一优先级要求第一优先级要求 minmin（d d1 1+d d2 2+)；第二优先级要求第二优先级要求 minmin（d d3 3+)；第三优先级要求第三优先级要求 minmin（d d4 4-)；第四优先级要求第四优先级要求 minmin（d d1 1-+2+2d d2 2-)，这里这里,当不能当不能满足市场需求时满足市场需求时,市场认为市场认为B B产品的重要性是产品的重要性是A A产品的产品的2 2倍即减少倍即减少B B产品的影响是产品的影响是A A产品的产品的2 2倍，因此我们引入倍，因此我们引入了了2:12:1的权系数。的权系数。精品课程运筹学综合上述分析，我们可得到下列目标规划模型综合上述分析，我们可得到下列目标规划模型 Minf=P1（d1+d2+)+P2 d3+P3 d4-+P4（d1-+2d2-)s.t.x1+d1-d1+=9 x2+d2-d2+=8 4x1+6x2+d3-d3+=60 12x1+18x2+d4-d4+=252 x1,x2,di-,di+0,i=1,2,3,4.精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法下面用图解法来求解例下面用图解法来求解例我们先在平面直角坐标系的第一象限内，作出与我们先在平面直角坐标系的第一象限内，作出与各约束条件对应的直线，然后在这些直线旁分各约束条件对应的直线，然后在这些直线旁分别标上别标上G-i G-i，i i=1=1，2 2，3 3，4 4。图中图中x x，y y分别分别表示问题的表示问题的x x1 1和和x x2 2；各直线移动使之函数值变各直线移动使之函数值变大、变小的方向用大、变小的方向用+、-表示表示 d di i+,d di i-精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法0 5 10 15 20 y x2015105+-G-1+-G-2+-G-4+-G-3图7-1精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法 根据目标函数的优先因子来分析求解首先考根据目标函数的优先因子来分析求解首先考虑第一级具有虑第一级具有P P1 1优先因子的目标的实现，在目标函优先因子的目标的实现，在目标函数中要求实现数中要求实现minmin（d d1 1+d d2 2+),),取取d d1 1+=d d2 2+=0.=0.图图 2 2 中中阴影部分即表示出该最优解集合的所有点。阴影部分即表示出该最优解集合的所有点。精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法图 20 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法 我们在第一级目标的最优解集合中找满足第二我们在第一级目标的最优解集合中找满足第二优先级要求优先级要求minmin（d d3 3+)的最优解的最优解.取取d d3 3+=0=0 ,可得到可得到图图3 3 中阴影部分即是满足第一、第二优先级要求的中阴影部分即是满足第一、第二优先级要求的最优解集合。最优解集合。精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法图3 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)精品课程运筹学 第第三三优优先先级级要要求求 minmin（d d4 4-)，根根据据图图示示可可知知，d d4 4-不不可可能能取取0 0值值，取取使使d d4 4-最最小小的的值值7272得得到到图图4 4中中两两阴阴影影部部分分的的交交线线(黑黑色色粗粗线线)，其其表表示示满满足足第第一一、第第二二及第三优先级要求的最优解集合。及第三优先级要求的最优解集合。最后，考虑第四优先级要求最后，考虑第四优先级要求minmin（d d1 1-+2+2d d2 2-)，即要在黑色粗线段中找出最优解。由于即要在黑色粗线段中找出最优解。由于d d1 1-的权因子的权因子小于小于d d2 2-，因此在这里可以考虑取因此在这里可以考虑取d d2 2-=0=0。于是解得于是解得d d1 1-=6=6，最优解为最优解为A A点点x x=3=3，y y=8=8。精品课程运筹学目标规划的几何意义及图解法目标规划的几何意义及图解法图4 0 5 10 15 20 yx2015105+-G-1+-G-2-+G-4+-G-3A(3,8)精品课程运筹学