当前位置：文档库 › matlab生产调度问题及其优化算法

matlab生产调度问题及其优化算法

生产调度问题及其优化算法（采用遗传算法与MATLAB编程）

信息014 孙卓明

二零零三年八月十四日

生产调度问题及其优化算法

背景及摘要

这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M

N)!

(种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。

本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。

一．问题重述

某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加

工序产品

1 2 3 4 5 6 7 8

S T S T S T S T S T S T S T S T

1 C 8 A

2 B 4 C 24 D 6

2 A 4 D 5 B

3 C 4

3 C 3 D 7 A 15 B 20 A 8

4 B 7 C 6 D 21 A 1 D 16 C 3

5 D 10 B 4 C 8 D 4 A 12 C

6 D 1

6 A 1 B 4 A

7 C 3 D 5 A 2 C 5 A 8

条件：1、每件产品必须按规定的工序加工，不得颠倒；

2、每台设备在同一时间只能担任一项任务。

（每件产品的每个工序为一个任务）

问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。要求：给出每台设备承担任务的时间表。

注：在上面，机器 A ，B ，C ，D 即为机器 1，2，3，4，程序中以数字1，2，3，4表示，

说明时则用A ，B ，C ，D

二．模型假设

1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加

工，同时加工过程为不间断； 2．所有机器均同时开工，且工件从机器I 到机器J 的转移过程时间损耗不计； 3．各工件必须按工艺路线以指定的次序在机器上加工多次；

4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。

三．符号说明及初始数据表达分析

i J - 第i 个工件（i=1…6）

M J - 机器顺序阵）（j i J M

,表示i 工件的第 j 个操作的机

器号

j M - 第j 台机器（j=1…4）

J M - 工件排列阵 ),(j i M J 表示i 机器上第j 次加工的工件

号

T - 加工时间阵 ),(j i T 为i 工件的第 j 个操作的时间周期 C - 整个任务完成时间

整理数据后得到：

M J =[ C A B C D 0 0 0 ] T = [ 8 2 4 24 6 0 0 0 ]

[ A D B C 0 0 0 0 ] [ 4 5 3 4 0 0 0 0 ] [ C D A B A 0 0 0 ] [ 3 7 15 20 8 0 0 0 ] [ B C D A D C 0 0 ] [ 7 6 21 1 16 3 0 0 ] [ D B C D A C D 0 ] [ 10 4 8 4 12 6 1 0 ] [ A B A C D A C A ] [ 1 4 7 3 5 2 5 8 ] 上述二阵直接从题目得出，而J M 则是我们要求的。

关于工件的加工时间表：(表二)

产品/工件（i ）: 1 2 3 4 5 6 总

计

J 总净加工时间（周期） 44 16 53 54 45 35 247 i J 加工工序总数（个） 5 4 5 6 7 8 35

关于机器的加工时间表(表三) 机器/设备(j): A B C D 总计 j M 总净加工时间 60 42 70 75 247

M 加工操作次数 10 6 10 9 3

分析：

由于各产品总净加工时间和各机器总净加工时间之中最大值为 75，而总计为247，那么总时间 C 介于[75，247]。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。

希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D 不间断工作,直至全部加工任务完成。

四．贪婪法快速求解

如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:

1. 优先选择总剩余时间或总剩余操作较多的工件。（如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析）。

2. 机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器 D ,即倘若能够使机器D 不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。

首先按照最优化时间为75的设想避免D 出现等待，排序后得到升以下具体排列顺序。

操作1 操作2 操作3 操作4 操作5 操作6 操作7 操作8 操作9 操作10

6 (1) 2 (2-5) 1 (12-13)

6 (14-20)

3 (21

-35)

4 (36)

5 (43-54)

6 (55-56) 3 (57-64) 6

(66-73

) B

4 (1-7)

6 (8-11)

(12-15)

(16-19)

(36-55)

(56-58

)

(1-3)

(4-11)

(12-17)

(18-25)

(26-28)

(29-52)

(55-60)

(61-65)

(66-69)

(70-72

) D

(1-10)

(11-17)

(18-38) 5

(39-42)

(43-47)

(48-52)

(53-68)

(69-74)

1037178

6464

31675242015162

666

512

4238

3040

D 机器C 机器B 机器

A 机器 (图一)

上图为加工周期图（甘特图），标注数字为相应操作的周期，完工时间为第75周期。

五．计算机随机模拟（编程）

1．编码：

随机产生生产的工序操作优先顺序，进行编码，如：K=[ 4 3 5 6 6

2 3 1 4

1 6 3 5 4 5 3 6 6 4 1 5 5 1 3

2 6 2 2 4 4 1 5 6 6 5 ] （注：同时作为下文的

染色体之用）意思为：工件4优先被考虑进行第一次操作，然后3进

行其第一步操作，然后5操作，6操作，再6操作其第二步工序，依次

进行。如果前后互相不冲突，则可同时在不同机器上操作。

通过排列组合得出，总共有类似K的排列序列223

多种！

当然，这其中只对应解[75，247]，意味着有大量排列序列对应同一加

工方案，而大量加工方案又对应同一时间解。

2．解码：

即对编码进行翻译，产生具体可操作工序安排方案，这里采用活动化解码算法。例如工件2第i步操作（记为

J（2，i），且在机

器A上进行）被安排在工件3第j步操作（记为JM（3,j））后面进行，

那么如果安排好

J（2，i）在工件2已经排序好的操作之后进行，那（3,j）后，只要

么操

J（2，i）可插入到机器A处最前可安置的时间段进行。

作

在这里，一个编码序列对应一个加工方案，而一个加工方案可对应一个或多个编码序列，这就是二者之关系。

3．编程：

通过一组随机编码产生一生产加工优先序列，通过解码过程产生相应加工方案及其总耗费时间C . N次模拟后即可得出解C的概率密度

分布情况以及相对最优解（N个C的最小值，如80，77等，甚至出现

75）。

4．计算机模拟所得数据分析

a. 进行100次模拟得出最优解情况：(共运行10次)

82，83，82，84，78，80，81，83，87，82 平均值82.2，每回耗时约3秒b. 进行1000次模拟得出最优解情况：(共运行10次)

80，79，78，78，79，79，76，80，77，78 平均值78.4 , 每回耗时25秒

c. 进行10000次模拟得出最优解情况：(共运行10次)

76，77，77，75，76，76，77，76，76，77 平均值76.3, 每回耗时4分钟

d. 模拟1000000次得到的解C的概率密度分布情况为：（如图二所示）

( 图二)

（注：75处为17次（概率为17/1000000=1/58823），76处为40次，77处167次）

结论：如果想将223

?中排序序列以平均出现一次的可能性进行模拟，

即运行223

?次，计算机需运行将近150万亿年！当然，我们没有

这个必要，因为我们只需要运行数万次，就很可能得到最优解75，

（在随机模拟1000000次后出现17次75，那么意味着概率大约

17/1000000=1/58823，另外76处为40次，77处167次）。

六．遗传算法模型建立和步骤解法

遗传算法（Genetic Algorithm）作为一种优化算法特别适合于对象模型难于建立、搜索空间非常庞大的复杂问题的优化求解。它和模糊控制技术一样，虽然在理论上还没有完善，但是在实践中已经得到了广泛的应用。遗传算法的基本思想是：模仿生物系统“适者生成"的原理，通过选择、复制、交叉、变异等简单操作的多次重复来达到去劣存优的目的，从而获得问题的优化结果。遗传算法的实现由两个部分组成，一是编码与解码，二是遗传操作。其中遗传操作又包括选择、复制、交叉、变异等步骤。

本文根据实际情况采取了1-6整数编码。数字1，2，3，4，5，6分别代表6件待加工产品。

本文遗传算法基本流程:

通过编码，解码程序随机产生N个（有一定数量,如50或100）个体构成初始种群

a)从初始中群中选取2个具有最优染色体（最有

排序方案）的个体作为临时个体（父代）；b)如果此2个体中有一个个体通过解码操作能

够实现最优排序（即使总时间为75周期），那么结束此算法，得到最优解；

c)对2个临时个体以一定方式(循环交叉)执行

染色体交叉变换和变异选择（小概率,互换操作），产生2个新的个体；

d)对父代和子代共4个个体进行选择，从中选出

最佳的2个个体，做为下一代的父代；

e)重复执行第二步(b)操作；

f)如果执行完M步后仍然未得出答案75，那么

将目前的最优解作为本算法的最优解答案。1．编码和解码（同上）

2．交叉变换(crossover)

对2个父代临时个体进行染色体交叉变换，采用循环交叉方法（Cycle crossover CX），如父代染色体为：X：[9 2 6 4 7 3 5

8 1]和Y：[3 4 5 8 1 6 7 2 9]，如果随机

选到第二位开始交叉，那么X的2对应Y的

4，X的4对应Y的8，X的8对应Y的2，

这样就确定了以上为不变的染色体，其余位

置的染色体互换位置，最后得到X': [3 2 5

4 1 6 7 8 9], Y': [9 4 6 8 7 3

5 2 1],

实现交叉变换。

3．变异选择（mutation）

采用互换操作（SWAP），，即随机交换染色体中两不同基因的位置。如上面的染色

体为：X': [3 2 5 4 1 6 7 8 9] 。随机产

生变换位置号，如产生随机数3和5，那么

交换数字后得到染色体： [3 2 1 4 5 6 7 8 9]，变异概率取0.1 。

4．选择操作（selection）

对父代2个体f1,f2和子代2个体f3,f4进行选择，通过编码操作确定具有最

优解的2个个体，成为新一代f1和f2 。

如此，通过多次编码和解码随机产生一定数量的个体，选取2个最佳个体进行交叉变换操作，产生2个新个体，然后对4个个体进行选择，产生下一代，如果某时刻通过解码操作得出最优解（所有解的下限，这里是75周期），那么算法结束，否则循环进行，直至预先给定的循环次数达到为止，以最后得到的最优解作为最终最优解。

七．遗传算法模拟（采用MATLAB工具编程）

主程序如下：（子程序见略）

% 本程序为主程序，调用以下各分支程序

task= 'Welcome! Wait a moment please! --- Writer: 孙卓明 ,信息 014',

f1=zeros(1,35);f2=zeros(1,35);

while f1==f2; % 此步避免初始染色体 f1,f2 相同，导致以下死循环

[minminmax1,s1]=chushijie(N); % 种群初始化；基于操作的编码策略；活动化解码算

法;chushijie(N) 参数 N 为初始种群数

f1=s1 ; minminmax1, % 选取的第一个初始个体

[minminmax2,s2]=chushijie(N); % 再次种群初始化

f2=s2 ; minminmax2, % 选取的第二个初始个体

end;

for e=1:M; % e=1:M 进行 M 次遗传操作（交叉-变异-选择)

[D]=jiaocha(f1,f2); % 交叉变化（循环交叉操作，cycle crossover CX）,选

取

f1; f2; “染色体”无需变动部分基因

[f3,f4]=jiaocha_bianyi(f1,f2,D); % 生成交叉后的“染色体”,并进行变异选择

f3; f4;

[f1,f2]=xuanze(f1,f2,f3,f4); % 选择：对父代f1,f2和子代f3,f4进行解码，得出2个f1; f2; 较优个体，成为下一代的父代

[minmaxf1,a1,b1]=tongbujinzhan(f1); % 求该时刻个体f1的最优时间(因为f1优于f2)

if minmaxf1==75;

f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,

task='Finish! Successful! Best answer! Congratulation! ' , return ;

end; end;

f1,a1,b1,minminmax1,minminmax2,minminmax_last=minmaxf1,

if minminmax_last>=90; task='Finish! Action again please!',end;

if minminmax_last>=80&&minminmax_last<90; task='Finish!' , end;

if minminmax_last<80; task='Finish! Successful!', end;

八．遗传算法模拟结果

首先给出最优方案:

在进行某次n=100,m=200的操作后得到模拟最优结果75周期时间：

minminmax1 =83 minminmax2 =78 （二个初始较优个体解）

f1 =[4 5 6 6 3 1 3 6 4 5 6 1 3 2 5 4 5 3

1 5

2 6 4 5 6 4 6 6 4

3 2 2 5 1 1]

（f1为

各工件优先选择顺序排列,即“染色体”）a1 = 5 35 39 64 0 0 0 0 0 （a1,b1为四台机器空闲周期段）

15 24 0 0 0 0 0 0 0

17 53 65 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

b1 =11 38 42 65 0 0 0 0 0

20 35 0 0 0 0 0 0 0

18 54 68 0 0 0 0 0 0

0 0 0 0 0 0 0

0 0

minminmax = 75 （最终最优解）

其中机器A空闲时间段为:5-11,35-38,39-42,64-65; 机器B则为:15-20,24-35; 机器C为:17-18,53-54,65-68;机器D无空闲。

以下为:取不同N和M值情况下数据优化过程以及时间上的比较: ( 表五 )

N N M 第一

次运

行第二

次运

行

第三

次运

行

第四

次运

行

第五

次运

行

平均运行时间

1 1 1 104-1

14-98 98-10

5-93

92-9

3-92

100-1

32-95

86-86

-84

1 1 10 106-9

7-86 108-1

00-89

102-8

7-87

99-90

-90

88-10

4-84

1 1 100 94-8

1-81 81-10

2-78

91-10

5-91

101-8

4-80

90-10

1-90

1 1 100

0 107-1

00-78

92-10

1-76

101-1

00-82

88-9

7-86

91-93

-87

8.5(s)

1 1 100

00 88-10

5-77

103-8

1-77

89-9

9-84

107-1

04-78

93-10

5-78

80(s)

1 0 1

10 90-10

8-90

104-9

1-83

104-1

00-93

95-9

8-87

105-1

06-87

11100 98-9693-988-90105-991-95/

0 0 -96 9-90 -80 2-80 -85

1 0 1

100

101-9

6-78

91-8

9-80

96-10

4-87

105-1

05-84

88-99

-78

9.5(s)

1 0 1

100

99-9

2-77

97-9

5-75

96-10

4-76

89-9

9-76

91-10

1-75

90(s)

1 0 0 1

100 95-10

0-86

98-9

0-80

104-9

9-78

93-8

8-81

92-9

9-80

1 0 0 1

100

109-9

8-85

91-10

0-82

100-9

9-77

114-1

01-84

96-11

0-76

11(s)

1 0 0 1

100

96-10

1-78

101-8

6-76

101-9

7-80

99-11

0-76

99-11

1-77

100(s)

100时得到的100*2个随机解中的最优解,78为经过M=10000代的遗传(交

叉变异选择)后得到的最终最优解。

明显地发现: M 的增大所产生的优化效果明显好于N增大产生的优化效果

M 从1-10-100-1000-10000的变化使最优解有从9*--8*--7* 的变化规律，

N 的1-10-100的变化则不明显。

因此相对于随机取解, 经过遗传算法优化之后效果是显著的。

第

一

次

第

二

次

第

三

次

第

四

次

第

五

次

均

值

平均

时间

N=1000 ,M=0 78 79 81 80 79 79．4 25(S)

N=1,N=1,M=1000 80 75 77 76 82 78.0 8.5(S)

由上表看来,虽然在均值方面相差不显著,但是时间上采用遗传算法之后节约了约三分之二的运行时间,效率显而易见。

九．模型优缺点及改进

模型优点，采用遗传算法可对一个理论上无法求尽的NP问题以较有效方法在较短时间内得到较精确解。

缺点，采用遗传算法还不全面，只是一个简单模型，未考虑收敛性,适配值等，对参数设置与最优解关系研究还不够深入。

模型本身还具有漏动，仍需改进，较好设想为采用和模拟退火算法的混合遗传算法，由于时间紧迫，在此就不再深入给出模型及分析了。

[参考文献]：

1．车间调度与遗传算法王凌清华大学出版社

2．数值计算的算法与分析张可村赵英良科学出版社3．Permutation Based GAs and Ordered Greed Peter G. Anderson, 4．MATLAB6.0 与科学计算王沫然电子工业出版社

5．C程序设计（第二版）潭浩强清华大学出版社

信息014 孙卓明

2003年8月14日

本文网上下载地址(个人主页): https://www.wendangku.net/doc/ab1009481.html,

附录：

子程序一：(种群初始化，得较优个体) function

[minminmax,ss]=chushijie(n)

% 种群初始化,以下为编码和解码过程，同时

对n次选取最优化个体

Jm=[3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ];

minminmax=200;

for d=1:n;

s=0; % 编码程序：基于操作的编码策略

k=1;

for t=1:35 ; I=randint(1,1,[1,6]); while Jm(I,1)==0;

I=randint(1,1,[1,6]); end; s(k)=I; k=k+1; x=1; while x<=7;

Jm(I,x)=Jm(I,x+1); x=x+1; end; Jm(I,8)=0; end;

Jm=[3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ];

T=[8 2 4 24 6 0 0 0;4 5 3 4 0 0 0 0;3 7 15 20 8 0 0 0;7 6 21 1 16 3 0 0;10 4 8 4 12 6 1 0;1 4 7

]; % 解码程序：活动化解码算法

for i=1:6; k(i)=1; end ; for q=1:4; for x=1:9;

a(q,x)=0;b(q,x)=0;flag_(q)=0; end; end; for p=1:6; flag(p)=0; end; for i=1:35;

q=Jm(s(i),k(s(i))); t=T(s(i),k(s(i))); z=0; v=0; for x=1:9; if

max(flag(s(i)),a(q,x))+t<=b(q,x)&&z==0 ; if

flag(s(i))<=a(q,x)&&a(q,x)+t==b(q,x); flag(s(i))=b(q,x); for y=x:8; a(q,y)=a(q,y+1);b(q,y)=b(q,y+1);

end; z=1 ;

elseif flag(s(i))<=a(q,x)&&a(q,x)+t

a(q,x)=a(q,x)+t;flag(s(i))=a(q,x);z=1 ;

elseif

flag(s(i))>a(q,x)&&a(q,x)+t==b(q,x) ;

flag(s(i))=b(q,x);b(q,x)=b(q,x)-t;z=1;

elseif

flag(s(i))>a(q,x)&&a(q,x)+t

a(q,y)=a(q,y-1);b(q,y)=b(q,y-1); end;

b(q,x+1)=b(q,x);b(q,x)=flag(s(i));a(q,x+1)=flag(s(i))+t; flag(s(i))=a(q,x+1);z=1; end; end; end; if z==0;

if flag(s(i))<=flag_(q); flag(s(i))=flag_(q)+t; flag_(q)=flag_(q)+t; elseif flag(s(i))>flag_(q);

for x=1:9;

if a(q,x)==0&&v==0;

a(q,x)=flag_(q);b(q,x)=flag(s(i));v=1; end;

end;flag(s(i))=flag(s(i))+t; flag_(q)=flag(s(i)); end; end;

k(s(i))=k(s(i))+1; end; minmax=0; for q=1:4;

if minmax

minminmax>minmax ; % 得出初始最优解 minminmax=minmax ;ss=s ;

end ; end;

子程序二：（父代交叉变换）

function [D]=jiaocha(f1,f2) % 交叉变化（循环交叉操作，CX）,选取“染色体”无需变动部分基因

s=randint(1,1,[1,35]);

while f1(s)==f2(s);

s=randint(1,1,[1,35]);

end;

for p=1:34;

D(p)=0;

end;

z=0;j=1;D(j)=s;j=j+1;

for i=1:35;

if f1(i)==f2(s)&&z==0 ;

D(j)=i;j=j+1;z=1;

end;

if f2(D(j-1))==f1(s);

return;

end;

for m=1:34;

z=0;

for i=1:35;

if f1(i)==f2(D(j-1)) && z==0 ;

w=0; for t=3:j;

if (i-D(t-1))>0||(i-D(t-1))<0;

w=w+1; end;

end;

if w==j-2;

D(j)=i; j=j+1;z=1;

end ;

end;

if f2(D(j-1))==f1(s)&&z==1;

return;

end;

end; 子程序三：（变异选择，形成子代）function

[f3,f4]=jiaocha_bianyi(f1,f2,D) % 生成交叉后的“染色体”,并进行变异选择

g2=f1;g1=f2;

for i=1:34;

if D(i)>0;

g1(D(i))=f1(D(i));g2(D(i))=f2(D(i));

end;

f3=g1;f4=g2;

c=randint(1,1,[1,100]);

if c==1 ;

d1=randint(1,1,[1,35]);

d2=randint(1,1,[1,35]);

while d1==d2;

d2=randint(1,1,[1,35]);

end;

m=f3(d1);f3(d1)=f3(d2);f3(d2)=m;

elseif c==2;

d1=randint(1,1,[1,35]);

d2=randint(1,1,[1,35]);

while d1==d2;

d2=randint(1,1,[1,35]);

end; m=f4(d1);f4(d1)=f4(d2);f4(d2)=m; end;

子程序四：（四者中选取最优二个体）function

[f1,f2]=xuanze(f1,f2,f3,f4) % 对父代f1,f2和子代f3,f4进行解码，得出2个较

优个体，成为下一代的父代

min1=0;min2=0;min3=0;min4=0;h=0;g=0;

[min1]=tongbujinzhan(f1);

[min2]=tongbujinzhan(f2);

[min3]=tongbujinzhan(f3);

[min4]=tongbujinzhan(f4);

if min1<=min2&&min1<=min3&&min1<=min4 ;

h=f1 ; if min2<=min3&&min2<=min4; g=f2;

elseif min3<=min2&&min3<=min4; g=f3;

elseif min4<=min2&&min4<=min3; g=f4;

end;

elseif

min2<=min1&&min2<=min3&&min2<=min4 ; h=f2; if min1<=min3&&min1<=min4 ; g=f1; elseif min3<=min1&&min3<=min4 ; g=f3; elseif min4<=min1&&min4<=min3 ; g=f4; end; elseif

min3<=min1&&min3<=min2&&min3<=min4 ; h=f3; if min1<=min2&&min1<=min4 ; g=f1; elseif min2<=min1&&min2<=min4 ; g=f2; elseif min4<=min1&&min4<=min2 ; g=f4; end; elseif

min4<=min1&&min4<=min2&&min4<=min3 ; h=f4; if min1<=min2&&min1<=min3 ; g=f1; elseif min2<=min1&&min2<=min3 ; g=f2; elseif min3<=min1&&min3<=min2 ; g=f3; end; end; end; f1=h;f2=g; while f1==f2;

[minminmax3,s1]=chushijie(30); f2=s1; end;

子程序五：（循环之中，同步求解）

function

[minmaxf1,a1,b1]=tongbujinzhan(f1) % 求该时刻个体f1的最优时间 Jm=[3 1 2 3 4 0 0 0 ;1 4 2 3 0 0 0 0 ;3 4 1 2 1 0 0 0 ;2 3 4 1 4 3 0 0 ;4 2 3 4 1 3 4 0 ;1 2 1 3 4 1 3 1 ];

T=[8 2 4 24 6 0 0 0;4 5 3 4 0 0 0 0;3 7 15 20 8 0 0 0;7 6 21 1 16 3 0 0;10 4 8 4 12 6 1 0;1 4 7 3 5 2 5 8 ]; s=f1

; % 解码程序：活动化解码算法

for i=1:6; k(i)=1; end ;

for q=1:4; for x=1:9;

a(q,x)=0;b(q,x)=0;flag_(q)=0; end; end; for p=1:6; flag(p)=0; end; for i=1:35;

q=Jm(s(i),k(s(i))); t=T(s(i),k(s(i))); z=0; v=0; for x=1:9; if

max(flag(s(i)),a(q,x))+t<=b(q,x)&&z==0 ; if

flag(s(i))<=a(q,x)&&a(q,x)+t==b(q,x);

flag(s(i))=b(q,x); for y=x:8; a(q,y)=a(q,y+1);b(q,y)=b(q,y+1); end; z=1 ; elseif

flag(s(i))<=a(q,x)&&a(q,x)+t

flag(s(i))>a(q,x)&&a(q,x)+t==b(q,x) ;

flag(s(i))=b(q,x);b(q,x)=b(q,x)-t;z=1 ;

elseif

flag(s(i))>a(q,x)&&a(q,x)+t

a(q,y)=a(q,y-1);b(q,y)=b(q,y-1); end;

b(q,x+1)=b(q,x);b(q,x)=flag(s(i));a(q,x+1)=flag(s(i))+t; flag(s(i))=a(q,x+1);z=1; end; end; end; if z==0;

if flag(s(i))<=flag_(q); flag(s(i))=flag_(q)+t; flag_(q)=flag_(q)+t;

elseif flag(s(i))>flag_(q);

for x=1:9; if a(q,x)==0&&v==0;

a(q,x)=flag_(q);b(q,x)=flag(s(i));v=1;

end;

end;flag(s(i))=flag(s(i))+t;flag_(q)=flag(s (i));

end;

k(s(i))=k(s(i))+1;

end;

minmaxf1=0;

for q=1:4;

if minmaxf1

minmaxf1=flag_(q);

end;

a1=a; b1=b;

遗传算法优化相关MATLAB算法实现

遗传算法 1、案例背景遗传算法（Genetic Algorithm，GA）是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。在遗传算法中，染色体对应的是数据或数组，通常是由一维的串结构数据来表示，串上各个位置对应基因的取值。基因组成的串就是染色体，或者叫基因型个体( Individuals) 。一定数量的个体组成了群体（Population)。群体中个体的数目称为群体大小（Population Size），也叫群体规模。而各个个体对环境的适应程度叫做适应度( Fitness) 。 2、遗传算法中常用函数 1)创建种群函数—crtbp 2)适应度计算函数—ranking 3)选择函数—select 4)交叉算子函数—recombin 5)变异算子函数—mut 6)选择函数—reins 7)实用函数—bs2rv 8)实用函数—rep 3、主程序： 1. 简单一元函数优化： clc clear all close all %% 画出函数图 figure(1); hold on; lb=1;ub=2; %函数自变量范围【1,2】 ezplot('sin(10*pi*X)/X',[lb,ub]); %画出函数曲线 xlabel('自变量/X') ylabel('函数值/Y') %% 定义遗传算法参数 NIND=40; %个体数目 MAXGEN=20; %最大遗传代数 PRECI=20; %变量的二进制位数 GGAP=0.95; %代沟 px=0.7; %交叉概率 pm=0.01; %变异概率

最优化算法-Matlab程序

CG程序代码 function [x,y] = cg(A,b,x0) %%%%%%%%%%%%%%%%%CG算法%%%%%%%%%%%% r0 = A*x0-b; p0 = -r0; k = 0; r = r0; p = p0; x = x0; while r~=0 alpha = -r'*p/(p'*A*p); x = x+alpha*p; rold = r; r = rold+alpha*A*p; beta = r'*r/(rold'*rold); p = -r+beta*p; plot(k,norm(p),'.--'); hold on k = k+1; end y.funcount = k; y.fval = x'*A*x/2-b'*x;

function [x,y] = cg_FR(fun,dfun,x0) %%%%%%%%%%%%%%%CG_FR算法%%%%%%%%%%%%%%% error = 10^-5; f0 = feval(fun,x0); df0 = feval(dfun,x0); p0 = -df0; f = f0; df = df0; p = p0; x = x0; k = 0; while ((norm(df)>error)&&(k<1000)) f = feval(fun,x); [alpha,funcNk,exitflag] = lines(fun,0.01,0.15,0.85,6,f,df'*p,x,p);%%用线搜索找下降距离%% if exitflag == -1 disp('Break!!!'); break; end x = x+alpha*p; dfold = df; df = feval(dfun,x); beta = df'*df/(dfold'*dfold); p = -df+beta*p; plot(k,norm(df),'.--'); hold on k = k+1; end y.funcount = k; y.fval = feval(fun,x); y.error = norm(df);

最优化方法的Matlab实现(公式(完整版))

第九章最优化方法的MatIab实现在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 9.1 概述利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。 9.1.1优化工具箱中的函数优化工具箱中的函数包括下面几类： 1 ?最小化函数

2.方程求解函数 3.最小—乘（曲线拟合）函数

4?实用函数 5 ?大型方法的演示函数 6.中型方法的演示函数 9.1.3参数设置利用OPtimSet函数，可以创建和编辑参数结构；利用OPtimget函数，可以获得o PtiOns优化参数。 ? OPtimget 函数功能：获得OPtiOns优化参数。语法：

最优化算法实验报告(附Matlab程序)

最优化方法(Matlab)实验报告 ——Fibonacci 法一、实验目的：用MATLAB 程序实现一维搜索中用Fibonacc 法求解一元单峰函数的极小值问题。二、实验原理：（一）、构造Fibonacci 数列：设数列{}k F ，满足条件： 1、011F F == 2、11 k k k F F F +-=+则称数列{}k F 为Fibonacci 数列。（二）、迭代过程：首先由下面的迭代公式确定出迭代点： 1 1 1 (),1,...,1(),1,...,1n k k k k k n k n k k k k k n k F a b a k n F F u a b a k n F λ---+--+=+ -=-=+ -=-易验证，用上述迭代公式进行迭代时，第k 次迭代的区间长度缩短比率恰好为 1 n k n k F F --+。故可设迭代次数为n ，因此有11121211221111223231 ()()......()()n n n n n n n n n F F F F F F b a b a b a b a b a F F F F F F F ------= -=?-==?-=-若设精度为L ，则有第n 次迭代得区间长度111 ()n n n b a L b a L F -≤-≤，即就是 111 ()n b a L F -≤，由此便可确定出迭代次数n 。

假设第k 次迭代时已确定出区间[,]k k a b 以及试探点,[,]k k k k u a b λ∈并且k k u λ<。计算试探点处的函数值，有以下两种可能：（1）若()()k k f f u λ>，则令 111111111,,()() () k k k k k k k k n k k k k k n k a b b f f F a b a F λλμλμμ++++--++++-=====+-计算1()k f μ+的值。（2）()()k k f f u λ≤，则令 111121111,,()() () k k k k k k k k n k k k k k n k a a b f f F a b a F μμλμλλ++++--++++-=====+-计算1()k f λ+的值。又因为第一次迭代确定出了两个迭代点，以后每迭代一次，新增加一个迭代点，这样在迭代n-1后便计算完了n 个迭代点。因此第n 次迭代中，选用第n-1次的迭代点以及辨别常数δ构造n λ和n μ： 1 1n n n n λλμλδ --==+再用同样的方法进行判断：（1）、若()n f λ>()n f μ则令 1 n n n n a b b λ-==（2）、若()n f λ<=()n f μ则令 1n n n n a a b μ-==这样便可确定出最优解的存在区间[,]n n a b 。

优化方法MATLAB编程——大连理工大学

优化方法上机大作业学院：姓名：学号：指导老师：肖现涛

第一题源程序如下： function zy_x = di1ti(x) %di1ti是用来求解优化作业第一题的函数。 x0=x; yimuxulong=0.000001; g0=g(x0);s0=-g0; A=2*ones(100,100); k=0; while k<100 lanmed=-(g0)'*s0/(s0'*A*s0); x=x0+lanmed*s0; g=g(x); k=k+1; if norm(g)

break; end miu=norm(g)^2/norm(g0)^2; s=-g+miu*s0; g0=g; s0=s;x0=x; end function f=f(x) f=(x'*ones(100,1))^2-x'*ones(100,1); function g=g(x) g=(2*x'*ones(100,1))*ones(100,1)-ones(100,1); 代入x0,运行结果如下： >> x=zeros(100,1); >> di1ti(x) After 1 iterations,obtain the optimal solution. The optimal solution is -0.250000. The optimal "x" is "ans". ans =0.005*ones(100,1).

最优化方法及其Matlab程序设计

最优化方法及其Matlab程序设计 1.最优化方法概述在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证，从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。最优化是每个人，每个单位所希望实现的事情。对于产品设计者来说，是考虑如何用最少的材料，最大的性能价格比，设计出满足市场需要的产品。对于企业的管理者来说，则是如何合理、充分使用现有的设备，减少库存，降低能耗，降低成本，以实现企业的最大利润。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容： 1）建立数学模型。即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解。数学模型建好以后，选择合理的最优化算法进行求解。最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 2.最优化方法（算法）浅析最优化方法求解很大程度上依赖于最优化算法的选择。这里，对最优化算法做一个简单的分类，并对一些比较常用的典型算法进行解析，旨在加深对一些最优化算法的理解。最优化算法的分类方法很多，根据不同的分类依据可以得到不同的结果，这里根据优化算法对计算机技术的依赖程度，可以将最优化算法进行一个系统分类：线性规划与整数规划；非线性规划；智能优化方法；变分法与动态规划。 2.1 线性规划与整数规划线性规划在工业、农业、商业、交通运输、军事和科研的各个研究领域有广泛应用。例如，在资源有限的情况下，如何合理使用人力、物力和资金等资源，以获取最大效益；如何组织生产、合理安排工艺流程或调制产品成分等，使所消耗的资源（人力、设备台时、资金、原始材料等）为最少等。线性规划方法有单纯形方法、大M法、两阶段法等。整数规划有割平面法、分枝定界法等。 2.2 非线性规划 20世纪中期，随着计算机技术的发展，出现了许多有效的算法——如一些非线性规划算法。非线性规划广泛用于机械设计、工程管理、经济生产、科学研究和军事等方面。

最优化方法matlab作业

实用最优化方法 ——matlab编程作业

题一、初值为[-1;1] 其中g0、g1分别为不同x值下得导数，f0、f1为函数值 MATLAB程序： x0=[-1;1]; s0=[1;1]; c1=0.1;c2=0.5;a=0;b=inf;d=1;n=0; x1=x0+d*s0; g0=[-400*(x0(2)-x0(1)^2)*x0(1)-2*(1-x0(1));200*(x0(2)-x0(1) ^2)]; g1=[-400*(x1(2)-x1(1)^2)*x1(1)-2*(1-x1(1));200*(x1(2)-x1(1) ^2)]; f1=100*(x1(2)-x1(1)^2)^2+(1-x1(1))^2; f0=100*(x0(2)-x0(1)^2)^2+(1-x0(1))^2; while((f0-f1<-c1*d*g0'*s0)||(g1'*s0

最优化方法的Matlab实现(公式完整版)

第九章最优化方法的Matlab实现在生活和工作中，人们对于同一个问题往往会提出多个解决方案，并通过各方面的论证从中提取最佳方案。最优化方法就是专门研究如何从多个方案中科学合理地提取出最佳方案的科学。由于优化问题无所不在，目前最优化方法的应用和研究已经深入到了生产和科研的各个领域，如土木工程、机械工程、化学工程、运输调度、生产控制、经济规划、经济管理等，并取得了显著的经济效益和社会效益。用最优化方法解决最优化问题的技术称为最优化技术，它包含两个方面的内容：1）建立数学模型即用数学语言来描述最优化问题。模型中的数学关系式反映了最优化问题所要达到的目标和各种约束条件。 2）数学求解数学模型建好以后，选择合理的最优化方法进行求解。最优化方法的发展很快，现在已经包含有多个分支，如线性规划、整数规划、非线性规划、动态规划、多目标规划等。 9.1 概述利用Matlab的优化工具箱，可以求解线性规划、非线性规划和多目标规划问题。具体而言，包括线性、非线性最小化，最大最小化，二次规划，半无限问题，线性、非线性方程（组）的求解，线性、非线性的最小二乘问题。另外，该工具箱还提供了线性、

非线性最小化，方程求解，曲线拟合，二次规划等问题中大型课题的求解方法，为优化方法在工程中的实际应用提供了更方便快捷的途径。 9.1.1 优化工具箱中的函数优化工具箱中的函数包括下面几类： 1．最小化函数表9-1 最小化函数表 2．方程求解函数表9-2 方程求解函数表

3．最小二乘（曲线拟合）函数表9-3 最小二乘函数表 4．实用函数表9-4 实用函数表 5．大型方法的演示函数表9-5 大型方法的演示函数表

优化算法的MATLAB实现技巧(单)

天津财经大学本科毕业论文中文题目：优化算法的MATLAB实现技巧英文题目：院系名称：专业班级：学号：姓名：指导教师： 20XX年 x月 x 日

内容摘要

目录第1章引言............................... 错误！未定义书签。 1.1 现代优化计算方法................. 错误！未定义书签。 1.2 MATLAB概述....................... 错误！未定义书签。 1.3 旅行商问题....................... 错误！未定义书签。第2章禁忌搜索算法的基本思想............. 错误！未定义书签。 2.1 相关概念介绍..................... 错误！未定义书签。 2.2 局部搜索算法..................... 错误！未定义书签。 2.3 禁忌搜索算法..................... 错误！未定义书签。第3章 MATLAB实现TSP问题的实现技巧....... 错误！未定义书签。 3.1 重要概念的定义................... 错误！未定义书签。 3.2 算法中的方法选择问题............. 错误！未定义书签。 3.3 MATLAB实现技巧................... 错误！未定义书签。第4章结果分析........................... 错误！未定义书签。 4.1 ................................. 错误！未定义书签。 4.2 ............................... 错误！未定义书签。五、总结与展望........................... 错误！未定义书签。 5.1 总结............................. 错误！未定义书签。 5.2 前景展望......................... 错误！未定义书签。

多目标优化实例和matlab程序

NSGA-II 算法实例目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。一、数值例子多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1．适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2．调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',,'populationsize',100,'ge nerations',200,'stallGenLimit',200,'TolFun',1e-100,'PlotFc ns',@gaplotpareto); % 最优个体系数paretoFraction 为；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200，适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,option

matlab生产调度问题及其优化算法

生产调度问题及其优化算法（采用遗传算法与MATLAB编程）信息014 孙卓明二零零三年八月十四日

生产调度问题及其优化算法背景及摘要这是一个典型的Job-Shop动态排序问题。目前调度问题的理论研究成果主要集中在以Job-Shop问题为代表的基于最小化完工时间的调度问题上。一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含M N)! (种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。本文给出三个模型。首先通过贪婪法手工求得本问题最优解，既而通过编解码程序随机模拟优化方案得出最优解。最后采用现代进化算法中有代表性发展优势的遗传算法。文章有针对性地选取遗传算法关键环节的适宜方法，采用MATLAB软件实现算法模拟，得出优化方案，并与计算机随机模拟结果加以比较显示出遗传算法之优化效果。对车间调度系列问题的有效解决具有一定参考和借鉴价值。一．问题重述某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工序产品 1 2 3 4 5 6 7 8 S T S T S T S T S T S T S T S T 1 C 8 A 2 B 4 C 24 D 6 2 A 4 D 5 B 3 C 4 3 C 3 D 7 A 15 B 20 A 8 4 B 7 C 6 D 21 A 1 D 16 C 3 5 D 10 B 4 C 8 D 4 A 12 C 6 D 1 6 A 1 B 4 A 7 C 3 D 5 A 2 C 5 A 8 条件：1、每件产品必须按规定的工序加工，不得颠倒； 2、每台设备在同一时间只能担任一项任务。（每件产品的每个工序为一个任务）

Matlab优化算法

Matlab优化主讲人：饶志欢现代优化算法什么是优化？就是从各种方案中选取一个最好的。从数学角度看，优化理论就是研究如何在状态空间中寻找到全局最优点。比如水泥混凝土的性能，涉及到水、沙、石子、水泥和其他掺杂物比例。学校课程表排课问题、售票员上岗问题、公司内部人员安排出效益等。降低成本、提高效益是问题的关键。

1.1 MATLAB解优化问题的主要函数 1.2 优化函数的输入变量

1.3 优化函数的输出变量下表 1.4 控制参数options的设置 (1)Display: 显示水平.取值为’off’时,不显示输出; 取值为’iter’时,显示每次迭代的信息;取值为’final’时,显示最终结果.默认值为 ’final’. (2)MaxFunEvals: 允许进行函数评价的最大次数,取值为正整数 . (3) MaxIter: 允许进行迭代的最大次数,取值为正整数控制参数options可以通过函数optimset创建或修改。命令的格式如下： (1) options=optimset(‘optimfun’) 创建一个含有所有参数名,并与优化函数optimfun相关的默认值的选项结构options.

1.4 控制参数options的设置 (2)options=optimset(‘param1’,value1,’param2’,value2,...) 创建一个名称为options的优化选项参数,其中指定的参数具有指定值,所有未指定的参数取默认值. (3)options=optimset(oldops,‘param1’,value1,’param2’, value2,...) 创建名称为oldops的参数的拷贝,用指定的参数值修改 oldops中相应的参数. 例：opts=optimset(‘Display’,’iter’,’TolFun’,1e-8) 该语句创建一个称为opts的优化选项结构,其中显示参数设为’iter’, TolFun参数设为1e-8. 2.1 一元函数无约束优化问题一元函数无约束优化问题常用格式如下：（1）x= fminbnd (fun,x1,x2) （2）x= fminbnd (fun,x1,x2，options) （3）[x，fval]= fminbnd（...）（4）[x，fval，exitflag]= fminbnd（...）（5）[x，fval，exitflag，output]= fminbnd（...）函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。

最优化各种方法MATLAB代码

最优化程序MATLAB 代码程序 1.目标任务分别用最速下降法、FR 共轭梯度法、DFP 法和BFGS 法求解无约束最值问题： 22 112212minf (x)x 2x x 4x x 3x =-++- 取初始点(1)T x (1,1)=和(2)T x (2,2)=，分别通过Matlab 编程实现求解过程。 2.程序实现（程序文件见附件） 2.1公用函数 1) function f= fun( X ) %所求问题目标函数 f=X(1)^2-2*X(1)*X(2)+4*X(2)^2+X(1)-3*X(2); end 2) function g= gfun( X ) %所求问题目标函数梯度 g=[2*X(1)-2*X(2)+1,-2*X(1)+8*X(2)-3]; end 3) function He = Hess( X ) %所求问题目标函数Hesse 矩阵 n=length(X); He=zeros(n,n); He=[2,-2; -2,4]; End 2.2其他函数

图2.2 函数程序文件图 1) 最速下降法的文件名为：grad.m 。 2) FR 共轭梯度法的文件名为：frcg.m 。 3) DFP 法的文件名为：dfp.m 。 4) BFGS 法的文件名为：bfgs.m 。 3.程序运行结果 3.1最速下降法 3.1.1 初值为(1)T x (1,1) 图3.1.1.1 最速下降法求解最小值输出结果图

图3.1.1.2最速下降法求解最小值过程图 3.1.2初值为(2)T x (2,2) 图3.1.2.1最速下降法求解最小值输出结果图

大连理工优化方法-增广拉格朗日方法MATLAB程序

上机大作业II 定义目标函数fun function f=fun(x) x1=x(1); x2=x(2); f=4*x1-x2^2-12; 定义目标函数梯度函数dfun function f=dfun(x) x2=x(2); f=[4;-2*x2]; 定义等式约束函数hf function qua=hf(x) qua=25-x(1)^2-x(2)^2; 定义等式约束函数梯度函数dhf function qua=dhf(x) qua=[-2*x(1);-2*x(2)]; 定义不等式约束函数gfun function inq=gfun(x) inq=10*x(1)-x(1)^2+10*x(2)-x(2)^2-34; 定义不等式约束梯度数dgf function inq=dgf(x) inq=[10-2*x(1);10-2*x(2)]; 定义增广拉格朗日函数mpsi function psi=mpsi(x,fun,hf,gfun,dfun,dhf,dgf,mu,lambda,sigma) f=feval(fun,x); he=feval(hf,x); gi=feval(gfun,x); l=length(he); m=length(gi); psi=f; s1=0; for i=1:l psi=psi-he(i)*mu(i); s1=s1+he(i)^2; end

psi=psi+0.5*sigma*s1; s2=0.0; for i=1:m s3=max(0.0, lambda(i) - sigma*gi(i)); s2=s2+s3^2-lambda(i)^2; end psi=psi+s2/(2.0*sigma); 定义增广拉格朗日函数梯度函数dmpsi function dpsi=dmpsi(x,fun,hf,gfun,dfun,dhf,dgf,mu,lambda,sigma) dpsi=feval(dfun,x); he=feval(hf,x); gi=feval(gfun,x); dhe=feval(dhf,x); dgi=feval(dgf,x); l=length(he); m=length(gi); for i=1:l dpsi=dpsi+(sigma*he(i)-mu(i))*dhe(:,i); end for i=1:m dpsi=dpsi+(sigma*gi(i)-lambda(i))*dgi(:,i); end 定义BFGS法函数函数bfgs function [x,val,k]=bfgs(mpsi,dmpsi,x0,fun,hf,gfun,dfun,dhf,dgf,mu,lambda,sigma) maxk=1000; rho=0.5; sigma1=0.4; epsilon1=1e-4; k=0; n=length(x0); Bk=eye(n); while(k

数学建模 MATLAB简介第六部分 MATLAB优化算法

第六部分MATLAB优化算法一、线性规划算法调用格式：[x, fval, exitflag]= linprog(f,A,b, Aeq,beq,lb,ub, x0) 说明：返回值x为最优解向量，fval为最优值；若没有不等式约束，则令A=[ ]、b=[ ] ；lb ,ub 为变量x的下界和上界，x0为初值点；exitflag 描述函数计算的退出条件：若为正值，表示目标函数收敛于解x处；若为负值，表示目标函数不收敛；若为零值，表示已经达到函数评价或迭代的最大次数。例1、求解线性规划问题 max f=70x1+120x2 s.t 9x1+4x2≤3600 4x1+5x2≤2000 3x1+10x2≤3000 x1,x2≥0 将其转换为标准形式： min f=-70x1-120x2 s.t 9x1+4x2≤3600 4x1+5x2≤2000 3x1+10x2≤3000 x1,x2≥0 算法如下：f=[-70 -120]; A=[9 4 ;4 5;3 10 ]; b=[3600;2000;3000]; lb=[0 0]; ub=[]; [x,fval,exitflag]=linprog(f,A,b,[],[],lb,ub)

maxf=-fval 例2、求解线性规划问题 max f=0.15x1+0.1x2+0.08 x3+0.12 x4 s.t x1-x2- x3- x4≤0 x2+ x3- x4≥0 x1+x2+x3+ x4=1 x j≥0 ， j=1,2,3,4 将其转换为标准形式： min z=-0.15x1-0.1x2-0.08 x3-0.12 x4 s.t x1-x2- x3- x4≤0 -x2- x3+ x4≤0 x1+x2+x3+ x4=1 x j≥0 ， j=1,2,3,4 算法如下：f = [-0.15;-0.1;-0.08;-0.12]; A = [1 -1 -1 -1；0 -1 -1 1]; b = [0; 0]; Aeq=[1 1 1 1]; beq=[1]; lb = zeros(4,1); [x,fval,exitflag] = linprog(f,A,b,Aeq,beq,lb) f=-fval 二、二次规划算法调用格式：[x,fval,exitflag]= quadprog(H,f,A,b,Aeq,beq,lb,ub,x0) 说明：输入参数中，x0为初始点；若无等式约束或无不等式约束，就将相应的矩阵和向量设置为空。输出参数中，x是返回最优解；fval是返回解所对应的目标函数值；exitflag是描述搜索是否收敛。例3、求解二次规划问题 min f(x)= x1-3x2+3x12+4x22-2x1x2 s.t 2x+x≤2

最优化算法实验报告(附Matlab程序)

最优化方法(Matlab)实验报告 —— Fibonacci 法一、实验目的：用MA TLAB 程序实现一维搜索中用Fibonacc 法求解一元单峰函数的极小值问题。二、实验原理：（一）、构造Fibonacci 数列：设数列{}k F ，满足条件： 1、0 11F F == 2、11k k k F F F +-=+ 则称数列{}k F 为Fibonacci 数列。（二）、迭代过程：首先由下面的迭代公式确定出迭代点： 111 (),1,...,1 (),1,...,1 n k k k k k n k n k k k k k n k F a b a k n F F u a b a k n F λ---+--+=+ -=-=+ -=- 易验证，用上述迭代公式进行迭代时，第k 次迭代的区间长度缩短比率恰好为 1 n k n k F F --+。故可设迭代次数为n ，因此有 111212112211112 2 3 2 3 1()()...... ()() n n n n n n n n n F F F F F F b a b a b a b a b a F F F F F F F ------=-= ? -== ?-=- 若设精度为L ，则有第n 次迭代得区间长度 111()n n n b a L b a L F -≤-≤ ，即就是 111()n b a L F -≤，由此便可确定出迭代次数n 。

假设第k 次迭代时已确定出区间 [,]k k a b 以及试探点,[,]k k k k u a b λ∈并且k k u λ<。计算试探点处的函数值，有以下两种可能：（1）若()() k k f f u λ> ，则令 111111111,,()()() k k k k k k k k n k k k k k n k a b b f f F a b a F λλμλμμ++++--++++-=====+ - 计算 1()k f μ+的值。（2）()()k k f f u λ≤ ，则令 111121111,,()()() k k k k k k k k n k k k k k n k a a b f f F a b a F μμλμλλ++++--++++-=====+ - 计算1()k f λ+ 的值。又因为第一次迭代确定出了两个迭代点，以后每迭代一次，新增加一个迭代点，这样在迭代n-1后便计算完了n 个迭代点。因此第n 次迭代中，选用第n-1次的迭代点以及辨别常数δ构造n λ和n μ： 11n n n n λλμλδ --==+ 再用同样的方法进行判断：（1）、若 ()n f λ>()n f μ则令 1 n n n n a b b λ-== （2）、若 ()n f λ<=()n f μ则令 1n n n n a a b μ-== 这样便可确定出最优解的存在区间[,]n n a b 。

实用最优化方法Matlab程序设计

程序如下： function lambda=nonexact(x0,s0) g0=grad(x0); f0=f(x0); a=0; c1=0.1; c2=0.5; lambdak=1; sk=s0; d=-c1*lambdak*g0'*sk; xk=x0+lambdak*sk; f1=f(xk); e=f0-f1; while d>e lambdak=(lambdak+a)/2; xk=x0+lambdak*sk; fk=f(xk); e=f0-fk; d=-c1*lambdak*g0'*sk; end lambdak function g=grad(x) g=zeros(2,1); g(1)=-4*x(1)*(x(2)-x(1)^2)-2*(1-x(1)); g(2)=2*(x(2)-x(1)^2); function fa=f(x) fa=(x(2)-x(1)^2)^2+(1-x(1))^2; 在命令窗口中输入x0=[0;1];s0=[-1;1];nonexact(x0,s0)输出结果为：

程序如下： function x_star=cong(x0,eps) g0=grad(x0); res0=norm(g0); resk=res0; k=0; xk=x0; while resk>eps k=k+1; if k==1 sk=-grad(xk); else sk=-grad(xk)+resk^2/res0^2*s0; end lambdak=step(xk,sk); x0=xk; xk=x0+lambdak*sk; res0=resk; resk=norm(grad(xk)); s0=sk; fprintf('------the%d-th iteration,the residual is%f,the lambdak is%f\n\n', k,resk,lambdak); end x_star=xk; disp('the optimal solution is'); x_star

现代优化方法与MATLAB实现

例8.2 第1种方法：首先建立适应度函数FitFun.m文件 function y=FitFun(x) y=x(1)^2+2*x(2)^2-4*x(1)-8*x(2)+15; 建立约束函数文件NonCon.m function[c,ceq]=NonCon(x) c=x(1)^2+x(2)^2-9; ceq=[]; 第2种方法：利用第1种方法中适应函数FitFun.m和约束函数NonCon.m，编写m文件调用ga函数进行求解。 objectivef=@FitFun; nvars=2; lb=[0 0]; ub=[]; constrainf=@NonCon; [x,fval]=ga(objectivef,nvars,[],[],[],[],lb,[],constrainf) 上述m文件运行结果如下 X=2.0000 2.0000 fval=3.0000 可见与第1种算法相同。 ============================================================== 例8-3 第1种方法：首先建立目标函数simple.m文件 function y=simple(x) y=(4-2.1*x(1)^2+x(1)^4/3)*x(1)^2+x(1)*x(2)+(-4+4*x(2)^2)*x(2)^2; Simulannea 第2种方法：利用第1种方法中目标函数simple.m，编写m文件调用lbnd 函数进行求解。 objectivef=@simple x0=[0.5 0.5]; lb=[-64 -64]; ub=[64 64]; [x fval]=simulannealbnd(objectivef,x0,lb,ub) 上述m文件运行结果如下 X=-0.0896 0.7127 fval=-1.0316 可见与第1种算法相同。