目錄
1、概述
（1）運輸問題
（2）基本思想
（3）表上作業法求解運輸問題步驟
2、知識點細講
（1）運輸問題及其數學模型
（2）表上作業法求解運輸問題——思想
（3）表上作業法求解運輸問題——尋找基可行解
（4）表上作業法求解運輸問題——解的最優檢驗
（5）表上作業法求解運輸問題——解的改進
（6）産銷不平衡的運輸問題
（7）有轉運的運輸問題
3、案例分析1——沃格爾法（尋找初始基可行解）
（1）案例分析
（2）Python實作
（3）結果
4、案例分析2——位勢法（解的最優檢驗）
（1）案例分析
（2）Python實作
（3）結果
5、緻謝
1、概述
（1）運輸問題
（2）基本思想
（3）表上作業法求解運輸問題步驟
2、知識點細講
（1）運輸問題及其數學模型
（2）表上作業法求解運輸問題——思想
（3）表上作業法求解運輸問題——尋找基可行解
（4）表上作業法求解運輸問題——解的最優檢驗
（5）表上作業法求解運輸問題——解的改進
（6）産銷不平衡的運輸問題
（7）有轉運的運輸問題
3、案例分析1——沃格爾法（尋找初始基可行解）
（1）案例分析
（2）Python實作
#運輸問題求解：使用Vogel逼近法尋找初始基本可行解
import numpy as np
import copy
import pandas as pd
def main():
mat=pd.read_csv('表上作業法求解運輸問題.csv',header=None).values
#mat = pd.read_excel('表上作業法求解運輸問題.xlsx', header=None).values
#c=np.array([[4,12,4,11],[2,10,3,9],[8,5,11,6]]) #成本矩陣
#a=np.array([16,10,22]) #供給量
#b=np.array([8,14,12,14]) #需求量
[c,x]=TP_vogel(mat)
#[c,x]=TP_vogel([c,a,b])
def TP_split_matrix(mat): #運輸分割矩陣
c=mat[:-1,:-1]
a=mat[:-1,-1]
b=mat[-1,:-1]
return (c,a,b)
def TP_vogel(var): #Vogel法代碼，變量var可以是以numpy.ndarray儲存的運輸表，或以tuple或list儲存的(成本矩陣,供給向量,需求向量)
import numpy
typevar1=type(var)==numpy.ndarray
typevar2=type(var)==tuple
typevar3=type(var)==list
if typevar1==False and typevar2==False and typevar3==False:
print('>>>非法變量<<<')
(cost,x)=(None,None)
else:
if typevar1==True:
[c,a,b]=TP_split_matrix(var)
elif typevar2==True or typevar3==True:
[c,a,b]=var
cost=copy.deepcopy(c)
x=np.zeros(c.shape)
M=pow(10,9)
for factor in c.reshape(1,-1)[0]:
while int(factor)!=M:
if np.all(c==M):
break
else:
print('c:\n',c)
#擷取行/列最小值數組
row_mini1=[]
row_mini2=[]
for row in range(c.shape[0]):
Row=list(c[row,:])
row_min=min(Row)
row_mini1.append(row_min)
Row.remove(row_min)
row_2nd_min=min(Row)
row_mini2.append(row_2nd_min)
#print(row_mini1,'\n',row_mini2)
r_pun=[row_mini2[i]-row_mini1[i] for i in range(len(row_mini1))]
print('行罰數：',r_pun)
#計算列罰數
col_mini1=[]
col_mini2=[]
for col in range(c.shape[1]):
Col=list(c[:,col])
col_min=min(Col)
col_mini1.append(col_min)
Col.remove(col_min)
col_2nd_min=min(Col)
col_mini2.append(col_2nd_min)
c_pun=[col_mini2[i]-col_mini1[i] for i in range(len(col_mini1))]
print('列罰數：',c_pun)
pun=copy.deepcopy(r_pun)
pun.extend(c_pun)
print('罰數向量：',pun)
max_pun=max(pun)
max_pun_index=pun.index(max(pun))
max_pun_num=max_pun_index+1
print('最大罰數：',max_pun,'元素序号：',max_pun_num)
if max_pun_num<=len(r_pun):
row_num=max_pun_num
print('對第',row_num,'行進行操作：')
row_index=row_num-1
catch_row=c[row_index,:]
print(catch_row)
min_cost_colindex=int(np.argwhere(catch_row==min(catch_row)))
print('最小成本所在列索引：',min_cost_colindex)
if a[row_index]<=b[min_cost_colindex]:
x[row_index,min_cost_colindex]=a[row_index]
c1=copy.deepcopy(c)
c1[row_index,:]=[M]*c1.shape[1]
b[min_cost_colindex]-=a[row_index]
a[row_index]-=a[row_index]
else:
x[row_index,min_cost_colindex]=b[min_cost_colindex]
c1=copy.deepcopy(c)
c1[:,min_cost_colindex]=[M]*c1.shape[0]
a[row_index]-=b[min_cost_colindex]
b[min_cost_colindex]-=b[min_cost_colindex]
else:
col_num=max_pun_num-len(r_pun)
col_index=col_num-1
print('對第',col_num,'列進行操作：')
catch_col=c[:,col_index]
print(catch_col)
#尋找最大罰數所在行/列的最小成本系數
min_cost_rowindex=int(np.argwhere(catch_col==min(catch_col)))
print('最小成本所在行索引：',min_cost_rowindex)
#計算将該位置應填入x矩陣的數值（a,b中較小值）
if a[min_cost_rowindex]<=b[col_index]:
x[min_cost_rowindex,col_index]=a[min_cost_rowindex]
c1=copy.deepcopy(c)
c1[min_cost_rowindex,:]=[M]*c1.shape[1]
b[col_index]-=a[min_cost_rowindex]
a[min_cost_rowindex]-=a[min_cost_rowindex]
else:
x[min_cost_rowindex,col_index]=b[col_index]
#填入後删除已滿足/耗盡資源系數的行/列，得到剩餘的成本矩陣，并改寫資源系數
c1=copy.deepcopy(c)
c1[:,col_index]=[M]*c1.shape[0]
a[min_cost_rowindex]-=b[col_index]
b[col_index]-=b[col_index]
c=c1
print('本次疊代後的x矩陣：\n',x)
print('a:',a)
print('b:',b)
print('c:\n',c)
if np.all(c==M):
print('【疊代完成】')
print('-'*60)
else:
print('【疊代未完成】')
print('-'*60)
total_cost=np.sum(np.multiply(x,cost))
if np.all(a==0):
if np.all(b==0):
print('>>>供求平衡<<<')
else:
print('>>>供不應求，需求方有餘量<<<')
elif np.all(b==0):
print('>>>供大于求，供給方有餘量<<<')
else:
print('>>>無法找到初始基可行解<<<')
print('>>>初始基本可行解x*：\n',x)
print('>>>目前總成本：',total_cost)
[m,n]=x.shape
varnum=np.array(np.nonzero(x)).shape[1]
if varnum!=m+n-1:
print('【注意：問題含有退化解】')
return (cost,x)
if __name__ =='__main__':
main() [注意]（1）copy子產品、（2）mat的操作、（3）在使用pandas導入檔案資料的時候，運作read_csv正常，運作的read_excel 出現錯誤，直接按照提示安裝openpyxl。
（3）結果
c:
[[ 4. 12. 4. 11.]
[ 2. 10. 3. 9.]
[ 8. 5. 11. 6.]]
行罰數： [0.0, 1.0, 1.0]
列罰數： [2.0, 5.0, 1.0, 3.0]
罰數向量： [0.0, 1.0, 1.0, 2.0, 5.0, 1.0, 3.0]
最大罰數： 5.0 元素序号： 5
對第 2 列進行操作：
[12. 10. 5.]
最小成本所在行索引： 2
本次疊代後的x矩陣：
[[ 0. 0. 0. 0.]
[ 0. 0. 0. 0.]
[ 0. 14. 0. 0.]]
a: [16. 10. 8.]
b: [ 8. 0. 12. 14.]
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[8.0e+00 1.0e+09 1.1e+01 6.0e+00]]
【疊代未完成】
------------------------------------------------------------
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[8.0e+00 1.0e+09 1.1e+01 6.0e+00]]
行罰數： [0.0, 1.0, 2.0]
列罰數： [2.0, 0.0, 1.0, 3.0]
罰數向量： [0.0, 1.0, 2.0, 2.0, 0.0, 1.0, 3.0]
最大罰數： 3.0 元素序号： 7
對第 4 列進行操作：
[11. 9. 6.]
最小成本所在行索引： 2
本次疊代後的x矩陣：
[[ 0. 0. 0. 0.]
[ 0. 0. 0. 0.]
[ 0. 14. 0. 8.]]
a: [16. 10. 0.]
b: [ 8. 0. 12. 6.]
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [0.0, 1.0, 0.0]
列罰數： [2.0, 0.0, 1.0, 2.0]
罰數向量： [0.0, 1.0, 0.0, 2.0, 0.0, 1.0, 2.0]
最大罰數： 2.0 元素序号： 4
對第 1 列進行操作：
[4.e+00 2.e+00 1.e+09]
最小成本所在行索引： 1
本次疊代後的x矩陣：
[[ 0. 0. 0. 0.]
[ 8. 0. 0. 0.]
[ 0. 14. 0. 8.]]
a: [16. 2. 0.]
b: [ 0. 0. 12. 6.]
c:
[[1.0e+09 1.0e+09 4.0e+00 1.1e+01]
[1.0e+09 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[1.0e+09 1.0e+09 4.0e+00 1.1e+01]
[1.0e+09 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [7.0, 6.0, 0.0]
列罰數： [0.0, 0.0, 1.0, 2.0]
罰數向量： [7.0, 6.0, 0.0, 0.0, 0.0, 1.0, 2.0]
最大罰數： 7.0 元素序号： 1
對第 1 行進行操作：
[1.0e+09 1.0e+09 4.0e+00 1.1e+01]
最小成本所在列索引： 2
本次疊代後的x矩陣：
[[ 0. 0. 12. 0.]
[ 8. 0. 0. 0.]
[ 0. 14. 0. 8.]]
a: [4. 2. 0.]
b: [0. 0. 0. 6.]
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [999999989.0, 999999991.0, 0.0]
列罰數： [0.0, 0.0, 0.0, 2.0]
罰數向量： [999999989.0, 999999991.0, 0.0, 0.0, 0.0, 0.0, 2.0]
最大罰數： 999999991.0 元素序号： 2
對第 2 行進行操作：
[1.e+09 1.e+09 1.e+09 9.e+00]
最小成本所在列索引： 3
本次疊代後的x矩陣：
[[ 0. 0. 12. 0.]
[ 8. 0. 0. 2.]
[ 0. 14. 0. 8.]]
a: [4. 0. 0.]
b: [0. 0. 0. 4.]
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [999999989.0, 0.0, 0.0]
列罰數： [0.0, 0.0, 0.0, 999999989.0]
罰數向量： [999999989.0, 0.0, 0.0, 0.0, 0.0, 0.0, 999999989.0]
最大罰數： 999999989.0 元素序号： 1
對第 1 行進行操作：
[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
最小成本所在列索引： 3
本次疊代後的x矩陣：
[[ 0. 0. 12. 4.]
[ 8. 0. 0. 2.]
[ 0. 14. 0. 8.]]
a: [0. 0. 0.]
b: [0. 0. 0. 0.]
c:
[[1.e+09 1.e+09 1.e+09 1.e+09]
[1.e+09 1.e+09 1.e+09 1.e+09]
[1.e+09 1.e+09 1.e+09 1.e+09]]
【疊代完成】
------------------------------------------------------------
>>>供求平衡<<<
>>>初始基本可行解x*：
[[ 0. 0. 12. 4.]
[ 8. 0. 0. 2.]
[ 0. 14. 0. 8.]]
>>>目前總成本： 244.0
Process finished with exit code 0 位勢法（解的最優檢驗）
（1）案例分析
（2）Python實作
#Vogel法尋找初始基可行解+位勢法判斷解的最優性
import numpy as np
import copy
import pandas as pd
def TP_split_matrix(mat):
c=mat[:-1,:-1]
a=mat[:-1,-1]
b=mat[-1,:-1]
return (c,a,b)
def TP_vogel(var): #Vogel法代碼，變量var可以是以numpy.ndarray儲存的運輸表，或以tuple或list儲存的(成本矩陣,供給向量,需求向量)
import numpy
typevar1=type(var)==numpy.ndarray
typevar2=type(var)==tuple
typevar3=type(var)==list
if typevar1==False and typevar2==False and typevar3==False:
print('>>>非法變量<<<')
(cost,x)=(None,None)
else:
if typevar1==True:
[c,a,b]=TP_split_matrix(var)
elif typevar2==True or typevar3==True:
[c,a,b]=var
cost=copy.deepcopy(c)
x=np.zeros(c.shape)
M=pow(10,9)
for factor in c.reshape(1,-1)[0]:
while int(factor)!=M:
if np.all(c==M):
break
else:
print('c:\n',c)
#擷取行/列最小值數組
row_mini1=[]
row_mini2=[]
for row in range(c.shape[0]):
Row=list(c[row,:])
row_min=min(Row)
row_mini1.append(row_min)
Row.remove(row_min)
row_2nd_min=min(Row)
row_mini2.append(row_2nd_min)
#print(row_mini1,'\n',row_mini2)
r_pun=[row_mini2[i]-row_mini1[i] for i in range(len(row_mini1))]
print('行罰數：',r_pun)
#計算列罰數
col_mini1=[]
col_mini2=[]
for col in range(c.shape[1]):
Col=list(c[:,col])
col_min=min(Col)
col_mini1.append(col_min)
Col.remove(col_min)
col_2nd_min=min(Col)
col_mini2.append(col_2nd_min)
c_pun=[col_mini2[i]-col_mini1[i] for i in range(len(col_mini1))]
print('列罰數：',c_pun)
pun=copy.deepcopy(r_pun)
pun.extend(c_pun)
print('罰數向量：',pun)
max_pun=max(pun)
max_pun_index=pun.index(max(pun))
max_pun_num=max_pun_index+1
print('最大罰數：',max_pun,'元素序号：',max_pun_num)
if max_pun_num<=len(r_pun):
row_num=max_pun_num
print('對第',row_num,'行進行操作：')
row_index=row_num-1
catch_row=c[row_index,:]
print(catch_row)
min_cost_colindex=int(np.argwhere(catch_row==min(catch_row)))
print('最小成本所在列索引：',min_cost_colindex)
if a[row_index]<=b[min_cost_colindex]:
x[row_index,min_cost_colindex]=a[row_index]
c1=copy.deepcopy(c)
c1[row_index,:]=[M]*c1.shape[1]
b[min_cost_colindex]-=a[row_index]
a[row_index]-=a[row_index]
else:
x[row_index,min_cost_colindex]=b[min_cost_colindex]
c1=copy.deepcopy(c)
c1[:,min_cost_colindex]=[M]*c1.shape[0]
a[row_index]-=b[min_cost_colindex]
b[min_cost_colindex]-=b[min_cost_colindex]
else:
col_num=max_pun_num-len(r_pun)
col_index=col_num-1
print('對第',col_num,'列進行操作：')
catch_col=c[:,col_index]
print(catch_col)
#尋找最大罰數所在行/列的最小成本系數
min_cost_rowindex=int(np.argwhere(catch_col==min(catch_col)))
print('最小成本所在行索引：',min_cost_rowindex)
#計算将該位置應填入x矩陣的數值（a,b中較小值）
if a[min_cost_rowindex]<=b[col_index]:
x[min_cost_rowindex,col_index]=a[min_cost_rowindex]
c1=copy.deepcopy(c)
c1[min_cost_rowindex,:]=[M]*c1.shape[1]
b[col_index]-=a[min_cost_rowindex]
a[min_cost_rowindex]-=a[min_cost_rowindex]
else:
x[min_cost_rowindex,col_index]=b[col_index]
#填入後删除已滿足/耗盡資源系數的行/列，得到剩餘的成本矩陣，并改寫資源系數
c1=copy.deepcopy(c)
c1[:,col_index]=[M]*c1.shape[0]
a[min_cost_rowindex]-=b[col_index]
b[col_index]-=b[col_index]
c=c1
print('本次疊代後的x矩陣：\n',x)
print('a:',a)
print('b:',b)
print('c:\n',c)
if np.all(c==M):
print('【疊代完成】')
print('-'*60)
else:
print('【疊代未完成】')
print('-'*60)
total_cost=np.sum(np.multiply(x,cost))
if np.all(a==0):
if np.all(b==0):
print('>>>供求平衡<<<')
else:
print('>>>供不應求，需求方有餘量<<<')
elif np.all(b==0):
print('>>>供大于求，供給方有餘量<<<')
else:
print('>>>無法找到初始基可行解<<<')
print('>>>初始基本可行解x*：\n',x)
print('>>>目前總成本：',total_cost)
[m,n]=x.shape
varnum=np.array(np.nonzero(x)).shape[1]
if varnum!=m+n-1:
print('【注意：問題含有退化解】')
return (cost,x)
def create_c_nonzeros(c,x):
import numpy as np
import copy
nonzeros=copy.deepcopy(x)
for i in range(x.shape[0]):
for j in range(x.shape[1]):
if x[i,j]!=0:
nonzeros[i,j]=1
#print(nonzeros)
c_nonzeros=np.multiply(c,nonzeros)
return c_nonzeros
def if_dsquare(a,b):
print('a:',a.shape,'\n','b:',b.shape)
correct='>>>位勢方程組可解<<<'
error='>>>位勢方程組不可解，請檢查基變量個數是否等于(m+n-1)及位勢未知量個數是否等于(m+n)<<<'
if len(a.shape)==2:
if len(b.shape)==2:
if a.shape[0]==a.shape[1] and a.shape==b.shape:
print(correct)
if_dsquare=True
else:
print(error)
if_dsquare=False
elif len(b.shape)==1 and b.shape[0]!=0:
if a.shape[0]==a.shape[1] and a.shape[0]==b.shape[0]:
print(correct)
if_dsquare=True
else:
print(error)
if_dsquare=False
else:
print(error)
if_dsquare=False
elif len(a.shape)==1:
if len(b.shape)==2:
if b.shape[0]==b.shape[1] and a.shape[0]==b.shape[0]:
print('>>>位勢方程組系數矩陣與方程組值向量位置錯誤<<<')
if_dsquare='True but not solvable'
else:
print(error)
if_dsquare=False
elif len(b.shape)==1:
print(error)
if_dsquare=False
else:
print(error)
if_dsquare=False
else:
print(error)
if_dsquare=False
return if_dsquare
def TP_potential(cost,x):
[m,n]=x.shape
varnum=np.array(np.nonzero(x)).shape[1]
if varnum!=m+n-1:
sigma=None
print('【問題含有退化解，暫時無法判斷最優性】')
else:
#print(c_nonzeros.shape)
c_nonzeros=create_c_nonzeros(c,x)
cc_nonzeros=np.array(np.nonzero(c_nonzeros))
A=[]
B=[]
length=c_nonzeros.shape[0]+c_nonzeros.shape[1]
zeros=np.zeros((1,length))[0]
for i in range(cc_nonzeros.shape[1]):
zeros=np.zeros((1,length))[0]
zeros[cc_nonzeros[0,i]]=1
zeros[cc_nonzeros[1,i]+c_nonzeros.shape[0]]=1
A.append(zeros)
B.append(c_nonzeros[cc_nonzeros[0,i],cc_nonzeros[1,i]])
l=[1]
for j in range(length-1):
l.append(0) #補充一個x1=0的方程以滿足求解條件
A.append(l)
B.append(0)
#print(A)
#print(B)
A=np.array(A)
B=np.array(B)
judge=if_dsquare(A,B)
if judge==True:
sol=np.linalg.solve(A,B) #求解條件：A的行數（方程個數)=A的列數(變量個數）=B的個數（方程結果個數）才能解
#print(sol)
var=[] #建立位勢名稱數組
for i in range(c_nonzeros.shape[0]):
var.append('u'+str(i+1))
for j in range(c_nonzeros.shape[1]):
var.append('v'+str(j+1))
#print(var)
solset=dict(zip(var,sol))
print('>>>目前位勢:\n',solset)
u=[]
v=[]
[m,n]=c_nonzeros.shape
zero_places=np.transpose(np.argwhere(c_nonzeros==0))
for i in range(m):
u.append(sol[i])
for j in range(n):
v.append(sol[j+m])
for k in range(zero_places.shape[1]):
c_nonzeros[zero_places[0,k],zero_places[1,k]]=u[zero_places[0,k]]+v[zero_places[1,k]]
#print(c_nonzeros)
sigma=cost-c_nonzeros
print('>>>檢驗表σ：\n',sigma)
if np.all(sigma>=0):
print('>>>TP已達到最優解<<<')
else:
print('>>>TP未達到最優解<<<')
else:
sigma=None
print('>>>位勢方程組不可解<<<')
return sigma
mat = pd.read_excel('表上作業法求解運輸問題.xlsx', header=None).values
# mat = pd.read_csv('表上作業法求解運輸問題.csv', header=None).values
# c=np.array([[4,12,4,11],[2,10,3,9],[8,5,11,6]])
# a=np.array([16,10,22])
# b=np.array([8,14,12,14])
[c, x] = TP_vogel(mat)
# [c,x]=TP_vogel([c,a,b])
sigma= TP_potential(c, x) （3）結果
c:
[[ 4. 12. 4. 11.]
[ 2. 10. 3. 9.]
[ 8. 5. 11. 6.]]
行罰數： [0.0, 1.0, 1.0]
列罰數： [2.0, 5.0, 1.0, 3.0]
罰數向量： [0.0, 1.0, 1.0, 2.0, 5.0, 1.0, 3.0]
最大罰數： 5.0 元素序号： 5
對第 2 列進行操作：
[12. 10. 5.]
最小成本所在行索引： 2
本次疊代後的x矩陣：
[[ 0. 0. 0. 0.]
[ 0. 0. 0. 0.]
[ 0. 14. 0. 0.]]
a: [16. 10. 8.]
b: [ 8. 0. 12. 14.]
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[8.0e+00 1.0e+09 1.1e+01 6.0e+00]]
【疊代未完成】
------------------------------------------------------------
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[8.0e+00 1.0e+09 1.1e+01 6.0e+00]]
行罰數： [0.0, 1.0, 2.0]
列罰數： [2.0, 0.0, 1.0, 3.0]
罰數向量： [0.0, 1.0, 2.0, 2.0, 0.0, 1.0, 3.0]
最大罰數： 3.0 元素序号： 7
對第 4 列進行操作：
[11. 9. 6.]
最小成本所在行索引： 2
本次疊代後的x矩陣：
[[ 0. 0. 0. 0.]
[ 0. 0. 0. 0.]
[ 0. 14. 0. 8.]]
a: [16. 10. 0.]
b: [ 8. 0. 12. 6.]
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[4.0e+00 1.0e+09 4.0e+00 1.1e+01]
[2.0e+00 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [0.0, 1.0, 0.0]
列罰數： [2.0, 0.0, 1.0, 2.0]
罰數向量： [0.0, 1.0, 0.0, 2.0, 0.0, 1.0, 2.0]
最大罰數： 2.0 元素序号： 4
對第 1 列進行操作：
[4.e+00 2.e+00 1.e+09]
最小成本所在行索引： 1
本次疊代後的x矩陣：
[[ 0. 0. 0. 0.]
[ 8. 0. 0. 0.]
[ 0. 14. 0. 8.]]
a: [16. 2. 0.]
b: [ 0. 0. 12. 6.]
c:
[[1.0e+09 1.0e+09 4.0e+00 1.1e+01]
[1.0e+09 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[1.0e+09 1.0e+09 4.0e+00 1.1e+01]
[1.0e+09 1.0e+09 3.0e+00 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [7.0, 6.0, 0.0]
列罰數： [0.0, 0.0, 1.0, 2.0]
罰數向量： [7.0, 6.0, 0.0, 0.0, 0.0, 1.0, 2.0]
最大罰數： 7.0 元素序号： 1
對第 1 行進行操作：
[1.0e+09 1.0e+09 4.0e+00 1.1e+01]
最小成本所在列索引： 2
本次疊代後的x矩陣：
[[ 0. 0. 12. 0.]
[ 8. 0. 0. 0.]
[ 0. 14. 0. 8.]]
a: [4. 2. 0.]
b: [0. 0. 0. 6.]
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 9.0e+00]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [999999989.0, 999999991.0, 0.0]
列罰數： [0.0, 0.0, 0.0, 2.0]
罰數向量： [999999989.0, 999999991.0, 0.0, 0.0, 0.0, 0.0, 2.0]
最大罰數： 999999991.0 元素序号： 2
對第 2 行進行操作：
[1.e+09 1.e+09 1.e+09 9.e+00]
最小成本所在列索引： 3
本次疊代後的x矩陣：
[[ 0. 0. 12. 0.]
[ 8. 0. 0. 2.]
[ 0. 14. 0. 8.]]
a: [4. 0. 0.]
b: [0. 0. 0. 4.]
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
【疊代未完成】
------------------------------------------------------------
c:
[[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]
[1.0e+09 1.0e+09 1.0e+09 1.0e+09]]
行罰數： [999999989.0, 0.0, 0.0]
列罰數： [0.0, 0.0, 0.0, 999999989.0]
罰數向量： [999999989.0, 0.0, 0.0, 0.0, 0.0, 0.0, 999999989.0]
最大罰數： 999999989.0 元素序号： 1
對第 1 行進行操作：
[1.0e+09 1.0e+09 1.0e+09 1.1e+01]
最小成本所在列索引： 3
本次疊代後的x矩陣：
[[ 0. 0. 12. 4.]
[ 8. 0. 0. 2.]
[ 0. 14. 0. 8.]]
a: [0. 0. 0.]
b: [0. 0. 0. 0.]
c:
[[1.e+09 1.e+09 1.e+09 1.e+09]
[1.e+09 1.e+09 1.e+09 1.e+09]
[1.e+09 1.e+09 1.e+09 1.e+09]]
【疊代完成】
------------------------------------------------------------
>>>供求平衡<<<
>>>初始基本可行解x*：
[[ 0. 0. 12. 4.]
[ 8. 0. 0. 2.]
[ 0. 14. 0. 8.]]
>>>目前總成本： 244.0
a: (7, 7)
b: (7,)
>>>位勢方程組可解<<<
>>>目前位勢:
{'u1': 0.0, 'u2': -2.0, 'u3': -5.0, 'v1': 4.0, 'v2': 10.0, 'v3': 4.0, 'v4': 11.0}
>>>檢驗表σ：
[[ 0. 2. 0. 0.]
[ 0. 2. 1. 0.]
[ 9. 0. 12. 0.]]
>>>TP已達到最優解<<<
Process finished with exit code 0