大学精品课件：第五章目标规划（第1-3节）.ppt

1、第第1页页第第2页页第第3页页为了具体说明目标规划与线性规划在处理问题方法为了具体说明目标规划与线性规划在处理问题方法上的区别，首先通过例子来介绍目标规划的概念及上的区别，首先通过例子来介绍目标规划的概念及数学模型。数学模型。第第4页页例例 某工厂生产某工厂生产 I、II 两种产品，已知有关数据如下两种产品，已知有关数据如下表所示。试求获利最大的生产方案。表所示。试求获利最大的生产方案。原材料（原材料（kg）设备（设备（h）利润（元利润（元/件）件）I218II1210拥有量拥有量1110第第5页页解：设解：设 x1、x2 分别表示产品分别表示产品 I、II 的产量，则建立的产量，则建立问题的

2、线性规划模型为：问题的线性规划模型为：0,102 11 2 .108 max21212121xxxxxxtsxxz用图解法求得最优决策方案为：用图解法求得最优决策方案为：x1=4，x2=3，z=62。第第6页页从线性规划的角度来看，问题已经得到了圆满解决。从线性规划的角度来看，问题已经得到了圆满解决。但从工厂领导进行决策的立场上，问题没有这么简单，但从工厂领导进行决策的立场上，问题没有这么简单，决策时还需要考虑一系列其他问题：决策时还需要考虑一系列其他问题：1、计划问题要满足多方面的要求：、计划问题要满足多方面的要求：（1）财务部门希望利润尽可能大；）财务部门希望利润尽可能大；（2）物资部门希

3、望原材料消耗尽可能小；）物资部门希望原材料消耗尽可能小；第第7页页（3）销售部门希望产品品种尽可能多；）销售部门希望产品品种尽可能多；（4）计划部门希望有尽可能大的批量，以便于安排）计划部门希望有尽可能大的批量，以便于安排生产。生产。由此可知：计划问题实际上一个多目标决策问题。由此可知：计划问题实际上一个多目标决策问题。由于需要用线性规划来处理，所以计划人员不得不从由于需要用线性规划来处理，所以计划人员不得不从众多目标要求中硬性地选择其一，作为线性规划的目众多目标要求中硬性地选择其一，作为线性规划的目标函数。标函数。第第8页页但这种做法的后果就是：但这种做法的后果就是：严重违背了某些部门的愿望

4、，因而使得生产计划的严重违背了某些部门的愿望，因而使得生产计划的实施受到影响。实施受到影响。一开始由于多方面矛盾而无法从多个目标中选出一一开始由于多方面矛盾而无法从多个目标中选出一个目标来。个目标来。第第9页页2、线性规划有最优解的必要条件是其可行解集非空，、线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容，而实际问题有时不能满足这即各约束条件彼此相容，而实际问题有时不能满足这样的要求：样的要求：生产计划中，由于资金限制，原材料最大供应量不能生产计划中，由于资金限制，原材料最大供应量不能满足计划产量时，从供给和需求两方面产生的约束条满足计划产量时，从供给和需求两方面产生的约束条

5、件就是彼此不相容的；件就是彼此不相容的；第第10页页3、实际问题中，决策者在作决策时，往往会对由数、实际问题中，决策者在作决策时，往往会对由数学模型求出的问题的解作某种调整和修改。学模型求出的问题的解作某种调整和修改。问题的数学模型并不能完全表述实际问题的所有内涵，问题的数学模型并不能完全表述实际问题的所有内涵，它们之间只是存在一定的近似性。它们之间只是存在一定的近似性。因此由数学模型求出的问题的解决方案，必须作出调因此由数学模型求出的问题的解决方案，必须作出调整和修改才能用来解决实际问题。整和修改才能用来解决实际问题。第第11页页上述分析表明：上述分析表明：同任何其他决策工具一样，线性规划并

6、不是完美无缺同任何其他决策工具一样，线性规划并不是完美无缺的，在处理实际问题时，线性规划存在着由其的，在处理实际问题时，线性规划存在着由其“刚性刚性”本质所注定的某些固有的局限性。本质所注定的某些固有的局限性。第第12页页现代决策强调现代决策强调定量分析定量分析和和定性分析定性分析的结合，强调的结合，强调硬技硬技术术和和软技术软技术的结合，强调的结合，强调矛盾矛盾和和冲突冲突的合理性，强调的合理性，强调妥协妥协和和让步让步的必要性，线性规划无法胜任这些要求。的必要性，线性规划无法胜任这些要求。第第13页页1961年，查恩斯（年，查恩斯（A.Charnes）和库柏（）和库柏（W.W.Cooper

7、）提出目标规划（）提出目标规划（goal programming），得），得到广泛重视和较快发展。到广泛重视和较快发展。第第14页页目标规划在处理实际决策问题时：目标规划在处理实际决策问题时：承认各项决策要求（即使是冲突的）的存在有其承认各项决策要求（即使是冲突的）的存在有其合理性；合理性；在作最终决策时，不强调其绝对意义上的最优性。在作最终决策时，不强调其绝对意义上的最优性。第第15页页由于目标规划一定程度上弥补了线性规划的上述局由于目标规划一定程度上弥补了线性规划的上述局限性，因此，目标规划被认为是一种限性，因此，目标规划被认为是一种较之线性规划较之线性规划更接近于实际决策过程的决策工具更

8、接近于实际决策过程的决策工具。第第16页页例例 某工厂生产某工厂生产 I、II 两种产品，已知有关数据如下两种产品，已知有关数据如下表所示。试求生产方案。表所示。试求生产方案。原材料（原材料（kg）设备（设备（h）利润（元利润（元/件）件）I218II1210拥有量拥有量1110第第17页页假设要求决策人员制定生产方案时考虑如下意见：假设要求决策人员制定生产方案时考虑如下意见：1、由于产品、由于产品 I 销售疲软，故希望产品销售疲软，故希望产品 I 的产量不超的产量不超过产品过产品 II 的产量；的产量；2、原材料严重短缺，生产中应避免过量消耗；、原材料严重短缺，生产中应避免过量消耗；3、尽可

9、能充分利用设备台时；、尽可能充分利用设备台时；4、计划利润可能达到并超过、计划利润可能达到并超过 56 元。元。第第18页页面对这些意见，决策人员需要会同有关各方作进一面对这些意见，决策人员需要会同有关各方作进一步的协调，最后达成一致意见：步的协调，最后达成一致意见：1、原材料使用限额不得突破；、原材料使用限额不得突破；2、产品、产品 I 产量要求必须优先考虑；产量要求必须优先考虑；3、设备工时问题其次考虑；、设备工时问题其次考虑；4、最后考虑利润要求。、最后考虑利润要求。第第19页页类似上述这样存在多个目标的多目标决策问题，称类似上述这样存在多个目标的多目标决策问题，称为目标规划问题。为目标

10、规划问题。第第20页页1.偏差变量偏差变量正偏差变量：表示决策值超过目标值的部分，记为正偏差变量：表示决策值超过目标值的部分，记为 d+；负偏差变量：表示决策值未达到目标值的部分，记为负偏差变量：表示决策值未达到目标值的部分，记为d-。第第21页页因为决策值不可能既超过目标值，同时又未达到目因为决策值不可能既超过目标值，同时又未达到目标值，所以标值，所以 d+和和 d-存在如下关系：存在如下关系：（1）d+0，d-=0（决策值超过目标值）（决策值超过目标值）（2）d-0，d+=0（决策值未达到目标值）（决策值未达到目标值）（3）d+d-=0（决策值等于目标值）（决策值等于目标值）第第22页页2

11、.绝对约束和目标约束绝对约束和目标约束（1）绝对约束：必须严格满足的约束条件。）绝对约束：必须严格满足的约束条件。绝对约束是硬约束，不能满足这些约束条件的解为绝对约束是硬约束，不能满足这些约束条件的解为非可行解。非可行解。如：线性规划问题中的所有约束条件。如：线性规划问题中的所有约束条件。第第23页页（2）目标约束：目标约束是目标规划特有的。）目标约束：目标约束是目标规划特有的。目标约束是软约束，在达到此目标值时允许发生正目标约束是软约束，在达到此目标值时允许发生正偏差或负偏差，因此在这些约束的左端要加入正偏偏差或负偏差，因此在这些约束的左端要加入正偏差、负偏差变量；其约束右端项是要追求的目标

12、值。差、负偏差变量；其约束右端项是要追求的目标值。第第24页页3.优先因子和权系数优先因子和权系数一个规划问题常常有若干个目标，决策者要求达到一个规划问题常常有若干个目标，决策者要求达到这些目标时，有主次或轻重缓急的不同。这些目标时，有主次或轻重缓急的不同。这种不同目标的主次轻重差别有两种：这种不同目标的主次轻重差别有两种：绝对的差别：优先因子区别绝对的差别：优先因子区别相对的差别：权系数区别相对的差别：权系数区别第第25页页（1）优先因子）优先因子优先因子用优先因子用 Pk 来表示。来表示。只有在高级优先因子对应的目标已满足的基础上，只有在高级优先因子对应的目标已满足的基础上，才能考虑低级优

13、先因子对应的目标；才能考虑低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝对不允许违在考虑低级优先因子对应的目标时，绝对不允许违背已经满足的高级优先因子对应的目标。背已经满足的高级优先因子对应的目标。第第26页页优先因子间的关系为：优先因子间的关系为：Pk Pk+1Pk 对应的目标比对应的目标比 Pk+1 对应的目标具有绝对的优先性。对应的目标具有绝对的优先性。注意：目标规划问题中，通常把绝对约束作为最高注意：目标规划问题中，通常把绝对约束作为最高优先级来考虑。优先级来考虑。第第27页页（2）权系数）权系数权系数用权系数用 j 来表示。来表示。多个目标具有相同的优先因子时，它们的重要

14、性可多个目标具有相同的优先因子时，它们的重要性可用权系数的不同来表示。用权系数的不同来表示。权系数的确定由决策者按具体情况而定。权系数的确定由决策者按具体情况而定。第第28页页4.目标规划的目标函数目标规划的目标函数目标规划的目标函数又称为目标规划的目标函数又称为准则函数准则函数或或达成函数达成函数。目标规划的目标函数由各目标约束的偏差变量、各目标规划的目标函数由各目标约束的偏差变量、各目标约束相应的优先因子、各目标约束相应的权系目标约束相应的优先因子、各目标约束相应的权系数共同构成。数共同构成。第第29页页当每一目标值确定后，决策者要求尽可能缩小偏离当每一目标值确定后，决策者要求尽可能缩小偏

15、离目标值，所以目标规划的目标函数只能是极小化，目标值，所以目标规划的目标函数只能是极小化，其基本形式有三种：其基本形式有三种：第第30页页（1）要求恰好达到目标值。）要求恰好达到目标值。这时，决策值超过目标值或不足目标值都是不希望这时，决策值超过目标值或不足目标值都是不希望的，即正、负偏差变量都要尽可能地小：的，即正、负偏差变量都要尽可能地小：)(min ddfz第第31页页（2）要求不超过目标值。）要求不超过目标值。这时，允许达不到目标值，但不希望超过目标值，这时，允许达不到目标值，但不希望超过目标值，即正偏差变量要尽可能地小：即正偏差变量要尽可能地小：)(min dfz第第32页页（3）要

16、求不低于目标值。）要求不低于目标值。这时，允许超过目标值，但不希望低于目标值，即这时，允许超过目标值，但不希望低于目标值，即负偏差变量要尽可能地小：负偏差变量要尽可能地小：)(min dfz第第33页页除上述三种基本表达式外，目标规划的目标函数还除上述三种基本表达式外，目标规划的目标函数还可以有其他表达式，如可以有其他表达式，如)(min ddfz)(min ddfz但这些形式的目标函数很少使用。但这些形式的目标函数很少使用。第第34页页目标排序如下：目标排序如下：1.原材料严重短缺，生产中应避免过量消耗；原材料严重短缺，生产中应避免过量消耗；2.由于产品由于产品 I 销售疲软，故希望产品销售

17、疲软，故希望产品 I 的产量的产量不超不超过过产品产品 II 的产量；的产量；3.尽可能尽可能充分利用充分利用设备台时；设备台时；4.计划利润可能计划利润可能达到并超过达到并超过 56 元。元。第第35页页1.原材料严重短缺，生产中应避免过量消耗；原材料严重短缺，生产中应避免过量消耗；11221 xx第第36页页2.由于产品由于产品 I 销售疲软，故希望产品销售疲软，故希望产品 I 的产量的产量不超不超过过产品产品 II 的产量；的产量；11210ddxx 11mindPz第第37页页00,02111 xxdd：超过目标超过目标00,02111 xxdd：未达到目标未达到目标第第38页页011

18、21 ddxx 11mindPz第第39页页3、尽可能、尽可能充分利用充分利用设备台时；设备台时；222110ddxx)(min222 ddPz第第40页页100,02122 xxdd：超过目标超过目标100,02122 xxdd：未达到目标未达到目标第第41页页1022221 ddxx)(min222 ddPz第第42页页4.计划利润可能计划利润可能达到并超过达到并超过 56 元。元。332156108ddxx 33mindPz第第43页页560,02133 xxdd：超过目标超过目标560,02133 xxdd：未达到目标未达到目标第第44页页561083321 ddxx 33mindPz

19、第第45页页从而建立问题的模型如下：从而建立问题的模型如下：3,2,1,0,5610810 2 0 11 2 .)(min21332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPzii第第46页页模型亦可表述为：模型亦可表述为：3,2,1,0,5610810 2 0 11 2 .),(,min21332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPii第第47页页目标规划的一般数学模型为：目标规划的一般数学模型为：KkddxbxaKkgddxctsddPzkkjinjjijknjkkjkjKkklkkl

20、kLll,.,1,0,0),(,.,1,.)(min1111 第第48页页 KkddxbxaKkgddxctsLlddPkkjinjjijknjkkjkjKkklkklkl,.,1,0,0),(,.,1,.,.2,1,)(min111 模型亦可表述为：模型亦可表述为：第第49页页对于具有两个决策变量的目标规划的数学模型，可对于具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。以用图解法来分析求解。1.在平面直角坐标系内画出由在平面直角坐标系内画出由绝对约束绝对约束和和非负条件非负条件所组成的公共取值范围。所组成的公共取值范围。第第50页页2.按优先因子的高低，依次在平面直角坐标系内

21、画按优先因子的高低，依次在平面直角坐标系内画出出目标约束目标约束所组成的公共取值范围：所组成的公共取值范围：（1）令正负偏差变量等于）令正负偏差变量等于0，画出相应直线；，画出相应直线；（2）在直线旁标出正、负偏差变量所示方向。）在直线旁标出正、负偏差变量所示方向。（3）正负偏差变量表示直线可以沿正、负偏差变量）正负偏差变量表示直线可以沿正、负偏差变量所示方向平移。所示方向平移。3.根据目标函数中的优先因子来分析求解。根据目标函数中的优先因子来分析求解。第第51页页 3,2,1,0,56108102 0 11 2 .)(min21332122211121213322211iddxxddxxdd

22、xxddxxxxtsdPddPdPzii第第52页页解：解：x2x11.画出绝对约束和非负条件所围成的取值范围。画出绝对约束和非负条件所围成的取值范围。O11221 xxAB第第53页页2.画出目标约束所围成的取值范围。画出目标约束所围成的取值范围。01121 ddxx 1112ddxxx2 轴上的截距轴上的截距第第54页页x2x1O 1d 1dBAC第第55页页1022221 ddxx 22122121521ddxxx2 轴上的截距轴上的截距第第56页页x2x1O 1d 1d 2d 2dABECD第第57页页561083321 ddxx 331210110152854ddxxx2 轴上的截距

23、轴上的截距第第58页页x2x1O 1d 1d 2d 2d 3d 3dBACEDFGJ第第59页页3.根据目标函数中的优先因子来分析求解。根据目标函数中的优先因子来分析求解。11mindPz表示直线表示直线 左上角的部分，左上角的部分，此时满足此时满足021 xx从而公共取值范围为：从而公共取值范围为：OBC（1）01 d第第60页页x2x1O 1d 1d 2d 2d 3d 3dBACEDFGJ第第61页页)(min222 ddPz表示直线表示直线 上的部分，上的部分，此时满足此时满足10221 xx从而公共取值范围为：线段从而公共取值范围为：线段 E D（2）022 dd第第62页页x2x1O

24、 1d 1d 2d 2d 3d 3dBACEDFGJ第第63页页 33mindPz（3）表示直线表示直线 的右上角部分，的右上角部分，此时满足此时满足5610821 xx从而公共取值范围为：线段从而公共取值范围为：线段 G D03 d第第64页页x2x1O 1d 1d 2d 2d 3d 3dBACEDFGJ第第65页页可求得：可求得：G 的坐标为的坐标为：（：（2，4）D 的坐标为的坐标为：（：（10/3，10/3）G 和和 D 的凸组合均是目标规划问题的解。的凸组合均是目标规划问题的解。第第66页页在本例中，依次先后次序满足了：在本例中，依次先后次序满足了：03 d01 d022 dd因而因

25、而 z*=0，问题的最终解是最优解。，问题的最终解是最优解。但在大多数问题中并非如此，会出现某些约束得但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为不到满足，故将目标规划问题的最优解称为满意满意解解。第第67页页例：某电视机厂装配黑白和彩色两种电视机。例：某电视机厂装配黑白和彩色两种电视机。每周市场的黑白电视机销量为每周市场的黑白电视机销量为 30 台，每台可获利台，每台可获利 40元；元；每周市场的彩色电视机销量为每周市场的彩色电视机销量为 24 台，每台可获利台，每台可获利 80元。元。每装配一台电视机需占用装配线每装配一台电视机需占用装配线 1 小时，装

26、配线每小时，装配线每周计划开动周计划开动 40 小时。小时。第第68页页该厂确定的目标为：该厂确定的目标为：第一优先级：装配线每周计划开动时间第一优先级：装配线每周计划开动时间不少于不少于 40 小时；小时；第二优先级：允许装配线加班，但加班时间每周尽第二优先级：允许装配线加班，但加班时间每周尽量量不超过不超过 10 小时；小时；第三优先级：装配电视机数量第三优先级：装配电视机数量不少于不少于市场需求量。市场需求量。因彩色电视机利润高，取其权系数为因彩色电视机利润高，取其权系数为 2。建立问题模型，并求解黑白和彩色电机机产量？建立问题模型，并求解黑白和彩色电机机产量？第第69页页1.装配线每周

27、计划开动时间装配线每周计划开动时间不少于不少于 40 小时：小时：401121 ddxx 11mindPz解：解：设设 x1、x2 分别表示彩色和黑白电视机产量。分别表示彩色和黑白电视机产量。第第70页页2.允许装配线加班，但加班时间每周尽量允许装配线加班，但加班时间每周尽量不超过不超过 10 小时：小时：502221 ddxx 22mindPz第第71页页3.装配彩色电视机数量装配彩色电视机数量不少于不少于市场需求量，且权市场需求量，且权系数为系数为 2：24331 ddx)2(min33 dPz第第72页页 43mindPz4.装配黑白电视机数量装配黑白电视机数量不少于不少于市场需求量，且

28、权市场需求量，且权系数为系数为 1：30442 ddx第第73页页从而建立问题的模型如下：从而建立问题的模型如下：4,3,2,1,0,30 24 5040 .)2(min21442331222111214332211iddxxddxddxddxxddxxtsddPdPdPzii第第74页页 1d 1dx2x1 2d 2dABCDO5040 min222111212211 ddxxddxxdPdPz第第75页页 1d 1dx2x1 2d 2dABCDO24)2(min33133 ddxdPz 3d 3dEF第第76页页 1d 1dx2x1 2d 2dABCDO 4d 4d 3d 3dGHEF30)(min44243 ddxdPz第第77页页在在 ABEF 中无法满足：中无法满足：04 d所以只能在所以只能在 ABEF 中取一点，使中取一点，使 尽可能小。尽可能小。4d在在 ABEF 中只有取中只有取 E 点才可使点才可使 最小。最小。4d故故 E 点为为满意解，点为为满意解，E=（24，26）。）。第第78页页 1d 1dx2x1 2d 2dABCDO 4d 4d 3d 3dGHEF第第79页页分析：分析：此例中约束此例中约束)(min43 dPz没有得到满足。没有得到满足。问题的最终解只是满意解而不是最优解。问题的最终解只是满意解而不是最优解。30442 ddx