《运筹学》课件 第6章 目标规划

第六章目标规划线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。实际决策中，衡量方案优劣考虑多个目标生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、提高质量、提高劳动生产率等；生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求量等经济指标外，还要考虑到污染和其它社会因素等。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。目标规划（GoalProgramming）在LP的基础上发展起来的解决多目标规划问题的最有效的方法之一。美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版的《管理模型及线性规划的工业应用》一书中，首先提出的。

处理多种目标的关系，求得更切合实际要求的解只能处理一个目标目标规划线性规划可以在相互矛盾的约束条件下找到满意解满足所有约束条件的可行解找到的最优解是指尽可能地达到或接近一个或若干个已给定的指标值约束条件同等重要可根据实际需要给予轻重缓急或主次之分的考虑第6章内容提要6.1多目标线性规划6.2目标规划的数学模型6.3线形规划的解法6.4目标规划的应用6.1多目标线性规划

多目标线性规划含有多个优化目标的线性规划。线性规划模型只能有一个目标函数，可称为单目标线性规划。多目标线性规划模型具有两个或两个以上的目标函数。例1某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如表所示。试确定计划期内的生产计划，使获得的利润最大。

一、问题的提出产品资源甲乙现有资源

设备4324单位产品利润

54解：设x1、x2分别表示甲、乙两种产品的产量，则可建立线规划模型如下：

maxZ=5x1+4x2

4x1+3x2≤24x1，x2≥0假设：该工厂根据市场需求或合同规定，希望尽量扩大甲产品的生产；减少乙产品的产量。这时又增加了二个目标，则可建立如下的模型：

maxZ1=5x1+4x2

maxZ2=x1minZ3=x24x1+3x2≤24x1，x2≥0

这些目标之间相互矛盾，一般的线性规划方法不能求解

加权系数法为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确定合理的权系数，以反映不同目标之间的重要程度。

优先等级法将各目标按其重要程度分成不同的优先等级，转化为单目标模型。

有效解法寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。二、求解思路加权系数法和优先等级法的结合对每个目标函数确定一个希望达到的期望值(目标值或理想值)；由于各种条件的限制，这些目标值往往不可能全部都达到；对每一个目标函数引入正的或负的偏差变量，分别表示超过或未达到目标值的情况；为区别各目标的重要程度，引入目标的优先等级和加权系数；对所有的目标函数建立约束方程，并入原来的约束条件中，组成新的约束条件；从这组新的约束条件，寻找使组合偏差最小的方案。三、目标规划法

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

欲达到的目标：

总工时限制：2000个；原材料限制：2500kg。满足需求800件；达到质量水平合格率98%；工时成本7000元。1）分析例2某企业生产某种产品的生产方式有四种：正常生产、加班生产、转包合同和雇临时工生产。有关数据如下表所示。在未来的一计划期内，可利用总工时为2000，原材料2500公斤（每件产品耗原料2公斤），产品需求量为800件。要求制订一生产计划，使其尽可能达到以下三项指标：（1）满足需要量；（2）质量水平达到98%；（3）7000元的工时成本。2）组建约束确定决策变量：假设正常生产、加班生产、转包合同和雇临时工生产的量分别为x1，x2，x3和x4。确定约束：工时限制：2x1+2x2+2.5x3+3x4

≤2000；原材料限制：2（x1+x2+x3+x4

）≤2500；非负限制：xi≥0（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%x4≤98%（x1+x2+x3+x4

）；或

99%x1+98%x2+95%x3+90%x4

≥98%（x1+x2+x3+x4

）；

（3）工时成本7000元：可能出现两种可能：20x1+30x2+20x3+24x4≤7000；或20x1+30x2+20x3+24x4

≥7000。（1）满足需求量800件：两种情况不可能同时出现，化为标准型约束。0.98（x1+x2+x3+x4

）≤800；→0.98（x1+x2+x3+x4

）+S1=8000.98（x1+x2+x3+x4

）≥800；→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%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元：20x1+30x2+20x3+24x4≤7000；→20x1+30x2+20x3+24x4+S5=700020x1+30x2+20x3+24x4≥7000。→20x1+30x2+20x3+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%（x1+x2+x3+x4

）（S3和S4中只可能出现一个，至少有一个为零）（3）工时成本7000元：

20x1+30x2+20x3+24x4+S5–S6=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+S3–S4=98%（x1+x2+x3+x4

）

20x1+30x2+20x3+24x4+S5–S6=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+*d—＝0)①

正、负偏差变量②

目标规划的约束形式

（1）绝对约束：也叫客观条件约束，为必须严格满足的约束。（2）目标约束：目标规划特有的约束，也叫软约束。（3）非负约束：要求所有决策变量和偏差量均≥0。如例2中的目标约束为：(1)满足需求800件；(2)达到质量水平合格率98%；(3)工时成本7000元；

(4)绝对约束

（5）非负约束:5）如何确定最终的目标方程？

设想：希望能尽量同时满足三个目标需求，即刚好达到800件产量，质量合格率刚好为98%，工时成本刚好为7000元。此时，所有的正偏差和负偏差量应均为0。但是，实际情况下，正偏差或负偏差量很难同时为0，即实际中不可能刚好同时达到目标要求。但是，应该尽力靠近目标要求，则需实际可能值应尽可能与目标要求值靠近，即使得所有目标约束的偏差量最小。由此，可建立新的目标函数：

原有目标变成了约束（目标约束），如何寻找新的目标方程？数学模型6.2目标规划的数学模型

目标函数的期望值每一个目标函数希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。偏差变量每个目标函数的期望值确定之后，目标的实际值和它的期望值之间就有正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标，它的取值不可能在超过期望值的同时，又没有达到期望值，所以在dk+和dk-中至少有一个必须为零。一、目标规划的基本概念

目标约束引入正、负偏差变量后，对各个目标建立的目标函数方程。原来的目标函数变成了约束条件的一部分，即目标约束(软约束)原来的约束条件称为系统约束(硬约束)。例1中，管理部门提出新要求：第一个目标是实现利润最大，计划部门规定利润目标是20；第二个目标是充分利用设备台时，但尽量少加班；第三个目标做如下规定，甲产品产量希望不少于3单位，乙产品产量比甲产品多2单位。对各目标函数引入正、负偏差变量：

5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2目标达成函数

各个目标函数引入正、负偏差变量，而被列入了目标约束条件。如何使各目标的实际值最接近于各自的期望值，构造一个新的目标函数以求得有关偏差变量的最小值。这个新的目标函数反映了各目标函数的期望值达到或实现的情况，故把这个新的目标函数称为目标达成函数。若要求尽可能达到规定的目标值，则正、负偏差变量dk+、dk-都尽可能最小，将dk+和dk-都列入目标函数中，即minSk=dk++dk-；若希望尽可能不低于期望值(允许超过)，则负偏差变量dk-尽可能的小，而不关心超出量dk+

，故只需将dk-列入目标函数，minSk=

dk-；若允许某个目标低于期望值，但希望不得超过期望值，则正偏差变量dk+

尽可能地小，而不关心低于量dk-，故只需将dk+列入目标函数，minSk=

dk+。优先等级和权数

目标的重要程度不同，用优先等级因子Pk来表示第k等级目标。优先等级因子Pk是正的常数，Pk>>Pk+1。同一优先等级下的目标的相对重要性，赋以不同的加权系数w。例如第一个目标是实现利润最大，其优先级为P1

；第二个目标是充分利用设备台时，但尽量少加班，其优先级为P2

；第三个目标：甲的产量不少于3，乙的产量比甲多2，优先级为P3

。假设：甲产品产量希望不少于3单位的权数为3，乙产品产量比甲产品多2单位的权数为5。

minZ=P1d1-+P2(d2-+d2+

)+P3(3d3-+5d4-

)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0二、目标规划的数学模型

例某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：（1）利润指标为每月16000元，争取超额完成；（2）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过24小时；（4）产量以预计销售量为准。试建立目标规划模型。

小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxa

xixsxad约束条件绝对约束目标约束、绝对约束解最优最满意6.3目标规划的解法

只含有两个决策变量的目标规划模型

线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路首先是在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2

R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3

R2

R1)；如此继续，直到寻找到一个区域RK(RK

RK-1

…

R3

R2

R1)，满足PK级各目标，这时RK即为这个目标规划的最优解空间，其中的任一点均为这个目标规划的满意解。

一、目标规划的图解法

目标规划的图解法的步骤首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=20①4x1+3x2+d2--d2+=24②x1

+d3--d3+=3③-x1+x2+d4--d4+=2④x1,x2,dk-,dk+≥0⑤x1x2①d1+d1-②d2+d2-③d3+d3-④d4-d4+DABC满意解：x1=3,x2=15/4

Minz=P1d1++P2(d2-+d2+)+P3d3-

subjectto 2x1+x2≤11(1)硬约束

x1-x2+d1--d1+=0(2)

x1+2x2+d2--d2+=10(3) 8x1+10x2+d3--d3+=56(4)

x1,x2,di--di+>=0,i=1,2,3(5)例:线性规划模型为024A6810可行域x2非可行域12

B10

86

4

2x1满意解线段数学模型归结为：Minz=P1d1++P2(d2-+d2+)+P3d3-

subjectto 2x1+x2≤11(1)硬约束

x1-x2+d1--d1+=0(2)

x1+2x2+d2--d2+=10(3) 8x1+10x2+d3--d3+=56(4)

x1,x2,di--di+>=0,i=1,2,3ECDGd1-d1+d2+d3+d3-d2-D(10/3,10/3)G(2,4)P2(d2-+d2+)

P1d1+P3d3-

35用图解法求解下列目标规划问题36(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)046834622目标规划与线性规划的数学模型的结构相似可用前述单纯形算法求解目标规划模型：将优先等级Pk视为正常数(大Ｍ法

)正负偏差变量dk+、dk-视为松弛变量以负偏差变量dk-为初始基变量，建立初始单纯形表检验数的计算与LP单纯形表检验数的计算完全相同，即

j=cj-CBiPj最优性判别准则类似于LP的单纯形算法：检验数一般是各优先等级因子的代数和判断检验数的正负和大小二、目标规划的单纯形法

minZ=P1d1-+P2(d2-+d2+)+P3(3d3-+5d4-)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0划为标准型

maxZ=-P1d1--P2(d2-+d2+)-P3(3d3-+5d4-)5x1+4x2+d1--d1+=204x1+3x2+d2--d2+=24x1

+d3--d3+=3-x1+x2+d4--d4+=2x1,x2,dk-,dk+≥0cj

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

j00-P10-P2-P2-3P20-5P2020541-10000002443001-1000031000001-1002-110000001-1d1-d2-d3-d4--P1-P2-3P3-5P3+5P1+4P2-2P3+4P1+3P2+5P30-P10-2P20-3P30-5P3463-检验数

jd1-d2-x1d4--P1-P20-5P331000001-1005041-100-55001203001-1-440050100001-11-10+4P1+3P2+5P30-P10-2P2-5P1-4P2+2P3+5P1+4P2-5P30-5P313--cj00-P10-P2-P2-3P20-5P20

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

jd3+d2-x1d4-0-P20-5P3104/51/5-1/500-110080-1/5-4/54/51-10000414/51/5-1/5000000609/51/5-1/500001-10-P1000-1/5P2-4/5P2+4/5P2-2P2+9P3+P3-P3-3P3-5P3-10--检验数

jd3+d1+x1d4-000-5P3100-1/4-115/4-5/40000303/4001/4-1/4-1100613/4001/4-1/40000807/4001/4-1/4001-10-P1000-P2-P235/4P3+5/4P3-5/4P3-3P3-5P34-832/7cj00-P10-P2-P2-3P20-5P20

值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数

jx2d1+x1d4-000-5P3401001/3-1/3-4/34/3001100-114/3-4/3-1/31/3003100000-110010000-1/31/37/3-7/31-100-P100-P2-P2-5/3P3+5/3P326/3P3-35/3P3-5P3---3检验数

jx2d1+x1d3-000-3P33/70000-1/71/71-13/7-3/732/701001/7-1/7004/7-4/778/700-119/7-9/7001/7-1/718/710001/7-1/700-3/73/700-P1000-P2-P2-3/7P3+3/7P3-3P3-26/7P3-9/7P36.4目标规划的应用经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？minZ=P1d1-+P2(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0

在目标管理中的应用

产品资源甲乙现有资源设备2010140售价108成本56最大需求量610x1x2x1=6x2=10③④d1+d1-d2+d2-CBD(6,5)满意解：x1=6,x2=5设备能力：需求：206+105=170，实际：140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%，甲产品的设备消耗降为20(1-18%)=16.4,

乙产品的设备消耗降为10(1-18%)=8.2。总利润：40单位甲：5单位乙：2生产部目标甲产品的产量：6，成本：5乙产品的产量：5，成本：6技术部目标甲产品的设备单耗：16.4乙产品的设备单耗：8.2销售部目标甲产品的销量：6，单价：10乙产品的销量：5，单价：8minZ=P2d1-+P1(d2-+d2+)x1≤6①x2≤10②5x1+2x2+d1--d1+=40③20x1+10x2+d2--d2+=140④x1,x2,d1-,d1+,d2-,d2+≥0x1x2x1=6x2=10④A(6,2)③d1+d1-d2+d2-E产品资源甲乙现有资源设备2010140售价108成本56最大需求量610降低设备消耗很困难，则调整经营目标的次序P1：充分利用设备能力，且尽量不超过140，P2：总利润不低于40如何安排生产？满意解：x1=6,x2=2利润指标：实际：56+22=34，期望：

40实现目标P1和P2，增加甲乙产品的单位利润:增长率(40-34)/34=18%产品售价由市场决定，为提高利润，应从降低成本入手：甲产品的成本由5降为10-5(1+18%)=4.12,

乙产品的成本由6降为8-2(1+18%)=5.63。总利润：40单位甲：5.88单位乙：2.26生产部目标甲产品的产量：6，成本：4.12乙产品的产量：2，成本：5.63技术部目标甲产品的设备单耗：20乙产品的设备单耗：10销售部目标甲产品的销量：6，单价：10乙产品的销量：2，单价：8某副食品批发店预测某商品今后4月的购进与售出价格如表：

在库存管理中的应用

月份1234成本(购价+库存)2.62.52.72.8售价2.92.73.13.3假设：该商品供不应求，最大销量受仓库容量限制；

正常库容3吨，机动库容2吨；月初批发销货，月中采购进货，进货所需资金完全来自销售收入；

1月初库存量2吨，成本2.5千元/吨，该月初无现金。经营目标：(1)每月都使用正常库容，尽量不超容；

(2)每月下旬都应储备1千元以备急用；

(3)4个月总盈利最大。决策变量：xj

第j月的采购量，yj第j月的销售量绝对约束条件各月销量约束：月初售货，各月销量不能多于其期初库存量。1月

y1≤22月

y2

≤2–y1+x1

→y1

+y2

–x1

≤23月

y3

≤2–y1

+x1

–y2

+x2

→y1

+y2

+y3

–x1

–x2

≤24月

y4≤2–y1

+x1

–y2

+x2

–y3

+x3

→y1

+y2

+y3

+y4

–x1

–x2

–x3

≤2各月采购量约束：每月采购量依赖月初的售货收入。1月

2.6x1

≤2.9y1→–

2.9y1