将 Ax=b 的任一解 x 用非基变量表示为
确定进基变量
◎最优性定理
◎定理:BFS的提高 给定目标值为z0的非退化基本可行解，且假定存
在 j 使得 rj < 0，则 i) 如果用 aj 替换基中某列得到了新的BFS，则新解
处的目标值比 z0 严格小. ii) 如果任何替换都产生不了新的BFS，则问题无界.
例3. 其它应用
• 数据包络分析(data envelope analysis, DEA) • 网络流问题(Network flow) • 博弈论(game theory)等
线性规划的一般形式 一般形式 转化 标准形
称 松弛(slack)/盈余(surplus)变量
线性规划的标准形(分析、算法)*****
的产品数量
目标函数： 产量约束： 销量约束： 非负约束：
问题中目标和约束函数都是线性函数, 称此类型的问题为线性规划问题.
优化实例2：数据拟合(data fitting problem) 已知： y y3
y2 y1
t1 t2 t3
t tm
推测：信号具有指数衰减和振荡行为！
模型函数(经验函数)：
其中
是待定参数
极点
线性方程组 的基本性质
代数理论 (与表述形式有关)
设计算法
凸集理论
几何理论
(与表述形式无关)
直观理解
凸集的定义及性质
称 中的集合 C 是凸的(convex)，如果对每个 x, y 及每
个
，点
.
几何解释：连接集合中任两点的线段仍含在该集合中
性质
称集合C是锥(cone)，如果
蕴含着对所有
有
. 若锥 C 还是凸的，称为凸锥(convex cone).
向量表示： 标准形的特征：极小化、等式约束、变量非负
例5. 化成标准形
等 价 表 示 为
5
基本解与基变量(*****)
其中 满秩假定：m<n，且A的行向量线性无关
定义 设B是A 的m个线性无关列组成的矩阵， 置 其余列所对应的变量为零，称所得方程组的解是 Ax=b的基本解(basic solution) 称B是基(basis)； 称与B对应的变量为基变量(basic variables)
一些重要的凸集
超平面(hyperplane): 正/负闭半空间： 多面集(polyhedral set):
有限个闭半空间的交集
推 广
平面上：多边形 注：任一线性规划的可行集是多面集！
极点
几何上：极点即不能位于连接该集合中其它两点的开线段 上的点
定义 称凸集 C 中的点 x 是 C 的极点，如果存在 C 中的点 y,
例1. 食谱问题
◎ 问题：确定食品数量，满足营养需求，花费最小？
n种食品，m种营养成份； －第 j 种食品的单价 －每单位第 j 种食品所含第 i 种营养的数量 －为了健康，每天必须食用第i 种营养的数量
◎ 变量： －食用第 j 种食品的数量 ◎ 模型：
4
例2. 目标函数中含绝对值的问题
假设： 事实： 转化为：
基本解
基变量
一般地：
只要有m个单位列
非基变量 即可，次序可以打乱！
8
规范形的转换问题
◎ 替换问题
假设在上述规范形中，想用
⊙ 什么时候可以替换？ ⊙ 替换后新规范形是什么？
转轴(pivot)
◎ 当且仅当
，可以替换
◎ 替换后，新规范形的系数
转轴公式
－转轴元(pivot element)
第二种解释： 表格中第 i 列的数据－用当前基表示 ai 时的系数
7
例1.
例2.
K 有3个极点 有3个基本解，均可行
K 有2个极点 有3个基本解，2个可行
例3.
Subject to
x*=(3/2, 1/2) － 极点
问题/作业 考虑集合
5个极点
证明这两个集合的极点是一一对应的！
3.2 单纯形法
单纯形法简介
• 适用形式：标准形(基本可行解=极点) • 理论基础：线性规划的基本定理！ • 基本思想：从约束集的某个极点/BFS开始，
课程主题
介绍线性与非线性规划的－－ 基本理论、实用算法和部分应用
具体的主题包括： • 线性规划
基本性质、单纯形法、对偶理论、网络流问题、整数规划
• 非线性规划
最优性条件、凸性、Lagrange对偶、半定规划 无约束优化的算法：线搜索法和信赖域法 约束优化的算法：二次规划、罚函数法、SQP法
• 多目标决策简介
基本可行解
定义 称
的非负基本解是标准形的基
本可行解(basic feasible solution)；
◆ 退化基本可行解：某个或某些基变量取零的基本可行解！ 问题：基本可行解与基的对应关系？(见习题2.5)
例. 基本可行解及几何意义
基本可行解的个数不超过
线性规划的基本定理(*****)
考虑线性规划标准形，其中A是秩为m的m×n 矩阵，则以下结论成立：
例1. 求下列方程组以
转轴
为基变量的基本解
转
轴
转 轴
转 轴
x=(0,0,0,4,2,1)
如何得到第一个规范形
处理：给表格附加m个单位列向量开始迭代，用A
中的列依次替换这些单位列向量
例2. 利用转轴解方程组
为了得到第一个规范形，形成增广表格
以下运算 同例1 !
3.2.2 BFS→相邻BFS(极点→相邻极点)
Pareto最优性和折衷曲线 目标规划
先修课程：线性代数，高等数学，最好会某种高级语言
课本与教辅材料：
1. 刘红英，实用优化方法讲义，北京航空航天大学，数学与系统科学学 院，2010年2月.
2. 陈宝林，最优化理论与算法(第二版)，清华大学出版社 3. 平时和作业 实践环节 期中考试 期末考试
实用优化方法(最优化理论与算法B)
54课时/3学分
刘红英 数学与系统科学学院 liuhongying@(个人邮箱) buaa_optimization@(公共邮箱，密码： 111222) (课程主页)
变量： 余量/残差(residual)：
确定参数！
非线性最小二乘问题
• 注1： 它说明即使变量数很小，计算目标函数也可能 很昂贵. 这里，n=6， m很大(比如10^5).
• 注2：数据拟合、参数估计、回归分析等许多问题中 均涉及此类优化问题.有专用的算法求解.
2
1.2 数学规划问题的分类与特征
连续与离散
z 和某
，有
则必有 y=z.
极点与基本可行解的等价性定理
考虑线性规划标准形，其中A是秩为m的m×n 矩阵，令
则x是 K 的极点当且仅当x是线性规划的基本可行解.
线
推论：
性
几
i) 若K非空，则至少有一个极点.
何 形
式
ii) 若线性规划有解，则必有一个极点是最优解.
规 划 基 本 定 理
的
iii) K的极点集是有限集.
• 1947年, G. Dantzig于发明了单纯形法
• 1979年，L. Khachain找到了求解线性规划的一 种有效方法(第一个多项式时间算法－椭球内点法)
• 1984年，N. Karmarkan发现了另一种求解线性 规划的有效方法，已证明是单纯形法的强有力的 竞争者(投影内点法)
• 现在求解大规模、退化问题最有效的是原－对偶 内点法
设x’是BFS, 且规范形如前，且假设 aq 进基 ◎问题：确定出基变量，使转轴后新规范形对应BFS？ 因为
所以
令 可否选取合适的
使得
是BFS ？
9
确定离基变量
至少有一个正元
例3. 考虑线性方程组
转 轴
B=(a1,a2,a3) X=(4,3,1,0,0,0)
a4进基
a1进基
x=(0,1,3,2,0,0)
优化问题的简单分类与求解难度
问题的求解难度依次增加！
1.3 优化算法和优化软件
◎ 优化算法
• 迭代法 • 从最优解的某个初始猜测出发，生成一个提高
的估计序列，直到达到一个解. • 大部分利用目标函数和约束，可能还有这些函
数的一阶和二阶导数. • 通常收敛到
(无约束问题)驻点或者 (约束问题)KKT点(极大点、极小点或鞍点). 如果问题是凸规划，则可确保算法收敛到全局极小点.
6
线性规划解的几何特征
可行集：多边形(二维)→多面集(高维空间)
• 有解：唯一解/多个解(整条边、面、甚至
整个可行集)
有顶点解
• 无界：没有有限最优解 • 不可行：没有可行解
无解
给出有效的代数刻画和严谨的几何描述，从理论上证 实上述几何特征，并寻求有效算法
与凸性的关系
线性规划的基本定理(标准形)
基本可行解
◎ 优化软件
• AMPL: A Modeling Language for Mathematical Programming
• Lindo/Lingo软件(\verb" " • Matlab优化工具箱(见姜启源等编的《数学实验》,
高教出版社) • Cplex • 其它(Mathematica, Minos, Excel等的优化功能).
• 选择特定算法：很重要--决定求解速度及质 量(无通用优化算法，有求解特定类型优化 问题的算法)
优化实例１：运输问题(transportation problem) 背 景：化学制品公司考虑某种产品的产销问题.
数 据：
问 题：确定从每个工厂运送到每个销地的产品 数量，使其满足需求，同时极小化费用
变 量：
依次移动到相邻极点/BFS，直到找出最优 解，或判断问题无界.