Python PuLP 优化问题 - 最小化与平均值的偏差

Question

我正在尝试使用 PuLP 解决优化问题，但在编写目标函数时遇到问题。

我已将现实生活中的示例简化为使用谷物的更简单的示例。假设我有一个产品列表和一些可以将它们放入的过道（对于本示例 2）。每种产品都有一个我们通常每周销售的数量（例如：我们每周销售 20 盒水果圈和 6 盒麦片）。每个物品还需要一定数量的架子（例如：磨砂片需要 1 个架子，但玉米片需要 2 个）。

产品	销售量	货架	指定通道
水果圈	20	2
磨砂片	15	1
可可卵石	8	1
果味鹅卵石	9	1
玉米片	12	2
麦片	6	1

每个过道只有4个货架。因此，理论上我可以将水果圈和玉米片放在一个过道上（2 个架子 + 2 个架子）。如果我将这些商品放在一个过道中，则该过道的每周销售额将为 20 + 12 = 32。如果我将其他 4 件商品（1 个货架 + 1 + 1 + 1）放入一个过道中，则该过道的销售额将为 15 + 8 + 9 + 6 = 38。过道的平均销售额应为 35。我的优化问题的目标是让每个过道尽可能接近该平均数字。我想最小化每个过道每周总销售额和平均数量之间的总绝对差异。在此示例中，我的偏差为 ABS(38-35) + ABS(32-35) = 6。这就是我想要最小化的数字。

我不知道如何写，所以 PuLP 接受了我的目标。我无法在网上找到具有这种复杂程度的示例，它将每个值与平均值进行比较并获取累积绝对偏差。当我写出技术上可以计算的代码时，PuLP 似乎不接受它。

这是一些示例代码：

products = ['Fruit Loops', 'Frosted Flakes', 'Cocoa Pebbles', 'Fruitty Pebbles', 'Corn Flakes', 'Cheerios']

sales = {'Fruit Loops': 20, 'Frosted Flakes': 15, 'Cocoa Pebbles': 8, 'Fruitty Pebbles': 9, 'Corn Flakes': 12, 'Cheerios': 6}

shelves = {'Fruit Loops': 2, 'Frosted Flakes': 1, 'Cocoa Pebbles': 1, 'Fruitty Pebbles': 1, 'Corn Flakes': 2, 'Cheerios': 1}

from pulp import *

problem = LpProblem('AisleOptimization', LpMinimize)

# For this simplified example there are only 2 aisles
Num_of_Aisles = 2

# Each Aisle has 4 shelves and can't have more than 4 shelves filled
Max_Shelves_Aisle = 4

# The Optimizer can change the Aisle each Product is assigned to try and solve the problem
AislePick = LpVariable.dicts('AislePick', products, lowBound = 0, upBound = (Num_of_Aisles - 1), cat='Integer')

# My attempt at the Minimization Formula
# First Calculate what the average sales would be if split perfectly between aisles
avgsales = sum(sales.values()) / Num_of_Aisles

# Loop through and calculate total sales in each aisle and then subtract from the average
problem += lpSum([sum(v for _, v in value) - avgsales for _, value in itertools.groupby(sorted([(aisle, sales[product]) for product, aisle in AislePick.items()]), lambda x: x[0])]), 'Hits Diff'

# Restriction so each Aisle can only have 4 shelves
for aisle in range(Num_of_Aisles):
    problem += lpSum([shelves[prod] for prod, ais in AislePick.items() if ais == aisle]) <= Max_Shelves_Aisle, f"Sum_of_Slots_in_Aislel{aisle}"

problem.solve()

我得到的结果是-3

如果我跑步，LpStatus[problem.status]我会得到Undefined。我认为我的目标函数太复杂，但我不确定。

任何帮助表示赞赏。

Answer 1

这里的主要问题是 ABS 功能是非线性的。（无论你想要做什么排序事情也是如此......；））。所以你必须重新制定。执行此操作的典型方法是引入辅助变量，并分别考虑 ABS 函数的“正”和“负”偏差，因为这两者都是线性的。网站上有几个这样的例子，包括我不久前回答的这个：

如何在Python中使用绝对值进行整数优化？

这就需要将过道选择纳入索引，因为您需要有过道总和或差异的索引。这并不太难。

然后，您必须（如下所示）施加约束以将新aisle_diff变量限制为大于 ABS 的正偏差或负偏差。

所以，我认为下面的效果很好。请注意，我引入了第三个过道，以使其更有趣/可测试。我对你现已失效的代码留下了一些评论。

from pulp import *

products = ['Fruit Loops', 'Frosted Flakes', 'Cocoa Pebbles', 'Fruitty Pebbles', 'Corn Flakes', 'Cheerios']
sales = {'Fruit Loops': 20, 'Frosted Flakes': 15, 'Cocoa Pebbles': 8, 'Fruitty Pebbles': 9, 'Corn Flakes': 12, 'Cheerios': 6}
shelves = {'Fruit Loops': 2, 'Frosted Flakes': 1, 'Cocoa Pebbles': 1, 'Fruitty Pebbles': 1, 'Corn Flakes': 2, 'Cheerios': 1}

problem = LpProblem('AisleOptimization', LpMinimize)

# Updated to 3 aisles for testing...
Num_of_Aisles = 3
aisles = range(Num_of_Aisles)

# Each Aisle has 4 shelves and can't have more than 4 shelves filled
Max_Shelves_Aisle = 4

avgsales = sum(sales.values()) / Num_of_Aisles

# The Optimizer can change the Aisle each Product is assigned to try and solve the problem
# value of 1:  assign to this aisle
AislePick = LpVariable.dicts('AislePick', indexs=[(p,a) for p in products for a in aisles], cat='Binary')

#print(AislePick)

# variable to hold the abs diff of aisles sales value...
aisle_diff = LpVariable.dicts('aisle_diff', indexs=aisles, cat='Real')

# constraint:  Limit aisle-shelf capacity
for aisle in aisles:
    problem += lpSum(shelves[product]*AislePick[product, aisle] for product in products) <= Max_Shelves_Aisle

# constraint:  All producst must be assigned to exactly 1 aisle (or the model would make no assignments at all...
#              or possibly make multiple assignements to balance out)
for product in products:
    problem += lpSum(AislePick[product, aisle] for aisle in aisles) == 1

# constraint:  the "positive" aisle difference side of the ABS
for aisle in aisles:
    problem += aisle_diff[aisle] >= \
               lpSum(sales[product]*AislePick[product, aisle] for product in products) - avgsales

# constraint:  the "negative" aisle diff...
for aisle in aisles:
    problem += aisle_diff[aisle] >= \
               avgsales - lpSum(sales[product]*AislePick[product, aisle] for product in products)

# OBJ:  minimize the total diff (same as min avg diff)
problem += lpSum(aisle_diff[aisle] for aisle in aisles)

# My attempt at the Minimization Formula
# First Calculate what the average sales would be if split perfectly between aisles


# Loop through and calculate total sales in each aisle and then subtract from the average
# illegal:  problem += lpSum([sum(v for _, v in value) - avgsales for _, value in itertools.groupby(sorted([(aisle, sales[product]) for product, aisle in AislePick.items()]), lambda x: x[0])]), 'Hits Diff'

# Restriction so each Aisle can only have 4 shelves
# illegal.  You cannot use a conditional "if" statement to test the value of a variable.
#           This statement needs to produce a constraint expression independent of the value of the variable...
# for aisle in range(Num_of_Aisles):
#     problem += lpSum([shelves[prod] for prod, ais in AislePick.items() if ais == aisle]) <= Max_Shelves_Aisle, f"Sum_of_Slots_in_Aislel{aisle}"

problem.solve()

for (p,a) in [(p,a) for p in products for a in aisles]:
    if AislePick[p,a].varValue:
        print(f'put the {p} on aisle {a}')

for a in aisles:
    aisle_sum = sum(sales[p]*AislePick[p,a].varValue for p in products)
    print(f'expectes sales in aisle {a} are ${aisle_sum : 0.2f}')

# for v in problem.variables():
#     print(v.name,'=',v.varValue)

产量：

Result - Optimal solution found

Objective value:                5.33333333
Enumerated nodes:               22
Total iterations:               1489
Time (CPU seconds):             0.10
Time (Wallclock seconds):       0.11

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.10   (Wallclock seconds):       0.11

put the Fruit Loops on aisle 0
put the Frosted Flakes on aisle 2
put the Cocoa Pebbles on aisle 2
put the Fruitty Pebbles on aisle 1
put the Corn Flakes on aisle 1
put the Cheerios on aisle 0
expectes sales in aisle 0 are $ 26.00
expectes sales in aisle 1 are $ 21.00
expectes sales in aisle 2 are $ 23.00
[Finished in 281ms]