目錄

1.算法流程簡介

2.算法核心代碼

3.算法效果展示

1.算法流程簡介

#整數(shù)規(guī)劃模型--匈牙利算法求解
"""
整數(shù)規(guī)劃模型及概念：規(guī)劃問題的數(shù)學(xué)模型一般由三個因素構(gòu)成 決策變量 目標(biāo)函數(shù) 約束條件；線性規(guī)劃即以線性函數(shù)為目標(biāo)函數(shù)，線性條件為約束條件；如果一個線性規(guī)劃模型中的部分或全部決策變量取整數(shù)值，則稱該線性規(guī)劃模型為整數(shù)線性規(guī)劃模型，除此還有非線性整數(shù)規(guī)劃。
整數(shù)規(guī)劃的幾種類型:1:純整數(shù)規(guī)劃：全部決策變量都必須取整數(shù)值的整數(shù)規(guī)劃模型;2:混合整數(shù)規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)規(guī)劃模型;3:0-1整數(shù)規(guī)劃:決策變量只能取0或1的整數(shù)規(guī)劃。
匈牙利算法基本思路:對費用矩陣C的行和列減去某個常數(shù),將C化為有n個位于不同行不同列的零元素,令這些零元素對應(yīng)的變量取1,其余變量取0,即得到指派問題的最優(yōu)解。匈牙利法是基于指派問題的標(biāo)準(zhǔn)型的,標(biāo)準(zhǔn)型需滿足以下3個條件:(1)目標(biāo)函數(shù)求min;(2)效率矩陣為n階方陣;(3)效率矩陣中所有的元素Cij>=0,且為常數(shù)
處理效率矩陣的原則:匈牙利算法的本質(zhì)工作就是處理效率矩陣,時期變的符合一定的輸入要求最終效果:效率矩陣通過一定的變換之后,每行每列都至少存在一個0,記這個矩陣為B。1.如果行列本身就有0,該行列不需要處理2.如果某行沒有0,尋找到該行的min元素,此行都減去min。3.如果某列沒有0,尋找到該列的min元素,此列都減去min。
"""

2.算法核心代碼

#開始求解整數(shù)規(guī)劃問題
from scipy.optimize import linear_sum_assignment
import numpy as np
#1.導(dǎo)入cost/效率矩陣:
cost_arr=np.array([[4,1,3],[2,0,5],[3,2,2]])
n=len(cost_arr)
row_best,col_best=linear_sum_assignment(cost_arr)
print("開銷矩陣最優(yōu)行索引解:",row_best)
print("開銷矩陣最優(yōu)列索引解:",col_best)
#求解最優(yōu)解:
ans=0
best_ans=[]
for i in range(n):ans+=cost_arr[row_best[i]][col_best[i]]best_ans.append(cost_arr[row_best[i]][col_best[i]])
print("最優(yōu)解由",n,"個數(shù)據(jù)進行組成")
for i in range(n):print("第",i+1,"個數(shù)據(jù)是位于開銷矩陣第",row_best[i],"行第",col_best[i],"列的值:",cost_arr[row_best[i]][col_best[i]])
print("綜上所示本題最優(yōu)解組成是:",best_ans)
print("本題規(guī)劃的最優(yōu)解是:",ans)

3.算法效果展示