數(shù)學(xué)建模筆記——整數(shù)規(guī)劃類問題之我見（匈牙利算法）

這篇具有很好參考價值的文章主要介紹了數(shù)學(xué)建模筆記——整數(shù)規(guī)劃類問題之我見（匈牙利算法）。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

淺淺敘述匈牙利算法

基本思路

計算步驟

來一道簡單例題

1.1 符號規(guī)定

1.2目標(biāo)函數(shù)?編輯

? ? ? 1.3約束條件

?編輯

1.4代碼

題目復(fù)述

基本假設(shè)

問題分析

符號說明

?模型的建立與求解

模型建立思路

模型建立的過程

建立0-1整數(shù)規(guī)劃模型

?運用匈牙利方法：

代碼實現(xiàn)

?文章來源地址http://www.zghlxwxcb.cn/news/detail-410687.html

基本思路

????????匈牙利法的基本思路:對費用矩陣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)效率矩陣中所有元素Cij20,且為常數(shù)。

計算步驟

匈牙利法的計算步驟:
(1)變換效率矩陣C,使每行每列至少有一個0,變換后的矩陣記為B
●行變換:找出每行min值，該行各元素減去它;
●列變換:找出每列min值，該列各元素減去它;
●若某行列已有0元素，則不用減。

來一道簡單例題

如何安排工作使得成本最低？（注：①每個人只能做一項工作；②每項工作只能分配給一個人做；③所有工作都要安排完。）

表1 不同人對每一項工作收費表

?	第一件	第二件	第三件	第四件	第五件
甲	12	7	9	7	9
乙	8	9	6	6	6
丙	7	17	12	14	9
丁	15	14	6	6	10
戊	4	10	10	10	9

1.1 符號規(guī)定

對上述問題進(jìn)行抽象，首先進(jìn)行如下符號定義

符號? ????????????????????????????????????? 含義

?? C? ????????????????????????????????????? 工人的成本矩陣

?? Cij ???????????????????????????????????? 工人 i對? j工作的收費.

?? Wij ?? ??????????????????????????????? ? 是否將工作 j 配給工作 i ，若是則為 1 ，若否則為 0

?? m?????? ? ?????????????????????????? ?? 工人的數(shù)量

?? n????????????????????????????????????? ? 工作的數(shù)量

1.2目標(biāo)函數(shù)

? ? ? 1.3約束條件

1.4代碼

from scipy.optimize import linear_sum_assignment
#由于python有scipy庫的支持，已經(jīng)有了現(xiàn)成的匈牙利方法，可以直接調(diào)用就行。
import numpy as np
#在使用的過程中，也需要調(diào)用numpy庫使矩陣的建立更簡單
cost_mat = np.array([[12, 7, 9, 7, 9],
                     [8, 9, 6, 6, 6],
                     [7, 17, 12, 14, 9],
                     [15, 14, 6, 6, 10],
                     [4, 10, 7, 10, 9]])
work_idx_ls, pokeman_idx_ls = linear_sum_assignment(cost_mat)
cost = 0
work = ['第一件', '第二件', '第三件', '第四件', "第五件"]
pokeman = ["甲", "乙", "丙", '丁', "戊"]
for work_idx, poken_idx in zip(work_idx_ls, pokeman_idx_ls):
    print(f"工作 {work[work_idx]} 指派給 工人 {pokeman[poken_idx]}")
    cost += cost_mat[work_idx][poken_idx]
print(f"最后消耗  {cost}元!")
#匈牙利法具體的python求解過程放在了文章末尾的py代碼段里，可以自行查看
#實際中可以直接使用scipy庫進(jìn)行求解

那么現(xiàn)在，讓我們來點真家伙吧！

廢話不多說，直接上題

2013年國賽b題第二問

題目復(fù)述

對于重大突發(fā)事件，需要調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實現(xiàn)快速全封鎖。實際中一個平臺的警力最多封鎖一個路口，請給出該區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案。

————————————此處應(yīng)該有數(shù)據(jù)表格，原題數(shù)據(jù)放文章結(jié)尾——————————

基本假設(shè)

1、假設(shè)每個突發(fā)事件需要處理的時間相同。
2、假設(shè)在出警過程中勻速行駛。
3、假設(shè)嫌疑犯逃亡時勻速行駛。
4、假設(shè)嫌疑犯逃離的速度不會大于警察迫捕速度。

問題分析

????????第二小問要求制定A區(qū)交巡警服務(wù)平臺警力合理的調(diào)度方案，調(diào)度全區(qū)20個交巡警服務(wù)平臺的警力資源，對進(jìn)出該區(qū)的13條交通要道實現(xiàn)快速封鎖?？紤]實際中一個平臺的警，力至多能夠封鎖一個路口,對每個路口分配-一個平臺警力進(jìn)行圍堵。
????????當(dāng)突發(fā)事件發(fā)生時，全區(qū)各個服務(wù)點對于交通要道的封鎖是同步進(jìn)行的。由于距離原因，每個服務(wù)點對要封鎖的交通要道所需時間是不同的，最后一個交通要道完成封鎖才算對全區(qū)的封鎖完成。本文考慮按最后完成對交通要道封鎖的時間作為標(biāo)準(zhǔn)，選擇最快完成全區(qū)封鎖的調(diào)度方案?？紤]對20個平臺與13個交通要道進(jìn)行遍歷，計算出每種組合中平臺到達(dá)交通要道的最大時間，將每種組合的最大時間進(jìn)行比較，選取值最小的組合作為交巡警服務(wù)平臺警力的調(diào)度方案。
????????本文考慮采用 0-1整數(shù)規(guī)劃的方法,對20個平臺分配13個交通要道以獲得最合理的調(diào)度方案。對每個平臺分配一個交通要道，并在分配完這些任務(wù)后，使完成全部任務(wù)的總時間為最小。

符號說明

數(shù)學(xué)建模筆記——整數(shù)規(guī)劃類問題之我見（匈牙利算法）

?模型的建立與求解

模型建立思路

????????制定合理的調(diào)度方案，使全區(qū)20個交巡警服務(wù)平臺的警力快速封鎖該區(qū)的13條交通要道，建立0-1整數(shù)規(guī)劃中的不平衡的指派類型模型求解此問。通過建立目標(biāo)函數(shù)和約束條件，利用匈牙利算法尋找最優(yōu)解，即選取完成時間最少的調(diào)度方案。
考慮一個平臺的警力最多封鎖一個路口，調(diào)度A區(qū)20各個交巡警服務(wù)平臺的警力資源對13條
交通要道進(jìn)行全封鎖。全封鎖是參與道路封鎖的各交巡警服務(wù)平臺同時進(jìn)行的以完成封鎖自標(biāo)為標(biāo)準(zhǔn)結(jié)果。但由于各平臺與所要封鎖道路的距離的不同，在警車時速相同的情況下，各平臺的出勤時間是不同的，到達(dá)所要封鎖自的地的時間不同，即結(jié)束封鎖時間不同。計算茁每個方案的結(jié)束時間，選取完成時間最少的方案作為最佳方案。

模型建立的過程

????????建立目標(biāo)函數(shù)本文根據(jù)0-1整數(shù)規(guī)劃中不平衡的指派類型求解此問,將A區(qū)20個交巡警服務(wù)平臺的警力資源分配13條交通要道以實現(xiàn)快速封鎖，設(shè)第i個服務(wù)點完成第j條交通要道的封鎖，給每條交通要道分配一個服務(wù)點進(jìn)行封鎖管理，并要求封鎖完成，以使完成全部任務(wù)的總時間為最小，以此建立目標(biāo)函數(shù)minZ=max T? 式中T表示時間。
????????

建立0-1整數(shù)規(guī)劃模型

①每個服務(wù)點的警力最多封鎖一個交通要道，即>xy = 1,j=1,2.... ,
②每個交通要道為避免警力資源浪費而只需一個服務(wù)點的平臺警力,
即x, =1,i=1,2...n
③對每個交通要道有無服務(wù)點的警力封鎖判斷，即x, = 0,1,其中0為
該交通要道沒有警力封鎖，1為該交通要道有警力封鎖。

數(shù)學(xué)建模筆記——整數(shù)規(guī)劃類問題之我見（匈牙利算法）

?對目標(biāo)函數(shù)進(jìn)行整合，最后最終的函數(shù)為：

數(shù)學(xué)建模筆記——整數(shù)規(guī)劃類問題之我見（匈牙利算法）

?運用匈牙利方法：

這個時候我們再來使用剛剛提到的匈牙利法來進(jìn)行求解

這個時候遇到一個問題:
20個巡警和13個交通路口無法構(gòu)成nx n的矩陣，無法構(gòu)成方陣,則無法進(jìn)行匈牙利法的求解

解決問題的方法:我們補7列0向量，讓其滿足20x 20的方陣，由于補足的列為0，則相當(dāng)于無用工作，不影響最后的結(jié)果。
這個題中
1，要求最小值
2，所有值都是正數(shù)
3，補完以后是方陣

所以可以用匈牙利法來做

針對0- 1整數(shù)規(guī)劃中不平衡的指派問題利用匈牙利法求解,步驟如下:
(1)將系數(shù)矩陣標(biāo)準(zhǔn)化，并變換系數(shù)矩陣，使其各行各列中都出現(xiàn)0元素。將20個交巡警服務(wù)平臺分別與13個交通要道的最短距離列為系數(shù)矩陣Cij，i=1,2...2.0.j=1.2..13.將Cj化為標(biāo)準(zhǔn)型，增加7列虛擬工作0,矩陣的階數(shù)為20。
(2)然后再將Cij系數(shù)矩陣帶入python的程序進(jìn)行求解即可

代碼實現(xiàn)

from json.encoder import INFINITY

import numpy as np
import xlrd
data = xlrd.open_workbook('2011B.xls')
#print("sheets：" + str(data.sheet_names()))  #打印sheets名

table1 = data.sheet_by_name('全市交通路口節(jié)點數(shù)據(jù)')
loc = [] 
 #節(jié)點位置列表
w = [] 
 #發(fā)案率列表           
 
loc.append([0, 0]) 
w.append(0.0)   # 為使索引值和節(jié)點編號對應(yīng)，填入一個數(shù)據(jù)

#讀入A區(qū)各節(jié)點的坐標(biāo)數(shù)據(jù)
for k in range(1, 93):
    x = table1.cell(k, 1).value  #注意，excel里的計數(shù)是從0開始的，和圖像化界面里顯示的不同
    y = table1.cell(k, 2).value
    loc.append([x, y])
    w.append(table1.cell(k, 4).value)

table2 = data.sheet_by_name('全市交通路口的路線')
distance = np.zeros((93, 93), dtype=np.float)

 
for i in range(1, 93):
    for j in range(1, 93):
        if i == j:
            distance[i, j] = 0.0
        else:
            distance[i, j] = INFINITY
 #路程矩陣
for k in range(1, table2.nrows):
    i = int(table2.cell(k, 0).value)
    j = int(table2.cell(k, 1).value)
    #print(i, j)
    if i <= 92 and j <= 92:
        distance[i, j] = np.sqrt((loc[i][0]-loc[j][0])**2 + (loc[i][1]-loc[j][1])**2)
        distance[j, i] = np.sqrt((loc[i][0]-loc[j][0])**2 + (loc[i][1]-loc[j][1])**2)

 #最短距離
for k in range(1, 93):
    for i in range(1, 93):
        for j in range(1, 93):
            if distance[i, k] + distance[k, j] < distance[i, j]:
                distance[i, j] = distance[i, k] + distance[k, j]

time = np.zeros((93, 93), dtype=np.float)
for i in range(1, 93):
    for j in range(1, 93):
        time[i, j] = distance[i, j]/10


filename = 'rask2.txt'
pingtai = range(1, 21)

table3 = data.sheet_by_name('全市區(qū)出入口的位置')
chukou = []
for k in range(1, 14):
    #print(int(table3.cell(k, 2).value))
    chukou.append(int(table3.cell(k, 2).value))
#創(chuàng)建文檔寫入數(shù)據(jù)
with open(filename, 'w') as f: 
    for i in pingtai:
        for j in chukou:
            f.write('%.4f' % time[i, j] +",")
        f.write("\n")

from scipy.optimize import linear_sum_assignment
import numpy as np
cost_mat = np.array([[22.2362,16.0285,9.2868,19.2934,21.0962,22.5018,22.8932,19.0012,19.5158,12.0834,5.8809,11.8501,4.8852,0,0,0,0,0,0,0],
[20.4639,14.1297,7.3881,17.3947,19.1975,20.6030,21.1210,17.2289,17.7436,10.3112,3.9822,10.3095,6.0351,0,0,0,0,0,0,0],
[18.3523,12.7672,6.0256,16.0322,17.8350,19.2405,19.0093,15.1173,15.6319,8.1996,6.0938,8.1979,4.3934,0,0,0,0,0,0,0],
[21.9974,15.0085,8.2669,18.2735,20.0763,21.4818,22.6544,16.2269,15.5353,8.1030,4.8610,7.3959,0.3500,0,0,0,0,0,0,0],
[17.6282,12.9696,6.2280,16.2346,17.7495,19.1551,18.2852,11.3069,10.6153,3.1829,9.4211,2.4758,5.2551,0,0,0,0,0,0,0],
[17.6588,13.0002,6.2586,16.2652,17.7801,19.1856,18.3158,11.3375,10.6459,3.2135,9.4517,2.5064,5.3373,0,0,0,0,0,0,0],
[14.9149,10.9012,4.1596,14.1662,15.0363,16.4418,15.5720,8.5702,8.0155,0.5831,7.3527,1.2902,7.9917,0,0,0,0,0,0,0],
[14.0925,9.4339,2.6923,12.6989,14.2138,15.6194,14.7496,10.2280,10.4932,3.0608,5.8854,3.0995,8.6773,0,0,0,0,0,0,0],
[13.0107,8.2742,1.5325,11.5392,13.1320,14.5376,13.6678,9.7757,10.7244,3.4923,4.7257,4.1994,9.3367,0,0,0,0,0,0,0],
[7.5866,12.7757,6.9567,9.5107,7.7079,9.1135,8.2436,14.1949,15.1435,7.9114,10.1498,8.6186,14.7608,0,0,0,0,0,0,0],
[3.7914,8.3373,11.3950,5.0723,3.2696,4.6751,3.8053,18.6332,19.5819,12.3498,14.5882,13.0569,19.1992,0,0,0,0,0,0,0],
[0.0000,11.9503,14.5433,8.6853,6.8825,6.4770,3.5916,21.7814,22.7301,15.4980,17.7364,16.2051,22.3474,0,0,0,0,0,0,0],
[5.9770,5.9733,12.7149,2.7083,0.9055,0.5000,2.3854,22.8083,23.7570,16.5249,16.1208,17.2320,21.3318,0,0,0,0,0,0,0],
[11.9503,0.0000,6.7417,3.2650,5.0677,6.4733,8.3587,18.0499,18.9167,11.4843,10.1475,12.1914,15.3585,0,0,0,0,0,0,0],
[17.0296,13.2981,6.5564,16.5630,17.1509,18.5565,17.6867,4.7518,5.7005,4.4015,9.7496,5.1086,11.8101,0,0,0,0,0,0,0],
[14.5433,6.7417,0.0000,10.0066,11.8094,13.2149,15.1003,11.3083,12.1750,4.7427,3.4059,5.4498,8.6169,0,0,0,0,0,0,0],
[21.8921,14.9032,8.1616,18.1682,19.9710,21.3765,22.5492,18.6571,19.5239,12.0915,4.7557,12.7986,7.8205,0,0,0,0,0,0,0],
[24.2472,18.5145,11.7728,21.7795,23.5822,24.9878,24.9042,21.0122,21.5268,14.0945,8.3669,13.6993,6.7344,0,0,0,0,0,0,0],
[22.5465,16.9615,10.2198,20.2264,22.0292,23.4348,23.2036,19.3115,19.8262,12.3938,7.6393,11.9986,5.0337,0,0,0,0,0,0,0],
[26.9458,21.2131,14.4714,24.4781,26.2809,27.6864,27.6029,23.0108,22.3192,14.8869,11.0656,14.1798,6.4489,0,0,0,0,0,0,0]])
work_idx_ls, pokeman_idx_ls = linear_sum_assignment(cost_mat)
cost = 0
work = ['a1', 'a2', 'a3', 'a4', "a5",'a6','a7','a8','a9','a10','a11','a12','a13']
pokeman = ["1", "2", "3", '4', "5",'6','7','8','9','10','11','12','13','14','15','16','17','18','19','20']
filename = '最后的結(jié)果.txt'

for work_idx, poken_idx in zip(work_idx_ls, pokeman_idx_ls):
    print(f"交通 {work[work_idx]} 指派給 警察 {pokeman[poken_idx]}")
    cost += cost_mat[work_idx][poken_idx]
print(f"最后消耗  {cost}時間!")

2011年數(shù)學(xué)建模國賽b題附件數(shù)據(jù)

https://download.csdn.net/download/aichi_shaqima/86438453

到了這里，關(guān)于數(shù)學(xué)建模筆記——整數(shù)規(guī)劃類問題之我見（匈牙利算法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！