整数规划(Integer Programming,IP)是线性规划的一个扩展形式,旨在找到使线性函数最小化(或最大化)的决策变量取整数值的最优解。与线性规划不同的是,整数规划中的决策变量被限制为整数而不是连续的。
其形式与线性规划问题的表现形式一样。
整数规划问题的求解相对于线性规划更加困难,因为整数变量的离散性质使得搜索空间更大,可能导致求解变得非常耗时。
分支定界法是一种在运筹学中常用的算法,主要用于解决整数规划问题。整数规划问题通常涉及到需要决策的变量只能取整数值,这样的问题在实际应用中十分常见,比如物流配送的路线规划、生产计划的排程等。
初始线性规划问题(松弛问题)
首先,我们将整数规划问题转换成线性规划问题,这个转换过程称为松弛。在松弛问题中,我们忽略整数限制,允许解是连续的。比如,如果原问题要求变量 必须是整数,那么在松弛问题中 可以是任意实数。
我们用线性规划的方法解这个松弛问题,得到一个初始的最优解。这个解是当前我们所知的上界(如果是最大化问题)或下界(如果是最小化问题)。
分支
接着我们进行分支。在这一步,我们选择一个决策变量,这个变量在松弛问题的最优解中不是整数。然后,我们围绕这个变量的值创建两个新的子问题:一个子问题中这个变量的上界被限制为它的整数部分;另一个子问题中这个变量的下界被限制为它的整数部分加一。
比如,如果我们的变量 在松弛问题中的解是 ,那么我们就创建两个新的问题:在一个问题中 ,在另一个问题中 。
解子问题
然后,我们分别解这两个新创建的子问题。这些子问题是原问题的更小的线性规划问题,但是它们比原问题更接近整数规划问题。
剪枝
在解子问题的过程中,我们可能会发现一些子问题实际上是不可能有更好解的。这可能是因为子问题的最优解仍然不是整数,或者即使是整数,它的目标函数值也不如我们已知的最优解。这时,我们可以放弃这些子问题,不再进一步搜索它们。这个过程被称为剪枝。
更新最优解
如果在解子问题时我们找到了一个整数解,并且它的目标函数值比我们已知的最优解更好,我们就更新当前最优解。
循环
接下来,我们重复分支、解子问题、剪枝和更新最优解这些步骤。每次我们都会进一步缩小搜索范围,直到我们找到最优解或者确定没有更好的解存在为止。
通过以上步骤,分支定界法能够有效地找到整数规划问题的最优解。这个方法的关键在于能够合理地选择分支变量,并且有效地进行剪枝,以减少不必要的计算和搜索。
初始线性规划问题
我们首先要处理的是整数规划问题。但是,直接解决整数规划可能非常复杂。因此,我们先忽略整数的要求,把问题转化为一个线性规划问题,这个过程称为“松弛”。然后,我们用线性规划的方法(比如单纯形法)来求解这个松弛问题,得到一个最优解。这个解可能是包含小数的,也就是说,可能不是原问题的有效解,因为原问题要求解必须是整数。
检查最优解
拿到松弛问题的最优解后,我们需要检查这个解是否已经满足整数的要求。如果这个解的所有变量都是整数,那么恭喜,这个解就是我们整数规划问题的最优解,我们的任务就完成了。
添加割平面
如果松弛问题的最优解包含了非整数,那么我们需要构造一个割平面来“剔除”这个非整数解。割平面是一个线性不等式,它的目的是将非整数解从当前的解空间中剪掉。这个割平面需要精心设计,以确保它不会剪掉任何整数解,只剪掉那些我们不想要的非整数解。
具体来说,我们首先要检查这个松弛解是否已经满足整数条件了。如果满足,那么这个解就是我们要找的整数解。但如果不满足,比如说我们得到了一个解 ,其中 和(或) 不是整数,我们就需要构造一个割平面。
这个割平面其实就是一个新的不等式,它可以帮助我们“剪裁”掉原来解空间中的一部分,这个被剪掉的部分包含了我们不想要的非整数解。而割平面的形式一般是这样的:
我们需要确定合适的 、 和 的值,使得以下两个条件都满足:
更新线性规划问题
接下来,我们将新添加的割平面纳入原线性规划问题中,形成一个新的线性规划问题。这个新问题的解空间会比原来的小,因为我们已经剔除了一部分空间。然后,我们再次用线性规划方法解这个新问题,得到一个新的最优解。
重复步骤
我们重复步骤2到步骤4,每次都检查最新得到的解是否是整数解。如果不是,就继续添加新的割平面来剔除非整数解。通过这样不断收紧解空间的方法,我们的目标是逐渐逼近一个满足整数要求的最优解。
结束条件
这个过程会一直进行下去,直到我们找到一个整数解,或者根据某些停止准则判断再继续添加割平面也不会得到更好的整数解。到那时,我们就可以宣布找到了整数规划问题的最优解或一个接近最优的可行解。
值得注意的是,虽然割平面法在理论上可以找到最优解,但在实践中可能因为计算复杂度和计算资源限制,而在找到一个足够好的解时就停止搜索。这种方法特别适合于那些直接寻求整数解非常困难的问题。
最大化:
限制条件:
其中,,
求解代码如下:
1from pulp import *
2
3# 创建问题实例
4prob = pulp.LpProblem('整数规划示例', LpMaximize)
5
6# 创建决策变量
7x1 = LpVariable("产品A单位", lowBound = 0, cat = 'Integer')
8x2 = LpVariable("产品B单位", lowBound = 0, cat = 'Integer')
9x3 = LpVariable("产品C单位", lowBound = 0, cat = 'Integer')
10
11# 定义目标函数(利润)
12prob += 5*x1 + 6*x2 + 4*x3, "总利润"
13
14# 添加资源约束
15prob += 2*x1 + 3*x2 + x3 <= 100
16
17prob += 0*x1 + 2*x2 + 4*x3 <= 80
18
19# 求解问题
20prob.solve()
21
22# 打印求解状态
23print("求解状态:", LpStatus[prob.status])
24
25# 打印最优解
26for v in prob.variables():
27 print(v.name, "=", v.varValue)
28
29# 打印最大利润
30print('最大的总利润是 %s 元' % value(prob.objective))
1from pulp import *
2
3# 创建问题实例
4prob = pulp.LpProblem('整数规划示例', LpMaximize)
5
6# 创建决策变量
7x1 = LpVariable("产品A单位", lowBound = 0, cat = 'Integer')
8x2 = LpVariable("产品B单位", lowBound = 0, cat = 'Integer')
9x3 = LpVariable("产品C单位", lowBound = 0, cat = 'Integer')
10
11# 定义目标函数(利润)
12prob += 5*x1 + 6*x2 + 4*x3, "总利润"
13
14# 添加资源约束
15prob += 2*x1 + 3*x2 + x3 <= 100
16
17prob += 0*x1 + 2*x2 + 4*x3 <= 80
18
19# 求解问题
20prob.solve()
21
22# 打印求解状态
23print("求解状态:", LpStatus[prob.status])
24
25# 打印最优解
26for v in prob.variables():
27 print(v.name, "=", v.varValue)
28
29# 打印最大利润
30print('最大的总利润是 %s 元' % value(prob.objective))
这样我们就看到了在有限资源下如何通过整数规划模型来获取最大利润的策略。
输出结果:
1求解状态: Optimal
2产品A单位 = 40.0
3产品B单位 = 0.0
4产品C单位 = 20.0
5最大的总利润是 280.0 元
1求解状态: Optimal
2产品A单位 = 40.0
3产品B单位 = 0.0
4产品C单位 = 20.0
5最大的总利润是 280.0 元
0-1规划(0-1 Integer Programming)是整数规划的一种特殊形式,其中的决策变量被限制为二进制变量,即取值为0或1。这种限制使得0-1规划具有两个可能的取值,适用于诸如选择或排除某些决策的问题。
其形式与线性规划问题的表现形式一样。求解时可以使用分支定界法、割平面法等。