运筹学：c12目标规划的数学模型与应用

1、2021-10-13第第4 4章章 目标规划Goal Programming目标规划的数学模型目标规划的数学模型解目标规划的图解法解目标规划的图解法解目标规划的单纯形法解目标规划的单纯形法本节内容提要本节内容提要p目标规划的数学模型目标规划的数学模型问题的提出问题的提出建立模型的有关概念建立模型的有关概念建模的一般步骤建模的一般步骤p解目标规划的图解法解目标规划的图解法p小结小结重点掌握重点掌握问题的提出问题的提出p单目标规划单目标规划p多目标规划多目标规划化多为少方法化多为少方法分层序列法分层序列法直接求非劣解直接求非劣解目标规划目标规划层次分析法层次分析法p目标规划目标规划(Goal Pr

2、ogramming,简称简称GP)解决多目标规划的方法之一。解决多目标规划的方法之一。1952年年,美国学者美国学者Charnes等提出等提出GP。p目前，目标规划已在目前，目标规划已在经济计划、生产管理、经营经济计划、生产管理、经营管理、市场分析、财务管理管理、市场分析、财务管理等得到了广泛应用。等得到了广泛应用。例例1 某工厂生产两种产品，具体数据如下表。某工厂生产两种产品，具体数据如下表。试求获利最大的生产方案。试求获利最大的生产方案。12121212LP: Max 810211 s.t. 2100,0zxxxxxxxx*T*(4,3) , 62xz拥有量原材料2111设备(台时)121

3、0单件利润810(1)依据市场情况，产品依据市场情况，产品销售量要下降，希望销售量要下降，希望产品产品的产量不大于产品的产量不大于产品的产量。的产量。(2)充分利用设备，不希望加班。充分利用设备，不希望加班。(3)尽可能达到并超过利润计划指标尽可能达到并超过利润计划指标56元。元。市场实际情况市场实际情况要实现上述多个目标要实现上述多个目标, ,决策者如何建模分析决策者如何建模分析? ?线性规划已经不能解决此类问题！线性规划已经不能解决此类问题！本节内容提要本节内容提要p目标规划的数学模型目标规划的数学模型问题的提出问题的提出建立模型的有关概念建立模型的有关概念建模的一般步骤建模的一般步骤p解

4、目标规划的图解法解目标规划的图解法p小结小结建立模型的有关概念建立模型的有关概念pGP通过引入目标值和偏差变量，将目标函通过引入目标值和偏差变量，将目标函数转化为目标约束。数转化为目标约束。目标值：预先给定的某个目标的一个期望值。目标值：预先给定的某个目标的一个期望值。如例如例1中：尽可能达到并超过利润计划指标中：尽可能达到并超过利润计划指标56元。元。实现值：指当决策变量实现值：指当决策变量xj 选定以后，目标函数选定以后，目标函数的对应值的对应值,也称为决策值。也称为决策值。偏差变量：实现值和目标值之间的差异。偏差变量：实现值和目标值之间的差异。正偏差变量：实现值超过目标值的部分正偏差变量

5、：实现值超过目标值的部分,记为记为d 。负偏差变量：实现值未达到目标值的部分负偏差变量：实现值未达到目标值的部分,记为记为d。在一次决策中，实现值不可能既超过目标值又未达在一次决策中，实现值不可能既超过目标值又未达到目标值，故有到目标值，故有dd=0,并规定并规定d 0, d0如：如：8x1+10 x2+dd=56，其中，其中d： 利润不足利润不足56部分部分; d：利润超过利润超过56部分部分建立模型的有关概念建立模型的有关概念p绝对约束和目标约束绝对约束和目标约束绝对约束是指必须严格满足的等式或不等式约绝对约束是指必须严格满足的等式或不等式约束。如束。如LP中所有约束条件都是绝对约束，若不

6、中所有约束条件都是绝对约束，若不满足则无可行解。所以，绝对约束是硬约束。满足则无可行解。所以，绝对约束是硬约束。引入了目标值和正、负偏差变量后，对某一问引入了目标值和正、负偏差变量后，对某一问题有了新的限制，即目标约束。目标约束既可题有了新的限制，即目标约束。目标约束既可对原目标函数起作用，也可对原约束起作用。对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。目标约束是目标规划中特有的，是软约束。如：如：尽可能达到并超过利润计划指标尽可能达到并超过利润计划指标56元，元，8x1+10 x2+dd=56，即为软约束，即为软约束建立模型的有关概念建立模型的有关概念p优先

7、因子（优先等级）与优先权系数优先因子（优先等级）与优先权系数优先因子优先因子Pk 是将决策目标按其重要程度排序并是将决策目标按其重要程度排序并表示出来：表示出来：P1P2Pk。首先保证。首先保证P1级目级目标的实现，其次标的实现，其次P2，依此类推，依此类推优先权系数优先权系数i 区别具有相同优先因子的两个目区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。标的差别，决策者可视具体情况而定。建立模型的有关概念建立模型的有关概念p目标函数：由各自目标约束的正、负偏差变量和目标函数：由各自目标约束的正、负偏差变量和相应的优先因子及权系数构造而成，目的是相应的优先因子及权系数构造而成，目

8、的是使总使总偏差量为最小，记为偏差量为最小，记为minZ=f（d，d）。）。p有三种情况，但每个目标约束中只出现其中之一有三种情况，但每个目标约束中只出现其中之一要求恰好达到规定的目标值，即正、负偏差变量要尽要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则可能小，则minZ = f（d d）。）。如如8x1+10 x2+dd=56，若要求等于，若要求等于56，则，则 min dd即可即可要求不超过目标值，即允许达不到目标值，也就是正要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则偏差变量尽可能小，则minZ = f（d）。）。如如8x1+10 x2+dd=56，若要求

9、小于，若要求小于56，则，则 min d即可即可要求超过目标值，即超过量不限，但不低于目标值，要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则也就是负偏差变量尽可能小，则minZ = f（d）。）。如如8x1+10 x2+dd=56，若要求大于，若要求大于56，则，则 min d即可即可努力方向与努力方向与要求一致要求一致例例2 生产两种产品，具体数据如右表生产两种产品，具体数据如右表1. 希望产品希望产品产量不大于产品产量不大于产品的产量的产量2. 充分利用设备，不希望加班充分利用设备，不希望加班3. 尽可能达到并超过利润计划指标尽可能达到并超过利润计划指标56元元

10、拥有量原材料2111设备(台时)1210单件利润810X1 -X2 +d1- -d1+=0X1 +2X2 +d2- -d2+=108X1 +10X2 +d3- -d3+=56 2X1+X2 11 X1 , X2 , di- , di+ 0 di- . di+ =0d1- : X1产量不足产量不足X2 部分部分; d1+ : X1产量超过产量超过X2 部分部分d2- : 设备使用不足设备使用不足10 部分部分; d2+ :使用超过使用超过10 部分部分d3- : 利润不足利润不足56 部分部分; d3+ :利润超过利润超过56 部分部分绝对约束绝对约束解：解：设设X1 ，X2为产品为产品，产品，

11、产品产量。产量。Min Z =P1d1+P2(d2-+d2+)+P3d3-努力方向与努力方向与要求一致要求一致例例3 电视机厂装配黑白和彩色两种电视机，每台电视机需装备时间电视机厂装配黑白和彩色两种电视机，每台电视机需装备时间1小时，每周装配线计划开动小时，每周装配线计划开动40小时，预计每周彩电销售小时，预计每周彩电销售24台，每台，每台可获利台可获利80元，每周黑白电视机销售元，每周黑白电视机销售30台，每台可获利台，每台可获利40元。元。该厂目标：该厂目标：第第1级：级：充分利用装配线每周计划开动充分利用装配线每周计划开动40小时。小时。 第第2级：级：允许装配线加班，但每周尽量不超过允

12、许装配线加班，但每周尽量不超过10小时。小时。 第第3级：级：尽量满足市场需求。因彩电利润高，取其权系数为尽量满足市场需求。因彩电利润高，取其权系数为2。试建立该问题的试建立该问题的GP,并求解黑白和彩色电视机的产量并求解黑白和彩色电视机的产量.解：设解：设X1 , X2 分别表示分别表示彩色和彩色和黑白电视机产量，有黑白电视机产量，有Min Z=P1d1-+P2d2+P3(2d3-+d4-)X1+X2 +d1- -d1+=40X1 +X2+d2- -d2+=50X1+d3- -d3+=24X2 +d4- -d4+=30X1 , X2 , di- , di+ 0 (i=1,2,3,4)努力方向

13、与努力方向与要求一致要求一致本节内容提要本节内容提要p目标规划的数学模型目标规划的数学模型问题的提出问题的提出建立模型的有关概念建立模型的有关概念建模的一般步骤建模的一般步骤p解目标规划的图解法解目标规划的图解法p小结小结建模的一般步骤建模的一般步骤1、设定约束条件。、设定约束条件。(目标约束、绝对约束目标约束、绝对约束)2、写出目标函数，规定目标约束优先级。、写出目标函数，规定目标约束优先级。3 、建立模型。、建立模型。1111min() (1.2)( . ) (1.2)0 (j1.2n). 0 (1.2)KLkkllkllklnkjjllljnijjijjllZPddc xddqlLa x

14、bimxddlL 模型的一般形式模型的一般形式如何求解？如何求解？难点难点本节内容提要本节内容提要p目标规划的数学模型目标规划的数学模型问题的提出问题的提出建立模型的有关概念建立模型的有关概念建模的一般步骤建模的一般步骤p解目标规划的图解法解目标规划的图解法p小结小结解目标规划的图解法解目标规划的图解法p图解法只适用两个变量的目标规划问题。图解法只适用两个变量的目标规划问题。p图解法解题步骤如下：图解法解题步骤如下：1、确定各约束条件的可行域，即将所有约束条件（包括、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐目标约束和绝对约束，暂不考虑正负偏差

15、变量）在坐标平面上表示出来；标平面上表示出来；2、在目标约束所代表的边界线上，用箭头标出正、负偏、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；差变量值增大的方向；3、求满足最高优先等级目标的解；、求满足最高优先等级目标的解；4、转到下一个优先等级的目标，在不破坏所有较高优先、转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；等级目标的前提下，求出该优先等级目标的解；5、重复、重复4，直到所有优先等级的目标都已审查完毕；，直到所有优先等级的目标都已审查完毕；6、确定最优解和满意解。、确定最优解和满意解。01 2 3 4 5 6 7 8

16、1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上线段上的所有点均是该问题的解（无穷多最优解）。的所有点均是该问题的解（无穷多最优解）。例例4、用图解法求解目标规划问题、用图解法求解目标规划问题11122121112221212min()101262.5 210 2 8,0,0(12)llZP ddPdxxddxxddxxx xd dl，2d1、将所有约束条、将所有约束条件（目标约束暂不件（目标约束暂不考虑偏差变量）表考虑偏差变量）表示出来；示出来；2、在目标约束代、在目标约束代表的直线上，标出表的

17、直线上，标出偏差变量值增大的偏差变量值增大的方向；方向；3、求最高优先等、求最高优先等级目标的解；级目标的解；4、转到下一个优、转到下一个优先等级的目标，求先等级的目标，求出该等级目标的解；出该等级目标的解；5、重复、重复4，6、确定最优解和、确定最优解和满意解。满意解。练习：用图解法求解下列目标规划问题练习：用图解法求解下列目标规划问题1122233121112221233121 2min() 0 210810562 110,. 0 (1.2.3)jjZPdP ddPdxxddxxddxxddxxxddj1、将所有约束条、将所有约束条件（目标约束暂不件（目标约束暂不考虑偏差变量）表考虑偏差变

18、量）表示出来；示出来；2、在目标约束代、在目标约束代表的直线上，标出表的直线上，标出偏差变量值增大的偏差变量值增大的方向；方向；3、求最高优先等、求最高优先等级目标的解；级目标的解；4、转到下一个优、转到下一个优先等级的目标，求先等级的目标，求出该等级目标的解；出该等级目标的解；5、重复、重复4，6、确定最优解和、确定最优解和满意解。满意解。CD2d2d1d1d3d3d结论：有无穷多最优解。结论：有无穷多最优解。C（2，4）D（10/3，10/3）1122233121112221233121 2min() 0 210810562 110,. 0 (1.2.3)jjZPdP ddPdxxddxxddxxddxxxddj本节内容提要本节内容提要p目标规划的数学模型目标规划的数学模型问题的提出问题的提出建立模型的有关概念建立模型的有关概念建模的一般步骤建模的一般步骤p解目标规划的图解法解目标规划的图解法p小结小结小结小结pGP与与LP的比较的比较线性规划线性规划LP目标规划目标规划GP目标函数目标函数min , max系数可正负系数可正负min , 偏差变量偏差变量系数系数0变量变量xi, xs xa xi xs xa d约束条件约束条件系统约束系统约束（绝对约束）（绝对约束）目标约束目标约束系统约束系统约束解解最优最优最满意最满意LP讨