整数规划的数学模型及解的特点

整数规划的数学模型及解的特点整数规划IP(integerprogramming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP。松弛问题(slackproblem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integerlinearprogramming)。一、整数线性规划数学模型的一般形式njjjxcZ1min)max(或中部分或全部取整数njnjijijxxxmjnixbxats,...,,...2,1,...,2,10),(.211整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pureintegerlinearprogramming)：指全部决策变量都必须取整数值的整数线性规划。有时，也称为全整数规划。2、混合整数线性规划(mixedintegerlinerprogramming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。3、0—1型整数线性规划(zero—oneintegerlinerprogramming)：指决策变量只能取值0或1的整数线性规划。1解整数规划问题且为整数0,3121451149max21212121xxxxxxxxz0—1型整数规划0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的且为整数0,5210453233max2121212121xxxxxxxxxxz变量xi称为0—1变量，或称为二进制变量。0—1型整数规划中0—1变量作为逻辑变量(logicalvariable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。为否或无如果决策为是或有如果决策iixi01一、0—1型整数规划的典型应用问题例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410解：引入0—1变量xi,xi=1表示应携带物品i，,xi=0表示不应携带物品i7,...,2,1,10254212625510481418152076543217654321ixxxxxxxxxxxxxxxnaxzi或上述问题就是一个标准的0-1整数规划问题，解得：X*=(1,1,1,1,0,1,1)’Z*=81例2：集合覆盖和布点问题某市消防队布点问题。该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min内赶到现场。据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。地区1地区2地区3地区4地区5地区6地区1地区2地区3地区4地区5地区6010162827201002432171016240122721283212015252717271501420102125140解：引入0—1变量xi,xi=1表示在该区设消防站，,xi=0表示不设01111111min6526545434362121654321或ixxxxxxxxxxxxxxxxxxxxxxxz解得：X*=(0,1,0,1,0,0)’Z*=2二、特殊约束的处理1.矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只能两者取一或，例如下面两个约束)2(0)()1(3)(xfxf先不等式同向处理，原式可化为：)4(0)()3(0)(3xfxf，再引入一个0－1变量y,及一个很大的正数M，)6()1()()5()(3yMxfMyxfy=0时，(5)与(1)相同，(6)自然满足，实际上不起作用y=1时，(6)与(2)相同，(5)自然满足，实际上起作用对于形似)0()(aaxf，可以用以下一对约束代替axfaxf)()(约束同向处理，改为()()fxafxa引入0—1变量后，()()(1)fxaMyfxaMy2.多中选一的约束模型希望在下列几个约束中，只能有一个约束有效：)1(),...,2,1(0)(nixfi引入n个0－1整数变量yi,i=1,2,…,n.则上式可改写为：yi=0时，（2）自然满足，此时约束不起作用yi=1时，约束起作用。而和式保证了在0—1整数变量中有一个且也只有一个取值1，其余取0值。若希望有k个约束有效，只需将(3)改为kyyyn...213、某市为方便学生，拟在新建的7个居民小区增设若干所学校。已知各备选校址代号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应建多少所学校？对应的校址代号是哪些？表1备选校址ABCDEF小区编号1，5，71，2，51，3，52，4，53，64，6解：对每一个学校定义一个变量jx1，当某居民小区可由第j个学校负责jx＝0，当某居民小区不可由第j个学校负责)3(1...)2(),...,2,1()1()(21niiyyyniyMxf则对于第1个小区：1231xxx对于第2个小区：241xx对于第3个小区：351xx对于第4个小区：461xx对于第5个小区：12341xxxx对于第6个小区：561xx对于第7个小区：11xMinz=61jjX解得：*1,0,0,1,1,0TX*Z=3例2有两个相互排斥的约束条件244521xx或453721xx。为了统一在一个问题中，引入10变量y，则上述约束条件可改写为：10)1(453724452121或yMyxxyMxx其中M是充分大的数。例3约束条件01x或8005001x可改写为108005001或yyxy3.1.3关于固定费用的问题（FixedCostProblem）在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。例5某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。所以必须全面考虑。今设有三种方式可供选择，令jx表示采用第j种方式时的产量；jc表示采用第j种方式时每件产品的变动成本；jk表示采用第j种方式时的固定成本。为了说明成本的特点，暂不考虑其它约束条件。采用各种生产方式的总成本分别为0,00,jjjjjjxxxckP当当3,2,1j.在构成目标函数时，为了统一在一个问题中讨论，现引入10变量jy，令.00,0,1时种生产方式，即当不采用第时，种生产方式，即当采用第jxjjxjjy于是目标函数)()()(min333322221111xcykxcykxcykz（3）（3）式这个规定可表为下述3个线性约束条件：3,2,1,jMyxyjjj（4）其中是一个充分小的正常数，M是个充分大的正常数。（4）式说明，当0jx时jy必须为1；当0jx时只有jy为0时才有意义，所以（4）式完全可以代替（3）式。例8求解下列指派问题，已知指派矩阵为1096109532485724679278310283，求最小指派问题。数学模型为：Minz=3*x11+8*x12+2*x13+10*x14+3*x15+8*x21+7*x22+…+5511*ijijjiax……+9*x51+10*x52+6*x53+9*x54+10*x55X11+x12+x13+x14+x15=1……5111..5ijjxiX51+x52+x53+x54+x55=1X11+x21+x31+x41+x51=1…..X15+x25+x35+x45+x55=1Xi,j=0,1Lingo程序为：model:sets:row/1..5/:;col/1..5/:;link(row,col):a,x;endsetsdata:a=3821038729764275842359106910;enddatamin=@sum(link(i,j):a(i,j)*x(i,j));@for(row(i):@sum(col(j):x(i,j))=1);@for(col(j):@sum(row(i)|i#le#2:x(i,j))+@sum(row(i)|i#ge#3:x(i,j))=1);end篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高和擅长位置见下表：出现阵容应满足以下条件：中锋只能有一个上场；x1+x2=1至少有一名后卫；x6+x7+x8=1如1号和4号上场，则6号不出场；y=x1+x4,ify=2x6=0X1=x62号和6号至少保留一个不出场。X2+x6=1应当选择哪5名队员上场，才能使出场队员平均身高最高？\\\\队员身高（米）擅长位置11.92中锋21.90中锋31.88前锋41.86前锋51.85前锋61.83后卫71.80后卫81.78后卫公司生产A、B、C三种产品，售价分别为12元、7元和6元。生产每单位A需要1小时技术服务、10小时直接劳动、3千克材料；生产每单位B需要2小时技术服务、4小时直接劳动、2千克材料；生产每单位C需要1小时技术服务、5小时直接劳动、1千克材料；现在最多能提供100小时技术服务、700小时直接劳动、400千克材料；生产成本是生产量的非线性函数，如下所示：产品A产品B产品C产量单位成本（元）0~4040~100100~150150以上10987产量单位成本（元）0~505~100100以上643产量单位成本（元）0~100100以上54要求建立一个总利润最大的生产计划数学模型。设产品A的产量为1x，且1111040yx0，其他，121140100yx0，其他，1311100150yx0，其他，1411150yx0，其他，设产品B的产量为2x，且：2121050yx0，其他，222150100yx0，其他，2321100yx0，其他，设产品C产量为3x，且：31310100yx0，其他，3231100yx0，其他，设总利润为：y1112131412122232313231231231231112131421222331321111121131112(10987)7(643)6(54)100,10425700,324001,1,1040,40100,100150..Maxyyyyyxyyyxyyxxxxxxxxxxyyyyyyyyyxyxyxystxy3242212223233313123150,050,50100,100,0100,100,0(1,2,3)0(1,2,3)0(1,2,3)0(1,2)jjjjxyxyxyxyxyxjyjyjyj或1，或1，或12某钻井队要从以下10个可供选择的井位中确定5个钻井采油，目的是使总的钻井费用最小。若10个钻井位代号为1210,,,SSS,相应的钻控费用为1210,,,ccc，并且井位的选择要满足