文档介绍：运筹学(IntegerProgramming)整数规划数学模型整数规划典型解法整数规划应用2020/3/1733求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的,而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数,则称为纯整数规划问题;如果只有一部分变量为非负整数,则称之为混合整数规划问题。如果所有的变量都为0-1变量,则称之为0-1规划。4第一节整数规划数学模型一、纯整数规划(pureintegerlinearprogramming)产品资源甲乙现有量A219B5735单台利润65例3-1:某企业利用材料和设备生产甲乙产品,其工艺消耗系数和单台产品的获利能力如下表所示:问如何安排甲、乙两产品的产量,使利润为最大。:设x1为甲产品的台数,x2为乙产品的台数。maxZ=6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整数6二、0-1规划(zero-oneintegerlinearprogramming)例3-2某企业计划在华东、华南、华北、华中、东北、西北、西南七个区域新建工厂。假设每个区域最多只能建设一个工厂,且该工厂只能覆盖本区域的销售。各区域的工厂建设成本见和销售份额见下表。一期建设最多可投入的建设资金为2500万。问该企业应优先建设哪些地区的工厂,使得覆盖的销售份额最大?序号1234567区域华东华南华北华中西南西北东北成本(百万)55261224销售份额(%):设8三、混合整数规划(mixedintegerlinearprogramming)例3-3:某产品有n个区域市场,各区域市场的需求量为bj吨/月;现拟在m个地点中选址建生产厂,一个地方最多只能建一家工厂;若选i地建厂,生产能力为ai吨/月,其运营固定费用为F元/月;已知址i至j区域市场的运价为cij元/吨。如何选址和安排调运,可使总费用最小?解:选址建厂与否是个0-1型决策变量,假设yi=1,选择第i址建厂,yi=0,不选择第i址建厂;计划从i址至区域市场j的运输运量xij为实数型决策变量。9第二节整数规划解法一、舍入化整法为了满足整数解的要求,自然想到“舍入”或“截尾”处理,以得到与最优解相近的整数解。这样做除少数情况外,一般不可行,因为化整后的解有可能超出了可行域,成为非可行解;或者虽是可行解,却不是最优解。不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题对于例3-1的数学模型,不考虑整数约束的最优解:x1*=28/9,x2*=25/9,Z*=293/9舍入化整x1=3,x2=3,Z=33,不满足约束条件5x1+7x2≤35,非可行解;x1=3,x2=2,Z=28,满足约束条件,是可行解,但不是最优解;x1=4,x2=1,Z=29,满足约束条件,才是最优解。10二、穷举整数法对于决策变量少,可行的整数解又较少时,这种穷举法有时是可行的,并且也是有效的。但对于大型的整数规划问题,可行的整数解数量很多,用穷举法求解是不可能的。例如,指派问题。5x1+7x2=352x1+x2=9•(3,3)••••••••••x1x2123125344