线性整数规划模型课件

《线性整数规划模型课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、优化建模与计算参考书《优化建模与LINDO/LINGO软件》谢金星,薛毅编著,清华大学出版社,2005年7月第1版.http://faculty.math.tsinghua.edu.cn/~jxie/lindo内容提要1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO软件简介1.优化模型的基本概念最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:优化模型和算法的重要意义结构设计资源分配生产计划运输方案解决优化问题的手段经验积累，主观判断作试验，比优劣建立数学模型，

2、求解最优策略最优化:在一定条件下，寻求使目标最大(小)的决策优化问题三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题的一般形式无约束优化(没有约束)与约束优化(有约束)可行解（只满足约束）与最优解(取到最优值)目标函数局部最优解与整体最优解局部最优解(LocalOptimalSolution,如x1)整体最优解(GlobalOptimalSolution,如x2)x*f(x)x1x2o优化模型的简单分类线性规划(LP)目标和约束均为线性函数非线性规划(NLP)目标或约束中存在非线性函数二次

3、规划(QP)目标为二次函数、约束为线性整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划连续优化离散优化数学规划优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加2.优化模型实例目标函数约束条件例2.1线性规划模型(LP)模型求解图解法x1x20ABCDl1l2l3l4l5约束条件目标函数Z=0Z=2400Z=3600z=c(常数)~等值线c

4、在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。求解LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。LP的约束和目标函数均为线性函数2维可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点LP的通常解法是单纯形法(G.B.Dantzig,1947)线性规划模型的解的几种情况线性规划问题有

5、可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)目标98x1+277x2－x12－0.3x1x2－2x22约束x1+x2≤100x1≤2x2x1,x2≥0二次规划模型(QP)若还要求变量为整数，则是整数二次规划模型(IQP)二次规划模型(QP)-例1.2决策变量：cij，(xj,yj)~16维非线性规划模型(NLP)非线性规划模型(NLP)－例1.3：整数规划问题一般形式整数线性规划(ILP)目标和约束均为线性函数整数非线性规划(NLP

6、)目标或约束中存在非线性函数整数规划问题的分类纯(全)整数规划(PIP)决策变量均为整数混合整数规划(MIP)决策变量有整数，也有实数0-1规划决策变量只取0或1取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入非最优解基本思想：隐式地枚举一切可行解（“分而治之”）所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题

7、）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.分枝定界法（B&B:BranchandBound）整数线性规划的分枝定界算法无约束优化更多的优化问题线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划连续优化离散优化从其他角度分类应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等实际问题规模往往较大，用软件求解比较方便3.LINDO/L

8、INGO软件简介常用优化软件1.LINDO/LINGO软件2.MATLAB优化工具箱/Mathematic的优化功能3.SAS(统计分析)软件的优化功能4.EXCEL软件的优化功能5.其他（如CPLEX等）MATLAB优化工具箱能求解的优化模型优化工具箱3.0(MATLAB7.0R14)连续优化离散优化无约束优化非线性极小fminunc非光滑(不可微)优化fminsearch非线性方程(组)fzerofsolve全局优化暂缺非线性最小二乘lsqnonli