运筹学(胡运权第三版)第四章 目标规划

0
0 0 -5 1 -4 -6 1 0
1
0 0 5 -1 4 6 0 0
0
0 0 0 0 1 0 0 0
0
1 0 0 0 -1 0 0 1
0
0 0 0 0 0 1 0 0
0
0 1 0 0 0 -1 0 0
P3
x3 x1 d 2x2 12 24/5 36/5 12/5 P1 P2
0
0 1 0 0 0 0
目 标 规 划 的 数 学 模 型
基本Biblioteka 念正偏差变量d+ 表示决策值超过目标值的部分； 负偏差变量d- 表示决策值未达到目标值的部分；
（1）偏差变量
d+≥0， d- ≥0，d+·-=0 d （2）绝对约束和目标约束 绝对约束就是必须要满足的约束条件，如线 性规划中的约束条件。绝对约束是硬约束，对 它的满足与否决定了解的可行性。 目标约束是目标规划特有的概念，是一种软 约束，目标约束中决策值之间的差异用偏差变 量表示。
-20
0 0 0 1 0 0
0
1 0 0 0 0 0
6
1 2/5 -2/5 -3/10 1 0
-6
-1 -2/5 2/5 3/10 0 0
0
0 0 1 0 0 0
0
0 0 -1 0 0 1
0
-1 1/10 -3/5 1/20 0 0
1
1 -1/10 3/5 -1/20 0 0
解 目 标 规 划 的 单 纯 形 法
解 目 标 规 划 的 单 纯 形 法
例4-5 用单纯形法解例4-4。
引入松弛变量x3， min {P1d1-,P2d2+,P3d3-}
5x 1 +10x 2 +x 3 =60 + x 1 -2x 2 +d 1 -d 1 =0 + s.t. 4x 1 +4x 2 +d 2 -d 2 =36 + 6x 1 +8x 2 +d 3 -d 3 =48 x ,x ,x ,d - ,d + 0(i=1,2,3) 1 2 3 i i
gk为第k个目标约束的预期目标值，Wlk-和Wlk+为Pl优 先因子对应各目标的权系数。

例1：
某工厂生产Ⅰ，Ⅱ两种产品，已知有关数据 见下表。试求获利最大的生产方案。
产品 原材料（kg/件） 设备（hr/件） 利润（元/件） Ⅰ 2 1 8 Ⅱ 1 2 10 限量 11 10
目 标 规 划 的 案 例
CB 0 P1 0 P3 zj-cj 0 0 0 P3 zj-cj 0 0 0 P3 zj-cj
xB x3 d 1d 2d 3-
P1
P2 P3 x3 x1 d 2d 360 0 36 48 P1 P2
-1
0 -6 0 1 0 0 0 0
2
0 -8 20 -2 12 [20] 0 0
0
0 0 1 0 0 0 0 0
目 标 规 划 问 题 的 导 出
一般来说，一个计划问题可能要满足多方面
得要求。 线性规划有最优解的必要条件是其可行解集 非空，即各约束条件彼此相容。但实际问题 有时不能满足这样的要求。 线性规划解得可行性和最优性具有十分明确 的意义，但那都是针对特定数学模型而言的。 实际中，决策者需要计划人员提供的不是严 格的数学上的最优解，而是可以帮助作出最 优决策的参考性计划，或是提供多种计划方 案，供最终决策时选择。
cj→
0 b 60 0 36 48 x1 5 [1] 4 6
0 x2 10 -2 4 8
0 x3 1 0 0 0
P1 d10 1 0 0
0 d1+ 0 -1 0 0
0 d 20 0 1 0
P2 d2+ 0 0 -1 0
P3 d30 0 0 1
0 d3+ 0 0 0 -1
解 目 标 规 划 的 单 纯 形 法
目 标 规 划 的 数 学 模 型

基本概念
（3）优先因子和权系数 一个规划问题常常有若干目标。但决策者在 要求达到这些目标时，是主次或轻重缓急的不 同。要求第一位达到的目标赋予优先因子P1， 次位的目标赋予优先因子P2， …，并规定 Pk>> Pk+1，k=1，2，…，K。表示Pk比 Pk+1有 更大的优先权。即首先保证P1级目标的实现， 这时可不考虑次级目标；而P2级目标是在实现 P1级目标的基础上考虑的；依此类推。这是绝 对差别。 若要区别具有相同优先因子的两个目标的差 别，这时可分别赋予他们不同的权系数wj，这 种差别是相对的。
目 标 规 划 的 数 学 模 型

基本概念
（4）目标规划的目标函数
目标规划的目标函数由各目标约束的偏差变量及 相应的优先因子和权系数构成。当每一目标值确定 后，决策者的要求是尽可能缩小偏离目标值。因此 目标规划的目标函数只能是极小化minz =f(d+，d-)。 三种基本表达式： ①要求恰好达到目标值，即正、负偏差变量都要尽 可能地小 min{f(d++d-)} 或者 minz = f(d++d-) ②要求不超过目标值，即允许达不到目标值，就是 正偏差变量要尽可能地小 min{f(d+)} 或者 minz = f(d+) ③要求不低于目标值，但允许超过目标值，即超过 量不限，但是必须是负偏差变量要尽可能地小 min{f(d-)} 或者 minz = f(d-)
在单纯形表Ⅲ中，由于非基变量d1+和d3+的检验数都是 零，故知例4-4有多重最优解(满意解)。
以d1+为换入变量继续迭代，可得如下单纯形表Ⅳ
cj→ CB 0 P1 0 xB x3 x1 d2d 1+ b 20 8 4 8 P1 cj-zj P2 P3 0 x1 0 1 0 0 0 0 0 0 x2 10/3 4/3 -4/3 10/3 0 0 0 0 x3 1 0 0 0 0 0 0 P1 d10 0 0 -1 1 0 0 0 d1+ 0 0 0 1 0 0 0 0 d20 0 1 0 0 0 0 P2 d 2+ 0 0 -1 0 0 1 0 P3 d3-5/6 1/6 -2/3 1/6 0 0 1 0 d 3+ 5/6 -1/6 2/3 -1/6 0 0 0
目 标 规 划
目标规划问题及其数学模型 目标规划的图解法 解目标规划的单纯形法 目标规划的灵敏度分析 目标规划应用举例

解 目 标 规 划 的 单 纯 形 法


目标规划的数学模型实际上是最小 化形的线性规划，可以用单纯形法 求解。 在用单纯形法解目标规划时，检验 数是各优先因子的线性组合。因此， 在判别各检验数的正负及大小时， 必须注意P1» 2» 3» P P …。当所有 检验数都已满足最优性条件(cj-zj≥0) 时，从最终单纯形表上就可以得到 目标规划的解。
例4-3 用图解法解例4-2。
目 标 规 划 的 图 解 法
目 标 规 划 的 图 解 法
△OAB区域是满足绝对约束和非负条件的解空 间。对于所有目标约束，去掉偏差变量，画出相 应直线，然后标出偏差变量变化时直线平移方向， 见图所示。 首先考虑P1，此时要求min d-1，因而解空间R1为 △OAC区域； 再考虑P2，此时要求min d2+，因而解空间R2为 △ODC区域； 最后考虑P3，此时要求min d3-，因而解空间R3为 四边形EDCF区域。 容易求得E，D，C，F四点的坐标分别为(8,0)、 (9,0)、(6,3)、(4.8,2.4)，故问题的解可表示为：
在单目标规划问题的基础上，决策者在原材 料受严格限制的条件下考虑：首先是产品Ⅱ 的产量不低于产品Ⅰ的产量；其次是充分利 用设备有效台时，不加班；再次是利润额不 小于56元。求决策方案。
目 标 规 划
目标规划问题及其数学模型 目标规划的图解法 解目标规划的单纯形法 目标规划的灵敏度分析 目标规划应用举例
max z 8 x1 10 x 2 2 x1 x 2 11 s .t . x1 2 x 2 10 x ,x 0 1 2
解得，最优解x1=4，x2=3，max z=62（元）
目 标 规 划 的 案 例
但实际上工厂在做决策时，要考虑市场等一 系列其他条件： (1) 根据市场信息，产品Ⅰ的销售量有下降趋势， 故考虑产品Ⅰ 的产量不大于产品Ⅱ； (2) 超过计划供应的原材料时，需用高价采购， 会使成本大幅度增加； (3) 应尽可能充分利用设备台时，但不希望加班； (4) 应尽可能达到并超过计划利润指标56元。
例4-4 用图解法解下面的目标规划
目 标 规 划 的 图 解 法
min{P1d1-,P2d2+,P3(5d3-+3d4-),P4d1+}
x 1 +2x 2 +d 1- -d 1 + =6 + x 1 +2x 2 +d 2 -d 2 =9 + s.t. x 1 -2x 2 +d 3 -d 3 =4 + x 2 +d 4 -d 4 =2 x ,x ,d - ,d + 0(i=1,2,3,4) 1 2 i i
目 标 规 划 的 图 解 法
所以满意解为：x1=6.5，x2=1.25 例4-4得到的解不能满足所有目标。这时， 我们要做的是寻找满意解，使它尽可能满足 高级别的目标，同时又使它对那些不能满足 的较低级别目标的偏离程度尽可能的小。 必须注意的是，在考虑低级别目标时， 不能破坏已经满足的高级别目标，这是目标 规划的基本原则。但是，也不能因此而以为， 当高级别目标不能满足时，其后的低级别目 标也一定不能被满足。事实上，在有些目标 规划中，当某一优先级的目标不能满足时， 其后的某些低级别目标仍有可能被满足。