• 另外也可用学术味更浓的名称：“运筹 学”。由于最优化问题背景十分广泛，涉 及的知识不尽相同，学科分枝很多，因此 这个学科名下到底包含哪些分枝，其说法 也不一致。
• 比较公认的是：“规划论”（包括线性和
非线性规划、整数规划、动态规划、多目
标规划和随机规划等），“组合最优化”，
“对策论”及“最优控制”等等。
j
1, 2,L
,n
(5)
14
nn
min
cij xij
i 1 j 1
n
xij 1, i 1, 2,L
,n
s.t.
j 1 n
(5)
xij 1, j 1, 2,L , n
i1
xij
0
或 1 ,i,
j
1, 2,L
,n
(5)的可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只
mn
min
cij xij
i 1 j 1
n
xij ai ,
i 1, , m
j 1
s.t.
m xij bj ,
j 1,2, , n
i 1
xij
0
11
对产销平衡的运输问题，由于有以下关系式存在：
n
bj
j1
m
i1
n xij
j1
n m
j1 i1
xij
费的总时间最少？
引入变量 xij ，若分配 i 干 j 工作，则取 xij 1，否则取 xij 0 。上
述指派问题的数学模型为
nn
min
cij xij
i 1 j 1
n
xij 1,i 1, 2,L
,n
j1
s.t.
n
xij 1, j 1, 2,L
,n
i1
xij
0
或 1 ,i,
5
• 2009B 眼科病床的合理安排
二、最优化问题的一般形式
无约束最优化问题
minf (x)
xRn
约束最优化问题 minf (x) s.t. ci(x) 0,iE ci (x) 0,i I
目标函数
约束函数
最优解；最优值
6
三、最优化问题分类
分类1： 无约束最优化 约束最优化
分类2： 线性规划 非线性规划
尽可能少的钱办尽可能多的事，出行时，
如何走最短的路程到达目的地，等等。总
而言之，在经济如此发展，竞争如此剧烈，
资源日渐紧张的今天，人们做任何事，无
不望求事半功倍之术，以求或提效、或增
收、或节约等等之目标。
3
一、最优化概念
• 所有类似的这种课题统称为最优化问题， 研究解决这些问题的科学一般就总称之为 最优化理论和方法
容易看出，要给出一个指派问题的实例，只需给出矩阵 C (cij ) ，C
被称为指派Assignment Problem）
例 2 拟分配 n 人去干 n 项工作，每人干且仅干一项工作，若分配第 i 人 去干第 j 项工作，需花费 cij 单位时间，问应如何分配工作才能使工人花
组合最优化：决策变量是离散状态，同时可行域是
由有限个点组成的集合
典型组合优化问题：旅行商问题；加工调度问题；
0-1背包问题；图着色问题
9
2 线性规划
线性规划(Linear Programming 简记 LP)则是数学规划 的一个重要分支。自从 1947 年 G. B. Dantzig 提出求解线 性规划的单纯形方法以来，线性规划在理论上趋向成熟， 在实用中日益广泛与深入。特别是在计算机能处理成千上 万个约束条件和决策变量的线性规划问题之后，线性规划 的适用领域更为广泛了，已成为现代管理中经常采用的基 本方法之一。
10
一 常见线性规划模型
1 运输问题(产销平衡)
例 1 某商品有 m 个产地、 n 个销地，各产地的产量分别为 a1, , am ，
各销地的需求量分别为 b1, , bn 。若该商品由 i 产地运到 j 销地的单位运
价为 cij ，问应该如何调运才能使总运费最省？
引入变量 xij ，其取值为由 i 产地运往 j 销地的该商品数量，数学模型为
有一个元素为 1，其余元素均为 0，也可以用1, , n 中的一个置换表示。
(5)的变量只能取 0 或 1，从而是一个 0-1 规划问题。一般的 0-1 规划问题 求解极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特
输表上对它进行调整改进，得一新解；再判断，再改进，直到得到最优
解。
12
2 指派问题（又称分配问题 Assignment Problem）
例 2 拟分配 n 人去干 n 项工作，每人干且仅干一项工作，若分配第 i 人 去干第 j 项工作，需花费 cij 单位时间，问应如何分配工作才能使工人花
费的总时间最少？
4
数学建模竞赛中的优化问题
• 2000B 钢管订购和运输问题—二次规划 • 2001B 公交车优化调度 • 2001C 基金使用的最优策略-----线性规划 • 2002B 彩票中的数学 • 2003B 露天矿生产的车辆安排问题 • 2004A 奥运会临时超市网点设计问题 • 2004D 公务员招聘工作中录用方案—多目标规划 • 2005B DVD在线租赁 • 2006A 出版社的资源配置问题 • 2007A 乘公交，看奥运 • 2008B 高等教育学费探讨
线性规划：目标函数与约束函数均为线性函数；
非线性规划：目标函数与约束函数中至少有一个
是变量x的非线性函数；
7
三、最优化问题分类(续）
分类3 （根据决策变量、 目标函数和要求 不同）
整数规划 动态规划 网络规划 随机规划 几何规划 多目标规划
8
三、最优化问题分类(续）
分类４
函数最优化 组合最优化
函数最优化：决策变量是一定区间内的连续变量．
第一部分 最优化方 法及应用
1
1 最优化概提论 要
2 线性规划 3 非线性规划
4 多目标规划 5 动态规划 6 最优化问题小结
2
1 最优化概论
• 当今，“优化”无疑是一个热门词。做宏
观经济规划要优化资源配置，搞企业经营
管理要优化生产计划，作新产品设计要优
化性能成本比。就是在人们的日常生活中，
优化的要求也比比皆是，消费时，如何花
m
ai
i1
其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称
为表上作业法（由康托洛维奇和希奇柯克两人独立地提出，简称康—希
表上作业法）。
表上作业法是单纯形法在求解运输问题时的一种简化方法，其求解
工作在运输表上进行逐步迭代如下：先按某一规则找出一个初始解（初
始调运方案）；再对现行解作最优性判断；若这个解不是最优的，就在运