管理运筹学讲义：目标规划

运筹学资料

SHUFE

运 筹 学 课 件

运 筹 帷 幄 之 中 Multiple Objective Programming

决 胜

多目标规划

千 里 之 外

1

上海电力学院管理与人文学院

运筹学资料

SHUFE

第五章

多目标规划

线性规划的局限性 只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大 或最小值的问题。

实际决策中，衡量方案优劣考虑多个目标 生产计划决策中，通常要考虑产值、利润、满足市场需求、降低消耗、 提高质量、提高劳动生产率等； 生产布局决策中，除了要考虑运输费用、投资、原料供应、产品需求 量等经济指标外，还要考虑到污染和其它社会因素等 。 这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定 量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。

目标规划(Goal Programming) 在LP的基础上发展起来的解决多目标规划问题的最有效的方法之一。 美国经济学家查恩斯(A.Charnes)和库柏(W.W.Cooper)在1961年出版 的《管理模型及线性规划的工业应用》一书中，首先提出的。2

上海电力学院管理与人文学院

运筹学资料

SHUFE

第一节

多目标线性规划

一、问题的提出 多目标线性规划 含有多个优化目标的线性规划。 线性规划模型只能有一个目标函数，可称为单目标线性规划。 多目标线性规划模型具有两个或两个以上的目标函数。

例题 某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品 的技术消耗定额及单位产品的利润如表所示。试确定计划期内 的生产计划，使获得的利润最大。资源 设备 单位产品利润

产品

甲453

乙34

现有资源24

上海电力学院管理与人文学院

运筹学资料

SHUFE

第一节

多目标线性规划

解： 设x1 、 x2 分别表示甲、乙两种产品的产量，则可建立线规划模型如下：maxZ=5x1+4x2 4x1+3x2 ≤24 x1,x2 ≥0

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

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

上海电力学院管理与人文学院

运筹学资料

SHUFE

第一节

多目标线性规划

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

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

有效解法 寻求能够照顾到各个目标，并使决策者感到满意的解。由决策 者来确定选取哪一个解，即得到一个满意解。但有

效解的数目 太多而难以将其一一求出。

5

上海电力学院管理与人文学院

运筹学资料

SHUFE

第一节

多目标线性规划

三、目标规划法

加权系数法和优先等级法的结合 对每个目标函数确定一个希望达到的期望值(目标值 或理想值); 由于各种条件的限制，这些目标值往往不可能全部都 达到； 对每一个目标函数引入正的或负的偏差变量，分别表 示超过或未达到目标值的情况； 为区别各目标的重要程度，引入目标的优先等级和加 权系数； 对所有的目标函数建立约束方程，并入原来的约束条 件中，组成新的约束条件； 从这组新的约束条件，寻找使组合偏差最小的方案。6

上海电力学院管理与人文学院

运筹学资料

SHUFE

第二节 目标规划的数学模型

一、目标规划的基本概念 目标函数的期望值 每一个目标函数希望达到的期望值(或目标值、理想值)。 根据历史资料、市场需求或上级部门的布置等来确定。

偏差变量 每个目标函数的期望值确定之后，目标的实际值和它的期望值 之间就有正的或负的偏差。 正偏差变量dk+ 表示第k个目标超过期望值的数值； 负偏差变量dk- 表示第k个目标未达到期望值的数值。 同一目标，它的取值不可能在超过期望值的同时，又没有达到 期望值，所以在dk+ 和dk- 中至少有一个必须为零。

7

上海电力学院管理与人文学院

运筹学资料

SHUFE

第二节 目标规划的数学模型

目标约束 引入正、负偏差变量后，对各个目标建立新的目标函数方程。 ckj x j d k d k E * j 1 n

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

5x1+4x2 +d1-- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4-- d4+ = 28

上海电力学院管理与人文学院

运筹学资料

SHUFE

第二节 目标规划的数学模型

目标达成函数 各个目标函数引入正、负偏差变量，而被列入了目标约束条件。 如何使各目标的实际值最接近于各自的期望值，构造一个新的 目标函数以求得有关偏差变量的最小值。 这个新的目标函数反映了各目标函数的期望值达到或实现的情 况，故把这个新的目标函数称为目标达成函数。 若要求尽可能达到规定的目标值，则正、负偏差变量dk+、dk-

都 尽 可 能 最 小 ， 将 dk+ 和 dk- 都 列 入 目 标 函

数 中 ， 即 minSk=dk++dk- ; 若希望尽可能不低于期望值(允许超过),则负偏差变量dk- 尽 可能的小，而不关心超出量dk+ ,故只需将dk- 列入目标函数， minSk= dk- ; 若允许某个目标低于期望值，但希望不得超过期望值，则正 偏差变量dk+ 尽可能地小，而不关心低于量dk- ,故只需将dk+ 列入目标函数，minSk= dk+ 。9

上海电力学院管理与人文学院

运筹学资料

SHUFE

第二节 目标规划的数学模型

优先等级和权数 目标的重要程度不同，用优先等级因子Pk 来表示第k等级目标。 优先等级因子Pk 是正的常数，Pk >> Pk+1 。 同一优先等级下的目标的相对重要性，赋以不同的加权系数w。 例如 第一个目标是实现利润最大，其优先级为P1 ; 第二个目标是充分利用设备台时，但尽量少加班，其优先级为P2 ; 第三个目标：甲的产量不少于3,乙的产量比甲多2,优先级为P3 。 假设： 甲产品产量希望不少于3单位的权数为3, 乙产品产量比甲产品多2单位的权数为5。

minZ= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- ) 5x1+4x2 +d1-- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ ≥010

上海电力学院管理与人文学院

运筹学资料

SHUFE

第二节 目标规划的数学模型

二、目标规划的数学模型 min Z Pk ( wkl d l wkl d l ) k 1 l 1 K Lk

绝对约束 目标约束 非负性约束

a xj 1 ij n j 1

n

j

( , )bi

i 1,2,..., m k 1,2,..., K

* ckj x j d k d k Ek

x j , d k , d k 0

j 1,2,..., n

11

上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法

一、目标规划的图解法 只含有两个决策变量的目标规划模型 线性规划是在可行域中寻找一点，使单个目标极大或极小； 目标规划则是寻找一个区域，这个区域提供了相互矛盾的目 标集的折衷方案。 目标规划的图解法的思路 首先是在可行域内寻找一个使P1级各目标均满足的区域R1; 然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2 R1); 接着再在R2中寻找一个满足P3级各目标的区域R3(R3 R2 R1); 如此继续，直到寻找到一个区域RK(RK RK-1 … R3 R2 R1), 满足PK级各目标，这时RK即为这个目标规划的最优解空间，其 中的任一点均为这个目标规划的满意解。上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法

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

x1+3x2 +d2 2 ②B ③ d4+ ④ x1 +d3- - d3+ = 3 ③ - x1 + x2 +d4- - d4+ = 2 ④ d4d3+ d3x1 , x2 ,dk- , dk+ ≥0 ⑤ ①

D

C

d2+

满意解：x1=18/7, x2=32/713

d2d1+ d1-

A

x1

上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法

二、目标规划的单纯形法

目标规划与线性规划的数学模型的结构相似 可用前述单纯形算法求解目标规划模型： 将优先等级Pk视为正常数(大M法 ) 正负偏差变量dk+、dk-视为松弛变量 以负偏差变量dk-为初始基变量，建立初始单纯形表 检验数的计算与LP单纯形表检验数的计算完全相同， 即 j= cj - CBi Pj 最优性判别准则类似于LP的单纯形算法： 检验数一般是各优先等级因子的代数和

判断检验数的正负和大小14

上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法

minZ=P1 d1-+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 划为标准型 maxZ=-P1 d1--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+ ≥015

上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法cjXB d1d2d3d4b 20 24 3 2 0 x1 5 4 1 -1 0 x2 4 3 0 1 - P1 d11 0 0 0 0 d1+ -1 0 0 0 - P2 - P2 d2- d2+ 0 0 1 -1 0 0 0 0- 3P2

CB - P1 - P2 - 3P3 - 5P3

d30 0 1 0

0 d3+ 0 0 -1 0

- 5P2

d40 0 0 1

0 d4+ 0 0 0 -1

值 4 6 3 -

检验数 j- P1 - P2 0 - 5P3 d1d2x1 d45 12 3 5

+5 P1 +4 P1 0 +4 P2 +3 P2 -2 P3 +5 P30 0 1 0 4 3 0 1 1 0 0 0

-P1

0-2P2

0-3P3

0-5P3 0 0 0 1 0 -5P3 0 0 0 -1 1 3 -

-1 0 0 0 -P1

0 1 0 0 0

0 -1 0 0

-5 -4 1 1

5 4 -1 -1

检验数 j

0 +4 P1 0 +3 P2 +5 P3

-5 P1 +5 P1 -2P2 -4 P2 +4 P2 +2 P3 -5 P316

上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法cjXB d3+ d2x1 d4b 1 8 4 6 0 x1 0 0 1 0 0 0 x2 4/5 -1/5 4/5 9/5 - P1 d11/5 -4/5 1/5 1/5 - P1 0 - P2 - P2 d1+ d2- d2+ -1/5 0 0 4/5 1 -1 -1/5 0 0 -1/5 0 0 0-2P2 -3P3 -5P3- 3P2

CB 0 - P2 0 - 5P3

d3-1 0 0 0

检验数 j0 0 0 - 5P3 d3+ d1+ x1 d43 10 6 8

0 d3+ 1 0 0 0 0

- 5P2

d40 0 0 1 0

0 d4+ 0 0 0 -1

值

10 -

-1/5P2 -4/5P2 +4/5P2 +9P3 +P3 -P3

检验数 j

0 0 1 0 0

3/4 -1/4 3/4 7/4

0 -1 0 0 - P1

0 1 0 0 0

1/4 5/4 1/4 1/4-P2

-1/4 -5/4 -1/4 -1/4-P2

-1 0 0 0

1 0 0 0 0

0 0 0 1 0

0 4 0 8 0 -1 32/7

35/4P3

+5/4P3 -5/4P3 -3P317

-5P3

上海电力学院管理与人文学院

运筹学资料

SHUFE

第三节 目标规划的解法cjXB x2 d1+ x1 d4b 4 11 3 1 0 x1 0 0 1 0 0 0 x2 1 0 0 0 0 - P1 d10 -1 0 0 - P1 0 - P2 d1+ d20 1/3 1 4/3 0 0 0 -1/3 0-P2

CB 0 0 0 - 5P3

- P2 d2+ -1/3 -4/3 0 1/3-P2

0 d3- d3+ -4/3 4/3 -1/3 1/3 -1 1 7/3 -7/3

- 3P2

- 5P2

检验数 j0 0 0 - 3P3 x2 32/7 d1+ 78/7 x1 18/7 d3- 3/7

d40 0 0 1 0

0 d4+ 0 0 0 -1

值 3

-5/3P3 +5/3P326/3P3 -35/3P3

-5P3

0 0 1 0 0

1 0 0 0 0

检验数 j

0 -1 0 0 - P1

0 1 0 0 0

1/7 9/7 1/7 -1/7-P2

-1/7 -9/7 -1/7 1/7-P2

0 0 0 1 0

0 0 0 -1

4/7 1/7 -3/7 3/7 0

-4/7 -1/7 3/7 -3/7

-3/7P3 +3/7P318

-3P3 -26/7P3 -9/7P3

上海电力学院管理与人文学院

运筹学资料

SHUFE

第四节 目标规划的应用产品

在目标管理中的应用资源

甲

乙

现有资源

20 10 140 设备 10 8 售价 5 6 成本 6 10 最大需求量 经营目标 x2 x1 =6 P1:总利润不低于40, ④ ③ P2:充分利用设备能力，且尽量不超过140 D C x2 =10 如何安排生产？ minZ= P1 d1- + P2 (d2-+d2+ ) x1 ≤6 ① x2 ≤10 ② B (6,5) d2+ + 5x1 + 2 x2 +d1- -d1+ =40 ③ d1 20x1 +10 x2 +d2- -d2+ = 140 ④ d2- -, d + , d -, d + ≥0 x1 x 1 , x2, d1 1 d1 2 219

上海电力学院管理与人文学院

运筹学资料

SHUFE

第四节 目标规划的应用

满意解：x1 =6, x2 = 5 设备能力：需求：20 6+10 5=170,实际：140 实现目标P1和P2,降低甲乙产品的设备消耗:降低率(170-140)/170=18%, 甲产品的设备消耗降为20 (1-18%)=16.4, 乙产品的设备消耗降为10 (1-18%)=8.2。 生产部目标 甲产品的产量：6,成本：5 乙产品的产量：5,成本：6 总利润：40 单位甲：5 单位乙：2 技术部目标 甲产品的设备单耗：16.4 乙产品的设备单耗： 8.2 销售部目标 甲产品的销量：6,单价：10 乙产品的销量：5,单价： 820

上海电力学院管理与人文学院

运筹学资料

SHUFE

第四节 目标规划的应用

降低设备消耗很困难，则调整经营目标的次序 P1:充分利用设备能力，且尽量不超过140, P2:总利润不低于40 如何安排生产？资源 产品

甲 20 10 5 6

乙 10 8 6 10

现有资源 140x2 ④ ③ E x1 =6 d1+ d2+ x2 =10

设备 售价 成本 最大需求量

minZ= P2 d1- + P1 (d2-+d2+ ) x1 ≤6 x2 ≤10 5x1 + 2 x2 +d1- -d1+ =40 20x1 +10 x2 +d2- -d2+ = 140 x1 , x2, d1-, d1+ , d2-, d2+ ≥0

① ② ③ ④

d1d2-

A (6,2)x121

上海电力学院管理与人文学院

本文来源：https://www.bwwdw.com/article/r4nj.html