整数规划案例

整数规划案例目录TOC\o"1-5"\h\z\o"CurrentDocument"例1固定费用问题 1\o"CurrentDocument"例2选择性约束条件 1\o"CurrentDocument"例3可行域描述问题 2\o"CurrentDocument"例4最优分配问题 2\o"CurrentDocument"例5选址问题 2\o"CurrentDocument"例6排序问题 3\o"CurrentDocument"例7利润分段线性问题 5\o"CurrentDocument"例8可靠性问题 5\o"CurrentDocument"例9装配线平衡问题 6\o"CurrentDocument"例10货物列车编组计划问题 7例1固定费用问题工厂准备生产Al、A2、A3三种产品。若Aj产品投产，无论产量大与小，都需要一笔固定费用dj（例如装夹具的设计制作费用）。而每生产一件产品，其利润为cj,试问固定费用这个因素如何体现在模型中而使总利润最大?（其它约束条件暂不列入）解设产品Aj的产量为xj,又设0一1变量yi=l（当xj>0）,0（否则）于是，目标函数为max仁clxl+c2x2+c3x3・dlyl-d2y2・d3y3例2选择性约束条件某工厂生产第j种产品的数量为Xj,j=l,2,3。其使用的材料在材料甲及乙中选择一种。材料消耗的约束条件分别为2x1+5x24-6x3W180及4x1+3x2+7x3^240（其它资源约束未列出），试问这类选择性约束条件如何体现在模型中？解引进0一1变量y：y=0（选择材料甲），0（否则）。这样，“或此或彼”相互排斥的约束条件就可化成下列两个约束条件：2xl+5x2+6x3W180+My,4x1+3x2+7x3W240+M（1-y）,其中M是充分大的正数。可以看出，当y=0时，第二个约束变成4xl+3x2+7x3W240+M,由于M是充分大的正数，所以这个约束条件自动满足而不起作用，而第一个约束为2xl+5x2+6x3W180，这意味着选择材料甲；反之，当y=l时，第二个约束起作用，第一个约束变为2xl+5x2+6x3W180+M不起作用，这意味着选择材料乙。因此，借助0一1变量，材料选择的两种可能性就同时包括在一个模型中了。一般地，假定在某种情况下要在P个约束条件中至少要选择q个约束条件得到满足，那么，我们引进P个0-1变量yi,则选择性的约束条件问题就化为.……例3可行域描述问题如何把图中的阴影部分所表示的可行域用联立的线性约束条件来描述?例4最优分配问题现有四部车床Ai(1=1,...,4)和四个零件Bj(j=l,...,4)，车床Ai加工零件Bj所需时间ti(j小时)由下表给出。问如何安排生产计划，使每部车床加工一个零件、一个零件由一部车床加工,且全部零件加工完成的时间最早(假定四部车床同时开始加工)。试建立整数规划模型。 B1 B2 B3B4A13541A27213A33451A46752例5选址问题现准备从Al、A2、A3三个地点选择二处开设工厂，它们每月的产量ai(i=l,2,3)分别至多为70、80和90个单位，每月的经营费用di(与产量无关)分别为100、90和120o有三家客户Bl、B2和B3,他们每月的需求量bj(j=l,2,3)分别为40、80和45个单位。Ai至Bj的单位运价cij如表，问如何选址，使每月经营和运输费用最低?试建立整数规划模型。解设yi=l（选地点Ai开设工厂），0（否则），又设xij为在地点Ai处开设工厂时从Ai至客户Bj的运量。显然，有yl+y2++y3=2。若在Ai处不开设工厂，则Ai至Bj的运量应为零；若在Ai处开设工厂，贝U每个月Ai至Bj的运量之和不超过Ai处开设工厂的产量ai,写成约束条件就成为：xil+xi2+xi3Waiyi,i=l,2,3。又客户Bj的需求量必须得到满足，所以有xlj+x2j+x3j=bj,j=l,2,3o每月的费用f为：则本问题的数学模型为：例6排序问题用编号为1号、2号、3号、4号的四种机床生产三种产品1号、2号、3号。这三种产品的工艺路线及工序加工时间如下表所示。工艺路线j号机床加工时间（小时）12341al a3 -►a4i号产品2bl土b43c2=3一台机床一次只能加工一个产品。现要求2号产品从开始加工到完成，经历时间不得超过d小时。问如何确定各种产品在机床上的加工顺序，使在最短时间内制成全部产品。试建立整数规划模型。解设xij为I号产品在机床j上开始加工的时间（从零基准点算起，以小时计）。第一组约束条件为要求三种产品都应按照工艺路线的规定顺序来进行加工。例如对1”产品来说，首先是在1”机床上加工，然后依次在3”和4”机床上加工，因此有：类似地,对2”和3”产品，有:zli+口1Wz13, zl3+口3Wzl.,z21+61W卫z2,zz2+62Wz24,z32+龟Wz33。第二组约束条件为一族选择性的约束条件，以保证一台机床一次只能加工一个产品。例如，对于机床1”来说，或者1。产品先于2”产品加工，或者2”产品先于1”产品加工，即应有t或zll+口iWz2L或z21+61Wzll。引进。一1变量y。，上述选择性约束条件就成为：zll+口1WZ21+坷1,'z21+61Wzll+M（l—yl）类似地，借助于O—1变量弛、y。和弘，对2”、3o和4。机床有；z22+62Wz32+Mj,2 'z32+f2Wz22+M（l一弛）zl3+口3Wz33+My3z33+f?Wzl3+M（l—y3）zl'+口4Wz2'+M负z2'+以Wzl.+M（1一执），其中8—0,1,一2,3,4o2”产品从10机床对它开始加工（在zoo时刻）到4”机床将其加工完毕（在z"+64时刻），其经历时间有约束：z2‘+6'—z21W：do三个产品都完工的时间y为：y=max（z…+口"z24+64,z33+c3},我们将它化为线性约束条件yNzl'+口'；yNz2'+机； y\z33+f3。.

昏9拳上所述，得整数规划模型如下例7利润分段线性问题某厂生产甲、乙两种产品，需经过金工和装配两个车间加工，有关数据如表工时定额(小时/件)—产—-品总有效工时田乙车问金工43480装配25500售价(兀/件)300520产品乙无论生产批量大小，每件产品生产成本总为400元。试根据产品甲生产成本的下列两种情况分别建立整数规划模型：(1)产品甲的生产成本分段线性：第1件至第30件，每件成本为200元；第31件至第70件，每件成本为190元；从第71件开始，每件成本为195元。(2)产品甲的产量不超过40件时，每件成本为200元，但若超过40件，则甲的全部产品每件成本都为195元。例8可靠性问题某种仪表由三个部件串联而成。j号部件的可靠性由所组装的元件个数决定每个j号元件的重量和成本由表给出。元件个数ij号部件可靠性12310.60.750.720.750.850.830.80.90.85元件成本重量1号303j号2号4043号506设计过程中，该仪表对三个部件的总重量限制为25,总成本限制为240,问j号部件如何选择j号元件的个数，使仪表的可靠性最大？例9装配线平衡问题若某工厂的产品的装配线由6道工序组成，各工序的加工时间及工序的前后顺序如表工序加工时间紧前工1325322461,3r\524634若这条装配线设若干个工作站。被装配的产品在这些编了号的工作站上流水移动时，每个工作站都要完成一道或几道工序。假设每个工作站加工每个被装配的产品时至多耗时10分钟，问最少应设立几个工作站?每个工作站完成哪些工序？解显然，需要的工作站不会多于4个。这是因为由表4—7可以观察到一个解：工序1、3在一个站上完成，而工序4、5和6各在一个工作站上进行，此时只需4个工作站。fl,在装配线上有工作站-『，删』一.{-『=1,…，4[0,否则，因此，为使工作站数实现最少.目标函数为：min厂=硼1+叫2+叫3+硼I。接下来我们来分析约束条件：第一组约束条件：对工序i来说，它应恰在某一个工作站上完成，为此有矗l+0i2+83+z"=1, i=l,•••,6；第二组约束条件：对工作站—『来说，在该站上完成的各道工序所需时间的总和不得超过10分钟，因此有：321J+5x2j+2x3』+6x,j+8站』+3XsiW10,第三组约束条件：工作站歹若设立，则在此站上完成的工序不会超过6道若不设立，那么就不能将任何工序分派给该站（换句话说，若叫J=0，则所有的z；j=0），从而有：'zlj+z2J+z3j+z',+z5J+z6jW6w』， ，=1,...,4；最后我们来考虑关于各道工序前后顺序这组约束条件：首先考虑工序2应当在工序3之前完成这个要求。若工序3在最后一个工作站4上完成，那显然没有什么问题，因为所有工序都要在此站前完成或就在此站上完成。若工序3分配在工作站3上完成，则工序2就不能分配在工作站4上完成，而必须分配在工作站1、2或3上完成，由此可得它说明，若x33=l,则x21,x22,x23中必有一个变量取值为1,以保证工序2在工序3之前完成。类似地，若工序3分配在工作站2或1上完成，就应分别有：例10货物列车编组计划问题某铁路线路有五个货物列车编组站Al、A2、A3、A4和A5。编组站Ai发往前方各编组站Aj的车辆数aij（或称为车流量）己知，如图4—3所示。若始发站Ai至到达站Aj开行直达列车（