现代物流运筹学 沈家骅 24320第4章整数规划简介

《现代物流运筹学 沈家骅 24320第4章整数规划简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章整数规划简介学习方法了解整数规划的数学模型的特点。掌握整数规划的分枝定界法。学会指派问题及其求解方法。•整数规划（IntegerLinearProgramming,ILP）可分成线性部分和整数部分，并常常把整数规划作为线性规划的特殊部分。•在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求解答必须是整数。•例如，所求解是机器的台数、工人的人数或装货的车数、场址的选定等，都必须部分或者全部满足整数要求，这样的问题称为整数线性规划问题，简称为整数规划，记为ILP。•整数规划的应用范围是极其广泛的，它不仅在工业、工程设

2、计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码、经济分析等方面也有新的应用。整数规划的数学模型4.1分枝定界法4.2指派问题4.3指派问题的Excel处理4.44.1整数规划的数学模型4.1.1案例•例4.1某厂生产A、B两种产品，这两种产品的单位利润分别为25元和40元。•生产每种产品都需要3道工序，其各种产品的工时（单位：时）、每一工序每周可供使用的时间如表4.1所示，问工厂如何安排生产，使其获利最大？•解设、分别是A产品和B产品的周产量，z为这两种产品每周总的利润。•根据题意，建立模型如下：•其中，max是英文maximiz

3、e（最大化）的缩写。•由于所有变量要求取整数，故称它为全整数规划问题。•例4.2我们要做投资决策，就是对几个潜在的投资方案做出选择，若投资决策可以是在可行的几个厂址中做出选择；或设备购置的选择；或对一组研究和发展项目做出决定。•在这类决策问题中，问题是在“要”或者“不要”之间进行选择，我们可以令决策变量是整数，且只取0或1，分别表示不投资或者投资。•假定cj代表第j项投资得到的收益，aij是用于第j项投资的第i项资源的数量，bi为第i种资源的限制，则上述问题可列成下式：•由于所有的变量都只能取0或1，所以，这样的整数规划问题称为0—1规划。4.1

4、.2整数规划数学模型的一般形式•整数规划数学模型一般可以表示如下：•式中opt即optimize（最优化）的缩写，根据问题要求不同，可以表示为max（最大化）或min（最小化）。•整数规划可分为以下3种类型。（1）纯整数规划（pureintegerlinearprogramming）（2）混合整数规划（mixedintegerlinerprogramming）（3）0—1型整数规划（zero—oneintegerlinerprogramming）•整数规划特点如下。（1）原线性规划有最优解，当自变量限制为整数后，其整数规划解出现下述情况。①原线性

5、规划最优解全是整数，则整数规划最优解与线性规划最优解一致。②整数规划无可行解。③有可行解（当然就存在最优解），但最优解值一定不会优于原线性规划的最优值。（2）整数规划最优解不能按照实数最优解简单取整而获得。•例4.5已知整数规划问题：•解如果先不考虑整数条件，得到如下线性规划问题（称为松弛问题）：图4.1例4.5•在B点得到最优解：•再考虑整数条件：•如将x2凑成整数，x2= 2，则点（2,2）落在可行域外，不是可行解；若将x2凑成整数1，但点（2,1）不是最优解。•因为当x1= 2，x2= 1，得到z= 7，而当x2= 0,x2= 2，得到z=

6、 10，显然点（0,2）比点（2,1）更好。•因此不能简单地将松弛问题的最优解舍入化整（如四舍五入），得出整数规划的最优解。•通过仔细分析，从图4.1可知，整数规划问题的可行解集是相应的线性规划问题的可行域内的整数格子点，它是一个有限集。•因此，我们可以用另一种方法进行讨论，即将所有的可行解依次代入目标函数，比较所得的目标函数值的大小，从而得到最优解。•这个方法称为完全枚举法。•如上例有整数可行解和目标函数值：•经过比较，所以得到最优解x1= 0,x2= 2，目标函数最优值z= 10。4.2分枝定界法•整数规划，除少数可以用完全枚举法或用线性规划

7、的单纯形法直接求解，一般整数规划必需寻找新的求解方法。•常用的求解整数规划的方法有分枝定界法、割平面法等，对于特别的0—1规划问题的求解，可以采用隐枚举法和匈牙利法。•这里我们仅介绍整数规划的分枝定界法，它也可以用于求解混合整数规划问题和0—1规划问题。4.2.1案例•例4.6求解下述整数规划。•解（1）首先，我们注意到式（4-1）的可行解集为图4.2中阴影部分内的整数格子点组成的集合，暂时不考虑整数限制条件（5）。图4.2例4.6•解相应的线性规划（1）～（4），即式（4-1）的松弛问题LP：•得最优解x1= 2.25,x2= 3.75,z0=

8、 41.25（2）其次，我们注意到线性规划式（4-2）的解x1、x2具有小数，但这两个变量在式（4-1）中都必须是整数，那就是说必须把小