运筹学chapt3.ppt

1、1.在第三章整数线性规划问题及其解法中，在前一章讨论的线性规划问题中，决策变量限于不能取负值的连续值，即它们可以是正分数或正小数。然而，在经济管理的许多实际问题中，决策变量只有当它们是非负整数时才具有实际意义。寻找整数的最优解的问题叫做整数规划。知识产权，也称为线性约束和函数，是整数线性规划(简称ILP)。根据变量取整数的情况，整数规划可以分为：(1)纯整数规划，其中所有变量取整数；(2)混合整数规划，其中一些变量取整数，一些变量取实数；(3)0-1整数规划，其中所有变量取0或1。整数规划常用的算法有分枝定界法、截平面法、隐式枚举法和求解0-1的匈牙利法。2，3.1整数线性规划模型的建立，实例

2、1 P72 A公司有5个投资项目可供选择，所需投资金额及预期收益如下。因为每个项目之间都有一定的联系，所以必须从A、C和E中选择一个，并且只能选择一个；b和d之间只有一个选择。因为C和D密切相关，所以C的实施必须以D的实施为基础。该单位共筹集了15万元，询问应该投资哪些项目以获得最大的预期回报。3。解决方案：决策变量：假设，目标函数：最大期望收益，约束条件：投资限制条件6x1 4x2 2x3 4x4 5x515，必须且仅需要在项目A、C和E中选择一个：x1 x3 x5=1，项目C的实施应以项目D: x3 x4的实施为基础，并且必须且仅需要在项目B和D: X2x4之间选择一个。数学模型如下：4，

3、示例2服务部门在每个时间段(一小时为一个时间段)需要的服务员数量如下根据规定，服务员一班连续工作八小时(即四个时间段)，要求安排服务员的工作时间，以尽量减少服务部门的服务员总数。解决方案：在时间J开始的时候去工作的服务员的数量是xj。由于在时间J开始时上班的服务员将在时间J结束时下班，所以决策变量只需要考虑X1、X2、X3、X4和X5。这个问题的数学模型是：5。例3(固定成本问题)有三种资源用于生产三种产品，资源量和单个产品的可变成本。需要制定一个生产计划来使总收入最大化。解决方案：总收入等于销售收入减去生产上述产品的固定和可变费用的总和。建模的主要困难是我们不能确切知道某个产品是否提前生产，

4、所以我们不能确定相应的固定费用是否发生。让我们借助0-1个变量来解决这个困难。6.假设xj是第j个乘积的输出，j=1，2，3。那么，问题的整数规划模型如下：m是一个大正数；7.案例4(作业排序问题)使用4台机床加工3个产品。每个产品的机床加工顺序和产品I在机床J上的加工工时aij如下表所示。由于某种原因，产品2的总加工时间不应超过d，因此需要确定机床上每个产品的加工方案，以便在最短的时间内加工完所有产品。解决方法：让xij代表产品I在机床j上开始加工的时间(i=1，2，3；J=1，2，3，4)问题的整数规划模型将在下面逐步列出。1.同一产品在不同机床上加工顺序的限制。对于同一产品，在下一台机床

5、上加工的开始时间不能早于在上一台机床上加工的约束时间，因此应该有：8，产品3:2。如果开始的加工尚未完成，每台机床对不同产品的加工顺序会限制一台机床工作。对于机床1，有两个加工顺序。或者先加工产品1，然后加工产品2；反之亦然。其他三种机床的情况相似。为了适应两个互斥的约束，引入了0-1个变量，9，那么在每个机床上加工的产品的顺序可以通过以下四组约束来保证：3。产品2的加工时间限定为x21，加工时间为x24 a24，因此应为：4。目标函数的建立将所有产品的结束时间设置为W，因为三个产品的处理时间分别为x14 a14、x24 a24、x33 a33。因此，所有产品的实际加工结束时间为：这被转换为线

6、性表达式：10。案例5:一个城市的消防指挥部将整个城市分为11个防火分区，有4个消防站。下图显示了每个防火区和消防站的位置，其中、代表消防站，1、2、3、11代表防火区。根据历史数据，确认每个消防站能够在事先规定的允许时间内扑灭其负责区域内的火灾。图中的虚线表示哪个消防站负责每个区域(如果没有虚线连接，则表示没有责任)。现在，总部已经提出了在同时负责全市消防的前提下，是否可以减少消防站的数量。如果是，应该关闭哪一个？11，解决方案：顺序，可以为每个防火区域列出以下约束：从上面的约束：x1，x3，x4必须是1，x2可以是0或1，这样消防站可以关闭而不影响任务的执行，12，因此，ILP数学模型的一

7、般形式是：找到一组变量X1，X2，XN，make，0-1变量的应用将在下面进一步解释。假设现有的M资源投资N个可选择项目的数学模型如下：找到一组决策变量x1，x2，xn，使13，1。选择可选项目；(1)如果必须只选择前k(kn)个可选项目中的一个，在(3.2)中添加新的约束；(2)如果可用，(3)如果应从k(kn)项目中至少选择一项投资，则在(3.2): 14中添加新的约束。(4)如果项目j的投资必须以项目I的投资为基础，在(3.2): xjxi中增加新的约束。(5)如果项目I和项目j同时存在。然后在(3.2)中添加一个新的约束：Xj=Xi (ij) 2。可用资源的选择(1)如果对第R个资源br和第T个资源bt的投资是互斥的，即只允许对资源br和bt中的一个进行投资，那么(3.2)中的第R和第T个约束可以重写为：15，其中显然，当y=0时，公式是原始的第R个约束条件，它具有约束函数。此