通過(guò)前兩期的學(xué)習(xí)，我們已經(jīng)學(xué)會(huì)了整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型、割平面法和分支定界法。本期小編帶大家學(xué)習(xí)0-1整數(shù)問(wèn)題和指派問(wèn)題。

一 0-1整數(shù)規(guī)劃

01定義

0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量xj僅取值0或1。這種只能取0或1的變量稱為0-1變量或二進(jìn)制變量。例如

當(dāng)問(wèn)題含有多項(xiàng)限制要素E1,E2,…,En，其中每項(xiàng)都有兩種選擇時(shí)，可令

若遇到變量可以取多個(gè)整數(shù)值時(shí)，可以用一組0-1變量取代該變量。例如，變量x可取0與9之間的任意整數(shù)時(shí)，可令

其中，x0，x1，x2，x3皆為0-1變量。

02應(yīng)用

案例1 含有互斥約束條件的問(wèn)題?

案例2 固定費(fèi)用問(wèn)題??

案例3 工件排序問(wèn)題?

?03解法

? ? ? 對(duì)于0-1型整數(shù)規(guī)劃，一般采用隱枚舉法，而不必采用完全枚舉法：

? ? ?1、只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。

? ? ?2、若已發(fā)現(xiàn)一個(gè)可行解，則可根據(jù)它的目標(biāo)函數(shù)值產(chǎn)生一個(gè)過(guò)濾條件，對(duì)于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性；在以后的求解中，每當(dāng)發(fā)現(xiàn)更好的可行解，則以此替換原來(lái)的過(guò)濾條件。

案例4?

二 指派問(wèn)題

01數(shù)學(xué)模型

02 匈牙利解法

? ? ? 1955年，庫(kù)恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問(wèn)題的一種算法，稱為匈牙利解法。

?★核心思想

? ? ? ?若從指派問(wèn)題的系數(shù)矩陣C的某行（或某列）各元素分別減去一個(gè)常數(shù)k，得到一個(gè)新的矩陣C’，則以C’和C為系數(shù)矩陣的兩個(gè)指派問(wèn)題有相同的最優(yōu)解。這是由于系數(shù)矩陣的變化并不影響數(shù)學(xué)模型的約束方程組，只是目標(biāo)函數(shù)值減少了常數(shù)k，所以最優(yōu)解不變。

★ 匈牙利解法步驟

? ? ? ?1、變換系數(shù)矩陣，先對(duì)各行元素分別減去本行中的最小元素，再對(duì)各列元素分別減去本列最小元素，從而保證系數(shù)矩陣中每行及每列中至少有一個(gè)零元素。

? ? ? ?2、在變換后的系數(shù)矩陣中確定獨(dú)立零元素。若獨(dú)立零元素有n個(gè)，則已得出最優(yōu)解；若獨(dú)立零元素少于n個(gè)，則做能覆蓋所有零元素的最少直線數(shù)目的直線集合。

? ? （1）對(duì)沒(méi)有?的行打√號(hào)；

? ? （2）對(duì)已打√號(hào)的行中所有被劃去0元素的所在列打√號(hào)；

? ? （3）再對(duì)打有√號(hào)的列中?中0元素的所在行打√號(hào)；

? ? （4）重復(fù)(2)(3)，直到得不出新的打√號(hào)的行(列)為止；

? ? （5）對(duì)沒(méi)有打√號(hào)的行畫橫線，對(duì)打√號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)目的直線集合。

? ? ? 3、繼續(xù)變換系數(shù)矩陣，在未被直線覆蓋的元素中找出一個(gè)最小元素，對(duì)未被覆蓋的元素所在行（或列）中各元素都減去這一最小元素。對(duì)出現(xiàn)負(fù)元素的行或列都加上這一最小元素。返回步驟2。

案例5?

? ? ? 求表中所示效率矩陣的指派問(wèn)題的最小解

03 非標(biāo)準(zhǔn)形式的指派問(wèn)題

核心思想

? ? ? ?對(duì)于非標(biāo)準(zhǔn)形式的指派問(wèn)題，通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式然后求解。

★最大化指派問(wèn)題

? ? ? ?當(dāng)面對(duì)最大化指派問(wèn)題，可以從系數(shù)矩陣C中，找出最大元素m，用m減去矩陣C中所有元素得到系數(shù)矩陣B，則以B為系數(shù)矩陣的最小化指派問(wèn)題和以C為系數(shù)矩陣的原最大化指派問(wèn)題有相同最優(yōu)解。

★ 人數(shù)和事數(shù)不等的指派問(wèn)題

? ? ? 若人數(shù)少事件多，添上虛擬的人，費(fèi)用系數(shù)值為0。

? ? ? 若事件少人數(shù)多，添上虛擬的事件，費(fèi)用系數(shù)值為0。

★ 一個(gè)人可做幾件事的指派問(wèn)題

? ? ? 將該人化作相同的幾個(gè)人來(lái)接受指派，這幾個(gè)人做同一事件的費(fèi)用系數(shù)都一樣。

★ 某事一定不能由某人做的指派問(wèn)題

? ? ? 若某事一定不能由某人做，將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M。

? ? ? ?以上就是關(guān)于0-1整數(shù)規(guī)劃和指派問(wèn)題的全部?jī)?nèi)容了，學(xué)習(xí)完這一節(jié)，大家可以試著對(duì)一些實(shí)際問(wèn)題進(jìn)行應(yīng)用練習(xí)。下一次小編將帶大家學(xué)習(xí)第六章——非線性規(guī)劃，敬請(qǐng)關(guān)注！? ?

作者 | 陳優(yōu) 王連聚

責(zé)編 | 劉文志

審核 | 徐小峰