北邮运筹学ch51整数规划数学模型.ppt

一个规划问题中要求部分或全部决策变量是整数,则这个规划称为整数规划。当要求全部变量取整数值的,称为纯整数规划;只要求一部分变量取整数值的,称为混合整数规划。如果模型是线性的,称为整数线性规划。本章只讨论整数线性规划。、,可选用一个逻辑变量x,当x=1表示投资,x=0表示不投资;,当变量xij=1表示安排第i人去做j工作,xij=0表示不安排第i人去做j工作。逻辑变量也是只允许取整数值的一类变量。Date运筹学北京邮电大学【】某人有一背包可以装10公斤重、。他准备用来装甲、乙两种物品,每件物品的重量、体积和价值如表5-1所示。问两种物品各装多少件,所装物品的总价值最大?表5—1物品重量(公斤/每件)体积(m3/每件)价值(元/每件)【解】设甲、乙两种物品各装x1、x2件,则数学模型为:()Date运筹学北京邮电大学如果不考虑x1、x2取整数的约束(称为()的松弛问题),线性规划的可行域如图5—1中的阴影部分所示。图5-1Date运筹学北京邮电大学用图解法求得点B为最优解:X=(,),Z=。由于x1,x2必须取整数值,实际上整数规划问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合,但(4,7)、(4,8)(3,8)都不是可行解,(3,7)虽属可行解,但代入目标函数得Z=33,并非最优。实际上问题的最优解是(5,5),Z=35。即两种物品各装5件,总价值35元。由图5-1知,点(5,5)不是可行域的顶点,直接用图解法或单纯形法都无法求出整数规划问题的最优解,因此求解整数规划问题的最优解需要采用其它特殊方法。还有些问题用线性规划数学模型无法描述,但可以通过设置逻辑变量建立起整数规划的数学模型。Date运筹学北京邮电大学【】,假设此人还有一只旅行箱,最大载重量为12公斤,。背包和旅行箱只能选择其一,建立下列几种情形的数学模型,使所装物品价值最大。(1)      所装物品不变;(2)      如果选择旅行箱,载重量和体积的约束为解:此问题可以建立两个整数规划模型,但用一个模型描述更简单。引入0-1变量(或称逻辑变量)yi,令i=1,2分别是采用背包及旅行箱装载。Date运筹学北京邮电大学(1)由于所装物品不变,式()约束左边不变,整数规划数学模型为(2)      由于不同载体所装物品不一样,数学模型为Date运筹学北京邮电大学式中M为充分大的正数。从上式可知,当使用背包时(y1=1,y2=0),式(b)和(d)是多余的;当使用旅行箱时(y1=0,y2=1),式(a)和(c)是多余的。上式也可以令:同样可以讨论对于有m个条件互相排斥、有m(≤m、≥m)个条件起作用的情形。Date运筹学北京邮电大学【】企业计划生产2000件某种产品,该种产品可利用A、B、C设备中的任意一种加工。已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量(件)如下表所示,试建立总成本最小的数学模型。设备生产准备结束费(元)生产成本(元/件)限定最大加工数(件)A10010600B3002800C20051200Date运筹学北京邮电大学【解】设xj表示在第j(j=1,2,3)种设备上加工的产品数量,其生产费用为:式中Kj是同产量无关的生产准备费用(即固定费用),cj是单位产品成本。设0-1变量yj,令目标函数为Date运筹学北京邮电大学式中是一个特殊的约束条件,显然当xj>0时,yj=1,当xj=0时,为使Z极小化,只有yj=0才有意义。用QSB软件求解得到:X=(0,800,1200),Y=(0,1,1),Z=,此问题称为0-1整数规划问题,简称0-1规划。Date运筹学北京邮电大学