《整数规划精美管理》PPT课件

1、整数规划(Integer Programming)，第1节。整数计划的一般形式，例如：实例1工厂，集装箱托运a，每箱体积，重量，获利能力，托运限额等，表51:询问两种商品能发运多少箱并获得最大收益。2，整数编程通用格式，解决方案：委托a，b两种商品x1，x2框，可数学表示：整数编程数学模型，通用格式，根据决策变量提取要求，整数编程可分为纯整数编程，整数编程，混合整数编程，01整数编程。纯整数编程：所有决定变量都需要非负整数。此时引入的松弛变量和其他变量不需要得到整数。完整整数编程：除了所有决策变量都需要非负整数外，系数AIJ和常量bi也需要整数(此时引入的松弛变量和其馀变量也必须为整数)。混合

2、整数编程：只有一些决定变量要求非负整数，其他部分则犯非负实数。01整数编程：所有决定变量只能使用0或1两个整数。整数规划与线性规划的关系，在数学模型方面，整数规划似乎是线性规划的特殊形式。解决方案只需要基于线性编程通过四舍五入找到满足整数要求的解决方案。但是，实际上徐璐差异很大，通过四舍五入得到的解决方案(整数)不一定是最佳解决方案，在某些情况下，生成的解决方案不能保证是整数可行的解决方案。举例说明。示例：整数编程问题如下：首先得到线性编程问题(通常称为平滑问题)，而不考虑整数约束。最佳解决方案x13/2，x2=10/3和z=29/6，x1，x2，3显然，两者都不能是整数编程的最优解。将线性编

3、程问题的可执行域内可能是整数点的约束计划为整数。因此，整数规划问题的可行解集是有限集，如图所示。您可以逐一寻找集合中的整数点，例如、和图表。最大目的函数值是完整枚举方法的最优解。以上范例：其中，(2，2)(3，1)点为最大值，Z=4。目前，常用的解决方案是支管和剖切面方法。对于特殊的01计划问题，使用隐藏的枚举法和匈牙利法。20世纪60年代初期，Land Doig和Dakin等提出了分支和警戒方法。由于该方法灵活，可以用计算机轻松地解决，现在已经成为解决整数编程的重要方法之一。分支和边界法可用于求解纯整数计划和混合整数计划。分支和边界方法的主要想法是首先解决整数规划的伴随规划(整数规划的松弛问

4、题)，如果最优解不满足整数条件，则增加新的约束，缩小可行区域。原始整数编程问题作为两个子计划，分支和子计划的伴随计划通过一系列子计划的伴随计划和持续分离解决。最后得到了原始整数规划问题的整数最优解。考虑分支和边界方法、基本思路、整数问题的整数问题：整数问题的缓解问题：是，公司计划建设两种类型的宿舍。a各占0.25 103m2，乙各占0.4103m2。该公司拥有土地3103m2。计划甲种为8洞，乙种为4洞以下。甲种每种利润10万韩元，乙种20万韩元。该公司要建多少套甲、乙两种宿舍，才是最大的利益？解决方案计划a种宿舍楼，b种宿舍楼，这个问题数学模型：问题是纯粹的整数编程问题。在(1)中，将约束的

5、系数规范化为整数(1)，消除整数条件，使用问题的伴随计划(2)，使用称为问题的简单方法解决问题，得到最佳解决方案和最佳值。1.由于问题的最优解不满足整数条件，因此不是问题的最优解，所以计算了原始问题目标函数值的初始上限。由于可能的域问题的可能域，问题的最佳值不会超过问题的最佳值。也就是说，因为存在，所以可以用作的初始上限。这意味着，通常情况下，如果没有问题的可行解决方案，则问题没有可行的解决方案，计算停止。问题的最佳解决方案是停止问题的整数、条件和计算的问题的最佳解决方案。2.计算原始问题目标函数值的初始下限，如果在问题的约束条件下可以观察到可整数的解决方案，则该目标函数值可以用作问题目标函数

6、值的初始下限，否则初始下限Z=-。您可以指定给定下限的目的。要在解决过程中查找比当前问题更好的原始问题的函数值。在此情况下，明确的可行解决方案X=(0，0)T，Z=0。问题的最佳目标函数值决不小于此值，因此=0， 3。添加约束条件会将问题分为原始问题。如果问题的最佳解决方案不符合整数条件，则选择不符合整数条件的变量。例如，在这个例子中，明确问题的整数最优解只是或，5和6之间不匹配。因此，在部分切削可执行区域时，未裁剪的整数不是可执行的解决方案。可用于添加每个约束条件和剪切部分约束条件。剪切后，分为和两部分。换句话说，问题分为问题和问题两种配置。有关问题、问题和问题的伴随计划，请参阅图2(b)。

7、接下来，将分解为同一问题的两个分支问题称为一对分支。4.单独解决一对分支问题。一般情况下，在解决一个分支问题(伴随计划)时，请注意以下可能的：(a)、(b)、图2、(1)如果没有可行的解决方案，则将检查该分支，该分支不会继续，分支称为“叶”，表示不需要修剪分支，(2)得到整数的最佳解，得到整数的最佳解，分支不再需要分叉，分支也是叶子。(3)得到非整数最优解，如果某个特定分支问题得到不满足整数条件的最优解，则最优解的目标函数值z小于当前下限，该分支不能包含原始问题的整数最优解。这叫“死枝”，必须剪掉。如果此最优解的目标函数值z大于当前下限，则需要继续对该分支进行分支，以确定该分支中的目标函数值是

8、否存在比当前更好的整数最优解。此示例中的问题和问题的模型和解决结果如下：问题、问题、解决方案：解决方案：问题的解决方案是整数最优解决方案，当然是问题的整数可行解决方案，因此可以用整数最优解决方案(即：)修改，问题标识为“叶”。由于不满足整数条件，问题分别增加了约束条件：和。分为两种，建立相应的伴随计划问题、问题、问题和可行的域。请参阅图3。图3，问题解决不了，所以这个问题已经是树叶，调查，问题解决，最佳解决方案，5。上、下、(l)的修正、下修正时间为：每次找到可能的整数的解决方案时，修正、下操作、下原则修正：都会选择迄今为止计算的所有可能的整数解决方案中最大的目标函数值作为最新下限。因此，在使

9、用分支划分方法的牵引过程中，下限继续增加。(2)修改上限的时间是：考虑每次求解一对分支时修改上限，修改上限的原则是：选择了迄今为止所有未分支问题的目标函数值中最大的一个作为新的上限。新的上限必须小于原来的上限。在分支和划分方法的整体解中，上限值继续减小。问题，问题，解决方案是：在此情况下，解决方案是整数解决方案，因此下限为=130，在此情况下，所有非分支问题()的目标函数值中的最大值为父项=130，6。结束条件已修改，所有分支均已确认，或者“树叶”没有可行的解决方案。或者，如果整数解“叶”，或者目标函数值不大于“阈值”枯枝)原始问题的整数最优，也就是目标函数值是阈值的整数解，在这个例子中，解一

10、对分支再次成为叶，因为它是枯枝，所以所有分支()都已确认。因此，已经获得了问题的最佳解决方案：或者公司要建造3套a种宿舍的7个b种宿舍。或5个a，4个b，最大收入。130万元。此示例的解决过程和结果可以用图5描述。问题，问题，问题，问题，问题，结论等于案例4或5。求解混合整数规划的分支和边界方法的计算步骤概括为：如下所示。在第一阶段：中，原整数线性编程问题被称为问题。删除问题的整数条件会伴随计划问题。在步骤2 :中，没有以下可能的：(l)可能的解决方案，没有可能的解决方案，停止计算。(2)满足得到的最优解和问题的整数条件时，最优解也是的最优解，停止计算。(3)得到不满足问题整数条件的最优解。目

11、标函数值为：此时，将问题分支，继续下一步。要知道，(3)得到了不满足问题的整数条件的最优解，并且相应的函数值是。此时，将问题(因此问题)分支，然后继续下一步。步骤3 :确定初始上限和下限，并将其用作上限边界。观察问题的整数可行解，并将目标函数值记录为子边界。如果未观察到，请转到下一步。在步骤4 :中，问题分支。在的最佳解决方案中，选择不满足整数条件的变量。值为：小于最小整数的整数。解决了通过将配置2、约束：两个约束分别添加到问题的约束集而获得的两个分支：问题和每个分支问题。以下可能性：(1)不可分支分支为叶：(2)求出该季度的最优解，并满足满足整数条件。相应最优解的目标函数值作为新的下限，相应

12、的分支也是叶。(3)求出该分支的最优解，求出不满足的整数条件，但如果目标函数不大于当前下限，则该分支必须截断“死枝”。(4)求出不满足整数条件的相应分支的最优解，并且如果相应的目标函数值大于当前子极限，则分支应继续分支，并且如果得到了前三种情况中的一种，则表示该分支已经识别，不再需要分支。解决了一对分支后，如果该对分支指示需要继续分支，则可以首先对目标函数值较大的点执行分支计算。这个分支一直持续到一切都弄清为止。返回并求解目标函数值较小的分支。在步骤6 :中，修改上限、下限、下限，修改下限。只要找到符合整数条件的可能解决方案，就修改下限，选择迄今为止最好的整数可能的解决方案，将相应的目标函数值

13、作为下限，(2)上限：求解每个分支，修改上限值应该是迄今为止没有分支的所有问题的目标函数值中的最大值。如果解决了每个分支对、上、下、分支对，那么在该时间点确定了所有分支，就得到问题的最佳值；如果问题解决了，分支还没有确定，就应该继续分支。阶段4，计算阶段，解决缓解问题，满足要求吗？结束，分支，Y，N，选择分支以解决创建和松弛问题，确定是否为整数解决方案，初始分支为可执行解决方案集，初始边界为无穷大，确定分支集是否为空，Y停止，确定当前最佳解决方案，确定最佳值是否优于当前边界，最佳值为当前边界将当前边界、y、y、N、修剪、N、N、N、N替换为最佳解决方案，以便仅分支整数变量，而不分支非整数变量。

14、如果两个分支都可以具有非整数解，则在得出整数解之前，必须在两侧同时分支，并且可以继续边界过程。许多变量具有整数约束时，分支宽而深。在最坏的情况下，等于组合所有可能的整数解决方案。一般的整数规划问题是未解决的问题之一，只有几个特殊问题的好算法。练习：使用分支和边界方法进行整数编程疑难解答，X11，x12，x22，x23，x12，x13，示例：使用切平面方法进行整数编程疑难解答，解决：松弛变量xxX=(1，3/2) Z=3/2，不是整数最佳解决方案。请看X2所在的行。X2、x3、x4是非负整数，等式右端是整数，()是正数，左端是负数，所以分解系数和常量。示例：有一个剪切公式用作附加约束条件。生成的

15、剖切面条件现在添加松弛变量并将其添加到表中。此时，X1 (2/3，1)，Z=1仍然不是整数解决方案。使用X=(1，1)，Z=1的最佳解决方案将生成的剖切面条件添加到松弛变量，然后添加到表中。在此情况下，最佳表格为x=(1，1)、z=1。这也是对原始问题的最佳解决方案。看上面的故障排除过程，该算法也称为分数双切面算法，因为表中有分数元素，并且算法始终保持双可能性。将(2)(3)替换为(1)，并为以下问题创建剪切表达式：例如：使用剖切面法求解数规划问题，初始表、最优表、李莞问题的最优解中，x1、x2是非整数解，在上表中：将系数和常数分解为整数和非负真分数之和。上述公式只能考虑一个解决。考虑公式右端最大真分数的公式，表明更快地发现了所需的剖切面约束。以上两个公式右端的真分数相同，可以作为选择考虑。现在，选择第二个公式，并将偏折向右移动。也就是说，在引入松弛变量S1后，获得：此约束条件已添加到上表中，并继续求解。获得、整数编程的最优解，即整数最优解。整数计划有两种最佳解决方案：X=(0，4)、Z=4或X=(2，2)、Z=4。0-1整数编程，问题，1，是，公司计划在东部，西部-南部地区建立城市部门。建议的7个位置(点)Ai可供选择。允许您从A1、A2、A3的3个地点中选择2个或更多地点。在西部区域，至少选取A4、A5两点中的一点。在南区，至少选择A6、A7两点中的一点。如果选择Ai