高級(jí)運(yùn)籌學(xué)習(xí)題解析與解答手冊(cè)1.寫(xiě)出其對(duì)偶問(wèn)題（D）。2.已知（P）的最優(yōu)解為x?*=1,x?*=-2,x?*=2，利用互補(bǔ)松弛條件求對(duì)偶問(wèn)題（D）的最優(yōu)解。解析與解答：第1問(wèn)：構(gòu)造對(duì)偶問(wèn)題（D）構(gòu)造對(duì)偶問(wèn)題，需遵循“原問(wèn)題與對(duì)偶問(wèn)題的對(duì)應(yīng)關(guān)系”，特別注意變量的符號(hào)約束與約束條件類(lèi)型之間的轉(zhuǎn)換。原問(wèn)題（P）為極小化問(wèn)題，其變量與約束條件情況如下：目標(biāo)函數(shù)：minz=3x?+2x?+x?約束條件：1.x?+x?+x?≥5（≥型約束）2.2x?-x?+3x?≤4（≤型約束）變量：x?≥0（非負(fù)）x?≤0（非正）x?無(wú)約束對(duì)偶問(wèn)題（D）應(yīng)為極大化問(wèn)題，設(shè)對(duì)偶變量為y?(對(duì)應(yīng)第一個(gè)約束)，y?(對(duì)應(yīng)第二個(gè)約束)。根據(jù)對(duì)偶規(guī)則：原問(wèn)題的第i個(gè)約束（≥型）對(duì)應(yīng)對(duì)偶變量y?≥0。原問(wèn)題的第j個(gè)約束（≤型）對(duì)應(yīng)對(duì)偶變量y?≤0。原問(wèn)題的第k個(gè)變量x?≥0，對(duì)應(yīng)對(duì)偶問(wèn)題的第k個(gè)約束為≤型。原問(wèn)題的第l個(gè)變量x?≤0，對(duì)應(yīng)對(duì)偶問(wèn)題的第l個(gè)約束為≥型。原問(wèn)題的第m個(gè)變量x?無(wú)約束，對(duì)應(yīng)對(duì)偶問(wèn)題的第m個(gè)約束為=型。因此，對(duì)偶問(wèn)題（D）的目標(biāo)函數(shù)系數(shù)為原問(wèn)題約束條件的右端項(xiàng)：5和4。對(duì)偶問(wèn)題（D）的約束條件系數(shù)矩陣為原問(wèn)題系數(shù)矩陣的轉(zhuǎn)置。故對(duì)偶問(wèn)題（D）為：maximizew=5y?+4y?subjectto:y?+2y?≤3（對(duì)應(yīng)x?≥0，≤型）y?-y?≥2（對(duì)應(yīng)x?≤0，≥型）y?+3y?=1（對(duì)應(yīng)x?無(wú)約束，=型）y?≥0,y?≤0（對(duì)偶變量符號(hào)）第2問(wèn)：利用互補(bǔ)松弛條件求對(duì)偶最優(yōu)解互補(bǔ)松弛條件指出：若x*是原問(wèn)題（P）的最優(yōu)解，y*是對(duì)偶問(wèn)題（D）的最優(yōu)解，則有：對(duì)于原問(wèn)題的每個(gè)變量x?*，若x?*>0，則對(duì)偶問(wèn)題的第j個(gè)約束取等式；若對(duì)偶問(wèn)題的第j個(gè)約束取嚴(yán)格不等式，則x?*=0。對(duì)于對(duì)偶問(wèn)題的每個(gè)變量y?*，若y?*>0，則原問(wèn)題的第i個(gè)約束取等式；若原問(wèn)題的第i個(gè)約束取嚴(yán)格不等式，則y?*=0。已知原問(wèn)題（P）的最優(yōu)解x?*=1,x?*=-2,x?*=2。首先，檢查原問(wèn)題變量：x?*=1>0，根據(jù)互補(bǔ)松弛條件，對(duì)偶問(wèn)題第一個(gè)約束（對(duì)應(yīng)x?）應(yīng)取等式：y?+2y?=3。(a)x?*=-2<0（注意x?本身是≤0的變量，此處其最優(yōu)值不為0），根據(jù)互補(bǔ)松弛條件，對(duì)偶問(wèn)題第二個(gè)約束（對(duì)應(yīng)x?）應(yīng)取等式：y?-y?=2。(b)x?*=2≠0，根據(jù)互補(bǔ)松弛條件，對(duì)偶問(wèn)題第三個(gè)約束（對(duì)應(yīng)x?）應(yīng)取等式：y?+3y?=1。(c)（這恰好是對(duì)偶問(wèn)題本身的約束，本就是等式）現(xiàn)在，我們有方程(a)和(b)：由(a):y?=3-2y?代入(b):(3-2y?)-y?=2→3-3y?=2→-3y?=-1→y?=1/3。但注意到對(duì)偶問(wèn)題中y?≤0，而此處解得y?=1/3>0，這似乎矛盾。這意味著什么？哦，我們需要再審視原問(wèn)題的約束條件是否取等式，以應(yīng)用互補(bǔ)松弛條件的另一部分。原問(wèn)題（P）的約束：1.x?+x?+x?≥5。代入最優(yōu)解：1+(-2)+2=1≥5？顯然1≥5不成立！這說(shuō)明我在抄錄題目或者計(jì)算時(shí)出現(xiàn)了錯(cuò)誤？或者，題目給出的“最優(yōu)解”本身就是錯(cuò)誤的？不，更可能是我剛才的計(jì)算失誤。1+(-2)+2=1？1減2是-1，-1加2是1。而原問(wèn)題第一個(gè)約束是≥5。1≥5顯然不成立。這表明，要么題目有誤，要么我理解錯(cuò)了題目。（*此處應(yīng)有一個(gè)停頓和反思，模擬真實(shí)解題時(shí)發(fā)現(xiàn)矛盾的過(guò)程*）?。∵@不可能。如果x*是原問(wèn)題的最優(yōu)解，它必須滿(mǎn)足所有約束條件。因此，我一定是在某個(gè)環(huán)節(jié)出了問(wèn)題。讓我再仔細(xì)檢查題目。題目：原問(wèn)題（P）的第一個(gè)約束是x?+x?+x?≥5。給定x?*=1,x?*=-2,x?*=2。那么1+(-2)+2=1，確實(shí)是1≥5不成立。這說(shuō)明這個(gè)x*根本不是原問(wèn)題的可行解，更談不上最優(yōu)解。這顯然是一個(gè)矛盾。那么，是題目給出的最優(yōu)解有誤，還是我哪里理解錯(cuò)了？（*再次審視題目*）或者，是否是我在構(gòu)造對(duì)偶問(wèn)題時(shí)，符號(hào)出現(xiàn)了錯(cuò)誤？不，對(duì)偶問(wèn)題的構(gòu)造規(guī)則是明確的。那么，更可能的情況是，在實(shí)際的習(xí)題中，這個(gè)最優(yōu)解應(yīng)該是滿(mǎn)足所有約束的?；蛟S是題目中的約束條件符號(hào)應(yīng)為≤5？或者最優(yōu)解的數(shù)值不同？例如，如果第一個(gè)約束是x?+x?+x?≤5，那么1+(-2)+2=1≤5是成立的?；蛘?，最優(yōu)解x?*是6？1+(-2)+6=5≥5，也成立。（*此處體現(xiàn)了解題時(shí)遇到矛盾的處理思路，即檢查前提和計(jì)算*）為了繼續(xù)演示互補(bǔ)松弛條件的應(yīng)用，我們假設(shè)題目中的第一個(gè)約束條件應(yīng)為x?+x?+x?≤5（即≤型），或者最優(yōu)解x?*的值為5（使得1+(-2)+5=4≥5？不，4也不大于等于5。x?*=6，則1-2+6=5≥5，成立）。我們假設(shè)正確的最優(yōu)解代入第一個(gè)約束后是取等式的，即1+(-2)+x?*=5→x?*=6。那么，原問(wèn)題第一個(gè)約束是等式。此時(shí)，原問(wèn)題約束條件：1.x?+x?+x?=5（等式，即≥且≤）2.2x?-x?+3x?≤4。代入x?*=1,x?*=-2,x?*=6：2*1-(-2)+3*6=2+2+18=22≤4？顯然不成立。看來(lái)，這個(gè)給定的“最優(yōu)解”與原問(wèn)題約束存在嚴(yán)重沖突。這提示我們，在實(shí)際解題時(shí)，首先必須驗(yàn)證解的可行性。若一個(gè)解連約束都不滿(mǎn)足，后續(xù)討論便無(wú)從談起。（*為了完成教學(xué)目標(biāo)，我們換一個(gè)角度，假設(shè)原問(wèn)題的最優(yōu)解是可行的，并且我們利用對(duì)偶問(wèn)題的三個(gè)等式約束來(lái)求解y?和y?。*）我們有方程(a):y?+2y?=3(來(lái)自x?*>0)方程(c):y?+3y?=1(來(lái)自x?*≠0，且對(duì)偶約束本身是等式)聯(lián)立(a)和(c):(a)-(c):(y?+2y?)-(y?+3y?)=3-1→-y?=2→y?=-2。代入(a):y?+2*(-2)=3→y?=3+4=7。此時(shí)y?=7≥0,y?=-2≤0，滿(mǎn)足對(duì)偶變量符號(hào)約束。再代入方程(b)驗(yàn)證：y?-y?=7-(-2)=9。而對(duì)偶問(wèn)題第二個(gè)約束是y?-y?≥2。9≥2，滿(mǎn)足。此時(shí)，由于x?*=-2<0（x?是≤0的變量，其最優(yōu)值為負(fù)，即不為0），根據(jù)互補(bǔ)松弛條件，對(duì)偶問(wèn)題對(duì)應(yīng)x?的約束應(yīng)取等式。但此處y?-y?=9>2，是嚴(yán)格不等式。這說(shuō)明，此時(shí)x?*應(yīng)該為0？這再次回到了原問(wèn)題解的可行性和最優(yōu)性的問(wèn)題上。這個(gè)例子充分說(shuō)明了，在運(yùn)用任何定理或條件之前，確保前提假設(shè)（如解的可行性、最優(yōu)性）的滿(mǎn)足是至關(guān)重要的。在實(shí)際解題中，遇到這種矛盾，應(yīng)首先回溯檢查。（*總結(jié)：互補(bǔ)松弛條件是強(qiáng)大的工具，但它的應(yīng)用建立在原問(wèn)題和對(duì)偶問(wèn)題均有最優(yōu)解且已知其中一個(gè)的最優(yōu)解的基礎(chǔ)上。實(shí)際操作中，需仔細(xì)核對(duì)每一步。*）評(píng)注與拓展：本題主要考察對(duì)偶問(wèn)題的構(gòu)造和互補(bǔ)松弛條件的應(yīng)用。對(duì)偶問(wèn)題的構(gòu)造需要細(xì)心，特別是變量符號(hào)和約束類(lèi)型的對(duì)應(yīng)關(guān)系?；パa(bǔ)松弛條件則是溝通原對(duì)偶最優(yōu)解的橋梁，在已知一個(gè)問(wèn)題的最優(yōu)解去求另一個(gè)問(wèn)題的最優(yōu)解時(shí)非常有效。但必須注意，應(yīng)用該條件的前提是所給解確實(shí)是最優(yōu)解且滿(mǎn)足可行性。在解題時(shí)，若出現(xiàn)矛盾，應(yīng)首先檢查模型、數(shù)據(jù)或計(jì)算過(guò)程。第二章整數(shù)規(guī)劃2.1核心知識(shí)點(diǎn)回顧整數(shù)規(guī)劃（IP）關(guān)注決策變量取整數(shù)值的優(yōu)化問(wèn)題，因其廣泛的實(shí)用性和理論挑戰(zhàn)性而成為運(yùn)籌學(xué)的重要分支。IP模型主要分為純整數(shù)規(guī)劃、混合整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃。求解IP的精確算法包括分支定界法、割平面法等，它們通?；诰€(xiàn)性規(guī)劃松弛。對(duì)于大規(guī)?；騈P難的IP問(wèn)題，啟發(fā)式算法和元啟發(fā)式算法（如遺傳算法、模擬退火等）是常用的求解策略。建模技巧，如邏輯約束的線(xiàn)性化、變量替換、有效不等式的引入等，對(duì)IP問(wèn)題的求解效率至關(guān)重要。2.2典型習(xí)題解析習(xí)題2.2.10-1整數(shù)規(guī)劃建模：選址問(wèn)題題目：某公司計(jì)劃在若干候選城市中選擇開(kāi)設(shè)若干個(gè)區(qū)域配送中心（RDC）。每個(gè)候選城市開(kāi)設(shè)RDC需承擔(dān)固定成本。同時(shí)，每個(gè)RDC有其覆蓋范圍，公司希望所有需求城市都能被至少一個(gè)開(kāi)設(shè)的RDC所覆蓋。已知每個(gè)候選城市開(kāi)設(shè)RDC的固定成本，以及每個(gè)候選RDC對(duì)各需求城市的覆蓋情況。試建立一個(gè)0-1整數(shù)規(guī)劃模型，以確定在哪些候選城市開(kāi)設(shè)RDC，使得總成本（固定成本之和）最低，且所有需求城市均被覆蓋。解析與解答：?jiǎn)栴}分析：這是一個(gè)典型的集合覆蓋問(wèn)題（SetCoveringProblem），屬于0-1整數(shù)規(guī)劃的范疇。目標(biāo)是選擇最小成本的候選集合（RDC），使得它們的并集能夠覆蓋所有的需求元素（需求城市）。模型構(gòu)建：1.決策變量：設(shè)I為候選RDC城市的集合，J為需求城市的集合。對(duì)于每個(gè)候選城市i∈I，定義0-1變量：x?=1，若在候選城市i開(kāi)設(shè)RDC；x?=0，否則。2.目標(biāo)函數(shù)：目標(biāo)是最小化總固定成本。設(shè)c?為在候選城市i開(kāi)設(shè)RDC的固定成本。則目標(biāo)函數(shù)為：minimizeZ=Σ(c?*x?)(i∈I)3.約束條件：核心約束是所有需求城市必須被至少一個(gè)開(kāi)設(shè)的RDC覆蓋。設(shè)a??為0-1系數(shù)，其中a??=1表示候選RDCi能夠覆蓋需求城市j；a??=0表示不能覆蓋。對(duì)于每個(gè)需求城市j∈J，覆蓋約束為：Σ(a??*x?)≥1(j∈J)此約束表示，至少選擇一個(gè)能夠覆蓋需求城市j的候選RDCi。變量非負(fù)整數(shù)約束：x?∈{0,1}(i∈I)完整模型：minZ=Σ(c?x?)s.t.Σ(a??x?)≥1,?j∈J,x?∈{0,1},?i∈I.評(píng)注與拓展：集合覆蓋問(wèn)題是NP難的，當(dāng)集合規(guī)模較大時(shí)，精確求解非常困難。此時(shí)，通常需要采用啟發(fā)式算法或基于松弛的近似算法。模型中，若某些需求城市的覆蓋有優(yōu)先級(jí)或必須被多個(gè)RDC覆蓋（冗余覆蓋以提高可靠性），則約束條件可以相應(yīng)修改，例如將“≥1”改為“≥k”（k為所需的覆蓋次數(shù)）。實(shí)際應(yīng)用中，還可能考慮開(kāi)設(shè)RDC的容量限制，即一個(gè)RDC能夠覆蓋的需求城市數(shù)量或總需求量有限，此時(shí)模型會(huì)更為復(fù)雜，可能需要引入額外的變量和約束來(lái)表示分配關(guān)系，從而轉(zhuǎn)化為集覆蓋與集packing/partitioning的混合問(wèn)題。對(duì)于大規(guī)模問(wèn)題，預(yù)處理技術(shù)（如刪除被支配的候選集、合并需求點(diǎn)等）可以顯著減小問(wèn)題規(guī)模，提高求解效率。第三章非線(xiàn)性規(guī)劃基礎(chǔ)與最優(yōu)性條件3.1核心知識(shí)點(diǎn)回顧非線(xiàn)性規(guī)劃（NLP）研究目標(biāo)函數(shù)或約束條件中包含