【正文】 方案時(shí)，若在(i,j)格填上某數(shù)字后,出現(xiàn)Ai處的余量=Bj處的需量，此時(shí)必須在平衡表上被劃去行和列相應(yīng)位置的任一空格處填上一個(gè)“0”，以滿足數(shù)格=m+n－1個(gè)的需要； iii) 在用閉回路法調(diào)整時(shí)，當(dāng)閉回路上第奇數(shù)次拐角數(shù)有幾個(gè)相同的最小值時(shí)，調(diào)整后只能有一個(gè)空格，其余均要保留數(shù)“0”，以保證數(shù)格=m+n－1個(gè)的需要。以上ii)，iii)均出現(xiàn)退化解。iv) 用最小元素法所得到的初始方案可以不唯一。 二、產(chǎn)銷不平衡的運(yùn)輸?shù)膯栴}及其求解方法 ：產(chǎn)大于銷 產(chǎn)小于銷 ：將不平衡轉(zhuǎn)化為平衡。即當(dāng)時(shí)，考慮在平衡表中增加一虛擬列，表示增加一個(gè)銷貨點(diǎn)(j=n+1)如倉庫，其銷貨量為，且各運(yùn)價(jià)Cin+1=0；當(dāng)時(shí)，考慮在平衡表中增加一虛擬行，表示增加一個(gè)新產(chǎn)地，且各運(yùn)價(jià)Cm+1j=0。然后再用產(chǎn)銷平衡的運(yùn)輸問題的解法進(jìn)行解之。例三、轉(zhuǎn)運(yùn)問題及其解法： ： (1)每個(gè)工廠生產(chǎn)的產(chǎn)品不直接運(yùn)到銷地，可以幾個(gè)產(chǎn)地集中一起運(yùn)。 (2)運(yùn)往各銷地的物資可先運(yùn)給其中的幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其它銷地。 (3)除產(chǎn)、銷地之外，還可以有幾個(gè)中間轉(zhuǎn)運(yùn)站，在產(chǎn)地之間，銷地之間或產(chǎn)銷之間轉(zhuǎn)運(yùn)。凡類似上述情況下的調(diào)運(yùn)物資并使總運(yùn)費(fèi)最小的問題統(tǒng)稱為轉(zhuǎn)運(yùn)問題?！稗D(zhuǎn)運(yùn)問題”的思路是把問題中所有的產(chǎn)地、中轉(zhuǎn)站和銷地都既看作產(chǎn)地，又都看作銷地，把“轉(zhuǎn)運(yùn)問題”變成擴(kuò)大后的產(chǎn)銷平衡的運(yùn)輸問題處理。 “轉(zhuǎn)運(yùn)問題”的方法步驟： (1)建立擴(kuò)大的產(chǎn)銷平衡運(yùn)輸問題單位運(yùn)價(jià)表。其中 1)對(duì)兩地不能直接運(yùn)輸?shù)膯挝贿\(yùn)價(jià)定為M（很大的正數(shù)）； 2)對(duì)所有中轉(zhuǎn)站Tj的產(chǎn)量和銷量定為相等，設(shè)定為； 3)對(duì)產(chǎn)量列的各數(shù)據(jù)可按下式計(jì)算并填入： Ai的產(chǎn)量=ai+q,Tj產(chǎn)量=q，Bj的產(chǎn)量=q 4)對(duì)銷量行的各數(shù)據(jù)可按下式計(jì)算并填入： Aj的產(chǎn)量=q,Tj銷量=q，Bj的銷量=q+bj (2)用表上作業(yè)法進(jìn)行求解 167。2 指派問題及其解法引例任務(wù)人員EJGR甲215134乙1041415丙9141613丁78119當(dāng)指派第i人去完成第j項(xiàng)工作否則 解：設(shè)Xij表示第i人從事第j項(xiàng)工作，且因此，該問題的數(shù)學(xué)模型為MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24 +9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44表示第j項(xiàng)工作只指派人完成表示第i人被指派完成一項(xiàng)工作Xij=0或1(i,j=1,2,3,4)諸如此類，有n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)，但由于每人的專長技術(shù)不同，完成任務(wù)的效率(所費(fèi)時(shí)間_不同，為使完成n項(xiàng)任務(wù)的總效率最高（即所需總時(shí)最少），應(yīng)如何指派（分派）人員的問題統(tǒng)稱為指派（分派）問題。一、指派問題的數(shù)學(xué)模型及其特點(diǎn) ： （1）給定一個(gè)指派問題時(shí)，必須給出效率矩陣（系數(shù)矩陣）C=(Cij)nxn,且Cij179。0，因此必有最優(yōu)解()。 （2）指派問題是一種特殊的平衡的運(yùn)輸問題，由于模型結(jié)構(gòu)的特殊性（看作每產(chǎn)地的產(chǎn)量均為1，每銷地的銷量均為1），故可用更為簡便的匈牙利法進(jìn)行求解。 （3）解矩陣是指派問題的可行解，但不一定是最優(yōu)解。 二、指派問題的解法──匈牙利法 ：對(duì)同一項(xiàng)工作（任務(wù)）j來說，同時(shí)提高或降低每人相同的效率（常數(shù)ti），不影響其最優(yōu)指派；同樣，對(duì)同一個(gè)人i來說，完成各項(xiàng)工作的效率都提高或降低相同的效率（常數(shù)di），也不影響其最優(yōu)指派，因此可得到新的效率矩陣(bij)nxn，其中bij=Cij+ti+dj （對(duì)所有的i,j）則新的目標(biāo)函數(shù)為 其中為常數(shù)這說明Z162。與Z同時(shí)達(dá)到最小值。因而最優(yōu)解相同。故指派問題有以下性質(zhì)：若從效率矩陣(Cij)nxn的一行（列）各元素中分別減去該行（列）的最小元素，得到的新效率矩陣(bij)nxn不改變原指派問題的最優(yōu)解。 三、對(duì)求最大化的指派問題，（即求）,可采用構(gòu)造新的效率矩陣(M－Cij)nxn，其中M=max{Cij}，（顯然M－Cij179。0），將其轉(zhuǎn)化為求所得到的最優(yōu)解就是原問題的最優(yōu)解。事實(shí)上 由于nM為常數(shù)，因此，使Z162。取得最小的最優(yōu)解就是使Z取得最大的最優(yōu)解。，即m+n的情況。當(dāng)m185。n時(shí)，則可用增加虛設(shè)的零元數(shù)行（列）使效率矩陣變成方陣后，再用匈牙利法求解。mn列nm行當(dāng)mn時(shí) 當(dāng)mn時(shí) ，但可以不唯一。 167。3 整數(shù)線性規(guī)劃問題及其解法 一、整數(shù)線性規(guī)劃在上一章討論的LP問題中,對(duì)決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值,即可以是正分?jǐn)?shù)或正小數(shù)。然而在許多經(jīng)濟(jì)管理的實(shí)際問題中，決策變量只有非負(fù)整數(shù)才有實(shí)際意義。對(duì)求整數(shù)最優(yōu)解的問題，稱為整數(shù)規(guī)劃(Integer Programming)(簡記為IP)。又稱約束條件和函數(shù)均為線性的IP為整數(shù)線性規(guī)劃(Integer Linear Programming)(簡記為ILP)。ILP問題數(shù)學(xué)模型的一般形式為：求一組變量X1,X2,…,Xn，使人們對(duì)IP感興趣，還因?yàn)橛行┙?jīng)濟(jì)管理中的實(shí)際問題的解必須滿足如邏輯條件和順序要求等一些特殊的約束條件。此時(shí)需引進(jìn)邏輯變量（又稱01變量），以“0”表示“非”，以“1”表示“是”。凡決策變量均是01變量的IP為01規(guī)劃。嚴(yán)格地說，IP是個(gè)非線性問題。這是因?yàn)镮P的可行解集是由一些離散的非負(fù)整數(shù)所組成，不是一個(gè)凸集。迄今為止，求解IP問題尚無統(tǒng)一的有效方法。求解ILP問題方法的思考：1）“舍入取整”法：即先不考慮整數(shù)性約束，而去求解其相應(yīng)的LP問題（稱為松馳問題），然后將得到的非整數(shù)最優(yōu)解用“舍入取整”的方法。這樣能否得到整數(shù)最優(yōu)解？否！這是因?yàn)椤吧崛肴≌钡慕庖话悴皇窃瓎栴}的最優(yōu)解，甚至是非可行解。但在處理個(gè)別實(shí)際問題是，如果允許目標(biāo)函數(shù)值在某一誤差范圍內(nèi)，有時(shí)也可采用“舍入取整”得到的整數(shù)可行解作為原問題整數(shù)最優(yōu)解的近似。這樣可節(jié)省求解的人力、物力和財(cái)力。設(shè)X*是原ILP的最優(yōu)解，X是其松馳問題的非整數(shù)最優(yōu)解，是“舍入取整”的整數(shù)可行解，d為給出目標(biāo)函數(shù)值的允許誤差。由于163。CX*163。CX所以 CX*－163。CX－當(dāng)CX－163。d時(shí)，則可將作為X*的近似解。2）完全枚舉法 此法僅在決策變量很少的情況下才實(shí)際有效。對(duì)于變量稍多的ILP問題則幾乎不可能。如在指派問題中，當(dāng)n=20，則有可行解20！個(gè)，而20！2X1018，這在計(jì)算機(jī)上也是不可能實(shí)現(xiàn)的。 3）求解ILP問題常見的幾種解法有：分枝定界法，割平面法，01規(guī)劃的特殊解法等。 二、01變量產(chǎn)生的背景和應(yīng)用引例（詳見書P72例2）由引例可見，利用01變量處理一類“可供選擇條件”的問題查非常簡明且方便的。下面再進(jìn)一步分別說明對(duì)01變量的應(yīng)用。假定現(xiàn)有m種資源對(duì)可供選擇的n個(gè)項(xiàng)目進(jìn)行投資的數(shù)學(xué)模型為：求一組決策變量X1,X2,…,Xn，使 （）（）（） 滿足 其中，Cj表示投資第j項(xiàng)獲得的期望收益，aij表示第i種資源投于第j項(xiàng)目數(shù)量，bj表示第i種資源的限量。 （1）如果在可供選擇的前k(k163。n)個(gè)項(xiàng)目中，必須且只能選擇一項(xiàng)，則在()中加入新的約束條件： （2）如果可供選擇的k(k163。n)個(gè)項(xiàng)目是相互排斥的，則在()中加入新的約束條件： 同時(shí)它還表示在第k個(gè)項(xiàng)目中至多只能選擇一項(xiàng)投資。（3）如果在可供選擇的k(k163。n)個(gè)項(xiàng)目中，至少應(yīng)選擇一項(xiàng)投資，則在()中加入新的約束條件：（4）如果項(xiàng)目j的投資必須以項(xiàng)目i的投資為前提，則可在()中加入新的約束條件：Xj163。Xi （5）如果項(xiàng)目i與項(xiàng)目j要么同時(shí)被選中，要么同時(shí)不被選中，則在()中加入新的約束條件：Xj=Xi (i185。j) （1）如果對(duì)第r種資源br與第t種資源bt的投資是相互排斥的，即只允許對(duì)資源br與bt中的一種進(jìn)行投資，則可將()的第r個(gè)和第t個(gè)約束條件改寫為： ① ②其中y為新引進(jìn)的01變量，M為充分大正數(shù)。易見，當(dāng)y=0時(shí)，①式就是原來的第r個(gè)約束條件，具有約束作用。此時(shí)對(duì)②式而方，無論Xj為何值，都成立，毫無約束作用，這就使問題僅允許第r種資源進(jìn)行投資。當(dāng)y=1時(shí)，②式對(duì)Xj起了約束作用，而①式成了多余的條件。到底是滿足①還是②，則視問題在求出最優(yōu)解后，y為0還是1而言。（2）如果問題是要求在前m個(gè)約束條件中至少滿足k(1km)個(gè)，則可將()中的原約束條件修改為：其中M為充分大的正數(shù)，k為整數(shù)。 （詳見書） 三、01規(guī)劃的解法 ：其基本思想是：首先將全部變量取0或1的所有組合（解）列出，然后在逐個(gè)檢查這些組合（解）是否可行的過程中，利用增加并不斷修改過濾條件的辦法，減少計(jì)算量，以達(dá)到求出最優(yōu)解之目的。 例（詳見書） 該法只在變量少的情況下使用才有效。 ： 01規(guī)劃的隱枚舉法是一種特殊的分枝定界法，其基本思想是利用變量只能為0或1兩個(gè)值的特性，進(jìn)行分枝定界，以減少枚舉而達(dá)到求出最優(yōu)解之目的。該法適用于任何01規(guī)劃問題的求解。49 /