第三章目标规划和整数规划.ppt

第三章目标规划和整数规划
目标规划
整数规划
第三章目标规划和整数规划
第三章目标规划和整数规划
3．1 目标规划
3．1．1 单目标规划
3．1．2 多目标规划
级别相同的目标规划
具有优先级目标规划
3．2 整数规划
3．2．1 整数规划分枝限界法
3．1．2 整数规划分割平面法
3．2．1 0-1规划
3．1．2 分派问题
OR
第三章目标规划和整数规划
3．1目标规划
3．1．1单目标规划
3．1．1．1单目标规划数学模型
(1)如何安排可获得最大利润
Max Z（X）= 8x1+6x2
4x1 + 2x2 ≤60
2x1 + 4x2 ≤48
x1，x2 ≥0
x1=12,x2 =6,
Z(X*)=132
A
B
4
2
4
2
6
8
60
可使用量
48
设备（hr)
原料（kg)
利润（千元）
例
OR
（线性规划）
第三章目标规划和整数规划
(2)利润目标为140（百元）
此目标称之为预定目标，实际完成的量与预定目标
之间可能出现偏差，通常用d+、d-（d+、d-≥0）表示，
称为偏差变量。
其中：
d+表示超过预定指标的部分，
d-表示未达到预定指标的部分
在客观条件下，最终完成的结果可能出现以下三种情况：
① d+>0,d-=0 表明超额完成预定指标
② d->0,d+=0 表明未达到预定指标
③ d+ =d- = 0 表明恰好完成预定指标
上述三种情况可用模型表示
OR
第三章目标规划和整数规划
8x1 + 6x2
特征：①增加了目标约束、
②目标中只出现偏差变量且为求极小化问题、
③d+×d-=0
d-
,d+
d-
+d-
-d+
=
目标约束
系统约束
Z=
4x1 + 2x2 ≤ 60
2x1 +4x2 ≤ 48
x1，x2， ≥0
140
Min
OR
第三章目标规划和整数规划
3．1．1．2 单目标规划解
用单纯形法求满意解,注意求极小化问题最优性条件：
[
]
标准型: Min Z= d-
8x1 + 6x2+d-- d+ =140
4x1 + 2x2 +x3 = 60
2x1 + 4x2 +x4 = 48
x1，x2 x3 ,x4 ,d-, d+ ≥0
X1 X2 X3 X4 d- d+
0 0 0 0 1 0
8 6 0 0 1 -1
4 2 1 0 0 0
2 4 0 1 0 0
-8
140
60
48
d-
X3
X4
1
0
0
OR
-6
0
0
0
1
第三章目标规划和整数规划
[
]
[
]
≥0
x1 =12， x2 = 6,d-=8 d+=0 完成利润132（百元）
OR
第三章目标规划和整数规划
由此可得：x1=12，x2=6，d+=0，d-=8
完成利润132（百元）
3．1．2 级别相同的多目标规划
3．1．2．1数学模型
（1）实现利润目标122（百元）
（2）产品A的产量不多于10
设：di+,di-(i=1,2)分别为超过目标值的部分，及未完成目标值的部分。
8x1 + 6x2
min
目标约束
系统约束
x1
4x1 + 2x2 ≤ 60
2x1 + 4x2 ≤ 48
x1，x2，
= 122
= 10
d1+,d1-，d2+,d2-≥0
Z=
+ d1-
- d1+
+d2-
- d2+
d1-
+ d2+
OR
第三章目标规划和整数规划
8x1 + 6x2 + d1- - d1+ = 122
x1