第1章第1节最优化的基本问题第1.1节(已修改)

1、提 纲一、 前沿问题：n 经济背景： 经济运行的对象：大规模、多层次、多元化 经济运行的行为：快速、多变、不确定、高风险 经济决策的方法：数学模型、算法、软件经济管理的手段：计算机、数字信息 n 关于模型： 非凸(non-convex)、非线性(non-linear)、非光滑(non-smooth )，高维(Large- scales）1、 管理决策问题：物流供应链问题，（协调,更新,替代等,博弈论，动态规划）2、 制造业问题:,:柔性生产,排序问题(Scheduling )3、 实时优化(Real-time)问题n 关于算法：NP, NPC, NP-hard 问题近似算法：启发式算法（heu

2、ristic ）GAS , NA, SA, AA, PSO 等 日本（Mitson Gen）二、 内容目录1、最优化的基本问题 （参数优化与非参数优化）2、动态优化问题：最优控制问题3、实时优化(Real-time)问题第一章 最优化的基本问题-最优化问题及最优化算法 §0 非线性规划与线性规划 数学规划问题：在一组约束条件下，使某分目标函数最优化问题称数学规划问题 网络流规划问题：定义在流动网络上的数学规划问题叫网络规划问题 组合最优化（规划）：在有限个可行解集中找出最优解的组合叫组合最优化 网络最优化：定义在图和网络上的一类组合最优化问题（是组合优化中最基本、最简单的一类）即网络

3、优化是组合优化的一部分内生。网络规划问题的解法可化为整数规划来求解，最终是解线性规划问题。线性规划：在线性约束条件下，求解线性目标函数的极值问题（最大、最小值问题）整数规划：在线性规划中，自变量只允许取整数，叫整数线性规划。整数规划以可行解都是相应性规划的可行解，有时线性规划多面体的每一个顶点，所有的特点恰好是整数，这时线性规划的最优解一定是整数规划的最优解和这些整数规划都可用线性规划方法来求解。0-1线性规划：在整数线性规划中，自变是只允许取0-1的线性规划叫0-1线性规划，它是整数线性规划的特殊情况。网络规划：有不少网络规划问题都可表示成整数规划问题，而整数规划问题的解可通过顶点生标是整数

4、的线性规划问题来求解。因此线性规划的理论与方法是解网络优化问题的重要方法。 变量取0-1 0-1线性规划即线性规划 利用 变量取整数 整数规划 求解网络规划 整数规划但某些特殊网络流问题的求解方法，比单纯形方法更为有效。因此有必要单独讨论网络规划的模型与算法。§1 非线性规划与线性规划优化问题：1无条件极值 问题：在分析中Rn ， ， 求f（x）最小值。即：无条极值问题 （1）当f(x)在闭上连续 且f(x)在内可微时最小值一定存在，且在内的稳定点或边界上达到。（稳定点即f(x)的所有偏导数都为0，即。2条件极值求, 且 x 满足： （2）（2）与（1）相比差别：x取值范围多了一组等

5、式约束。解法：利用logrange和子法，把条件极值问题化为一般的条件极值问题。3非线性规划问题如果：1° （1）式 比（2）式更一般一此：除对x等式约束再加上一组不等式约束。 2° 都是非线性函数。即求： （3）非线性规划是近几十年，计算机出现后才发展起来的新数学分支，因为各类实际问题应用广泛，所以发展迅速，目前，大多取名“最优化”的论着，主要讨论非线性规划。4非线性规划的标准形式 不等式约束比不等式约束更具一般性，由于等式约束可用两个不等式约束代替，即所以非线性规划可写成： （4）可行解：满足约束条件x值：称为该非线性规划问题的可行解。最优解：使目标函数达最小值的可行解

6、称为最优解。注：一个规划问题最优解 可能不是唯一的，但在解规划问题时任意找到一个最优解，就认为非解决了。一般不要求找到全部最优解。 定义非线性规划问题的全体可行解构成Rn的区域。若把约束条件看成是，定义方式即：，则（1）式具有更一般意义，而（3）、（4）则可看成（1）式的特例。非线性规划所研究内容比分析中要深刻得多，重点在于研究能快速求出最优解的方法。5凸规划：非线性规划中的一种特殊情况def: 当是凸区域，同时目标函数也是凸函数时，这样的非线性规划称为凸规划。凸规划的特性：局部极值点就是整体极值点。6线性规划在（4）中： （4）当都是线性函数时，该解为线性规划。注意 ：显然，线性规划是凸规划

7、的特殊情况。线性规划研究的内容和方法与其它非线性规划有很大差别。而且在应用中特别重要，所以独立出来研究。线性规划的标准形式： （5） 其中：若x是Min f(x)的最优解x也是的最优解。于是：在线性规划中，求最大值与最小值没有本质的区别。注意：“”号不能改为“<”，否则可行解的区域就由闭区域变成开区域了，那么最优解的存在性就要发生疑问了。可行解的非负性：，是讨论需要引入的，这并不破坏（5）式的一般性，因为不包括非负性的规划可通过一些简单变换，归结为非负性。约束条件所决定的可行解的全体，决定了Rn的一个凸区域，称为线性规划的多面体，同二维、三维多面体一样，可定义多面体的面和顶点（极点）。线

8、性规划约束条件所定义的多面体顶点个数有限，且线性规划最优解一定在顶点达到。因为线性规划的最优解的一点在某个顶点达到，因此求解性规划的最优解：只要在有限个作为顶点的可行集解中去寻找就够了。即把连续寻优变成了离散寻优。基于此种想法,Dantzig 1947年发现了解线性规划问题的单纯形法。就实用性来说，单纯形法自然是解决线性规划问题的最好方法。线性规划是解“网络规划”的重要方法。许多网络流规划都可归结为线性规划，从而用单纯形法求解，但某些特殊网络流的求解方法，比单纯形法更为有效。因此有必要单独讨论网络规划的模型与算法。附1：单纯形法（simplex algorithm）的求解思路：从一个基解开始，

9、然后由安产生另一个合适的基解，使目标函数有较佳的数值，将过程重复进行（选代），直至求得一个被认为是最优的基本解为止。此过程只是重复进行有限次，因为没有一个基本解会重复出现（每一步都产生一个较佳解），而是仅有有限个不同的解。附2：某些图论的问题，将用类似于单纯形的方法求解，即求出一个基本解，然后从原始基解中再产生另一个较佳的基本解。重复有限次，直至求出最优解。因此，有必要研究在有限可行解集中找出优化问题最优解的问题，而网络优化的可行的大部分都是有限集，故有组合优化问题。附3: 关于整数规划求解与线性规划求解（单纯形法）的关系问题：· 纯整数规划：所有变量全部都是（非负）整数。（Pure

10、 zutegerprogramming All znteger programming）· 混合整数规划：（Mixed Znteger programming）· 0-1规划：变量取值仅为0或1，是一种特殊线性规划，指派问题就0-1规划问题。例：某厂利用集装箱托运甲、乙两种货物，每箱的体积、重量及每箱的托运限制；及每种货物可获得利润如下表： 货物/每箱体积重量甲乙托运限制（每箱）体积（m3）5424（m3）（每箱）重量（kg）2513(kg)利润（百元/箱）2010问两种货物各托运多少箱，可使获利润最大？解：分别为甲、乙两种货物的托运箱数（当然为非负整数）故有： （1）S.

11、 t （2） （3） （4） ，即为整数 （5）解法：若不考虑（5），用单纯形法求解得考虑（5）：因托运货物为甲种货物的箱数，故为整数。但= 4.8故不符合条件（5）：为此采用取整数的方法。（i）若令则破坏条件（2）（5×5+4×0=2524不成立）即=5 不是可行解。（ii）又若令则此时满足（2）、（3）、（4）、（5）即为可行解，但此时有此时不是最优解，因为此时可行域内还有 时，此时有因此求解整数规划不能简单用求解线性规划求解方法，再取整的方法。应单独讨论艺术解方法。并用于求解网络规划问题上来。图解如下：x2321x11 2 3 4 5 6 7（5，0）不在可行域内(4

12、.8,0)是LP问题（2）（4）最优解但不是整数解。§2 组合最优化问题1组合最优化在有限个可行解集合中找出最优解，这类问题称为组合最优化问题。即：设F是有限集，C是F到R（实数）的映射（实数）即：C是定义在F上的一个函数。组合优化问题即：求，使得对任意都有：即：求，使得 组合优化问题中，最优解的存在性是不成问题的。唯一性不感兴趣，唯一感兴趣的是：迅速求出组合优化问题的最优解。2网络最优化定义在图和网络上的一类组合最优化问题，叫网络最优化问题。网络优化是组合优化中最简单、最基本的一类组合优化(关于图和网络的定义将在下一节详细讨论)。3网络最优化的例子EX1：最短路问题：1n已知：给定

13、n个城市1，2，n，已知连接城市，道路长度为（共i与j之间无直接相连的道路则规定）求一条连接城市1和城市n的最短道路。这个问题称为最短路问题。分析：最短路问题的可行解集F是所有可能连接城市1和城市n的道路集且通过其它城市2，3，n-1不超过一次。显然道路集F中的元素是有限的，即所有从1到n的道路只有有限条。是道路f的长度，它等于各段道路之和。问题是设计一个有效算法，把和其对应的路段连接起来。EX2：最小连接问题：（最小树问题）已知：有n个城市，即要架设通讯线路，把n个城市都连接起来。架设城市的通讯线路所需费用为。求：在那些城市之间架设线路，既能使所有城市之间都能连通，又要总架设费用最小？分析：

14、 网络规划中最小树问题EX3：分配问题(Assignment )已知：有n个工人分配去干n项工作，每人只能干一项工作。工人i去干j项工作，收益为（即每个工人干不同的工作所得效益是不同的）。求：如何安排n个工人去干n项工作，使总收益最大。（总收益即每个工人收益的总和）分析：每种工作分配方案相当于一个n的排列 因此可行解的个数恰好为 n2个0-1变更：即令为第i个工人去干第j件工作。即即：注意：该计算该问题的严重性， 若 来看计算 种可行方案的所用时间：假定一台计算机一秒钟计算100万个方案，则在n 取不同值时，种可行方案的计算时间如下表 取值可行方案 ： F 种方案 种方案 种方案计算所需时间

15、4秒 年（7万7千年） 年（比地球年龄长） EX4：运输问题已知：某种物质（例如水泥、生猪）有m个产地，可供给量分别为。供销平衡。从产地i运往销地j的单位运费。求：运输方案，使总运费最少。分析：假定要求：运输是，供给量、需求量都是整数。即：注1：前面介绍的是组合优化问题的一部分，大多都可归为网络优化问题，有些问题本身就是网络优化问题。2：本书只介绍与图和网有关的最优化问题。3：组合优化与线性规划在形式上很接近，都是线性目标和线性约束，只是在约束中多了一个限制：自变量取整数，或整数中特殊情况只取0-1（因此可称整数规划或0-1线性规划）。4：组合优化可行解的性质组合优化与线性规划关系。整数规划的可行解都是相应线性规划可行解。即如果线性规划在顶点处的解的坐标如果