Python 具有动态约束的纸浆线性规划
Python Pulp linear programming with dynamic constraint
我目前在 excel 中使用 Solver 来寻找制造的最佳解决方案。这是当前设置：
它是在旋转机器上制造鞋子，即批量重复生产。例如，一批将是“10x A1”（参见 table 中的 A1），这将产生 10x 尺寸 36、20x 尺寸 37... 10x 尺寸 41。
有一些前缀设置； A1、A2； R7...如您在上面 table 中所见。
然后是 requested 变量（或者更确切地说是变量列表），它基本上说明了客户的要求，每个尺寸的数量。
objective 函数 是找到一组重复项，使其尽可能匹配请求的数量。因此在求解器中（对于非英语屏幕截图，抱歉）您可以看到目标是 N21（即每个尺寸的绝对差之和）。变量是 N2:N9 - 这是每个设置的重复次数，唯一的限制是 N2:N9 是一个整数。
如何使用 python 模拟此行为？我的起点：
from collections import namedtuple
from pulp import *
class Setup(namedtuple('IAmReallyLazy', 'name ' + ' '.join(f's{s}' for s in range(36, 47)))):
# inits with name and sizes 's36', 's37'... 's46'
repetitions = 0
setups = [
Setup('A1', 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0),
Setup('A2', 0, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0),
Setup('R7', 0, 0, 1, 1, 1, 1, 2, 0, 0, 0, 0),
Setup('D1', 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
# and others
]
setup_names = [s.name for s in setups]
requested = {
's36': 100,
's37': 250,
's38': 300,
's39': 450,
's40': 450,
's41': 250,
's42': 200,
}
def get_quantity_per_size(size: str) -> int:
return sum([getattr(setup, size) * setup.repetitions for setup in setups])
def get_abs_diff(size: str) -> int:
requested_size = requested.get(size, 0)
return abs(get_quantity_per_size(size) - requested_size)
problem = LpProblem('Optimize Batches', LpMinimize)
# goal is to minimise the sum(get_abs_diff(f's{size}') for size in range(36, 47))
# variables are [setup.repetitions for setup in setups]
# constraints are all([isinstance(setup.repetitions, int) for setup in setups])
在理想世界中如果有不止一个最优解，应该选择具有最大绝对差异的那个（即具有最小最高差异的那个）。也就是说，如果一个解决方案的绝对差异为每个尺码 10 和 10 个尺码（总共 100 个），而另一个有 20 + 80 = 100，则第一个更适合客户。
另一个约束应该是 min(setup.repetitions for setup in setups if setup.repetitions > 0) > 9 基本上重复约束应该是：
- 是整数
- 是 0 还是 大于 9 - 根据我目前的理解，这在线性规划中是不可能的。
这里有几件事。首先，如果您使用 abs() 那么问题将是非线性的。相反，您应该引入新的变量，例如 over_mfg 和 under_mfg，它们表示目标 以上 生产的单位数量和数量 低于目标。您可以这样声明：
over_mfg = LpVariable.dicts("over_mfg", sizes, 0, None, LpInteger)
under_mfg = LpVariable.dicts("under_mfg", sizes, 0, None, LpInteger)
我声明了一个名为 sizes 的列表，它在上面的定义中使用：
min_size = 36
max_size = 46
sizes = ['s' + str(s) for s in range(min_size, max_size+1)]
您还需要指示每个设置重复的变量：
repetitions = LpVariable.dicts("repetitions", setup_names, 0, None, LpInteger)
您的 objective 函数声明为：
problem += lpSum([over_mfg[size] + under_mfg[size] for size in sizes])
（请注意，在 pulp 中，您使用 lpSum 而不是 sum。）现在，您需要说明 over_mfg 是多余的并且 under_mfg 是差额：
for size in sizes:
problem += over_mfg[size] >= lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]) - requested[size], "DefineOverMfg" + size
problem += under_mfg[size] >= requested[size] - lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]), "DefineUnderMfg" + size
另请注意，我没有使用您的 get_quantity_per_size() 和 get_abs_diff() 函数。这些也会混淆 pulp，因为它不会意识到这些是简单的线性函数。
这是我的完整代码：
from collections import namedtuple
from pulp import *
class Setup(namedtuple('IAmReallyLazy', 'name ' + ' '.join(f's{s}' for s in range(36, 47)))):
# inits with name and sizes 's36', 's37'... 's46'
repetitions = 0
setups = [
Setup('A1', 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0),
Setup('A2', 0, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0),
Setup('R7', 0, 0, 1, 1, 1, 1, 2, 0, 0, 0, 0),
Setup('D1', 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
# and others
]
setup_names = [s.name for s in setups]
min_size = 36
max_size = 46
sizes = ['s' + str(s) for s in range(min_size, max_size+1)]
requested = {
's36': 100,
's37': 250,
's38': 300,
's39': 450,
's40': 450,
's41': 250,
's42': 200,
's43': 0, # I added these for completeness
's44': 0,
's45': 0,
's46': 0
}
problem = LpProblem('Optimize Batches', LpMinimize)
# goal is to minimise the sum(get_abs_diff(f's{size}') for size in range(36, 47))
# variables are [setup.repetitions for setup in setups]
# constraints are all([isinstance(setup.repetitions, int) for setup in setups])
repetitions = LpVariable.dicts("repetitions", setup_names, 0, None, LpInteger)
over_mfg = LpVariable.dicts("over_mfg", sizes, 0, None, LpInteger)
under_mfg = LpVariable.dicts("under_mfg", sizes, 0, None, LpInteger)
problem += lpSum([over_mfg[size] + under_mfg[size] for size in sizes])
for size in sizes:
problem += over_mfg[size] >= lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]) - requested[size], "DefineOverMfg" + size
problem += under_mfg[size] >= requested[size] - lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]), "DefineUnderMfg" + size
# Solve problem
problem.solve()
# Print status
print("Status:", LpStatus[problem.status])
# Print optimal values of decision variables
for v in problem.variables():
if v.varValue is not None and v.varValue > 0:
print(v.name, "=", v.varValue)
这是输出：
Status: Optimal
over_mfg_s38 = 62.0
over_mfg_s41 = 62.0
repetitions_A1 = 25.0
repetitions_A2 = 88.0
repetitions_D1 = 110.0
repetitions_R7 = 1.0
under_mfg_s36 = 75.0
under_mfg_s37 = 2.0
under_mfg_s40 = 25.0
因此，我们制造了 25 次 A1 重复、88 次 A2 重复、110 次 D1 重复和 1 次 R7 重复。这给出了 25 个单位的 s36（因此在 100 的目标下有 75 个单位）； 248 个 s37 单位（2 个低于目标）； s38 的 362 个单位（超过目标 300 的 62 个单位）；等等。
现在，对于您的约束，即您 要么 必须生成设置的 0 或 >9，您可以引入新的二进制文件指示是否生成每个设置的变量：
is_produced = LpVariable.dicts("is_produced", setup_names, 0, 1, LpInteger)
然后添加这些约束：
M = 1000
min_reps = 9
for s in setup_names:
problem += M * is_produced[s] >= repetitions[s] # if it's produced at all, must set is_produced = 1
problem += min_reps * (1 - is_produced[s]) + repetitions[s] >= min_reps
M是一个很大的数字；它应该大于最大可能的重复次数，但不能更大。我定义了 min_reps 以避免 "hard-coding" 约束中的 9。因此，这些约束说明 (1) 如果 repetitions[s] > 0，则 is_produced[s] 必须等于 1，并且 (2) either is_produced[s] = 1 或 repetitions[s] > 9.
输出：
Status: Optimal
is_produced_A1 = 1.0
is_produced_A2 = 1.0
is_produced_D1 = 1.0
over_mfg_s38 = 63.0
over_mfg_s39 = 1.0
over_mfg_s41 = 63.0
repetitions_A1 = 25.0
repetitions_A2 = 88.0
repetitions_D1 = 112.0
under_mfg_s36 = 75.0
under_mfg_s40 = 24.0
请注意，现在我们没有任何重复次数 >0 但 <9 次的设置。
In an ideal world if there is more than one optimal solution, the one with most spread abs diff should be selected (ie. the one with the smallest highest difference).
这个比较棘手，而且（至少现在），我会把它留给一个理想的世界，或者另一个人的答案。
顺便说一下：我们正在努力推出一个Stack Exchange site for Operations Research，我们将在其中解决像这样的问题。如果您有兴趣，我鼓励您单击 link 和 "commit"。
我目前在 excel 中使用 Solver 来寻找制造的最佳解决方案。这是当前设置：
它是在旋转机器上制造鞋子，即批量重复生产。例如，一批将是“10x A1”（参见 table 中的 A1），这将产生 10x 尺寸 36、20x 尺寸 37... 10x 尺寸 41。
有一些前缀设置； A1、A2； R7...如您在上面 table 中所见。
然后是 requested 变量（或者更确切地说是变量列表），它基本上说明了客户的要求，每个尺寸的数量。
objective 函数 是找到一组重复项，使其尽可能匹配请求的数量。因此在求解器中（对于非英语屏幕截图，抱歉）您可以看到目标是 N21（即每个尺寸的绝对差之和）。变量是 N2:N9 - 这是每个设置的重复次数，唯一的限制是 N2:N9 是一个整数。
如何使用 python 模拟此行为？我的起点：
from collections import namedtuple
from pulp import *
class Setup(namedtuple('IAmReallyLazy', 'name ' + ' '.join(f's{s}' for s in range(36, 47)))):
# inits with name and sizes 's36', 's37'... 's46'
repetitions = 0
setups = [
Setup('A1', 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0),
Setup('A2', 0, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0),
Setup('R7', 0, 0, 1, 1, 1, 1, 2, 0, 0, 0, 0),
Setup('D1', 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
# and others
]
setup_names = [s.name for s in setups]
requested = {
's36': 100,
's37': 250,
's38': 300,
's39': 450,
's40': 450,
's41': 250,
's42': 200,
}
def get_quantity_per_size(size: str) -> int:
return sum([getattr(setup, size) * setup.repetitions for setup in setups])
def get_abs_diff(size: str) -> int:
requested_size = requested.get(size, 0)
return abs(get_quantity_per_size(size) - requested_size)
problem = LpProblem('Optimize Batches', LpMinimize)
# goal is to minimise the sum(get_abs_diff(f's{size}') for size in range(36, 47))
# variables are [setup.repetitions for setup in setups]
# constraints are all([isinstance(setup.repetitions, int) for setup in setups])
在理想世界中如果有不止一个最优解，应该选择具有最大绝对差异的那个（即具有最小最高差异的那个）。也就是说，如果一个解决方案的绝对差异为每个尺码 10 和 10 个尺码（总共 100 个），而另一个有 20 + 80 = 100，则第一个更适合客户。
另一个约束应该是 min(setup.repetitions for setup in setups if setup.repetitions > 0) > 9 基本上重复约束应该是：
- 是整数
- 是 0 还是 大于 9 - 根据我目前的理解，这在线性规划中是不可能的。
这里有几件事。首先，如果您使用 abs() 那么问题将是非线性的。相反，您应该引入新的变量，例如 over_mfg 和 under_mfg，它们表示目标 以上 生产的单位数量和数量 低于目标。您可以这样声明：
over_mfg = LpVariable.dicts("over_mfg", sizes, 0, None, LpInteger)
under_mfg = LpVariable.dicts("under_mfg", sizes, 0, None, LpInteger)
我声明了一个名为 sizes 的列表，它在上面的定义中使用：
min_size = 36
max_size = 46
sizes = ['s' + str(s) for s in range(min_size, max_size+1)]
您还需要指示每个设置重复的变量：
repetitions = LpVariable.dicts("repetitions", setup_names, 0, None, LpInteger)
您的 objective 函数声明为：
problem += lpSum([over_mfg[size] + under_mfg[size] for size in sizes])
（请注意，在 pulp 中，您使用 lpSum 而不是 sum。）现在，您需要说明 over_mfg 是多余的并且 under_mfg 是差额：
for size in sizes:
problem += over_mfg[size] >= lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]) - requested[size], "DefineOverMfg" + size
problem += under_mfg[size] >= requested[size] - lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]), "DefineUnderMfg" + size
另请注意，我没有使用您的 get_quantity_per_size() 和 get_abs_diff() 函数。这些也会混淆 pulp，因为它不会意识到这些是简单的线性函数。
这是我的完整代码：
from collections import namedtuple
from pulp import *
class Setup(namedtuple('IAmReallyLazy', 'name ' + ' '.join(f's{s}' for s in range(36, 47)))):
# inits with name and sizes 's36', 's37'... 's46'
repetitions = 0
setups = [
Setup('A1', 1, 2, 3, 3, 2, 1, 0, 0, 0, 0, 0),
Setup('A2', 0, 1, 2, 3, 3, 2, 1, 0, 0, 0, 0),
Setup('R7', 0, 0, 1, 1, 1, 1, 2, 0, 0, 0, 0),
Setup('D1', 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0),
# and others
]
setup_names = [s.name for s in setups]
min_size = 36
max_size = 46
sizes = ['s' + str(s) for s in range(min_size, max_size+1)]
requested = {
's36': 100,
's37': 250,
's38': 300,
's39': 450,
's40': 450,
's41': 250,
's42': 200,
's43': 0, # I added these for completeness
's44': 0,
's45': 0,
's46': 0
}
problem = LpProblem('Optimize Batches', LpMinimize)
# goal is to minimise the sum(get_abs_diff(f's{size}') for size in range(36, 47))
# variables are [setup.repetitions for setup in setups]
# constraints are all([isinstance(setup.repetitions, int) for setup in setups])
repetitions = LpVariable.dicts("repetitions", setup_names, 0, None, LpInteger)
over_mfg = LpVariable.dicts("over_mfg", sizes, 0, None, LpInteger)
under_mfg = LpVariable.dicts("under_mfg", sizes, 0, None, LpInteger)
problem += lpSum([over_mfg[size] + under_mfg[size] for size in sizes])
for size in sizes:
problem += over_mfg[size] >= lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]) - requested[size], "DefineOverMfg" + size
problem += under_mfg[size] >= requested[size] - lpSum([repetitions[setup.name] * getattr(setup, size) for setup in setups]), "DefineUnderMfg" + size
# Solve problem
problem.solve()
# Print status
print("Status:", LpStatus[problem.status])
# Print optimal values of decision variables
for v in problem.variables():
if v.varValue is not None and v.varValue > 0:
print(v.name, "=", v.varValue)
这是输出：
Status: Optimal
over_mfg_s38 = 62.0
over_mfg_s41 = 62.0
repetitions_A1 = 25.0
repetitions_A2 = 88.0
repetitions_D1 = 110.0
repetitions_R7 = 1.0
under_mfg_s36 = 75.0
under_mfg_s37 = 2.0
under_mfg_s40 = 25.0
因此，我们制造了 25 次 A1 重复、88 次 A2 重复、110 次 D1 重复和 1 次 R7 重复。这给出了 25 个单位的 s36（因此在 100 的目标下有 75 个单位）； 248 个 s37 单位（2 个低于目标）； s38 的 362 个单位（超过目标 300 的 62 个单位）；等等。
现在，对于您的约束，即您 要么 必须生成设置的 0 或 >9，您可以引入新的二进制文件指示是否生成每个设置的变量：
is_produced = LpVariable.dicts("is_produced", setup_names, 0, 1, LpInteger)
然后添加这些约束：
M = 1000
min_reps = 9
for s in setup_names:
problem += M * is_produced[s] >= repetitions[s] # if it's produced at all, must set is_produced = 1
problem += min_reps * (1 - is_produced[s]) + repetitions[s] >= min_reps
M是一个很大的数字；它应该大于最大可能的重复次数，但不能更大。我定义了 min_reps 以避免 "hard-coding" 约束中的 9。因此，这些约束说明 (1) 如果 repetitions[s] > 0，则 is_produced[s] 必须等于 1，并且 (2) either is_produced[s] = 1 或 repetitions[s] > 9.
输出：
Status: Optimal
is_produced_A1 = 1.0
is_produced_A2 = 1.0
is_produced_D1 = 1.0
over_mfg_s38 = 63.0
over_mfg_s39 = 1.0
over_mfg_s41 = 63.0
repetitions_A1 = 25.0
repetitions_A2 = 88.0
repetitions_D1 = 112.0
under_mfg_s36 = 75.0
under_mfg_s40 = 24.0
请注意，现在我们没有任何重复次数 >0 但 <9 次的设置。
In an ideal world if there is more than one optimal solution, the one with most spread abs diff should be selected (ie. the one with the smallest highest difference).
这个比较棘手，而且（至少现在），我会把它留给一个理想的世界，或者另一个人的答案。
顺便说一下：我们正在努力推出一个Stack Exchange site for Operations Research，我们将在其中解决像这样的问题。如果您有兴趣，我鼓励您单击 link 和 "commit"。