管理運籌學復習題及參考答案

《運籌學》復習題及參考答案第一章運籌學概念一、填空題1．運籌學的重要研究對象是多個有組織系統(tǒng)的管理問題，經(jīng)營活動。2．運籌學的核心重要是運用數(shù)學辦法研究多個系統(tǒng)的優(yōu)化途徑及方案,為決策者提供科學決策的根據(jù)。3．模型是一件實際事物或現(xiàn)狀的代表或抽象。4普通對問題中變量值的限制稱為約束條件，它能夠表達成一種等式或不等式的集合。5．運籌學研究和解決問題的基礎是最優(yōu)化技術，并強調系統(tǒng)整體優(yōu)化功效.運籌學研究和解決問題的效果含有持續(xù)性。6．運籌學用系統(tǒng)的觀點研究功效之間的關系。7．運籌學研究和解決問題的優(yōu)勢是應用各學科交叉的辦法，含有典型綜合應用特性。8．運籌學的發(fā)展趨勢是進一步依賴于_計算機的應用和發(fā)展。9．運籌學解決問題時首先要觀察待決策問題所處的環(huán)境.10．用運籌學分析與解決問題，是一種科學決策的過程。11.運籌學的重要目的在于求得一種合理運用人力、物力和財力的最佳方案。12．運籌學中所使用的模型是數(shù)學模型。用運籌學解決問題的核心是建立數(shù)學模型，并對模型求解。13用運籌學解決問題時，要分析，定議待決策的問題.14．運籌學的系統(tǒng)特性之一是用系統(tǒng)的觀點研究功效關系。15.數(shù)學模型中，“s·t"表達約束。16．建立數(shù)學模型時，需要回答的問題有性能的客觀量度,可控制因素，不可控因素。17．運籌學的重要研究對象是多個有組織系統(tǒng)的管理問題及經(jīng)營活動。18.1940年8月，英國管理部門成立了一種跨學科的11人的運籌學小組，該小組簡稱為OR.二、單選題建立數(shù)學模型時,考慮能夠由決策者控制的因素是（A）A．銷售數(shù)量B．銷售價格C．顧客的需求D．競爭價格2．我們能夠通過（C)來驗證模型最優(yōu)解。A．觀察B．應用C．實驗D．調查3．建立運籌學模型的過程不涉及（A）階段.A．觀察環(huán)境B．數(shù)據(jù)分析C．模型設計D．模型實施4。建立模型的一種基本理由是去揭曉那些重要的或有關的（B）A數(shù)量B變量C約束條件D目的函數(shù)5。模型中規(guī)定變量取值（D）A可正B可負C非正D非負6.運籌學研究和解決問題的效果含有（A）A持續(xù)性B整體性C階段性D再生性7.運籌學運用數(shù)學辦法分析與解決問題，以達成系統(tǒng)的最優(yōu)目的。能夠說這個過程是一種（C)A解決問題過程B分析問題過程C科學決策過程D前期預策過程8。從趨勢上看，運籌學的進一步發(fā)展依賴于某些外部條件及手段,其中最重要的是（C）A數(shù)理統(tǒng)計B概率論C計算機D管理科學9.用運籌學解決問題時，要對問題進行（B）A分析與考察B分析和定義C分析和判斷D分析和實驗三、多選1模型中目的可能為（ABCDE)A輸入最少B輸出最大C成本最小D收益最大E時間最短2運籌學的重要分支涉及（ABDE）A圖論B線性規(guī)劃C非線性規(guī)劃D整數(shù)規(guī)劃E目的規(guī)劃四、簡答1．運籌學的計劃法涉及的環(huán)節(jié)。答:觀察、建立可選擇的解、用實驗選擇最優(yōu)解、擬定實際問題2．運籌學分析與解決問題普通要通過哪些環(huán)節(jié)?答：一、觀察待決策問題所處的環(huán)境二、分析和定義待決策的問題三、擬訂模型四、選擇輸入數(shù)據(jù)五、求解并驗證解的合理性六、實施最優(yōu)解3．運籌學的數(shù)學模型有哪些優(yōu)缺點?答：優(yōu)點：（1）．通過模型可覺得所要考慮的問題提供一種參考輪廓,指出不能直接看出的成果。（2）．花節(jié)省時間和費用。（3)．模型使人們能夠根據(jù)過去和現(xiàn)在的信息進行預測，可用于教育訓練,訓練人們看到他們決策的成果，而不必作出實際的決策.（4)．數(shù)學模型有能力揭示一種問題的抽象概念，從而能更簡要地揭示出問題的本質。（5）．數(shù)學模型便于運用計算機解決一種模型的重要變量和因素，并易于理解一種變量對其它變量的影響.模型的缺點（1）．數(shù)學模型的缺點之一是模型可能過分簡化,因而不能對的反映實際狀況。（2）．模型受設計人員的水平的限制，模型無法超越設計人員對問題的理解。（3)．發(fā)明模型有時需要付出較高的代價.4．運籌學的系統(tǒng)特性是什么？答:運籌學的系統(tǒng)特性能夠概括為下列四點：一、用系統(tǒng)的觀點研究功效關系二、應用各學科交叉的辦法三、采用計劃辦法四、為進一步研究揭發(fā)新問題5、線性規(guī)劃數(shù)學模型含有哪幾個要素？答：（1）.求一組決策變量xi或xij的值（i=1，2，…mj=1，2…n)使目的函數(shù)達成極大或極??；(2）。表達約束條件的數(shù)學式都是線性等式或不等式；（3）。表達問題最優(yōu)化指標的目的函數(shù)都是決策變量的線性函數(shù)第二章線性規(guī)劃的基本概念一、填空題1．線性規(guī)劃問題是求一種線性目的函數(shù)_在一組線性約束條件下的極值問題.2．圖解法合用于含有兩個變量的線性規(guī)劃問題。3．線性規(guī)劃問題的可行解是指滿足全部約束條件的解.4．在線性規(guī)劃問題的基本解中,全部的非基變量等于零。5．在線性規(guī)劃問題中，基可行解的非零分量所對應的列向量線性無關6．若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定能夠在可行域的頂點（極點）達成.7．線性規(guī)劃問題有可行解，則必有基可行解。8．如果線性規(guī)劃問題存在目的函數(shù)為有限值的最優(yōu)解，求解時只需在其基可行解_的集合中進行搜索即可得到最優(yōu)解。9．滿足非負條件的基本解稱為基本可行解.10．在將線性規(guī)劃問題的普通形式轉化為原則形式時，引入的松馳數(shù)量在目的函數(shù)中的系數(shù)為零。11．將線性規(guī)劃模型化成原則形式時，“≤”的約束條件要在不等式左_端加入松弛變量。12．線性規(guī)劃模型涉及決策（可控)變量，約束條件，目的函數(shù)三個要素。13．線性規(guī)劃問題可分為目的函數(shù)求極大值和極小_值兩類。14．線性規(guī)劃問題的原則形式中，約束條件取等式，目的函數(shù)求極大值，而全部變量必須非負。15．線性規(guī)劃問題的基可行解與可行域頂點的關系是頂點多于基可行解16．在用圖解法求解線性規(guī)劃問題時，如果獲得極值的等值線與可行域的一段邊界重疊，則這段邊界上的一切點都是最優(yōu)解。17．求解線性規(guī)劃問題可能的成果有無解，有唯一最優(yōu)解,有無窮多個最優(yōu)解。18。如果某個約束條件是“≤”情形，若化為原則形式，需要引入一松弛變量。19。如果某個變量Xj為自由變量，則應引進兩個非負變量Xj′,Xj〞，同時令Xj＝Xj′－Xj。20.體現(xiàn)線性規(guī)劃的簡式中目的函數(shù)為max(min)Z=∑cijxij.21。。(2.1P5))線性規(guī)劃普通體現(xiàn)式中,aij表達該元素位置在i行j列.二、單選題如果一種線性規(guī)劃問題有n個變量，m個約束方程(m<n)，系數(shù)矩陣的數(shù)為m，則基可行解的個數(shù)最為_C_。A．m個B．n個C．CnmD．Cmn個2．下圖形中陰影部分構成的集合是凸集的是A3．線性規(guī)劃模型不涉及下列_D要素。A．目的函數(shù)B．約束條件C．決策變量D．狀態(tài)變量4．線性規(guī)劃模型中增加一種約束條件，可行域的范疇普通將_B_。A．增大B．縮小C．不變D．不定5．若針對實際問題建立的線性規(guī)劃模型的解是無界的，不可能的因素是B__.A．出現(xiàn)矛盾的條件B．缺少必要的條件C．有多出的條件D．有相似的條件6．在下列線性規(guī)劃問題的基本解中，屬于基可行解的是DA．(一1，0，O)TB．(1，0,3，0）TC．(一4，0，0，3）TD．（0，一1,0，5）T7．有關線性規(guī)劃模型的可行域，下面_B_的敘述對的。A．可行域內(nèi)必有無窮多個點B．可行域必有界C．可行域內(nèi)必然涉及原點D．可行域必是凸的8．下列有關可行解，基本解，基可行解的說法錯誤的是_D__。A．可行解中包含基可行解B．可行解與基本解之間無交集C．線性規(guī)劃問題有可行解必有基可行解D．滿足非負約束條件的基本解為基可行解9。線性規(guī)劃問題有可行解，則AA必有基可行解B必有唯一最優(yōu)解C無基可行解D無唯一最優(yōu)解10。線性規(guī)劃問題有可行解且凸多邊形無界，這時CA沒有無界解B沒有可行解C有無界解D有有限最優(yōu)解11.若目的函數(shù)為求max，一種基可行解比另一種基可行解更加好的標志是AA使Z更大B使Z更小C絕對值更大DZ絕對值更小12。如果線性規(guī)劃問題有可行解，那么該解必須滿足DA全部約束條件B變量取值非負C全部等式規(guī)定D全部不等式規(guī)定13.如果線性規(guī)劃問題存在目的函數(shù)為有限值的最優(yōu)解，求解時只需在D集合中進行搜索即可得到最優(yōu)解。A基B基本解C基可行解D可行域14。線性規(guī)劃問題是針對D求極值問題。A約束B決策變量C秩D目的函數(shù)15如果第K個約束條件是“≤”情形，若化為原則形式，需要BA左邊增加一種變量B右邊增加一種變量C左邊減去一種變量D右邊減去一種變量16。若某個bk≤0,化為原則形式時原不等式DA不變B左端乘負1C右端乘負1D兩邊乘負117.為化為原則形式而引入的松弛變量在目的函數(shù)中的系數(shù)應為AA0B1C2D312.若線性規(guī)劃問題沒有可行解，可行解集是空集,則此問題BA沒有無窮多最優(yōu)解B沒有最優(yōu)解C有無界解D有無界解三、多選題在線性規(guī)劃問題的原則形式中，不可能存在的變量是D.A．可控變量B．松馳變量c．剩余變量D．人工變量2．下列選項中符合線性規(guī)劃模型原則形式規(guī)定的有BCDA．目的函數(shù)求極小值B．右端常數(shù)非負C．變量非負D．約束條件為等式E．約束條件為“≤”的不等式3．某線性規(guī)劃問題，n個變量,m個約束方程，系數(shù)矩陣的秩為m(m〈n）則下列說法對的的是ABDE。A．基可行解的非零分量的個數(shù)不不不大于mB．基本解的個數(shù)不會超出Cmn個C．該問題不會出現(xiàn)退化現(xiàn)象D．基可行解的個數(shù)不超出基本解的個數(shù)E．該問題的基是一種m×m階方陣4．若線性規(guī)劃問題的可行域是無界的,則該問題可能ABCDA．無有限最優(yōu)解B．有有限最優(yōu)解C．有唯一最優(yōu)解D．有無窮多個最優(yōu)解E．有有限多個最優(yōu)解5．判斷下列數(shù)學模型，哪些為線性規(guī)劃模型（模型中a．b．c為常數(shù)；θ為可取某一常數(shù)值的參變量，x，Y為變量）ACDE6．下列模型中，屬于線性規(guī)劃問題的原則形式的是ACD7．下列說法錯誤的有_ABD_.基本解是不不大于零的解B．極點與基解一一對應C．線性規(guī)劃問題的最優(yōu)解是唯一的D．滿足約束條件的解就是線性規(guī)劃的可行解8.在線性規(guī)劃的普通體現(xiàn)式中，變量xij為ABEA不不大于等于0B不大于等于0C不不大于0D不大于0E等于09。在線性規(guī)劃的普通體現(xiàn)式中，線性約束的體現(xiàn)有CDEA＜B＞C≤D≥E=10。若某線性規(guī)劃問題有無界解，應滿足的條件有ADAPk＜0B非基變量檢查數(shù)為零C基變量中沒有人工變量Dδj＞OE全部δj≤011.在線性規(guī)劃問題中a23表達AEAi=2Bi=3Ci=5Dj=2Ej=343。線性規(guī)劃問題若有最優(yōu)解，則最優(yōu)解ADA定在其可行域頂點達成B只有一種C會有無窮多個D唯一或無窮多個E其值為042。線性規(guī)劃模型涉及的要素有CDEA．目的函數(shù)B．約束條件C．決策變量D狀態(tài)變量E環(huán)境變量四、名詞1基：在線性規(guī)劃問題中，約束方程組的系數(shù)矩陣A的任意一種m×m階的非奇異子方陣B，稱為線性規(guī)劃問題的一種基.2、線性規(guī)劃問題:就是求一種線性目的函數(shù)在一組線性約束條件下的極值問題。3?？尚薪猓涸诰€性規(guī)劃問題中，凡滿足全部約束條件的解稱為線性規(guī)劃問題可行解4、行域：線性規(guī)劃問題的可行解集合。5、本解：在線性約束方程組中，對于選定的基B令全部的非基變量等于零，得到的解，稱為線性規(guī)劃問題的一種基本解。6。、圖解法：對于只有兩個變量的線性規(guī)劃問題，能夠用在平面上作圖的辦法來求解，這種辦法稱為圖解法。7、本可行解：在線性規(guī)劃問題中，滿足非負約束條件的基本解稱為基本可行解.8、模型是一件實際事物或實際狀況的代表或抽象,它根據(jù)因果顯示出行動與反映的關系和客觀事物的內(nèi)在聯(lián)系。四、把下列線性規(guī)劃問題化成原則形式：2、minZ=2x1—x2+2x3五、按各題規(guī)定.建立線性規(guī)劃數(shù)學模型1、某工廠生產(chǎn)A、B、C三種產(chǎn)品，每種產(chǎn)品的原材料消耗量、機械臺時消耗量以及這些資源的限量,單位產(chǎn)品的利潤以下表所示：根據(jù)客戶訂貨，三種產(chǎn)品的最低月需要量分別為200，250和100件，最大月銷售量分別為250,280和120件。月銷售分別為250，280和120件。問如何安排生產(chǎn)計劃，使總利潤最大。2、某建筑工地有一批長度為10米的相似型號的鋼筋，今要截成長度為3米的鋼筋90根,長度為4米的鋼筋60根，問如何下料，才干使所使用的原材料最省?某運輸公司在春運期間需要24小時晝夜加班工作，需要的人員數(shù)量以下表所示：起運時間服務員數(shù)2-66-1010一1414-1818—2222-248107124每個工作人員持續(xù)工作八小時,且在時段開始時上班，問如何安排，使得既滿足以上規(guī)定，又使上班人數(shù)最少？第三章線性規(guī)劃的基本辦法一、填空題1．線性規(guī)劃的代數(shù)解法重要運用了代數(shù)消去法的原理，實現(xiàn)基可行解的轉換，尋找最優(yōu)解。2．原則形線性規(guī)劃典式的目的函數(shù)的矩陣形式是_maxZ=CBB－1b+（CN－CBB－1N）XN。3．對于目的函數(shù)極大值型的線性規(guī)劃問題，用單純型法求解時，當基變量檢查數(shù)δj_≤_0時，現(xiàn)在解為最優(yōu)解。4．用大M法求目的函數(shù)為極大值的線性規(guī)劃問題時，引入的人工變量在目的函數(shù)中的系數(shù)應為－M。5．在單純形迭代中，能夠根據(jù)最后_表中人工變量不為零判斷線性規(guī)劃問題無解。6．在線性規(guī)劃典式中,全部基變量的目的系數(shù)為0.7．當線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時，普通能夠加入人工變量構造可行基。8．在單純形迭代中，選出基變量時應遵照最小比值θ法則。9．線性規(guī)劃典式的特點是基為單位矩陣,基變量的目的函數(shù)系數(shù)為0。10．對于目的函數(shù)求極大值線性規(guī)劃問題在非基變量的檢查數(shù)全部δj≤O、問題無界時，問題無解時狀況下，單純形迭代應停止。11．在單純形迭代過程中,若有某個δk>0對應的非基變量xk的系數(shù)列向量Pk_≤0_時,則此問題是無界的。12．在線性規(guī)劃問題的典式中，基變量的系數(shù)列向量為單位列向量_13。對于求極小值而言,人工變量在目的函數(shù)中的系數(shù)應取—114.(單純形法解基的形成來源共有三種15.在大M法中，M表達充足大正數(shù)。二、單選題1．線性規(guī)劃問題C 2．在單純形迭代中,出基變量在緊接著的下一次迭代中B立刻進入基底。A．會B．不會C．有可能D．不一定3．在單純形法計算中，如不按最小比值原則選用換出變量，則在下一種解中B.A．不影響解的可行性B．最少有一種基變量的值為負C．找不到出基變量D．找不到進基變量4．用單純形法求解極大化線性規(guī)劃問題中，若某非基變量檢查數(shù)為零，而其它非基變量檢查數(shù)全部〈0，則闡明本問題B。A．有惟一最優(yōu)解B．有多重最優(yōu)解C．無界D．無解5．線性規(guī)劃問題maxZ=CX，AX=b，X≥0中,選定基B，變量Xk的系數(shù)列向量為Pk，則在有關基B的典式中，Xk的系數(shù)列向量為_DA．BPKB．BTPKC．PKBD．B-1PK6．下列說法錯誤的是B圖解法與單純形法從幾何理解上是一致的B．在單純形迭代中，進基變量能夠任選C．在單純形迭代中，出基變量必須按最小比值法則選用D．人工變量離開基底后,不會再進基7.單純形法當中，入基變量的擬定應選擇檢查數(shù)CA絕對值最大B絕對值最小C正值最大D負值最小8.在單純形表的終表中，若若非基變量的檢查數(shù)有0，那么最優(yōu)解AA不存在B唯一C無窮多D無窮大9.若在單純形法迭代中,有兩個Q值相等，當分別取這兩個不同的變量為入基變量時，獲得的成果將是CA先優(yōu)后劣B先劣后優(yōu)C相似D會隨目的函數(shù)而變化10.若某個約束方程中含有系數(shù)列向量為單位向量的變量，則該約束方程不必再引入CA松弛變量B剩余變量C人工變量D自由變量11。在線性規(guī)劃問題的典式中,基變量的系數(shù)列向量為DA單位陣B非單位陣C單位行向量D單位列向量12。在約束方程中引入人工變量的目的是DA體現(xiàn)變量的多樣性B變不等式為等式C使目的函數(shù)為最優(yōu)D形成一種單位陣13。出基變量的含義是DA該變量取值不變B該變量取值增大C由0值上升為某值D由某值下降為014.在我們所使用的教材中對單純形目的函數(shù)的討論都是針對B狀況而言的。AminBmaxCmin+maxDmin，max任選15.求目的函數(shù)為極大的線性規(guī)劃問題時，若全部非基變量的檢查數(shù)≤O，且基變量中有人工變量時該問題有BA無界解B無可行解C唯一最優(yōu)解D無窮多最優(yōu)解三、多選題對取值無約束的變量xj。普通令xj=xj'—x”j，其中xj'≥0，xj”≥0，在用單純形法求得的最優(yōu)解中，可能出現(xiàn)的是ABC2．線性規(guī)劃問題maxZ=x1+CX2其中4≤c≤6，一1≤a≤3，10≤b≤12,則當_BC時，該問題的最優(yōu)目的函數(shù)值分別達成上界或下界.A．c=6a=—1b=10B．c=6a=—1b=12C．c=4a=3b=12D．c=4a=3b=12E．c=6a=3b=123．設X（1)，X(2)是用單純形法求得的某一線性規(guī)劃問題的最優(yōu)解，則闡明ACDE.A．此問題有無窮多最優(yōu)解B．該問題是退化問題C．此問題的全部最優(yōu)解可表達為λX(1)+（1一λ）X（2），其中0≤λ≤1D．X（1)，X(2)是兩個基可行解E．X（1），X(2)的基變量個數(shù)相似4．某線性規(guī)劃問題，含有n個變量，m個約束方程，（m〈n）,系數(shù)矩陣的秩為m，則ABD.A．該問題的典式不超出CNM個B．基可行解中的基變量的個數(shù)為m個C．該問題一定存在可行解D．該問題的基至多有CNM=1個E．該問題有111個基可行解5．單純形法中，在進行換基運算時，應ACDE。A．先選用進基變量,再選用出基變量B．先選出基變量，再選進基變量C．進基變量的系數(shù)列向量應化為單位向量D．旋轉變換時采用的矩陣的初等行變換E．出基變量的選用是根據(jù)最小比值法則6．從一張單純形表中能夠看出的內(nèi)容有ABCE。A．一種基可行解B．現(xiàn)在解與否為最優(yōu)解C．線性規(guī)劃問題與否出現(xiàn)退化D．線性規(guī)劃問題的最優(yōu)解E．線性規(guī)劃問題與否無界7.單純形表迭代停止的條件為（AB）A全部δj均不大于等于0B全部δj均不大于等于0且有aik≤0C全部aik＞0D全部bi≤08.下列解中可能成為最優(yōu)解的有(ABCDE）A基可行解B迭代一次的改善解C迭代兩次的改善解D迭代三次的改善解E全部檢查數(shù)均不大于等于0且解中無人工變量9、若某線性規(guī)劃問題有無窮多最優(yōu)解，應滿足的條件有（BCE）APk＜Pk0B非基變量檢查數(shù)為零C基變量中沒有人工變量Dδj＜OE全部δj≤010。下列解中可能成為最優(yōu)解的有（ABCDE)A基可行解B迭代一次的改善解C迭代兩次的改善解D迭代三次的改善解E全部檢查數(shù)均不大于等于0且解中無人工變量四、名詞、簡答1、人造初始可行基:當我們無法從一種原則的線性規(guī)劃問題中找到一種m階單位矩陣時，普通在約束方程中引入人工變量，而在系數(shù)矩陣中湊成一種m階單位矩陣，進而形成的一種初始可行基稱為人造初始可行基。2、單純形法解題的基本思路？可行域的一種基本可行解開始，轉移到另一種基本可行解，并且使目的函數(shù)值逐步得到改善，直到最后球場最優(yōu)解或鑒定原問題無解.五、分別用圖解法和單純形法求解下列線性規(guī)劃問題．并對照指出單純形迭代的每一步相稱于圖解法可行域中的哪一種頂點。六、用單純形法求解下列線性規(guī)劃問題:七、用大M法求解下列線性規(guī)劃問題.并指出問題的解屬于哪一類.八、下表為用單純形法計算時某一步的表格。已知該線性規(guī)劃的目的函數(shù)為maxZ=5x1+3x2，約束形式為“≤”,X3，X4為松馳變量．表中解代入目的函數(shù)后得Z=10XlX2X3X4—10b-1fgX32CO11／5Xlade01(1）求表中a～g的值（2)表中給出的解與否為最優(yōu)解?（1）a=2b=0c=0d=1e=4/5f=0g=－5（2）表中給出的解為最優(yōu)解第四章線性規(guī)劃的對偶理論一、填空題1．線性規(guī)劃問題含有對偶性，即對于任何一種求最大值的線性規(guī)劃問題，都有一種求最小值/極小值的線性規(guī)劃問題與之對應，反之亦然。2．在一對對偶問題中，原問題的約束條件的右端常數(shù)是對偶問題的目的函數(shù)系數(shù)。3．如果原問題的某個變量無約束，則對偶問題中對應的約束條件應為等式_。4．對偶問題的對偶問題是原問題_.5．若原問題可行，但目的函數(shù)無界,則對偶問題不可行。6．若某種資源的影子價格等于k。在其它條件不變的狀況下(假設原問題的最佳基不變)，當該種資源增加3個單位時。對應的目的函數(shù)值將增加3k。7．線性規(guī)劃問題的最優(yōu)基為B，基變量的目的系數(shù)為CB，則其對偶問題的最優(yōu)解Y﹡=CBB－1。8．若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX﹡=Y﹡b.9．若X、Y分別是線性規(guī)劃的原問題和對偶問題的可行解,則有CX≤Yb.10．若X﹡和Y﹡分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則有CX﹡=Y*b.11．設線性規(guī)劃的原問題為maxZ=CX,Ax≤b，X≥0，則其對偶問題為min=YbYA≥c Y≥0_。12．影子價格事實上是與原問題各約束條件相聯(lián)系的對偶變量的數(shù)量體現(xiàn)。13．線性規(guī)劃的原問題的約束條件系數(shù)矩陣為A,則其對偶問題的約束條件系數(shù)矩陣為AT.14．在對偶單純形法迭代中，若某bi<0，且全部的aij≥0(j=1，2,…n)，則原問題_無解。二、單選題1．線性規(guī)劃原問題的目的函數(shù)為求極小值型，若其某個變量不大于等于0，則其對偶問題約束條件為A形式.A．“≥”B．“≤”C，“〉”D．“=”2．設、分別是原則形式的原問題與對偶問題的可行解，則C。3．對偶單純形法的迭代是從_A_開始的.A．正則解B．最優(yōu)解C．可行解D．基本解4．如果z。是某原則型線性規(guī)劃問題的最優(yōu)目的函數(shù)值，則其對偶問題的最優(yōu)目的函數(shù)值w﹡A。A．W﹡=Z﹡B．W﹡≠Z﹡C．W﹡≤Z﹡D．W﹡≥Z﹡5．如果某種資源的影子價格不不大于其市場價格，則闡明_BA．該資源過剩B．該資源稀缺C．公司應盡快解決該資源D．公司應充足運用該資源，開僻新的生產(chǎn)途徑三、多選題1．在一對對偶問題中，可能存在的狀況是ABC。A．一種問題有可行解，另一種問題無可行解B．兩個問題都有可行解C．兩個問題都無可行解D．一種問題無界,另一種問題可行2．下列說法錯誤的是B .A．任何線性規(guī)劃問題都有一種與之對應的對偶問題B．對偶問題無可行解時，其原問題的目的函數(shù)無界。C．若原問題為maxZ=CX，AX≤b,X≥0，則對偶問題為minW=Yb，YA≥C,Y≥0.D．若原問題有可行解，但目的函數(shù)無界,其對偶問題無可行解。3．如線性規(guī)劃的原問題為求極大值型，則下列有關原問題與對偶問題的關系中對的的是BCDE。A原問題的約束條件“≥”，對應的對偶變量“≥0"B原問題的約束條件為“="，對應的對偶變量為自由變量C．原問題的變量“≥0"，對應的對偶約束“≥”D．原問題的變量“≤O”對應的對偶約束“≤"E．原問題的變量無符號限制,對應的對偶約束“=”4．一對互為對偶的問題存在最優(yōu)解，則在其最優(yōu)點處有BDA．若某個變量取值為0，則對應的對偶約束為嚴格的不等式B．若某個變量取值為正,則對應的對偶約束必為等式C．若某個約束為等式，則對應的對偶變?nèi)≈禐檎鼶．若某個約束為嚴格的不等式，則對應的對偶變量取值為0E．若某個約束為等式,則對應的對偶變量取值為05．下列有關對偶單純形法的說法對的的是ABCD。A．在迭代過程中應先選出基變量，再選進基變量B．當?shù)械玫降慕鉂M足原始可行性條件時,即得到最優(yōu)解C．初始單純形表中填列的是一種正則解D．初始解不需要滿足可行性E．初始解必須是可行的。6．根據(jù)對偶理論，在求解線性規(guī)劃的原問題時,能夠得到下列結論ACD。對偶問題的解B．市場上的稀缺狀況C．影子價格D．資源的購銷決策E．資源的市場價格7．在下列線性規(guī)劃問題中，CE采用求其對偶問題的辦法，單純形迭代的環(huán)節(jié)普通會減少。四、名詞、簡答題1、對偶可行基：凡滿足條件δ=C-CBB—1A≤0的基B稱為對偶可行基。2、.對稱的對偶問題：設原始線性規(guī)劃問題為maxZ=CXs.tAX≤bX≥0稱線性規(guī)劃問題minW=Ybs。tYA≥CY≥0為其對偶問題.又稱它們?yōu)橐粚ΨQ的對偶問題。3、影子價格：對偶變量Yi表達與原問題的第i個約束條件相對應的資源的影子價格，在數(shù)量上體現(xiàn)為,當該約束條件的右端常數(shù)增加一種單位時（假設原問題的最優(yōu)解不變），原問題目的函數(shù)最優(yōu)值增加的數(shù)量。4．影子價格在經(jīng)濟管理中的作用。（1）指出公司內(nèi)部挖潛的方向;（2）為資源的購銷決策提供根據(jù)；（3)分析現(xiàn)有產(chǎn)品價格變動時資源緊缺狀況的影響；(4）分析資源節(jié)省所帶來的收益；（5）決定某項新產(chǎn)品與否應投產(chǎn)。5．線性規(guī)劃對偶問題能夠采用哪些辦法求解？（1）用單純形法解對偶問題;(2)由原問題的最優(yōu)單純形表得到;（3）由原問題的最優(yōu)解運用互補松弛定理求得；（4)由Y＊=CBB—1求得，其中B為原問題的最優(yōu)基6、一對對偶問題可能出現(xiàn)的情形：1.原問題和對偶問題都有最優(yōu)解，且兩者相等；2.一種問題含有無界解，則另一種問題含有無可行解;3。原問題和對偶問題都無可行解。五、寫出下列線性規(guī)劃問題的對偶問題1．minZ=2x1+2x2+4x3六、已知線性規(guī)劃問題應用對偶理論證明該問題最優(yōu)解的目的函數(shù)值不不不大于25七、已知線性規(guī)劃問題maxZ=2x1+x2+5x3+6x4其對偶問題的最優(yōu)解為Yl﹡=4，Y2﹡=1，試應用對偶問題的性質求原問題的最優(yōu)解。七、用對偶單純形法求解下列線性規(guī)劃問題：八、已知線性規(guī)劃問題寫出其對偶問題(2）已知原問題最優(yōu)解為X﹡=（2，2,4，0）T,試根據(jù)對偶理論,直接求出對偶問題的最優(yōu)解。W*=16第五章線性規(guī)劃的敏捷度分析一、填空題1、敏捷度分析研究的是線性規(guī)劃模型的原始、最優(yōu)解數(shù)據(jù)變化對產(chǎn)生的影響。2、在線性規(guī)劃的敏捷度分析中，我們重要用到的性質是_可行性，正則性。3．在敏捷度分析中，某個非基變量的目的系數(shù)的變化，將引發(fā)該非基變量本身的檢查數(shù)的變化.4．如果某基變量的目的系數(shù)的變化范疇超出其敏捷度分析允許的變化范疇，則此基變量應出基。5．約束常數(shù)b；的變化,不會引發(fā)解的正則性的變化。6．在某線性規(guī)劃問題中，已知某資源的影子價格為Y1，對應的約束常數(shù)b1,在敏捷度允許變動范疇內(nèi)發(fā)生Δb1的變化，則新的最優(yōu)解對應的最優(yōu)目的函數(shù)值是Z*+yi△b(設原最優(yōu)目的函數(shù)值為Z﹡）7．若某約束常數(shù)bi的變化超出其允許變動范疇，為求得新的最優(yōu)解，需在原最優(yōu)單純形表的基礎上運用對偶單純形法求解。8．已知線性規(guī)劃問題，最優(yōu)基為B，目的系數(shù)為CB，若新增變量xt，目的系數(shù)為ct，系數(shù)列向量為Pt，則當Ct≤CBB－1Pt時，xt不能進入基底.9．如果線性規(guī)劃的原問題增加一種約束條件，相稱于其對偶問題增加一種變量。10、若某線性規(guī)劃問題增加一種新的約束條件,在其最優(yōu)單純形表中將體現(xiàn)為增加一行，一列。11．線性規(guī)劃敏捷度分析應在最優(yōu)單純形表的基礎上，分析系數(shù)變化對最優(yōu)解產(chǎn)生的影響12．在某生產(chǎn)規(guī)劃問題的線性規(guī)劃模型中，變量xj的目的系數(shù)Cj代表該變量所對應的產(chǎn)品的利潤,則當某一非基變量的目的系數(shù)發(fā)生增大變化時,其有可能進入基底.二、單選題1．若線性規(guī)劃問題最優(yōu)基中某個基變量的目的系數(shù)發(fā)生變化，則C。A．該基變量的檢查數(shù)發(fā)生變化B．其它基變量的檢查數(shù)發(fā)生變化C．全部非基變量的檢查數(shù)發(fā)生變化D．全部變量的檢查數(shù)都發(fā)生變化2．線性規(guī)劃敏捷度分析的重要功效是分析線性規(guī)劃參數(shù)變化對D的影響。A．正則性B．可行性C．可行解D．最優(yōu)解3．在線性規(guī)劃的各項敏感性分析中，一定會引發(fā)最優(yōu)目的函數(shù)值發(fā)生變化的是B。A．目的系數(shù)cj的變化B．約束常數(shù)項bi變化C．增加新的變量D．增加新約束4．在線性規(guī)劃問題的多個敏捷度分析中,B_的變化不能引發(fā)最優(yōu)解的正則性變化。A．目的系數(shù)B．約束常數(shù)C．技術系數(shù)D．增加新的變量E．增加新的約束條件5．對于原則型的線性規(guī)劃問題，下列說法錯誤的是CA．在新增變量的敏捷度分析中，若新變量能夠進入基底，則目的函數(shù)將會得到進一步改善。B．在增加新約束條件的敏捷度分析中，新的最優(yōu)目的函數(shù)值不可能增加。C．當某個約束常數(shù)bk增加時，目的函數(shù)值一定增加。D．某基變量的目的系數(shù)增大，目的函數(shù)值將得到改善6.敏捷度分析研究的是線性規(guī)劃模型中最優(yōu)解和C之間的變化和影響.A基B松弛變量C原始數(shù)據(jù)D條件系數(shù)三、多選題1．如果線性規(guī)劃中的cj、bi同時發(fā)生變化，可能對原最優(yōu)解產(chǎn)生的影響是_ABCD.A．正則性不滿足，可行性滿足B．正則性滿足，可行性不滿足C．正則性與可行性都滿足D．正則性與可行性都不滿足E．可行性和正則性中只可能有一種受影響2．在敏捷度分析中，我們能夠直接從最優(yōu)單純形表中獲得的有效信息有ABCE。A．最優(yōu)基B的逆B-1B．最優(yōu)解與最優(yōu)目的函數(shù)值C．各變量的檢查數(shù)D．對偶問題的解E．各列向量3．線性規(guī)劃問題的各項系數(shù)發(fā)生變化，下列不能引發(fā)最優(yōu)解的可行性變化的是ABC_。A．非基變量的目的系數(shù)變化B．基變量的目的系數(shù)變化C．增加新的變量D,增加新的約束條件4．下列說法錯誤的是ACDA．若最優(yōu)解的可行性滿足B-1b≥0,則最優(yōu)解不發(fā)生變化B．目的系數(shù)cj發(fā)生變化時，解的正則性將受到影響C．某個變量xj的目的系數(shù)cj發(fā)生變化，只會影響到該變量的檢查數(shù)的變化D．某個變量xj的目的系數(shù)cj發(fā)生變化，會影響到全部變量的檢查數(shù)發(fā)生變化。四、名詞、簡答題1.敏捷度分析:研究線性規(guī)劃模型的原始數(shù)據(jù)變化對最優(yōu)解產(chǎn)生的影響2．線性規(guī)劃問題敏捷度分析的意義。（1）預先擬定保持現(xiàn)有生產(chǎn)規(guī)劃條件下，單位產(chǎn)品利潤的可變范疇；(2)當資源限制量發(fā)生變化時，擬定新的生產(chǎn)方案;（3）擬定某種新產(chǎn)品的投產(chǎn)在經(jīng)濟上與否有利；（4）考察建模時無視的約束對問題的影響程度;（5）當產(chǎn)品的設計工藝變化時,原最優(yōu)方案與否需要調節(jié)。四、某工廠在計劃期內(nèi)要安排生產(chǎn)I、Ⅱ兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)品所需的設備臺時及A、B兩種原料的消耗如表所示：IⅡ設備原材料A原材料B1402048臺時16kg12kg該工廠每生產(chǎn)一件產(chǎn)品I可獲利2百元，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3百元.(1)單純形迭代的初始表及最后表分別以下表I、Ⅱ所示:x1x2x3x4x5xB -Z023O00X3X4X581612121O040010040011400—3/2-1/80XlX5X24421001/4000-21/21011/2—1/80闡明使工廠獲利最多的產(chǎn)品混合生產(chǎn)方案。（2)如該廠從別處抽出4臺時的設備用于生產(chǎn)I、Ⅱ,求這時該廠生產(chǎn)產(chǎn)品I、Ⅱ的最優(yōu)方案。（3)擬定原最優(yōu)解不變條件下，產(chǎn)品Ⅱ的單位利潤可變范疇。（4）該廠預備引進一種新產(chǎn)品Ⅲ，已知生產(chǎn)每件產(chǎn)品Ⅲ，需消耗原材料A、B分別為6kg，3kg使用設備2臺時，可獲利5百元，問該廠與否應生產(chǎn)該產(chǎn)品及生產(chǎn)多少？(1)使工廠獲利最多的產(chǎn)品混合生產(chǎn)方案：生產(chǎn)I產(chǎn)品4件,生產(chǎn)II產(chǎn)品2件,設備臺時與原材料A全部用完，原材料B剩余4kg，此時，獲利14百元.（2）X*=(4,3,2，0，o）Tz＊=17(3)0≤C2≤4(4）應生產(chǎn)產(chǎn)品Ⅲ，產(chǎn)量為2。五、給出線性規(guī)劃問題用單純形表求解得單純形表以下，試分析下列多個條件變化下最優(yōu)解（基）的變化:xlx2x3x4x5xB -Z-800-3—5—1xlx21210—14—1012-11(1)分別擬定目的函數(shù)中變量X1和X2的系數(shù)C1，c2在什么范疇內(nèi)變動時最優(yōu)解不變；(2）目的函數(shù)中變量X3的系數(shù)變?yōu)?;(3）增添新的約束X1+2x2+x3≤4解：（1)3/4≤C1≤32≤C2≤8(2）X*=(2，0,1，0,0，0)TZ*=10（3)X*=（2,1,0，0，1，0)TZ＊=7（4)X＊=（0,2,0，0,0，1/3)TZ*=25/3第六章物資調運規(guī)劃運輸問題一、填空題物資調運問題中，有m個供應地，Al，A2…，Am，Aj的供應量為ai（i=1，2…，m），n個需求地B1，B2,…Bn，B的需求量為bj(j=1，2，…，n),則供需平衡條件為=2．物資調運方案的最優(yōu)性鑒別準則是：當全部檢查數(shù)非負時，現(xiàn)在的方案一定是最優(yōu)方案。3．能夠作為表上作業(yè)法的初始調運方案的填有數(shù)字的方格數(shù)應為m+n－1個(設問題中含有m個供應地和n個需求地）4．若調運方案中的某一空格的檢查數(shù)為1，則在該空格的閉回路上調節(jié)單位運置而使運費增加1。5．調運方案的調節(jié)是要在檢查數(shù)出現(xiàn)負值的點為頂點所對應的閉回路內(nèi)進行運量的調節(jié)。6．按照表上作業(yè)法給出的初始調運方案,從每一空格出發(fā)能夠找到且僅能找到_1條閉回路7．在運輸問題中,單位運價為Cij位勢分別用ui,Vj表達，則在基變量處有cijCij=ui+Vj。8、供不不大于求的、供不應求的不平衡運輸問題,分別是指_＞的運輸問題、_＜的運輸問題。10．在表上作業(yè)法所得到的調運方案中，從某空格出發(fā)的閉回路的轉角點所對應的變量必為基變量。11．在某運輸問題的調運方案中，點(2，2）的檢查數(shù)為負值，（調運方案為表所示）則對應的調節(jié)量應為300_.IⅡⅢⅣA300100300B400C60030012.若某運輸問題初始方案的檢查數(shù)中只有一種負值：－2，則這個－2的含義是該檢查數(shù)所在格單位調節(jié)量.13。運輸問題的初始方案中的基變量取值為正.14表上作業(yè)法中，每一次調節(jié)1個“入基變量".15。在編制初始方案調運方案及調節(jié)中,如出現(xiàn)退化，則某一種或多個點處應填入數(shù)字016運輸問題的模型中,含有的方程個數(shù)為n+M個。17表上作業(yè)法中,每一次調節(jié),“出基變量”的個數(shù)為1個.18給出初始調運方案的辦法共有三種.19.運輸問題中，每一行或列若有閉回路的頂點,則必有兩個。二、單選題1、在運輸問題中,能夠作為表上作業(yè)法的初始基可行解的調運方案應滿足的條件是D。A．含有m+n-1個基變量B．基變量不構成閉回路C．含有m+n一1個基變量且不構成閉回路D．含有m+n一1個非零的基變量且不構成閉回2．若運輸問題的單位運價表的某一行元素分別加上一種常數(shù)k，最優(yōu)調運方案將B。A．發(fā)生變化B．不發(fā)生變化C．A、B都有可能3．在表上作業(yè)法求解運輸問題中，非基變量的檢查數(shù)D.A．不不大于0B．不大于0C．等于0D．以上三種都可能4.運輸問題的初始方案中，沒有分派運量的格所對應的變量為BA基變量B非基變量C松弛變量D剩余變量5。表上作業(yè)法的基本思想和環(huán)節(jié)與單純形法類似，那么基變量所在格為CA有單位運費格B無單位運費格C有分派數(shù)格D無分派數(shù)格6.表上作業(yè)法中初始方案均為AA可行解B非可行解C待改善解D最優(yōu)解7.閉回路是一條封閉折線，每一條邊都是DA水平B垂直C水平＋垂直D水平或垂直8當供應量不不大于需求量，欲化為平衡問題,可虛設一需求點，并令其對應運價為DA0B全部運價中最小值C全部運價中最大值D最大與最小運量之差9.運輸問題中分派運量的格所對應的變量為AA基變量B非基變量C松弛變量D剩余變量10.全部物資調運問題，應用表上作業(yè)法最后均能找到一種DA可行解B非可行解C待改善解D最優(yōu)解11.普通講，在給出的初始調運方案中,最靠近最優(yōu)解的是CA西北角法B最小元素法C差值法D位勢法12。在運輸問題中,調節(jié)對象的擬定應選擇CA檢查數(shù)為負B檢查數(shù)為正C檢查數(shù)為負且絕對值最大D檢查數(shù)為負且絕對值最小13。運輸問題中，調運方案的調節(jié)應在檢查數(shù)為C負值的點所在的閉回路內(nèi)進行。A任意值B最大值C絕對值最大D絕對值最小14。表上作業(yè)法的基本思想和環(huán)節(jié)與單純形法類似，因而初始調運方案的給出就相稱于找到一種CA基B可行解C初始基本可行解D最優(yōu)解15平衡運輸問題即是指m個供應地的總供應量Dn個需求地的總需求量。A不不大于B不不大于等于C不大于D等于三、多選題1．運輸問題的求解成果中可能出現(xiàn)的是ABC_.A、惟一最優(yōu)解B．無窮多最優(yōu)解C．退化解D．無可行解2．下列說法對的的是ABD。A．表上作業(yè)法也是從尋找初始基可行解開始的B．當一種調運方案的檢查數(shù)全部為正值時，現(xiàn)在方案一定是最佳方案C．最小元素法所求得的運輸?shù)倪\量是最小的D．表上作業(yè)法中一張供需平衡表對應一種基可行解3．對于供過于求的不平衡運輸問題，下列說法對的的是ABC。A．仍然能夠應用表上作業(yè)法求解B．在應用表上作業(yè)法之前，應將其轉化為平衡的運輸問題C．能夠虛設一種需求地點,令其需求量為供應量與需求量之差.D．令虛設的需求地點與各供應地之間運價為M（M為極大的正數(shù))4．下列有關運輸問題模型特點的說法對的的是ABD約束方程矩陣含有稀疏構造B．基變量的個數(shù)是m+n-1個C．基變量中不能有零D．基變量不構成閉回路5。對于供過于求的不平衡運輸問題，下列說法對的的是ABCA．仍然能夠應用表上作業(yè)法求解B．在應用表上作業(yè)法之前，應將其轉化為平衡的運輸問題C．能夠虛設一種需求地點,令其需求量為供應量與需求量之差。D．令虛設的需求地點與各供應地之間運價為M（M為極大的正數(shù))E.能夠虛設一種庫存，令其庫存量為0三、判斷表(a)（b)(c)中給出的調運方案能否作為表上作業(yè)法求解時的初始解，為什么？(a)BlB2B3B4B5B6產(chǎn)量Al201030A2302050A3101050575A42020銷量204030105025（b)（c)BlB2B3B4B5B6產(chǎn)量BlB2B3B4產(chǎn)量Al3030Al6511A2203050A254211A31030102575A3538A42020銷量5997銷量204030105025（a）可作為初始方案；(b）中填有數(shù)字的方格數(shù)少于9（產(chǎn)地數(shù)+銷地數(shù)－1),不能作為初始方案；(c)中存在以非零元素為頂點的閉回路,不能作為初始方案四、已知某運輸問題的產(chǎn)銷平衡表。單位運價表及給出的一種調運方案分別見表（a）和（b）,判斷給出的調運方案與否為最優(yōu)?如是闡明理由;如否。也闡明理由。表(a)產(chǎn)銷平衡表及某一調運方案單位運價表銷地產(chǎn)地BlB2B3B4B5B6產(chǎn)量l302050A2301040A310401060A4201131銷量305020403011五、給出以下運輸問題銷運價銷產(chǎn)B1B2B3B4產(chǎn)量Al5310490A2169640A320105770銷量30508040200(1）應用最小元素法求其初始方案;（2）應用位勢法求初始方案的檢查數(shù),并檢查該方案與否為最優(yōu)方案六、用表上作業(yè)法求給出的運輸問題的最優(yōu)解甲乙丙丁產(chǎn)量11067124216059935410104銷量5246甲乙丙丁產(chǎn)量112142369344銷量5246在最優(yōu)調運方案下的運輸費用最小為118。七、名詞平衡運輸問題：m個供應地的供應量等于n個需求地的總需求量，這樣的運輸問題稱平衡運輸問題。2、不平衡運輸問題:m個供應地的供應量不等于n個需求地的總需求量,這樣的運輸問題稱不平衡運輸問題。第七章整數(shù)規(guī)劃一、填空題1．用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一種可行解的目的函數(shù)值是該問題目的函數(shù)值的下界。2．在分枝定界法中，若選Xr=4／3進行分支,則構造的約束條件應為X1≤1,X1≥2。3．已知整數(shù)規(guī)劃問題P0，其對應的松馳問題記為P0’，若問題P0’無可行解，則問題P.無可行解。4．在0-1整數(shù)規(guī)劃中變量的取值可能是_0或1。5．對于一種有n項任務需要有n個人去完畢的分派問題,其解中取值為1的變量數(shù)為n個。6．分枝定界法和割平面法的基礎都是用_線性規(guī)劃辦法求解整數(shù)規(guī)劃.7．若在對某整數(shù)規(guī)劃問題的松馳問題進行求解時，得到最優(yōu)單純形表中，由X。所在行得X1+1／7x3+2／7x5=13／7，則以X1行為源行的割平面方程為_－X3－X5≤0_。8．在用割平面法求解整數(shù)規(guī)劃問題時，規(guī)定全部變量必須都為整數(shù).9．用割平面法求解整數(shù)規(guī)劃問題時,若某個約束條件中有不為整數(shù)的系數(shù)，則需在該約束兩端擴大適宜倍數(shù),將全部系數(shù)化為整數(shù)。10．求解純整數(shù)規(guī)劃的辦法是割平面法。求解混合整數(shù)規(guī)劃的辦法是分枝定界法_.11．求解0—1整數(shù)規(guī)劃的辦法是隱枚舉法。求解分派問題的專門辦法是匈牙利法。12．在應用匈牙利法求解分派問題時，最后求得的分派元應是獨立零元素_.13.分枝定界法普通每次分枝數(shù)量為2個。二、單選題1．整數(shù)規(guī)劃問題中，變量的取值可能是D。A．整數(shù)B．0或1C．不不大于零的非整數(shù)D．以上三種都可能2．在下列整數(shù)規(guī)劃問題中，分枝定界法和割平面法都能夠采用的是A。A．純整數(shù)規(guī)劃B．混合整數(shù)規(guī)劃C．0-1規(guī)劃D．線性規(guī)劃3．下列辦法中用于求解分派問題的是D_。A．單純形表B．分枝定界法C．表上作業(yè)法D．匈牙利法三、多選1．下列闡明不對的的是ABC。A．求解整數(shù)規(guī)劃能夠采用求解其對應的松馳問題，然后對其非整數(shù)值的解四舍五入的辦法得到整數(shù)解。B．用分枝定界法求解一種極大化的整數(shù)規(guī)劃問題，當?shù)玫蕉嘤谝环N可行解時，普通任取其中一種作為下界。C．用割平面法求解整數(shù)規(guī)劃時，構造的割平面可能割去某些不屬于最優(yōu)解的整數(shù)解。D．用割平面法求解整數(shù)規(guī)劃問題時，必須首先將原問題的非整數(shù)的約束系數(shù)及右端常數(shù)化為整數(shù)。2．在求解整數(shù)規(guī)劃問題時，可能出現(xiàn)的是ABC。A．唯一最優(yōu)解B．無可行解C．多重最佳解D．無窮多個最優(yōu)解3．有關分派問題的下列說法對的的是_ABD.A．分派問題是一種高度退化的運輸問題B．能夠用表上作業(yè)法求解分派問題C．從分派問題的效益矩陣中逐行取其最小元素，可得到最優(yōu)分派方案D．匈牙利法所能求解的分派問題,規(guī)定規(guī)定一種人只能完畢一件工作，同時一件工作也只給一種人做。4.整數(shù)規(guī)劃類型涉及（CDE）A線性規(guī)劃B非線性規(guī)劃C純整數(shù)規(guī)劃D混合整數(shù)規(guī)劃E0—1規(guī)劃5.對于某一整數(shù)規(guī)劃可能涉及到的解題內(nèi)容為（ABCDE）A求其松弛問題B在其松弛問題中增加一種約束方程C應用單形或圖解法D割去部分非整數(shù)解E多次切割三、名詞1、純整數(shù)規(guī)劃：如果規(guī)定全部的決策變量都取整數(shù),這樣的問題成為純整數(shù)規(guī)劃問題。2、0—1規(guī)劃問題：在線性規(guī)劃問題中，如果規(guī)定全部的決策變量只能取0或1，這樣的問題稱為0-1規(guī)劃。3、混合整數(shù)規(guī)劃:在線性規(guī)劃問題中，如果規(guī)定部分決策變量取整數(shù),則稱該問題為混合整數(shù)規(guī)劃。四、用分枝定界法求解下列整數(shù)規(guī)劃問題:(提示:可采用圖解法）maxZ=40x1+90x2五、用割平面法求解六、下列整數(shù)規(guī)劃問題闡明能否用先求解對應的線性規(guī)劃問題然后四舍五入的方法來求得該整數(shù)規(guī)劃的一種可行解.答:不考慮整數(shù)約束，求解對應線性規(guī)劃得最優(yōu)解為x1=10/3，x2=x3=0，用四舍五人法時,令x1=3,x2=x3=0，其中第2個約束無法滿足，故不可行。七、若某鉆井隊要從下列10個可供選擇的井位中擬定5個鉆井探油。使總的鉆探費用為最小.若10個井位的代號為S1,S2．…，S10對應的鉆探費用為C1,C2，…C10，并且井位選擇要滿足下列限制條件:(1)在s1，s2，S4中至多只能選擇兩個;(2)在S5，s6中最少選擇一種；（3）在s3，s6,S7，S8中最少選擇兩個；試建立這個問題的整數(shù)規(guī)劃模型八、有四項工作要甲、乙、丙、丁四個人去完畢．每項工作只允許一人去完畢。每個人只完畢其中一項工作，已知每個人完畢各項工作的時間以下表。問應指派每個人完畢哪項工作，使總的消耗時間最少?工作人IⅡⅢⅣ甲乙丙丁151961918237212l22162324181917第八章圖與網(wǎng)絡分析一、填空題1．圖的最基本要素是點、點與點之間構成的邊2．在圖論中,普通用點表達,用邊或有向邊表達研究對象，以及研究對象之間含有特定關系.3．在圖論中，普通用點表達研究對象，用邊或有向邊表達研究對象之間含有某種特定的關系。4．在圖論中，圖是反映研究對象_之間_特定關系的一種工具。5．任一樹中的邊數(shù)必然是它的點數(shù)減1.6．最小樹問題就是在網(wǎng)絡圖中,找出若干條邊，連接全部結點，并且連接的總長度最小。7．最小樹的算法核心是把近來的未接_結點連接到那些已接結點上去。8．求最短路問題的計算辦法是從0≤fij≤cij開始逐步推算的，在推算過程中需要不停標記平衡和最短路線。二、單選題1、有關圖論中圖的概念，下列敘述（B）對的。A圖中的有向邊表達研究對象,結點表達銜接關系。B圖中的點表達研究對象，邊表達點與點之間的關系。C圖中任意兩點之間必有邊。D圖的邊數(shù)必然等于點數(shù)減1。2．有關樹的概念，下列敘述（B）對的。A樹中的點數(shù)等于邊數(shù)減1B連通無圈的圖必然是樹C含n個點的樹是唯一的D任一樹中，去掉一條邊仍為樹.3．一種連通圖中的最小樹（B），其權(A)。A是唯一擬定的B可能不唯一C可能不存在D一定有多個.4．有關最大流量問題，下列敘述(D）對的.A一種容量網(wǎng)絡的最大流是唯一擬定的B達成最大流的方案是唯一的C當用標號法求最大流時，可能得到不同的最大流方案D當最大流方案不唯一時,得到的最大流量亦可能不相似。5．圖論中的圖，下列敘述(C)不對的。A．圖論中點表達研究對象，邊或有向邊表達研究對象之間的特定關系。B．圖論中的圖,用點與點的互相位置,邊的長短曲直來表達研究對象的互有關系.C．圖論中的邊表達研究對象，點表達研究對象之間的特定關系。D．圖論中的圖，能夠變化點與點的互相位置。只要不變化點與點的連接關系.6．有關最小樹,下列敘述(B）對的。A．最小樹是一種網(wǎng)絡中連通全部點而邊數(shù)最少的圖B．最小樹是一種網(wǎng)絡中連通全部的點，而權數(shù)最少的圖C．一種網(wǎng)絡中的最大權邊必不包含在其最小樹內(nèi)D．一種網(wǎng)絡的最小樹普通是不唯一的.7．有關可行流，下列敘述(A)不對的。A．可行流的流量不不大于零而不大于容量限制條件B．在網(wǎng)絡的任一中間點，可行流滿足流人量=流出量。C．各條有向邊上的流量均為零的流是一種可行流D．可行流的流量不大于容量限制條件而不不大于或等于零.三、多選題1．有關圖論中圖的概念，下列敘述（123）對的。(1）圖中的邊能夠是有向邊，也能夠是無向邊(2)圖中的各條邊上能夠標注權。(3)結點數(shù)等于邊數(shù)的連通圖必含圈（4）結點數(shù)等于邊數(shù)的圖必連通。2．有關樹的概念，下列敘述（123）對的。1）樹中的邊數(shù)等于點數(shù)減1(2)樹中再添一條邊后必含圈。(3）樹中刪去一條邊后必不連通(4）樹中兩點之間的通路可能不唯一.3．從連通圖中生成樹，下列敘述(134）對的。（1)任一連通圖必有支撐樹(2)任一連通圖生成的支撐樹必唯一（3)在支撐樹中