Chapter4 目标规划(Goal Programming )目标规划问题及其数学模型目标规划问题及其数学模型目标规划的图解法目标规划的图解法目标规划的单纯形法目标规划的单纯形法目标规划应用举例目标规划应用举例本章主要内容：本章主要内容：本章主要内容：本章主要内容：4.1目标规划问题及其数学模型目标规划问题及其数学模型目标规划的产生：目标规划的产生：线性规划的局限性线性规划的局限性目标单一性，不能处理多目目标单一性，不能处理多目标问题；硬约束标问题；硬约束。但现在很多问题都有但现在很多问题都有多个目标多个目标，希望能获得，希望能获得综合的综合的最优最优，但目标之间往往存在一定的矛盾，如利润最高、，但目标之间往往存在一定的矛盾，如利润最高、成本最低、产量高、质量好、用工最少等。传统的线成本最低、产量高、质量好、用工最少等。传统的线性规划很难同时处理？对于这种多目标的问题，性规划很难同时处理？对于这种多目标的问题，如何如何解决？解决？一、基本概念一、基本概念目标规划可统筹兼顾的处理多种目标的关系目标规划可统筹兼顾的处理多种目标的关系例例1 某企业生产某种产品的生产方式有四种：某企业生产某种产品的生产方式有四种：正常生产、正常生产、加班生产、转包合同和雇临时工加班生产、转包合同和雇临时工生产。有关数据如下表所生产。有关数据如下表所示。示。在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤（每件产品耗原料公斤（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（1）满足需要量；（）满足需要量；（2）质量水平达到）质量水平达到98%；（；（3）7000元元的工时成本的工时成本。正常生产正常生产加班生产加班生产转包合同转包合同临时工临时工所需工时所需工时/件件222.53成本费用元成本费用元/工时工时101588质量水平质量水平99%98%95%90%目标规划的引出目标规划的引出生产条件生产条件约束约束:欲达到的目标：欲达到的目标： 总工时限制：总工时限制：2000个；个；原材料限制：原材料限制：2500kg。1.满足需求满足需求800件；件；2.达到质量水平合格率达到质量水平合格率98%；3.工时成本工时成本7000元。元。1）分）分析析例例 某企业生产某种产品的生产方式有四某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用在未来的一计划期内，可利用总工时总工时为为20002000，原材料，原材料25002500公斤公斤（每件产品耗原（每件产品耗原料料2 2公斤），公斤），产品需求量为产品需求量为800800件。件。 要求制订一生产计划，使其尽可能达要求制订一生产计划，使其尽可能达到以下到以下三项指标三项指标：（1 1）满足需要量；）满足需要量；（2 2）质量水平达到）质量水平达到98%98%；（；（3 3）70007000元的工元的工时成本。时成本。2）组建约束）组建约束确定决策变量确定决策变量：假设正常生产、加班生产、转包合同：假设正常生产、加班生产、转包合同和雇临时工生产的量分别为和雇临时工生产的量分别为x1，x2，x3和和x4。确定约束确定约束：工时限制：工时限制：2x1+2x2+2.5x3+3x42000；原材料限制：原材料限制：2（x1+x2+x3+x4）2500；非负限制：非负限制：xi0（i=1，2，3，4）正常生产正常生产加班生产加班生产转包合同转包合同临时工临时工所需工时所需工时/件件222.53成本费用元成本费用元/工时工时101588质量水平质量水平99%98%95%90%需要达到的目标需要达到的目标：（1）满足需求量）满足需求量800件；（件；（2）产品质量水平）产品质量水平98%；（；（3）工时成本）工时成本7000元。元。3）分析目标需求）分析目标需求三个目标要求，如何得到集中体现？三个目标要求，如何得到集中体现？是否需要建立三个目标函数？是否需要建立三个目标函数？传统线性规划一般只建立一个目标函数，而有传统线性规划一般只建立一个目标函数，而有多个约束。多个约束。是否可以将三个目标以约束的形式是否可以将三个目标以约束的形式表现出来，这样可解决多目标的问题？表现出来，这样可解决多目标的问题？3）目标需求分析与目标向约束的转化）目标需求分析与目标向约束的转化需要达到的目标需要达到的目标：实际也变成了约束情况实际也变成了约束情况（1）满足需求量）满足需求量800件件：在实际生产中，可能：在实际生产中，可能会出现两种情况会出现两种情况，生，生产量产量不够不够800件或超过件或超过800件，则会产生件，则会产生不同的情况不同的情况：0.98（x1+x2+x3+x4）800；或或0.98（x1+x2+x3+x4）800；（2）产品质量水平）产品质量水平98%：出现两种可能：出现两种可能99%x1+98%x2+95%x3+90%x498%（x1+x2+x3+x4）；或或99%x1+98%x2+95%x3+90%x498%（x1+x2+x3+x4）；（3）工时成本）工时成本7000元元：可能出现两种可能：可能出现两种可能：20x1+30x2+20x3+24x47000；或或20x1+30x2+20x3+24x47000。（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%x498%（x1+x2+x3+x4）；99%x1+98%x2+95%x3+90%x4+S3=98%（x1+x2+x3+x4）99%x1+98%x2+95%x3+90%x498%（x1+x2+x3+x4）；99%x1+98%x2+95%x3+90%x4S4=98%（x1+x2+x3+x4）（S3和和S4中只可能出现一个）中只可能出现一个）（3）工时成本）工时成本7000元：元：20x1+30x2+20x3+24x47000；20x1+30x2+20x3+24x4+S5=700020x1+30x2+20x3+24x47000。20x1+30x2+20x3+24x4S6=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+S3S4=98%（x1+x2+x3+x4）（S3和和S4中只可能出现一个，至少有一个为零）中只可能出现一个，至少有一个为零）（3）工时成本）工时成本7000元：元：20x1+30x2+20x3+24x4+S5S6=7000（S5和和S6中只可能出现中只可能出现一个，至少有一个为零）一个，至少有一个为零）如何综合考虑目标要求中可能会出现的两种情况？如何综合考虑目标要求中可能会出现的两种情况？这里就在目标中引入了这里就在目标中引入了偏差量偏差量的概念，使多个目的概念，使多个目标要求转变成了约束标要求转变成了约束目标约束目标约束。S奇奇松弛变量，称为负松弛变量，称为负偏差量（偏差量（0）S偶偶剩余变量，称为正偏剩余变量，称为正偏差量（差量（0）目标要求转换成约束后的情形目标要求转换成约束后的情形（1）满足需求量）满足需求量800件：归一化处理件：归一化处理（2）产品质量水平）产品质量水平98%（3）工时成本）工时成本7000元元0.98（x1+x2+x3+x4）+S1-S2=80099%x1+98%x2+95%x3+90%x4+S3S4=98%（x1+x2+x3+x4）20x1+30x2+20x3+24x4+S5S6=70000.98（x1+x2+x3+x4）+d1-d1+=8001%x1-3%x3-8%x4+d2-d2+=020x1+30x2+20x3+24x4+d3-d3+=7000di-，负偏差量，负偏差量di+，正偏差量，正偏差量目目标标约约束束4）相关概念引入）相关概念引入d+：正偏差量，可能实现值：正偏差量，可能实现值高于高于目标指标值的部分；目标指标值的部分；d-：负偏差量，可能实现值：负偏差量，可能实现值低于低于目标指标值的部分。目标指标值的部分。实现目标的三种情况：实现目标的三种情况：（1）超过目标值超过目标值k 0，k- 0（2）达不到目标值达不到目标值k =0，k- 0（3）刚好达到目标值刚好达到目标值k =0，k- 0(d+*d0)正、负偏差变量正、负偏差变量目标值目标值d1-d1+实际值实际值实际值实际值当实际值同目标值恰好一致时，正负偏差同为当实际值同目标值恰好一致时，正负偏差同为0d1-d1+=0d1- 0，d1+ 0,正负偏差两者中必有一个为正负偏差两者中必有一个为0正偏差变量正偏差变量负偏差变量负偏差变量目标规划的约束形式目标规划的约束形式（1）绝对约束）绝对约束：也叫：也叫客观条件约束客观条件约束，为必须严格，为必须严格满足的约束。满足的约束。（2）目标约束）目标约束：目标规划特有的约束，也叫：目标规划特有的约束，也叫软约软约束束。（3）非负约束）非负约束：要求所有决策变量和偏差量均：要求所有决策变量和偏差量均0。如例如例1中的目标约束为：中的目标约束为：(1)满足需求满足需求800件；件；(2)达到质量水平合格率达到质量水平合格率98%；(3)工时成本工时成本7000元；元；(4)绝对约束绝对约束（5）非负约束非负约束:5）如何确定最终的目标方程？）如何确定最终的目标方程？设想：设想：希望能希望能尽量同时满足三个目标需求尽量同时满足三个目标需求，即，即刚好刚好达达到到800件产量，质量合格率件产量，质量合格率刚好刚好为为98%，工时成本，工时成本刚好刚好为为7000元。此时，元。此时，所有的正偏差和负偏差量应均为所有的正偏差和负偏差量应均为0。但是，实际情况下，正偏差或负偏差量但是，实际情况下，正偏差或负偏差量很难同时为很难同时为0，即实际中即实际中不可能刚好同时达到目标要求不可能刚好同时达到目标要求。但是，应该但是，应该尽力靠近目标要求尽力靠近目标要求尽力靠近目标要求尽力靠近目标要求，则需，则需实际可能值应尽实际可能值应尽可能与目标要求值靠近可能与目标要求值靠近，即使得，即使得所有目标约束的偏差量所有目标约束的偏差量最小最小。由此，可建立新的目标函数：。由此，可建立新的目标函数：原有目标变成了约束（目标约束），原有目标变成了约束（目标约束），如何寻找如何寻找新的目标方程？新的目标方程？例例1的数学模型的数学模型例例1 1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。雇临时工生产。有关数据如下表所示。 在未来的一计划期内，可利用在未来的一计划期内，可利用总工时为总工时为20002000，原材料，原材料25002500公斤公斤（每件产品耗原（每件产品耗原料料2 2公斤），公斤），产品需求量为产品需求量为800800件。件。 要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（1 1）满足需要量；）满足需要量；（2 2）质量水平达到）质量水平达到98%98%；（；（3 3）70007000元的工时成本。元的工时成本。6）目标规划的特点）目标规划的特点约束一般包括约束一般包括目标约束、系统约束和非目标约束、系统约束和非负约束负约束三部分；三部分；目标函数转换成求目标函数转换成求多个期望目标值的偏多个期望目标值的偏差量和的最小差量和的最小；目标及约束仍然为目标及约束仍然为线性线性。目标规划所得的是满意方案。目标规划所得的是满意方案。问题问题A、目标要求中，是否都需要同时满足？即实际、目标要求中，是否都需要同时满足？即实际中可能会出现需要某种情况越大越好（如利润），即中可能会出现需要某种情况越大越好（如利润），即在原有基本目标值的基础上偏离越大越好，也可能需在原有基本目标值的基础上偏离越大越好，也可能需要出现在原基本目标值的基础上越小越好（如成本）。要出现在原基本目标值的基础上越小越好（如成本）。这样的情况如何在目标函数中得到体现？这样的情况如何在目标函数中得到体现？7）由例）由例1引发的思考与相关讨论引发的思考与相关讨论例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（：（1）满）满足需要量足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的工的工时成本时成本。7）由例）由例1引发的思考与相关讨论引发的思考与相关讨论例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（：（1）满）满足需要量足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的工的工时成本时成本。并且优先满足（并且优先满足（2）、其次为（）、其次为（3），最后为（），最后为（1）。）。问题问题B：目标要求有目标要求有轻重缓急轻重缓急的情况，这种情况的情况，这种情况如如何在目标函数中体现何在目标函数中体现？比如，要求必须优先保证产？比如，要求必须优先保证产品质量，然后是控制成本，最后是达到产量要求？品质量，然后是控制成本，最后是达到产量要求？优先量必须优先考虑，那优先量必须优先考虑，那如何率先满足优先目标如何率先满足优先目标？问题问题B、目标有轻重缓急的情况，这种情况如何目标有轻重缓急的情况，这种情况如何在目标函数中体现在目标函数中体现？比如，要求必须优先保证产？比如，要求必须优先保证产品质量，然后是控制成本，最后是达到产量要求品质量，然后是控制成本，最后是达到产量要求？优先量必须优先考虑，那如何率先满足优先优先量必须优先考虑，那如何率先满足优先目标目标？采用采用优先权优先权来区分目标的来区分目标的优先级别优先级别，并将，并将其在目标函数中作为相应偏差量的其在目标函数中作为相应偏差量的目标系目标系数数。同时，根据优先级别不一样，应将目。同时，根据优先级别不一样，应将目标系数拉开。标系数拉开。越优先，代表目标函数中越优先，代表目标函数中最先接近于最先接近于0，则目标系，则目标系数应越大。数应越大。优先因子与权系数优先因子与权系数 用于区分各目标的主次或轻重缓急的不同，第用于区分各目标的主次或轻重缓急的不同，第一优先的目标赋予一优先的目标赋予p1，次优先的为，次优先的为p2且且pkpk+同一优先级别内的区别用权系数同一优先级别内的区别用权系数wj表示差异。表示差异。minw=p1(d2+d2- )+ p2(d3+d3- )+p3(d1+d1- )例例1中，如果要求首先满足质量，然后是成中，如果要求首先满足质量，然后是成本，最后是需求，则可建立：本，最后是需求，则可建立：（1）对于）对于利润型目标利润型目标，要求是可能实现值超过目标值越多越好，要求是可能实现值超过目标值越多越好，即即d+越大越好（不希望低于目标值）越大越好（不希望低于目标值），则在目标函数中，则在目标函数中，对对d-求最求最小小；（2）对于）对于成本型目标成本型目标，要求可能实现值低于目标值越多越好，即，要求可能实现值低于目标值越多越好，即d-越大越好越大越好(不希望超过目标值）不希望超过目标值），则在目标函数中，则在目标函数中对对d-+求最小求最小；（3）对）对于合同型目标，要求跟目标保持一致，不超过也不短缺，于合同型目标，要求跟目标保持一致，不超过也不短缺，即要求即要求d+和和d-都最小都最小，则在目标函数中应将，则在目标函数中应将两者综合考虑两者综合考虑。分成三种目标形式分成三种目标形式要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（1）满足需要量）满足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的工时成本的工时成本。合同型目标合同型目标利润型目标利润型目标成本型目标成本型目标(1)恰好达到目标（恰好达到目标（合同型目标合同型目标）：）：minZ= p(d k-+dk+)(2)超过目标（超过目标（利润型目标利润型目标）：）：minZ= p (dk -)(3)不超过目标（不超过目标（成本型目标成本型目标）：）：minZ= p (dk+)目标函数的处理目标函数的处理例例1 某企业生产某种产品的生产方式有四种：正常生产、加班生产、某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为在未来的一计划期内，可利用总工时为2000，原材料，原材料2500公斤公斤（每件产品耗原料（每件产品耗原料2公斤），产品需求量为公斤），产品需求量为800件。件。要求制订一生产计划，使其尽可能达到以下要求制订一生产计划，使其尽可能达到以下三项指标三项指标：（：（1）满）满足需要量足需要量；（2）质量水平）质量水平超过超过98%；（3）不超过不超过7000元元的工的工时成本时成本。并且优先满足（并且优先满足（2）、其次为（）、其次为（3），最后为（），最后为（1）。）。minZ=d 1-+d1+ + d 2-+d2+ + d 3-+d3+最终目标函数最终目标函数建模方法建模方法：(1)设定约束条件设定约束条件(构建构建目标约束、绝对约束目标约束、绝对约束和非负约束和非负约束)；(2)规定目标约束规定目标约束优先级优先级；(3)根据目标所属的类型，建立新的目标函根据目标所属的类型，建立新的目标函数，完成模型的建立。数，完成模型的建立。二、二、目标规划的一般数学模型目标规划的一般数学模型一般模型：一般模型：优先因子优先因子加权系数加权系数第第k个目标的期望值个目标的期望值目标规划：目标规划：求一组决策变量的求一组决策变量的满意值满意值，使决策，使决策结果与给定结果与给定目标总偏差最小目标总偏差最小。Z=0各级目标均已达到各级目标均已达到Z0 部分目标未达到。部分目标未达到。 约束包括目标约束、绝对约束、非负约束。约束包括目标约束、绝对约束、非负约束。目标函数及约束均为线性的。目标函数及约束均为线性的。 目标函数中只有偏差变量，总是求偏差变目标函数中只有偏差变量，总是求偏差变量最小。量最小。目标规划的目标函数目标规划的目标函数由各目标约束的正、负偏差变量及相应的优先因子和权系数构由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。从决策者的要求来分析，总希望得到的结果与规定的指标成。从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，化的目标函数，min Z = f（d +，d -）其基本形式有三种：其基本形式有三种：（1 1） 要求恰好达到目标值，即正、负偏差变量都要尽可能要求恰好达到目标值，即正、负偏差变量都要尽可能地小地小 。构造的目标函数是。构造的目标函数是 minZ= f（d +d -） （2 2） 要求不超过目标值，但允许达不到目标值，即只有使要求不超过目标值，但允许达不到目标值，即只有使正偏差量要尽可能地小（实现最少或为零）正偏差量要尽可能地小（实现最少或为零） minZ= f（d +）（3 3） 要求超过目标值，即超过量不限。要求超额完成规定要求超过目标值，即超过量不限。要求超额完成规定目标，要实现负偏差量为零或为最小目标，要实现负偏差量为零或为最小 minZ=f（d -）用目标规划求解问题的过程：明确问题，列出明确问题，列出目标的优先级和目标的优先级和权系数权系数构造目标规构造目标规划模型划模型求出满意解求出满意解满意否满意否？分析各项目标分析各项目标完成情况完成情况据此制定出决策方案据此制定出决策方案NY例例2 2 某厂生产某厂生产、两种两种产品，有关数据如表所示。产品，有关数据如表所示。试求获利最大的生产方案试求获利最大的生产方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑： 1、产品、产品的产量不低于产品的产量不低于产品的产量；（第一目标）的产量；（第一目标） 2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班； （第二目标）（第二目标） 3、利润不小于、利润不小于 56 元。元。 （第三目标）（第三目标）解解: : 分析分析 第二目标第二目标P2：第三目标第三目标P3：第一目标第一目标P1: 拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 1 1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量； 2 2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班； 3 3、利润不小于、利润不小于 56 56 元。元。2x1+x211（在绝对约束基础上进行目标规划）（在绝对约束基础上进行目标规划）x1-x2+d1-d1+=0( (要求：要求： d d1 1+ + 尽可能小，最好是尽可能小，最好是0 0才能满足才能满足 ) )x1+2x2+d2-d2+=10（要求：（要求：d d2 2- - 和和 d d2 2+ + 都尽可能小，最好等于都尽可能小，最好等于0 0）8x1+10x2+d3-d3+=56（要求：（要求：d d3 3- - 尽可能小，最好是尽可能小，最好是0 0才能满足才能满足）x1,x2,di-,di+0规划模型：规划模型：例例3某某企企业业计计划划生生产产甲甲，乙乙两两种种产产品品，这这些些产产品品分分别别要要在在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。四种不同设备上加工。按工艺文件规定，如表所示。ABCD单件利润单件利润甲甲11402乙乙22043最大负荷最大负荷1281612问该企业应如何安排计划，使得计划期内的总利润收入为最大问该企业应如何安排计划，使得计划期内的总利润收入为最大？现企业追求如下目标：现企业追求如下目标：(1)力求使利润指标不低于力求使利润指标不低于12元；元；(2)考虑到市场需求，甲、乙两种产品的生产量需保持考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比例；的比例；(3)C和和D为贵重设备，为贵重设备，严格禁止严格禁止超时使用；超时使用；(4)设备设备B必要时可以加班，但加班时间要控制；设备必要时可以加班，但加班时间要控制；设备A即要求充分利即要求充分利用，又尽可能不加班。用，又尽可能不加班。第第1优先级优先级P1企业利润；企业利润；第第2优先级优先级P2甲乙产品的产量保持甲乙产品的产量保持1:1的比例的比例第第3优先级优先级P3设备设备A,B尽量不超负荷工作。其中设备尽量不超负荷工作。其中设备A的重要性的重要性比设备比设备B大三倍。大三倍。上述目标规划模型可以表示为：目标规划的解法目标规划的解法1、图解法；、图解法；2、单纯形法。、单纯形法。例例1用图解法求解用图解法求解4.2目标规划的图解法目标规划的图解法minZ=p1(d1+d1+)+p2d2s.t 10x1+12x2+d1d1+62.5x1+2x2+d2d2+102x1+x28x1、x2、dk+、dk0(k=1,2)p1合同型合同型p2利润型利润型求解步骤：求解步骤：1.在坐标轴上根据在坐标轴上根据绝对约束和非负约束绝对约束和非负约束确定变量的确定变量的可行域；可行域；2.暂不考虑偏差变量暂不考虑偏差变量时，按照时，按照优先级别优先级别做出做出目标约束目标约束曲线（越优先，先确定）曲线（越优先，先确定），并标出偏差量，并标出偏差量dk+（一（一般朝向上方）和般朝向上方）和dk的的方向方向（一般朝向下方）（一般朝向下方）；3.根据目标函数要求求解：根据目标函数要求求解：对于对于合同型目标合同型目标，落在对，落在对应的应的目标约束曲线上目标约束曲线上即为最优；对于即为最优；对于利润型目标利润型目标，应，应使使d-越小越好，即应沿着越小越好，即应沿着目标线向上移动目标线向上移动；对于；对于成本型成本型目标目标，应沿着，应沿着目标线向下运动目标线向下运动。同时，取值过程中，。同时，取值过程中，优先级别低的应在优先级别高的可行域内执行。优先级别低的应在优先级别高的可行域内执行。O5X2X124810d1+d1d2+d2C2x1+x2 =8BminZ=p1(d1+d1)+p2d2C10x1+12x2 = 62.5Dx1+2x2 = 10E（1）可行域：）可行域：OBC（2）优先级）优先级p1目标，属于目标，属于合同型目合同型目标标，满足（，满足（d1+d1）最小，则在目）最小，则在目标线上即可满足。同时满足可行域，标线上即可满足。同时满足可行域，则则CD直线可行。直线可行。（3）次优先级）次优先级p2目目标，属于利润型目标，标，属于利润型目标，满足满足d2最小，则沿最小，则沿其目标线往上即可满其目标线往上即可满足。同时满足可行域，足。同时满足可行域，则则FGC可行。但可行。但要优先考虑要优先考虑p1，则只，则只能是能是ED直线。直线。FG解：解：可行域可行域OBC目标目标1：线段线段DC目标目标2：线段线段DE，其中，其中D为超额完成任务。为超额完成任务。E为正好完成任务，由题意选为正好完成任务，由题意选D点。点。得目标解得目标解x1=0d1+=0d1=0x2=62.5/12d2+=0.4d2=0例例2用图解法求解用图解法求解minZ=p1d1+p2d23x1+4x295x1+2x28s.t12x1+15x2+d1d1+3012x1+8x2+d2d2+12x1、x2、dk+、dk0p1利润型利润型p2成本型成本型x1x2123123minZ=p1d1+p2d2oMCDp1d1ABp2d2F（1）可行区域：）可行区域：OMCD;（2）满足）满足p1，d1-最好为最好为0，可行，可行域域ABCD；（3）满足）满足p2，d2+最好为最好为0，但是，但是要首先满足要首先满足p1，即只能在，即只能在ABCD中取值，必然有中取值，必然有d2+0，则应在，则应在ABCD中选择一个，使中选择一个，使d2+最小。最小。解：解：可行域可行域OACD目标目标1：区域区域ABCD目标目标2：点：点A得目标解得目标解x1=0d1+=0d1=0x2=2d2+=4d2=04.3目标规划的单纯形法目标规划的单纯形法图解法的缺点：只能解决二维决策变量的情况，图解法的缺点：只能解决二维决策变量的情况，对于三维及以上，很难顺利解决；对于三维及以上，很难顺利解决；一般的方式：单纯形法；一般的方式：单纯形法；优先因子的处理：在计算中，应注意优先因子的处理：在计算中，应注意p1p2.pn，优先因子之间差距非常大，优先因子之间差距非常大，可采用差距很大的数来代替；可采用差距很大的数来代替；目标约束看做目标约束看做等式约束等式约束，偏差量也看做决策变偏差量也看做决策变量量。特点特点目标函数目标函数：min最优性最优性判断：判断：j0 时为最优时为最优非非基变量检验数的特殊性：基变量检验数的特殊性： 含有不同等级的优先因子含有不同等级的优先因子 P1,P2,Pk ; ; 又因又因 P1P2 P3Pk ，所以检验数的正负首，所以检验数的正负首先取决于先取决于P1 的系数的正负，若的系数的正负，若P1 的系数为的系数为0，再，再由由P2 的系数的正负决定检验数的正负，然后依次的系数的正负决定检验数的正负，然后依次类推。类推。目标规划的目标规划的“特殊特殊”单纯形法单纯形法1.列出初始单纯形表。目标规划中目标函数一定是求最小，列出初始单纯形表。目标规划中目标函数一定是求最小，不必将不必将极小的情况转换为求极大极小的情况转换为求极大，仍然采用，仍然采用原有目标函数原有目标函数。同时，选择。同时，选择负偏差量负偏差量作为作为基变量基变量，构成初始基向量，构成初始基向量；（求；（求min，非基变量的，非基变量的检验数全检验数全0合格合格）2.按照按照传统单纯形法传统单纯形法的方式求解检验数的方式求解检验数，此时由于检验数中必然会，此时由于检验数中必然会含有优先因子，按照含有优先因子，按照优先因子的优先程度优先因子的优先程度，将，将检验数分成多行检验数分成多行，每行输入检验数中对应的优先因子的系数每行输入检验数中对应的优先因子的系数，则每个变量对应的总，则每个变量对应的总检验数即为检验数即为（行系数（行系数*优先因子）；优先因子）；3.从从最优先因子最优先因子开始，检查其系数，观察其开始，检查其系数，观察其系数是否为系数是否为非负非负非负非负，如非，如非负，则完成。如负，则完成。如含有负系数含有负系数，则，则需要进行变量的替代需要进行变量的替代；4.确定换入变量确定换入变量：从：从最优先因子最优先因子开始，选择其负开始，选择其负检验数检验数中中最小值最小值所所对应的变量为对应的变量为换入变量换入变量；（；（选择绝对值最大的负检验数选择绝对值最大的负检验数）5.确定换出变量：按照单纯形法的方法，确定确定换出变量：按照单纯形法的方法，确定b/alj（alj0）中中最小最小值值对应的行作为对应的行作为主元行主元行，其，其对应的原基变量为换出向量对应的原基变量为换出向量；6.用换入向量替代基变量中的换出向量，对矩阵进行用换入向量替代基变量中的换出向量，对矩阵进行迭代运算；迭代运算；7.再次检查检验数，再次检查检验数，观察检验数是否为非负观察检验数是否为非负。如果。如果第第一优先级所有检验数均为非负一优先级所有检验数均为非负时，则转入下一优先时，则转入下一优先级；级；8.迭代运算停止的准则：迭代运算停止的准则：（1）检验数）检验数p1，p2.，pk行行的所有值均为非负；（的所有值均为非负；（2）p1，p2.，pi行所有检验行所有检验数均为非负，第数均为非负，第pi+1行存在负检验数，但在负检验行存在负检验数，但在负检验数所在的列的上面行中都有正检验数（原因是数所在的列的上面行中都有正检验数（原因是p1p2.pi+1）例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题解：将上述目标规划问题化为标准型：解：将上述目标规划问题化为标准型：解：将上述目标规划问题化为标准型：解：将上述目标规划问题化为标准型：= min，10/2，56/10，11/1= 5进基变量x2Cj000P1 P2 P2P3 00CBXBbx1x2x3 00111100000P210120011000P35681000001100x3 11210000001jP1 000100000P2 120002000P3 8100000010换出变量d2-建立初始单纯形表：建立初始单纯形表：建立初始单纯形表：建立初始单纯形表：目标规划的单纯形法Cj000P1P2P2P300CBXBbx1x2x3 053/20111/2-1/20000x251/21001/2-1/2000P363000-551100x3 63/2000-1/21/2001jP1 000100000P2 000011000P3 30005-5010= min10/3,10,6/3,12/3=2,进基变量x1换出变量d3-目标规划的单纯形法Cj000P1 P2 P2P3 00CBXBbx1x2x3 0200113-3-1/21/200x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300x3 300002-2-1/21/21jP1 000100000P2 000011000P3 000000100最优解为最优解为x12，x2 4。但非基变量但非基变量d3+的检验数为零，故此题有无穷多最优解。的检验数为零，故此题有无穷多最优解。目标规划的单纯形法Cj000P1 P2 P2P3 00CBXBbx1x2x3 0200113-3-1/21/200x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300x3 300002-2-1/21/21jP1 000100000P2 000011000P3 000000100= min4 , 24 , 6= 4进基变量d3+换出变量d1-目标规划的单纯形法Cj000P1 P2 P2P3 00CBXBbx1x2x3 04002-26-6-1100x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000x3 100-11-11001jP1 000100000P2 000011000P3 000000100最优解为最优解为x110/3，x2 10/3。例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011jP1 301201000000P2 00000002.501P3 0000010000= min2500/30,140/2,60/1,-=60,进基变量x1换出变量d3-目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000x160100000110001000100000011jP1 0120100303000P2 00000002.501P3 0000010000= min700/30,20/2, =10进基变量d3+换出变量d2-目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000x17011/2001/2-1/200000100010000001-1jP1 030115-150000P2 0-5/400-5/45/45/2001P3 0000010000= min400/15, =10进基变量d2+换出变量d1-目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000x1250/312/51/30-1/3000000001000100000011jP1 0010000000P2 0-1-1/121/12002/5001P3 01/5-1/151/15100000= min,350/6,1250/6,100/1=75进基变量x2换出变量d3+目标规划的单纯形法Cj00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000x2175/3011/12-1/1200-5/25/2000x160100000-11000125/300-1/121/12005/2-5/211jP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/200 P3 优先等级目标没有实现，但已无法改进，得到满意解优先等级目标没有实现，但已无法改进，得到满意解 x1 60， x2 175/3， d2+115/3，d4-125/3例例用单纯形法求解用单纯形法求解cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+P1d1-10101-100000d2-4021001-100P2d3-1003200001-1jP1-10010100P2-3-2 000001初始表初始表cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+0x110101-100000d2-2001 -221-100P2d3-7002-33001-1jP100100100P20-23-30001cj00P100P1P20CB基基bx1x2d1-d1+d2-d2+d3-d3+0x110101-100000x22001-221-100P2d3-30001-1-221-1jP100100100P200-112-201最优表最优表4.3应用举例应用举例例、某单位制定职工升级计划，基本情况如下：例、某单位制定职工升级计划，基本情况如下：等级等级月工资月工资现有人数现有人数编制人数编制人数ABC2000150010001001201501201501501、升级调薪模型、升级调薪模型尽可能的满足如下要求：尽可能的满足如下要求：1、不能超过月工资总额、不能超过月工资总额600000元；元；2、提级时，不能超过每级的定编人数；、提级时，不能超过每级的定编人数；3、升级面不超过现有人数的、升级面不超过现有人数的20；4、C级不足的人数可用新职工补足；级不足的人数可用新职工补足；A级将有级将有10的人要退休，退休的人要退休，退休后后工资由福利基金中开支。工资由福利基金中开支。解：解：设设x1表示由表示由B级提升到级提升到A级的人员数；级的人员数；x2表示由表示由C级提升到级提升到B级的人员数；级的人员数；x3表示新录用表示新录用C级的人员数。级的人员数。根据规定优先因子：根据规定优先因子：p1不超过工资总额；不超过工资总额；p2各级人员不超编；各级人员不超编；p3升级面升级面20%，但尽可能多提。，但尽可能多提。工资总额工资总额2000（1001000.1+x1）+1500(120x1+ x2)+1000(150x2+ x3)（）600000化为化为编制限额的目标约束：编制限额的目标约束：提升的目标约束提升的目标约束构造目标函数构造目标函数（1）目标）目标1：工资总额不得超过，：工资总额不得超过，成本型目标成本型目标，不能对，不能对d1-求求min，则，则目标函数中取消目标函数中取消d1-；（2）目标）目标2：编制限额，：编制限额，成本型目标成本型目标，不能对，不能对d2-、d3-、d4-和和求求min，则，则目标函数中取消目标函数中取消；（3）目标）目标3：人员升级，：人员升级，利润型目标利润型目标，不能对，不能对d5+和和d6+求求min，目标函数中应取消。，目标函数中应取消。得到的结果：得到的结果：变量变量含义含义x1提升到提升到A级的人数级的人数24303024x2提升到提升到B级的人数级的人数30305052x3录用为录用为C级的人数级的人数30305052d1-工资总额节余工资总额节余3300030000d2-A级编制不足人数级编制不足人数66d3-B级编制不足人数级编制不足人数243012d4-C级编制不足人数级编制不足人数d5+B级编制超过人数级编制超过人数66d6+C级编制超过人数级编制超过人数20222、投资计划模型、投资计划模型某经济特区的计委有一笔资金，在下一个计划期内可向某经济特区的计委有一笔资金，在下一个计划期内可向钢铁、化工、石油等行业投资建新厂。这些工厂能否预钢铁、化工、石油等行业投资建新厂。这些工厂能否预期建成是一定风险的，在建成投产后，其收入与投资额期建成是一定风险的，在建成投产后，其收入与投资额有关，经过分析研究，各工厂的建设方案的风险因子及有关，经过分析研究，各工厂的建设方案的风险因子及投产后可增收入的百分比例如表所示。投产后可增收入的百分比例如表所示。计委根据该地区情况提出以下要求：计委根据该地区情况提出以下要求：用于钢用于钢铁的投资额不超过总资金的铁的投资额不超过总资金的35%；用于化工；用于化工的投资额至少占总资金的的投资额至少占总资金的15%；用于石油的；用于石油的投资不超过总资金的投资不超过总资金的50%。并且，首先要考虑并且，首先要考虑总风险不超过总风险不超过0.2；其次；其次考虑总收入至少要增长考虑总收入至少要增长0.55%；然后再考虑；然后再考虑各项投资的总和不能超过总资金额各项投资的总和不能超过总资金额，现在要，现在要确定对不同行业的各投资历方案所占的比例。确定对不同行业的各投资历方案所占的比例。解：解：（1）确定决策变量：）确定决策变量：假设假设xi为第为第i方案投资金的百分比，方案投资金的百分比，且总的投资比例为且总的投资比例为100%；（2）确定绝对约束：）确定绝对约束：1）用于钢铁工业的投资额不超过总资金的）用于钢铁工业的投资额不超过总资金的35%：2）用于化工工业的投资额至少占总资金的）用于化工工业的投资额至少占总资金的15%：3）用于石油工业的投资额不超过总资金的）用于石油工业的投资额不超过总资金的50%：（3）确定目标约束：）确定目标约束：1）总风险不超过）总风险不超过0.2，为第一优先级，赋予有限因子，为第一优先级，赋予有限因子p1：2）总收入至少要增长）总收入至少要增长0.55%，为第二优先级，赋予有限因子，为第二优先级，赋予有限因子p2：3）各项投资不能超过总投资金额）各项投资不能超过总投资金额，为第三优先级，赋予有限，为第三优先级，赋予有限因子因子p3：（4）建立目标函数，完成模型：）建立目标函数，完成模型：s.t.例：某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间例：某电子厂生产录音机和电视机两种产品，分别经由甲、乙两个车间生产。已知除外购件外，生产一台生产。已知除外购件外，生产一台录音机录音机需甲车间加工需甲车间加工2h，乙车间装，乙车间装配配1h；生产一台；生产一台电视机电视机需甲车间加工需甲车间加工1h，乙车间装配，乙车间装配3h。这两种产。这两种产品生产出来后均需经检验、销售等环节。已知每台录音机品生产出来后均需经检验、销售等环节。已知每台录音机检验销售费检验销售费用用需需50元元，每台电视机检验销售费用需，每台电视机检验销售费用需30元元。又甲车间每月可用的生。又甲车间每月可用的生产工时为产工时为120h，车间管理费用为，车间管理费用为80元元/h；乙车间每月可用的生产工时；乙车间每月可用的生产工时为为150h，车间管理费用为，车间管理费用为20元元/h。估计每台录音机利润为。估计每台录音机利润为100元元，每，每台电视机利润为台电视机利润为75元元，又估计下一年度内平均每月可销售录音机，又估计下一年度内平均每月可销售录音机50台台，电视机电视机80台台。工厂确定制订月度计划的目标如下：工厂确定制订月度计划的目标如下：第一优先级第一优先级：检验和销售费用每月不超过：检验和销售费用每月不超过4600元；元；第二优先级第二优先级：每月售出录音机不少于：每月售出录音机不少于50台；台；第三优先级第三优先级：甲、乙量车间的：甲、乙量车间的生产工时生产工时得到充分利用（重要性权系数得到充分利用（重要性权系数按两个车间每小时费用的比例确定）；按两个车间每小时费用的比例确定）；第四优先级第四优先级：甲车间加班不超过：甲车间加班不超过20h；第五优先级第五优先级：每月销售电视机不少于：每月销售电视机不少于80台；台；第六优先级第六优先级：两个车间加班总时间要有控制（权系数分配与第三优先：两个车间加班总时间要有控制（权系数分配与第三优先级相同）。级相同）。试确定该厂为达到以上目标的最优月度计划生产数字试确定该厂为达到以上目标的最优月度计划生产数字。建模方法建模方法：(1)设定约束条件设定约束条件(构建构建目标约束、绝对约束目标约束、绝对约束和非负约束和非负约束)；(2)规定目标约束规定目标约束优先级优先级；(3)根据目标所属的类型，建立关于偏差量根据目标所属的类型，建立关于偏差量的目标函数，完成模型的建立。的目标函数，完成模型的建立。（3）甲、乙两车间的可用工时约束：）甲、乙两车间的可用工时约束：2x1+x2+d3-d3+=120（甲车间）；（甲车间）；x1+3x2+d4-d4+=150（乙车间）（乙车间）解：设解：设x1为每月生产的录音机台数，为每月生产的录音机台数，x2为每月生产的电视机为每月生产的电视机台数。列出约束条件：台数。列出约束条件：（1）检验和销售费用的限制：）检验和销售费用的限制：50x1+30x2+d1-d1+=4600（2）每月录音机销售量的要求：）每月录音机销售量的要求：x1+d2-d2+=50（录音机）（录音机）（4）对甲加班的限制：）对甲加班的限制：d1+d5-d5+=20目标目标1：检验和销售费用每月：检验和销售费用每月不超过不超过4600元；元；目标目标2：每月售出录音机不少：每月售出录音机不少于于50台；台；目标目标3：甲、乙两车间的生产：甲、乙两车间的生产工时得到充分利用（重要性权工时得到充分利用（重要性权系数按两个车间每小时费用的系数按两个车间每小时费用的比例确定）；比例确定）；目标目标4：甲车间加班不超过：甲车间加班不超过20h；目标目标5：每月销售电视机不少：每月销售电视机不少于于80台台（6）每月电视机销售量的要求：）每月电视机销售量的要求：x2+d6-d6+=80（电视机）（电视机）确定目标函数：确定目标函数：首先要确定优先级；然后确定各目标的类型，对目标函数进首先要确定优先级；然后确定各目标的类型，对目标函数进行取舍。行取舍。第一优先级第一优先级：检验和销售费用：检验和销售费用每月不超过每月不超过4600元；元；第二优先级第二优先级：每月售出录音机：每月售出录音机不少于不少于50台；台；第三优先级第三优先级：甲、乙量车间的：甲、乙量车间的生产工时得到充分利用（重要生产工时得到充分利用（重要性权系数按两个车间每小时费性权系数按两个车间每小时费用的比例确定）；用的比例确定）；（1）对于第一优先级：）对于第一优先级：属于属于成本型成本型目标，在目标函数中相应目标，在目标函数中相应的部分为：的部分为：p1d1+。（2）第二优先级：）第二优先级：属于属于利润型利润型目标，在目标函数中相应目标，在目标函数中相应的部分为：的部分为：p2d2-。（3）第三优先级：）第三优先级：属于属于利润型利润型目标，同时，在同一优先目标，同时，在同一优先级内，存在权重。权重比为甲：乙级内，存在权重。权重比为甲：乙=80元元/h：20元元/h=4：1。则在目标函。则在目标函数中相应的部分为：数中相应的部分为：p3（4d3-+d4-）。）。第四优先级第四优先级：甲车间加班不超过：甲车间加班不超过20h；第五优先级第五优先级：每月销售电视机不少于：每月销售电视机不少于80台；台；第六优先级第六优先级：加班时间进行控制（权重与三：加班时间进行控制（权重与三一致）。一致）。（4）第四优先级：）第四优先级：属于属于成本型成本型目标，则在目标函数中相应的部分为：目标，则在目标函数中相应的部分为：p4d5+。（5）第五优先级：）第五优先级：属于属于利润型利润型目标，则在目标函数中相应的部分为：目标，则在目标函数中相应的部分为：p5d6-。（6）第六优先级：）第六优先级：属于属于成本型成本型目标，则在目标函数中相应的部分为：目标，则在目标函数中相应的部分为：p6（4d3+d4+）。）。目标规划的模型为：目标规划的模型为：