Matlab在优化问题上的应用

毕业论文 论文题目MATLAB在优化问题上的应用 学 院 专 业数学与应用数学（金融数学） 年 级 学 号 学生姓名 指导教师 完成时间 2014 年 4 月 肇庆学院教务处制 Mat I ab在优化问题上的应用 陈志杰 摘要 本文通过探究一般求解优化问题的方法的算法步骤，编写出Matlab程序，并通 过算例，验证程序的正确性. 关键词最优化；线性规划；非线性规划；黄金分割法；牛顿法；急速下降法；惩罚函 数法 1引言 最优化是一门新的学科，它按照特定目标，在一定的限制条件下，以科学、技术 和实践经验的综合成果为基础，对标准系统的构成因素及其关系进行选择、设计或调 整，最后在众多可行方案中选择最合理的一种以达到最优目标，它广泛应用于工业、 商业、农业、军事、交通运输、政府部门和其他方面.例如，在资源分配中，怎样分配 有限资源，才能使资源利用率达到最小化的同时，经济效益又能达到最大化；在城建 规划中，怎样对工厂、学校、医院、商店、住户和其他单位，进行安排布局，才能方 便群众，又有利于各行各业的发展.最优化技术，它包含两方面的内容，一方面是建 立数学模型，即用数学关系式反映最优化问题所要达到的目标和各种约束；另一方面 是数学求解，即数学模型建立完毕后，选择合理的最优化方法对模型进行求解.优化 问题的数学模型一般表示为 min /x s.t. g, x0, z 1,2,,771. 1 /x 0,顶 式中XG 7 ,/xg R , x称为决策变量，fx称为目标函数，gjx V0z l,2,...,p为 不等式约束，为x 0/ l,2,...,q为等式约束，两者统称为约束条件.如果x*是使 fx在约束条件下取得最大值的点，显然三是-/W在同样约束条件下取得最小值的 点，因此为论述的方便，本文只讨论最小值问题. 根据变量、目标函数和约束函数的不同，可对优化问题进行分类 1 根据是否有约束条件，可分为无约束最优化问题和约束最优化问题； 2 根据目标函数和约束函数的类型，可分为线性规划、二次规划和非线性规划等. 不同类型的规划，有不同的算法，例如解线性规划最常用的是单纯型方法和对偶 单纯形表法，求解整数规划有Gomory割平面法和分支定界法，解一维无约束优化问题 有0. 618法和Newton法，解非线性规划的方法有最速下降和共轲方向法等. Matlab I具箱给我们解优化问题带来了很大的帮助，提供了一些函数，用户可以 直接调用.为此，本文对各种类型的优化问题的算法进行了总结，并用matlab编程实 现. 2线性规划 线性规划⑵指目标函数和约束函数都是决策变量的线性函数的优化问题，常应用于 如何在有限的资源条件下完成最多的任务，或者如何统筹任务以使用最少的资源.一 般可以表示为 min yx qx|... €■,冉 由.a*0.2土 /,, 々，i l,2-・，p2] aiXxx ai2x2 〃％2 々，i p 1,p 2,・・，m lbi Xj ubj1 1,2,,〃 记 x x|,x2---,x„r,, an airl Aeq 「., beq b[,b2,,bp, _ap\ ap2 apn_ p1,1 p1,2 J，apl,n Ab b* ci i tz o , a _ mlmlmn _ 活仍1，仍2,，也，ub 也,ub2, , ubT , 则式2. 1可以写成如下矩阵表示形式 min fTc s.t. Aeq - x - beq,. 2. 2 Axb lbxub 2. 1求解线性规划 在Matlab中，可调用linprog函数包求解线性规划问题，其格式为 [x,fval, exitflag]linprogf,A,b,Aeq,beq,lb,ub,xO,options 1 linprog为函数名，x是最优解，fval是目标函数在最优解x处的最优值，exitflag 表示所得x是否为最优解若exitflag0,则x为最优解;否则，x不是最优解，它 只是迭代终止时优化过程的值，一般可以省略不写. 2 函数中的输入参数f、A、b、Aeq、beq、lb、ub同式2.2相同. 若没有不等式约束，则A和b为口；若没有等式约束，则Aeq和beq为口. 当x无下界时，lb为口；当x无上界时，ub为口. 3 xO是初始迭代值，适用于除fminbnd以外的函数，也可以省略. 4 options是控制输出格式的参数，取值可以参考其它文献龙 例1某企业生产桌子和椅子，每张单品的制作和装配所需时间如表1所示.试问 何种组合的产品使利润最大 表1某企业生产资料 桌子 椅子 工序可利用时间 在制作工序上的时间（小时） 2 4 48 在装配工序上的时间（小时） 4 2 60 单位产品利润（元） 8 6 解设生产桌子和椅子的数量分别为叫和尤2,利润为y，建立模型 max y 8邑 6x2 s.t 2尤1 4x2 48 4尤] 2x2 60 0,x2 0 首先将最大值问题转化为最小值问题，即目标函数为miny -8吐- 6工2・在mat lab命 令窗口输入以下命令 f[-8;-6]; A[2,4；4,2]; b[48;60]; Aeq[]; beq[]; lb[0;0]; ub[]; [x,fval]linprog（f,A,b,Aeq,beq,lb,ub,[]） 输出结果得 Optimization terminated. x 12.0000 6.0000 fval -132.0000 因此，在规定时间内，该公司生产12张桌子和6张椅子，获取最大利润132元. 2. 2求解整数线性规划问题 整数规划⑵是线性规划的特殊形式，它是指决策变量全部或部分为整数的线性规 划，可用下列模型表示 min /（.X） cTX 睛（2.3） Aeq x beq lb xub x为整数 若要求决策变量全部为整数，则（2. 3）为纯整数线性规划问题；若要求决策变量部分 为整数，则（2.3）为混合整数线性规划问题.求解整数线性规划问题的方法主要有 Gomory割平面法和分支定界法. 2. 2. 1用分支定界法解整数线性规划问题 分支定界法是的基本思路是如果线性规划的最优解恰好是整数解，则这个解就 是整数规划的最优解.如果线性规划的最优解中至少有一个变量不是整数，那么就把 线性规划的可行域切割成两部分，分别求解两个线性规划的最优解.如果这两个线性 规划的最优解还不是整数解，分别把