基于GEKKO的整数料箱平衡优化及最小移动量求解问询

问题背景 #

需要平衡3个存储整数的料箱，使各箱总和尽可能接近甚至相等，同时满足以下规则：

• 通过料箱间移动整数实现平衡；
• 整数仅为1、2、3，每个整数带有唯一ID，可追踪最终所在料箱；
• 料箱最终长度无需与初始一致；
• 不可拆分整数移动（如料箱[2,3]中无法移出1）；
• 优先最小化移动次数：整数留在原箱成本为0，移动则成本为1（优先移动单个大整数而非多个小整数）。

完整代码实现 #

from gekko import GEKKO

# 初始料箱数据
bin1 = [1,2,2,1,1,1,3,1]
bin2 = [2,2,1,1,3,1,1]
bin3 = [2,1,2,1,1,1,1]

bin1_IDs=[15,28,39,111,202,300,411,415]
bin2_IDs=[2,10,56,117,132,189,367]
bin3_IDs=[44,102,211,227,351,389,406]

# 整理所有物品的信息：值、原始箱号（0/1/2）、ID
items = []
item_ids = []
original_bin = []
for bin_idx, (contents, ids) in enumerate(zip([bin1, bin2, bin3], [bin1_IDs, bin2_IDs, bin3_IDs])):
    for val, id_num in zip(contents, ids):
        items.append(val)
        item_ids.append(id_num)
        original_bin.append(bin_idx)

# 基础参数计算
original_sums = [sum(bin1), sum(bin2), sum(bin3)]
num_bins = 3
num_items = len(items)
total_sum = sum(items)
target_sum = total_sum / num_bins  # 理想的各箱总和

# 创建GEKKO模型
m = GEKKO(remote=False)

# 决策变量：x[i][j]为1表示物品i被分配到料箱j，0则否（二进制整数变量）
x = [[m.Var(integer=True, lb=0, ub=1) for j in range(num_bins)] for i in range(num_items)]

# 约束1：每个物品必须被分配到恰好一个料箱
for i in range(num_items):
    m.Equation(sum(x[i][j] for j in range(num_bins)) == 1)

# 计算各料箱的最终总和
bin_sums = [m.sum(x[i][j] * items[i] for i in range(num_items)) for j in range(num_bins)]

# 目标函数：加权组合两个优化目标
# 1. 最小化各箱总和与目标总和的平方差（优先保证总和接近）
sum_diff = m.sum((s - target_sum)**2 for s in bin_sums)
# 2. 最小化移动次数（物品不在原始箱的数量）
move_count = m.sum(x[i][j] for i in range(num_items) for j in range(num_bins) if j != original_bin[i])

# 给总和差异更高权重，确保优先平衡总和
m.Obj(10 * sum_diff + move_count)

# 求解优化问题
m.solve(disp=True)

# 输出结果
print("\n=== 平衡结果 ===")
print(f"原始料箱总和: {original_sums}")
print(f"理想目标总和: {target_sum:.2f}")

for j in range(num_bins):
    # 收集当前料箱的物品值、ID
    current_contents = []
    current_ids = []
    stayed_items = []
    moved_in_items = []
    for i in range(num_items):
        if x[i][j].value[0] > 0.5:
            current_contents.append(items[i])
            current_ids.append(item_ids[i])
            if original_bin[i] == j:
                stayed_items.append(f"{items[i]}(ID:{item_ids[i]})")
            else:
                moved_in_items.append(f"{items[i]}(ID:{item_ids[i]})")
    current_sum = sum(current_contents)
    print(f"\n料箱{j+1}:")
    print(f"  内容: {current_contents}")
    print(f"  对应ID: {current_ids}")
    print(f"  当前总和: {current_sum}")
    print(f"  留箱物品: {stayed_items}")
    print(f"  移入物品: {moved_in_items}")

print(f"\n总移动次数: {int(move_count.value[0])}")

代码说明 #

1. 决策变量定义：x[i][j]是二进制整数变量，标记物品i是否被分配到料箱j，确保每个物品仅属于一个料箱。
2. 目标函数设计：通过加权方式优先保证料箱总和接近（权重10），其次减少移动次数（权重1）。这种设计会让优化器优先选择移动大整数（比如一个3的移动能顶三个1的调整效果，且移动成本相同），符合需求中的优先级。
3. 结果输出：不仅展示平衡后的料箱内容与总和，还追踪每个物品的ID及移动状态，方便查看调整过程。

内容的提问来源于stack exchange，提问作者geoladig