离 散
整数线性规划(ILP)，整数非线性规划(INLP)
优
纯整数规划(PIP), 混合整数规划(MIP)
化 2020/8/1
一般整数规划，0-1（整数）规划
新余学院 建模组
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
优化模型的简单分类和求解难度
优化
连续优化
整数规划
线性规划
x1 x2 x3 x4 x7 50 x1 x2 x3 x4 x5 80
整数规划
x2 x3 x4 x5 x6 90
模型(IP)
2020/8/1
x3 x4 x5 x6 x7 80
新余学院 建模组
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
0-1规划 －混合泳接力队的选拔
例1.5： 5名候选人的百米成绩
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
1. 优化模型的基本概念
优优 化化建建模 模
优化模型和算法的重要意义
最优化: 在一定条件下，寻求使目标最大(小)的决策 最优化是工程技术、经济管理、科学研究、社 会生活中经常遇到的问题, 如:
结构设计 资源分配 生产计划 运输方案
: x2
0c
0
l5
l2 C Z=3600 l3
D x1
Z=0 Z=2400
在B(20,30)点得到最优解
LP的通常解法是单纯形法(G. B. Dantzig, 1947)
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
线性规划模型的解的几种情况
向各工地运送多少吨水泥，使总的吨公里数最小。
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
26
min
cij[(x j ai )2 ( y j bi )2 ]1/ 2
决策变量：ci j (料场j到工地i的 s.t. 运量）~12维
j1i1
2
cij
1桶 牛奶 或
12小时 8小时
3公斤A1 4公斤A2
获利24元/公斤 获利16元/公斤
每天： 50桶牛奶 时间480小时 至多加工100公斤A1
制订生产计划，使每天获利最大
• 35元可买到1桶牛奶，买吗？若买，每天最多买多少?
• 可聘用临时工人，付出的工资最多是每小时几元?
• A1的获利增加到 30元/公斤，应否改变生产计划？
线性规划问题
有可行解(Feasible)
无可行解 （Infeasible）
有最优解（Optimal） 无 最 优 解 (Unbounded)
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
二次规划模型－例1.2：产销计划问题
某厂生产两个牌号的同一种产品，如何确定产量使利润最大
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
假设C
优优 化化建建模 模
b1 100, a11 1, a12 0.1, b2 280, a21 0.2, a22 2
假设D 两产品的产量之和不可能超过100件
假设E 甲产量不可能超过乙的产量的2倍
假设F q1 2, q2 3
cij
i=1
i=2
i=3
i=4
i=5
j=1
66.8
57.2
78
70
67.4
j=2
75.6
66
67.8
74.2
71
j=3
87
66.4
84.6
69.6
83.8
j=4
58.6
53
59.4
57.2
62.4
若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0
目标 函数
Min Z
45
cij xij
j1i1
6
cij ej , j 1, 2
i1
c 0 2020/8/1 新余ij学院 建模组
(NLP)
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
整数规划 - 例1.4: 聘用方案
某服务部门一周中每天需要不同数目的雇 员：周一到周四每天至少 50 人，周五和周日 每天至少 80 人，周六至少 90 人。
a 1.25 8.75 0.5 5.75 3 7.25
b 1.25 0.75 4.75 5 6.5 7.75
d3
5
4
7
6
11
假设：料场 和工地之间 有直线道路
1)现有 2 料场，位于 A (5,日储量 ej 各有 20 吨。
目标：制定每天的供应计划，即从 A, B 两料场分别
甲
乙
丙
丁
戊
蝶泳 1’06 57”2 1’18” 1’10” 1’07 仰泳 1”’815 1’06” 1’07 1’14 1’”114” 蛙泳 1’”276” 1’06 1”’824 1”’209 1’23 自由泳 58”6 5”3”4 5”9”64 5”7”62 1”’802
如何选拔队员组成4100米混合泳接力队? ”4
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
优优 化化建建模 模
1桶 牛奶 或
12小时 8小时
3公斤A1 4公斤A2
每天 50桶牛奶 时间480小时
获利24元/公斤 获利16元/公斤 至多加工100公斤A1
决策变量 x1桶牛奶生产A1 x2桶牛奶生产A2
目标函数
g j (x) 0, j 1,..., l
束 条
决策变量
xD
n
件
• 无约束优化(没有约束)与约束优化(有约束)
• 可行解（只满足约束）与最优解(取到最优值)
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
局部最优解与整体最优解
优优 化化建建模 模
f(x)
x1* ox2 x
求甲、乙产量，使总利润最大？
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
目标 利润最大
优优 化化建建模 模
max
x1 ,x2
z(x1,
x2 )
( p1 q1)x1 ( p2
= （100-x1-0.1 x2-2）x1
q2 )x2
牌号 产量 成本 价格 +（280-0.2x1-2x2-3）x2
0-1规划: 整数规划的特例
约束 每人最多入选泳姿之一 每种泳姿有且只有1人
条件
2020/8/1
4
xij 1, i 1, 5
j1
5
xij 1, j 1, 4
i1
新余学院 建模组
上一页
下一页
Xinyu University MCM
整数规划问题 min f (x)
一般形式
x Zn
s.t. hi (x)
优优 化化建建模 模
模型求解
图解法
Ax2
约 x1 x2 50
l1 : x1 x2 50
l1
束 12x1 8x2 480 l2 :12x1 8x2 480
B
条 件
3x1
100
x1, x2 0
l3 : 3x1
l4 : x1 0,
目标 Max z 72x1 64x2
函数 z=c (常数) ~等值线
l5
100 l4
• 局部最优解 (Local Optimal Solution, 如 x1 )
• 整体最优解 (Global Optimal Solution, 如 x2 )
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
优化模型的
优优 化化建建模 模
min f (x)
简单分类
现规定应聘者需连续工作 5 天，试确定聘用 方案，即周一到周日每天聘用多少人，使在 满足需要的条件下聘用总人数最少。
决策变量：周一至周日每天(新)聘用人数 x1, x2,x7
目标函数：7天(新)聘用人数之和
约束条件：周一至周日每天需要人数
2020/8/1
新余学院 建模组
上一页
下一页
Xinyu University MCM
甲 x1 q1 p1 =98 x1 + 277 x2 － x12 － 0.3 x1 x2 － 2x22
乙 x2 q2 p2
b1 100, a11 1, a12 0.1, b2 280, a21 0.2, a22 2
约束
x1 + x2 ≤100
x1 ≤ 2 x2 x1 , x2 ≥ 0
二次规划模型(QP)
聘用方案
连续工作5天
优优 化化建建模 模
设系统已进入稳态（不是开始的几周） 周一工作的应是(上)周四至周一聘用的
x4 x5 x6 x7 x1 50
min z x1 x2 x3 x4 x5 x6 x7
s.t. x1 x4 x5 x6 x7 50 x1 x2 x5 x6 x7 50