- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
TP SHUAI
20
基本概念
• 在上述例子中,有的目标函数和约束函数 都是线性的,称之为线性规划问题,而有的模 型中含有非线性函数,称之为非线性规划. 在线性与非线性规划中,满足约束条件的点 称为可行点,全体可行点组成的集合称为 可行集或可行域.如果一个问题的可行域 是整个空间,则称此问题为无约束问题.
最优化理论与算法
帅天平
北京邮电大学数学系 Email: tpshuai@, Tel: 62281308, Rm:主楼814
TP SHUAI
1
提纲
使用教材：
最优化理论与算法 (第2 版)
陈宝林 编著， 清华大学出版社
主要内容 1. 线性规划 对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化 算法设计技巧
TP SHUAI
16
3 选址问题（2）
利润 cij: i I, j J, 在j处的设施服务顾客i所得的利润 费用 f j : j J, 打开j处设施的费用
每一j J 0-1 变量 x j : x j 1,open j 1, 顾客 i由在 j的设施服务 yij : i I, j J 否则 0,
x S的最优解（整体最优解）
Df 1.2 设f(x)为目标函数，S为可行域，
若存在x0的邻域 N (x 0 ) {x | x x 0 , 0} 使得对每个x S N (x 0 ), 成立f (x) f (x 0 )
则称x0为极小化问题min f(x),x S的局部最优解
TP SHUAI
8
拉格朗日，1797
Min f(x1 x2 · · · xn) s.t. gk (x1 x2 · · · xn )=0, k=1,2,…,m
欧拉，拉格朗日：无穷维问题，变分学 柯西：最早应用最速下降法
TP SHUAI
9
电子计算机----------最优化
1930年代，康托诺维奇：线性规划 1940年代，Dantzig：单纯形方法， 冯 诺依曼：对策论 1950年代，Bellman：动态规划，最优性原理； KKT条件； 1960年代：Zoutendijk,Rosen,Carroll,etc.非线性规划算 法，Duffin，Zener等几何规划，Gomory，整数规 划,Dantzig等随机规划 6-70年代：Cook等复杂性理论，组合优化迅速发展
TP SHUAI 2
参考书目
Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley & Sons, Inc. 3nd Edit，2006 Linear and Nonlinear Programming David G. Luenberger Addison-Wesley Publishing Company, 2nd Edition, 2003.. Convex Analysis R. T. Rockafellar Princeton Landmarks in Mathematics and Physics, 1996. Optimization and Nonsmooth Analysis Frank H. Clarke SIAM, 1990.
TP SHUAI 10
最优化应用举例
• • • • • • • • • 具有广泛的实用性 运输问题，车辆调度，员工安排，空运控制等 工程设计，结构设计等 资源分配，生产计划等 通信：光网络、无线网络，ad hoc 等. 制造业：钢铁生产，车间调度等 医药生产，化工处理等 电子工程，集成电路VLSI etc. 排版（TEX,Latex,etc.）
TP SHUAI
18
4负载平衡(1)
实例: 网络G(V,E) 及一组m 个数的集合{s,d>0}，表示 连接源点 s与汇点d 之间的流量 解: {s,d>0}的一组路由, 即G(V,E) 中m 条s 与 d间的路, 表示连接s与d 的负载流量的路径。 目标:极小化网络负载
用F 表示由s到d的流经过边 (vi , v j )的流量。
TP SHUAI
3
其他参考书目
数值最优化影印版
Jorge Nocedal Stephen J. Wright 科学出版社，2006 组合最优化算法和复杂性 蔡茂诚、刘振宏 清华大学出版社，1988 运筹学基础手册 Combinatorial Optimization Algorithms and Complexity Printice-Hall Inc.,1982/1998
TP SHUAI
17
3选址问题（3）
max s.t.
c
iI jJ ij
i j ij
y f jx j
jJ
y
jJ
1
i I; i I, j J; j J; i I, j J.
yij x j , x j {0,1}, yij {0,1},
sd ij
TP SHUAI
19
4 负载平衡(2)
min s.t. L L Li,j s,d Fijsd , F 0,or s,d ,
sd ij
(1) (i,j) E (i,j) E (2) (3) (4)
s,d , if s j sd sd i Fij k Fjk s,d , if d j 0, otherwise
TP SHUAI
21
基本概念
• 最优化问题可写成如下形式:
min f ( x) n
xR
---目标函数
s.t.
gi ( x) 0, i I h j ( x) 0, j E
TP SHUAI
22
基本概念
Df 1. 1 设f(x)为目标函数，S为可行域，x0S,若对 每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x),
统计学方法
回归分析 群分析 模式识别 实验设计 因子分析等
动态规划
不确定规划：随机规 划、模糊规划等 多目标规划 对策论等
TP SHUAI
6
优化树
TP SHUAI
7
•最优化的发展历程
费马:1638;牛顿,1670
mi,1755
Min f(x1 x2 · · · xn ) f(x)=0
TP SHUAI 13
2 运输问题
设某种物资有m个产地A1,A2,…Am,各产地的产量是 a1,a2,…,am;有 n个销地B1,B2,…,Bn.各销地的销量是 b1,b2,…,bn.假定从产地Ai(i=1,2,…,m)到销地 Bj(j=1,2,…,n)运输单位物品的运价是cij问怎样调运 这些物品才能使总运费最小？ 如果运输问题的总产量等于总销量，即有
徐光辉、刘彦佩、程侃
科学出版社，1999
TP SHUAI 4
1,绪论----学科概述
• 最优化是从所有可能的方案中选择最合理 的一种方案,以达到最佳目标 的科学. • 达到最佳目标的方案是最优方案,寻找最优 方案的方法----最优化方法(算法) • 这种方法的数学理论即为最优化理论. • 是运筹学的方法论之一.是其重要组成部分. 最优化首先是一种理念, 其次才是一种方法. 运筹学的“三个代表” • 模型 • 理论
a b
i 1 i j 1
m
n
j
则称该运输问题为产销平衡问题；反之，称产销不平 衡问题。
TP SHUAI 14
2 运输问题（续）
令xij表示由产地Ai运往销地Bj的物品数量，则产销平衡 问题的数学模型为：
min z cij xij
i 1 j 1 n m
n xij ai i 1, 2, , m j 1 m s.t xij b j j 1, 2, n i 1 i 1, 2, , m xij 0 j 1, 2, n
TP SHUAI
15
3 选址问题（1）
实例:一组潜在位置（地址）, 一组顾客集合及相应的 利润和费用数据； 解: 设施开放(使用)的数目，他们的位置，以及顾客 被哪个设施服务的具体安排方案； 目标：总的利润最大化。 数据与约束 J={1,2,…,n}:放置设施的可能的潜在位置集合 I={1,2,…,m}:顾客集合,其要求的服务需要某设施所提 供.
TP SHUAI
23
TP SHUAI
24
TP SHUAI 11
1. 食谱问题
我每天要求一定量的两种维生素，Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到。
维生素 Vc(mg) Vb(mg) 单价(US$)
奶中含量 2 3 3
蛋中含量 4 2 2.5
每日需求 40 50
需要确定每天喝奶和吃蛋的量， 目标以便以最低可能的花费购买这些食物， 而满足最低限度的维生素需求量。
TP SHUAI 12
1. 食谱问题（续）
令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写 成如下的数学形式： Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0. 可行区域（单纯形） 可行解 极小化目标函数
运筹学工作者参与建立关于何时出现最小费用 （或者最大利润）的排序，或者计划，早期被标示为programs。 求最优安排或计划的问题，称作programming问题。
TP SHUAI
• 算法
5
绪论---运筹学（Operations Research - OR）
运筹学方法
最优化/数学规划方法
连续优化：线性规划、 非线性规划、非光滑优 化、全局优化、变分法、 二次规划、分式规划等 离散优化：组合优化、 网络优化、整数规划等 几何规划
