资源描述：
《混合整数线性规划.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、混合整数线性规划第二篇过程优化张冰剑020-84113653zhbingj@mail.sysu.edu.cn1优化问题的一般形式优化问题三要素：决策变量；目标函数；约束条件目标函数minf(x)ts..h(x)=,0i=1,...,m约i束gj(x)≤,0j=1,...,l条件决策变量x∈D⊆ℜn2变量类型连续变量：温度、压力和流程等，通常称为操作变量决策变量离散变量：设备和流程选择等，通常称为结构变量3整数规划问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。松弛问题：不考虑整数条件，由余下的目标函
2、数和约束条件构成的规划问题。学习重点：整数线性规划问题(MIP)4nmax(min)Z=∑cjxjj=1n⎧⎪∑aijxj≤(≥,=)bi⎨j=1⎪x≥0⎩jx中取部分或全部为整数j若变量全部取整数，称此为纯整数规划。若其中仅部分变量要求取整数，则称为混合整数规划，其解法较一般线性规划的解法要复杂些。5背包问题(KnapsackProblem)一个旅行者一个旅行者,,为了准备旅行的必须用品为了准备旅行的必须用品,,要在要在背包内装一些最有用的东西背包内装一些最有用的东西,,但有个限制但有个限制,,最最多只能装多只能装bb公斤的
3、物品公斤的物品,,而每件物品只能整个而每件物品只能整个携带携带,,这样旅行者给每件物品规定了一个这样旅行者给每件物品规定了一个““价价值值””以表示其有用的程度以表示其有用的程度,,如果共有如果共有nn件物品件物品,,第第jj件物品件物品aaj公斤公斤,,其价值为其价值为ccj..问题变成问题变成::在在携带的物品总重量不超过携带的物品总重量不超过bb公斤条件下公斤条件下,,携带携带哪些物品哪些物品,,可使总价值最大可使总价值最大??6解：解：如果令如果令xxj=1=1表示携带物品表示携带物品jj，，xxj=0=0表示不携带物
4、品表示不携带物品jj，，则问题表则问题表示成示成00--11规划规划::MaxZ=MaxZ=ΣΣccjjxxjjs.t.s.t.ΣΣaajjxxjj≤≤bbxxjj=0=0或或117解法概述解法概述当人们开始接触整数规划问题时，常会当人们开始接触整数规划问题时，常会有如下两种初始想法：有如下两种初始想法：因为可行方案数目有限，因此经过一一因为可行方案数目有限，因此经过一一比较后，总能求出最好方案，例如，背比较后，总能求出最好方案，例如，背包问题充其量有包问题充其量有22n-1种方式；实际上这种种方式；实际上这种方法是不可行。方
5、法是不可行。8假设有假设有3535件物品，计算机每秒能件物品，计算机每秒能比较比较1000010000个方式，那么要比较完个方式，那么要比较完223434种方式，大约需要种方式，大约需要2020天！天！9先放弃变量的整数性要求，解一个先放弃变量的整数性要求，解一个线性规划问题，然后用线性规划问题，然后用““四舍五入四舍五入””法取整数解，这种方法，只有在变法取整数解，这种方法，只有在变量的取值很大时，才有成功的可能量的取值很大时，才有成功的可能性，而当变量的取值较小时，特别性，而当变量的取值较小时，特别是是00--11规划时，
6、往往不能成功。规划时，往往不能成功。10可行域可行域OABDOABD内整数点，放弃整数要求后，最优内整数点，放弃整数要求后，最优解解B(9.2,2.4)ZB(9.2,2.4)Z0=58.8=58.8，，而原整数规划最优而原整数规划最优解解I(2,4)ZI(2,4)Z0=58=58，，实际上实际上BB附近四个整点附近四个整点(9,2)(10,2)(9,3)(10,3)(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。都不是原规划最优解。x25DI(2,4)43B(9.2,2.4)21x1O12345678910A1
7、1x2maxz=5x+8x612ts..x+x≤65．．．．．12．．oP．．5x+9x≤45．．．．．12．．．．．x,x≥0且为整数91206Zmaxx1去掉整数限制后，可行域为点（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最优解12假如能求出可行域的假如能求出可行域的““整点凸包整点凸包””（包含所有整（包含所有整点
8、的最小多边形点的最小多边形OEFGHIJOEFGHIJ），），则可在此凸包上则可在此凸包上求线性规划的解，即为原问题的解。但求求线性规划的解，即为原问题的解。但求““整整点凸包点凸包””十分困难。十分困难。x25DI(2,4)4JI3HB(9.2,2.4)2G1Fx1O123
