Ch3整数规划ppt课件

1、，3.1整数规划的数学模型，3.2纯整数规划的解，3.3 01二进制整数规划的解，第3章整数规划的整数规划，运筹学，3.1整数规划的数学模型，21.07.2020，一个规划问题要求一些或所有的决策变量是整数，那么这个规划称为整数规划。当所有变量都需要取整数值时，这叫做纯整数规划；如果只要求部分变量取整数值，这就叫做混合整数规划。如果模型是线性的，它被称为整数线性规划。本章只讨论整数线性规划。许多实际规划问题属于整数规划问题。1.变量是人数、机器和设备的数量或产品的数量等。所有这些都必须是整数。2.对于是否投资某个项目的决策问题，可以选择一个逻辑变量X。当x=1表示投资时，x=0表示无投资；3.

2、人员的合理安排。当变量xij=1表示第一个人被安排做J工作时，xij=0表示第一个人没有被安排做J工作。逻辑变量也是一种只允许整数值的变量。3.1整数规划的知识产权数学模型，21.07.2020，例3.1某人有一个背包，可以装10公斤和0.025立方米的物品。他准备使用甲和乙。每个物品的重量、体积和价值如表3-1所示。询问两个项目中每个项目装载了多少件，装载项目的总值是最大的。表3-1，解决方案如果甲、乙分别配有x1和x2件，数学模型为：(3.1)、3.1知识产权数学模型。21.07.2020。如果不考虑x1和x2取整数的约束(称为(3.1)的松弛问题)，3.1整数规划的知识产权数学模型，图3

3、-1。21.07.2020，而点b是用图解法得到的最优解：X(3.57，7.14)，Z35.7。由于x1和x2必须取整数值，实际上，整数规划问题的可行解集只是图的可行域中的那些整数点。当使用舍入方法时，需要比较四种组合，但是(4，7)、(4，8)、(3，8)不是可行解，并且(3，7)是可行解，但是代入目标函数的Z=33不是最优的。实际上，这个问题的最优解是(5，5)，Z=35。也就是说，这两件物品每件装5件，总价值35元。从图31可以看出，点(5，5)不是可行域的顶点，整数规划问题的最优解不能用图解法或单纯形法直接求得，因此需要用其它特殊方法来求解整数规划问题的最优解。仍有一些问题不能用线性规

4、划的数学模型来描述，但整数规划的数学模型可以通过设置逻辑变量来建立。3.1整数规划的知识产权数学模型，21.07.2020，示例3.2在示例3.1中，假设此人还有一个最大负载为12千克、体积为0.02立方米的行李箱。您只能选择背包和行李箱中的一个，并建立以下情况的数学模型，以最大化装载物品的价值。(一)内容不变；(2)如果您选择一个行李箱，您只能装载两个项目，C和D，值分别为4和3。负载能力和容量的限制如下。解决方案对于这个问题，可以建立两个整数规划模型，但是用一个模型来描述更简单。01变量(或逻辑变量)yi的引入，使I=1和2分别由背包和手提箱装载。3.1整数规划的知识产权数学模型，21.0

5、7.2020，(1)整数规划的数学模型是，(2)整数规划的数学模型是，3.1不同载波的IP的数学模型。从上述公式可以看出，当使用背包时(y1=1，y2=0)，公式(b)和(d)是多余的；当使用手提箱时(y1=0，y2=1)，公式(a)和(c)是多余的。上面的公式也可以得出：也可以讨论有m个互斥的条件和m(m，m)个有效的条件。，3.1整数规划的知识产权数学模型，21.07.2020，(1)当右常数是k值之一时，类似于公式(3.2)的约束条件是，(2)当m组条件中有k(m)组时，类似于公式(3.3db)的约束条件被写入，这里yi=0=1当约束条件是 符号时，右常数项应该是，(3)当m组条件中的k

6、(m)有效时，约束条件被写入，3.1知识产权的数学模型。21.07.2020，示例3.3尝试引入01变量将以下问题表示为一般线性约束(1)x1 x26或4x1 6x210或2x1 4x220 (2)如果x15，则x20，否则x28 (3)x2取0，1，3，5，7，解决方案 (1)三个约束中只有一个有效。3.1整数规划的知识产权数学模型，或，21.07.2020，(3)右边的常数是五个值之一，(3.1整数规划的知识产权数学模型，(2)两套约束条件中只有一套起作用，(21.07.2020，例3.4企业计划生产4000件某一产品，该产品可以自己加工，也可以在外部加工中以任何形式生产。众所周知，每种产

7、品的固定成本、生产该产品的单件成本以及每种生产形式的最大加工量(件)限值如表32所示。如何安排产品的加工以使总成本最小化，表32，解决方案让xj成为第一个j(j=1，2，3 3.1知识产权的数学模型，21.07.2020，其中kj为固定成本，cj为单位产品成本，设置01变量yj，let，数学模型为，3.1知识产权的数学模型，(3.4)，它处理xj和yj之间的逻辑关系。例3.4是WinQSB软件解决的混合整数规划问题：x (0，2000，2000) t，y (0，1，1) t，Z=25400。21.07.2020，作业：课本p751，2，3，4，5，5。3.1整数规划的知识产权数学模型，下一节：

8、求解纯整数规划，3.2求解纯整数规划，21.07.2020，分支定界法步骤，1。寻找整数规划松弛问题的最优解；2.如果松弛问题的最优解满足整数要求，则得到整数规划的最优解，否则，进入下一步；3.任意选择一个非整数解的变量xi，并在松弛问题中加入约束条件xixi和xixi 1，形成两个新的松弛问题，称为分支。新松弛问题具有以下特点：当原问题是寻找最大值时，目标值是分支问题的上界；当原问题是寻找最小值时，目标值是分支问题的下界；4.检查所有分支机构的解决方案和目标函数值。如果一个分支的解是整数，并且目标函数值大于(最大)等于其他分支的目标值，则其他分支将被切断，并且不进行计算。如果存在非整数解，并

9、且目标值大于(最大)整数解的目标值，则有必要继续分支并再次检查，直到获得最佳解。3.2.1求解纯整数规划的分枝定界法，3.2求解纯整数规划。21.07.2020，示例3.5使用分支定界法求解示例5.1，解首先找到相应的松弛问题(记录为LP0):并使用图解法获得最优解X (3.57)。3.2求解纯整数规划，21.07.2020，8.33，10，松弛问题LP0的最优解是x=(3.57，7.14)，z0=35.7，x1，X2 3.2求解纯整数规划，10，10，x1，x2，O，A，B，C，LP1，LP2，3，4，LP13360 x=(3，7.6)，Z1=34.8，Z1，X1，x2，O，A，B虽然lp1

10、中的x1不是整数Z5Z，因此，lp5的最优解是原始整数规划上述分支过程可由下图表示：lp0:x=(3.57，7.14)，z0=35.7，lp1:x=(3，7.6) Z1=34.8，lp2:x=(4，6.5) z2=35.5，x13 lp43360 x=(4，6) Z4=34，LP 53360 x=(5，5) Z5=35，x14，21.07.2020，让纯整数规划，松弛问题，最优解，3.2求解纯整数规划。21.07.2020，将被分成一个整数和一个非负真分数的和：那么，方程的两边都是整数，3.2求解纯整数规划。21.07.2020，添加松弛变量si，该变量称为以xi为源线(源线)的切割平面，或分

11、数切割公式，或R.E.Gomory约束方程。在松弛问题的最优表中加入Gomory约束，用对偶单纯形法计算，如果最优解中有非整数解，继续切割，直到所有解都是整数解。然后，3.2求解纯整数规划，21.07.2020，例如，行x1:移位项：让，添加松弛变量s1，类似地，对于行x2，有：3.2求解纯整数规划，21.07.2020，示例3.6使用切割平面方法解决以下知识产权问题，解决方法变量约束的松弛，相应的松弛问题是，3.2求解纯整数规划。21.07.2020，在加入松弛变量x3和x4后，用单纯形法求解，并得到最优表3。最优解X(0)(5/2，15/4)不是IP的最优解。选择表3-3的第一行(或第二行

12、)作为源行，3.2求解纯整数规划，表3-3。21.07.2020，将其重写为，在分离系数后，添加松弛变量x5以获得高莫雷约束方程，并将公式(3.8)作为约束条件添加到表中。如表34所示，3.2求解纯整数规划。21.07.2020，最优解x (1) (3，3)，最优值Z21。所有变量都是整数，X(1)是整数的最优解。如果不是整数解，需要继续切割并重复上述计算过程。3.2求解纯整数规划，表34，如果原始切割方程的松弛变量仍然是对偶单纯形法中的基本变量，则松弛变量所在的列在被转换成单位向量后可以被移除并再次切割。21.07.2020，家庭作业：课本P76 T 7，8，1。理解分支和定界的含义。选择适

13、当的“分支”生出“分支”3。掌握何时停止生“枝”4。了解切割平面方法的基本原理。分离源行，找出蛾摩里约束6。向最优表中添加蛾眉约束。3.2求解纯整数规划，下一节：01求解规划、3.3 01求解规划、21.07.2020，3.3.1用隐式枚举法求解01整数规划，隐式枚举法的步骤：1。用目标函数值Z0找到任何可行解，2。当原始问题最大化时，添加一个约束，当获得最小值时，将上述公式更改为小于或等于约束。3.列出所有可能的解决方案，并首先检查每个可能解决方案的公式(*)。如果满足其他约束条件，然后进行检查，则认为不可行。如果满足所有约束，则认为解决方案是可行的，并获得目标值。4.3.3 01编程解决BIP。21.07.2020，示例3.7使用隐式枚举法解决以下BIP问题，解决方案 (1)不难看出，当所有变量等于0或1的任意组合时，第一个约束条件得到满足，这意味着第一个约束条件不具有约束力，并且是冗余的，从约束条件中删除。还可以观察到x0 (1，0，0，1)是一个可行解，而目标值Z011是BIP问题的下界，因此构造了一个约束：原来的BIP问题变成3.3 01规划解求解BIP。21.07.2020，(2)列出了变量值0和1的组合，共244个。首先，判断公