python - Python PuLP 优化问题 - 最小化平均偏差

Question

我正在尝试用纸浆做一个优化问题，但我在编写我的目标函数时遇到了问题。

我已将我的真实示例简化为使用谷物的更简单示例。因此，假设我有一个产品列表和一些可以将它们放入的通道（对于本例 2）。每个产品都有一个我们通常每周销售的编号（例如：我们每周销售 20 盒 Fruit Loops 和 6 盒 Cheerios）。每件商品还需要一定数量的架子（例如：Frosted Flakes 需要 1 个架子，但 Corn Flakes 需要 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. 我认为我的目标函数太复杂了，但我不确定。

任何帮助表示赞赏。

标签： pythonmathematical-optimizationlinear-programmingpulp

Answer 1

您的主要问题是 ABS 函数是非线性的。（你想要做的任何排序事情也是如此......;)）。所以你必须重新制定。执行此操作的典型方法是引入辅助变量，并将“正”和“负”偏差与 ABS 函数分开考虑，因为它们都是线性的。网站上有几个这样的例子，包括我不久前回答的这个例子：

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

这就需要将通道选择纳入索引，因为您需要为通道总和或差异建立一个索引。这并不太难。

然后你必须（如下所示）设置约束以将新aisle_diff变量约束为大于与 ABS 的正偏差或负偏差。

所以，我认为下面的工作正常。请注意，我引入了第 3 通道以使其更有趣/可测试。我对你现在死掉的代码留下了一些评论。

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]