运筹学目标规划

1、目标规划目标规划( Goal Programming)本章基本要求：本章基本要求： 理解目标规划概念理解目标规划概念 掌握目标规划建模技巧掌握目标规划建模技巧 能够运用图解法求解模型能够运用图解法求解模型 能够运用单纯形法求解模型能够运用单纯形法求解模型运筹学目标规划5.1 基本概念及数学模型基本概念及数学模型目标规划的产生：目标规划的产生： 线性规划的局限性线性规划的局限性 目标单一性，不能处理多目标单一性，不能处理多目标问题。目标问题。 但现在很多问题都有多个目标，希望能获得综合的但现在很多问题都有多个目标，希望能获得综合的最优，但目标之间往往存在一定的矛盾，如利润最高、最优，但目标之间往

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

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

4、个；原材料限制：原材料限制：2500kg。 满足需求满足需求 800件；件； 达到质量水平合格率达到质量水平合格率98%；工时成本工时成本7000元。元。1）分）分 析析例例1 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 +

6、x3 +x4 ）2500；非负限制：非负限制： xi 0（i=1，2，3，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

8、 +x4 ）800；或；或0.98（x1 + x2 + x3 +x4 ）800；（2）产品质量水平）产品质量水平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。运筹学目标规划

9、（1）满足需求量）满足需求量800件：件：两种情况不可能同时出现两种情况不可能同时出现，化为标准型约束。，化为标准型约束。0.98（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%x

10、1 + 98%x2 + 95%x3 +90%x4 +S3=98% （ x1 + x2 + x3 +x4） 99%x1 + 98%x2 + 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 x

11、3 +24x4 7000。 20 x1 + 30 x2 + 20 x3 +24x4 S6=7000（S5和和S6中只可能出现一个）中只可能出现一个）如何综合考虑目标要求中可能会出现的两种情况？如何综合考虑目标要求中可能会出现的两种情况？运筹学目标规划（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% （

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

13、差量（0）S偶偶剩余变量，称为正剩余变量，称为正偏差量（偏差量（0）运筹学目标规划目标要求转换成约束后的情形目标要求转换成约束后的情形（1）满足需求量）满足需求量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 ）+ d

14、1- - d1+ =800 1%x1 -3%x3 -8%x4 +d2- d2+ =0 20 x1 + 30 x2 + 20 x3 +24x4 +d3- d3+ =7000di-，负偏差量，负偏差量di+，正偏差量，正偏差量目目标标约约束束运筹学目标规划4）相关概念引入）相关概念引入 d+：正偏差量，可能实现值高于目标指标值的部分；：正偏差量，可能实现值高于目标指标值的部分； d-：负偏差量，可能实现值低于目标指标值的部分。：负偏差量，可能实现值低于目标指标值的部分。实现目标的三种情况：实现目标的三种情况：（1） 超过目标值超过目标值 k 0 ，k- 0（2） 达不到目标值达不到目标值 k =0

15、，k- 0（3） 刚好达到目标值刚好达到目标值 k =0，k- 0 ( d+ * d0 ) 正、负偏差变量正、负偏差变量 运筹学目标规划 目标规划的约束形式目标规划的约束形式 （1）绝对约束：也叫客观条件约束，为必须严）绝对约束：也叫客观条件约束，为必须严格满足的约束。格满足的约束。（2）目标约束：目标规划特有的约束，也叫软约）目标约束：目标规划特有的约束，也叫软约束。束。（3）非负约束：要求所有决策变量和偏差量均）非负约束：要求所有决策变量和偏差量均0。运筹学目标规划如例如例1中的目标约束为：中的目标约束为： (1)满足需求满足需求 800件；件； (2)达到质量水平合格率达到质量水平合格率

16、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,xkjddkkj运筹学目标规划5）如何确定最终的目标方程？）如何确定最终的目标方程？ 设想：希望能尽量同时满足三个目标需求，即刚好达到800件产量，质量合格率刚好为98%，工时成本刚好为7000元。此时，所有的正偏差和负偏差

17、量应均为0。但是，实际情况下，正偏差或负偏差量很难同时为0，即实际中。 但是，应该，则需实际可能值应尽可能与目标要求值靠近，即使得所有目标约束的偏差量最小。由此，可建立新的目标函数： 112233minwdddddd 原有目标变成了约束（目标约束），如何寻找原有目标变成了约束（目标约束），如何寻找新的目标方程？新的目标方程？运筹学目标规划1122331234111342212343312341234min0.980.980.980.988000.010.030.0801015887000222.53200022222500,jkkwddddddxxxxddxxxddxxxxddxxxxxxxx

18、x dd目标约束系统约束非负约束0(1,2,3,4,1,2,3)jk例例1的数学模型的数学模型例例1 1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为20002000，原材料，原材料25002500公斤（每件产品耗原公斤（每件产品耗原料料2 2公斤），产品需求量为公斤），产品需求量为800800件。件。 要求制订一生产计划，使其尽可能达到以下三项指标：（要求制订一生产计划

19、，使其尽可能达到以下三项指标：（1 1）满足需要量；（）满足需要量；（2 2）质量水平达到质量水平达到98%98%；（；（3 3）70007000元的工时成本。元的工时成本。运筹学目标规划6）目标规划的特点）目标规划的特点 约束一般包括目标约束、系统约束和非负约束一般包括目标约束、系统约束和非负约束三部分；约束三部分； 目标函数转换成求多个期望目标值的偏差目标函数转换成求多个期望目标值的偏差量和的最小；量和的最小； 目标及约束仍然为线性。目标及约束仍然为线性。 目标规划所得的是满意方案。目标规划所得的是满意方案。运筹学目标规划 问题问题A、目标要求中，是否都需要同时满足？即实际、目标要求中，是

20、否都需要同时满足？即实际中可能会出现需要某种情况越大越好（如利润），即中可能会出现需要某种情况越大越好（如利润），即在原有基本目标值的基础上偏离越大越好，也可能需在原有基本目标值的基础上偏离越大越好，也可能需要出现在原基本目标值的基础上越小越好（如成本）。要出现在原基本目标值的基础上越小越好（如成本）。 这样的情况如何在目标函数中得到体现？这样的情况如何在目标函数中得到体现？7）由例）由例1引发的思考与相关讨论引发的思考与相关讨论例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转

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

22、企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。 要求制订一生产计划，使其尽可能达到以下三项指标要求制订一生产计划，使其尽可能达到以下三项指标：（：（1）满）满足需要量足需要量；（2）质量水平超过）质量水平超过98%；（3）不超过）不超过7000元的工元的工时成本时成本。 并且优先满足（并且优先满足（2）、

23、其次为（）、其次为（3），最后为（），最后为（1）。）。问题问题B：目标要求有轻重缓急的情况，这种情况如：目标要求有轻重缓急的情况，这种情况如何在目标函数中体现？比如，要求必须优先保证产何在目标函数中体现？比如，要求必须优先保证产品质量，然后是控制成本，最后是达到产量要求？品质量，然后是控制成本，最后是达到产量要求？优先量必须优先考虑，那如何率先满足优先目标？优先量必须优先考虑，那如何率先满足优先目标？运筹学目标规划问题问题B、目标有轻重缓急的情况，这种情况如何、目标有轻重缓急的情况，这种情况如何在目标函数中体现？比如，要求必须优先保证产在目标函数中体现？比如，要求必须优先保证产品质量，然后是

24、控制成本，最后是达到产量要求？品质量，然后是控制成本，最后是达到产量要求？优先量必须优先考虑，那如何率先满足优先目优先量必须优先考虑，那如何率先满足优先目标？标？采用优先权来区分目标的优先级别，并将采用优先权来区分目标的优先级别，并将其在目标函数中作为相应偏差量的目标系其在目标函数中作为相应偏差量的目标系数。同时，根据优先级别不一样，应将目数。同时，根据优先级别不一样，应将目标系数拉开。标系数拉开。越优先，代表目标函数中越优先，代表目标函数中最先接近于最先接近于0，则目标系，则目标系数应越大。数应越大。运筹学目标规划 优先因子与权系数优先因子与权系数 用于区分各目标的主次或轻重缓急的不同，第用

25、于区分各目标的主次或轻重缓急的不同，第一优先的目标赋予一优先的目标赋予 p1 ，次优先的为，次优先的为p2 且且 pk pk+同一优先级别内的区别用权系数同一优先级别内的区别用权系数 wj表示差异。表示差异。min w= p1(d2+d2- )+ p2(d3+d3- )+ p3(d1+d1- ) 例例1中，如果要求首先满足质量，然后是中，如果要求首先满足质量，然后是成本，最后是需求，则可建立：成本，最后是需求，则可建立：运筹学目标规划（1）对于）对于利润型目标利润型目标，要求是可能实现值超过目标值越多越，要求是可能实现值超过目标值越多越好，即好，即d+越大越好越大越好，则在目标函数中，则在目标

26、函数中，不能对不能对d+求最小求最小；（2）对于）对于成本型目标成本型目标，要求可能实现值低于目标值越多越好，要求可能实现值低于目标值越多越好，即即d-越大越好越大越好，则在目标函数中，则在目标函数中不能对不能对d-求最小求最小；（3）对）对于合同型目标，要求跟目标保持一致，不超过也不短于合同型目标，要求跟目标保持一致，不超过也不短缺，即要求缺，即要求d+和和d-都最小都最小，则在目标函数中应将，则在目标函数中应将两者综合考虑两者综合考虑。分成三种目标形式分成三种目标形式 要求制订一生产计划，使其尽可能达到以下三项指标要求制订一生产计划，使其尽可能达到以下三项指标：（1）满足需要量）满足需要量

27、；（2）质量水平超过）质量水平超过98%；（3）不超过）不超过7000元的工时成本元的工时成本。合同型目标合同型目标利润型目标利润型目标成本型目标成本型目标运筹学目标规划(1) 恰好达到目标（合同型目标）：恰好达到目标（合同型目标）： min Z= p(d k-+dk+)(2) 超过目标（利润型目标）：超过目标（利润型目标）： min Z= p (dk -) (3) 不超过目标（成本型目标）：不超过目标（成本型目标）： min Z= p (dk+) 目标函数的处理目标函数的处理运筹学目标规划例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常

28、生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。 要求制订一生产计划，使其尽可能达到以下三项指标要求制订一生产计划，使其尽可能达到以下三项指标：（：（1）满）满足需要量足需要量；（2）质量水平超过）质量水平超过98%；（3）不超过）不超过7000元的工元的工时成本时成本。 并且优先满足（并且优先满足（2）、其次为（）、其次为（3），最后为（），

29、最后为（1）。）。min Z= d 1-+d1+ + d 2-+d2+ + d 3-+d3+1223311min()Zp dp dp dd最终目标函数最终目标函数运筹学目标规划建模方法：建模方法：(1) 设定约束条件设定约束条件 (构建构建目标约束、绝对约束目标约束、绝对约束和非负约束和非负约束)；(2) 规定目标约束优先级；规定目标约束优先级；(3) 根据目标所属的类型，建立新的目标函根据目标所属的类型，建立新的目标函数，完成模型的建立。数，完成模型的建立。 二、二、 目标规划的一般数学模型目标规划的一般数学模型运筹学目标规划一般模型：一般模型： KkddnjxKkqddxCmibxadwd

30、wPdwdwPZkkjnjkkkjjknjijijkkkLkkLkLkkkkkk10,1011,min1111111非负约束目标约束绝对约束优先因子优先因子加权系数加权系数第第k个目标的期望值个目标的期望值运筹学目标规划目标规划：求一组决策变量的满意值，使决策目标规划：求一组决策变量的满意值，使决策结果与给定目标总偏差最小。结果与给定目标总偏差最小。 Z=0 各级目标均已达到各级目标均已达到 Z0 部分目标未达到。部分目标未达到。 约束包括目标约束、绝对约束、非负约束。约束包括目标约束、绝对约束、非负约束。 目标函数及约束均为线性的。目标函数及约束均为线性的。 目标函数中只有偏差变量，总是求偏

31、差目标函数中只有偏差变量，总是求偏差变量最小。变量最小。运筹学目标规划5.2 目标规划的解法目标规划的解法1、图解法；、图解法；2、单纯形法。、单纯形法。运筹学目标规划例例2 用图解法求解用图解法求解 一、一、 目标规划的图解法目标规划的图解法min Z=p1 (d1 +d1+) + p2 d2s.t 10 x1 +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利润型利润型运筹学目标规划求解步骤：求解步骤：在坐标轴上根据绝对约束和非负约束确定变量的在坐标轴上根据绝对约束

32、和非负约束确定变量的可行域；可行域；2. 暂不考虑偏差变量时，按照暂不考虑偏差变量时，按照优先级别优先级别做出目标约束做出目标约束曲线（越优先，先确定），并标出偏差量曲线（越优先，先确定），并标出偏差量 dk+ （一（一般朝向上方）和般朝向上方）和 dk 的方向（一般朝向下方）的方向（一般朝向下方） ；3. 根据目标函数要求求解：对于根据目标函数要求求解：对于合同型目标合同型目标，落在对，落在对应的应的目标约束曲线上目标约束曲线上即为最优；对于即为最优；对于利润型目标利润型目标，应，应使使d-越小越好，即应沿着越小越好，即应沿着目标线向上移动目标线向上移动；对于；对于成本型成本型目标目标，应沿

33、着，应沿着目标线向下运动目标线向下运动。同时，取值过程中，。同时，取值过程中，优先级别低的应在优先级别高的可行域内执行。优先级别低的应在优先级别高的可行域内执行。运筹学目标规划O 5X2X124 8 10d1+d1d2+d2C2x1+x2 =8Bmin Z=p1 ( d1+ + d1) + p2 d2C10 x1+12x2 = 62.5Dx1+2x2 = 10E（1）可行域：）可行域：OBC（2）优先级）优先级p1目标，属于合同型目目标，属于合同型目标，满足（标，满足（d1+ + d1）最小，则在目）最小，则在目标线上即可满足。同时满足可行域，标线上即可满足。同时满足可行域，则则CD直线可行。

34、直线可行。（3）次优先级）次优先级p2目目标，属于利润型目标，标，属于利润型目标，满足满足d2最小，则沿最小，则沿其目标线往上即可满其目标线往上即可满足。同时满足可行域，足。同时满足可行域，则则FGC可行。但可行。但要优先考虑要优先考虑p1，则只，则只能是能是ED直线。直线。FG运筹学目标规划解：解： 可行域可行域OBC 目标目标1： 线段线段 DC 目标目标2： 线段线段 DE ，其中，其中D为超额完成任务。为超额完成任务。 E为正好完成任务，由题意选为正好完成任务，由题意选D点。点。 得目标解得目标解x1 =0 d1+ =0 d1 =0 g1 =12.5x2 =5.2 d2+ =0.4 d

35、2 =0 g2 =10.4运筹学目标规划例例3 用图解法求解用图解法求解 min Z=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 Z=p1 d1 + p2 d2oMCDp1d1ABp2d2F（1）可行区域：）可行区域：OMCD;（2）满足）满足p1，d1-最好为最好为0，可行，可行域域ABCD；（3）满足）满足p2，d2+最好为最好为0，但是，但是要首

36、先满足要首先满足p1，即只能在，即只能在ABCD中取值，必然有中取值，必然有d2+ 0，则应在，则应在ABCD中选择一个，使中选择一个，使d2+最小。最小。运筹学目标规划解：解： 可行域可行域OACD 目标目标1： 区域区域 ABCD 目标目标2：点：点A 得目标解得目标解x1 =0 d1+ =0 d1 =0 g1 =30 x2 =2 d2+ =4 d2 =0 g2 =16运筹学目标规划 图解法的缺点：只能解决二维决策变量的情况，图解法的缺点：只能解决二维决策变量的情况，对于三维及以上，很难顺利解决；对于三维及以上，很难顺利解决； 一般的方式：单纯形法；一般的方式：单纯形法； 优先因子的处理：

37、在计算中，应注意优先因子的处理：在计算中，应注意p1p2.pn，优先因子之间差距非常大，可，优先因子之间差距非常大，可采用差距很大的数来代替；采用差距很大的数来代替； 目标约束看做等式约束，目标约束看做等式约束，偏差量也看做决策变量偏差量也看做决策变量。二、目标规划的一般解法二、目标规划的一般解法运筹学目标规划112231111222123312min() 102 40.32100,0 (1,2,3) iiZp ddp dxddxxddS txxddxx ddi 5.2 目标规划的一般解法目标规划的一般解法例例4 用单纯形法求解用单纯形法求解运筹学目标规划解法一：传统型单纯形法解法一：传统型单

38、纯形法112231111222123312max() 102 40.32100,0 (1,2,3) iiwp ddp dxddxxddS txxddxx ddi 1、标准化、标准化运筹学目标规划cj00-p100-p1-p20CB基基bx1x2d1-d1+d2-d2+d3-d3+-p1d1-10 101-1 0 0 0 00d2-4021 0 01-1 0 0-p2d3-10032 0 0 0 01-1jp1+3p22p20-p10-p10-p22、建立初始单纯形表、建立初始单纯形表选择选择负偏差量负偏差量为基准变量。为基准变量。检验检验数是否均为非负？如否，则要进行变量替换。检验检验数是否均

39、为非负？如否，则要进行变量替换。maxcC Bi a ij运筹学目标规划cj00-p100-p1-p20CB基基bx1x2d1-d1+d2-d2+d3-d3+-p1d1-10101-1 0 0 0 00d2-4021 0 01-1 0 0-p2d3-10032 0 0 0 01-1jp1+3p22p20-p10-p10-p22、基变量的替换、基变量的替换x1换入；换入；d1-换出。换出。x10020-2211-100702-33001-10-p12p20-p1-3p23p200-p2mini =bi/aik|aik0=l运筹学目标规划cj00-p100-p1-p20CB基基bx1x2d1-d1

40、+d2-d2+d3-d3+0 x110 101-1 0 0 0 00 x22001 -2 21-1 0 0-p2d3-3000 1 -1 -2 01-1j00-p1+p2-p2-2p22p2 -p10-p23、最终单纯形表、最终单纯形表x1 =10， x2 =20， d3- =30g1=10，g2=40，g3=70运筹学目标规划解法二：目标规划的解法二：目标规划的“特殊特殊”单纯形单纯形法法列出初始单纯形表。目标规划中目标函数一定是求最小，不必将极小的情况转换为求极大，仍然采用原有目标函数。同时，选择负偏差量作为基变量，构成初始基向量；（求min，非基变量的检验数全0合格）按照传统单纯形法的方

41、式求解检验数，此时由于检验数中必然会含有优先因子，按照优先因子的优先程度，将检验数分成多行，每行输入检验数中对应的优先因子的系数，则每个变量对应的总检验数即为（行系数*优先因子）；从最优先因子开始，检查其系数，观察其系数是否为，如非负，则完成。如含有负系数，则需要进行变量的替代；确定换入变量：从最优先因子开始，选择其负检验数中最小值所对应的变量为换入变量；（选择绝对值最大的负检验数）确定换出变量：按照单纯形法的方法，确定b/alj（alj0）中最小值对应的行作为主元行，其对应的原基变量为换出向量；运筹学目标规划用换入向量替代基变量中的换出向量，对矩阵进行用换入向量替代基变量中的换出向量，对矩阵

42、进行迭代运算；迭代运算；再次检查检验数，观察检验数是否为非负。如果再次检查检验数，观察检验数是否为非负。如果第第一优先级所有检验数均为非负一优先级所有检验数均为非负时，则转入下一优先时，则转入下一优先级；级；迭代运算停止的准则：（迭代运算停止的准则：（1）检验数）检验数p1，p2.，pk行行的所有值均为非负；（的所有值均为非负；（2）p1，p2.，pi行所有检验行所有检验数均为非负，第数均为非负，第pi+1行存在负检验数，但在负检验行存在负检验数，但在负检验数所在的列的上面行中都有正检验数（原因是数所在的列的上面行中都有正检验数（原因是p1p2.pi+1）运筹学目标规划112231111222

43、123312min() 102 40.32100,0 (1,2,3) iiZp ddp dxddxxddS txxddxx ddi 运筹学目标规划cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+P1d1-10 1 01-10d2-40211-1 P2d3-100321-1jP1-111P2-3-21初始表初始表运筹学目标规划cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+0 x120101-1 1/20d2-101 -2 21/21 P2d3-402 -33-3/2 1-1jP10 0 1001 00P20-23 0-3 01运筹

44、学目标规划cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+0 x11011-10 x2201 -2 21-1 P2d3-30 1 -1 -2 21-1jP1 11P2 -1 1 2 -21最优表最优表运筹学目标规划目标规划的目标规划的“特殊特殊”单纯形法总结单纯形法总结1、列出初始单纯形表。仍然采用原有目标函数，且选择作为，构成初始基向量；2、按照传统单纯形法的方式求解检验数，并按照优先因子的优先程度，将检验数分成多行，每行中填入检验数中相应的优先因子的系数，则每个变量对应的总检验数即为（行系数*优先因子）；3、从最优先因子开始，检查其系数，观察其系数是否为，如

45、非负，则完成。如含有负系数，则需要进行变量的替代；4、确定换入变量：从最优先因子开始，选择其检验数中最小值所对应的变量为换入变量；5、确定换出变量：按照单纯形法的方法，确定b/alj中最小的值对应的行作为主元行，其对应的原基变量为换出向量；运筹学目标规划6、用换入向量替代基变量中的换出向量，对矩阵进、用换入向量替代基变量中的换出向量，对矩阵进行迭代运算；行迭代运算；7、再次检查检验数，观察检验数是否为非负。如果、再次检查检验数，观察检验数是否为非负。如果第一优先级所有检验数均为非负第一优先级所有检验数均为非负时，则转入下一优先时，则转入下一优先级；级；8、迭代运算停止的准则：（、迭代运算停止的

46、准则：（1）检验数）检验数p1，p2.，pk行行的所有值均为非负；（的所有值均为非负；（2）p1，p2.，pi行所有检验数行所有检验数均为非负，第均为非负，第pi+1行存在负检验数，但在负检验数所行存在负检验数，但在负检验数所在的列的上面行中都有正检验数（原因是在的列的上面行中都有正检验数（原因是p1p2.pi+1）运筹学目标规划5.3 应用举例应用举例例、某单位制定职工升级计划，基本情况如下：例、某单位制定职工升级计划，基本情况如下：等级等级月工资月工资现有人数现有人数 编制人数编制人数ABC2000150010001001201501201501501、升级调薪模型、升级调薪模型运筹学目标

47、规划要求：要求： 1、不能超过月工资总额、不能超过月工资总额600000元；元； 2、提级时，每级的定编人数不能超过；、提级时，每级的定编人数不能超过； 3、升级面不超过现有人数的、升级面不超过现有人数的20； 4、C级不足的人数可用新职工补足；级不足的人数可用新职工补足； A级将有级将有10的人要退休，退休的人要退休，退休 后工资由福利基金中开支。后工资由福利基金中开支。运筹学目标规划解：设解：设x1表示由表示由B级提升到级提升到A级的人员数；级的人员数； x2表示由表示由C级提升到级提升到B级的人员数；级的人员数； x3表示新录用表示新录用C级的人员数。级的人员数。 根据规定优先因子：根据

48、规定优先因子： p1 不超过工资总额；不超过工资总额； p2 各级人员不超编；各级人员不超编； p3 升级面升级面20%，但尽可能多提。，但尽可能多提。运筹学目标规划 工资总额工资总额 2000（1001000.1+x1）+1500(120 x1+ x2) +1000(150 x2+ x3)（）600000化为化为12311500500100090000 xxxdd1221233234411223A 100(1-0.1)+ 12030B12015030C1501500( )( )( )xxddxxxxddxxxxdd 11552266B( )120 0.224C( )150 0.230 xxd

49、dxxdd 级级 编制限额的目标约束：编制限额的目标约束： 提升的目标约束提升的目标约束运筹学目标规划构造目标函数构造目标函数1 112 2233443 5566m i n()()( )z p d d p d d d d d d p d d d d （1）目标）目标1：工资总额不得超过，成本型目标，不能对：工资总额不得超过，成本型目标，不能对d1-求求min，则目标函数中取消，则目标函数中取消d1- ；112234356min()()()zp dp dddp dd（2）目标）目标2：编制限额，成本型目标，不能对：编制限额，成本型目标，不能对d2-、 d3- 、d4-和和求求min，则目标函数中

50、取消；，则目标函数中取消；（3）目标）目标3：人员升级，利润型目标，不能对：人员升级，利润型目标，不能对d5+和和 d6+ 求求min，目标函数中应取消。目标函数中应取消。运筹学目标规划得到的结果：得到的结果：变量变量 含义含义 x1 提升到提升到A级的人数级的人数 24 30 30 24 x2 提升到提升到B级的人数级的人数 30 30 50 52x3 录用为录用为C级的人数级的人数 30 30 50 52 d1- 工资总额节余工资总额节余 33000 30000d2- A级编制不足人数级编制不足人数 6 6d3- B级编制不足人数级编制不足人数 24 30 1 2 d4- C级编制不足人数

51、级编制不足人数d5+ B级编制超过人数级编制超过人数 6 6 d6+ C级编制超过人数级编制超过人数 20 22 运筹学目标规划2、投资计划模型、投资计划模型某经济特区的计委有一笔资金，在下一个计划期内可向某经济特区的计委有一笔资金，在下一个计划期内可向钢铁、化工、石油等行业投资建新厂。这些工厂能否预钢铁、化工、石油等行业投资建新厂。这些工厂能否预期建成是一定风险的，在建成投产后，其收入与投资额期建成是一定风险的，在建成投产后，其收入与投资额有关，经过分析研究，各工厂的建设方案的风险因子及有关，经过分析研究，各工厂的建设方案的风险因子及投产后可增收入的百分比例如表所示。投产后可增收入的百分比例

52、如表所示。 运筹学目标规划计委根据该地区情况提出以下要求：用于钢计委根据该地区情况提出以下要求：用于钢铁的投资额不超过总资金的铁的投资额不超过总资金的35%；用于化工；用于化工的投资额至少占总资金的的投资额至少占总资金的15%；用于石油的；用于石油的投资不超过总资金的投资不超过总资金的50%。并且，首先要考虑总风险不超过并且，首先要考虑总风险不超过0.2；其次；其次考虑总收入至少要增长考虑总收入至少要增长0.55%；然后再考虑；然后再考虑各项投资的总和不能超过总资金额，现在要各项投资的总和不能超过总资金额，现在要确定对不同行业的各投资历方案所占的比例。确定对不同行业的各投资历方案所占的比例。

53、运筹学目标规划解：解：（1）确定决策变量：）确定决策变量：假设假设xi为第为第i方案投资金的百分比，方案投资金的百分比，且总的投资比例为且总的投资比例为100%；（2）确定绝对约束：）确定绝对约束：1）用于钢铁工业的投资额不超过总资金的）用于钢铁工业的投资额不超过总资金的35% ：12340.35xxxx2）用于化工工业的投资额至少占总资金的）用于化工工业的投资额至少占总资金的15% ：3）用于石油工业的投资额不超过总资金的）用于石油工业的投资额不超过总资金的50% ：5670.15xxx8910110.5xxxx运筹学目标规划（3）确定目标约束：）确定目标约束：1）总风险不超过）总风险不超过

54、0.2，为第一优先级，赋予有限因子，为第一优先级，赋予有限因子p1： 111110.2iiirxdd2）总收入至少要增长）总收入至少要增长0.55% ，为第二优先级，赋予有限因子，为第二优先级，赋予有限因子p2： 112210.55iiig xdd3）各项投资不能超过总投资金额）各项投资不能超过总投资金额 ，为第三优先级，赋予有限，为第三优先级，赋予有限因子因子p3： 113311iixdd运筹学目标规划（4）建立目标函数，完成模型：）建立目标函数，完成模型：112233minZp dp dp d12340.35xxxx5670.15xxx8910110.5xxxx111110.2iiirxd

55、d112210.55iiig xdd113311,0iiiiixddx dds.t.运筹学目标规划应用举例应用举例2某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外购件外，生产一台录音机需甲车间加工间生产。已知除外购件外，生产一台录音机需甲车间加工2 h，乙，乙车间装配车间装配1 h；生产一台电视机需甲车间加工；生产一台电视机需甲车间加工1 h，乙车间装配，乙车间装配3 h。这两种产品生产出来后均需经检验、销售等环节。已知每台录音这两种产品生产出来后均需经检验、销售等环节。已知每台录音机机检验销售费用检验销售费用需

56、需50元，每台电视机检验销售费用需元，每台电视机检验销售费用需30元。又甲元。又甲车间每月可用的生产工时为车间每月可用的生产工时为120 h，车间管理费用为，车间管理费用为80元元/h；乙车；乙车间每月可用的生产工时为间每月可用的生产工时为150 h，车间管理费用为，车间管理费用为20元元/h。估计每。估计每台录音机利润为台录音机利润为100元，每台电视机利润为元，每台电视机利润为75元，又估计下一年元，又估计下一年度内平均每月可销售录音机度内平均每月可销售录音机50台，电视机台，电视机80台。台。工厂确定制订月度计划的目标如下：工厂确定制订月度计划的目标如下：第一优先级：检验和销售费用每月不

57、超过第一优先级：检验和销售费用每月不超过4600元；元；第二优先级：每月售出录音机不少于第二优先级：每月售出录音机不少于50台；台；第三优先级：甲、乙量车间的生产工时得到充分利用（重要性权第三优先级：甲、乙量车间的生产工时得到充分利用（重要性权系数按两个车间每小时费用的比例确定）；系数按两个车间每小时费用的比例确定）；第四优先级：甲车间加班不超过第四优先级：甲车间加班不超过20 h；第五优先级：每月销售电视机不少于第五优先级：每月销售电视机不少于80台；台；第六优先级：两个车间加班总时间要有控制（权系数分配与第三第六优先级：两个车间加班总时间要有控制（权系数分配与第三优先级相同）。优先级相同）

58、。试确定该厂为达到以上目标的最优月度计划生产数字。试确定该厂为达到以上目标的最优月度计划生产数字。运筹学目标规划建模方法：建模方法：(1) 设定约束条件设定约束条件 (构建构建目标约束、绝对约束目标约束、绝对约束和非负约束和非负约束)；(2) 规定目标约束优先级；规定目标约束优先级；(3) 根据目标所属的类型，建立关于偏差量根据目标所属的类型，建立关于偏差量的目标函数，完成模型的建立。的目标函数，完成模型的建立。运筹学目标规划（1）甲、乙两车间的可用工时约束：）甲、乙两车间的可用工时约束：2 x1 +x2 +d1- -d1+=120（甲车间）；（甲车间）；x1 +3x2 +d2- -d2+=1

59、20（乙车间）（乙车间）解：设解：设x1为每月生产的录音机台数，为每月生产的录音机台数，x2为每月生产的电视机为每月生产的电视机台数。列出约束条件：台数。列出约束条件：（2）检验和销售费用的限制：）检验和销售费用的限制：50 x1 +30 x2 +d3- -d3+=4600（3）每月销售量的要求：）每月销售量的要求：x1 +d4- -d4+=50（录音机）；（录音机）；x2 +d5- -d5+=120（电视机）（电视机）（4）对甲加班的限制：）对甲加班的限制：d1+ d6- -d6+=20目标目标1：检验和销售费用每月：检验和销售费用每月不超过不超过4600元；元；目标目标2：每月售出录音机不

60、少：每月售出录音机不少于于50台；台；目标目标3：甲、乙量车间的生产：甲、乙量车间的生产工时得到充分利用（重要性权工时得到充分利用（重要性权系数按两个车间每小时费用的系数按两个车间每小时费用的比例确定）；比例确定）；目标目标4：甲车间加班不超过：甲车间加班不超过20 h；目标目标5：每月销售电视机不少：每月销售电视机不少于于80台台运筹学目标规划确定目标函数：确定目标函数：首先要确定优先级；然后确定各目标的类型，对目标函数进首先要确定优先级；然后确定各目标的类型，对目标函数进行取舍。行取舍。第一优先级：检验和销售费用第一优先级：检验和销售费用每月不超过每月不超过4600元；元；第二优先级：每月