文档介绍：整数规划与混合整数规划2015/10/22应用优化技术1整数规划与混合整数规划混合整数规划问题分支定界法0-1规划的隐数法割平面法混合整数非线性规划2015/10/22应用优化技术2混合整数规划问题f,h,g线性minf(xy,)LPxy,Y空st..h(x,y)0一大类f,h,g非线性NLPg(x,y)0优化命题xXRnf,h,g线性yY整数MILPY非空f,h,g非线性MINLP2015/10/22应用优化技术3混合整数线性规划问题mincTTxdyxy,LPst..AxBybnxx0,XR0-1规划y0,1LN1yyz12z24z32zNULlogyyN1INTlog22015/10/22应用优化技术4实例一0-1背包问题容积v物品j:价值wj,体积vj设1j放入xj0j不放nmaxwxjjj1ns..tvjjxvj1xj0或1,j1,2,n2015/10/22应用优化技术5实例二工厂选址问题n个城市,需要某种物资数量为d1,d2,…,dn现计划建造m座工厂假设在城市j建厂,规模为Sj,投资为Fj,从城市i到j的单位运价为Cij问m个工厂应设在何处,使满足需要且成本最低minCxFy1若有一个工厂建在城市iijijiii,jiyi.xijSiyii1,,nj1nxij为i运往j的物资总量xijdjj1,,ni1nymii1或2015/10/22应用优化技术yi016xij0i,j1,2,,n实例三调和问题:利用一些成分mincjxjdkvkyk调和为一个产品jklus..twxjvkykwxj——连续用量的j成分的量jkyk——1或0表示离散用量的luAiaijxjaikvkykAi成分用或不用;vk表示用量jkc,d——成分的成本jk0xjjuforallja——成分j中i组分分量ijykk(0,1)forall如何调和使得产品质量合格ujj成分上界且成本最低?wwlu,重量上下界luAii,Ai分析上下界2015/10/22应用优化技术7实例四对任意、,引入xij(0,1)TSP问题AiAj若紧跟着Ai后的是Aj,取从A0出发,经过A1、xij1,否则xij0A2、…、An再回到A0nnmindx到的距离:ijijAiAjdijij00.xij1i0,,nj0个城市A0,Ai1,Ai2,,Ain,A0nxij1j0,,ni0任意非空真子集xij1S0,1,,njSjS形成回路nnxnij1ij00xij0或1i,j0,,n2015/10/22应用优化技术8实例五加工问题m台机床,n种零件加工时间a12,a,,an如何分配,使各机床总加工任务相等,或尽可能均衡minx0nx0i1,,mxij不在上加工j10aijmxij=1j1,,ni1xij(0,1)i1,,m,j1,,n2015/10/22应用优化技术9整数规划解法概述枚举可行方案的数目常常是有限求解实际问题不现实先放弃变量的整数性要求,然后求整数解只有在变量取值很大时才有成功的可能性变量取值较小时,如0-1变量,往往不会成功2015/10/22应用优化技术10