7.运筹学之目标规划(胡运权版)

线性规划问题是讨论一个给定的线性目标函数在一组线性约束条件下的最大值或最小值问题。对于一个实际问题,管理科学者根据管理层决策目标的要求，首先确定一个目标函数以衡量不同决策的优劣，且根据实际问题中的资源、资金和环境等因素对决策的提出相应的约束条件以建立线性规划模型；然后用计算机软件求出最优方案并作灵敏度分析以供管理层决策之用。而在一些问题中,决策目标往往不只一个，且模型中有可能存在一些互相矛盾的约束条件的情况，用已有的线性规划的理论和方法无法解决这些问题。因此，1961年美国学者查恩斯（A。Charnes）和库柏(W。W。Coopor）提出了目标规划的概念与数学模型，以解决经济管理中的多目标决策问题。

我们将通过几个例子来说明在实际应用中线性规划存在一系列的局限性.

例1 某厂生产A、B两种产品每件所需的劳动力分别为4个人工和6个人工，所需设备的单位台时均为1。已知该厂有10个单位机器台时提供制造这两种产品，并且至少能提供70个人工。又，A、B产品的利润，每件分别为300元和500元。试问：该厂各应生产多少件A、B产品，才能使其利润值最大?

解 设该厂能生产A、B产品的数量分别为x1,x2件，则有

1

maxz300x1500x2x1x210 s.. t4x16x270x0, j1,2.j图解法求解如下：

由上图可得，满足约束条件的可行解集为,即机时约束和人工约束之间产生矛盾，因而该问题无解.但在实际中,该厂要增加利润，不可能不生产A、B两种产品,而由线性规划模型无法为其找到一个合适的方案。

例2 某厂为进行生产需采购A、B两种原材料，单价分别为70元/公斤和50元/公斤。现要求购买资金不超过5000元，总购买量不少于80公斤,而A原材料不少于20公斤。问如何确定最好的采购方案（即花掉的资金最少，购买的总量最大）?

解 这是一个含有两个目标的数学规划问题。设x1,x2分别为购买两种原材料的公斤数,f1x1,x2为花掉的资金，f2x1,x2为购买的总量.建立该问题的数学模型形式如下：

2

minf1x1,x270x150x2 maxf2x1,x2x1x2

 70x150x25000 xx8012s..t x120 x1,x20

对于这样的多目标问题，线性规划很难为其找到最优方案。极可能的结果是,第一个方案使第一目标的结果值优于第二方案，同时第二方案使第二目标的结果值优于第一方案。也就是说很难找到一个最优方案，使两个目标的函数值同时达到最优。另外，对于多目标问题，还存在有多个目标存在有不同重要程度的因素，而这也是线性规划所无法解决的。

在线性规划的基础上，建立了一种新的数学规划方法——目标规划法，用于弥补线性规划的上述局限性。总的来说，目标规划和线性规划的不同之处可以从以下几点反映出来：

1、线性规划只能处理一个目标，而现实问题往往存在多个目标。目标规划能统筹兼顾地处理多个目标的关系，求得切合实际需求的解。

2、线性规划是求满足所有约束条件的最优解。而在实际问题中，可能存在相互矛盾的约束条件而导致无可行解，但此时生产还得继续进行。即使存在可行解，实际问题中也未必一定需要求出最优解。目标规划是要找一个满意解,即使在相互矛盾的约束条件下也找到尽量满足约束的满意解，即满意方案。

3

3、线性规划的约束条件是不分主次地等同对待，这也并不都符合实际情况。而目标规划可根据实际需要给予轻重缓急的考虑。

§2 目标规划的基本概念与数学模型

§2。1 基本概念

在这一小节里介绍与目标规划有关的基本概念。 1．偏差变量

对于例1，造成无解的关键在于约束条件太死板。设想把约束条件“放松”，比如占用的人力可以少于70人的话，机时约束和人工约束就可以不再发生矛盾.在此基础上,引入了正负偏差的概念，来表示决策值与目标值之间的差异。

di—-正偏差变量，表示决策值超出目标值的部分，目标规划里规

定di0;

di——负偏差变量，表示决策值未达到目标值的部分，目标规划

里规定di0。

实际操作中，当目标值(也就是计划的利润值）确定时，所作的决策可能出现以下三种情况之一：

（1）决策值超过了目标值（即完成或超额完成计划利润值）,表示为di0,di0；

4

(2）决策值未达到目标值（即未完成计划利润值），表示为di0，

di0；

（3）决策值恰好等于目标值(即恰好完成计划利润指标），表示为

di0，di0。

以上三种情况，无论哪种情况发生，均有di •di=0.

2．绝对约束与目标约束

绝对约束也称系统约束，是指必须严格满足的等式约束和不等式约束，它对应于线性规划模型中的约束条件。

目标约束是目标规划所特有的。当确定了目标值，进行决策时，允许与目标值存在正或负的偏差。因而目标约束中加入了正、负偏差变量。

如，例1中假定该企业计划利润值为5000元,那么对于目标函数

maxz300x1500x2，可变换为

300x1500x2didi5000.

该式表示决策值与目标值5000之间可能存在正或负的偏差（请读者分别按照上面所讲的三种情况来理解）.

绝对约束也可根据问题的需要变换为目标约束。此时将约束右端项看作所追求的目标值。如，例1中绝对约束x1x210，可变换为目标约束x1x2didi10.

3．目标规划的目标函数

5

对于满足绝对约束与目标约束的所有解，从决策者的角度来看,判断其优劣的依据是决策值与目标值的偏差越小越好.因此目标规划的目标函数是与正、负偏差变量密切相关的函数，我们表示为

minzfdi,di.它有如下三种基本形式：

（1）要求恰好达到目标值，即正、负偏差变量都尽可能地小.此

时，构造目标函数为:minzdidi

（2）要求不超过目标值，即允许达不到目标值，正偏差变量尽可能地小。此时构造目标函数为：minzdi

（3）求超过目标值，即超过量不限，负偏差变量尽可能地小。此

时构造目标函数为：minzdi

4．优先次序系数与权系数

一个规划问题往往有多个目标。决策者在实现这些目标时，存在有主次与轻重缓急的不同。对于有K级目标的问题，按照优先次序分别赋予不同大小的大M系数：M1，M2，，MK。M1，M2，，MK为无穷大的正数,并且,M1

M2MK（“

\"符号表示“远大于”）,

这样，只有当某一级目标实现以后（即目标值为0） ，才能忽略大M的影响，否则目标偏离量会因为大M的原因而无穷放大。并且由于

MkMk1，所以只有先考虑忽略Mk影响（实现第k级目标）后，才

能考虑第k1级目标。实际上这里的大M是对偏离目标值的惩罚系数，优先级别越高，惩罚系数越大。

权系数i用来区别具有相同优先级别的若干目标.在同一优先级

6

别中，可能包含有两个或多个目标，它们的正负偏差变量的重要程度有差别，此时可以给正负偏差变量赋予不同的权系数i和i。

各级目标的优先次序及权系数的确定由决策者按具体情况给出。

§2。2 目标规划的数学模型

综上所述，目标规划模型由目标函数、目标约束、绝对约束以及变量非负约束等几部分构成。目标规划的一般数学模型为：

目标函数 minZMkkldlkldl

k1l1nKLcxdd目标约束 ijjllgl l1,2,j1L

绝对约束

ax,b i1,2,ijjij1nm

非负约束 xj0 j1,2,n

d,d kk0 k1,2,,K

例3 在例1中,假定目标利润不少于15000元，为第一目标；占用的人力可以少于70人，为第二目标。求决策方案。

解 按决策者的要求分别赋予两个目标大M系数M1,M2.列出模型如下：

7

 minzM1d1M2d2 300x1500x2d1d115000 4x6xdd122270t s..  x1x210 x,x,d,d0 i1,2,3. 12ii

例4 某纺织厂生产A、B两种布料，平均生产能力均为1千米/小时，工厂正常生产能力是80小时/周。又A布料每千米获利2500元,B布料每千米获利1500元。已知A、B两种布料每周的市场需求量分别是70千米和45千米。现该厂确定一周内的目标为:

第一优先级：避免生产开工不足; 第二优先级：加班时间不超过10小时； 第三优先级:根据市场需求达到最大销售量； 第四优先级：尽可能减少加班时间. 试求该问题的最优方案。

解 设x1,x2分别为生产甲、乙布料的小时数。对于第三优先级目标，根据A、B布料利润的比值2500:15005:3，取二者达到最大销量的权系数分别为5和3。该问题的目标规划模型为：

minzM1d1M2d2M35d33d4M4d1 x1x2d1d180 x1x2d2d290 s..t x1d3d370 xdd45244 x,x,d,d0 i1,12ii

,4.

8

综上所述，目标规划建立模型的步骤为: 1、

根据问题所提出的各目标与条件,确定目标值,列出目标

约束与绝对约束；

2、根据决策者的需要将某些或全部绝对约束转换为目标约束，方法是绝对约束的左式加上负偏差变量和减去正偏差变量； 3、给各级目标赋予相应的惩罚系数Mk（k1,2,K)，Mk为无穷大的正数，且M1

M2MK；

4、对同一优先级的各目标，再按其重要程度不同，赋予相应的权系数kl；

5、根据决策者的要求，各目标按三种情况取值:①恰好达到目标值，取didi②允许超过目标值，取di③不允许超过目标值,取di；然后构造一个由惩罚系数、权系数和偏差变量组成的、要求实现极小化的目标函数。

§3 目标规划的求解

3。1 图解法

只有两个决策变量的目标规划数学模型，可以使用简单直观的图解法求解。其方法与线性规划图解法类似，先在平面直角坐标系第一象限内作出各约束等式或不等式的图象，然后由绝对约束确定了可行域,由目标约束和目标函数确定最优解或满意解.

9

对于绝对约束，与线性规划中的约束条件画法完全相同。对于目标约束方程,除作出直线外，还要在直线上要标出正负偏差变量的方向，其可行域方向取决于目标函数中对应目标.另外，目标规划是在前一级目标满足的情况下再来考虑下一级目标，很有可能尽可能满足目标的解不是可行解（即非可行解）,而是权衡以后得出的最优解-—满意解.因而在目标规划里称求得的解为满意解。 注意在求解的时候，把绝对约束作最高级别考虑。

例5 用图解法求解目标规划问题

 minzM1d1d1M2d2M3d3 x1x2d1d10 3x15x2d2d215 s..t 4x13x2d3d324 xx712 x1,x2,di,di0 i1,2,3.

解 在平面直角坐标系第一象限内作出各约束条件的图像,目标约束要在直线旁标上di和di+。

10

首先，绝对约束x1x27确定了可行解范围在三角形OEF内; 根据第一级目标，要求实现mind1d1（恰好），因而可行解范围缩小到线段OC上；

根据第二级目标，要求实现mind2(不少于)，在线段OC上，取d20的点A，此时可行解范围缩小到线段AC上；

根据第三级目标，要求实现mind3,在线段AC上,取d30的点B，此时解的范围缩小到线段AB上。

所以，线段AB上的所有点为满意解。可求得A（15/8，15/8)，B(24/7，24/7）.

2。winQSB求解目标规划

[例]求解目标规划：

minzPd11P2d2P3d3x1x2d1d110xdd2227x d3d381s..t6x12x2603x4x6021x,x,d,d0,j1,2,312jj第1步：生成表格

选择“程序winQSBGaol ProgrammingFileNew Program\"，弹出对话框:

11

输入:目标约束数(Number of Goals）“3” 决策变量数（Number of Variables）“2” 系统约束数（Number of Constraints）“2” 目标要求（Default Goal Criteria）：因3个目标不同，第1、2个目标极大化，第3个目标极小化,可任选1个按钮，之后再进行调整。

数据输入方式（Data Entry Format），采取默认的表格形式. 变量数据类型（Default Variable Type）：默认的为非负连续型。 单击“OK”，生成表格:

第2步：修改目标要求，输入数据

从系统菜单选择“EditGoal Criteria and Names”，弹出对话框：

12

选择第3个目标约束，将Maximize改为Minimeze，“OK”，输入数据，得：

第3步：求解

从菜单选择“Solve and AnalyzeSolve the Problem”，生成如下运行结果：

13

决策变量x1=6.67，x2=10,目标值：G1=16。67，G2=10，G3=6。67

三、目标规划上机程序

1、运行“Goal programming”,出现图7所示界面

图 7

2、运行file菜单下的new problem 命令，出现图8所示界面。 图8中各项目含义：

Number of Goals：目标的个数，即目标函数优先级的个数

Number of Variables：变量的个数，为决策变量个数和偏差变量个数之和。 其余项目含义同图2。

如求解下列目标规划问题按图8输入，输入结果如图9所示：

minzP1(d1d1)P2d210x112x2d1d162.5x12x2d2d2102x1x28x,x,d,d0(i1,,2)12ii

图 8

14

图 9

3、输入完成确定后出现如图10所示界面 图10中各行含义如下:

第一行:变量代号，具体含义自己定义，如本例中可定义如下：

x1 — x1；x2 - x2；x3 - b1-；x4 - b1+;x5 — b2—；x6 - b2+

其余各项目含义同图4。

图 10

4、将数据输入图10后，结果如图11所示。

5、图11输入完成后，按运行键（同图5所示）.运行结果如图12所示。图12种各项目含义同图6。

15

图 11

图 12

习题

7。1 判断以下目标规划的目标函数是否正确。 (1）maxzdd (2)minzdd （3)maxzdd （4）minzdd

7。2 用图解法求解下列目标规划问题:

16

minzM1d1M2d3M3d2;minzM1d3M2d2M3d1d1x12x2d1d14;6x12x2d1d124;（1）x12x2d2d24; （2）x1x2d2d25;s..ts..tx12x2d3d38;5x2d3d315;x,x,d,d0(i1,2,3).x,x,d,d0(i1,2,3).12ii12iiminzM1(d1d1)M2(d2d2)

minzM1d1M2d2M3d3x1x24;x12x26;（3）s..t2x13x2d1d118;3x2xdd18;1222x,x,d,d0(i1,2).12ii3 2xxdd1211210;2 x1d2d260; （4) s..t x2d3d345; x80;2 x1,x2,di,di0.7.3 某厂组装两种产品，有关数据如表7—1。要求确定两种产品的日生产计划，并满足: （1）不得使装配线超负荷生产; (2）不得有剩余产品；

（3）日产值尽可能达到5000元。 试找出满意解，并用图示说明之。

表7—1 产品 A B

7.4 上题中，若将目标要求改为：

单件组装工日销量(件） 时 1。1 1。3 70 60 件） 40 150 60 能力 产值（元/日装配 17

（1）尽可能发挥工厂的装配能力；

（2）尽可能满足市场的需求，并使产量与销量保持一致； （3）装配生产线可加班，但时数不得超过30小时； （4）尽可能使日产值最大。

试定出两种产品满意的日产计划。

7。5 已知目标规划问题的约束条件如下:

2x1x2d1d12; s..t2xd13x22d26; x16;x1,x2,di,di0(i1,2) 求在下述各目标函数下的满意解：

（1）minzM1(d1d1d2d2) (2）minz2M1(d1d1)M2(d2d2) （3）minzM1(d1d1)2M2(d2d2) （4）minzM1(d1d1)M2(d2d2)

7。6 某公司要将一批货从三个产地运到四个销地，有关数据如表7-2。现要求订出调运计划，且依次满足：

(1）B4要保证供应；

（2）其余销地的供应量不低于80％； （3）A2给B2的供应量不低于150； （4）A2尽可能少给B1；

18

（5）销地B1、B2的供应量尽可能保持平衡。 要求：

（1)建立使总运费最小的目标规划模型？

（2）建立该问题的电子表格模型，并用winqsb进行求解。 表7—2 产销地 A1 A2 A3 需求量

7。7 某公司的管理层已经为其公司的两种新产品制定了各自的市场目标，具体地说，产品1必须占据15%的市场份额，而产品2必须有10%的市场份额。为了获得市场，准备开展三次广告活动，其中两个广告是分别针对产品1和产品2的,而广告3是为了提高整个公司及其产品的声誉。以x1,x2,x3分别表示分配在三个广告上的资金（以百万元为单位），相应的两种产品取得的市场份额估计值（以百分比表示)为

产品1的市场份额=0.5x10.2x3 产品2的市场份额=0.3x10.2x3

广告总预算为5500万元，其中必须有至少1000万投资在第

19

地 B1 7 2 6 B2 3 6 4 B3 7 5 2 B4 9 11 5 供应量 560 400 750 320 240 480 380 三个广告上。如果两个产品的市场份额目标不能同时实现，管理层认为两种产品上目标偏离的严重性是同等的.在上述条件下,管理曾希望得到最有效的资金分配方法。试：

（1）建立该问题的数学模型；

(2)建立电子表格模型，并用winqsb进行求解.

7.8 某发展中国家有1500万亩共用耕地,该过目前正计划将这些土地分配给三种基本的农作物。生产的农产品一部分出口以换取紧缺的外币，剩下的是居民的食粮。种植这些农作物也为国家相当一部分人提供了就业。因此，在分配土地时要考虑的主要因素为：（1）能获得的外币，（2）可供养的居民数，（3）种植农作物需要的劳动力。表7-3给出了各种农作物每千亩产量对三个因素的贡献，表的最后一列为给三个因素建立的目标.在估计各个目标的重要性时，认为下面的三个因素是同等重要的，或者说如果目标不能达到的话，问题的严重性是同等的:（1）外币数量少于目标值100元,（2）供养目标中有一个人不能得到足够的食物，(3）需要的劳动力比劳动力目标少或多一人。试：

（1）建立该问题的数学模型；

（2）建立电子表格模型，并用winqsb进行求解;

（3)对该问题进行如下的what-if分析：（a）若改变各因素的重要程度,三因素的罚系数分别设为7，5，3，会产生怎样的结果;（b）若将外币数量的最少目标值100改为200，保持原来的罚数权重不变

20

的情况，会有什么影响？

表7—3

每千亩底的贡献 因素 目标 1 2 3 外币 3000 5000 4000 70000000 可供养的居150 75 100 1750000 民 可雇佣的居10 15 12 =200000 民

21