最优化方法教案东北大学

1 第一章 最优化问题与数学预备知识 最优化分支：线性规划，整数规划，几何规划，非线性规划，动态规划。又称规划论。 应用最优化方法解决问题时一般有以下几个特点： 1 . 实用性强 2 . 采用定量分析的科学手段 3 . 计算量大，必须借助于计算机 4 . 理论涉及面广 应用领域：工业，农业，交通运输，能源开发，经济计划，企业 管理，军事作战„„。 2 §1.1 最优化问题实例 最优化问题：追求最优目标的数学问题。 经典最优化理论： （1） 无约束极值问题：),,,(opt 21nxxxf （),,,(min 21nxxxf或),,,(max 21nxxxf） 其中，),,,(21nxxxf是定义在 n 维空间上的可微函数。 解法（求极值点）：求驻点，即满足 0),,(0),,(0),,(11121nxnxnxxxfxxfxxfn 并验证这些驻点是否极值点。 （2） 约束极值问题：),,,(opt 21nxxxf s.t. )(,,2,1,0),,,(21nlljxxxhnj 解法：采用 Lagrange 乘子法，即将问题转化为求 Lagrange 函数 ),,(),,,(),,;,,,(1121121njjljnlnxxhxxxfxxxL的无约束极值问题。 近代最优化理论的实例： 例 1 (生产计划问题) 设某工厂有 3 种资源 B1，B2，B3，数量各为 b1，b2，b3，要生产 10 种产品 A1，„，A10 。每生产一个单位的Aj 需要消耗 Bi 的量为 aij，根据合同规定，产品 Aj 的量不少于 dj，再 3 设Aj 的单价为cj 。问如何安排生产计划，才能既完成合同，又使总收入最多？（线性规划问题） 数学模型：设Aj 的计划产量为 jx，z 为总收入。 目标函数： max101jjjxcz  约束条件： 10,,2,1,3,2,1,101jdxibxajjjijij 线性规划问题通常采用单纯形法来求解。 例 2 (工厂设址问题) 要在 m 个不同地点计划修建m 个规模不完全相同的工厂，他们的生产能力分别是maaa,,21（为简便起见，假设生产同一种产品），第 i 个工厂的建设费用mifi,,2,1,。又有 n 个零售商店销售这种产品，对这种产品的需求量分别为nbbb,,21，从第 i 个工厂运送一个单位产品到第 j 个零售商店的运费为cij。试决定应修建哪个工厂，使得既满足零售商店的需求，又使建设工厂和运输的总费用最小。（混合整数规划问题） 数学模型： 设第 i 个工厂运往第 j 个零售商店的产品数量为xij（i=1，„，m；j=1，„，n），且 miiyi,,1, ,0 ,1否则...