《2013参考数学建模常用方法：整数规划资料.ppt》由会员分享，可在线阅读，更多相关《2013参考数学建模常用方法：整数规划资料.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 整整 数数 规规 划划1整数规划的基本概念整数规划的基本概念2分枝定界法解整数规划分枝定界法解整数规划3规划规划4.4.指派问题的解法指派问题的解法第一节第一节 概概 述述 人人们们探探讨讨某某些些线线性性规规划划问问题题，有有时时必必须须把把全全部部或或部部分分决决策策变变量量限限制制为为整整数数。这这样样的的线线性性规规划划问问题题，通通常常称称为为整整数数规规划划。作作为为线线性性规规划划的的特特殊殊情情况况，整整数数规规划划也也有有最最小小化化和和最最大大化化之之别别。此此外外，整整数数规规划划还还可可以以分分成成纯纯整整数数规规划划和和混混整整数数规规划划。二二者者的的
2、区区别别在在于于：前前者者的的决决策策变变量量必必定定全全全全部部部部取取取取整整整整数数数数。而而后后者者的的决决策策变变量量只只只只是是是是部部部部分取整数分取整数分取整数分取整数。例例例例1 1 某某医医药药公公司司现现有有两两个个制制药药厂厂A1和和A2，三三个个销销售售店店B1、B2 和和 B3。公公司司打打算算由由两两个个拟拟建建的的制制药药厂厂A3 和和 A4 中中选选择择一一个个，来来兴兴建建新新厂厂。各各销销售售店店每每周周药药品品需需求求量量见见表表2-1。各各制制药药厂厂每每周周药药品品产产量量和和每每箱箱药药品品运运费费见见表表2-2。新新厂厂投投产产后后，估估计计每每
3、周周的的操操作作费费（含含折折旧旧费费）：A3 是是100元元，A4 是是120元元。在在两两个个拟拟建建的的制制药药厂厂中，应当选择哪个呢？中，应当选择哪个呢？销售店销售店 需求量（箱需求量（箱/周）周）B1 50 B2 60 B3 30 产量产量制药厂制药厂 (箱箱/周周)运资运资(元元/箱箱)B1 B2 B3 A1 50 3 2 3 A2 70 10 5 8 A3 20 1 3 10 A4 20 4 5 3表表 21表表 22 设设设设：制制药药厂厂Ai 每每周周运运到到销销售售店店Bj 的的药药品品为为xij 箱（箱（i=1,2=1,2，3 3，4 4；j=1=1，2 2，3 3）；）
4、；解解：建立数学模型建立数学模型建立数学模型建立数学模型 两个老厂两个老厂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+5x4
5、2+3x43（A4每周的运费）每周的运费）+100 u（A3每周的操作费）每周的操作费）+120 v（A4每周的操作费）每周的操作费）(1)(1)u 和和 v 全是全是 01 变量：变量：约束条件：约束条件：x11+x 12+x13 50 x21+x 22+x23 70 x31+x 32+x33 20 u x41+x 42+x43 20 vu,v=0,1(2)(2)由由 A3 和和 A4 选择一个来兴建新厂：选择一个来兴建新厂：u+v=1(3)(3)每个制药厂每周运到各销售店的药品不会超每个制药厂每周运到各销售店的药品不会超过其产量：过其产量：(4)每每个个销销售售店店每每周周药药品品的的需需
6、求求量量能能够够得得到到各各制制药药厂的充分供应：厂的充分供应：（5）药品箱数一定取非负值：）药品箱数一定取非负值：xij 0 x11+x21+x31+x41=50 x12+x22+x32+x42=60 x13+x23+x33+x43=30例例1的数学模型为：的数学模型为：Min y=3x11+2x12+3x13+10 x21+5x22+8x23+x31+3x32+10 x33+4x41+5x42+3x43+100u+120vx11+x 12+x13 50 x21+x 22+x23 70 x31+x 32+x33 20u x41+x 42+x43 20vx11+x21+x31+x41=50 x
7、12+x22+x32+x42=60 x13+x23+x33+x43=30 xij0 (i=1,2,3,4;j=1,2,3)u,v=0,1 本数学模型本数学模型属于最小化属于最小化混整数规划混整数规划 例例2 某某医疗器械厂生产医疗器械厂生产A1和和A2两种产品。出两种产品。出 厂前，每种产品均须经过两道工序：先用机器厂前，每种产品均须经过两道工序：先用机器B1 制造，后由机器制造，后由机器B2包装。每台产品的利润和加工包装。每台产品的利润和加工 时间见表时间见表2-3。在下周内，机器。在下周内，机器B1和和B2分别可以分别可以 使用使用45小时和小时和6小时。问怎样安排下周的生产任小时。问怎样
8、安排下周的生产任 务，才能使所获利润最大？务，才能使所获利润最大？解：解：建立数学模型建立数学模型建立数学模型建立数学模型设：设：在下周产品在下周产品A1和和 A2分别生产分别生产 x1 合和合和 x2 合，合，所获利润为所获利润为 y 百元。例百元。例2的数学模型为：的数学模型为：产产 品品 利利 润润（百元（百元/合）合）加工时间（小时加工时间（小时/合）合）B1B2A1551A2891表 2-3最大化最大化纯纯整数整数规划规划其中：其中：“xk 为整数为整数”,称为整数条件。称为整数条件。一般地，可把整数规划的数学模型写为：一般地，可把整数规划的数学模型写为：整数规划问题及其数学模型一律
9、简称为整数整数规划问题及其数学模型一律简称为整数规划；整数规划删去整数条件之前和之后，分别规划；整数规划删去整数条件之前和之后，分别称为称为原整数规划原整数规划原整数规划原整数规划和和相应线性规划相应线性规划相应线性规划相应线性规划。按按照照四四舍舍五五入入的的规规则则，使使相相应应线线性性规规划划的的最最优优解解整整数数化化，在在通通常常情情况况下下，不不能能作作为为原原整整数数规规划的最优解。这可以从两个方面来说明：划的最优解。这可以从两个方面来说明：其其一一、相相应应线线性性规规划划的的最最优优解解化化整整后后，已已经经不不是是原原整整数数规规划划的的可可行行解解，当当然然也也就就不不可
10、可能能是是它它的最优解。的最优解。其二、相应线性规划的最优解化整后，虽然其二、相应线性规划的最优解化整后，虽然是原整数规划的可行解，但是有可能不是它的最是原整数规划的可行解，但是有可能不是它的最优解。优解。例例2 2是最大化纯整数规划，其相应线性规划为：是最大化纯整数规划，其相应线性规划为：下面求解这个相应线性规划。我们采用图解法。下面求解这个相应线性规划。我们采用图解法。并且最优解是：并且最优解是：(x x1 1,x x2 2)=（2.25,3.752.25,3.75）。按照四舍五入的规则，按照四舍五入的规则，将这个最优解整数化，就得到：将这个最优解整数化，就得到：(x x1 1,x x2
11、2)=（2 2，4 4）。它对应于它对应于点点D，而点而点D却位于可行域却位于可行域R 之外，因此之外，因此,D D（2 2，4 4）不是例不是例2 2的的可行解。从而，可行解。从而，D D（2 2，4 4）也不可能是例也不可能是例2 2的最优解。容易断定，的最优解。容易断定，点点 A A（0 0，5 5）才是例才是例2 2的最优解。的最优解。图解法图解法:相应线性规划的可行域相应线性规划的可行域R为图中的四边形为图中的四边形OABC，5x1+9 x2=45x1+x2=6B(2.25,3.75)D(2,4)x2ox19C(6,0)RA最优解最优解A(0,5)n整数规划常用的解法是整数规划常用的
12、解法是分枝定界法分枝定界法和和割平面法割平面法。一旦遇到仅含两个决策变量的情况，可以采用一旦遇到仅含两个决策变量的情况，可以采用图解法图解法，其计算方法与线性规划图解法大同小，其计算方法与线性规划图解法大同小异，就不再赘述。异，就不再赘述。n 求解整数规划不宜采用枚举法。求解整数规划不宜采用枚举法。第二节第二节 分分 枝枝 定定 界界 法法n分分枝枝定定界界法法可可以以用用来来求求解解纯纯整整数数规规划划和和混混整整数数规规划划，它它是是整整数数规规划划的的常常用用解法。解法。n 分枝定界法可以划分为三步。现就每分枝定界法可以划分为三步。现就每 一步的主要特征、理论依据和具体作一步的主要特征、
13、理论依据和具体作 法说明如下：法说明如下：第一步第一步 第第第第一一一一步步步步的的的的具具具具体体体体作作作作法法法法是是是是：首首先先，删删去去整整整整数数数数条条条条件件件件，把把原原整整数数规规划划化化化化成成成成相相相相应应应应线线线线性性性性规规规规划划划划。其其次次，求求求求解解解解相相相相应应应应线线线线性性性性规规规规划划划划。最最后后，如如果果相相应应线线性性规规划划的的最最优优解解也也是是原原整整数数规规划划的的最最优优解解，那那么么整整个个计计算算过过程程即即告告结结束束；否否则则，便转入第二步。便转入第二步。实实现现放放宽宽之之后后，能能够够得得到到三三个个结结论论：
14、原原整整数数规规划划的的可可行行域域真真真真包包包包含含含含于于于于相相应应线线性性规规划划的的可可行行域域。不不失失一一般般性性，单单就就最最大大化化问问题题而而言言（下下同同），原原整整数数规规划划的的最最优优值值不不不不大大大大于于于于相相应应线线性性规规划划的的最最优优解解。若若相相应应线线性性规规划划的的最最优优解解满满足足原原整整数数规规划划的的整整数数条条件件，则则它也是原整数规划的最优解。它也是原整数规划的最优解。主要特征就是主要特征就是放宽放宽放宽放宽。指通过删去整数条件，把原整。指通过删去整数条件，把原整数规划化成数规划化成相应线性规划相应线性规划相应线性规划相应线性规划。
15、第二步第二步 主主要要特特征征是是分分分分枝枝枝枝。从从相相应应线线性性规规划划的的最最优优解解中中，任任意意选选择择一一个个不不满满足足原原整整数数规规划划整整数数条条件件的的决决策策变变量量xj=bj。以以使使相相应应线线性性规规划划增增加加一一个个约约束束条条件件；x xj j小小小小于于于于b bj j的的的的最最最最大大大大整整整整数数数数（或或x xj j大大大大于于于于b bj j的的的的最最最最小小小小整整整整数数数数），因因而而得得到到两两个个新新的的线线性性规规划划，称称为为分分枝枝。其其中中每每个新的线性规划，统称为个新的线性规划，统称为枝枝。经过分枝之后，就有如下结论：
16、原整数规划的经过分枝之后，就有如下结论：原整数规划的可行域可行域真包含于真包含于真包含于真包含于两枝可行域的并集。原整数规划的两枝可行域的并集。原整数规划的最优解最优解不大于不大于不大于不大于两枝最优值的最大值。两枝最优值的最大值。第二步的具体作法是第二步的具体作法是第二步的具体作法是第二步的具体作法是：先列出两枝各自的数学先列出两枝各自的数学模型，后计算每枝的最优解和最优值。模型，后计算每枝的最优解和最优值。第三步第三步 主主要要特特征征就就是是定定定定界界界界，由由各各枝枝的的最最优优值值中中选选最最大大值值，称称为为定定界界。而而该该最最大大值值，称称为为界界界界。最最优优值值称称为界的
17、枝，称为为界的枝，称为界枝界枝界枝界枝。完成定界之后，即可得到这样的结论：若界枝完成定界之后，即可得到这样的结论：若界枝的最优解满足原整数规划的最优条件，则它也是的最优解满足原整数规划的最优条件，则它也是原整数规划的最优解。原整数规划的最优解。第三步的具体做法为第三步的具体做法为第三步的具体做法为第三步的具体做法为：进行定界，找出界枝。：进行定界，找出界枝。若界枝的最优解就是原整数规划的最优解，则计若界枝的最优解就是原整数规划的最优解，则计算过程便告结束；否则，回到第二步。算过程便告结束；否则，回到第二步。解解：它它是是例例2 2的的数数学学模模型型，并并且且属属于于最最大大化化纯纯整整数数规
18、规划划。为为便便于于叙叙述述，我我们们将将其其记记作作A。现在利用分枝定界法求解之。现在利用分枝定界法求解之。例例3 利用分枝定界法求解：利用分枝定界法求解：A放宽：放宽：由由A得到相应线性规划，记作得到相应线性规划，记作B。采取图解法或单纯形法，求得采取图解法或单纯形法，求得B的的最优解（最优解（x1,x2）=（2.25,3.75）最优值最优值 ymax=41.25。B B的最优解不满足的最优解不满足A的整数条件，所以的整数条件，所以它并非它并非A的最优解。的最优解。分分分分枝枝枝枝：由由B的的最最优优解解中中，选选择择决决策策变变量量x2=3.75，按按照既定的原则写出照既定的原则写出B的
19、两枝：的两枝：把它们依次记作把它们依次记作B B1 1和和B B2 2。解解B B1 1得：最优解（得：最优解（x1 1，x2 2）=（3 3，3 3）,最优值最优值 ymaxmax=39=39解解B B2 2得：最优解（得：最优解（x1，x2 2）=（1.8,41.8,4）,最优值最优值 ymaxmax=41=41B1B2 B x1=2.25x2=3.75y=41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41x23x24 已完成的求解过程和所得到的计算结果可用已完成的求解过程和所得到的计算结果可用框图来表示，见下图。框图来表示，见下图。定定定定界界界界：由
20、由图图可可知知。界界为为max 39，41 =41。于于是是界界枝枝是是B2。但但是是，B2的的最最优优解解不不满满足足A的的整整数数条条件件，从从而而它它不不是是A的的最最优解。因此，应当再次分枝。优解。因此，应当再次分枝。第第第第二二二二次次次次分分分分枝枝枝枝：由由B2的的最最优优解解中中，选选择择决决策策变变量量 x1=1.8，写写出出B2的两枝：的两枝：解解B21得：最优解（得：最优解（x1，x2）=（1，4），），最优值最优值ymax=40.不难判断，不难判断，B22无可行解。无可行解。B21B22 至此，已完成的求解过程和所得到的计算结果运用框图来至此，已完成的求解过程和所得到的
21、计算结果运用框图来表示，如图所示：表示，如图所示：B x1=2.25 x2=3.75 y=41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41 B21 x1=1 x2=40/9 y=365/9 B22 无无 可可 行行 解解x23x24x11x12第三次分枝：第三次分枝：第三次分枝：第三次分枝：解解B211得：最优解（得：最优解（x1,x2）=（1,4）,最优值最优值 ymax=37。解解B212得：最优解（得：最优解（x1,x2）=（0,5）,最优值最优值 ymax=40。B212 B211第二次定界：第二次定界：第二次定界：第二次定界：由上图可知，界为由上
22、图可知，界为max 39，365/9 =365/9。界枝为界枝为B21.因为因为B21最优解不满足最优解不满足A的整数条件，不是的整数条件，不是A的最优解。的最优解。由由B21最优解中，选择变量最优解中，选择变量把把B21分成两枝：分成两枝：现现在在，已已完完成成的的求求解解过过程程和和所所得得到到的的计计算结果见下图：算结果见下图：B x1=2.25 x2=3.75 y=41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41 B21 x1=1 x2=40/9 y=365/9 B22 无无 可可 行行 解解x2 3x2 4x1 1x1 2B211x1=1x2=4
23、y=37B212x1=0 x2=5y=40 x2 5x2 4 第第三三次次定定界界：由由上上图图可可知知，界界为为max 39,37,40 =40.所所以以，界界枝枝是是B212。由由于于B212的的最最优优解解满满足足A的的整整数数条条件件，它它一一定定也也是是A的的最最优优解解。于于是，原整数规划的最优解为：是，原整数规划的最优解为：（x1，x2）=（0，5），），最优值最优值 ymax=40。例例3是是一一个个利利用用分分枝枝定定解解法法求求解解纯纯整整数数规规划划问题，其基本步骤也适用于混整数规划问题。问题，其基本步骤也适用于混整数规划问题。A 1A 2A 3A 4A 5A 6A 7A
24、 8 需需 要要 量量（根）（根）钢钢 管管 数数（根）（根）2.9211100001002.1021032101001.510130234100料头料头长度（米）长度（米）0.10.3 0.901.10.20.81.4 例例4 某卫生防疫站准备做某卫生防疫站准备做100套钢架。每套钢架均套钢架。每套钢架均由长为由长为2.9米、米、2.1米和米和1.5米的钢管各一根所组成。已米的钢管各一根所组成。已知原料长知原料长7.4米。如何下料方能使原料最省？米。如何下料方能使原料最省？解：解：原料的下料方式如下表。原料的下料方式如下表。设按照方式设按照方式 Aj下料的原料有下料的原料有 xj 根（根（j
25、=1，2，8）；所所用用原原料料为为 y 根根。于于是是，本本下下料问题的数学模型是：料问题的数学模型是：这是最小化纯整数规划，利用分枝定界法解之。这是最小化纯整数规划，利用分枝定界法解之。采采取取单单纯纯形形法法来来求求解解。可可知知最最优优解解（x1 1，x2 2，x3 3，x4 4，x5 5，x6 6，x7 7，x8 8）=（4040，2020，0 0，0 0，0 0，3030，0 0，0 0）。由由于于它它是是整整数数解解，它它必必定定也也是是例例4 4的的最最优优解解。这这表表明明，只只须须采采用用下下料料方方式式A A1 1、A A2 2 和和 A A6 6，而而且且所所用用原原料
26、料分分别别为为4040根根、2020根根和和3030根根，可可使使所所用用原原料料最最省省。例例4 4的的求求解解过过程程说说明明，当当利利用用分分枝枝定定界界法法时时，有有时时仅仅仅仅经经历历“放放宽宽”这这一一步步，就就能能够求得最优解。够求得最优解。放宽放宽放宽放宽:得到相应线性规划为：得到相应线性规划为：例例4还还可可以以采采用用另另外外的的目目标标函函数数，即即100套套钢架的料头总长度为钢架的料头总长度为 y 米。数学模型是：米。数学模型是：#小小 结结一、整数规划的基本概念一、整数规划的基本概念二、分枝定界法解整数规划二、分枝定界法解整数规划纯整数规划、混整数规划纯整数规划、混整数规划分枝定界法分三步：分枝定界法分三步：第一步第一步第一步第一步 放宽放宽放宽放宽第二步第二步第二步第二步 分枝分枝分枝分枝第三步第三步第三步第三步 定界定界定界定界