運(yùn)籌學(xué)(整數(shù)規(guī)劃)

運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件整數(shù)線性規(guī)劃IntegerLinearProgramming整數(shù)規(guī)劃

(IntegerProgramming)整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃算法分配問題與匈牙利法計(jì)算軟件應(yīng)用案例本章主要內(nèi)容：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃（簡稱：IP）

要求一部分或全部決策變量取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)規(guī)劃問題的松弛問題。若該松弛問題是一個(gè)線性規(guī)劃，則稱該整數(shù)規(guī)劃為整數(shù)線性規(guī)劃。整數(shù)線性規(guī)劃數(shù)學(xué)模型的一般形式：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)線性規(guī)劃問題的種類：純整數(shù)線性規(guī)劃：指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃?；旌险麛?shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃。

0-1型整數(shù)線性規(guī)劃：決策變量只能取值0或1的整數(shù)線性規(guī)劃。線性整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型0-1整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型?íì33T為整數(shù)xxbAxtsxc,0..min

0-1整數(shù)規(guī)劃模型?íì==3TnixbAxtsxci,...,2,1;1,0..min

混合整數(shù)規(guī)劃模型整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃的典型例子例1工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1,B2,B3,B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各工廠至各需求地的單位物資運(yùn)費(fèi)cij，見下表：B1B2B3B4年生產(chǎn)能力A12934400A28357600A37612200A44525200年需求量350400300150工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬或1500萬元。現(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用最少。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用解：這是一個(gè)物資運(yùn)輸問題，特點(diǎn)是事先不能確定應(yīng)該建A3還是A4中哪一個(gè)，因而不知道新廠投產(chǎn)后的實(shí)際生產(chǎn)物資。為此，引入0-1變量：再設(shè)xij為由Ai運(yùn)往Bj的物資數(shù)量，單位為千噸；z表示總費(fèi)用，單位萬元。則該規(guī)劃問題的數(shù)學(xué)模型可以表示為：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用混合整數(shù)規(guī)劃問題整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用例2現(xiàn)有資金總額為B。可供選擇的投資項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj（j＝1,2,..,n），此外由于種種原因，有三個(gè)附加條件：若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2。反之不一定項(xiàng)目3和4中至少選擇一個(gè)；項(xiàng)目5,6,7中恰好選擇2個(gè)。應(yīng)該怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用解：對每個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能，因此分別用0和1表示，令xj表示第j個(gè)項(xiàng)目的決策選擇，記為：投資問題可以表示為：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用例3指派問題或分配問題。人事部門欲安排四人到四個(gè)不同崗位工作，每個(gè)崗位一個(gè)人。經(jīng)考核四人在不同崗位的成績（百分制）如表所示，如何安排他們的工作使總成績最好。工作人員ABCD甲85927390乙95877895丙82837990丁86908088整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用設(shè)數(shù)學(xué)模型如下：要求每人做一項(xiàng)工作，約束條件為：整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用每項(xiàng)工作只能安排一人，約束條件為：變量約束：背包問題背景案例模型背景郵遞包裹把形狀可變的包裹用盡量少的車輛運(yùn)走旅行背包容量一定的背包里裝盡可能的多的物品實(shí)例某人出國留學(xué)打點(diǎn)行李，現(xiàn)有三個(gè)旅行包，容積大小分別為1000毫升、1500毫升和2000毫升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有7件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有10件可帶可不帶物品，如果不帶將在目的地購買，通過網(wǎng)絡(luò)查詢可以得知其在目的地的價(jià)格（單位美元）。這些物品的容量及價(jià)格分別見下表，試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里。

物品12345678910體積200350500430320120700420250100價(jià)格1545100705075200902030實(shí)例問題分析變量—對每個(gè)物品要確定是否帶同時(shí)要確定放在哪個(gè)包裹里，如果增加一個(gè)虛擬的包裹把不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在包裹的編號(hào)，則每個(gè)包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們設(shè)變量為第i個(gè)物品是否放在第j個(gè)包裹中約束條件包裹容量限制必帶物品限制選帶物品限制目標(biāo)函數(shù)—未帶物品購買費(fèi)用最小模型特征—變量整數(shù)性要求來源

問題本身的要求引入的邏輯變量的需要性質(zhì)—可行域是離散集合整數(shù)規(guī)劃的特點(diǎn)整數(shù)規(guī)劃的特點(diǎn)整數(shù)規(guī)劃的特點(diǎn)整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題解的特征：整數(shù)規(guī)劃問題的可行解集合是它松弛問題可行解集合的一個(gè)子集，任意兩個(gè)可行解的凸組合不一定滿足整數(shù)約束條件，因而不一定仍為可行解。整數(shù)規(guī)劃問題的可行解一定是它的松弛問題的可行解（反之不一定），但其最優(yōu)解的目標(biāo)函數(shù)值不會(huì)優(yōu)于后者最優(yōu)解的目標(biāo)函數(shù)值。與線性規(guī)劃的關(guān)系整數(shù)規(guī)劃放松的線性規(guī)劃可行解是放松問題的可行解最優(yōu)值大于等于放松問題的最優(yōu)值整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用例4設(shè)整數(shù)規(guī)劃問題如下首先不考慮整數(shù)約束，得到線性規(guī)劃問題（一般稱為松弛問題）。整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用用圖解法求出最優(yōu)解為：x1＝3/2,x2=10/3，且有Z=29/6 現(xiàn)求整數(shù)解(最優(yōu)解):如用舍入取整法可得到4個(gè)點(diǎn)即(1,3),(2,3),(1,4),(2,4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。x1x2⑴⑵33(3/2,10/3) 按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個(gè)有限集，如右圖所示。其中(2,2),(3,1)點(diǎn)的目標(biāo)函數(shù)值最大，即為Z=4。注釋最優(yōu)解不一定在頂點(diǎn)上達(dá)到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多余于頂點(diǎn)，枚舉法不可取整數(shù)規(guī)劃的特點(diǎn)及應(yīng)用整數(shù)規(guī)劃問題的求解方法：分支定界法和割平面法匈牙利法（指派問題）分支定界算法算法思想算法步驟算例注釋算法思想隱枚舉法求解放松問題最優(yōu)值比界壞最優(yōu)解為整數(shù)最優(yōu)值比界好最優(yōu)解為非整數(shù)最優(yōu)值比界好分支邊界分支舍棄分支定界法1）求整數(shù)規(guī)劃的松弛問題最優(yōu)解； 若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解,否則轉(zhuǎn)下一步；2）分支與定界： 任意選一個(gè)非整數(shù)解的變量xi，在松弛問題中加上約束：xi≤[xi]和xi≥[xi]+1組成兩個(gè)新的松弛問題，稱為分枝。新的松弛問題具有特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分枝問題的上界；當(dāng)原問題是求最小值時(shí)，目標(biāo)值是分枝問題的下界。 檢查所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值大于（max）等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計(jì)算，若還存在非整數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分枝，再檢查，直到得到最優(yōu)解。分支定界法的解題步驟：分支定界法例5用分枝定界法求解整數(shù)規(guī)劃問題解：首先去掉整數(shù)約束，變成一般線性規(guī)劃問題(原整數(shù)規(guī)劃問題的松馳問題)LPIP分支定界法用圖解法求松弛問題的最優(yōu)解，如圖所示。x1x2⑴⑵3(18/11,40/11)⑶21123x1＝18/11,x2=40/11Z=－218/11≈(－19.8)即Z也是IP最小值的下限。對于x1＝18/11≈1.64，取值x1≤1，x1≥2對于x2=40/11≈3.64，取值x2≤3，x2≥4先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2分支定界法分支：分別求出（LP1）和（LP2）的最優(yōu)解。分支定界法先求LP1,如圖所示。此時(shí)在B點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)＝－16找到整數(shù)解，問題已探明，此枝停止計(jì)算。x1x2⑴⑵33(18/11,40/11)⑶11BAC同理求LP2,如圖所示。在C

點(diǎn)取得最優(yōu)解。即:x1＝2,x2=10/3,Z(2)＝－56/3≈－18.7∵Z(2)<Z(1)＝－16∴原問題有比－16更小的最優(yōu)解，但x2不是整數(shù)，故繼續(xù)分支。分支定界法在IP2中分別再加入條件：x2≤3,x2≥4得下式兩支：分別求出LP21和LP22的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACD先求LP21,如圖所示。此時(shí)D在點(diǎn)取得最優(yōu)解。即x1＝12/5≈2.4,x2=3,Z(21)＝-87/5≈-17.4<Z(1)=-16但x1＝12/5不是整數(shù)，可繼續(xù)分枝。即3≤x1≤2。求LP22，如圖所示。無可行解，故不再分枝。分支定界法在（LP21）的基礎(chǔ)上繼續(xù)分枝。加入條件3≤x1≤2有下式：分別求出（LP211）和（LP212）的最優(yōu)解分支定界法x1x2⑴⑵33(18/11,40/11)⑶11BACDEF先求（LP211）,如圖所示。此時(shí)在E點(diǎn)取得最優(yōu)解。即x1＝2,x2=3,Z(211)＝－17找到整數(shù)解，問題已探明，此枝停止計(jì)算。求（LP212），如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。即x1＝3,x2=2.5,Z(212)＝－31/2≈－15.5>Z(211)

如對LP212繼續(xù)分解，其最小值也不會(huì)低于－15.5，問題探明,剪枝。分支定界法原整數(shù)規(guī)劃問題的最優(yōu)解為:x1=2,x2=3,Z*=－17以上的求解過程可以用一個(gè)樹形圖表示如右：LP1x1=1,x2=3Z(1)＝－16LPx1=18/11,x2=40/11Z(0)＝－19.8LP2x1=2,x2=10/3Z(2)＝－18.5LP21x1=12/5,x2=3Z(21)＝－17.4LP22無可行解LP211x1=2,x2=3Z(211)＝－17LP212x1=3,x2=5/2Z(212)＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃分支定界法例6用分枝定界法求解解:先求對應(yīng)的松弛問題（記為LP0）用圖解法得到最優(yōu)解X＝(3.57,7.14),Z0=35.7,如下圖所示。分支定界法1010松弛問題LP0的最優(yōu)解X=(3.57,7.14),Z0=35.7x1x2oABC分支定界法10x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8①②LP2:X=(4,6.5),Z2=35.5分支定界法10x1x2oABCLP1LP2134LP21:X=(4.33,6),Z21=35.336分支定界法10x1x2oACLP1346LP211:X=(4,6),Z211=34LP212:X=(5,5),Z212=355LP212分支定界法上述分枝過程可用下圖表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP21:X=(4.33,6)Z21=35.33x2≤6LP211:X=(4,6)Z211=34LP212:X=(5,5)Z212=35x1≤4x1≥5LP22無可行解x2≥7分支的方法分支的方法定界當(dāng)前得到的最好整數(shù)解的目標(biāo)函數(shù)值分支后計(jì)算放松的線性規(guī)劃的最優(yōu)解★整數(shù)解且目標(biāo)值小于原有最好解的值則替代原有最好解★整數(shù)解且目標(biāo)值大于原有最好解的值則刪除該分支其中無最優(yōu)解★非整數(shù)解且目標(biāo)值小于原有最好解的值則繼續(xù)分支★非整數(shù)解且目標(biāo)值大于等于原有最好解的值則刪除該分支其中無最優(yōu)解注釋求解混合整數(shù)規(guī)劃問題，只對整數(shù)變量分支，對非整數(shù)變量不分支。對0-1整數(shù)規(guī)劃分支時(shí)小結(jié)學(xué)習(xí)要點(diǎn)：掌握一般整數(shù)規(guī)劃問題概念及模型結(jié)構(gòu)掌握分支定界法原理能夠用分支定界法求解一般整數(shù)規(guī)劃問題課后練習(xí)：算法思想算法步驟算例割平面算法算法思想由放松問題的可行域向整數(shù)規(guī)劃的可行域逼近方法—利用超平面切除要求整數(shù)解保留放松問題最優(yōu)值增加割平面生成方法條件--保留整數(shù)解刪除最優(yōu)解整數(shù)可行解最優(yōu)基可行解割平面生成方法割平面生成方法割平面生成方法割平面生成方法割平面生成方法割平面生成方法正則解割平面生成方法算法步驟求放松問題的最優(yōu)基可行解判斷是否為整數(shù)解是停止得到最優(yōu)解否在單純性表中加入一行一列利用對偶單純性算法求最優(yōu)解算例(1,1.5)算例算例算例算例算例算例計(jì)算軟件整數(shù)變量定義LinGo

一般整數(shù)變量:@GIN(variable_name);0-1整數(shù)變量：@BIN(variable_name);算例算例

max=3*x1+5*x2+4*x3;2*x1+3*x2<=1500;2*x2+4*x3<=800;3*x1+2*x2+5*x3<=2000;@gin（x1）;@gin（x3）;分配問題與匈牙利法指派問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式： 設(shè)n個(gè)人被分配去做n件工作，規(guī)定每個(gè)人只做一件工作，每件工作只有一個(gè)人去做。已知第i個(gè)人去做第j件工作的效率（時(shí)間或費(fèi)用）為Cij(i=1.2…n;j=1.2…n)并假設(shè)Cij≥0。問應(yīng)如何分配才能使總效率（時(shí)間或費(fèi)用）最高？設(shè)決策變量

分配問題與匈牙利法指派問題的數(shù)學(xué)模型為：分配問題與匈牙利法克尼格定理

:

如果從分配問題效率矩陣[aij]的每一行元素中分別減去(或加上)一個(gè)常數(shù)ui，從每一列中分別減去(或加上)一個(gè)常數(shù)vj，得到一個(gè)新的效率矩陣[bij]，則以[bij]為效率矩陣的分配問題與以[aij]為效率矩陣的分配問題具有相同的最優(yōu)解。分配問題與匈牙利法指派問題的求解步驟：1)變換指派問題的系數(shù)矩陣(cij)為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即從(cij)的每行元素都減去該行的最小元素；再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2)進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。分配問題與匈牙利法找獨(dú)立0元素，常用的步驟為：從只有一個(gè)0元素的行開始，給該行中的0元素加圈，記作◎。然后劃去◎所在列的其它0元素，記作?；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進(jìn)行到最后一行。從只有一個(gè)0元素的列開始（畫?的不計(jì)在內(nèi)），給該列中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作?，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進(jìn)行到最后一列。若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。分配問題與匈牙利法若◎元素的數(shù)目m等于矩陣的階數(shù)n（即：m＝n），那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。3)用最少的直線通過所有0元素。其方法：

對沒有◎的行打“√”；對已打“√”

的行中所有含?元素的列打“√”

；再對打有“√”的列中含◎元素的行打“√”

；重復(fù)①、②直到得不出新的打√號(hào)的行、列為止；對沒有打√號(hào)的行畫橫線，有打√號(hào)的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。注：l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第2步，另行試指派；若l＝m<n，表示還不能確定最優(yōu)指派方案，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第4步。分配問題與匈牙利法4)變換矩陣(bij)以增加0元素 在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第2步。分配問題與匈牙利法例7有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？任務(wù)人員ABCD甲67112乙4598丙31104丁5982分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。－52）試指派（找獨(dú)立0元素）◎◎◎??找到3個(gè)獨(dú)立零元素但m=3<n=

4分配問題與匈牙利法3）作最少的直線覆蓋所有0元素

◎◎◎??√√√獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l，即l＝m=3<n=4；4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。得到新的矩陣，重復(fù)2）步進(jìn)行試指派分配問題與匈牙利法000000試指派◎◎◎??◎得到4個(gè)獨(dú)立零元素，所以最優(yōu)解矩陣為：即完成4個(gè)任務(wù)的總時(shí)間最少為：2＋4＋1+8=15分配問題與匈牙利法例8已知四人分別完成四項(xiàng)工作所需時(shí)間如下表，求最優(yōu)分配方案。任務(wù)人員ABCD甲215134乙1041415丙9141613丁78119分配問題與匈牙利法解：1）變換系數(shù)矩陣，增加0元素。◎?◎??◎◎2）試指派（找獨(dú)立0元素）獨(dú)立0元素的個(gè)數(shù)為4,指派問題的最優(yōu)指派方案即為甲負(fù)責(zé)D工作，乙負(fù)責(zé)B工作，丙負(fù)責(zé)A工作，丁負(fù)責(zé)C工作。這樣安排能使總的工作時(shí)間最少，為4＋4＋9＋11＝28。分配問題與匈牙利法例9已知五人分別完成五項(xiàng)工作耗費(fèi)如下表，求最優(yōu)分配方案。任務(wù)人員ABCDE甲759811乙9127119丙85468丁73696戊467511分配問題與匈牙利法-1-2解：1）變換系數(shù)矩陣，增加0元素。分配問題與匈牙利法◎?◎◎◎??2）試指派（找獨(dú)立0元素）獨(dú)立0元素的個(gè)數(shù)l＝4<5，故畫直線調(diào)整矩陣。分配問題與匈牙利法◎?◎◎◎??√√√選擇直線外的最小元素為1；直線外元素減1，直線交點(diǎn)元素加1，其他保持不變。分配問題與匈牙利法◎?◎?◎?◎?√√√√√√√l=m=4<n=5選擇直線外最小元素為1，直線外元素減1，直線交點(diǎn)元素加1，其他保持不變，得到新的系數(shù)矩陣。分配問題與匈牙利法◎??◎??◎?◎?◎總費(fèi)用為=5+7+6+6+4=28注：此問題有多個(gè)最優(yōu)解分配問題與匈牙利法◎??◎??◎?◎?◎總費(fèi)用為=7+9+4+3+5=28分配問題與匈牙利法◎??◎??◎?◎?◎總費(fèi)用為=8+9+4+3+4=28分配問題與匈牙利法課堂練習(xí)：用匈牙利法求解下列指派問題。練習(xí)1：練習(xí)2：分配問題與匈牙利法4821答案：分配問題與匈牙利法非標(biāo)準(zhǔn)型的指派問題：匈牙利法的條件是：模型求最小值、效率cij≥0。當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時(shí)，處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解。分配問題與匈牙利法1.最大化指派問題處理方法：設(shè)m為最大化指派問題系數(shù)矩陣C中最大元素。令矩陣B＝（m-cij）nn則以B為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解。例10

某人事部門擬招聘4人任職4項(xiàng)工作，對他們綜合考評(píng)的得分如下表（滿分100分），如何安排工作使總分最多。分配問題與匈牙利法解:M＝95，令用匈牙利法求解C’，最優(yōu)解為：即甲安排做第二項(xiàng)工作、乙做第三項(xiàng)、丙做第四項(xiàng)、丁做第三項(xiàng),最高總分Z＝92＋95＋90＋80＝357分配問題與匈牙利法2.不平衡的指派問題

當(dāng)人數(shù)m大于工作數(shù)n時(shí)，加上m－n項(xiàng)虛擬工作，例如：

當(dāng)人數(shù)m小于工作數(shù)n時(shí)，加上n－m個(gè)人，例如分配問題與匈牙利法3.一個(gè)人可做幾件事的指派問題若某人可做幾件事，則將該人化作相同的幾個(gè)“人”來接受指派，且費(fèi)用系數(shù)取值相同。例如：丙可以同時(shí)任職A和C工作，求最優(yōu)指派方案。分配問題與匈牙利法4.某事一定不能由某人做的指派問題將該人做此事的效率系數(shù)取做足夠大的數(shù)，可用M表示。例11分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)E必須完成，其他4項(xiàng)中可任選3項(xiàng)完成。試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁2442362345分配問題與匈牙利法解:1)這是不平衡的指派問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。2)由于任務(wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因?yàn)楣ぷ鱁必須完成，故設(shè)戊完成E的時(shí)間為M（M為非常大的數(shù)），其余效率系數(shù)為0，則標(biāo)準(zhǔn)型的效率矩陣表示為：任務(wù)人員ABCDE甲2529314237乙3938262033丙3427284032丁2442362345戊0000M分配問題與匈牙利法用匈牙利法求出最優(yōu)指派方案為：即甲－B，乙－D，丙－E，?。瑼,任務(wù)C放棄。最少時(shí)間為105。人力資源分配問題某個(gè)中型百貨商場對售貨人員（周工資200元）的需求經(jīng)統(tǒng)計(jì)如下表

為了保證銷售人員充分休息，銷售人員每周工作5天，休息2天。問應(yīng)如何安排銷售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最?。啃瞧谝欢奈辶呷藬?shù)12151214161819應(yīng)用案例分析模型假設(shè)每天工作8小時(shí)，不考慮夜班的情況；每個(gè)人的休息時(shí)間為連續(xù)的兩天時(shí)間；每天安排的人員數(shù)不得低于需求量，但可以超過需求量問題分析因素：不可變因素：需求量、休息時(shí)間、單位費(fèi)用；可變因素：安排的人數(shù)、每人工作的時(shí)間、總費(fèi)用；方案：確定每天工作的人數(shù)，由于連續(xù)休息2天，當(dāng)確定每個(gè)人開始休息的時(shí)間就等于知道工作的時(shí)間，因而確定每天開始休息的人數(shù)就知道每天開始工作的人數(shù)，從而求出每天工作的人數(shù)。變量：每天開始休息的人數(shù)約束條件：

1.每人休息時(shí)間2天，自然滿足。

2.每天工作人數(shù)不低于需求量，第i天工作的人數(shù)就是從第i-2天往前數(shù)5天內(nèi)開始工作的人數(shù)，所以有約束：

3.變量非負(fù)約束：約束條件目標(biāo)函數(shù)：總費(fèi)用最小，總費(fèi)用與使用的總?cè)藬?shù)成正比。由于每個(gè)人必然在且僅在某一天開始休息，所以總?cè)藬?shù)等于page113目標(biāo)函數(shù)模型Globaloptimalsolutionfoundatiteration:9Objectivevalue:4400.000VariableValueReducedCostX15.0000000.000000X22.0000000.000000X38.0000000.000000X40.0000000.000000X54.0000000.000000X60.00000066.66667X73.0000000.000000結(jié)果

RowSlackorSurplusDualPrice14400.000-1.00000022.0000000.00000030.000000-66.6666740.0000000.00000050.000000-66.6666762.0000000.00000070.000000-66.6666780.000000-66.66667結(jié)果注解該問題本質(zhì)上是個(gè)整數(shù)規(guī)劃問題，放松的線性規(guī)劃的最優(yōu)解是個(gè)整數(shù)解，所以兩規(guī)劃等價(jià)。定義整數(shù)變量用函數(shù)@gin(x1)……@gin(x7);

0-1整數(shù)變量為@bin(x1)運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型例12某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷地B1,B2,B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷量150150200運(yùn)輸規(guī)劃問題的數(shù)學(xué)模型解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝500

設(shè)xij

為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，得到下列運(yùn)輸量表：B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200MinC=6x11+4x12+6x13+6x21+5x22+5x23

s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200

xij≥0(i=1、2；j=1、2、3）運(yùn)輸問題的應(yīng)用生產(chǎn)與儲(chǔ)存問題例13某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。季度生產(chǎn)能力/臺(tái)單位成本/萬元Ⅰ2510.8Ⅱ3511.1Ⅲ3011Ⅳ1011.3運(yùn)輸問題的應(yīng)用解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：

x11=10生產(chǎn)：x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35x13+x23+x33=25x33+x34≤30x14+x24+x34+x44=20x44≤10把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷售點(diǎn)的銷量；設(shè)cij是第i季度生產(chǎn)的第j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本，應(yīng)該等于該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用?？蓸?gòu)造下列產(chǎn)銷平衡問題：運(yùn)輸問題的應(yīng)用

jiⅠⅡⅢⅣ產(chǎn)量Ⅰ10.810.9511.111.2525ⅡM11.1011.2511.4035ⅢMM11.0011.1530ⅣMMM11.3010銷量1015252010070由于產(chǎn)大于銷，加上一個(gè)虛擬的銷地D，化為平衡問題，即可應(yīng)用表上作業(yè)法求解。運(yùn)輸問題的應(yīng)用該問題的數(shù)學(xué)模型：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23 +11.4x24+11.0x33+11.15x34+11.3x44

jiⅠⅡⅢⅣD產(chǎn)量Ⅰ10.810.9511.111.25025ⅡM11.1011.2511.40035ⅢMM11.0011.15030ⅣMMM11.30010銷量1015252030100100運(yùn)輸問題的應(yīng)用

jiⅠⅡⅢⅣD產(chǎn)量Ⅰ1010525Ⅱ5003035Ⅲ201030Ⅳ1010銷量1015252030100100最優(yōu)生產(chǎn)決策如下表，最小費(fèi)用z＝767.8萬元。Globaloptimalsolutionfoundatiteration:4Objectivevalue:775.0000VariableValueReducedCostX1110.000000.000000