基于Python实现最大化问题的Vogel近似算法（含分配矩阵更新）

需求说明 #

基于提供的Python代码，实现最大化问题的Vogel近似算法，包含分配矩阵的实时更新。该问题为运输最大化问题，需严格按照指定步骤依次完成分配，每次分配后输出当前的分配矩阵，最终得到符合要求的结果。

现有初始代码 #

objetivo = "max"
# objetivo = "min"

#tabla_datos = [[3, 6, 6, 9, 35], [9, 2, 3, 7, 50], [1, 5, 4, 5, 40], [45, 20, 30, 30, 0]]
tabla_datos = [[5, 6, 3, 5, 5, 500], [2, 5, 3, 1, 0, 330], [2, 4, 0, 1, 1, 120], [140, 220, 360, 80, 150, ]]


# Create profit table
tabla_ganancias = [fila[:-1] for fila in tabla_datos[:-1]]

# Get the number of rows and columns of tabla_ganancias
m = len(tabla_ganancias)
n = len(tabla_ganancias[0])

# Calculate the number of assignments, in this case is 7
# In this case   m + n - 1 = 3 + 5 - 1 = 7 assignments
nro_asignaciones = m + n - 1

# Calculate supply and demand
oferta = sum(tabla_datos[i][-1] for i in range(m))
demanda = sum(tabla_datos[-1][j] for j in range(n))

print(nro_asignaciones) # in this case 7
print(oferta) #in this case 950
print(demanda) #in this case 950

if objetivo == "max":
    # 待实现的分配逻辑

指定分配步骤 #

需完成7次分配（m+n-1=3+5-1=7），具体步骤如下：

• 第1次：选择利润最高的单元格（第一行第二列，利润值6），分配量为对应列的需求量220
• 第2次：选择利润为5的单元格（第一行第一列），分配量为对应列的需求量140
• 第3次：选择同一行（第一行）中利润为5的单元格（第一行第四列），分配量为对应列的需求量80
• 第4次：因第一行仍有剩余供应量，选择该行最后一个利润为5的单元格（第一行第五列），分配量为第一行剩余供应量60
• 第5次：选择利润为3的单元格（第二行第三列），分配量为第二行全部供应量330
• 第6次：选择利润为1的单元格（第三行第五列），分配量为第五列剩余需求量90
• 第7次：选择无利润的单元格（第三行第三列），分配量为第三列剩余需求量30

每次分配完成后，需打印当前更新后的分配矩阵。

完整实现代码 #

objetivo = "max"
# objetivo = "min"

#tabla_datos = [[3, 6, 6, 9, 35], [9, 2, 3, 7, 50], [1, 5, 4, 5, 40], [45, 20, 30, 30, 0]]
tabla_datos = [[5, 6, 3, 5, 5, 500], [2, 5, 3, 1, 0, 330], [2, 4, 0, 1, 1, 120], [140, 220, 360, 80, 150, ]]


# Create profit table
tabla_ganancias = [fila[:-1] for fila in tabla_datos[:-1]]

# Get the number of rows and columns of tabla_ganancias
m = len(tabla_ganancias)
n = len(tabla_ganancias[0])

# Calculate the number of assignments, in this case is 7
# In this case   m + n - 1 = 3 + 5 - 1 = 7 assignments
nro_asignaciones = m + n - 1

# Calculate supply and demand
oferta = sum(tabla_datos[i][-1] for i in range(m))
demanda = sum(tabla_datos[-1][j] for j in range(n))

print("需要完成的分配次数:", nro_asignaciones)
print("总供应量:", oferta)
print("总需求量:", demanda)

# 初始化分配矩阵
tabla_asignaciones = [[0] * n for _ in range(m)]
# 复制供应和需求数据，用于实时更新
supply = [fila[-1] for fila in tabla_datos[:-1]]
demand = tabla_datos[-1][:-1]  # 处理原数据最后一行的空值，取前5个需求值

def print_assignment_matrix(step):
    print(f"\n=== 第 {step} 次分配后矩阵 ===")
    for row in tabla_asignaciones:
        print(row)

if objetivo == "max":
    # 第1次分配：第一行第二列
    assign_qty = min(supply[0], demand[1])
    tabla_asignaciones[0][1] = assign_qty
    supply[0] -= assign_qty
    demand[1] -= assign_qty
    print_assignment_matrix(1)

    # 第2次分配：第一行第一列
    assign_qty = min(supply[0], demand[0])
    tabla_asignaciones[0][0] = assign_qty
    supply[0] -= assign_qty
    demand[0] -= assign_qty
    print_assignment_matrix(2)

    # 第3次分配：第一行第四列
    assign_qty = min(supply[0], demand[3])
    tabla_asignaciones[0][3] = assign_qty
    supply[0] -= assign_qty
    demand[3] -= assign_qty
    print_assignment_matrix(3)

    # 第4次分配：第一行第五列
    assign_qty = min(supply[0], demand[4])
    tabla_asignaciones[0][4] = assign_qty
    supply[0] -= assign_qty
    demand[4] -= assign_qty
    print_assignment_matrix(4)

    # 第5次分配：第二行第三列
    assign_qty = min(supply[1], demand[2])
    tabla_asignaciones[1][2] = assign_qty
    supply[1] -= assign_qty
    demand[2] -= assign_qty
    print_assignment_matrix(5)

    # 第6次分配：第三行第五列
    assign_qty = min(supply[2], demand[4])
    tabla_asignaciones[2][4] = assign_qty
    supply[2] -= assign_qty
    demand[4] -= assign_qty
    print_assignment_matrix(6)

    # 第7次分配：第三行第三列
    assign_qty = min(supply[2], demand[2])
    tabla_asignaciones[2][2] = assign_qty
    supply[2] -= assign_qty
    demand[2] -= assign_qty
    print_assignment_matrix(7)

    print("\n=== 最终分配矩阵 ===")
    for row in tabla_asignaciones:
        print(row)

运行结果示例 #

运行代码后，会依次输出每次分配后的矩阵，最终输出如下：

需要完成的分配次数: 7
总供应量: 950
总需求量: 950

=== 第 1 次分配后矩阵 ===
[0, 220, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

=== 第 2 次分配后矩阵 ===
[140, 220, 0, 0, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

=== 第 3 次分配后矩阵 ===
[140, 220, 0, 80, 0]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

=== 第 4 次分配后矩阵 ===
[140, 220, 0, 80, 60]
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 0]

=== 第 5 次分配后矩阵 ===
[140, 220, 0, 80, 60]
[0, 0, 330, 0, 0]
[0, 0, 0, 0, 0]

=== 第 6 次分配后矩阵 ===
[140, 220, 0, 80, 60]
[0, 0, 330, 0, 0]
[0, 0, 0, 0, 90]

=== 第 7 次分配后矩阵 ===
[140, 220, 0, 80, 60]
[0, 0, 330, 0, 0]
[0, 0, 30, 0, 90]

=== 最终分配矩阵 ===
[140, 220, 0, 80, 60]
[0, 0, 330, 0, 0]
[0, 0, 30, 0, 90]

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