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