Python最小费用法求解运输问题代码逻辑错误排查

问题说明 #

• 实现目标：基于Python和Numpy编写最小费用法（Least Cost Method）求解运输问题，二维数组values存储各供应点（supply）到需求点（demand）的运输距离
• 设计逻辑：迭代遍历values数组查找全局最小值，基于最小值完成供需量计算、运输成本累加后，将已处理完的行/列替换为0；设定循环终止条件为values数组与同形状全0数组完全匹配，之后继续查找下一个最小值重复流程
• 已知设定：所有需求点的demand值均为负数
• 现存问题：
  • while循环无法正常启动，条件判断values.all() != constantarray.all()求值结果恒为False
  • 最小值坐标m、n取值始终固定不变，仅能移除values中的一个值，无法将运输量正常写入sandmoved数组
  • 已尝试嵌套for循环、多种while循环语法组合均未实现预期效果；已额外编写supply[m] == demand[n]场景的判断分支，但不确定该分支是否必要

现有代码 #

constarray = np.zeros((len(supply),len(demand)) #create array of 0s
sandmoved = np.zeros((len(supply),len(demand)) #used to store information needed for later
totalcost = 0 
while values.all() != constantarray.all(): #iterate until `values` only contains 0s
    m = np.argmin(values,axis = 0)[0] #find coordinates of minimum value 
    n = np.argmin(values,axis = 1)[0]
    if supply[m] > abs(demand[m]): #all demand numbers are negative
        supply[m]+=demand[n] #subtract demand from supply
        totalcost +=abs(demand[n])*values[m,n] 
        sandmoved[m,n] = demand[n] #add amount of 'sand' moved to an empty array
        values[m,0:-1] = 0 #replace entire m row with 0s since demand has been filled
        demand[n]=0 #replace demand value with 0
    elif supply[m]< abs(demand[n]):
        demand[n]+=supply[m] #combine positive supply with negative demand
        sandmoved[m,n]=supply[m]
        totalcost +=supply[m]*values[m,n] 
        values[:-1,n]=0 #replace entire column with 0s since supply has been depleted
        supply[m] = 0 

已定位的代码错误 #

• 循环条件逻辑错误：ndarray.all()方法用于判断数组内所有元素是否为真值，返回单个布尔值；全0数组constarray调用.all()永远返回False，和values.all()的比较完全无法实现“判断values是否全0”的需求
• 最小值坐标获取错误：按axis=0/1分别取argmin再取[0]的写法，只能拿到某行/某列的第一个最小值索引，无法获取全局最小值的二维坐标
• 索引引用错误：第一个判断分支中对比供应量和需求量时，错误使用了供应点索引m取需求值，正确应该使用需求点索引n
• 行列置零逻辑错误：values[m,0:-1]仅会将第m行除最后一列外的元素置0，未覆盖整行；values[:-1,n]仅会将第n列除最后一行外的元素置0，未覆盖整列
• 基础语法错误：两处np.zeros()调用缺失闭合右括号，会直接触发语法报错
• 缺失边界处理：未覆盖供需量相等的分支场景，遇到该情况时代码不会执行任何操作，会陷入死循环

内容的提问来源于stack exchange，提问作者Swan L.