优化建模与LINGO第01章

优化建模优化建模与LINDO/LINGO软件第1章引言［原书相关信息］谢金星,薛毅编著,清华大学出版社,2005年7月第1版.~jxie/lindo优化建模内容提要1.优化模型的基本概念2.优化问题的建模实例3.LINDO/LINGO软件简介优化建模1.优化模型的基本概念优化建模最优化是工程技术、经济管理、科学研究、社会生活中经常遇到的问题,如:优化模型和算法的重要意义结构设计资源分配生产计划运输方案解决优化问题的手段•经验积累，主观判断•作试验，比优劣•建立数学模型，求解最优策略最优化:在一定条件下，寻求使目标最大(小)的决策优化建模优化问题三要素：决策变量；目标函数；约束条件约束条件决策变量优化问题的一般形式njiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(min•无约束优化(没有约束)与约束优化(有约束)•可行解（只满足约束）与最优解(取到最优值)目标函数优化建模局部最优解与整体最优解•局部最优解(LocalOptimalSolution,如x1)•整体最优解(GlobalOptimalSolution,如x2)x*f(x)x1x2o优化建模优化模型的简单分类•线性规划(LP)目标和约束均为线性函数•非线性规划(NLP)目标或约束中存在非线性函数二次规划(QP)目标为二次函数、约束为线性•整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)纯整数规划(PIP),混合整数规划(MIP)一般整数规划，0-1（整数）规划njiDxljxgmixhtsxf,...,1,0)(,...,1,0)(..)(min连续优化离散优化数学规划优化建模优化模型的简单分类和求解难度优化线性规划非线性规划二次规划连续优化整数规划问题求解的难度增加优化建模2.优化问题的建模实例优化建模1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大•35元可买到1桶牛奶，买吗？若买，每天最多买多少?•可聘用临时工人，付出的工资最多是每小时几元?•A1的获利增加到30元/公斤，应否改变生产计划？每天：线性规划模型－例1.1:奶制品生产计划优化建模1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤x1桶牛奶生产A1x2桶牛奶生产A2获利24×3x1获利16×4x2原料供应5021xx劳动时间48081221xx加工能力10031x决策变量目标函数216472xxzMax每天获利约束条件非负约束0,21xx线性规划模型(LP)时间480小时至多加工100公斤A150桶牛奶每天优化建模模型分析与假设比例性可加性连续性xi对目标函数的“贡献”与xi取值成正比xi对约束条件的“贡献”与xi取值成正比xi对目标函数的“贡献”与xj取值无关xi对约束条件的“贡献”与xj取值无关xi取值连续A1,A2每公斤的获利是与各自产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数A1,A2每公斤的获利是与相互产量无关的常数每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数加工A1,A2的牛奶桶数是实数线性规划模型优化建模模型求解图解法x1x20ABCDl1l2l3l4l55021xx48081221xx10031x0,21xx约束条件50:211xxl480812:212xxl1003:13xl0:,0:2514xlxl216472xxzMax目标函数Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解目标函数和约束条件是线性函数可行域为直线段围成的凸多边形目标函数的等值线为直线最优解一定在凸多边形的某个顶点取得。优化建模求解LP的基本思想思路：从可行域的某一顶点开始，只需在有限多个顶点中一个一个找下去，一定能得到最优解。LP的约束和目标函数均为线性函数2维可行域线段组成的凸多边形目标函数等值线为直线最优解凸多边形的某个顶点n维超平面组成的凸多面体等值线是超平面凸多面体的某个顶点LP的通常解法是单纯形法(G.B.Dantzig,1947)优化建模内点算法(Interiorpointmethod)•20世纪80年代人们提出的一类新的算法——内点算法•也是迭代法，但不再从可行域的一个顶点转换到另一个顶点，而是直接从可行域的内部逼近最优解。LP其他算法有效集(ActiveSet)方法•LP是QP的特例（只需令所有二次项为零即可）•可以用QP的算法解QP(如:有效集方法)优化建模线性规划模型的解的几种情况线性规划问题有可行解(Feasible)无可行解（Infeasible）有最优解（Optimal）无最优解(Unbounded)优化建模牌号产量成本价格甲x1q1p1乙x2q2p2假设A产销平衡假设Bp随x(两种牌号)增加而减小，呈线性关系12111211121211111,0,,,aaaabxaxabp某厂生产两个牌号的同一种产品，如何确定产量使利润最大21222221222212122,0,,,aaaabxaxabp二次规划模型－例1.2：产销计划问题优化建模22211121,)()(),(max21xqpxqpxxzxx目标利润最大=（100-x1-0.1x2-2）x1+（280-0.2x1-2x2-3）x2=98x1+277x2－x12－0.3x1x2－2x22约束x1+x2≤100x1≤2x2x1,x2≥0二次规划模型(QP)若还要求产量为整数，则是整数二次规划模型(IQP)优化建模非线性规划模型－例1.3：选址问题某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）i１２３４５６a1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)现有2料场，位于A(5,1),B(2,7),记(xj,yj),j=1,2,日储量ej各有20吨。假设：料场和工地之间有直线道路目标：制定每天的供应计划，即从A,B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。优化建模用例中数据计算，最优解为i1234561ic（料场A）3507012ic（料场B）0040610总吨公里数为136.22,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij线性规划模型(LP)决策变量：cij(料场j到工地i的运量）~12维优化建模选址问题：NLP2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。2,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：cij，(xj,yj)~16维非线性规划模型(NLP)优化建模整数规划-例1.4:聘用方案某服务部门一周中每天需要不同数目的雇员：周一到周四每天至少50人，周五和周日每天至少80人，周六至少90人。决策变量：周一至周日每天(新)聘用人数x1,x2,x7目标函数：7天(新)聘用人数之和约束条件：周一至周日每天需要人数现规定应聘者需连续工作5天，试确定聘用方案，即周一到周日每天聘用多少人，使在满足需要的条件下聘用总人数最少。优化建模80908050505050..min765436543254321743217632176521765417654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz连续工作5天5017654xxxxx周一工作的应是(上)周四至周一聘用的设系统已进入稳态（不是开始的几周）聘用方案即为非负整数，Zxi整数规划模型(IP)优化建模丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?0-1规划－混合泳接力队的选拔甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”4例1.5：5名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。优化建模目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=00-1规划模型cij(秒)~队员i第j种泳姿的百米成绩约束条件每人最多入选泳姿之一ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每种泳姿有且只有1人5,1,141ixjij4,1,151jxiij0-1规划:整数规划的特例优化建模整数规划问题一般形式ljxgmixhtsxfjiZxn,...,1,0)(,...,1,0)(..)(min•整数线性规划(ILP)目标和约束均为线性函数•整数非线性规划(NLP)目标或约束中存在非线性函数整数规划问题的分类•纯(全)整数规划(PIP)决策变量均为整数•混合整数规划(MIP)决策变量有整数，也有实数•0-1规划决策变量只取0或1优化建模取消整数规划中决策变量为整数的限制（松弛），对应的连续优化问题称为原问题的松弛问题整数规划问题对应的松弛问题松弛问题松弛整数规划问题最优解最优解整数非整数整数舍入下界（对Min问题）上界（对Max问题）非最优解优化建模用连续优化方法求解松弛问题，如果松弛问题最优解（分量）全为整数，则也是原整数规划问题的最优解对松弛问题的最优解（分量）舍入为整数，得到的往往不是原整数规划问题的最优解（甚至不是可行解）IP可行解对应于整点A(2,2)和B(1,1),而最优解为A点.但LP松弛的最优解为C(3.5,2.5)目标函数下降方向x1x2CABO优化建模且为整数0,45956..85max21212121xxxxxxtsxxz．．．．．．．．．．．．．．．．．．．x1x20Po69Zmax56去掉整数限制后，可行域为点（0,0),(6,0),(0,5),P(2.25,3.75)围成的4边形LP最优解PP的舍入解最靠近P的可行解IP最优解（2.25，3.75）（2，4）（2，3）（0，5）z=41.25不可行z=34z=40从LP最优解经过简单的“移动”不一定能得到IP最优解例1.6优化建模基本思想：隐式地枚举一切可行解（“分而治之”）所谓分枝，就是逐次对解空间（可行域）进行划分；而所谓定界，是指对于每个分枝（或称子域），要计算原问题的最优解的下界（对极小化问题）.这些下界用来在求解过程中判定是否需要对目前的分枝进一步划分，也就是尽可能去掉一些明显的非最优点，避免完全枚举.分枝定界法（B&B:BranchandBound）对于极小化问题，在子域上解LP，其最优值是IP限定在该子域时的下界；IP任意可行点的函数值是IP的上界。这里仅介绍整数线性规划的分枝定界算法优化建模无约束优化更多的优化问题线性规划非线性规划网络优化组合优化整数规划不确定规划多目标规划目标规划动态规划连续优化离散优化从其他角度分类•应用广泛：生产和运作管理、经济与金融、图论和网络优化、目标规划问题、对策论、排队论、存储论，以及更加综合、更加复杂的决策问题等•实际问题规模往往较大，用软件求解