Advanced Operations Research智慧樹知到答案2024年上海大學(xué)

AdvancedOperationsResearch上海大學(xué)智慧樹知到答案2024年第一章測(cè)試

求解一個(gè)規(guī)模為n的問題，一個(gè)特定的算法所需要的計(jì)算步數(shù)是2358+1000000log(n)+67n2+9n4，那么這個(gè)算法的時(shí)間復(fù)雜度應(yīng)該是（）。

A:O(n2)B:O(9n4)C:O(log(n))D:O(n4)

答案:D已知c>1,以下算法復(fù)雜度，效率最高的是（）。

A:O(nc)B:O((log(n))c),C:O(n2)D:O(n)

答案:BNP完全問題是最難的P問題。（）

A:錯(cuò)B:對(duì)

答案:ANP完全問題是求解難度最低的NP-Hard問題。（）

A:對(duì)B:錯(cuò)

答案:A如果一個(gè)問題A可以多項(xiàng)式時(shí)間可解，那么問題B就一定多項(xiàng)式時(shí)間可解，我們就說問題A可以多項(xiàng)式規(guī)約到問題B。（）

A:對(duì)B:錯(cuò)

答案:B如果我們找到了一個(gè)求解SAT問題的多項(xiàng)式時(shí)間算法，那么P問題就等于NP問題。（）

A:對(duì)B:錯(cuò)

答案:A如果我們找到了一個(gè)求解3劃分問題的多項(xiàng)式時(shí)間算法，那么劃分問題也就可以多項(xiàng)式時(shí)間可解了。（）

A:對(duì)B:錯(cuò)

答案:A判定性問題是答案只有對(duì)和錯(cuò)的問題。（）

A:錯(cuò)B:對(duì)

答案:B因?yàn)樗械腘P完全問題都沒有辦法在多項(xiàng)式時(shí)間內(nèi)求解，而NP-hard的難度最小又是NP完全問題的難度，所以不存在求解NP-hard問題的多項(xiàng)式時(shí)間算法（）

A:錯(cuò)B:對(duì)

答案:A時(shí)間復(fù)雜度為O(1.01n)的算法優(yōu)于時(shí)間復(fù)雜度為O(n8888)的算法。（）

A:對(duì)B:錯(cuò)

答案:BNP-Hard問題可能是NP完全問題，但是NP完全問題不一定是NP-Hard問題。（）

A:錯(cuò)B:對(duì)

答案:A

第二章測(cè)試

數(shù)學(xué)規(guī)劃是一種特殊的線性規(guī)劃問題。（）

A:對(duì)B:錯(cuò)

答案:B圖解法無法求解行業(yè)級(jí)的線性規(guī)劃問題，因?yàn)樗疃嘀荒芮蠼馊齻€(gè)決策變量的線性規(guī)劃問題，無法處理大規(guī)模線性規(guī)劃問題。（）

A:對(duì)B:錯(cuò)

答案:B雙線性規(guī)劃模型是一種非線性規(guī)劃模型。（）

A:對(duì)B:錯(cuò)

答案:A二次錐規(guī)劃模型是一種非線性規(guī)劃模型。（）

A:對(duì)B:錯(cuò)

答案:A正八面體是凸多面體。（）

A:對(duì)B:錯(cuò)

答案:A因?yàn)閮?nèi)點(diǎn)法是求解線性規(guī)劃問題的多項(xiàng)式時(shí)間算法，而單純形法不是，所以求解線性規(guī)劃問題時(shí)，內(nèi)點(diǎn)法一定比單純形法更快。（）

A:對(duì)B:錯(cuò)

答案:B兩個(gè)三角形的交集是凸集。（）

A:對(duì)B:錯(cuò)

答案:A兩個(gè)正方形的并集是凸集。（）

A:錯(cuò)B:對(duì)

答案:A直線是凸集，而線段不是凸集。（）

A:對(duì)B:錯(cuò)

答案:B凸集不一定是閉合區(qū)間。（）

A:對(duì)B:錯(cuò)

答案:A多重最優(yōu)解是指：最優(yōu)解有兩個(gè)極點(diǎn)組成。（）

A:錯(cuò)B:對(duì)

答案:A在求解線性規(guī)劃問題時(shí)，如果出現(xiàn)了無界解的情況，那么該線性規(guī)劃的可行域一定不是一個(gè)閉合的凸集。（）

A:對(duì)B:錯(cuò)

答案:A

第三章測(cè)試

在高維空間中，constraintboundary是一個(gè)超平面。（）

A:對(duì)B:錯(cuò)

答案:A線性規(guī)劃問題的極點(diǎn)的個(gè)數(shù)一定是有限個(gè)的。（）

A:對(duì)B:錯(cuò)

答案:A一個(gè)包含4個(gè)決策變量的線性規(guī)劃問題中，每個(gè)極點(diǎn)是4個(gè)超平面的交點(diǎn)。（）

A:對(duì)B:錯(cuò)

答案:A在一個(gè)包含10個(gè)決策變量的線性規(guī)劃問題中，每個(gè)兩個(gè)相鄰的極點(diǎn)共享10個(gè)超平面。

（）

A:對(duì)B:錯(cuò)

答案:B線性規(guī)劃問題的決策變量必須大于等于0（）

A:對(duì)B:錯(cuò)

答案:B不能以可行域是否相同來判斷兩個(gè)線性規(guī)劃模型是否等價(jià)（）

A:錯(cuò)B:對(duì)

答案:BBasicSolution與CPFSolution是等價(jià)的（）

A:對(duì)B:錯(cuò)

答案:A求解線性規(guī)劃模型的時(shí)候，基變量永遠(yuǎn)為0（）

A:錯(cuò)B:對(duì)

答案:A單純形法每次迭代得到的解都是可行解（）

A:對(duì)B:錯(cuò)

答案:A當(dāng)求解線性規(guī)劃問題得到最優(yōu)解時(shí)，發(fā)現(xiàn)有松弛變量大于0，那么表示該線性規(guī)劃問題無可行解（）

A:對(duì)B:錯(cuò)

答案:B當(dāng)求解線性規(guī)劃問題得到最優(yōu)解時(shí)，發(fā)現(xiàn)有松弛變量大于0，那么其對(duì)應(yīng)的約束條件的對(duì)偶價(jià)格一定等于0（）

A:對(duì)B:錯(cuò)

答案:A當(dāng)求解線性規(guī)劃問題得到最優(yōu)解時(shí)，如果一條約束條件的對(duì)偶價(jià)格大于0，那么該約束條件對(duì)應(yīng)的松弛變量一定等于0（）

A:對(duì)B:錯(cuò)

答案:A

第四章測(cè)試

在含有n個(gè)決策變量和m個(gè)約束條件的線性規(guī)劃問題中，在n+m個(gè)Constraints里邊任選n個(gè)constraintboundaryequation，它們可能形成一個(gè)無界解（）

A:錯(cuò)B:對(duì)

答案:A在我們確定一個(gè)CPFSolution的definingequation的時(shí)候，我們會(huì)觀察約束條件的松弛變量和剩余變量（）

A:錯(cuò)B:對(duì)

答案:A一個(gè)CPFSolution的definingequation其實(shí)就是線性規(guī)劃模型中的不等式約束條件（）

A:對(duì)B:錯(cuò)

答案:B松弛變量是引入松弛變量的小于等于約束條件的indicatingvariable（）

A:錯(cuò)B:對(duì)

答案:B原問題的決策變量是該變量的非負(fù)約束條件的indicatingvariable（）

A:對(duì)B:錯(cuò)

答案:A人工變量是引入人工變量的等式約束條件的indicatingvariable（）

A:錯(cuò)B:對(duì)

答案:B剩余變量是引入它們的大于等于約束條件的indicatingvariable（）

A:對(duì)B:錯(cuò)

答案:B單純形法在做最優(yōu)性檢驗(yàn)的時(shí)候，如果非基變量是原問題的決策變量，用公式B－1A計(jì)算它的檢驗(yàn)數(shù)（）

A:錯(cuò)B:對(duì)

答案:A單純形法利用公式CBB－1b做最優(yōu)性檢驗(yàn)（）

A:對(duì)B:錯(cuò)

答案:B單純形法每次迭代都會(huì)得到一個(gè)BFSolution，這個(gè)BFSolution對(duì)應(yīng)的目標(biāo)函數(shù)值是CBB－1b（）

A:對(duì)B:錯(cuò)

答案:A單純形法每次迭代都會(huì)得到一個(gè)BFSolution，這個(gè)BFSolution的基變量取值為CBB－1（）

A:對(duì)B:錯(cuò)

答案:B

第五章測(cè)試

一個(gè)線性規(guī)劃問題的目標(biāo)函數(shù)系數(shù)在其對(duì)偶問題中是functionalconstraint的右端項(xiàng)（）

A:錯(cuò)B:對(duì)

答案:B一個(gè)線性規(guī)劃問題的functionalconstraint右端項(xiàng)是對(duì)偶問題的目標(biāo)函數(shù)系數(shù)（）

A:錯(cuò)B:對(duì)

答案:B一個(gè)線性規(guī)劃問題的決策變量系數(shù)在對(duì)偶問題中是functionalconstraint的右端項(xiàng)

（）

A:錯(cuò)B:對(duì)

答案:A一個(gè)線性規(guī)劃問題的決策變量系數(shù)是其對(duì)偶問題的functionalconstraint系數(shù)（）

A:對(duì)B:錯(cuò)

答案:A在求解一個(gè)線性規(guī)劃問題的單純形表中，第零行檢驗(yàn)數(shù)是對(duì)偶問題的決策變量（）

A:對(duì)B:錯(cuò)

答案:A對(duì)偶價(jià)格是指約束條件右端項(xiàng)每增加一個(gè)單位，目標(biāo)函數(shù)增加的數(shù)量（）

A:對(duì)B:錯(cuò)

答案:AReducedcost是指決策變量每增加一個(gè)單位，對(duì)偶價(jià)格增加的數(shù)量（）

A:對(duì)B:錯(cuò)

答案:B對(duì)于目標(biāo)函數(shù)最大化的原問題來說，如果x*是原線性規(guī)劃問題的最優(yōu)解，y*是對(duì)偶問題的最優(yōu)解，那么cx*≤y*b（）

A:對(duì)B:錯(cuò)

答案:B對(duì)于目標(biāo)函數(shù)最大化的原問題來說，如果x是原問題的一個(gè)可行解，y是對(duì)偶問題的一個(gè)可行解，那么cx≥yb（）

A:錯(cuò)B:對(duì)

答案:A如果一個(gè)線性規(guī)劃問題有可行解，并且目標(biāo)函數(shù)有界，那么它的對(duì)偶問題也一樣：有可行解，且目標(biāo)函數(shù)有界。（）

A:錯(cuò)B:對(duì)

答案:B如果一個(gè)線性規(guī)劃問題目標(biāo)函數(shù)值無界，那么它的對(duì)偶問題一定沒有可行解。（）

A:對(duì)B:錯(cuò)

答案:A如果一個(gè)線性規(guī)劃問題目標(biāo)函數(shù)值無界，那么它的對(duì)偶問題要么是沒有可行解，要么是目標(biāo)函數(shù)值無界。（）

A:對(duì)B:錯(cuò)

答案:B

第六章測(cè)試

靈敏度分析中，當(dāng)我們說目標(biāo)函數(shù)系數(shù)有一個(gè)變化區(qū)間，系數(shù)在這個(gè)區(qū)間變化，最優(yōu)解不會(huì)發(fā)生變化。這個(gè)變化區(qū)間只對(duì)一個(gè)目標(biāo)函數(shù)系數(shù)變化有效。（）

A:對(duì)B:錯(cuò)

答案:A靈敏度分析中，當(dāng)我們說約束條件右端項(xiàng)有一個(gè)變化區(qū)間，在這個(gè)區(qū)間變化，對(duì)偶價(jià)格不會(huì)發(fā)生變化。這個(gè)變化區(qū)間只對(duì)一個(gè)約束條件右端項(xiàng)變化有效。（）

A:對(duì)B:錯(cuò)

答案:A初始單純形表中的b向量發(fā)生變化，那么當(dāng)前finaltableau中新的Solution的可行性

不會(huì)受到影響。（）

A:錯(cuò)B:對(duì)

答案:A初始單純形表中的非基變量目標(biāo)函數(shù)系數(shù)發(fā)生變化，那么當(dāng)前finaltableau中新的Solution的可行性不會(huì)受到影響。（）

A:錯(cuò)B:對(duì)

答案:B初始單純形表中的非基變量約束條件系數(shù)發(fā)生變化，那么當(dāng)前finaltableau中新的Solution的最優(yōu)性不會(huì)受到影響。（）

A:對(duì)B:錯(cuò)

答案:B初始單純形表中的基變量目標(biāo)函數(shù)系數(shù)發(fā)生變化，那么當(dāng)前finaltableau中新的Solution的可行性不會(huì)受到影響。（）

A:對(duì)B:錯(cuò)

答案:B初始單純形表中的基變量約束條件系數(shù)發(fā)生變化，那么當(dāng)前finaltableau中新的Solution的最優(yōu)性不會(huì)受到影響。（）

A:對(duì)B:錯(cuò)

答案:B在做靈敏度分析的時(shí)候，在初始單純形表中新加入一個(gè)決策變量，那么當(dāng)前finaltableau中新的Solution的最優(yōu)性不會(huì)受到影響。（）

A:錯(cuò)B:對(duì)

答案:A在線性規(guī)劃模型求得最優(yōu)解以后，新添加了一條約束條件。如果當(dāng)前解滿足該約束條件，那么當(dāng)前解依然是最優(yōu)解。（）

A:對(duì)B:錯(cuò)

答案:A在線性規(guī)劃模型求得最優(yōu)解以后，新添加了一條約束條件。如果當(dāng)前解不滿足該約束條件，并且約束條件中的基變量系數(shù)不等于0，那么在討論當(dāng)前解的性質(zhì)前要先做高斯消元。（）

A:錯(cuò)B:對(duì)

答案:B

第七章測(cè)試

單純形法無法求解運(yùn)輸問題。（）

A:錯(cuò)B:對(duì)

答案:A匈牙利法無法求解運(yùn)輸問題。（）

A:對(duì)B:錯(cuò)

答案:A單純形法可以求解指派問題。（）

A:對(duì)B:錯(cuò)

答案:A運(yùn)輸單純形法可以求解指派問題。（）

A:錯(cuò)B:對(duì)

答案:B運(yùn)輸問題中，約束條件的數(shù)量等于供給節(jié)點(diǎn)的數(shù)量加上需求節(jié)點(diǎn)的數(shù)量。（）

A:錯(cuò)B:對(duì)

答案:B運(yùn)輸問題中，決策變量的數(shù)量等于問題中運(yùn)輸線路的數(shù)量（）

A:錯(cuò)B:對(duì)

答案:B因?yàn)檫\(yùn)輸問題具有特殊的結(jié)構(gòu)，我們可以利用這種特殊的結(jié)構(gòu)設(shè)計(jì)出比單純形法更快的算法。（）

A:對(duì)B:錯(cuò)

答案:A因?yàn)橹概蓡栴}具有特殊的結(jié)構(gòu)，我們可以利用這種特殊的結(jié)構(gòu)設(shè)計(jì)出比運(yùn)輸單純形法更快的算法。（）

A:對(duì)B:錯(cuò)

答案:AVogel算法沒有考慮成本，而西北角法考慮了成本因素。（）

A:對(duì)B:錯(cuò)

答案:B一個(gè)有m個(gè)供給點(diǎn)，n個(gè)需求點(diǎn)的運(yùn)輸問題，有n+m－1個(gè)基變量。（）

A:錯(cuò)B:對(duì)

答案:B

第八章測(cè)試

具有n個(gè)頂點(diǎn)和n－1條邊的無向加權(quán)圖必是樹。（）

A:對(duì)B:錯(cuò)

答案:B具有n個(gè)頂點(diǎn)的樹必有n－1條邊。（）

A:對(duì)B:錯(cuò)

答案:A具有n個(gè)頂點(diǎn)無向加權(quán)完全圖必有n×n條邊。（）

A:錯(cuò)B:對(duì)

答案:A最大割問題的對(duì)偶問題是最小流問題。（）

A:錯(cuò)B:對(duì)

答案:A網(wǎng)絡(luò)流問題中，往往邊上存在一個(gè)容量，稱之為度。（）

A:錯(cuò)B:對(duì)

答案:A我們可以利用殘差網(wǎng)絡(luò)和增廣路等方法來求解最大流問題。（）

A:對(duì)B:錯(cuò)

答案:A最大網(wǎng)絡(luò)流問題中，除了源點(diǎn)和匯入點(diǎn)以外，所有節(jié)點(diǎn)的入度等于出度。（）

A:錯(cuò)B:對(duì)

答案:B如果在一個(gè)可行流對(duì)應(yīng)的殘差網(wǎng)絡(luò)中不存在增廣路徑，那么該可行流就是最大流。（）

A:錯(cuò)B:對(duì)

答案:B對(duì)于任意一個(gè)割，割的流量一定小于等于割的容量。（）

A:對(duì)B:錯(cuò)

答案:A

一個(gè)n個(gè)節(jié)點(diǎn)的無向網(wǎng)絡(luò)中，如果邊的數(shù)量小于n-1，那么該網(wǎng)絡(luò)一定不連通。

A:對(duì)B:錯(cuò)

答案:A

第九章測(cè)試

割平面法也是一種求解整數(shù)規(guī)劃問題的一種方法（）

A:對(duì)B:錯(cuò)

答案:A割平面實(shí)際上是在模型中加入新的約束條件，或者收緊原模型的約束條件（）

A:對(duì)B:錯(cuò)

答案:A整數(shù)規(guī)劃問題的可行域不是凸集（）

A:錯(cuò)B:對(duì)

答案:B如果一個(gè)純整數(shù)規(guī)劃問題的線性松弛問題的目標(biāo)函數(shù)值有界，那么這個(gè)整數(shù)規(guī)劃問題僅有有限個(gè)可行點(diǎn)（）

A:錯(cuò)B:對(duì)

答案:B整數(shù)規(guī)劃問題忽略整數(shù)約束條件所得到的新問題被稱為整數(shù)規(guī)劃問題的線性松弛（）

A:錯(cuò)B:對(duì)

答案:B一般整數(shù)規(guī)劃可以分成兩類：變量全限制為整數(shù)的純整數(shù)規(guī)劃，和變量部分限制為整數(shù)的混合整數(shù)規(guī)劃（）

A:錯(cuò)B:對(duì)

答案:B整數(shù)規(guī)劃的求解難度大于線性規(guī)劃問題的求解難度（）

A:對(duì)B:錯(cuò)

答案:B我們可以利用靈敏度分析方法來討論整數(shù)規(guī)劃右端項(xiàng)變化對(duì)目標(biāo)函數(shù)的影響（）

A:錯(cuò)B:對(duì)

答案:A我們可以利用靈敏度分析方法來討論整數(shù)規(guī)劃目標(biāo)函數(shù)系數(shù)變化對(duì)最優(yōu)解的影響（）

A:錯(cuò)B:對(duì)

答案:A我們可以通過整數(shù)規(guī)劃最優(yōu)解中松弛變量的值來判斷資源是否有剩余（）

A:對(duì)B:錯(cuò)

答案:A

第十章測(cè)試

動(dòng)態(tài)規(guī)劃實(shí)際上是一個(gè)多階段決策過程（）

A:錯(cuò)B:對(duì)

答案:B可以使用動(dòng)態(tài)規(guī)劃求解的問題必須具有無后效性（）

A:錯(cuò)B:對(duì)

答案:B動(dòng)態(tài)規(guī)劃雖然是遞歸過程，但是可以通過運(yùn)用一定技術(shù)可以提高其運(yùn)行效率（）