420
A13
210
A12
A14
195
31
306
480
A9
A10 300
A11
680
1150
10
201 A8
5
450
3 104
600 80
2 750
A3
301
A2
10 194
606 A5 A4
A6 205 A7
A1
问题1的基本模型和解法 总费用最小的优化问题
总费用：订购，运输（由各厂Si经铁路、公路至各点Aj, i=1,…7; j=1, …15 ），铺设管道Aj Aj+1 （j=1, …14)
目标函数值 f ( X * ) 的为最优化模型 Min{ f ( X ) | X D} 的（全局） 最优值；
称 X * D 为最优化模型 Min{ f ( X ) | X D} 的局部最优解，若存在
n
0 ， 对 X D { X Rn | ( xi xi* )2 } ， 均 有 i 1
max z 2x1 4x2 3x3 目标函数(利润最大化）
s.t.
3x1 4x2 2x3 60 2x1 x2 2x3 40 x1 3x2 2x3 80 x1, x2 , x3 0



约束条件


二、最优化方法的基本概念
在生产、经济与管理等领域中遇到的大量最优决策 问题，对一个方案的评价是多角度多指标的，反映在数 学模型中，优化的目标是关于决策变量的一个函数组， 我们称之为多目标规划问题。
引例
钢管订购和运输
S4 S3
S2
160
690
290
30 S7
160 320
70
20 20
30
70
1200
690 170
S6
A15
cm2 … cmn
d1
d2 … dn
产量
s1 s2
┇
sm
设 xij 为从产地 Ai 运往销地 Bj 的运
输量，根据这个运输问题的要求，可以建立 运输变量表。
销地 产地
B1 B2 … Bn
产量
A1
x11
x12 … x1n
s1
A2
x21
x22 … x2n
s2
┇
┇ ┇ ┇┇
┇
Am
xm1
xm2 … xmn
(5)
z1 0, y15 0
(6)
模型求解
利用MATLAB软件包求解得：
钢 厂 S1 S2 S3 S4 S5 S6 S7
订购量 800 800 1000 0 1015 1550 0
总费用
1278632
精品课件！
精品课件！
订购和运输方案表
订购量A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 S1 800 0 201 133 200 266 0 0 0 0 0 0 0 0 0 S2 800 179 11 14 295 0 0 300 0 0 0 0 0 0 0 S3 1000 139 11 186 0 0 0 664 0 0 0 0 0 0 0 S4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 S5 1015 0 358 242 0 0 0 0 0 0 415 0 0 0 0 S6 1556 0 0 0 0 0 0 0 0 0 351 86 333 621 165 S7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3
A3
301
104 A2
路、公路运输，铺设一条
A1
钢管管道 A1 A2 A15
火车站 公路 管道
450 里程（km） （沿管道建有公路）
钢厂的产量和销价（1单位钢管=1km管道钢管）
钢厂i
12
3
产量上限 si
800 800 1000
销价 pi （万元） 160 155 155
钢厂产量的下限：500单位钢管
最优化问题的一些典型的分类
根据决策变量的取值类型，可分为函数优化问题与 组合优化问题，称决策变量均为连续变量的最优化问题 为函数优化问题，否则，若一个最优化问题的有的决策 变量为离散取值，则称之为组合优化问题；
另外的一种分类方式是根据问题中目标、约束条件 函数的形式或性质来加以划分的：若一个最优化问题的 目标、约束条件函数均为决策变量的线性函数，则称之 为线性规划问题，否则称之为非线性最优化问题；
例、求解如下非线性规划: Min x12 2x1 x22 。 s.t. 0 x2 x1 2
基本概念
称 X* D 为最优化模型 Min{ f ( X ) | X D} 的（全局）最优
解，若满足：对 X D 均有 f ( X * ) f ( X ) ，这时称 X* D 处的
801～900 55
901～1000 60
1000km以上每增加1至100km运价增加5万元
1单位钢管的公路运价：0.1万元/km（不足整公里部分按整公里计）
（1）制定钢管的订购和运输计划，使总费用最小.
（2）分析对购运计划和总费用影响：哪个钢厂钢管销价的 变化影响最大；哪个钢厂钢管产量上限的变化影响最大？
(1)
15
s.t. xij {0} [500, si ] i 1,2, ,7
(2)
j 1
7
xij z j y j
j 1,2, ,15
(3)
i 1
y j z j1 l j
j 1,2, ,14
(4)
xij 0, z j 0, y j 0
i 1,2, ,7, j 1,2, ,15
由Aj向Aj Aj-1段铺设的运量为 1+ … +zj= zj( zj+1)/2 由Aj向Aj Aj+1段铺设的运量为 1+ … +yj= yj( yj+1)/2
基本模型
二次规划
min
7 i 1
15
cij xij
j 1
0.1 2
15
(zj(zj
j 1
1)
yj(yj
1))
sm
销量
d1
d2 … dn
于是得到下列一般运输问题的模型：

mn
Min f = cij xij
i=1 j=1
n
s.t.
j=1
xij
si
i = 1,2,…,m
im=1xij (=,)dj j = 1,2,…,n
xij 0 (i=1,2,…,m;j=1,2,…,n)
对于产销平衡问题，可得到下列运输 问题的模型：
产每种产品在消耗原料方面的各项技术条件和单位产品的
利润，以及可利用的各种原料的量（具体数据如下表），试
制订适当的生产规划使得该厂的总的利润最大。
产品 生产每单位产品所消耗的原料 现有原
原料
A
B
C 料的量
a
3
4
2
60
b
2
1
2
40
c
1
3
2
80
单位产品利润 2
4
3
一般数学模型
以 x1、 x2 、 x3 分别表示生产 A、B、C 三种产品的量， 称之为决策变量
mn
Min
f n
=
i=1

j=1
cij
s.t.
j=1
xij = si
m
i=1 xij = dj
xij i = 1,2,…,m (4-5) j = 1,2,…,n (4-6)
xij≥0(i=1,2,…,m;j=1,2,…,n)
在实际问题建模时，还会出现如下一些变化： （1）有时目标函数求最大，如求利润最大或
一、最优化问题举例
利用最优化理论和方法解决生产实践以及 科学研究中的具体问题，一般分为如下两 个步骤： • 建立数学模型； • 进行数学加工和求解
1、运输问题
假设某种产品有 m 个生产地，用
Ai (i 1,2...m) 表示，其产量分别为si (i 1, 2...m)；
有 n 个消费地点，用 Bj ( j 1,2...n) 表示，需要
营业额最大等； （2）当某些运输线路上的能力有限制时，模
型中可直接加入（等式或不等式）约束；
产销不平衡的情况。当销量大于产量时 可加入一个虚设的产地去生产不足的物资， 当产量大于销量时可加入一个虚设的销地去 消化多余的物资。
2、生产计划问题
某厂利用 a、b、c 三种原料生产 A、B、C 三种产品，已知生
Min{ f ( X ) | X D} 与 Min f ( X ) s.t. ci ( X ) 0 (i 1..m1 )
ci ( X ) 0 (i m1 1..m)
• 基本概念 • 最优化问题的一些典型分类
基本概念
X ( x1, x2 xn )T 表示一组决策变量，xi (i 1..n) 通常在实数域 R 内取值； 称决策变量的函数 f ( X ) 为该最优化模型的目标函数；
f (X*) f (X)。
基本概念
（全局）最优解一定是局部最优解，但反之不然，其关系可由 下图得到反映：
上图为函数 y x sin( x2 ) 在区间 [2,3.5] 上的一段函数曲线（由 Mathematica 绘制）
最优化问题的一些典型的分类
• 函数优化问题与组合优化问题 • 线性规划问题与非线性最优化问题 • 多目标规划
（3）讨论管道为树形图的情形