例2.多参数曲线拟合问题 已知两个物理量x和之间的依赖关系为： y=a1+ 11+ep as 其中a a a; a4和a待定参数，为确定这些参数， 对x,y测得m个实验点)()(ny) 试将确定参数的问题表示成最优化问题 X
例2. 多参数曲线拟合问题 已知两个物理量x和y之间的依赖关系为: 其中 和 待定参数,为确定这些参数, − + + = + 5 4 3 2 1 1 ln 1 exp a x a a a y a a1 a2 a3 a4 a5 x y 对x，y测得m个实验点: 试将确定参数的问题表示成最优化问题. ( ) ( ) ( ) 1, 1 2, 2 , , , . m m x y x y x y
解：很显然对参数44 aa和as任意给定的一组数值，就 由上式确定了y关于x的一个函数关系式，在几何上它对应一条 曲线，这条曲线不一定通过那个测量点，而要产生“偏差”. 将测量点沿垂线方向到曲线的距离的 平方和作为这种“偏差”的度量.即 f(aaz.as.as.a)=y- 显然偏差$越小，曲线就拟合得越好，说明参数值就选择得越好 从而我们的问题就转化为5维无约束最优化问题。即： min f(a,a,a,a,as) 最小二乘问题
解:很显然对参数 和 任意给定的一组数值,就 由上式确定了y关于x的一个函数关系式,在几何上它对应一条 曲线,这条曲线不一定通过那m个测量点，而要产生“偏差”. 将测量点沿垂线方向到曲线的距离的 平方和作为这种“偏差”的度量.即 显然偏差S越小,曲线就拟合得越好,说明参数值就选择得越好， 从而我们的问题就转化为5维无约束最优化问题。即： 1 2 3 4 a a a a a5 2 2 1 2 3 4 5 1 1 4 3 5 ( , , , , ) 1 ln 1 exp m i i i a f a a a a a y a x a a a = = − + − + + 1 2 3 4 5 min ( , , , , ) f a a a a a 最小二乘问题
例3：旅游售货员TSP问题 旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路一货郎担问题 送货地到达一次 总路程最短
例3：旅游售货员TSP问题 ⚫ 旅游线路安排 预定景点走且只走一次 路上时间最短 ⚫ 配送线路—货郎担问题 送货地到达一次 总路程最短
●有一旅行团从Y出发要遍游城市Y,2,,Vn, 已知从y,到V,的旅费为C,,问应如何安排行程使总 费用最小？ 模型： 变量一是否从第个城市到第个城市 x=1,0 约束—每个城市只能到达一次、离开一次 之xy=15i=1,2n ∑x=5j=1,2m i=(
⚫ 有一旅行团从 出发要遍游城市 ， 已知从 到 的旅费为 ，问应如何安排行程使总 费用最小？ 0 v 1 2 , ,..., n v v v j v i v ij c 模型： ⚫ 变量—是否从第i个城市到第j个城市 ⚫ 约束—每个城市只能到达一次、离开一次 1,0; ij x = 0 0 1; 1,2,... 1; 1,2,... n n ij ij j i x i n x j n = = = = = =
。目标一总费用最小 2Σ =00 min ∑zex i=0j=0 空==128 st. ∑x=j=L2n x=1或0，i=1,2,n,j=1,2,,n
⚫ 目标—总费用最小 0 0 n n ij ij i j c x = = 0 0 0 0 min 1; 1, 2,..., . . 1; 1, 2,..., 1 0, 1, 2,..., , 1, 2,..., n n ij ij i j n ij j n ij i ij c x x i n s t x j n x i n j n = = = = = = = = = = = 或