资源描述
,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,其次章 整 数 规 划,1,整数规划的基本概念,2,分枝定界法解整数规划,3规划,4.指派问题的解法,第一节 概 述,人们探讨某些线性规划问题，有时必需把全部或部分决策变量限制为整数。这样的线性规划问题，通常称为整数规划。作为线性规划的特殊状况，整数规划也有最小化和最大化之别。此外，整数规划还可以分成纯整数规划和混整数规划。二者的区分在于：前者的决策变量必定全部取整数。而后者的决策变量只是部分取整数。,例1 某医药公司现有两个制药厂A1和A2，三个销售店B1、B2 和 B3。公司准备由两个拟建的制药厂A3 和 A4 中选择一个，来兴建新厂。各销售店每周药品需求量见表2-1。各制药厂每周药品产量和每箱药品运费见表2-2。新厂投产后，估计每周的操作费（含折旧费）：A3 是100元，A4 是120元。在两个拟建的制药厂中，应当选择哪个呢？,销售店 需求量（箱/周）,B,1,50,B,2,60,B,3,30,产量,制药厂 (箱/周),运资(元/箱),B,1,B,2,B,3,A,1,50 3 2 3,A,2,70 10 5 8,A,3,20 1 3 10,A,4,20 4 5 3,表 21,表 22,设：,制,药厂,A,i,每周运到销售店,B,j,的药品为,x,ij,箱（,i,=1,2，3，4；,j,=1，2，3）；,解,：,建立数学模型,两个老厂A1 和 A2 及一个新厂A3 和 A4 每周的,总费用为 y 元。新厂厂址的选择应当确保 y 达到,最小值。于是，y 是目标函数，xij、u 和 v 都是,决策变量。它们之间的关系可以表述为：,y =3x11+2x12+3x13（A1每周的运费）,+10 x21+5x22+8x23（A2每周的运费）,+x31+3x32+10 x33（A3每周的运费）,+4x41+5x42+3x43（A4每周的运费）,+100 u（A3每周的操作费）,+120 v（A4每周的操作费）,(1),u,和,v,全是,0,1,变量：,约束条件：,x,11,+,x,12,+,x,13,50,x,21,+,x,22,+,x,23,70,x,31,+,x,32,+,x,33,20 u,x,41,+,x,42,+,x,43,20 v,u,v=0,1,(2)由,A,3,和,A,4,选择一个来兴建新厂：,u+v=1,(3)每个制药厂每周运到各销售店的药品不会超过其产量：,(4),每个销售店每周药品的需求量能够得到各制药厂的充分供应：,（5）药品箱数确定取非负值：,x,ij,0,x,11,+,x,21,+,x,31,+,x,41,=50,x,12,+,x,22,+,x,32,+,x,42,=60,x,13,+,x,23,+,x,33,+,x,43,=30,例,1,的数学模型为：,Min,y,=3,x,11,+2,x,12,+3,x,13,+10,x,21,+5,x,22,+8,x,23,+,x,31,+,3,x,32,+10,x,33,+4,x,41,+5,x,42,+3,x,43,+100u+120v,x,11,+,x,12,+,x,13,50,x,21,+,x,22,+,x,23,70,x,31,+,x,32,+,x,33,20u,x,41,+,x,42,+,x,43,20v,x,11,+,x,21,+,x,31,+,x,41,=50,x,12,+,x,22,+,x,32,+,x,42,=60,x,13,+,x,23,+,x,33,+,x,43,=30,x,ij,0,(i=1,2,3,4;j=1,2,3),u,v=0,1,本数学模型属于最小化,混整数规划,例2 某医疗器械厂生产A1和A2两种产品。出,厂前，每种产品均须经过两道工序：先用机器B1,制造，后由机器B2包装。每台产品的利润和加工,时间见表2-3。在下周内，机器B1和B2分别可以,运用45小时和6小时。问怎样支配下周的生产任,务，才能使所获利润最大？,解：,建立数学模型,设：,在下周产品,A,1,和,A,2,分别生产,x,1,合和,x,2,合，所获利润为,y,百元。例,2,的数学模型为：,产 品,利 润,（百元/合）,加工时间（小时/合）,B,1,B,2,A,1,5,5,1,A,2,8,9,1,表,2-3,最大化,纯,整数,规划,其中：“,x,k,为整数”,称为整数条件。,一般地，可把整数规划的数学模型写为：,整数规划问题及其数学模型一律简称为整数规划；整数规划删去整数条件之前和之后，分别称为,原整数规划,和,相应线性规划,。,依据四舍五入的规则，使相应线性规划的最优解整数化，在通常状况下，不能作为原整数规划的最优解。这可以从两个方面来说明：,其一、相应线性规划的最优解化整后，已经不是原整数规划的可行解，当然也就不行能是它的最优解。,其二、相应线性规划的最优解化整后，虽然是原整数规划的可行解，但是有可能不是它的最优解。,例2是最大化纯整数规划，其相应线性规划为：,下面求解这个相应线性规划。我们接受图解法。,并且最优解是：(x1,x2)=（2.25,3.75）。依据四舍五入的规则，将这个最优解整数化，就得到：(x1,x2)=（2，4）。它对应于点D，而点D却位于可行域R 之外，因此,D（2，4）不是例2的可行解。从而，D（2，4）也不行能是例2的最优解。简洁断定，点 A（0，5）才是例2的最优解。,图解法,:,相应线性规划的可行域,R,为图中的四边形,OABC，,5,x,1,+9,x,2,=45,x,1,+,x,2,=6,B,(2.25,3.75),D,(2,4),x,2,o,x,1,9,C,(6,0),R,A,最优解,A,(0,5),整数规划常用的解法是分枝定界法和割平面法。一旦遇到仅含两个决策变量的状况，可以接受图解法，其计算方法与线性规划图解法大同小异，就不再赘述。,求解整数规划不宜接受枚举法。,其次节 分 枝 定 界 法,分枝定界法可以用来求解纯整数规划和混整数规划，它是整数规划的常用解法。,分枝定界法可以划分为三步。现就每,一步的主要特征、理论依据和具体作,法说明如下：,第一步,第一步的具体作法是：首先，删去整数条件，把原整数规划化成相应线性规划。其次，求解相应线性规划。最终，假如相应线性规划的最优解也是原整数规划的最优解，那么整个计算过程即告结束；否则，便转入其次步。,实现放宽之后，能够得到三个结论：原整数规划的可行域真包含于相应线性规划的可行域。不失一般性，单就最大化问题而言（下同），原整数规划的最优值不大于相应线性规划的最优解。若相应线性规划的最优解满足原整数规划的整数条件，则它也是原整数规划的最优解。,主要特征就是,放宽,。指通过删去整数条件，把原整数规划化成,相应线性规划,。,其次步,主要特征是分枝。从相应线性规划的最优解中，随意选择一个不满足原整数规划整数条件的决策变量xj=bj。以使相应线性规划增加一个约束条件；xj小于bj的最大整数（或xj大于bj的最小整数），因而得到两个新的线性规划，称为分枝。其中每个新的线性规划，统称为枝。,经过分枝之后，就有如下结论：原整数规划的可行域,真包含于,两枝可行域的并集。原整数规划的最优解,不大于,两枝最优值的最大值。,其次步的具体作法是：先列出两枝各自的数学模型，后计算每枝的最优解和最优值。,第三步,主要特征就是,定界,，由各枝的最优值中选最大值，称为,定界,。而该最大值，称为,界,。最优值称为界的枝，称为,界枝,。,完成定界之后，即可得到这样的结论：若界枝的最优解满足原整数规划的最优条件，则它也是原整数规划的最优解。,第三步的具体做法为：进行定界，找出界枝。若界枝的最优解就是原整数规划的最优解，则计算过程便告结束；否则，回到其次步。,解：,它是例2的数学模型，并且属于最大化纯整数规划。为便于叙述，我们将其记作,A,。现在利用分枝定界法求解之。,例,3,利用分枝定界法求解：,A,放宽：,由,A,得到相应线性规划，记作,B,。,实行图解法或单纯形法，求得B的,最优解（x1,x2）=（2.25,3.75）,最优值 ymax=41.25。,B,B的最优解不满足A的整数条件，所以它并非A的最优解。,分枝：由B的最优解中，选择决策变量x2=3.75，依据既定的原则写出B的两枝：,把它们依次记作,B,1,和,B,2,。,解,B,1,得：最优解（,x,1,，,x,2,）=（3，3）,最优值,y,max,=39解,B,2,得：最优解（,x,1,，,x,2,）=（1.8,4）,最优值,y,max,=41,B,1,B,2,B,x,1,=2.25,x,2,=3.75,y,=41.25,B,1,x,1,=3,x,2,=3,y,=39,B,2,x,1,=1.8,x,2,=4,y,=41,x,2,3,x,2,4,已完成的求解过程和所得到的计算结果可用框图来表示，见下图。,定界：由图可知。界为max 39，41 =41。于是界枝是B2。但是，B2的最优解不满足A的整数条件，从而它不是A的最优解。因此，应当再次分枝。,其次次分枝：由B2的最优解中，选择决策变量 x1=1.8，写出B2的两枝：,解B21得：最优解（x1，x2）=（1，4），最优值ymax=40.不难推断，B22无可行解。,B,21,B,22,至此，已完成的求解过程和所得到的计算结果运用框图来表示，如图所示：,B,x,1,=2.25,x,2,=3.75,y,=41.25,B,1,x,1,=3,x,2,=3,y,=39,B,2,x,1,=1.8,x,2,=4,y,=41,B,21,x,1,=1,x,2,=40/9,y,=365/9,B,22,无 可,行 解,x,2,3,x,2,4,x,1,1,x,1,2,第三次分枝：,解,B,211,得：最优解（,x,1,x,2,）,=,（,1,4,）,最优值,y,max,=37,。,解,B,212,得：最优解（,x,1,x,2,）,=,（,0,5,）,最优值,y,max,=40,。,B,212,B,211,其次次定界：由上图可知，界为max 39，365/9=365/9。界枝为B21.因为B21最优解不满足A的整数条件，不是A的最优解。,由,B,21,最优解中，选择变量,把,B,21,分成两枝：,现在，已完成的求解过程和所得到的计算结果见下图：,B,x,1,=2.25,x,2,=3.75,y,=41.25,B,1,x,1,=3,x,2,=3,y,=39,B,2,x,1,=1.8,x,2,=4,y,=41,B,21,x,1,=1,x,2,=40/9,y,=365/9,B,22,无 可,行 解,x,2,3,x,2,4,x,1,1,x,1,2,B,211,x,1,=1,x,2,=4,y,=37,B,212,x,1,=0,x,2,=5,y,=40,x,2,5,x,2,4,第三次定界：由上图可知，界为max 39,37,40 =40.所以，界枝是B212。由于B212的最优解满足A的整数条件，它确定也是A的最优解。于是，原整数规划的最优解为：,（x1，x2）=（0，5），最优值 ymax=40。,例3是一个利用分枝定解法求解纯整数规划问题，其基本步骤也适用于混整数规划问题。,A,1,A,2,A,3,A,4,A,5,A,6,A,7,A,8,需 要 量,（根）,钢 管 数（根）,2.9,2,1,1,1,0,0,0,0,100,2.1,0,2,1,0,3,2,1,0,100,1.5,1,0,1,3,0,2,3,4,100,料头长度（米）,0.1,0.3,0.9,0,1.1,0.2,0.8,1.4,例4 某卫生防疫站准备做100套钢架。每套钢架均由长为2.9米、2.1米和1.5米的钢管各一根所组成。已知原料长7.4米。如何下料方能使原料最省？,解：,原料的下料方式如下表。,设依据方式 Aj下料的原料有 xj 根（j=1，,2，8）；所用原料为 y 根。于是，本下料问题的数学模型是：,这是最小化纯整数规划，利用分枝定界法解之。,实行单纯形法来求解。可知最优解
展开阅读全文