课件实验04目标

目标规划

Goal

Programming（GP）第四章目标规划——多目标线性规划目标规划

Goal

Programming（GP）目标规划问题及其数学模型目标规划（

Goal

Programming

）方法是Charnes和Cooper于1961年提出的，目前已成为一种简单、实用的处理多目标决策问题的方法，是多目标决策中应用最为广泛的一种方法。为了学习和初步掌握目标规划与线性规划在处理问题的方法上的区别，我们分析如下案例——目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题背景材料：王老板过去一直从事专业家具制造，主要生产桌子、椅子两种家具，王老板的经营环境主要受到两种资源——木工和油漆工每天的有效工作时间的限制。王老板过去的经营环境条件如下：1、每天木工和油漆工的总有效工作时间分别为11小时和10小时。2、每生产一把椅子需要2小时的木工、1小时的油漆工。3、每生产一张桌子需要1小时的木工、2小时的油漆工。4、每生产一把椅子和一张桌子分别可获利润8元、10元。为了追求最大利润，王老板建立了此问题的线性规划模型并解得最优方案：每天生产椅子4

把，桌子3

张，获最大利润62

元。目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题王老板过去一直以如何计划两种家具的生产量才能获得最大总利润为其生产、经营的唯一目标。然而，市场经济环境下新的问题出现了，它迫使王老板不得不考虑…...首先，根据市场信息，椅子的销售量已有下降的趋势，故应果断决策减少椅子的产量，其产量最好不大于桌子的产量。其次，市场上找不到符合生产质量要求的木工了，因此决不可能考虑增加木工这种资源来增加产量，并且由于某种原因现有木工决不可能加班。再其次，应尽可能充分利用油漆工的现有有效工作时间，但油漆工希望最好不加班。最后，新王老板考虑最好达到并超过预计利润指标56元。目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题讨论——1、王老板现在的生产、经营问题——多个目标的生产问题2、决策变量——椅子、桌子的生产量x1，x2引入一种新的变量——正、负偏差变量d

+、d

-，d

+、d

-≥0。目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题讨论——3、约束条件——绝对约束、目标约束——硬约束、软约束。4、目标函数——优先因子（优先等级）P1，P2，…，规定Pk>>Pk+1，k=1，2，…。表示Pk比Pk+1有更大的优先权。这意味着当目标与目标之间发生冲突时应按其优先等级来实现。目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题目标规划独特的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋予相应的优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此，目标规划的目标函数只能是min Z=f（

d+，d-

）。其基本形式有三种：目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题要求恰好达到目标值，即正、负偏差变量都要尽可能地小min

Z

=

f（

d

++

d

-

）要求不超过目标值，即允许达不到目标值，即正偏差变量要尽可能地小min

Z

=

f（

d

+）要求超过目标值，即超过量不限，但必须是即负偏差变量要尽可能地小min

Z

=

f（

d

-）目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题归纳上面的分析——新王老板应在木工每天的有效工作时间受到严格限制的基础上按顺序考虑其他目标的实现。目标优先等级：P1——椅子的产量最好不大于桌子的产量。P2——尽可能充分利用油漆工的有效工作时间，但希望不加班。P3——总利润最好不小于56元。多个目标！每个目标都带有柔性！目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题决策变量：x1——椅子的产量，

x2——桌子的产量。各个目标偏的差变量：P

等级正、负偏差变量——d

+、d

-1

1

1P

等级正、负偏差变量——d

+、d

-2

2

2P

等级正、负偏差变量——d

+、d

-3

3

3x

、x

、d

+、d

-、d

+、d

-

、d

+、d

-

≥

01

2

1

1

2

2

3

3目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题约束条件：（1）绝对约束——

2x1+

x2

≤

11（2）目标约束——

x

-

x +

d

-

-

d

+

=

01

2

1

11x

+

2x +

d

-

-

d

+

=

101

2

2

221

2

3

38x

+10x +

d

-

-

d

+

=

563（

P

）（

P

）（

P

）目标函数：+

-

+

-min

Z

=

P1

d1

+

P2（

d2

+

d2

）+

P3

d3目标规划

Goal

Programming（GP）家具制造问题——王老板遇到的新问题王老板的多目标线性规划问题——目标规划问题：+

-

+minZ

=

P1d1

+

P2（

d2

+

d2

）+

P3

d3-s.t.2x1+

x2

≤

11x1

- x2

+

d1-

+-

d1

=

0-

+x1

+ 2x2

+

d28x1

+10x2

+

d3+-

d2

=

10-

-

d

=

563x

+

-

+

-

+

-1

、x2

、d1

、d1

、d2

、d2

、d3

、d3

≥

0目标规划

Goal

Programming（GP）目标规划的图解法如何求解多目标线性规划问题，其方法与求解线性规划问题的方法相似——目标线性规划单纯形法。但是，对于只有两个决策变量的目标线性规划问题同样可以采用图解的方法来揭示问题的解的某种特征。在用图解法解目标规划时，首先必须满足所有绝对约束条件。在此基础上，再按照目标优先级别从高到低的顺序，逐个地考虑各个目标约束条件。目标规划

Goal

Programming（GP）目标规划的图解法王老板的目标规划新问题图解+

-

+

-min

Z=

P1

d1

+

P2（

d2

+

d2

）+

P3d3s.t.

2x1+

x2

≤

11x

- x

+

d

-

-

d

+=

01

2

1

1x

-

+1

+

2x2+

d2

-

d2

=

108x

-

+1

+10x2

+

d3

-

d3

=

56x

+

-

+

-

+

-1

、x2

、d1

、d1

、d2

、d2

、d3

、d3

≥08x1

+10x2

=

56x1

+

2x2=

102x1+

x2

=11绝对约束域2d

++d33d

-d2-1d

-1x1

-

x2

=

0d

+（10/3，10/3）（2，4）目标规划

Goal

Programming（GP）目标规划的图解法案例——电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；每周黑白电视机的销量是

30台，每台可获利40元。决策者的目标为：第一优先级目标：充分利用装配线每周计划开动的40小时；第二优先级目标：允许装配线加班；但加班时间每周尽量不超过10小时；第三优先级目标：装配电视机的数量尽量满足市场需求。因为彩色电视机的利润更高（是黑白电视机利润的2倍），取其市场需求满足权系数为2。目标规划

Goal

Programming（GP）1

2

1

1x +

x +

d

-

-

d

+=

40-

+x1

+

x2

+

d2

-

d2

=

40+10=50-

+-

+x1

+

d3

-

d3

=

24x2+

d4

-

d4

=

30x

+

-

+

-

+

-

+

-1

、x2

、d1

、d1

、d2

、d2

、d3

、d3

、d4

、d4

≥0目标规划的图解法目标线性规划模型：x1

——彩色电视机的生产量x2

——黑白电视机的生产量min

Z

=

P

d

-+

P

d

++

P

（2d

-

+1d

-）1

1

2

2

3

3

4s.t.目标规划

Goal

Programming（GP）3d

-d1-3d

+4d

++d2+d1d4--x1d2x1

+

x2

=

40x1

+

x2

=

50目标规划的图解法电视机厂的目标线性规划问题——图解：x2x1

=

24x2

=

30满意解（24，26）目标规划

Goal

Programming（GP）目标规划模型的一般形式：l

lk

klk

kMin

Z

=∑

P

（∑（

w

-d

-

+

w

+d

+

））k=1l

=1L

Kn∑cx +

d

-

-

d

+

=

gkj

j

k

k

k，

k

=1，2，…，Kj

=1∑aij

xj

≤（=，≥）

bi，

i

=1，2，…，mj

=1nxj

≥

0

,j

=1，2，…，n-+dk

，dk

≥

0

,k

=1，2，…，KS.t.目标规划

Goal

Programming（GP）目标规划的单纯形解法目标规划的模型实际上是求min型的线性规划，因此，也可以用单纯形法求解。在采用单纯形法求解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，关键是要注意到优先因子的级别。当检验数按优先级别从高到低已满足最优性条件时，且无法进一步优化时，从单纯形表上就可以得到目标规划的最优解或满意解。目标规划

Goal

Programming（GP）目标规划的单纯形解法例

现有如下目标规划问题Min Z

=

P1d1-

+P2d2+

+P3d3-5x1

+

10x2

+

x3x1

–

2x24x1

+

4x26x1

+

8x2=

60+

d1-

–

d1+

=

0+

d2-

–

d2+

=

36+

d3-

–

d3+

=48xj

，

di-

，di+

≥

0当前基变量：x3

，d1-，d2-，d3-。目标规划

Goal

Programming（GP）目标规划的单纯形解法例

目标规划问题的典式Min Z

=

P1（

–

x1

+

2x2

+

d1+

）+

P2

d2++

P3（48

–

6x1

–

8x2

+

d3+

）5x1

+

10x2

+

x3=

60x1

–

2x2+

d1-

–

d1+=

04x1

+

4x2+

d2-

–

d2+=

366x1

+

8x2+

d3-

–

d3+=

48xj

，

di-

，di+

≥

0目标规划

Goal

Programming（GP）目标规划的单纯形解法例

目标规划问题的单纯形表P1

1P3

1cj000P100P2P30CB基解x1x2x3-d1+d1-d2+d2-d3+d30x3605101000000P1-d101-201-100000-d236440001-100P3-d34868000001-1sj

fiP1-121P21P3-6-81目标规划

Goal

Programming（GP）目标规划的单纯形解法例cj

0

0

0

P1

0

0

P2

P3

0-

+

-

+

-

+CB

基

解

x1

x2

x3

d1

d1

d2

d2

d3

d30x3605

10

1

0

0

0

0

0

0P1-d101

-2

0

1

-1

0

0

0

00-d2364

4

0

0

0

1

-1

0

0P3-d3486

8

0

0

0

0

0

1

-1P1

-1

2

1P2

1P3

-6

-8

1cj000P100P2P30CB基解x1x2x3-d1+d1-d2+d2-d3+d30x3600201-5500000x101-201-100000-d2360120-441-100P3-d3480200-66001-1sj

fiP11P21P3-206-61目标规划

Goal

Programming（GP）目标规划的单纯形解法例cj

0

0

0

P1

0

0

P2

P3

0-

+

-

+

-

+CB

基

解

x1

x2

x3

d1

d1

d2

d2

d3

d30x3600

20

1 -5

5

0

0

0

00x101 -2

0

1 -1

0

0

0

00-d2360

12

0 -4

4

1 -1

0

0P3-d3480

20

0 -6

6

0

0

1 -1P1

1P2

1P3

-20

6 -6

1cj000P100P2P30CB基解x1x2x3-d1+d1-d2+d2-d3+d30x3120011-100-110x124/51002/5-2/5001/10-1/100-d236/5000-2/52/51-1-3/53/50x212/5010-3/103/10001/20-1/20sj

fiP11P21P31目标规划

Goal

Programming（GP）目标规划的灵敏度分析目标规划的灵敏度分析主要针对优先级别进行，其原因是目标优先级别和权系数的确定往往带有一定的主观性。分析的方法主要是通过改变优先级别的顺序来观察解的变化情况。目标规划Goal

Programming（GP）目标规划应用问