最优化理论与方法

最优化理论与方法课件制作：北方民族大学高岳林任子晖目录•第一章概论•第二章线性规划•第三章无约束非线性规划•第四章约束非线性规划•第五章多目标规划•第六章整数规划•第七章动态规划第一章概论模型举例最优化问题的模型与分类第二章线性规划凸集与凸函数线性规划的几何特征线性规划的标准型线性规划的基本定理单纯型法大M法第三章无约束非线性规划最优性条件一维搜索最速下降法与共轭梯度法牛顿法与拟牛顿法第四章约束优化方法最优性条件二次规划可行方向法惩罚函数法复型法第五章多目标规划模型举例向量集的优化问题有效解和弱有效解评价函数法第六章整数规划整数规划问题的基本概念线性整数规划问题的分枝定界法0—1的隐枚举法第七节动态规划动态规划的基本概念动态规划的最优性与基本方程第一章概论随着生产、经济、技术的发展，工程技术、管理人员在实际工作中，肯定会面临这样的一类问题：工程设计中怎样选择参数，使得设计既满足要求，又能降低成本；资源分配中，怎样的分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产计划安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例才能提高质量、降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住宅和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域，诸如此类问题，不胜枚举。这一类问题的共同特点，就是要在所有可能的方案中，选出最合理的，达到事先规定的最优目标的方案，这个方案可称为最优方案，寻求最优方案的方法称为最优化方法，它是一门应用广泛、实用性强的学科。定义1：寻找最优方案的方法称为最优化方法。所谓的最优方案就是要在所有可能的方案中，选出最合理的，达到事先规定的最优目标的方案，最优化结合管理，经济等一些领域，而最根本的要以我们的数学知识为基础，现已被广泛地应用于工程，国防，管理和经济等许多重要的领域。1.1模型举例当我们要量化一个问题时，首先需要将此问题转化为一个数学问题，即建立数学模型。抓住其主要因素，理清其相互的联系，然后综合地运用有关学科的知识和数学知识才能完成。下面举几个例子。例1：配棉问题所谓的配棉问题就是要根据棉纱的质量指标，采用各种价格不同的棉花，按一定的比例配制成纱，使其即达到质量指标又使总成本最低。棉纱的质量指标一般有棉结和品质指标来决定，这两项指标都可以用数量形式来表示，一般来说，棉结粒越少越好，品质指标越大越好。个年纺能力为15000锭的小厂在采用最优化方法配棉时，某一产品32D纯棉纱的棉花配比质量指标及单价如下：原料品名单价（元/t）混合比（%）棉结（粒）品质指标混棉单价（元/t）国棉1318400256038002100国棉2297500356535002625国棉3276700408025002680平均合计1007031757405有关部门对32D纯棉纱规定的质量指标为棉结不多于70粒，品质指标不小于2900。下面我们建立数学模型：首先：根据问题需要设置变量：设分别为国棉131,229,327的棉花配比，然后用所设置的变量把所追求的目标及所受的约束，用数学语言表达出来，即得到该问题的数学模型。321,,xxx本例的目标是混棉单价最小，用即可表示为：本例关于32D纯棉纱的质量指标作为约束条件表出，即有：3216700750018400minxxxz321,,xxx290025003500380070806560321321xxxxxx又因为的实际意义，它们应为百分数且和为100%，故又有：321,,xxx0,,1321321xxxxxx故32D纯棉纱配棉问题的数学模型为：0,,1290025003500380070806560..6700750018400minz321321321321321xxxxxxxxxxxxtsxxx例2：资金使用问题设有400万元资金，要求4年内使用完，若在一年内使用资金万元，则可得到效益万元，（效率不能再次使用），当年使用的资金可存入银行，年利率为10%，试制定出资金的使用计划，以使4年资金效益之和最大。很明显，不同的使用方案，所取得的效益之和是不同的，如第一年就把400万元全部用完，则效益总和为20万元，若前三年均不使用而存入银行，则第四年把本息和400=532.4万元全部用完，则效益总和为万元，比第一种方案效益大3万多元。xx07.234.532第一年第二年第三年第四年现有资金400345.2265.1152.8使用资金86.2104.2126.2152.8效益总和为万元，使第一种效益总和的两倍多。注：此例反映出进行定量的优化计算作用，故一些工业人士称最优化方法是不需要增加投入而增加产出的手段。为了将上述的问题转化为最优化问题，先建立数学模型，设变量分别表示第年所使用的资金数，于是所追求的目标----4年的效益总和最大，即可表示为：1.438.1522.1262.1042.86)4,3,2,1(ixii4321maxxxxxz所受的约束为每年的使用金额既不能为负数又不能超过当年资金拥有数，即：第一年：第二年：第三年：第四年：40001x1.1)400(012xx1.1]1.1)400[(0213xxx1.1}1.1]1.1)400{[(03214xxxx故资金使用问题的数学模型为：0,,,4.5321.121.1331.14841.121.14401.1400.max432143213212114321xxxxxxxxxxxxxxtsxxxxz例3：汽轮机排序问题环形排序问题：由于考虑其共振的因素，一百多个叶片的质量及几何形状各不相同。转动时产生的惯性离心力也就存在差异，如何确定它们的安转位置（排列顺序），使诸离心力的合力最小。设有个叶片，第个叶片在转动时产生的惯性离心的数值（模）为，转子的一周被分为等份，安装位置用辐角表示，如将第个叶片安装在位置上，它产生的离心力（向量）可用复数表示：nj)1(njrjn)1(2nknkkjk)sin(cos),(kkjijirerkjfk设叶片的排序方案用排列来表示，即叶片排在第位，那么合力就是：问题就是求排列使为最小。于是，设变量为，其意义为：),,,(21njjjkjknknkijkkkerkjfF11),()(,)(Fnknjxjk,,2,1;,,2,1,位未被排在第表示叶片位被排在第表示叶片kj0kj1jkx这样合力可表示为：而于是问题的目标可以表示为：，而约束条件为每片叶子只能安装在一个位置上，即：njnkjkijxerk11FnjnkpqnpnqjkpkpjnpnqpqipnjnkjkijxxrrxerxerFFFqk111111112)cos(,,2minFnkjknjx1,,2,11而且每个位置上只能安装一片叶子，即：故汽轮机叶片排序问题的数学模型为：njjknkx1,,2,1,1nkjxxnkxnjxtsxxrrFjkjknjjknkjknjnkpqnpnqjkpkpj,,2,1,,10,2,1,1,2,1,1..)cos(min1111112或例4：投资的收益与风险市场上有种资产(如股票，债券等)共投资者选择，某公司有一笔数额为的资产作为一个时期的投资，公司财务人员对几种资产进行了评估，估算出在这一时期内购买的平均收益率为，并预测购买的风险损失率为,考虑到投资越分散，总的风险越小，公司决定，当用这笔资金购买若干种资产时，总体风险可用所投资的中最大的一个风险来度量。n),2,1(nisiMisirisiqis购买要付交易费，费率为，并且当购买不超过给定值时，交易费按购买计算（不买无需付费），另外，假定同期存款利率且既无交易费又无风险。已知时的相关数据如下：isipiuiu%)5(00rr4nisiriqipiu1s2s3s4s（%）（%）（%）(元)282.51103211.52198235.54.552252.66.540is1s2s3s4siriqipiu试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或银行生息，使净收益尽可能的大，总风险尽可能的小。M设变量分别表示存入银行和购买的金额，表示不购买，表示购买，目标有两个：第一个目标：第二个目标：约束是总资金为，以及之间的关系。)4,3,2,1,0(,iyxiiis0iyisis)4,3,2,1(,1jyi40411},max{maxiiiiiiiiuxypxrz}{maxmin412iiixqzMniiixMx10,iiyx,故投资的收益和风险的数学模型为：4,3,2,1,1or0,4,3,2,1,00..}{maxmin},max{max141240411jyMyxixMxtsxqzuxypxrzjjjiniiiiiiiiiiiii1.2最优化问题的模型与分类数学规划定义：在一些等式或不等式约束条件下，求一个目标函数的极大或极小的优化模型称为数学规划。数学规划分为：约束数学规划和无约束数学规划。约束数学规划一般形式为：(P)其中称为优化向量或决策变量；称为目标函数；约束函数分别称为不等式约束和等式约束，等式约束和不等式约束统称为约束条件。},,2,1{,0)(},,2,1{,0)(s.t.))(min(or)(maxmIjxglEixhxfxfjinTnRxxxx),,,(21RRfn:)(),(EjhIigji令：,我们称D为（P）的约束集合（约束区域）或可行域。若，则称为可行点或可行解，设若对任意的，都有，则称为优化问题（P）的全局最优解（极小点或极大点）若存在的一个的领域：当时，有，称为优化问题（P）的局部最优解，如时，有，称为优化问题（P）的严格局部最优解。},0)(;,0)({EjxhIixgRxDjinDxxDx*Dx)()(*xfxf*x*x)0(}{),(**xxxxN),(*xNDx)()(*xfxf*x),(*xNDx)()(*xfxf*x问题的分类1．无约束优化问题当时，问题(P)称为无约束优化问题，无约束优化问题是指在空间上寻求使目标函数达到极小或最小的点（解）。2．约束优化问题若指标集I与E中至少有一个非空，则称(P)为约束优化问题，约束优化问题是在约束集D上寻求使目标函数达到极小或最小的点（解）。IEnR若，即问题(P)只含有等式约束，此时称问题(P)为等式约束优化问题；若，即问题(P)只含不等式约束，此时称问题(P)问不等式约束优化问题；否则称问题(P)为混合优化问题。如果目标函数目标函数和约束函数都是线性，则称问题为线性规划，线性规划常记为LP；如果目标函数和约束函数中至少有一个是非线性函数，则称问题为非线性规划，常记为NP；在非线性规划中，若约束函数均是线性函数，则称问题为线性约束非线性规划问题，常记为NLP；EI,EI,目标函数为二次函数的线性约束问题称为二次规划问题，常记为QP。若变量限制取整数，则称为整数规划；若变量限制取0或1，则称为0—1规划；若变量既可取整数，又可取小数，则成为混合整数规划。若所研究的问题只含一个