nbhkdz.com冰点文库

第三章-线性规划-1


线性规划
1. 线性规划模型 2. 标准型 3. 图解法 4. 解的概念和性质 5. 单纯形算法

一. 线性规划模型
例1 生产计划问题
某工厂利用某种原材料生产A、B、C三种产品,它们的单位 产品所需材料的数量和耗费的加工时间各不相同,如下表。 A、B、C单位产品的利润为4、、千元。问:该厂应如何安排 57 生产计划,才能使

所获利润最大?
产品

资源 原材料
工时

A 2 1

B
1 .5

C

资源总量
100 150

3

2

2

解: 1. 确定决策变量

设 A、B、C 的产量分别为x1、x2、x3 。

2. 确定目标函数

设总利润为 ,则 S
S ? 4 x1 ? 5 x2 ? 7 x3 3. 确定约束条件 2 x1 ? 1.5 x2 ? 3 x3 ? 100 x1 ? 2 x 2 ? 2 x 3 ? 150
x i ? 0 , i ? 1,2,3

4. 数学模型

S ? 4 x1 ? 5 x2 ? 7 x3 ? 2 x1 ? 1.5 x 2 ? 3 x 3 ? 100 ? s .t . ? x1 ? 2 x 2 ? 2 x 3 ? 150 ? x i ? 0, i ? 1,2,3 ? min

线性规划模型:
(1) 一组决策变量; (2) 一个线性目标函数; (3) 一组线性的约束条件。

线性规划模型 (LP )的一般形式:
min (max)

?c x
i i ?1

n

i

? a11 x1 ? a12 x 2 ? ? ? a1n x n ? ( ? , ? )b1 ? a x ? a x ? ? ? a x ? ( ? , ? )b 22 2 2n n 2 ? 21 1 ? ? s .t . ? ?a x ? a x ? ? ? a x ? ( ? , ? )b m2 2 mn n m ? m1 1 ? x i ? ( ? , ? )0 , i ? 1 , 2 ,? , n ?

二. 标准型
1. 标准型

min

?c x
i ?1 i

n

i

? a11 x1 ? a12 x 2 ? ? ? a1n x n ? b1 ? a x ? a x ??? a x ? b 22 2 2n n 2 ? 21 1 ? ? s .t . ? ?a x ? a x ? ? ? a x ? b m2 2 mn n m ? m1 1 ? x i ? 0 , i ? 1 , 2 ,? , n ?

记 c ? ( c1 , c2 ,?, cn )T , b ? ( b1 , b2 ,?, bm )T ? 0, x ? ( x1 , x2 ,?, xn )T , A ? (aij )m?n 。则线性规划 标准型可记为

min c T x
? Ax ? b s.t . ? ? x?0

2. 化标准型 (1)目标函数:

原问题目标函数: max
( 2) 约束条件:

cT x ? min

? cT x

(i ) 原问题条件 ai1 x1 ? ai 2 x2 ? ?? ain xn ? bi :
?a i 1 x1 ? a i 2 x 2 ? ? ? a in x n ? x n? i ? bi ?? x n? i ? 0 ?

xn? i 称为松弛变量。

(ii ) 原问题条件 ai1 x1 ? ai 2 x2 ? ?? ain xn ? bi :
?a i 1 x1 ? a i 2 x 2 ? ? ? a in x n ? x n? i ? bi xn? i 称为剩余变量。 ?? x n? i ? 0 ? ? x i ? ui ? v i ( iii ) 原问题: x i 无非负约束,则令? 。 ? ui , v i ? 0

例1 将下述线性规划模型化 为标准型。

max

2 x1 ? 3 x2 ? x3 ? 3 x4

? 2 x1 ? x 2 ? 3 x 3 ? x4 ? 3 ? 3x ? 2x ? 2x ? 7 ? 1 2 4 s .t . ? ? ? x1 ? 4 x 2 ? 3 x 3 ? x4 ? 6 ? x1 , x 3 , x4 ? 0 , x 2无约束 ?
解: 令x2 ? u2 ? v 2 , 则

min ? 2 x1 ? 3u2 ? 3v2 ? x3 ? 3 x4

? 2 x1 ? u2 ? v2 ? 3x3 ? x4 ? x5 ? 3 ? 3x1 ? 2u2 ? 2v2 ? 2 x4 ? 7 ? s.t. ? ?? x1 ? 4u2 ? 4v2 ? 3x3 ? x4 ? x6 ? 6 ? x1 , x3 , x4 , x5 , x6 , u2 , v2 ? 0 ?

三. 图解法
例2 求解线性规划max
s .t . z ? 4 x1 ? 3 x 2 ? x1 ? 2 x 2 ? 4 ? ? 2 x1 ? x 2 ? 5 ? x ,x ?0 ? 1 2

解: 1) 画出可行解的范围 ( 。

(2) 利用等值线平移的方法 求极值点。 x 2
以 z 为参数,则方程 4 x1 ? 3 x 2 ? z 表示一族等值平行线。

A

B

? 极大值点为 顶点B。

o

C

x1 x1 ? 2 x2 ? 4

2 x1 ? x2 ? 5

例 3 将例2中的目标函数改为 ? x1 ? 2 x2 。 z x2 解:分析同例2。 等值线:1 ? 2 x2 ? z。 x

A

B

?极大值点为线段 AB 上的 任一点。

o

C

x1 x1 ? 2 x2 ? 4

2 x1 ? x2 ? 5

max 例4 求解线性规划 s .t .
解:分析同例2。

z ? 4 x1 ? 3 x 2 ? x1 ? x 2 ? 2 ? ? x1 ? x 2 ? 2 ? x ,x ?0 ? 1 2
x2
A

等值线:x1 ? 3 x2 ? z。 4

x1 ? x2 ? 2
C

x1

?不存在最大值。

o

B

原问题无界。

x1 ? x2 ? 2

结果:
?在顶点取到唯一最优解 ?有最优解 ? ? 有无穷多最优解 ? ? 线性规划问题的解? ? 解无界 ? ?无最优解 ?? ? ?可行域为空集

四. 线性规划解的概念和性 质
1. 线性规划解的概念

(LP)

min

z ? c T x (1)
( 2) ( 3)

? Ax ? b s.t . ? ? x?0
( LP )的可行解。

可行解: 满足(2)、(3)式的解x ? ( x1 , x 2 ,?, x n )T 称为

可行域: ? { x | Ax ? b , x ? 0 }。 D

定理 线性规划问题的可行域 是凸集。 D
证明: 任取 x1 , x2 ? D , 0 ? ? ? 1。

A( ?x1 ? (1 ? ? ) x2 ) ? ?Ax1 ? (1 ? ? ) Ax2
? ? b ? (1 ? ? )b ?b

所以?x1 ? (1 ? ? ) x2 ? D。即D是凸集。
顶点: S为凸集,x ? S。如果不存在 x 1 ? x 2 ? S , 0 ? ? ? 1。 设 及 使 x ? ?x 1 ? (1 ? ? ) x 2 , 则称 x 为 S 的一个顶点。

x

x2 x1

基 : 设 A为m ? n的系数矩阵, 秩为m。 B 为A中m ? m 阶的非 若 退化子阵,则称B为A的(或( LP )问题)一个基。

设 基 B ? ( Pi1 , Pi2 , ? , Pim ) , 称 Pik ( k ? 1 , ? , m ) 为 基 向 量 , 称Pik 对 应 的 变 量x ik ( k ? 1 , ? , m ) 为 基 变 量 , 不 是 基 变 量 变 量 称 为 的 非基变量。
已知 r ( Am?n ) ? m , 不妨设 A的前m列向量线性无关,则可取 B ? ( P1 , P2 ,?, Pm ) 为基,则 x1 ,?, x m 为基变量。
Ax ? b

因为 即 所以

P1 x1 ? ?? Pm xm ? Pm ?1 xm ? ? ? Pn xn ? b P1 x1 ? ?? Pm xm ? b ? Pm ?1 xm ? ? ? Pn xn

令非基变量xm ?1 ? ? ? xn ? 0 , 解得
( x1 ,?, xm )T ? B ?1b
基本解: 取定线性规划问题的基 B,令非基变量取零,求得基 变量的取值B ?1b, 称解 ( B ?1b , 0)T 为对应于基 B的基本解。

基本可行解:满足非负 条件 的基本解称为基本可行 解。
例 给定(LP )问题 min

z ? x1 ? 2 x2 ? x3 ? 2 x4 ? x1 ? 2 x2 ? x3 ? 4 x4 ? 8 ? ? 2 x1 ? 2 x2 ? 2 x3 ? x4 ? 2 ? x1 , x2 , x3 , x4 ? 0 ?

s.t .

求此问题的一个基本解 和一个基本可行解。

?1 ? 2 ?1 4 ? ?。 解: 系数矩阵 A ? ? ? 2 2 ? 2 ? 1? ? 1 ? 2? 取B ? ? ?,则令非基变量 x 3 ? x4 ? 0 , 得 ?2 2 ? 10 ? ? x1 ? 3 ? x1 ? 2 x 2 ? 8 ?? ? 7 ? 2 x1 ? 2 x 2 ? 2 ? x2 ? ? ? 3 10 ? 7 ? x1 ? ( , , 0 , 0 )T 是基本解,但不是基本可行解。 3 3 ?1 4 ? 取B ? ? ?,则令非基变量 x 2 ? x 3 ? 0 , 得 ? 2 ? 1? 16 ? x1 ? ? ? x1 ? 4 x4 ? 8 9 ?? ? 14 ? 2 x1 ? x4 ? 2 ? x4 ? ? 9 16 14 ? x 2 ? ( , 0 , 0 , )T 是基本可行解。 9 9

可行解 基本可行解 基本解

可行解 满足约束条件(包括非负条件)的一组变 量值,称可行解。 所有可行解的集合称为可行域。 最优解 使目标函数达到最大的可行解称为最优解。 基本解 对于有n个变量、m个约束方程的标准型线性 规划问题,取其m个变量。若这些变量在约束方程中的系数列 向量线性无关,则它们组成一组基变量。确定一组基变量后, 其它n-m个变量称为非基变量。 令非基变量都为 0 ,解约束 方程,可唯一得到基变量的值,从而得到一个满足约束方程的 解,称为基本解。可见,一个基本解的非零分量个数不超过m 个。 基本可行解 满足非负条件的基本解称为基本可行解。 基本可行解既是基本解、又是可行解,它对应于线性 规划问题可行域的顶点。

五. 单纯形算法
1. 算法思路: 从一个基本可行解开始,判断其是否为最优解。 是则算法结束。不是,则转换到另一个更好的基本可行解, 直到找到最优解,或者判断出不存在最优解。

问题:
(1) 如何得到第一个基本可 行解? ( 2) 最优解的判定法则? (3) 如何从一个基本可行解 变换到另一个基本可行 解?

2. 单纯形算法分析
例1 求解线性规划问题 LP ) (

min s .t .

Z ? ?4 x1 ? 3 x 2 ? x1 ? 2 x 2 ? x 3 ? 4 ? ? 2 x1 ? x 2 ? x4 ? 5 ?x ,x ,x ,x ?0 ? 1 2 3 4

? 1 2 1 0? ?。 系数矩阵 A ? ? 解: ? 2 1 0 1?

? 1 0? ? , 则基变量为 x 3和 x4 , 非基变量为 x1和 x 2 。 令基 B ? ? ? 0 1?
? x 3 ? 4 ? x1 ? 2 x 2 ?? ? x 4 ? 5 ? 2 x1 ? x 2

代入目标函数得

z ? 0 ? 4 x1 ? 3 x2

? x3 ? 4 令 x1 ? x 2 ? 0 , 则 ? ? x4 ? 5

? 基本可行解x 1 ? ( 0 , 0 , 4 , 5 )T 。 目标函数值z 1 ? 0。

是否为最优解?利用目标函数分析。

? z ? 0 ? 4 x1 ? 3 x2 目标函数中非基变量x1 和 x2 的系数为负数,因此若 1 和 x2 的 x

取值可以增大为正数, 则目标函数值就可以减 小。
固定 x2 不变,考察x1 是否可以增大?
? ? x 3 ? 4 ? x1 ? 2 x 2 ? ? x 4 ? 5 ? 2 x1 ? x 2

? x 3 ? 4 ? x1 ? ? ? x 4 ? 5 ? 2 x1
? x3 ? 0 ?? ? x4 ? 0 ? x1 ? 4 ? ? ? 5 x1 ? ? ? 2
? x1 ? 5 2

5 且 x1 ? 时,x 4 ? 0。即 x1变为基变量,x 4 变为非基变量。 2 3 3 1 ? x3 ? ? x2 ? x4 ? ? x 3 ? 4 ? x1 ? 2 x 2 2 2 2 ? ? ? 5 1 1 ? x 4 ? 5 ? 2 x1 ? x 2 ? x1 ? ? x 2 ? x 4 ? 2 2 2
5 ? x1 ? ? 2 令 x2 ? x4 ? 0 , 则 ? 3 ? x3 ? ? 2

? z ? ?10 ? x2 ? 2 x4

5 3 ? 基本可行解x ? ( , 0 , , 0 )T 。 目标函数值z 2 ? ?10。 2 2
2

? z ? ?10 ? x2 ? 2 x4 因为x2 的系数为负,考察能否 增大 x2 。固定 x4 ,则
3 3 1 ? ? x3 ? 2 ? 2 x2 ? 2 x4 ? 5 1 1 ? x1 ? ? x 2 ? x 4 ? 2 2 2 3 3 ? ? x3 ? 2 ? 2 x2 ? ? 5 1 ? x1 ? ? x 2 ? 2 2

? x2 ? 1

且 x2 ? 1时,x3 ? 0。即 x2变为基变量, 3变为非基变量。 x
2 1 ? x2 ? 1 ? x3 ? x4 ? 3 3 ?? 1 2 ? x1 ? 2 ? x 3 ? x 4 ? 3 3

?

2 5 z ? ?11 ? x3 ? x4 3 3

? x1 ? 2 令 x 3 ? x4 ? 0 , 则 ? ? x2 ? 1

? 基本可行解x 3 ? ( 2 , 1 , 0 , 0 )T 。 目标函数值z 3 ? ?11。

2 5 因为目标函数 z ? ?11 ? x3 ? x4 , 其中 x 3 和 x4 的系数皆为正数, 3 3 所以目标函数值不能再 减小,所以最优解为
x* ? x 3 ? ( 2 , 1 , 0 , 0 )T , 最优的目标函数值为* ? z 3 ? ?11。 z

例 2 求解线性规划问题 LP ) ( min Z ? ?2 x1 ? x2 ? x3

s.t .

? x1 ? 3 x2 ? x3 ? 6 ? ?4 x1 ? 2 x2 ? x3 ? 8 ? x ,x ,x ?0 1 2 3 ?

解: 化标准型:

max s.t .

Z ? ?2 x1 ? x2 ? x3 ? x1 ? 3 x2 ? x3 ? x4 ? 6 ? ?4 x1 ? 2 x2 ? x3 ? x5 ? 8 ? x ,x ,x ,x ,x ?0 ? 1 2 3 4 5

一、常用的优化功能函数

?

求解线性规划问题的主要函数是linprog。

?
?

求解二次规划问题的主要函数是quadprog。
求解无约束非线性规划问题的主要函数是fminbnd、fminunc

和fminsearch。
?

求解约束非线性规划问题的主要函数是fgoalattain和 fminimax。

针对具体工程问题建立优 化设计的数学模型

不等式约束条件表示成g(X)≥0的形式

建立目标函数文件

文件内容:必须的输入参数、描述标函数表达式等 存储:以自定义的目标函数文件名存储在文件夹中 文件内容:必须的输入参数、约束函数表达式等 存储:以自定义的约束函数文件名存储在文件夹中

建立约束函数文件

建立调用优化工具函 数的命令文件

分析优化设计的数学模型,选择适用的优化工具函数 文件内容:初始点,设计变量的边界约束条件, 运算结果输出等内容 存储:以自定义的命令文件名存储于文件夹中。

将优化设计的命令文件复制到MATLAB命令窗口中进行运算求解。

1.主要应用对象: (1)在有限的资源条件下完成最多的任务; (2)如何统筹任务以使用最少资源。 非负数 2.数学模型形式: 决策变量 TX min f 目标函数 s.t. AX≤b (线性不等式约束条件) AeqX=beq (线性等式约束条件) 线 lb ≤X ≤ub (边界约束条件) 性

约 束 条 件

3.MATLAB中函数调用格式 [xopt, fopt]=linprog( f, A, b, Aeq, beq, lb, ub, x0, options)
最 优 解

最 优 值

目标函数 各维变量 系数向量

初 始 点

可 选 项

生产规划问题:某厂利用a,b,c三种原料生产A,B,C三种产品, 已知生产每种产品在消耗原料方面的各项指标和单位产品的 利润,以及可利用的数量,试制定适当的生产规划使得该工 厂的总利润最大。 生产每单位产品所消耗的原料 现有原料数 A→x1 B→x2 C→x3 量(千克) a b 3 3x1 2 2x1 1 x1 2 2x1

c
单位产品利润 (万元)

+ 4 4x + x + 1 3x + +3 + 4 + 4x +
2 2 2 2

2 2x3 ≤ 2 2x3 ≤ 2 2x3 ≤ 3 3x3

600 400

800
合计 1800千克

解: 1.确定决策变量 : 设生产A、B、C三种产品的数量分别是x1,x2,x3,决策变量: X=[x1,x2,x3]T 2.建立目标函数: 根据三种单位产品的利润情况,按照实现总的利润最大化, 建立关于决策变量的函数: 4.编制线性规划计算的M文件 5.M文件运行结果: max2x1+4x2+3x3 ’ f=[-2, - 4, -3] Optimization terminated 3.确定约束条件: 根据三种资料数量限制,建立三个线性不等式约束条件 A=[3,4,2;2,1,2;1,3,2]; successfully. b=[600;400;800]; 3x1+4x2+2x3≤600 xopt =0.0000 2x1+x2+2x3≤400 Aeq=[];beq=[]; 66.6667 x1+3x2+2x3≤800 lb=zeros(3,1); 166.6667 x1,x2,x3≥0 [xopt,fopt]=linprog(f,A,b,Aeq,beq,lb) fopt=-766.6667 [xopt, fopt]=linprog( f, A, b, Aeq, beq, lb, ub, x0, options)

非负数 Matlab数学模型形式: 决策变量 TX min f 目标函数 s.t. AX≤b (线性不等式约束条件) AeqX=beq (线性等式约束条件) 线 lb ≤X ≤ub (边界约束条件) 性

约 束 条 件

MATLAB中函数调用格式 [xopt, fopt]=linprog( f, A, b, Aeq, beq, lb, ub, x0, options)
最 优 解

最 优 值

目标函数 各维变量 系数向量

初 始 点

可 选 项

max f ? 3 x1 - x2 ? x3 ? x1 - 2 x2 ? x3 ? 11 ?- 4 x1 ? x2 ? 2 x3 ? 3 ? ? ?- 2 x1 ? x3 ? 1 ? x1 , x2 , x3 ? 0 ?

s.t.

编制线性规划计算的M文件 f=[ -3, 1, 1]’ A=[1,-2,1;4,-1,-2];(不等式约束) b=[11;-3]; Aeq=[-2,0,1]; ( 等式约束) beq=[1];(等式约束) lb=zeros(3,1); [xopt,fopt]=linprog(f,A,b,Aeq,beq,lb)

max f ? 4 x1 - 2 x2 ? x3 ? 2 x1 - x2 ? x3 ? 12 ?- 8 x1 ? 2 x2 - 2 x3 ? 8 ? ?- 2 x1 ? x3 ? 3 ?x ? x ? 7 ? 1 2 ? x1 , x2 , x3 ? 0

s.t.

编制线性规划计算的M文件 f=[ -4, 2, -1]’ A=[2,-1,1;8,-2,2];(不等式约束) b=[12;-8]; Aeq=[-2,0,1;1,1,0]; ( 等式约束) beq=[3;7];(等式约束) lb=zeros(3,1); [xopt,fopt]=linprog(f,A,b,Aeq,beq,lb)

1.研究意义: (1)最简单的非线性规划问题; (2)求解方法比较成熟。 决策变量 2.数学模型形式:
min f (X) ?
目标函数
二次 函数

s.t. AX≤b (线性不等式约束条件) AeqX=beq (线性等式约束条件) lb ≤X ≤ub (边界约束条件)

1 T X HX ? C T X 2

约 束 条 件

3.MATLAB中函数调用格式 [xopt, fopt]=quadprog(H,C, A, b, Aeq, beq, lb, ub, x0, options)
最 优 解

最 优 值

赛数 目 矩的 标 阵海 函

数次 数 目 向项 的 标 量系 一 函

初 始 点

可 选 项

2 求解约束优化问题 f ( X) ? 2x1 ? 2x 2 ? x 2 ? 2x1x 2 ? x 3 2 3 s.t. g( X) ? x1 ? 3x 2 ? 2x 3 ? 6 h( X) ? 2x1 ? x 2 ? x 3 ? 4

1 ,其中: 解:(1)将目标函数写成二次函数的形式 f ( X) ? 2 XT HX ? CT X
? x1 ? X ? ?x 2 ? ? ? ?x 3 ? ? ?
? 4 ? 2 0? H ? ? ? 2 4 0? ? ? ? 0 0 2? ? ?

x1 , x 2 , x 3 ? 0

?0? C ? ?0? ? ? ?1 ? ? ?

(2)编写求解二次规划的M文件: 结果 H=[4,-2,0;-2,4,0;0,0,2]; Aeq=[2,-1,1]; xopt=[2.571,1.143,0.000] beq=[4]; C=[0,0,1]; fopt=-16.4898 lb=zeros(3,1); A=[1,3,2]; [xopt,fopt]=quadprog(H,C,A,b,Aeq,beq,lb) b=[6]; [xopt, fopt]=quadprog( H, C, A, b, Aeq, beq, lb, ub, x0, options)

fminbnd

只求解单变量问题 要求目标函数为连续函数

fminsearch

适用于简单优化问题 可求解单变量和多变量问题

fminunc
可求解复杂优化问题

1.使用格式: [xopt,fopt]=fminbnd(fun,x1,x2,options)
设置优化选项参数 迭代搜索区间 目标函数 返回目标函数的最优值 返回目标函数的最优解

运行结果: 2.例题: xopt = 求解一维无约束优化问题f(x)=(x3+cosx+xlogx/ex) 0.5223 fopt = 在区间[0,1]中的极小值。 0.3974 解:(1)编制求解优化问题的M文件。 %求解一维优化问题 fun=inline(‘(x^3+cos(x)+x*log(x))/exp(x)’,‘x’);%目标函数 x1=0;x2=1;%搜索区间 [xopt,fopt]=fminbnd(fun,x1,x2)

(2)编制一维函数图形的M文件。 ezplot(fun,[0,10]) title('(x^3+cosx+xlogx)/e^x') grid on
[xopt,fopt,exitflag,output]

一维搜索方法的分类:
? 试探法:它是按照某种给定的规律来确定区间内插入点 的位置的。插入点位置的确定是为了使区间缩短的更快, 而不管函数值的分布规律。它包括:黄金分割法(0.618 法)、裴波纳契(Fibonacci)法等。

? 插值法(函数逼近法):这种方法是根据某点处的某些 信息(如函数值、一阶导数、二阶导数等)来构造一个 差值函数来逼近原来的函数,用插值函数的极小点作为 区间的插入点。它包括:二次差值法、三次插值法等。

一维搜索的试探法

黄金分割法(0.618法):
基本原理:
通过比较单峰区间内两个内分点的函数值,不断舍弃 单峰区间的左端或者右端的一部分,使区间按照固定区间 缩短率(λ=0.618)逐步缩短,直到极小点所在的区间缩 短到给定的误差范围内,而得到近似最优解。

一维搜索的试探法

黄金分割法(0.618法):
黄金分割法的内分点的选取原则:每次区间缩短都取相等 的区间缩短率(λ),同时插入点距离两个端点有对称性。

? ? 0.618
?1 ? b ? ? (b ? a) ? b ? 0.618(b ? a ) ? 2 ? a ? ? (b ? a) ? a ? 0.618(b ? a )

一维搜索的试探法

黄金分割法(0.618法):
计算步骤:
1)给定初始单峰区间 a b 和收敛精度?,将?赋值为0.618; 2)在区间[a, b]内,取两个内分点?1和? 2,并计算其函数值:

?1 ? b ? ? (b ? a) ? b ? 0.618(b ? a) ? 2 ? a ? ? (b ? a) ? a ? 0.618(b ? a) 和y1 ? f (?1 ),y2 ? f (? 2 )

一维搜索的试探法

黄金分割法(0.618法):
计算步骤:
3)比较函数值大小,根据区间消去法原理缩短区间: 若y1 ? y2,则极小点必在区间[? , ? 2 ]内,即[? , ? 2 ]为新区间,则

?1为新区间内的第一个试验点,即令b ? ? 2 , ? 2 ? ?1 , y2 ? y1,
而另一个试验点可按下式?1 ? b ? ? (b ? a )算出,它的函数值 为y1 ? f (?1 ); 若y1 ? y2,则极小点必在区间[?1 , b]内,即[?1 , b]为新区间,则

? 2为新区间内的第一个试验点,即令a ? ?1 , ?1 ? ? 2 , y1 ? y2, 而另外一个试验点可以按下式给出? 2 ? a ? ? (b ? a ), y2 ? f (? 2 )。

一维搜索的试探法

黄金分割法(0.618法):
计算步骤:
4)进行迭代终止条件检验,检查区间是否缩短到足够小和 y2 ? y1 b?a 函数值是否收敛到足够近,即 ? ?和 ? ?,如果 b y2 不满足条件,则转到第3)步;满足条件则继续执行下一步。 1 5)输出最优解x* ? (a ? b)和最优函数值y* ? f ( x* )。 2

一维搜索的试探法

黄金分割法(0.618法):
程序框图:

1.使用格式: [xopt,fopt]=fminsearch(fun,x0,options)
设置优化选项参数 初始点 目标函数 返回目标函数的最优值 返回目标函数的最优解

2.例题:求解二维无约束优化问题 f(x)=(x14+3x12+x22-2x1-2x2-2x12x2 +6)的极小值。 解:(1)编制求解二维无约束优化问题的M文件。 %求解二维优化问题 fun='x(1)^4+3*x(1)^2+x(2)^2-2*x(1)-2*x(2)-2*x(1)^2*x(2)+6'; x0=[0,0]; %初始点 [xopt,fopt]=fminsearch(fun,x0) (2)讨论。 将目标函数写成函数文件的形式: %目标函数文件search.m function f=search(x) f=x(1)^4+3*x(1)^2+x(2)^2-2*x(1)-2*x(2)-2*x(1)^2*x(2)+6; 则命令文件变为: %命令文件名称为eg9_4.m x0=[0,0]; %初始点 [xopt,fopt]=fminsearch(@search,x0)

运行结果: xopt = 1.0000 2.0000 fopt = 4.0000

附加参数

1.使用格式: [x,fval,exitflag,output,grad,hessian]=fminunc(@fun,x0,options,P1,P2…)
设置优化选项参数 初始点 调用目标函数的函数文件名 目标函数在最优解的海色矩阵

返回目标函数在最优解的梯度 优化算法信息的一个数据结构 返回算法的终止标志 返回目标函数的最优值
返回目标函数的最优解

2.例题: 已知梯形截面管道的参数是:底边长度c,高度h,面积 A=64516mm2,斜边与底边夹角为θ。管道内液体的流速与管 道截面的周长s的倒数成比例关系。试按照使液体流速最大确 定该管道的参数。 解:(1)建立优化设计数学模型 θ h 管道截面周长 s ? c ? 2h c f(X) sin ?
? x1 ? 2 ?h ? A 其中设计变量: ? ch ??h?ctg? ? 64516 管道截面积:X ? ? x 2 ? ??? ? ? ?

c?

64516 ? hctg? h

64516 2 x1 64516 2h ? ? x1ctgx2 ? ? hctg? ? min s ? x1 sin x 2 h sin ?

x1

x2

64516 2x 1 2.例题: f ( X) ? ? x1ctgx 2 ? x1 sin x 2 解:(1)建立优化设计数学模型 (2)编写求解无约束非线性优化问题的M文件
目标函数的文件(sc_wysyh.m): function f=sc_wysyh(x) %定义目标函数调用格式 a=64516;hd=pi/180; f=a/x(1)-x(1)/tan(x(2)*hd)+2*x(1)/sin(x(2)*hd); %定义目标函数 求最优化解时的命令程序: x0=[25,45]; %初始点 [x,Fmin]=fminunc(@sc_wysyh,x0); %求优语句 fprintf(1,'截面高度h x(1)=%3.4fmm\n',x(1)) fprintf(1,'斜边夹角θ x(2)=%3.4f度\n',x(2)) fprintf(1,'截面周长s f=%3.4fmm\n',Fmin)

计算结果 截面高度h x(1)=192.9958mm 斜边夹角θ x(2)=60.0005度 截面周长s f=668.5656mm

[x,fval,exitflag,output,grad,hessian]=fminbnd(@fun,x0,options,P1,P2…)

2.例题: 解:(1)建立优化设计数学模型 (2)编写求解无约束非线性优化问题的M文件 (3)编写绘制一维函数图形的M文件
xx1=linspace(100,300,25); xx2=linspace(30,120,25); [x1,x2]=meshgrid(xx1,xx2); a=64516;hd=pi/180; f=a./x1-x1./tan(x2*hd)+2*x1./sin(x2*hd); subplot(1,2,1); h=contour(x1,x2,f); clabel(h); axis([100,300,30,120]) xlabel('高度 h/mm') ylabel('倾斜角\theta/(^{。})')

title('目标函数等值线') subplot(1,2,2); meshc(x1,x2,f); axis([100,300,30,120,600,1200]) title('目标函数网格曲面图')

3

2

1

序号
1 2 3 4 5

功能
输出形式 解x的精度 函数f的精度 约束g的精度 选择主要算法

默认值及其含义
0,无中间结果 输出 1e-4 1e-4 1e-6 0

说明
Options(1)=1,按照表格输出结果 Options(1)=-1,隐藏警告信息 Options(2)设置x解的终止条件 Options(3)设置函数f的终止条件 Options(4)设置约束g的终止条件 Options(5)选择主要优化算法

6

搜索方向算法

0

fmin()函数为无约束优化搜索方向提 供3种算法: Options(6)=0,拟牛顿法BFGS公式 Options(6)=1,拟牛顿法DFP公式 Options(6)=2,梯度法
fmin()函数为无约束优化的步长一维 搜索提供2种算法: Options(7)=0,二次和三次混合插值法 Options(7)=1,三次多项式插值法

7

步长一维搜索

0

3

2

1

序号
8 9 10 11 12 13

功能
函数值输出 梯度检验 函数计算次数 梯度计算次数 约束计算次数

默认值及其含义
0,不检验

说明
Options(8)输出最终迭代函数值 Options(9)比较梯度 Options(10)输出函数计算次数 Options(11)输出函数梯度计算次数 Options(12)输出约束计算次数

等式约束个数 0,等式约束为0 Options(13)输入等式约束个数

14
15

最大迭代次数
目标个数

100n Options(14)输入最大迭代次数 (n为变量维数)
0 Options(15)输入目标个数

16
17

差分步长 最小值
差分步长 最大值

1e-8
0.1

Options(16) 步长的下限或变量的最小梯度值
Options(17) 步长的上限或变量的最大梯度值

18

步长

Options(18)


第三章 3.3.2 简单的线性规划问题(1)

第三章 3.3.2 简单的线性规划问题(1)_高一数学_数学_高中教育_教育专区。必修5 第三章:不等式课后练习题 3.3.2 简单的线性规划问题(一) 课时目标 1....

必修2第三章简单的线性规划问题(1)教案

必修2第三章简单的线性规划问题(1)教案_数学_高中教育_教育专区。第 2 课 教学内容 (单元) 主题 3.3.2 简单的线性规划问题(1) 1 课时 1、使学生了解二元...

《运筹学》 第三章线性规划对偶理论与灵敏度分析习题及 答案

第三章线性规划对偶理论与灵敏度分析习题一,思考题 思考题 1.对偶问题和对偶变量的经济意义是什么? 2.简述对偶单纯形法的计算步骤.它与单纯形法的异同之处是...

第三章 线性规划的对偶理论及灵敏度分析1

第三章 线性规划的对偶理论及灵敏度分析1_财务管理_经管营销_专业资料。运筹学第三章 线性规划的对偶理论及灵敏度分析 第22页 第三章 线性规划的对偶理论及灵敏...

第三章线性规划的解法习题解答090426y

第三章 线性规划的解法 §3.1 重点、难点提要 线性规划问题的图解法及几何意义 1.图解法。 线性规划问题采用在平面上作图的方法求解,这种方法称为图解法。...

数学人教A版必修5第三章3.3.2简单的线性规划问题(第1课时)

数学人教A版必修5第三章3.3.2简单的线性规划问题(第1课时)_数学_高中教育_教育专区。第 1 课时 简单的线性规划问题 1.了解线性规划中的基本概念. 2.会用图...

高中数学 第三章 简单线性规划教案1 北师大版必修5

高中数学 第三章 简单线性规划教案1 北师大版必修5_数学_高中教育_教育专区。§4.2 教学目标: 简单线性规划(1) 1.了解线性规划的意义及线性约束条件、线性目标...

简单的线性规划第一课时习题(有答案)

简单的线性规划课时习题(有答案)_数学_高中教育_教育专区。习题配置精准,...第 1 页共 1 页 人教 A 版 数学习题 必修 5 第三章 3.3.2 第一课时...

第三章 整数线性规划

运筹学整数线性光规划运筹学整数线性光规划隐藏>> 第三章 整数线性规划本章, ...1. MATLAB 程序说明程序名: 程序名 intprogram, L01p_e, L01p_ie, trans...

江苏省高中数学必修五第三章:3.2简单的线性规划(1)教案

江苏省高中数学必修五第三章:3.2简单的线性规划(1)教案_数学_高中教育_教育专区...? x ? 与不等式组(1)的区域的交点 3 3 z 满足不等式组(1) ,而且当...