第三章 数学规划基础.pptVIP

第三章 数学规划基础 主要内容 线性规划 目标规划 整数规划 非线性规划 动态规划 例3-1 某工厂生产A, B两种产品，产量分别为x1, x2 每生产一台产品A，投入原料5kg，占地4m2 ，60单位/小时 每生产一台产品B，需要上述资源3Kg，5m2，30单位/小时 工厂每天可用资源，原料1575kg，占地面积1500m2,工时7小时 产品A收益13元，产品B收益11元 工厂每天A，B各多少台总收益最大。 线性规划(Linear Programming) 建立线性规划模型 明确决策变量； 明确约束条件； 明确目标函数。 数学模型 线性规划的标准形式 两变量线性规划的图解法 例： 基本概念 可行解：在阴影区域，一切x1和x2的值能满足全部约束条件，x1和x2称为线性规划问题的可行解； 全部可行解的集称为可行解集或可行域； 线性规划的解是指可行解中使目标函数值极大或极小的那个解，称为最优解； 对应最优解的目标函数值称为最优值。 例 线性规划的解 单纯形法 1947年，美国学者GeorgeDantzig提出； 基本思想：从一个基本可行解开始，转换到另一个相邻的基本可行解，并且相应的目标函数值有所改进。 单纯形法的一般步骤 如果线性规划存在基础可行解，就可以找出一个，称为初始基础可行解； 如果线性规划不存在基础可行解，则由找基础可行解的过程可知问题无解； 以初始基础可行解为起点，找到相邻的另一 基础可行解，这一步骤为迭代，直到找到最优解。 案例 单纯形法迭代的基本原理 两个原则 引入变量——最大增加原则 退出变量——最小比值原则 线性规划问题 单纯形表（1） 单纯形表（2） 单纯形表（3） 表格形式的单纯形法（1） 表格形式的单纯形法（2） 表格形式的单纯形法（3） 单纯形法具体迭代过程 化线性规划为标准型 确定初始基础可行解 迭代 引入变量 退出变量 高斯消元法求新的可行解（基变量的解） 重复迭代 目标函数中检验数=0，停止迭代 线性规划的对偶问题 对偶问题数学模型 对偶问题的性质 互为对偶 对偶两问题，极小（大）问题的可行解的目标函数不小（大）于极大问题的最优值。 其一有最优解，另一也有最优解 目标规划 1961年，美国学者Charnes和Cooper提出目标规化； 目标规划根据实际需要，对多目标关系给予轻重缓急的考虑，找到尽量满足约束的满意解。 目标规划数学模型 目标规划的图解法 目标规划的单纯形法（1） 目标规划的单纯形法（2） 目标规划的单纯形法（3） 目标规划的单纯形法（4） 目标规划的单纯形法（5） 整数规划 要求一部分或全部决策变量必须取整数值的规划问题。 不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题。 整数规划的数学模型 案例1 某服务部门各时段（每2h为一时段）需要的服务人数。服务员连续工作8h为一班，如何安排服务员工作时间，使服务部门服务员总数最少 时段 1 2 3 4 5 6 7 8 最少人数 10 8 9 11 13 8 5 3 案例2 资金总额B，可供选择项目有n个，项目j所需投资和收益分别为aj和cj 若选项目1，必须同时选项目2；反之，不一定 项目3和4中至少选1个； 项目5、6和7中恰好选择2个； 分枝定界图解 分支界定法 首先求解原问题的松弛问题xi=bi； 若解不符合整数要求——分支； xi≤[bi]和xi≥[bi]+1 根据界限剪枝； 分支界定法 非线性规划 目标函数或约束条件中包含有自变量的非线性函数； 非线性规划常用方法 无约束极值的解析方法: 一维最优化：Fibonacci法 多维最优化：梯度法 有约束极值条件：罚函数法，线性逼近法 区间消去法 菲波那契法(Fibonacci) Fibonacci数列 特点 F0=F1=1 Fk=Fk-1+Fk-2 lim(Fk/FK+1)=0.618 图 解 公 式 公 式 最速下降法 最速下降法 最优步长 惩罚函数法 动态规划(dynamic programming) 解决多阶段决策过程最优化问题； 最优路径问题 分阶段的最短路径 Ⅳ ： C1—T 3 Ⅲ --Ⅳ : B1—C1—T 4 Ⅱ--Ⅲ--Ⅳ ：A2—B1—C1—T 7 Ⅰ--Ⅱ--Ⅲ --Ⅳ： Q—A2—B1—C1—T 11 Q--A3—B1—C1—T 11 Q--A3—B2—C2—T 11 最短路径解的特点 1、可以将全过程求解分为若干阶段求解；------多阶段决策问题 2、在全过程最短路径中，将