目标规划 本章内容重点 目标规划模型 目标规划的几何意义 目标规划的单纯形方法.

Presentation on theme: "目标规划 本章内容重点 目标规划模型 目标规划的几何意义 目标规划的单纯形方法."— Presentation transcript:

1 目标规划 本章内容重点 目标规划模型 目标规划的几何意义 目标规划的单纯形方法

2 问题的提出 线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度(即优先顺序)也不相同，有些目标之间往往相互发生矛盾。 线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。

3 问题的提出 线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。
求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。 为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。

4 目标规划与线性规划的比较 线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。
线性规划求最优解；目标规划是找到一个满意解。 线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。 线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要(或更能满足需要)。

5 目标规划与线性规划的比较 例5-1：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。 120 70 单件利润 3000 10 3 设备台时 2000 5 4 煤炭 3600 9 钢材 资源限制 乙 甲 单位 产品 资源 消耗

6 目标规划数学模型 maxZ=70 x1 + 120 x2 maxZ1=70 x1 + 120x2 minZ2= x1
根据市场预测： 设：甲产品x1 ，乙产品 x2 maxZ=70 x x2 9 x1 +4 x2 ≤3600 4 x1 +5 x2 ≤ 2000 3 x1 +10 x2 ≤3000 x1 ， x2 ≥0 maxZ1=70 x x2 minZ2= x1 maxZ3= x2 9 x1 +4 x2 ≤3600 4 x1 +5 x2 ≤ 2000 3 x1 +10 x2 ≤3000 x1 ， x2 ≥0

7 目标规划的数学模型 1.目标值和偏差变量 目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。
目标值：是指预先给定的某个目标的一个期望值。 实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。 偏差变量(事先无法确定的未知数)：是指实现值和目标值之间的差异,记为 d 。 正偏差变量:表示实现值超过目标值的部分，记为d＋。 负偏差变量:表示实现值未达到目标值的部分，记为d－。

8 目标规划的数学模型 在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0, d－≥0

9 目标规划的数学模型 2.目标约束和绝对约束 引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。
目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。 绝对约束(系统约束)是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。

10 目标规划的数学模型 例如：在例一中，规定Z1的目标值为 50000,正、负偏差为d＋、d－ ,则目标函数可以转换为目标约束，既: 50000
120 70 1 2 = - + d x 若规定3600的钢材必须用完，原式9x1 +4x2 ≤3600变为 3600 4 9 2 1 = - + d x

11 目标规划的数学模型 3.优先因子(优先等级)与优先权系数
目标等级化:将目标按重要性程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。 (1)对同一目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。 (2)不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别目标上的收获不可弥补。故在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。 (3)同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。

12 目标规划的数学模型 3.优先因子(优先等级)与优先权系数
优先因子Pk是将决策目标按其重要程度排序并表示出来。P1>>P2>>…>>Pk>>Pk+1>>…>>PK ，k=1,2…,K。表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。 若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数ωj,这些都由决策者按具体情况而定。

13 目标规划的数学模型 4.达成函数(即目标规划中的目标函数)
目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minZ = f(d＋、d－)。 一般说来，有以下三种情况，但只能出现其中之一： (1)要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ = f(d＋＋ d－)。 (2)要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ = f(d＋)。 (3)要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ = f(d－)。 对由绝对约束转化而来的目标函数，也照上述处理即可。

14 目标规划的数学模型 5.多目标规划的解 (1)若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；
(2)若解只能满足部分目标，就称该解为多目标规划的次优解； (3)若找不到满足任何一个目标的解，就称该问题为无解。 (4)前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现，就称该解为多目标规划的满意解(具有层次意义的解)

15 单目标规划 例5-2:某工厂生产A，B两种产品，有关数据如下。实现目标利润为140万元的最优生产方案 A B 可用量 设备(台时) 4 2
60 原材料(KG) 48 利润(万元) 8 6 从决策者的角度看，他希望超过利润目标值，若达不到，也希望尽可能接近，即负偏差最小 = - min d Z = + - 140 6 8 2 1 d x ï î í ì st + 60 2 4 1 x + 48 4 2 1 x - + , 2 1 d x

16 级别相等的多目标规划 例5-3：若上例中假设决策者根据市场预测，产品A的销售量有下降的趋势，故考虑实现下列两个目标：
(1)实现利润目标122万元 (2)产品A的产量不多于10 分析: 两个目标级别相等，即两个目标的重要程度一样，不存在谁优先的问题 设d＋，d-分别为超过目标值的部分，以及未完成目标值的部分，于是两个目标可以等价表示为： 10 122 6 8 1 2 = - + d x

17 级别相等的多目标规划 ï î í ì ³ £ + = - , 48 4 2 60 10 122 6 8 d x st MinZ
, 48 4 2 60 10 122 6 8 1 d x st MinZ x1=10，x2=7，d－1＝0，d+2＝0，利润为122，两个目标均已经实现

18 具有优先级别的多目标规划 对于多个目标，如果有一定的优先顺序，即第一位重要的目标，其优先因子为P1，第二位重要的目标，其优先因子为P2，并规定P1>>P2 优先保证P1级目标的实现，此时不考虑次级目标；次级目标P2在实现了P1级目标的基础上再予以考虑。如果无法实现P1目标，则不考虑P2目标能否取得最优 若有k个不同优先顺序的目标，则有P1>>P2>>…>>Pk 将权重与偏差相乘构成目标函数，这样，权重越大，越先迫使相应的偏差等于零，这样可保证优先级高的目标首先实现。

19 具有优先级别的多目标规划 例5-4：若上例中决策者拟订下列经营目标，并确定了目标之间的优先顺序 P1级目标：充分利用设备有效台时，不加班；
P2级目标：产品B的产量不多于4； P3级目标：实现利润值130万元 分析：题目有三个目标层次，包含三个目标值。 第一目标： P1(d1＋+d1-) 第二目标：P2d2＋ 第二目标：P3d3 - ï î í ì + = - , 48 4 2 130 6 8 60 ) ( 1 3 i d x st P MinZ

20 具有优先级别的多目标规划 例5-5：某厂计划下一个生产周期内生产甲、乙两种产品，已知资料如表所示。制定生产计划，满足下列目标：
P1级目标：完成或超额完成利润指标 50000元； P2级目标：产品甲不超过 200件，产品乙不低于 250件； P3级目标：现有钢材 3600吨必须用完 120 70 单件利润 3000 10 3 设备台时 2000 5 4 煤炭 3600 9 钢材 资源限制 乙 甲 单位 产品 资源 消耗

21 具有优先级别的多目标规划 分析：题目有三个目标层次，包含四个目标值。 第一目标： P1d1＋
第二目标：有两个要求即甲d2＋，乙d3-，但两个具有相同的优先因子，需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12，P2(7d2＋+12d2 -) 第二目标：P3(d4＋+d4 -) ï î í ì + = - , 3000 10 3 2000 5 4 3600 9 250 200 50000 120 70 ) ( 12 7 2 1 i d x st P MinZ

22 数学模型的一般形式 å 其中Pl为优先因子， w-lk，w+lk为优先系数 ï î í ì - = ³ £ + ) 5 ( 3 , 2 1
4 min k d n j x m i b a K g c P z ij kj lk L l 满足约束条件： 目标函数： w 其中Pl为优先因子， w-lk，w+lk为优先系数

23 建模的步骤 根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；
可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。 给各目标赋予相应的优先因子 Pk 对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数 ωkl+和ωkl- 。 根据决策者的要求，构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。

24 线性规划与目标规划 线性规划LP 目标规划GP 目标函数 min, max 系数可正负 min , 偏差变量 系数≥0 变量
xi , xs , xa xi , xs , xa , d 约束条件 系统约束 (绝对约束) 目标约束 解 最优 满意

25 目标规划的图解法 图解法解题步骤如下： 1.确定各约束条件的可行域，即将所有约束条件(包括目标约束和绝对约束，暂不考虑正负偏差变量)在坐标平面上表示出来； 2.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向； 3.求满足最高优先等级目标的解； 4.转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解； 5.重复4，直到所有优先等级目标都已审查完毕为止； 6.确定最优解和满意解。

26 目标规划的图解法 ï î í ì = + - ) 2 . 1 ( , 8 10 5 62 12 min l d x P Z x2 C B A x1 ⑵ ⑶ ⑴ B ( , ) C (0 , ) ， B、C 线段上的所有点均是该问题的解 (无穷多最优解)。

27 目标规划的图解法 结论：C(60 ,58.3)为所求的满意解。 ï î í ì = ³ - + ) 4 . 3 2 1 ( , 100 60
, 100 60 140 2500 12 30 5 min l d x P Z x2 (3) 140 120 100 80 60 40 20 B A (4) C D x1 (1) (2) 结论：C(60 ,58.3)为所求的满意解。

28 目标规划的单纯形法 å K k n j P a z c , 2 1 ; L = -
目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定： (1) 因目标规划问题的目标函数都是求最小化，所以以cj-zj≥0，j=1,2,…，n为最优准则。 (2)因非基变量的检验数中含有不同等级的优先因子，即 K k n j P a z c kj , 2 1 ; L = - å 因P1>>P2>>…>>PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数α1j的正、负。若α1j=0，这时此检验数的正、负就决定于P2的系数α2j的正、负。

29 目标规划的单纯形法 (1)建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。
(3)按最小比值规则确定换出变量，当存在两个或以上相同的最小比值时，选取具有较高优先级别变量为换出变量。 (4)按单纯形法进行基变换运算，建立新的计算表，返回(2)。 (5)当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。

30 目标规划的单纯形法 例5-8：用单纯形法求解下列目标规划问题 MinZ=P1 d1- + P2(d2-+d2+)+P3(3d3-+5d4-)
5x1+4x2 +d1-- d1+ = 20 4x1+3x2 +d2- - d2+= 24 x d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ ≥0

31 目标规划的单纯形法 cj 检验数 λj 检验数 λj d1- d2- d3- d4- 20 5 4 1 -1 24 3 2 4 6 3 -
 值 CB XB b x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 检验数 λj P1 P2 P3 P1 P2 3P3 5P3 P1 P2 3P3 5P3 d1- d2- d3- d4- 20 5 4 1 -1 24 3 2 4 6 3 - -5 -4 1 -3 2 3 5 P1 P2 5P3 检验数 λj P1 P2 P3 d1- d2- x1 d4- 5 4 1 -1 -5 1 3 - 12 3 1 -1 -4 4 3 1 -1 5 1 -1 -4 1 5 -5 -3 2 4 -2

32 目标规划的单纯形法 检验数 λj 检验数 λj cj  值 P2 5P3 d3+ d2- x1 d4- 1 4/5 1/5 -1/5 -1
P1 P2 3P3 5P3  值 CB XB b x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 检验数 λj P3 P2 5P3 d3+ d2- x1 d4- 1 4/5 1/5 -1/5 -1 - 10 8 -1/5 -4/5 4/5 1 -1 4 1 4/5 1/5 -1/5 6 9/5 1/5 -1/5 1 -1 1 1/5 4/5 -4/5 2 -9 -1 3 5 检验数 λj P1 P2 P3 5P3 d3+ d1+ x1 d4- 3 3/4 1/4 -1/4 -1 1 4 - 8 32/7 10 -1/4 -1 1 5/4 -5/4 6 1 3/4 1/4 -1/4 8 7/4 1/4 -1/4 1 -1 1 -35/4 -5/4 5/4 3 5

33 目标规划的单纯形法 λj λj cj  值 CB XB b x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+
P1 P2 3P3 5P3  值 CB XB b x1 x2 d1- d1+ d2- d2+ d3- d3+ d4- d4+ 检验数 λj P3 5P3 x2 d1+ x1 d4- 4 1 1/3 -1/3 -4/3 4/3 - 3 11 -1 1 4/3 -4/3 -1/3 1/3 3 1 -1 1 -1/3 1/3 7/3 -7/3 -1 1 5/3 -5/3 -26/3 35/3 5 检验数 λj P1 P2 P3 3P3 x2 d1+ x1 d3- 32/7 1 1/7 -1/7 4/7 -4/7 78/7 -1 1 9/7 -9/7 1/7 -1/7 18/7 1 1/7 -1/7 -3/7 3/7 3/7 -1/7 1/7 1 -1 -3/7 1 3/7 -3/7 3 26/7 9/7

34 目标规划的单纯形法 例5-9：用单纯形法求解下列目标规划问题 minZ=P1 d1++P2(d2-+d2+)+P3d3-
2x1+ x2 + x3 = 11 x1 - x2 +d1- - d1+= 0 x1 + 2x2 +d2- - d2+ = 10 8x1 + 10x2 +d3- - d3+ = 56 xi,dk- , dk+ ≥0

35 目标规划的应用 minZ= P1 d1- + P2 (d2-+d2+ ) x1 ≤6 x2 ≤10
5x x2 +d1- -d1+ =40 20x1+10 x2 +d2- -d2+ =140 x1 , x2, d1-, d1+ , d2-, d2+ ≥0 例5-10：已知一个生产计划的线性规划模型，经营目标： P1：总利润不低于40 P2：充分利用设备能力，且尽量不超过140 如何安排生产？ x1 x2 x1 =6 产品 资源 甲 乙 现有资源 设备 20 10 140 售价 8 成本 5 6 最大需求量 ④ ③ x2 =10 C B D (6,5) d2+ d2- d1+ d1-

36 目标规划的应用 满意解:x1 =6，x2 = 5 设备能力:需求206+10 5=170，实际140
实现目标P1和P2，降低甲乙产品的设备消耗:降低率( )/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，单价： 8

37 目标规划的应用 降低设备消耗很困难，则调整经营目标的次序 P1：充分利用设备能力，且尽量不超过140， P2：总利润不低于40
如何安排生产？ 产品 资源 甲 乙 现有资源 设备 20 10 140 售价 8 成本 5 6 最大需求量 x1 x2 x1 =6 ④ ③ x2 =10 E d1+ d1- d2+ d2- minZ= P2 d1- + P1 (d2-+d2+ ) x ≤ ① x ≤ ② 5x x2 +d1- -d1+ = ③ 20x1 +10 x2 +d2- -d2+ = ④ x1 , x2, d1-, d1+ , d2-, d2+ ≥0 A (6,2)

38 目标规划的应用 满意解：x1 =6, x2 = 2 利润指标：实际5×6+2×2=34，期望40
实现目标P1和P2，增加甲乙产品的单位利润: 增长率(40-34)/34=18% 产品售价由市场决定，为提高利润，应从降低成本入手： 甲产品的成本由5降为10-5(1+18%)=4.12,乙产品的成本由6降为8-2 (1+18%)=5.63。 生产部目标 甲产品的产量：6，成本：4.12 乙产品的产量：2，成本：5.63 总利润：40 单位甲：5.88 单位乙：2.36 技术部目标 甲产品的设备单耗：20 乙产品的设备单耗：10 销售部目标 甲产品的销量：6，单价：10 乙产品的销量：2，单价： 8

39 目标规划的应用 月份 1 2 3 4 成本(购价+库存) 2.6 2.5 2.7 2.8 售价 2.9 3.1 3.3
某副食品批发店预测某商品今后4月的购进与售出价格如表。 假设:(1)该商品供不应求，最大销量受仓库容量限制； (2)正常库容3吨，机动库容2吨； (3)月初批发销货，月中采购进货，进货所需资金完全来销售收入； (4)1月初库存量2吨，成本2.5千元/吨，该月初无现金。 经营目标：(1)每月都使用正常库容，尽量不超容； (2) 每月下旬都应储备1千元以备急用； (3)4个月总盈利最大。 月份 1 2 3 4 成本(购价+库存) 2.6 2.5 2.7 2.8 售价 2.9 3.1 3.3

40 目标规划的应用 决策变量：xj 第j 月的采购量， yj 第j 月的销售量 绝对约束条件
各月销量约束:月初售货，各月销量不多于其期初库存量。 1月 y1 ≤2 2月 y2 ≤2 – y1 + x → y1 + y2 – x ≤2 3月 y3 ≤2 – y1 + x1 – y2 + x2 → y1+y2+ y3 – x1 – x ≤2 4月 y4≤2 – y1 +x1 –y2+x2–y3+x3→ y1+y2+y3+y4 – x1 –x2–x3≤2 各月采购量约束:每月采购量依赖月初的售货收入。 1月 x1 ≤2.9y1→ – 2.9y x1 ≤0 2月 – 2.9y1 –2.7y x1 +2.5x ≤0 3月 – 2.9y1 –2.7y2 –3.1y x1+2.5x2+2.7x3 ≤0 4月 – 2.9y1 –2.7y2 –3.1y3 –3.3y4+ 2.6x1 +2.5x2+2.7x3+2.8x4≤0

41 目标规划的应用 目标达成函数 目标约束条件 正常库容约束 各月储备金约束 总盈利约束：期望利润(3.3-2.5)×(3+2) × 4=16
1月 2 –y1 + x1 ≤ 3→ –y x d1- – d1+ =1 2月 –y1 –y x1+ x d2- – d2+ = 1 3月 –y1 –y2 –y x1+ x2+ x d3- – d3+ = 1 4月 –y1 –y2 –y3 –y4 + x1+ x2+ x3 + x4 + d4- – d4+ = 1 各月储备金约束 1月 y x d5- – d5+ = 1 2月 2.9y1 +2.7y x1 -2.5x d6- – d6+ = 1 3月 2.9y1 +2.7y2 +3.1y x1-2.5x2-2.7x d7- – d7+ = 1 4月 y1 +2.7y2 +3.1y3 +3.3y4- 2.6x1 -2.5x2-2.7x3-2.8x4 + d8- – d8+ = 1 总盈利约束：期望利润( )×(3+2) × 4=16 销售收入: 2.9y1 +2.7y2 +3.1y3 +3.3y4 销售成本: 2.5×2+2.6x1 +2.5x2+2.7x3 2.9y1 +2.7y2 +3.1y3 +3.3y4 -2.6x1 -2.5x2-2.7x3 + d9- – d9+ = 21 目标达成函数 minZ=P1 (d1+ + d2+ + d3+ + d4+ ) + P2 ( d5- + d6- + d7- + d8- ) + P3 d9-