注：不含主觀題第1題判斷題(1分)線性規(guī)劃問題的對偶理論將學(xué)習(xí)弱對偶性、強(qiáng)對偶性和互補(bǔ)松緊性。第2題判斷題(1分)本課程以線性規(guī)劃的原始對偶算法為橋梁，將其應(yīng)用到最短路問題、最大流問題和最大匹配問題上。第3題判斷題(1分)通過《組合最優(yōu)化》課程的學(xué)習(xí)，將加強(qiáng)我們問題轉(zhuǎn)化的思想，提升創(chuàng)新思維的科研能力。第4題判斷題(1分)通過《組合最優(yōu)化》課程的學(xué)習(xí)，將訓(xùn)練我們從一般到特殊的歸納思維，將賦權(quán)優(yōu)化問題轉(zhuǎn)化為一個新圖上的基數(shù)優(yōu)化問題。1.1作業(yè)第1題單選題(2分)什么是優(yōu)化問題？AA.線性規(guī)劃問題B從一個離散區(qū)域能找到一個使目標(biāo)函數(shù)極小的點C在一個可行區(qū)域內(nèi)找一個使目標(biāo)函數(shù)極小或者極大的解D從一個連續(xù)區(qū)域能找到一個使目標(biāo)函數(shù)極小或者極大的解1.2作業(yè)第1題第2題判斷題(2分)TSP的2-交換鄰域不是精確鄰域，3-交換鄰域是精確鄰域。1.3作業(yè)第1題第2題單選題(2分)兩個凸函數(shù)的乘積是凸函數(shù)嗎？A是B不是第3題判斷題(1分)凸規(guī)劃問題的特點就是局部最優(yōu)解等于全局最優(yōu)解。第4題判斷題(2分)整數(shù)線性規(guī)劃問題與線性規(guī)劃問題的區(qū)別在于，前者的變量中有整數(shù)變量，后者的變量都是連續(xù)變量。第5題判斷題(2分)一個優(yōu)化問題的可行域是凸集，目標(biāo)函數(shù)是定義在凸集上的凸函數(shù)，則這個極小化的優(yōu)化問題是一個凸規(guī)劃問題。第6題判斷題(2分)多個凸集的并集日仍是一個凸集。2.1作業(yè)第1題判斷題(1分)若線性規(guī)劃問題存在有限最優(yōu)解，則最優(yōu)值必在某個基可行解上達(dá)到。第2題判斷題(1.5分)兩階段法的第一階段的輔助線性規(guī)劃問題的最優(yōu)值等于0時，再把最優(yōu)基中的人工變量換出基后，才可以進(jìn)入第二階段進(jìn)行單純形的迭代。第3題判斷題(1分)一個線性規(guī)劃問題只要可行，則一定存在基本可行解。第4題判斷題(1.5分)一個線性規(guī)劃問題的基可行解中，非基變量的取值必為0。第5題判斷題(2分)一個非空的線性規(guī)劃可行域可能沒有極點。2.2作業(yè)第1題判斷題(2分)在一對互為對偶的線性規(guī)劃問題中，原問題一定是極小型，對偶問題一定是極大型。第2題判斷題(1分)每一個線性規(guī)劃問題的約束條件都對應(yīng)一個對偶變量。第3題第4題2.3作業(yè)第1題判斷題(1分)在互為對偶的一對線性規(guī)劃問題中，目標(biāo)極大化的線性規(guī)劃的最優(yōu)值小于等于其對偶規(guī)劃的最優(yōu)值。第2題判斷題(1分)若線性規(guī)劃問題有兩個最優(yōu)解，則有無窮多個最優(yōu)解。第3題判斷題(1分)如果原問題有最優(yōu)解，則其對偶問題也有最優(yōu)解。第4題判斷題(1分)如果原問題無界，則其對偶問題也無可行解。第5題判斷題(1分)任何一個線性規(guī)劃都有一個對偶規(guī)劃。第6題第7題2.4作業(yè)第1題判斷題(1分)最短路問題的對偶規(guī)劃的變量的含義可以解釋為一個交通運輸公司的交通費用。3.0.1作業(yè)第1題判斷題(1分)兩階段法的第一階段是為了求得初始基可行解，當(dāng)?shù)谝浑A段的最優(yōu)值>0時，原線性規(guī)劃問題無解。第2題判斷題(1分)當(dāng)?shù)谝浑A段的最優(yōu)值=0時，且基變量不含有人工變量時，可求得原線性規(guī)劃問題的初始基可行解，將目標(biāo)函數(shù)替換為原問題的目標(biāo)函數(shù)，進(jìn)入第二階段求解原問題。第3題判斷題(2分)在兩階段法的第一階段，如果最優(yōu)值等于0，且基變量中不含有人工變量，則第一階段的最優(yōu)表中人工變量的檢驗數(shù)必為1，其他變量的檢驗數(shù)都是0.3.0.2作業(yè)第1題填空題(2分)修正單純形法主要減少的運算量在于計算元素的個數(shù)從

____

降到了____。（m+1）×（n+1）;（m+1）×（m+1）+(n-m)正確答案：:["(m+1)*(n+1)","(m+1)(n+1)","(m+1)x(n+1)","（m+1）×（n+1）"]正確答案：:["(m+1)*(m+1)+(n-m)","(m+1)*(m+1)+n-m","(m+1)(m+1)+n-m","(m+1)(m+1)+(n-m)","(m+1)x(m+1)+(n-m)","(m+1)x(m+1)+n-m","（m+1）×（m+1）+(n-m)"]第2題填空題(3分)修正單純形法的好處可以不計列數(shù)的多少，當(dāng)一個線性規(guī)劃問題的行數(shù)比列數(shù)多，可以用____方法求解該線性規(guī)劃的____問題。正確答案：:["修正單純形法","修正單純形"]正確答案：:["對偶","對偶問題"]第3題填空題(3分)修正單純形法的第一階段結(jié)束時進(jìn)入第二階段只需替換檢驗數(shù)行為____和____。正確答案：:["-pi^T","-pi","-(c_B^T)*(B^-1)","-pi'","-cB’*B-1"]正確答案：:["-pi^Tb","-pi*b","-pi^T*b","-(c_B^T)*(B^-1)*b","-pi'b","-cB’*B-1*b"]第4題3.0.3作業(yè)第1題判斷題(1分)在修正單純形法中，需要直接計算基矩陣的逆矩陣。第2題判斷題(2分)修正單純形法中，對偶變量、生成的入基列和基可行解的基變量的值，這些向量的計算量和存儲量都是O(km),

其中k為迭代次數(shù)。3.0.4作業(yè)第1題判斷題(1分)當(dāng)用修正單純性法求解最大流問題時，其系數(shù)矩陣是弧鏈關(guān)聯(lián)矩陣，所以要列出所有從起點s到終點t的鏈路。第2題判斷題(2分)在用修正單純形法求解最大流問題時，因為每次迭代要選擇檢驗數(shù)最小的變量入基，所以每次迭代需要求一條每條邊的權(quán)值為（-pi）的s-t最短路，則改最短路所對應(yīng)的鏈路變量入基。第3題判斷題(1分)在用修正單純形法求解最大流問題時，每次迭代入基的鏈路變量的序號無關(guān)緊要。3.0.5作業(yè)第1題判斷題(2分)Dantzig-Wolfe分解算法適用于變量可分離的線性規(guī)劃問題，將該線性規(guī)劃問題的每個變量描述為各自子問題的極點的凸組合，從而把該線性規(guī)劃模型轉(zhuǎn)化為變量為凸組合系數(shù)的線性規(guī)劃模型，因此通過增加列數(shù)而減少行數(shù)，再利用修正單純形法求解新模型。第2題判斷題(2分)Dantzig-Wolfe分解算法用修正單純形法求解轉(zhuǎn)化后的新模型，每次迭代通過最小檢驗數(shù)選擇入基變量的問題轉(zhuǎn)化為一個規(guī)模更小的線性規(guī)劃子問題，當(dāng)所有子問題的目標(biāo)值都大于等于當(dāng)前各自的對偶變量時，則達(dá)到了最優(yōu)。第3題判斷題(2分)修正單純形法適合系數(shù)矩陣是扁寬型的線性規(guī)劃問題的求解，如果系數(shù)矩陣是窄條型的，可以用單純形法求解其對偶問題。因此，可以通過增加列數(shù)而減少行數(shù)的方法，而列數(shù)的增加對于每次迭代的計算量沒有影響。第4題判斷題(2分)當(dāng)要求解復(fù)雜的線性規(guī)劃問題時，可以嘗試使用列生成的技巧，將入基列的選擇轉(zhuǎn)化為一個更易求解的子問題。3.1作業(yè)第1題判斷題(1分)限制原問題(RP)的目的是求解原問題(P)的一個可行解并滿足互補(bǔ)松緊性。第2題填空題(2分)

在什么情況下原始對偶算法終止，可以得到原始問題的最優(yōu)解？____如何得到P的最優(yōu)解？____正確答案：:["DRP的最優(yōu)值為0","DRP的最優(yōu)值=0","\xiopt=0","DRP的最優(yōu)值等于0","DRP最優(yōu)值xi_OPT=0","RP的最優(yōu)值為0","限制原問題的最優(yōu)值為0"]正確答案：:["互補(bǔ)松緊性求得對偶問題最優(yōu)解得到原始問題最優(yōu)解","互補(bǔ)松緊性","DRP的最優(yōu)值等于0時，RP的最優(yōu)解即為P的最優(yōu)解","根據(jù)互補(bǔ)松弛性，用RP的最優(yōu)解得到P的最優(yōu)解"]第3題填空題(3分)1.原始對偶算法是保持____

可行性，向____可行性和____

逼近。正確答案：:["對偶","對偶問題"]\xiopt=0","DRP的最優(yōu)值等于0","DRP最優(yōu)值xi_OPT=0","RP的最優(yōu)值為0","限制原問題的最優(yōu)值為0"]正確答案：:["原始","原始問題"]正確答案：:["互補(bǔ)松緊性","互補(bǔ)松緊","CS_pi"]3.2作業(yè)第1題判斷題(1分)在原始對偶算法的迭代中，表示(DRP)的最優(yōu)解，J表示允許列的集合，若下式成立，則對偶問題無界，相應(yīng)的原問題不可行。第2題判斷題(1分)只要原問題可行，那么很容易確定一個初始對偶可行解。第3題判斷題(1分)當(dāng)原線性規(guī)劃問題的價值向量c是非負(fù)向量，則初始對偶可行解只要取π=0.第4題第5題3.3作業(yè)第1題判斷題(1分)在求解線性規(guī)劃問題時，如果模型中價值向量c比右端向量b復(fù)雜，則將其看成原問題，極小化目標(biāo)函數(shù)，組合化價值向量。第2題判斷題(1分)在原始對偶算法的相鄰兩次迭代的允許列J和J*中，既在J中又在J*中的列是等于0點列。第3題判斷題(1分)在原始對偶算法中，關(guān)于基列與允許列的關(guān)系如下：允許列一定是基列。第4題4.1作業(yè)第1題填空題(1分)用原始對偶方法應(yīng)用到最大流問題上得到Ford-Furkerson標(biāo)號算法時，為什么將最大流問題看成對偶問題？____正確答案：:["因為b比c復(fù)雜","因為右端向量比價值向量復(fù)雜","b比c復(fù)雜","右端向量比價值向量復(fù)雜","右端向量b比價值向量c更復(fù)雜","最大流問題的右端向量更復(fù)雜","右端向量比價值系數(shù)復(fù)雜","因為右端向量b比價值向量c復(fù)雜"]第2題第3題判斷題(1分)最大流的標(biāo)號算法每次只選取一條增廣路,最好的增廣路算法是最短增廣路算法.4.2作業(yè)第1題第2題判斷題(1分)任意一個s-t割都能割斷從s到t的流量，并且給出了最大流的上界。4.3作業(yè)第1題判斷題(1.5分)最大流的預(yù)流推進(jìn)算法是針對增廣路算法每次迭代只找一條增廣路的缺陷而設(shè)計的，其每個階段盡可能多地沿多條路推進(jìn)流量。第2題判斷題(1.5分)通過廣度優(yōu)先搜索方法可以找到當(dāng)前流對應(yīng)的剩余網(wǎng)絡(luò)上從s到t的最短路，并且最短路長都相等，這里最短路長指最短路所含的邊數(shù)。4.4作業(yè)第1題判斷題(2分)最大流的預(yù)流推進(jìn)算法中，各個階段之間最短路的長度嚴(yán)格遞增，直到當(dāng)前增廣網(wǎng)絡(luò)中不存在增廣路，則找到了最大流.

第2題4.5作業(yè)第1題判斷題(1分)最大流的預(yù)流推進(jìn)算法的時間復(fù)雜性為O(|V|^3).第2題多選題(3分)關(guān)于最大流的預(yù)流推進(jìn)算法，正確的是：A預(yù)流推進(jìn)算法綜合利用了BFS求s-t最短路，分層網(wǎng)絡(luò)的特性，和每次迭代推進(jìn)盡可能多的流的思想。B預(yù)流推進(jìn)算法每一輪迭代得到的s-t最短路長都是嚴(yán)格遞減的。C預(yù)流推進(jìn)算法的迭代次數(shù)是O(|V|)，每次迭代的運算量不超過O(|V|2).D預(yù)流推進(jìn)算法每輪迭代增廣的流量由最小通行能力的點來確定。正確答案：ACD第3題5.1作業(yè)第1題判斷題(1.5分)最小費用流的線性規(guī)劃模型中，價值向量和右端向量都是一般向量，所以用原始對偶算法求解時，既可以將其看成是原問題也可以看成是對偶問題，因此可以分別從這兩個角度來設(shè)計算法。第2題判斷題(1.5分)消圈算法將DRP問題的求解轉(zhuǎn)化為求一個負(fù)費用的有向圈。第3題5.2作業(yè)第1題判斷題(2分)最小費用路算法從零流開始，每次迭代沿一條最小費用路增廣流量，若增廣前后的流值分別為δ0和δ1，則可以證明增廣流值后的流時流值為δ1的最小費用流。第2題判斷題(2分)最小費用流問題的消圈算法和最小費用路算法可以設(shè)計特定的順序或結(jié)構(gòu),得到多項式時間算法.第3題5.3作業(yè)第1題多選題(3分)關(guān)于最小費用流問題和Hitchcock問題，正確的是A原始對偶方法把Hitchcock問題看成原問題，組合化價值向量，得到的方法稱為ab算法。Bab算法每次迭代通過標(biāo)號算法求解最大流問題RP，并通過最優(yōu)圖中的標(biāo)號點來確定對偶問題DRP的最優(yōu)解。Cab算法嵌套使用了原始對偶方法，外層求解RP轉(zhuǎn)化為最大流，內(nèi)層最大流算法轉(zhuǎn)化為s-t路的可達(dá)性問題。D最小費用流問題和Hitchcock問題可以相互轉(zhuǎn)化，因此也可以用ab算法求解最小費用流問題。正確答案：ABCD第2題6.1作業(yè)第1題多選題(3分)關(guān)于匹配和二部圖，請選擇正確的選項：A二部圖一定是連通圖。B一個圖是二部圖當(dāng)且僅當(dāng)其不含有奇圈。C一個二部圖的完全匹配必是最大匹配，也是完美匹配。D一個二部圖的完全匹配必是最大匹配，完美匹配也是最大匹配。正確答案：BD6.2作業(yè)第1題多選題(3分)關(guān)于二部圖的匹配算法，正確的是：A對應(yīng)一個最大匹配必存在一條交錯增廣路。B二部圖上的最大匹配問題的交錯增廣路算法通過構(gòu)造輔助圖來找一條交錯增廣路，其對應(yīng)輔助圖中從一個未蓋點到一個目的點的路。C輔助圖上找一條交錯增廣路是通過廣度優(yōu)先搜索算法完成的。D二部圖上的最大匹配問題的交錯增廣路算法的時間復(fù)雜性為O(|E|min{(|V|,|U|}).正確答案：BCD6.3作業(yè)第1題判斷題(2分)只要存在奇圈必定造成非二部圖上找一條交錯增廣路的困難。第2題判斷題(2分)將匹配算法從二部圖推廣到一般圖的困難在于從未蓋點到目標(biāo)點的路不一定是原圖中一條交錯增廣路，產(chǎn)生這個困難的原因是有花的存在。6.4作業(yè)第1題判斷題(1分)收縮花之后圖的結(jié)構(gòu)雖然發(fā)生改變，但不需要重新構(gòu)造輔助圖。第2題判斷題(2分)在某次迭代從未蓋點u開始未能找到交錯增廣路，那么在后續(xù)迭代增廣匹配后中仍舊要考慮這個未蓋點u相對于新的匹配是否存在交錯增廣路。第3題7.1作業(yè)第1題判斷題(1分)求解指派問題的匈牙利算法的時間復(fù)雜性是O(n3).第2題判斷題(1分)簡約矩陣中的元素大于等于0就是流量變量的對偶約束.第3題判斷題(1分)二部圖的賦權(quán)匹配問題也稱為指派問題，這是運輸問題的特殊情況，特殊在運輸問題中約束右端的值a_i和b_j都是1.第4題判斷題(1分)求解指派問題的匈牙利算法本質(zhì)上是求解Hitchcock問題的原始對偶算法，只是用不同的方式來呈現(xiàn)算法的運行。第5題7.2作業(yè)第1題判斷題(2分)用原始對偶算法求解賦權(quán)匹配問題的線性規(guī)劃模型時，將RP轉(zhuǎn)化為收縮了極大奇集的允許圖GJ上的最大基數(shù)匹配問題，這很好地體現(xiàn)了將一般賦權(quán)匹配問題轉(zhuǎn)化為一系列基數(shù)匹配問題求解這一歸納研究思想。第2題判斷題(2分)一般圖的賦權(quán)匹配算法通過收縮\bar{J_b}中的奇圈和收縮輔助圖Gc中的花來消除花對于一般圖的影響。第3題判斷題(1分)為了將二部圖的賦權(quán)匹配問題的線性規(guī)劃模型推廣到非二部圖上，我們引入奇集的概念和奇集中匹配邊數(shù)不超過其基數(shù)的一半的約束,得到其線性規(guī)劃模型。第4題判斷題(1分)一般圖的賦權(quán)匹配算法的關(guān)鍵是找到一個合適的數(shù)學(xué)模型，使得其松弛問題的最優(yōu)基可行解對應(yīng)一個匹配。7.3作業(yè)第1題判斷題(2分)非二部圖的賦權(quán)匹配問題的算法的階段數(shù)為O(n)，因為最外層循環(huán)的迭代次數(shù)由判斷條件|M|<n/2確定。第2題判斷題(2分)一般圖的賦權(quán)匹配算法是原始對偶算法應(yīng)用的一個典范，其說明了如何將一個賦權(quán)問題轉(zhuǎn)化為基數(shù)問題進(jìn)行迭代求解。第3題判斷題(1分)在非二部圖的賦權(quán)匹配算法中，迭代的過程中發(fā)現(xiàn)的花可能是