运筹学：第四章目标规划新

1、Chapter4 目标规划(Goal Programming )目标规划问题及其数学模型目标规划问题及其数学模型目标规划的图解法目标规划的图解法目标规划的单纯形法目标规划的单纯形法目标规划应用举例目标规划应用举例4.1 目标规划问题及其数学模型目标规划问题及其数学模型目标规划的产生：目标规划的产生： 线性规划的局限性线性规划的局限性 目标单一性，不能处理多目标单一性，不能处理多目标问题；硬约束目标问题；硬约束。 但现在很多问题都有但现在很多问题都有多个目标多个目标，希望能获得，希望能获得综合的综合的最优最优，但目标之间往往存在一定的矛盾，如利润最高、，但目标之间往往存在一定的矛盾，如利润最高、

2、成本最低、产量高、质量好、用工最少等。传统的线成本最低、产量高、质量好、用工最少等。传统的线性规划很难同时处理？对于这种多目标的问题，性规划很难同时处理？对于这种多目标的问题，如何如何解决？解决？一、基本概念一、基本概念例例1 某企业生产某种产品的生产方式有四种：某企业生产某种产品的生产方式有四种：正常生产、正常生产、加班生产、转包合同和雇临时工加班生产、转包合同和雇临时工生产。有关数据如下表所生产。有关数据如下表所示。示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤（每件产品耗原料公斤（每件产品耗原料2公斤），产品需求量为公斤），

3、产品需求量为800件。件。 要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（1）满足需要量；（）满足需要量；（2）质量水平达到）质量水平达到98%；（；（3）7000元的工时成本元的工时成本。正常生产正常生产加班生产加班生产转包合同转包合同临时工临时工所需工时所需工时/件件222.53成本费用元成本费用元/工时工时101588质量水平质量水平99%98%95%90%目标规划的引出目标规划的引出生产条件生产条件约束约束: 欲达到的目标：欲达到的目标： 总工时限制：总工时限制：2000个；个；原材料限制：原材料限制：2500kg。1. 满足需求满足需

4、求 800件；件；2. 达到质量水平合格率达到质量水平合格率98%；3. 工时成本工时成本7000元。元。1）分）分 析析例例 某企业生产某种产品的生产方式有四某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用在未来的一计划期内，可利用总工时总工时为为20002000，原材料，原材料25002500公斤公斤（每件产品耗原（每件产品耗原料料2 2公斤），公斤），产品需求量为产品需求量为800800件。件。 要求制订一生产计划，使其尽可能达要求制订一生产

5、计划，使其尽可能达到以下到以下三项指标三项指标：（1 1）满足需要量；（）满足需要量；（2 2）质量水平达到质量水平达到98%98%；（；（3 3）70007000元的工时成元的工时成本。本。2）组建约束）组建约束确定决策变量确定决策变量：假设正常生产、加班生产、转包合同：假设正常生产、加班生产、转包合同和雇临时工生产的量分别为和雇临时工生产的量分别为x1，x2，x3和和x4。确定约束确定约束：工时限制：工时限制： 2x1 + 2x2 + 2.5x3 +3x4 2000；原材料限制：原材料限制： 2（x1 + x2 + x3 +x4 ）2500；非负限制：非负限制： xi 0（i=1，2，3，

6、4）正常生产正常生产加班生产加班生产转包合同转包合同临时工临时工所需工时所需工时/件件222.53成本费用元成本费用元/工时工时101588质量水平质量水平99%98%95%90%需要达到的目标需要达到的目标：（1）满足需求量）满足需求量800件；（件；（2）产品质量水平）产品质量水平98%；（；（3）工时成本）工时成本7000元。元。3）分析目标需求）分析目标需求 三个目标要求，如何得到集中体现？三个目标要求，如何得到集中体现？ 是否需要建立三个目标函数？是否需要建立三个目标函数？ 传统线性规划一般只建立一个目标函数，而有传统线性规划一般只建立一个目标函数，而有多个约束。多个约束。是否可以将

7、三个目标以约束的形是否可以将三个目标以约束的形式表现出来，这样可解决多目标的问题？式表现出来，这样可解决多目标的问题？3）目标需求分析与目标向约束的转化）目标需求分析与目标向约束的转化需要达到的目标需要达到的目标：实际也变成了约束情况实际也变成了约束情况（1）满足需求量）满足需求量800件件：在实际生产中，可能：在实际生产中，可能会出现两种情况会出现两种情况，生，生产量产量不够不够800件或超过件或超过800件，则会产生件，则会产生不同的情况不同的情况：0.98（x1 + x2 + x3 +x4 ）800；或或0.98（x1 + x2 + x3 +x4 ）800；（2）产品质量水平）产品质量水

8、平98%：出现两种可能：出现两种可能99%x1 + 98%x2 + 95%x3 +90%x4 98% （x1 + x2 + x3 +x4 ） ；或或 99%x1 + 98%x2 + 95%x3 +90%x4 98% （x1 + x2 + x3 +x4 ） ； （3）工时成本）工时成本7000元元：可能出现两种可能：可能出现两种可能：20 x1 + 30 x2 + 20 x3 +24x4 7000；或或20 x1 + 30 x2 + 20 x3 +24x4 7000。（1）满足需求量）满足需求量800件：件：两种情况不可能同时出现两种情况不可能同时出现，化为标准型约束。，化为标准型约束。0.98

9、（x1 + x2 + x3 +x4 ）800； 0.98（x1 + x2 + x3 +x4 ）+S1=8000.98（x1 + x2 + x3 +x4 ）800800； 0.98（x1 + x2 + x3 +x4 ）-S2=800（松弛变量（松弛变量S1和剩余变量和剩余变量S2中只可能出现一个）中只可能出现一个）（2）产品质量水平）产品质量水平98%：99%x1 + 98%x2 + 95%x3 +90%x4 98%（ x1 + x2 + x3 +x4） ； 99%x1 + 98%x2 + 95%x3 +90%x4 +S3=98% （ x1 + x2 + x3 +x4） 99%x1 + 98%x

10、2 + 95%x3 +90%x4 98% （ x1 + x2 + x3 +x4） ； 99%x1 + 98%x2 + 95%x3 +90%x4 S4 =98% （ x1 + x2 + x3 +x4） （S3和和S4中只可能出现一个）中只可能出现一个）（3）工时成本）工时成本7000元：元：20 x1 + 30 x2 + 20 x3 +24x4 7000； 20 x1 + 30 x2 + 20 x3 +24x4 +S5=700020 x1 + 30 x2 + 20 x3 +24x4 7000。 20 x1 + 30 x2 + 20 x3 +24x4 S6=7000（S5和和S6中只可能出现一个）

11、中只可能出现一个）如何综合考虑目标要求中可能会出现的两种情况？如何综合考虑目标要求中可能会出现的两种情况？（1）满足需求量）满足需求量800件：归一化处理件：归一化处理0.98（x1 + x2 + x3 +x4 ）+ S1-S2 =800（S1和和S2中只可能出现一中只可能出现一个，即其中至少有一个为零）个，即其中至少有一个为零）（2）产品质量水平）产品质量水平98%：99%x1 + 98%x2 + 95%x3 +90%x4 +S3 S4 =98% （x1 + x2 + x3 +x4 ） （S3和和S4中只可能出现一个，至少有一个为零）中只可能出现一个，至少有一个为零）（3）工时成本）工时成本

12、7000元：元： 20 x1 + 30 x2 + 20 x3 +24x4 +S5 S6 =7000（S5和和S6中只可能出现中只可能出现一个，至少有一个为零）一个，至少有一个为零）如何综合考虑目标要求中可能会出现的两种情况？如何综合考虑目标要求中可能会出现的两种情况？这里就在目标中引入了这里就在目标中引入了偏差量偏差量的概念，使多个目的概念，使多个目标要求转变成了约束标要求转变成了约束目标约束目标约束。S奇奇松弛变量，称为负松弛变量，称为负偏差量（偏差量（0）S偶偶剩余变量，称为正剩余变量，称为正偏差量（偏差量（0）目标要求转换成约束后的情形目标要求转换成约束后的情形（1）满足需求量）满足需求

13、量800件：归一化处理件：归一化处理（2）产品质量水平）产品质量水平98%（3）工时成本）工时成本7000元元 0.98（x1 + x2 + x3 +x4 ）+ S1-S2 =800 99%x1 + 98%x2 + 95%x3 +90%x4 +S3 S4 =98% （x1 + x2 + x3 +x4 ） 20 x1 + 30 x2 + 20 x3 +24x4 +S5 S6 =7000 0.98（x1 + x2 + x3 +x4 ）+ d1- - d1+ =800 1%x1 -3%x3 -8%x4 +d2- d2+ =0 20 x1 + 30 x2 + 20 x3 +24x4 +d3- d3+

14、=7000di-，负偏差量，负偏差量di+，正偏差量，正偏差量目目标标约约束束4）相关概念引入）相关概念引入 d+：正偏差量，可能实现值：正偏差量，可能实现值高于高于目标指标值的部分；目标指标值的部分； d-：负偏差量，可能实现值：负偏差量，可能实现值低于低于目标指标值的部分。目标指标值的部分。实现目标的三种情况：实现目标的三种情况：（1） 超过目标值超过目标值 k 0 ，k- 0（2） 达不到目标值达不到目标值 k =0，k- 0（3） 刚好达到目标值刚好达到目标值 k =0，k- 0 ( d+ * d0 ) 正、负偏差变量正、负偏差变量 目标值目标值d1-d1+实际值实际值实际值实际值当实

15、际值同目标值恰好一致时，正负偏差同为当实际值同目标值恰好一致时，正负偏差同为0d1- d1+ =0d1- 0， d1+ 0,正负偏差两者中必有一个为正负偏差两者中必有一个为0正偏差变量正偏差变量负偏差变量负偏差变量 目标规划的约束形式目标规划的约束形式 （1）绝对约束）绝对约束：也叫：也叫客观条件约束客观条件约束，为必须严，为必须严格满足的约束。格满足的约束。（2）目标约束）目标约束：目标规划特有的约束，也叫：目标规划特有的约束，也叫软约软约束束。（3）非负约束）非负约束：要求所有决策变量和偏差量均：要求所有决策变量和偏差量均0。如例如例1中的目标约束为：中的目标约束为： (1)满足需求满足需

16、求 800件；件； (2)达到质量水平合格率达到质量水平合格率98%； (3)工时成本工时成本7000元；元； 1234110.98)800 xxxxdd（134220.010.030.080 xxxdd123433203020247000 xxxxdd (4) 绝对约束绝对约束 （5）非负约束非负约束:1234222.532000 xxxx12342()2500 xxxx) 3, 2, 1, 4, 3, 2, 1(0,xkjddkkj5）如何确定最终的目标方程？）如何确定最终的目标方程？ 设想：设想：希望能希望能尽量同时满足三个目标需求尽量同时满足三个目标需求，即，即刚好刚好达达到到800件

17、产量，质量合格率件产量，质量合格率刚好刚好为为98%，工时成本，工时成本刚好刚好为为7000元。此时，元。此时，所有的正偏差和负偏差量应均为所有的正偏差和负偏差量应均为0。但是，实际情况下，正偏差或负偏差量但是，实际情况下，正偏差或负偏差量很难同时为很难同时为0，即实际中即实际中。 但是，应该但是，应该，则需，则需实际可能值应尽实际可能值应尽可能与目标要求值靠近可能与目标要求值靠近，即使得，即使得所有目标约束的偏差量所有目标约束的偏差量最小最小。由此，可建立新的目标函数：。由此，可建立新的目标函数： 112233min,dddddd 原有目标变成了约束（目标约束），原有目标变成了约束（目标约束

18、），如何寻找如何寻找新的目标方程？新的目标方程？1122331234111342212343312341234min,0.980.980.980.988000.010.030.0801015887000222.53200022222500,目标约束系统约束非负约束jkkddddddxxxxddxxxddxxxxddxxxxxxxxx dd 0(1,2,3,4,1,2,3)jk例例1的数学模型的数学模型例例1 1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。雇临时工生产。有关

19、数据如下表所示。 在未来的一计划期内，可利用在未来的一计划期内，可利用总工时为总工时为20002000，原材料，原材料25002500公斤公斤（每件产品耗（每件产品耗原料原料2 2公斤），公斤），产品需求量为产品需求量为800800件。件。 要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（1 1）满足需要量；）满足需要量；（2 2）质量水平达到）质量水平达到98%98%；（；（3 3）70007000元的工时成本。元的工时成本。6）目标规划的特点）目标规划的特点 约束一般包括约束一般包括目标约束、系统约束和非目标约束、系统约束和非负约束负约束三部

20、分；三部分； 目标函数转换成求目标函数转换成求多个期望目标值的偏多个期望目标值的偏差量和的最小差量和的最小； 目标及约束仍然为目标及约束仍然为线性线性。 目标规划所得的是满意方案。目标规划所得的是满意方案。 问题问题A、目标要求中，是否都需要同时满足？即实际、目标要求中，是否都需要同时满足？即实际中可能会出现需要某种情况越大越好（如利润），中可能会出现需要某种情况越大越好（如利润），即在原有基本目标值的基础上偏离越大越好，也可即在原有基本目标值的基础上偏离越大越好，也可能需要出现在原基本目标值的基础上越小越好（如能需要出现在原基本目标值的基础上越小越好（如成本）。成本）。 这样的情况如何在目标

21、函数中得到体现？这样的情况如何在目标函数中得到体现？7）由例）由例1引发的思考与相关讨论引发的思考与相关讨论例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。 要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标

22、三项指标：（：（1）满足需要量满足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的的工时成本工时成本。7）由例）由例1引发的思考与相关讨论引发的思考与相关讨论例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。 要

23、求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（：（1）满足需要量满足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的的工时成本工时成本。 并且优先满足（并且优先满足（2）、其次为（）、其次为（3），最后为（），最后为（1）。）。问题问题B：目标要求有目标要求有轻重缓急轻重缓急的情况，这种情况的情况，这种情况如如何在目标函数中体现何在目标函数中体现？比如，要求必须优先保证产？比如，要求必须优先保证产品质量，然后是控制成本，最后是达到产量要求？品质量，然后是控制成本，最后是达到产量要求？优先量必须优先考虑，那优先量必须

24、优先考虑，那如何率先满足优先目标如何率先满足优先目标？问题问题B、目标有轻重缓急的情况，这种情况如何目标有轻重缓急的情况，这种情况如何在目标函数中体现在目标函数中体现？比如，要求必须优先保证产？比如，要求必须优先保证产品质量，然后是控制成本，最后是达到产量要求？品质量，然后是控制成本，最后是达到产量要求？优先量必须优先考虑，那如何率先满足优先目优先量必须优先考虑，那如何率先满足优先目标标？采用采用优先权优先权来区分目标的来区分目标的优先级别优先级别，并将，并将其在目标函数中作为相应偏差量的其在目标函数中作为相应偏差量的目标系目标系数数。同时，根据优先级别不一样，应将目。同时，根据优先级别不一样

25、，应将目标系数拉开。标系数拉开。越优先，代表目标函数中越优先，代表目标函数中最先接近于最先接近于0，则目标系，则目标系数应越大。数应越大。 优先因子与权系数优先因子与权系数 用于区分各目标的主次或轻重缓急的不同，第用于区分各目标的主次或轻重缓急的不同，第一优先的目标赋予一优先的目标赋予 p1 ，次优先的为，次优先的为p2 且且 pk pk+同一优先级别内的区别用权系数同一优先级别内的区别用权系数 wj表示差异。表示差异。Min p1(d2+d2- ), p2(d3+d3- ), p3(d1+d1- ) 例例1中，如果要求首先满足质量，然后是中，如果要求首先满足质量，然后是成本，最后是需求，则可

26、建立：成本，最后是需求，则可建立：（1）对于）对于利润型目标利润型目标，要求是可能实现值超过目标值越多越好，要求是可能实现值超过目标值越多越好，即即d+越大越好（不希望低于目标值）越大越好（不希望低于目标值），则在目标函数中，则在目标函数中，对对d-求最求最小小；（2）对于）对于成本型目标成本型目标，要求可能实现值低于目标值越多越好，即，要求可能实现值低于目标值越多越好，即d-越大越好越大越好(不希望超过目标值）不希望超过目标值），则在目标函数中，则在目标函数中对对d-+求最小求最小；（3）对）对于合同型目标，要求跟目标保持一致，不超过也不短缺，于合同型目标，要求跟目标保持一致，不超过也不短缺

27、，即要求即要求d+和和d-都最小都最小，则在目标函数中应将，则在目标函数中应将两者综合考虑两者综合考虑。分成三种目标形式分成三种目标形式 要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（1）满足需要量）满足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的工时成本的工时成本。合同型目标合同型目标利润型目标利润型目标成本型目标成本型目标(1) 恰好达到目标（恰好达到目标（合同型目标合同型目标）：）： min Z= p(d k-+dk+)(2) 超过目标（超过目标（利润型目标利润型目标）：）： min Z= p (dk

28、-) (3) 不超过目标（不超过目标（成本型目标成本型目标）：）： min Z= p (dk+) 目标函数的处理目标函数的处理例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。 要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可

29、能达到以下三项指标三项指标：（：（1）满足需要量满足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的的工时成本工时成本。 并且优先满足（并且优先满足（2）、其次为（）、其次为（3），最后为（），最后为（1）。）。min d 1-+d1+ , d 2-+d2+ , d 3-+d3+1223311min,()p dp dp dd最终目标函数最终目标函数建模方法建模方法：(1) 设定约束条件设定约束条件 (构建构建目标约束、绝对约束目标约束、绝对约束和非负约束和非负约束)；(2) 规定目标约束规定目标约束优先级优先级；(3) 根据目标所属的类型，建立新的目标函根据目标

30、所属的类型，建立新的目标函数，完成模型的建立。数，完成模型的建立。 二、二、 目标规划的一般数学模型目标规划的一般数学模型一般模型：一般模型：1111111min,1101,01绝对约束目标约束非负约束kkkkkkLLkkLkkkknijjijnk jjkkkjjkkPw dw dPw dw da xb imC xddqkKxjnddkK 优先因子优先因子加权系数加权系数第第k个目标的期望值个目标的期望值目标规划：目标规划：求一组决策变量的求一组决策变量的满意值满意值，使决策，使决策结果与给定结果与给定目标总偏差最小目标总偏差最小。 Z=0 各级目标均已达到各级目标均已达到 Z0 部分目标未达

31、到。部分目标未达到。 约束包括目标约束、绝对约束、非负约束。约束包括目标约束、绝对约束、非负约束。目标函数及约束均为线性的。目标函数及约束均为线性的。 目标函数中只有偏差变量，总是求偏差变目标函数中只有偏差变量，总是求偏差变量最小。量最小。目标规划的目标函数目标规划的目标函数由各目标约束的正、负偏差变量及相应的优先因子和权系数构由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。从决策者的要求来分析，总希望得到的结果与规定的指标成。从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小

32、化的目标函数，化的目标函数，min Z = f（d +，d -）其基本形式有三种：其基本形式有三种：（1 1） 要求恰好达到目标值，即正、负偏差变量都要尽可能要求恰好达到目标值，即正、负偏差变量都要尽可能地小地小 。构造的目标函数是。构造的目标函数是 min Z = f（ d + d - ） （2 2） 要求不超过目标值，但允许达不到目标值，即只有使要求不超过目标值，但允许达不到目标值，即只有使正偏差量要尽可能地小（实现最少或为零）正偏差量要尽可能地小（实现最少或为零） min Z = f（ d +）（3 3） 要求超过目标值，即超过量不限。要求超额完成规定要求超过目标值，即超过量不限。要求超

33、额完成规定目标，要实现负偏差量为零或为最小目标，要实现负偏差量为零或为最小 min Z = f（ d -）明确问题，列出明确问题，列出目标的优先级和目标的优先级和权系数权系数构造目标规构造目标规划模型划模型求出满意解求出满意解满意否？满意否？分析各项目标分析各项目标完成情况完成情况据此制定出决策方案据此制定出决策方案NY例例2 2 某厂生产某厂生产、两种两种产品，有关数据如表所示。产品，有关数据如表所示。试求获利最大的生产方案？试求获利最大的生产方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑： 1、产品、产品的产量不低于

34、产品的产量不低于产品的产量；（第一目标）的产量；（第一目标） 2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班； （第二目标）（第二目标） 3、利润不小于、利润不小于 56 元。元。 （第三目标）（第三目标）解解: : 分析分析 第二目标第二目标P2 ：)(222ddP第三目标第三目标P3 ：33dP第一目标第一目标P1: Pd11 拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 1 1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量； 2 2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班； 3 3、利润不小于、利润

35、不小于 56 56 元。元。 2x1 +x2 11 （在绝对约束基础上进行目标规划）（在绝对约束基础上进行目标规划） x1 - x2 + d1- - d1+ = 0 ( (要求：要求： d d1 1+ + 尽可能小，最好是尽可能小，最好是0 0才能满足才能满足 ) ) x1 +2x2 + d2- - d2+ =10 （要求：（要求：d d2 2- - 和和 d d2 2+ + 都尽可能小，最好等于都尽可能小，最好等于0 0） 8x1 +10 x2 + d3- - d3+ =56 （要求：（要求：d d3 3- - 尽可能小，最好是尽可能小，最好是0 0才能满足才能满足） x1 , x2 , d

36、i- ,di+ 0 规划模型：规划模型：1122233121112221233121 2min,(),0210810562110,.0(1.2.3) jjPdP ddP dxxddxxddxxddxxxddj例例3 某企业计划生产甲，乙两种产品，这些产品分别要在某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润单件利润甲甲11402乙乙22043最大负荷最大负荷1281612问该企业应如何安排计划，使得计划期内的总利润收入为最大？问该企业应如何安排计划，使得计划期内的总利润收入

37、为最大？现企业追求如下目标：现企业追求如下目标：(1)力求使利润指标不低于力求使利润指标不低于12元；元；(2)考虑到市场需求，甲、乙两种产品的生产量需保持考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；的比例；(3)C和和D为贵重设备，为贵重设备，严格禁止严格禁止超时使用；超时使用；(4)设备设备B必要时可以加班，但加班时间要控制；设备必要时可以加班，但加班时间要控制；设备A即要求充分即要求充分利用，又尽可能不加班。利用，又尽可能不加班。 第第1优先级优先级P1企业利润；企业利润； 第第2优先级优先级P2甲乙产品的产量保持甲乙产品的产量保持1:1的比例的比例 第第3优先级优先级P3

38、设备设备A,B尽量不超负荷工作。其中设备尽量不超负荷工作。其中设备A的重要性的重要性比设备比设备B大三倍。大三倍。上述目标规划模型可以表示为：2341 12223333 412121112212312412iiminPd ,P (dd ),3P (dd ),P d 4x164x122x3xdd12s.t. xxdd0 x2xdd12x2xdd8x ,x ,d ,d0 (i1,.,4)目标规划的解法目标规划的解法1、图解法；、图解法；2、单纯形法。、单纯形法。例例1 用图解法求解用图解法求解 4.2 目标规划的图解法目标规划的图解法min p1 (d1 +d1+) , p2 d2s.t 10 x

39、1 +12 x2 + d1 d1+62.5 x1 + 2 x2 + d2 d2+10 2x1 + x2 8 x1、x2 、dk+ 、dk 0 (k=1, 2)p1合同型合同型p2利润型利润型求解步骤：求解步骤：1. 在坐标轴上根据在坐标轴上根据绝对约束和非负约束绝对约束和非负约束确定变量的确定变量的可行域；可行域；2. 暂不考虑偏差变量暂不考虑偏差变量时，按照时，按照优先级别优先级别做出做出目标约束目标约束曲线（越优先，先确定）曲线（越优先，先确定），并标出偏差量，并标出偏差量 dk+ （一（一般朝向上方）和般朝向上方）和 dk 的的方向方向（一般朝向下方）（一般朝向下方） ；3. 根据目标函

40、数要求求解：根据目标函数要求求解：对于对于合同型目标合同型目标，落在对，落在对应的应的目标约束曲线上目标约束曲线上即为最优；对于即为最优；对于利润型目标利润型目标，应，应使使d-越小越好，即应沿着越小越好，即应沿着目标线向上移动目标线向上移动；对于；对于成本型成本型目标目标，应沿着，应沿着目标线向下运动目标线向下运动。同时，取值过程中，。同时，取值过程中，优先级别低的应在优先级别高的可行域内执行。优先级别低的应在优先级别高的可行域内执行。O 5X2X124 8 10d1+d1d2+d2C2x1+x2 =8Bmin p1 ( d1+ + d1) , p2 d2C10 x1+12x2 = 62.5

41、Dx1+2x2 = 10E（1）可行域：）可行域：OBC（2）优先级）优先级p1目标，属于目标，属于合同型目合同型目标标，满足（，满足（d1+ + d1）最小，则在目）最小，则在目标线上即可满足。同时满足可行域，标线上即可满足。同时满足可行域，则则CD直线可行。直线可行。（3）次优先级）次优先级p2目目标，属于利润型目标，标，属于利润型目标，满足满足d2最小，则沿最小，则沿其目标线往上即可满其目标线往上即可满足。同时满足可行域，足。同时满足可行域，则则FGC可行。但可行。但要优先考虑要优先考虑p1，则只，则只能是能是ED直线。直线。FG解：解： 可行域可行域OBC 目标目标1： 线段线段 DC

42、 目标目标2： 线段线段 DE ，其中，其中D为超额完成任务。为超额完成任务。 E为正好完成任务，由题意选为正好完成任务，由题意选D点。点。得目标解得目标解x1 =0 d1+ =0 d1 =0 x2 =62.5/12 d2+ =0.4 d2 =0例例2 用图解法求解用图解法求解 min p1 d1 , p2 d2 3x1 + 4x2 9 5x1 + 2x2 8s.t 12 x1 +15 x2 + d1 d1+30 12x1 + 8 x2 + d2 d2+12 x1、x2 、dk+ 、dk 0p1 利润型利润型p2 成本型成本型x1 x2 123123min p1 d1 , p2 d2oMCDp

43、1d1ABp2d2F（1）可行区域：）可行区域：OMCD;（2）满足）满足p1，d1-最好为最好为0，可行，可行域域ABCD；（3）满足）满足p2，d2+最好为最好为0，但是，但是要首先满足要首先满足p1，即只能在，即只能在ABCD中取值，必然有中取值，必然有d2+ 0，则应在，则应在ABCD中选择一个，使中选择一个，使d2+最小。最小。解：解： 可行域可行域OACD 目标目标1： 区域区域 ABCD 目标目标2：点：点A得目标解得目标解x1 =0 d1+ =0 d1 =0 x2 =2 d2+ =4 d2 =04.3目标规划的单纯形法目标规划的单纯形法 图解法的缺点：只能解决二维决策变量的情况

44、，图解法的缺点：只能解决二维决策变量的情况，对于三维及以上，很难顺利解决；对于三维及以上，很难顺利解决； 一般的方式：单纯形法；一般的方式：单纯形法； 优先因子的处理：在计算中，应注意优先因子的处理：在计算中，应注意p1p2.pn，优先因子之间差距非常大，优先因子之间差距非常大，可采用差距很大的数来代替；可采用差距很大的数来代替； 目标约束看做目标约束看做等式约束等式约束，偏差量也看做决策变偏差量也看做决策变量量。特点特点 目标函数：目标函数：min 最优性判断：最优性判断：j 0 时为最优时为最优 非基变量检验数的特殊性：非基变量检验数的特殊性： 含有不同等级的优先因子含有不同等级的优先因子

45、 P1, P2 , Pk ; ; 又因又因 P1 P2 P3 Pk ，所以检验数的正负首，所以检验数的正负首先取决于先取决于P1 的系数的正负，若的系数的正负，若P1 的系数为的系数为0，再，再由由P2 的系数的正负决定检验数的正负，然后依次的系数的正负决定检验数的正负，然后依次类推。类推。目标规划的目标规划的“特殊特殊”单纯形法单纯形法1.列出初始单纯形表。目标规划中目标函数一定是求最小，列出初始单纯形表。目标规划中目标函数一定是求最小，不必将不必将极小的情况转换为求极大极小的情况转换为求极大，仍然采用，仍然采用原有目标函数原有目标函数。同时，选择。同时，选择负偏差量负偏差量作为作为基变量基

46、变量，构成初始基向量，构成初始基向量；（求；（求min，非基变量的，非基变量的检验数全检验数全0合格合格）2.按照按照传统单纯形法传统单纯形法的方式求解检验数的方式求解检验数，此时由于检验数中必然会，此时由于检验数中必然会含有优先因子，按照含有优先因子，按照优先因子的优先程度优先因子的优先程度，将，将检验数分成多行检验数分成多行，每行输入检验数中对应的优先因子的系数每行输入检验数中对应的优先因子的系数，则每个变量对应的总，则每个变量对应的总检验数即为检验数即为（行系数（行系数*优先因子）；优先因子）；3.从从最优先因子最优先因子开始，检查其系数，观察其开始，检查其系数，观察其系数是否为系数是否

47、为，如非，如非负，则完成。如负，则完成。如含有负系数含有负系数，则，则需要进行变量的替代需要进行变量的替代；4.确定换入变量确定换入变量：从：从最优先因子最优先因子开始，选择其负开始，选择其负检验数检验数中中最小值最小值所所对应的变量为对应的变量为换入变量换入变量；（；（选择绝对值最大的负检验数选择绝对值最大的负检验数）5.确定换出变量：按照单纯形法的方法，确定确定换出变量：按照单纯形法的方法，确定b/alj（alj0）中中最小最小值值对应的行作为对应的行作为主元行主元行，其，其对应的原基变量为换出向量对应的原基变量为换出向量；6. 用换入向量替代基变量中的换出向量，对矩阵进行用换入向量替代基

48、变量中的换出向量，对矩阵进行迭代运算；迭代运算；7. 再次检查检验数，再次检查检验数，观察检验数是否为非负观察检验数是否为非负。如果。如果第第一优先级所有检验数均为非负一优先级所有检验数均为非负时，则转入下一优先时，则转入下一优先级；级；8. 迭代运算停止的准则：迭代运算停止的准则：（1）检验数）检验数p1，p2.，pk行行的所有值均为非负；（的所有值均为非负；（2）p1，p2.，pi行所有检验行所有检验数均为非负，第数均为非负，第pi+1行存在负检验数，但在负检验行存在负检验数，但在负检验数所在的列的上面行中都有正检验数（原因是数所在的列的上面行中都有正检验数（原因是p1p2.pi+1）11

49、222331211122212331212m in,(),0210810562110,.0(1.2.3) jjP dPddP dxxddxxddxxddxxxddj112223312111222123312313m in,(),0210810562110,.jP dPddP d x xd d x x d dxx d dx x + x xd d 0(1.2.3)j j = min，10/2，56/10，11/1= 5进基变量x2Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000

50、001jP1 000100000P2 120002000P3 81000000101d2d2d3d3d1d2d3dd1 换出变量d2-112223312111222123312313m in,(),0210810562110,.jP dPddP d x xd d x x d dxx d dx x + x xd d 0(1.2.3)j j 目标规划的单纯形法Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 053/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-1/21/2001jP1 000100000

51、P2 000011000P3 30005-50101d1d2d2d3d3d1d3d= min10/3,10,6/3,12/3= 2,进基变量x1换出变量d3-目标规划的单纯形法Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21jP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d1d最优解为最优解为x12， x2 4。但非基变量但非基变量d3+的检验数为零，故此题有无

52、穷多最优解。的检验数为零，故此题有无穷多最优解。目标规划的单纯形法Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21jP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d1d= min4 , 24 , 6= 4进基变量d3+换出变量d1-目标规划的单纯形法Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-

53、1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001jP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d1d最优解为最优解为x110/3， x2 10/3。112324321211122213324412min, 2.5,301225002140601000,0(1.2.3.4) llP dP dP dP dxxddxxddxddxddxddl目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P12500301211000000014021001100000

54、60100000110001000100000011jP1 301201000000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1, -= 60,进基变量x1换出变量d3-112324321211122213324412min, 2.5,301225002140601000,0(1.2.3.4) llP dP dP dP dxxddxxddxddxddxddl目标规划的单纯形法Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122

55、000 x160100000110001000100000011jP1 0120100303000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20/2, =10进基变量d3+换出变量d2-目标规划的单纯形法Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1jP1 030115-150000P2 0-5/400-5/45/45/2001P3 00

56、000100001d1d2d2d3d3d4d4d1d4d3d= min400/15, =10进基变量d2+换出变量d1-目标规划的单纯形法Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011jP1 0010000000P2 0-1-1/121/12002/5001P3 01/5-1/151/15100000= min,350/6,1250/6,100/1=751d1d2d2d3d3d4d4d4d

57、2d3d进基变量x2换出变量d3+目标规划的单纯形法Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211jP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2d P3 优先等级目标没有实现，但已无法改进，得到满意解优先等级目标没有实现，但已无法改进，得到满意解 x1 60， x2 175/

58、3， d2+115/3，d4-125/3112324321211122213324412min, 2.5,301225002140601000,0(1.2.3.4) llP dP dP dP dxxddxxddxddxddxddl112231111222123312min(), 102 40.32100,0 (1,2,3) iip ddp dxddxxddS txxddxx ddi 例例 用单纯形法求解用单纯形法求解cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+P1d1-10 1 01-1 0 0 0 00d2-4021 0 01-1 0 0P2d3-1003

59、2 0 0 0 01-1jP1-1 0 01 01 0 0P2-3-2 0 0 0 0 01初始表初始表cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+0 x110101-1 0 0 0 00d2-2001 -2 21-1 0 0 P2d3-7002 -33 0 01-1jP10 0 1001 0 0P20-23 -30 0 01cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+0 x110101-1 0 0 0 00 x22001 -2 21-1 0 0P2d3-3000 1 -1 -2 21-1jP10 0 10 0100P20

60、0 -1 1 2 -201最优表最优表4.5 应用举例应用举例例、某单位制定职工升级计划，基本情况如下：例、某单位制定职工升级计划，基本情况如下：等级等级月工资月工资现有人数现有人数编制人数编制人数ABC2000150010001001201501201501501、升级调薪模型、升级调薪模型尽可能的满足如下要求：尽可能的满足如下要求： 1、不能超过月工资总额、不能超过月工资总额600000元；元；2、提级时，不能超过每级的定编人数；、提级时，不能超过每级的定编人数；3、升级面不超过现有人数的、升级面不超过现有人数的20；4、C级不足的人数可用新职工补足；级不足的人数可用新职工补足； A级将有