鐵路管理運籌學(xué)

管理運籌學(xué)復(fù)習(xí)題（吉林）第一章一、以下知識點可出單選題和填空題單選題知識點：運籌學(xué)研究和解決問題的優(yōu)勢是應(yīng)用各學(xué)科交叉的方法，其具有的典型特性具有綜合性。數(shù)學(xué)模型中，“s?t”表示，即具體問題之資源和變量取值范圍。3?運籌學(xué)作為一門現(xiàn)代的新興科學(xué)，起源于第二次世界大戰(zhàn)的軍事適動，具體為領(lǐng)空防御。4?用運籌學(xué)解決問題時，要對問題進(jìn)行分析和定義，建立模型，將具體問題抽象化。5?運籌學(xué)中所使用的模型是數(shù)學(xué)模型，即使用數(shù)字、符號和變量等將問題表述出來。6?運籌學(xué)的研究對象是管理理，它涉及軍事、經(jīng)濟、企業(yè)和團體等各領(lǐng)域。7?運籌學(xué)運用數(shù)學(xué)方法分析與解決問題，以達(dá)到系統(tǒng)的最優(yōu)目標(biāo)。可以說這個過程是一個科學(xué)決策過程，因為它是根據(jù)科學(xué)方法計算而得到的。8?運籌學(xué)的主要研究對象是各種有組織系統(tǒng)的管理問題及經(jīng)營活動，包括企業(yè)、團體組織等。填空題知識點：用運籌學(xué)分析與解決問題的過程是一個科學(xué)決策過程，其核心過程為建立模型并求解。運籌學(xué)的主要目的在于求得一個合理運用人力、物力和財力的最佳方案，為決策提供依據(jù)。運籌學(xué)研究功能之間關(guān)系是應(yīng)用系統(tǒng)觀點，應(yīng)用多學(xué)科的知識和多領(lǐng)域人員參加。運籌學(xué)解決問題的核心是建立數(shù)學(xué)模型并對模型求解，模型不同，解題方法不同。運籌學(xué)是近代形成的一門應(yīng)用科學(xué)，其應(yīng)用領(lǐng)域廣泛，并使用計算機求解。運籌學(xué)的主要分支包括圖論、線性規(guī)劃、整數(shù)規(guī)劃和目標(biāo)規(guī)劃等，對它們的研究比較成熟。二、下列知識點可出簡答題簡答：運籌學(xué)的數(shù)學(xué)模型有哪些優(yōu)點?答：（1）通過模型可以為所要考慮的問題提供一個參考輪廓，指出不能直接看出的結(jié)果。（2）節(jié)省時間和費用。（3）模型使人們可以根據(jù)過去和現(xiàn)在的信息進(jìn)行預(yù)測，可用于教育訓(xùn)練，訓(xùn)練人們看到他們決策的結(jié)果，而不必作出實際的決策。（4）數(shù)學(xué)模型有能力揭示一個問題的抽象概念，從而能更簡明地揭示出問題的本質(zhì)。（5）數(shù)學(xué)模型便于利用計算機處理一個模型的主要變量和因素，并易于了解一個變量對其他變量的影響。這些都是使得運籌學(xué)能夠快速發(fā)展的有利條件。簡答：運籌學(xué)的系統(tǒng)特征是什么?答：運籌學(xué)的系統(tǒng)特征可以概括為以下四點：（1）用系統(tǒng)的觀點研究功能關(guān)系（2）應(yīng)用各學(xué)科交叉的方法（3）采用計劃方法（4）為進(jìn)一步研究揭露新問題。新發(fā)現(xiàn)的問題，可能要求用修正過去的模型、輸入新的數(shù)據(jù)以及調(diào)整以前類似項目的解，獲得解決。第二章一、以下知識點可出單選題和填空題單選題知識點：如果一個線性規(guī)劃問題有n個變量，m個約束方程m<n，系數(shù)矩陣的個數(shù)為m，則基可行解的個數(shù)為Cm,即可找到相應(yīng)數(shù)量的滿秩子矩陣。2?在用圖解法求解線性規(guī)劃問題時，如果取得極值的等值線與可行域的一段邊界重合，則該問題有無窮多最優(yōu)解，即該線上的人一點坐標(biāo)的目標(biāo)函數(shù)值都是相等的。3?如果某個變量X為自由變量，則應(yīng)引進(jìn)兩個非負(fù)變量X，,X”，同時令X=X，—X”，用后者替代前者，將所有的自由變量變成非負(fù)值。 jj j ―j4?圖解法適用于求解有關(guān)線性規(guī)劃問題，但該問題中只能含有兩個變量，因為圖解法是在二維直角坐標(biāo)系中體現(xiàn)的。線性規(guī)劃模型三個要素中不包括基，基是根據(jù)模型求解出來的。6?下列圖形中陰影部分構(gòu)成的集合為凸集的是A ，在這個圖形中的任意兩點上的連線均在該凸集內(nèi)。線性規(guī)劃問題的基可行解與可行域頂點的關(guān)系體現(xiàn)為頂點多于基可行解,我們沿著頂點去尋找而不用一一—求解。下列關(guān)于基本解，基可行解，可行解的說法錯誤的是可行解與基本解之間無交集，三者是遞進(jìn)的。9?在線性規(guī)劃問題中，基可行解的非零分量所對應(yīng)的列向量線性無關(guān)，即兩者沒有關(guān)系。填空題知識點線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，所有變量必須大于等于零，其物理意義與現(xiàn)實是一致的。線性規(guī)劃問題是求極值問題，這是針對亙標(biāo)函數(shù)，可以是求極大或求極小。線性規(guī)劃問題有可行解，則必有基可行解,因為可行解是在基可行解基礎(chǔ)上得來的。從趨勢上看，運籌學(xué)的進(jìn)一步發(fā)展依賴于一些外部條件及手段，其中最主要的是辻算機，使得其效率和方便性大大增加。如果線性規(guī)劃問題存在目標(biāo)函數(shù)為有限值的最優(yōu)解，求解時只需在某集合中進(jìn)行搜索即可得到最優(yōu)解，這個集合是可行域，在二維直角坐標(biāo)系中常用陰影區(qū)表示。15?若目標(biāo)函數(shù)為求max，一個基可行解比另一個基可行解更好的標(biāo)志是使Z更大，這是對于目標(biāo)函數(shù)為求極大的標(biāo)準(zhǔn)型而言的。運籌學(xué)中，“LP”表示線性規(guī)劃，當(dāng)變量為兩個時，目標(biāo)函數(shù)和各約束都可表示為直線。在線性規(guī)劃的一般表達(dá)式中，變量x可能為大于等于0、小于等于0、等于0，即取值無約束。求解線性規(guī)劃問題解的結(jié)果可能有曜一最優(yōu)解、無可行解、無窮多最優(yōu)解、無界解、無最優(yōu),但對于某一個問題來說，結(jié)果只能是其中一種。19?在線性規(guī)劃問題中a表示i=2、j=3，即在約束條件系數(shù)行列式中的第2行，第3列的位置。23 若線性規(guī)劃問題的可行域是無界的，則該問題可能無最優(yōu)解、有最優(yōu)解、有唯一最優(yōu)解、有無窮多個最優(yōu)解，具體是哪一種，要看其目標(biāo)函數(shù)和約束條件的組合情況。在線性規(guī)劃問題的標(biāo)準(zhǔn)形式中，可能存在的變量有可控變量、松馳變量、剩余變量，這些變量可能是原問題所含有的，有的是在變成變成標(biāo)準(zhǔn)形時增加的，數(shù)量上也要看具體問題而定。22?若線性規(guī)劃問題有可行解，則其可行域可能是一凸多邊形、可能有界也可能無界、也可能有無數(shù)可行解，即能找到陰影區(qū)，對該問題有可行的方案。二、下列知識點可出名詞解釋和簡答題概念：可行解：在線性規(guī)劃問題中，凡滿足所有約束條件的解稱為線性規(guī)劃問題可行解。概念：可行域：線性規(guī)劃問題的可行解集合。3?概念：基本解：在線性約束方程組中，對于選定的齢所有的非基變量等于零，得到的解，稱為線性規(guī)劃問題的一個基本解。概念：非基變量：在線性規(guī)劃問題中，與非基向量相對應(yīng)變量。概念：圖解法：對于只有兩個變量的線性規(guī)劃問題，可以用在平面上作圖的方法來求解，這種方法稱為圖解法概念：線性規(guī)劃問題：就是求一個線性目標(biāo)函數(shù)在一組線性約束條件下的極值問題。簡答：根據(jù)已知條件建立線性規(guī)劃數(shù)學(xué)模型某工廠生產(chǎn)A、B、C三種產(chǎn)品，每種產(chǎn)品的原材料消耗量、機械臺時消耗量以及這些資源的限量，單位產(chǎn)品的利潤如下表所示：

單位產(chǎn)品消耗資源ABC資源限量原材料1.01.54.02000機械臺時2.01.21.01000單位利潤101412根據(jù)客戶訂貨，三種產(chǎn)品的最低月需要量分別為200，250和100件，最大月銷售量分別為250280和120件。月銷售分別為250，280和120件，問如何安排生產(chǎn)計劃，使總利潤最大？解：設(shè)XXX分別設(shè)代表三種產(chǎn)品的產(chǎn)量，則線性規(guī)劃模型為1,2,3maxZ=10X+14X+12XTOC\o"1-5"\h\z1 2 3s?tX+1.5X+4X<20001 2 32X+1?2X+X<10001 2 3< 200<X<25011IX,X,X201IX,X,X208.簡答：把下列線性規(guī)劃問題化成標(biāo)準(zhǔn)形式:1?minZ=5xi-2x2X!+yX2^4s.t.v-X!+x2<-22X2<3,X2>0答：第一步，將目標(biāo)函數(shù)變?yōu)榍髽O大；第二步，將約束不等式變?yōu)榈仁?；第三步，將b值變?yōu)榉秦?fù)。結(jié)果如下：maxZ'=－5x+2x12孔+ mMM.小H]一竝一嗎=戈2jci+Hirm.齊m0(>匸1,2?3?4?5)簡答：把下列線性規(guī)劃問題化成標(biāo)準(zhǔn)形式：minZ=2x-x+2x1 2 3_X]+X2+X3=4s.t.5-Xi+x2-x3C6x1<0,x2>0,x3無約束答：第一步，將目標(biāo)函數(shù)變?yōu)榍髽O大；第二步，將約束不等式變?yōu)榈仁?；第三步，將b值變?yōu)榉秦?fù)第四步，將變量無約束變?yōu)榉秦?fù)值；第五步，將變量由小于等于情形變?yōu)榇笥诘扔谇樾巍＝Y(jié)果如下:答：(1)求一組決策變量x或x的值(i=1,2,???mj=1,2???n)使目標(biāo)函數(shù)達(dá)到極大或極小;10.簡答：線性規(guī)劃數(shù)學(xué)模型具備哪幾個要素？10.簡答：線性規(guī)劃數(shù)學(xué)模型具備哪幾個要素？表示約束條件的數(shù)學(xué)式‘都是線性等式或不等式；表示問題最優(yōu)化指標(biāo)的目標(biāo)函數(shù)都是決策變量的線性函數(shù)。這三個要素即組成缺一不可，共同構(gòu)成一個完整的線性規(guī)劃問題。簡答：根據(jù)所給條件建立線性規(guī)劃模型。某建筑工地有一批長度為10米的相同型號的鋼筋,今要截成長度為3米的鋼筋90根,長度為4米的鋼筋60根,問怎樣下料,才能使所使用的原材料最省?答：將10米長的鋼筋截為3米和4米長,共有以下幾種下料方式：長度?類--一IIIIII丿3米0124米210設(shè)X,X,X分別表示采用I、II、III種，則線性規(guī)劃模型可寫成：123minZ=X+X+X廣1 2 3s?t2X+3X±902 3丿2X+X±6012X,X,X±0目標(biāo)函數(shù)Z2表示所使用的鋼筋數(shù)，其總量為三種下料方式所得鋼筋數(shù)，我們希望它用料最少，所以為求極小;截成3米和4的鋼筋數(shù)最大為90和60根，滿足問題要求。第三章一、 以下知識點可出單選題和填空題單選題知識點：1?單純形法當(dāng)中，入基變量的確定應(yīng)選擇檢驗數(shù)正值最大,這樣會使目標(biāo)增長最快，加快尋找最優(yōu)解的速度。2?線性規(guī)劃的代數(shù)解法主要利用了代數(shù)消元法的原理來實現(xiàn)一種轉(zhuǎn)換尋找最優(yōu)解，這種轉(zhuǎn)換是基可行解，隨著解的不斷改變，目標(biāo)函數(shù)值也在不斷變優(yōu)。出基變量的含義是由某值下降為0,其對應(yīng)的變量變?yōu)榉腔兞俊??在單純形迭代過程中，若此問題是無界，則有某個5k>0對應(yīng)的非基變量x的系數(shù)列向量P小于k k等于零，由此，無法使用最小Q比值原則獲得出基變量，計算無法進(jìn)行。5?下列說法錯誤的是單純形迭代中，進(jìn)基變量可以任選，它必須依照檢驗數(shù)大小、正負(fù)來判斷和確定。6?入基變量的含義是由0值上升為某值，即該變量使得目標(biāo)函數(shù)發(fā)生變化。7?用大M法求目標(biāo)函數(shù)為極大值的線性規(guī)劃問題時，引入的人工變量在目標(biāo)函數(shù)中的系數(shù)應(yīng)為-M，它起到阻礙達(dá)到極大的目的，只有當(dāng)該變量取值為0時，阻礙作用消失。8?在單純形迭代中，出基變量丕會在緊接著的下一次迭代中立即入基，如果是這樣，那么很可能計算失誤。求目標(biāo)函數(shù)為極大的線性規(guī)劃問題時，若全部非基變量的檢驗數(shù)WO,且基變量中有人工變量時該問題有無可行解，即人工變量不出基，置換不出來，所以無解。填空題知識點當(dāng)已化為標(biāo)準(zhǔn)形的線性規(guī)劃問題的系數(shù)矩陣中仍不存在可行基時，要構(gòu)造可行基一般可以采取的方法是增加人工變量，借助人工變量找到可行基，方便求解。在線性規(guī)劃典式中，所有基變量的目標(biāo)系數(shù)為0。在單純形表的終表中，若非基變量的檢驗數(shù)有0,那么最優(yōu)解丕存在。所以這是一個判斷標(biāo)準(zhǔn)。若在單純形法迭代中，有兩個Q值相等，當(dāng)分別取這兩個不同的變量為入基變量時，獲得的結(jié)果將是擔(dān)回的。這相當(dāng)于從不同方向?qū)ふ易顑?yōu)解，最終目標(biāo)是相同的，殊途同歸。當(dāng)線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時，若要構(gòu)造可行基一般可以采取的方法是增加人工變量，但最終人工變量要出基，該問題才有最優(yōu)解。16?設(shè)X（i）=X⑵是用單純形法求得的某一線性規(guī)劃問題的最優(yōu)解，則此問題存在以下情形：有無窮多最優(yōu)解、此問題的全部最優(yōu)解可表示為入X（1）+（1一入）X（2），其中0W入W1、X（1）,X（2）是兩個基可行解、X（1）,X⑵的基變量個數(shù)相同。某線性規(guī)劃問題，含有n個變量，m個約束方程，（m<n）,系數(shù)矩陣的秩為m,則存在該問題的典式不超過Cm個、基可行解中的基變量的個數(shù)為m個、該問題一定存在可行解、該問題的基至多有Cm=1個，這對于所有線性規(guī)劃問題都是適用的。N二、 下列知識點可出簡答題簡答：單純形法解題的基本思路。答：從可行域的一個基本可行解開始，轉(zhuǎn)移到另一個基本可行解，并且使目標(biāo)函數(shù)值逐步得到改善，直到最后球場最優(yōu)解或判定原問題無解。最后從終表中直接寫出解和目標(biāo)函數(shù)值或得出解處于怎樣的情形。三、 下列知識點可出計算題1.用單純形法求解下列線性規(guī)劃問題：maxZ=3x+5x12{X]W152^W123x+2xW1812x，x三012解：化為標(biāo)準(zhǔn)形式maxZ=3x＋5x＋x＋0x＋0xTOC\o"1-5"\h\z1 2 3 4 5s?t廣x+x=151 32x+x=12丿 2 5[3x+2x+x=181 2 5[x±0（j=1,……，5）寫出初表及迭代過程如下：c35000C j xbxxxxxBB123450x1501一000x120(2)0100X18320015c—z350000J Jx15101000x60101/200xs6(3)00—11c—z300—5/200 j j x130011/3—1/353x60101/203x2100—1/31/2c—z000—3/2—1所有檢驗數(shù)均為小于等于零，所以計算結(jié)束。最優(yōu)解X*二（2，6，13，0，0）TZ*=36用大M法求解下列線性規(guī)劃問題maxZ云出卄2勒t3和▼K|+2x^+ =15+xz+5xj=20s,tXt+2xj+加+%M10=1,…,4)解：化為標(biāo)準(zhǔn)形式maxZ=x+2x+3x－x－mx－mxTOC\o"1-5"\h\z1 2345 6s?t廣x+2x+3x+x=1512 3 52x+x+5x+x=20丿 12 3 61x+2x+x+x4=101 2 3[Xj±0 (j=1,……,6)c123-1-M-MCJxbxxxxxxBB123456-Mx15123010-Mx20215001-1x101(2)1100c—z4M+15M+29M+3000—MJ Jx5002-110—M5x15(3/2)04/2-1/2012x251/211/21/200c—zj j3M013M+2-3M+200222—Mx500(2)-1101x10103-1/302/321x000112/30-1/3c—z002M+2-M-20-M3 j jx5/2001-1/21/201x5/21007/6-3/22/32x5/201011/2-1/32c—zjj000-7/2-M-1-Mx*=(-,5,-, 0,0,0)t,z*=15222用圖解法求解下列線性規(guī)劃問題。maxZ=10x+5x廣 1 23x+4xW912s.t5x+2xW812x,x±01 2解：建立直角坐標(biāo)系；取值并將約束條件和目標(biāo)函數(shù)在其中表示出來；確定可行域；確定最優(yōu)解點。3最優(yōu)點為A(1,23最優(yōu)解為X*二(1, )T2用單純形法求解線性規(guī)劃問題minZ=－2x+x+x123s?t廠3x+x+xW60TOC\o"1-5"\h\z1 2 3x—x+2xW10丿 1 2 31x+x—xW201 2 3.x±0(j=1,2,3)解：化為標(biāo)準(zhǔn)形式maxZ'=2x—x＋xs?tw123廣3x+x+x+x=601 2 3 4x—x+2x+x=101 2 3 5x+x—x+x=201 2 3 6〔x±0(j=1, ,6)cj j 2—11000C xB Bbx1xx2x3x4x50x3111060400x(1)—12011000x11—1002061c一jzj20—11000x04—51—330400x1—120110100x0(2)—30—1101c一jzj001—30—20x0011—1104—22 x15101/201/21一1x1/2501—3/20—1/21/2c—zj j0—1/20—5/20—1/2最優(yōu)解X*=(15,5,0,10,0,0)TZ*=—251.下表為用單純形法計算時某一步的表格。已知該線性規(guī)劃的目標(biāo)函數(shù)為maxZ=5x+3x，約束形式12為“W”，X,X為松馳變量，表中解代入目標(biāo)函數(shù)后得Z=10X1XQXoX—10b-1fgX32CO11/5X 1—ade01（1） 求表中a?g的值（2）表中給出的解是否為最優(yōu)解?解：（1）a=2b=0c=0d=1e=4/5f=0g=－5（2） 表中給出的解為最優(yōu)解47．用單純型表求解下列線性規(guī)劃問題maxZ=2x+3xTOC\o"1-5"\h\z廣 1 23x+2x+xW101 2 3s.t6x+x+4xW121 2 3x,x,x20< 1’ 2 ' 3第四章一、以下知識點可出單選題和填空題單選題知識點：1?若某種資源的影子價格等于k。在其他條件不變的情況下（假設(shè)原問題的最佳基不變），當(dāng)該種資源增加3個單位時，相應(yīng)的目標(biāo)函數(shù)值將增加6K，二者相聯(lián)系。2?設(shè)線性規(guī)劃的原問題為maxZ=CX，AxWb,X20，則其對偶問題為max二YbYAWcY20,即可以通過具體轉(zhuǎn)換表進(jìn)行。3?線性規(guī)劃問題的最優(yōu)基為B,基變量的目標(biāo)系數(shù)為C，則其對偶問題的最優(yōu)解Y*=.CB-1,這是B B普遍適用的。若X*和Y*分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則下面有關(guān)式子中正確的是CX*二Y*b二者存在這樣的必然聯(lián)系。5?設(shè)X、Y分別是標(biāo)準(zhǔn)形式的原問題與對偶問題的可行解，則在 門「I—兩個式子中C是存在的，并且絕對存在。6.在對偶單純形法迭代中，若某b<0，且所有的a20（j=1，2，???n），則原問題無解，這是一條重要的判斷原則。 i ij7?在下列線性規(guī)劃問題B中，采用求其對偶問題的方法，單純形迭代的步驟一般會增加，因為其對偶問題的變量要增加到3個。B.maxZ_X|+X2:亠旳十毛.十Z2s,t<-2xl+x2I*】”陶,x3^0若X*和Y*分別是線性規(guī)劃的原問題和對偶問題的最優(yōu)解，則CX*與Y*B的關(guān)聯(lián)關(guān)系為CX*=Y*B線性規(guī)劃的原問題的約束條件系數(shù)矩陣為A,則其對偶問題的約束條件系數(shù)矩陣為At如果z。是某標(biāo)準(zhǔn)型線性規(guī)劃問題的最優(yōu)目標(biāo)函數(shù)值，則其對偶問題的最優(yōu)目標(biāo)函數(shù)值w*有W*=Z*

填空題知識點對偶單純形法的迭代起始點是正則解，這和單純形法的情形是不同的。若原問題可行，但目標(biāo)函數(shù)無界，則對偶問題丕可行，可用該定理直接判斷。影子價格實際上是與原問題各約束條件相聯(lián)系的某個變量的數(shù)量表現(xiàn)。這個變量是基變量，它反映了與市場相關(guān)的某些經(jīng)濟信息和指導(dǎo)作用。如果原問題的某個變量無約束，則對偶問題中對應(yīng)的約束條件應(yīng)為等式，二者是絕對對應(yīng)的，這在將某一問題變?yōu)閷ε紗栴}時用處很大。對偶問題的對偶問題是原鹽，即原問題可以看成是對偶問題。根據(jù)對偶理論，在求解線性規(guī)劃的原問題時，可以得到相關(guān)信息包括對偶問題的解、影子價格、資源的購銷決策17?如線性規(guī)劃的原問題為求極大值型，則下列關(guān)于原問題與對偶問題的關(guān)系中正確的有：原鹽的約束條件為“二”對應(yīng)的對偶變量為自由變量、原問題的變量“三0”對應(yīng)的對偶約束“三”原問題的變量“WO”對應(yīng)的對偶約束“W”原問題的變量無符號限制，對應(yīng)的對偶約束“=”這種關(guān)系是一種無差別對應(yīng)。當(dāng)原問題為極小時，對應(yīng)關(guān)系有所改變。下列有關(guān)對偶單純形法的說法正確的有：在迭代過程中應(yīng)先選出基變量，再選進(jìn)基變量；當(dāng)?shù)械玫降慕鉂M足原始可行性條件時，即得到最優(yōu)解；初始單純形表中填列的是一個正則解；初始解不需要滿足可行性，這些情形與單純形法是不同的。二、下列知識點可出簡答題簡答：一對對偶問題可能出現(xiàn)的情形。答：①原問題和對偶問題都有最優(yōu)解，且二者相等；②一個問題具有無界解，則另一個問題具有無可行解；③原問題和對偶問題都無可行解。并且原問題也可作為對偶問題，對偶問題也可作為原問題來求解。簡答：寫出下列線性規(guī)劃問題的對偶問題minZ=2x+2x+4x3x[—x2+7x3=3.Xi,x2,x3^0解：根據(jù)二者對應(yīng)轉(zhuǎn)換表所示的對應(yīng)關(guān)系，設(shè)對偶問題的目標(biāo)函數(shù)為W，有:maxW/=2y+3y+5yt2y+3y+y1233y—y+4yW2123\—5y+7y+6yW4123maxW/=2y+3y+5yt2y+3y+y1233y—y+4yW2123\—5y+7y+6yW4123W4yWOy±0，yWO，yWO三、下列知識點可出計算題已知線性規(guī)劃問題maxZ=4xi+7x2+2x3x,+2x2+X3WIOt<2xi+3x2+3x3=10,Xi,x2,x3>0應(yīng)用對偶理論證明該問題最優(yōu)解的目標(biāo)函數(shù)值不大于25證明鬧從對怛閩JU為:W= +LO-^.','*、+2^z亠片<3亠+\>:M2*1rgM°1&砂察町躋時仙問則的一UJ行解 T=(]；2Pfll理的El標(biāo)苗救眉「祁7二S歯劃炳理覽可倚-W■況市■”2、用對偶單純形法求解下列線性規(guī)劃問題：minZ=3xj+2x2+x3(X[+X?+X3W6Jxt-x3y4X2一X3>4、Xi,x2,x3^0解：化為標(biāo)準(zhǔn)形式maxZ'=－3x－2x－x＋0x＋0x＋0xTOC\o"1-5"\h\z1 2 3 456s?t廣x+x+x+x=6123 4—x+x+x=—4丿 1 3 5” —x+x+x=—4一Xj±0(j=1, , 6)入表、計算得:c3—2—1000CBJxBbx1x2x3x4x5x60x611110「00x_4(—1)010100x40—11001cz—3—2—10000 J J—x2012110_3x410—10—100xs40(—1)1000c_z0—2—40—300 J J—x_2003111_3x410—10—102x401—100—12c_z j j 100—70—3—2x為—2，無法迭代，此題無解。4用對偶單純形法求解下列線性規(guī)劃問題minZ=X+X12.-2X+X三4s.t ?-X+7X三7--X+x$三012解：maxZ，=-X]_X2+OX3+OX4「-2X]_1X2+X3=-4S.J-X1-7X2+X4=-7IX],x2,X3,x4±o4?某工廠在計劃期內(nèi)要安排生產(chǎn)I、II兩種產(chǎn)品。已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺時及A、B兩種原料的消耗如表所示：III設(shè)備128臺時原材料A4016kg原材料B0412kg該工廠每生產(chǎn)一件產(chǎn)品I可獲利2百元，每生產(chǎn)一件產(chǎn)品II可獲利3百元。(1)單純形迭代的初始表及最終表分別如下表I、II所示：B ?023O00X8121O0X16400104X12040011400-3/2-1/80X41001/40X400-21/215Xc2011/2-1/80說明使工廠獲利最多的產(chǎn)品混合生產(chǎn)方案。(2)如該廠從別處抽出4臺時的設(shè)備用于生產(chǎn)I、II,求這時該廠生產(chǎn)產(chǎn)品I、II的最優(yōu)方案。解：(1)使工廠獲利最多的產(chǎn)品混合生產(chǎn)方案：生產(chǎn)I產(chǎn)品4件,生產(chǎn)II產(chǎn)品2件,設(shè)備臺時與原材料A全部用完，原材料B剩余4kg，此時，獲利14百元。(2)X=(4,3,2,0,o)Tz=17第五章一、以下知識點可出單選題和填空題單選題知識點：1?在線性規(guī)劃的靈敏度分析中，我們主要用到的性質(zhì)是正則性和可行性,靈敏性和最優(yōu)性則是次要的。2?在某生產(chǎn)規(guī)劃問題的線性規(guī)劃模型中，變量x的目標(biāo)系數(shù)C代表該變量所對應(yīng)的產(chǎn)品的利潤，則當(dāng)某一非基變量的目標(biāo)系數(shù)處于某種狀態(tài)時，其有可能進(jìn)入基底。這種狀態(tài)是增大,而不是縮小或不變。3?在某線性規(guī)劃問題中，已知某資源的影子價格為Y,相應(yīng)的約束常數(shù)B,在靈敏度容許變動范圍內(nèi)發(fā)生AB的變化，設(shè)原最優(yōu)目標(biāo)函數(shù)值為Z*,1則新的最優(yōu)解對應(yīng)的最優(yōu)目標(biāo)函數(shù)值是Z*+y.△B，Z*-y△B則是錯誤的。填空題知識點靈敏度分析研究的是線性規(guī)劃模型中兩個數(shù)據(jù)之間的變化和影響，這兩個數(shù)據(jù)是原始數(shù)據(jù)和最優(yōu)解，當(dāng)原始數(shù)據(jù)發(fā)生改變時，最優(yōu)解將跟著發(fā)生變化。5?在靈敏度分析中，某個非基變量的目標(biāo)系數(shù)的改變，將引起某變量的檢驗數(shù)的變化，這個變量是該非基變量自身，二者存在很大影響關(guān)系。6.線性規(guī)劃靈敏度分析應(yīng)在某個基礎(chǔ)上，分析系數(shù)變化對最優(yōu)解產(chǎn)生的影響。這個基礎(chǔ)是最優(yōu)單純

形表。系數(shù)則是指約束條件系數(shù)、目標(biāo)函數(shù)系數(shù)等。7?靈敏度分析研究的是線性規(guī)劃模型中兩個數(shù)據(jù)之間的變化和影響，這兩個數(shù)據(jù)是最優(yōu)解和原始數(shù)據(jù)，系數(shù)包括a、b、c等8?若某約束常數(shù)b的變化超過其容許變動范圍，為求得新的最優(yōu)解，需在原最優(yōu)單純形表的基礎(chǔ)上運用某種方法求解，這種方對法是對偶單純形法，這是最簡便的方法。能引起線性規(guī)劃問題最優(yōu)解可行性變化的是增加新的約束條件,如果約束條件的增加使問題可行域范圍縮小，那么原有最優(yōu)解可能變成非可行解。在線性規(guī)劃問題的各種靈敏度分析中，各條件的變化中不能引起最優(yōu)解的正則性變化的是約束常數(shù)，即其影響性很小。11?如果線性規(guī)劃的原問題增加一個約束條件，相當(dāng)于其對偶問題增加一個變量，二者一一對應(yīng)。在線性規(guī)劃的各項敏感性分析中，一定會引起最優(yōu)目標(biāo)函數(shù)值發(fā)生變化的是約束常數(shù)項b變化，因為它確定了整個資源的總量。 i—線性規(guī)劃問題的各項系數(shù)發(fā)生變化，下列不能引起最優(yōu)解的可行性變化的有：非基變量的目標(biāo)系數(shù)變化；基變量的目標(biāo)系數(shù)變化；增加新的變量。而當(dāng)目標(biāo)函數(shù)改變時則會相反。若線性規(guī)劃問題最優(yōu)基中某個基變量的目標(biāo)系數(shù)發(fā)生變化，則下列結(jié)論中不成立的有：該基變量的檢驗數(shù)發(fā)生變化；其他基變量的檢驗數(shù)發(fā)生變化；所有變量的檢驗數(shù)都發(fā)生變化；目標(biāo)最優(yōu)解發(fā)生變化。但這種變化卻會使所有非基變量的檢驗數(shù)發(fā)生變化。在靈敏度分析中，我們可以直接從最優(yōu)單純形表中獲得的有效信息有：最優(yōu)基 B的逆B-1 ；最優(yōu)解與最優(yōu)目標(biāo)函數(shù)值；各變量的檢驗數(shù)，對偶問題的解卻不會得到，需要通過求解。二、 下列知識點可出名詞解釋和簡答題概念：靈敏度分析：研究線性規(guī)劃模型的原始數(shù)據(jù)變化對最優(yōu)解產(chǎn)生的影響叫做線性規(guī)劃的靈敏度分析。簡答：線性規(guī)劃問題靈敏度分析的意義。答：（1）預(yù)先確定保持現(xiàn)有生產(chǎn)規(guī)劃條件下，單位產(chǎn)品利潤的可變范圍；（2）當(dāng)資源限制量發(fā)生變化時，確定新的生產(chǎn)方案；（3）確定某種新產(chǎn)品的投產(chǎn)在經(jīng)濟上是否有利；（4）考察建模時忽略的約束對問題的影響程度；（5）當(dāng)產(chǎn)品的設(shè)計工藝改變時，原最優(yōu)方案是否需要調(diào)整。因此，靈敏度分析對于企業(yè)生產(chǎn)等方面的管理等進(jìn)行動態(tài)分析和決策是非常及時和適用的。三、 下列知識點可出計算題1.給出線性規(guī)劃問題1.給出線性規(guī)劃問題c在什么范圍內(nèi)變動時最優(yōu)解不變；c在什么范圍內(nèi)變動時最優(yōu)解不變；12（3）增添新的約束X+2x+xW41 2 3（2）X*=（2，0，1，0，0，0）TZ*=10Z*=72WCW82T用單純形表求解得單純形表如下，試分析下列各種條件變化下最優(yōu)解（基）的變化xxxxx J 2 ° " ￡ -800-3-5-1x110-14-1lxQ2012-11（1） 分別確定目標(biāo)函數(shù)中變量X和X的系數(shù)C，12（2） 目標(biāo)函數(shù)中變量X的系數(shù)變?yōu)?；3解：（1）3/4WCW31（3） X*=（2，1，0，0，1，0）

已知線性規(guī)劃問題maxZ=2xx+4x2+X3+氐X]+3x2+X4M82xl+x2M6s?#X2+X3+ ￡6X]+X2+X3￡9^>0(j=l,2,3,4)(1)寫出其對偶問題(2)已知原問題最優(yōu)解為X*=(2,2,4,0)T，試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：(1)對偶問題minW=8y+6y+6y+9y1234s?t廣 y+2y+y三2TOC\o"1-5"\h\z1 2 43y+y+y+y±412 3 4\ y+y±1\o"CurrentDocument"3 4y+y±1，4)1 3，4)Ly±0(j=1,?…(2)把x*=(2,2,4,0)T代入原問題，可知第四個約束條件為嚴(yán)格不等式，則y*=04可知s?t「- y+2y=2123y+y+y=41 2 4「 y=1y*=1y*=13TW*=16解得y*=4/5 y*=3/5原對偶問題的最優(yōu)解為Y*=(4/5,3/5,1,0)第六章一、以下知識點可出單選題和填空題單選題知識點：1．表上作業(yè)法的基本思想和步驟與單純形法類似,因而初始調(diào)運方案的給出就相當(dāng)于找到一個初始基本，這個可行解有可能是最優(yōu)解。2?物資調(diào)運問題中，有m個供應(yīng)地，A,A…，A,A的供應(yīng)量為a(i=1,2…，m),n個需求地TOC\o"1-5"\h\zl2 mj iB,B，…B,B的需求量為b(j=1,2,…，n),則供需平衡條件為遲a=工b。遲a＜工b則1 2 n j i i i ii=1 j=1 i=1 j=1顯示不平衡狀態(tài)。3?運輸問題的模型中，含有的方程個數(shù)為n+m，因為它涉及產(chǎn)地和銷地兩方面的問題。若運輸問題的單位運價表的某一行元素分別加上一個常數(shù)k最優(yōu)調(diào)運方案將肯定不發(fā)生變化,當(dāng)運量發(fā)生變化時才可使其發(fā)生變化。表上作業(yè)法的基本思想和步驟與單純形法類似，那么基變量所在格為有分配數(shù)格，相當(dāng)于基變量取某值。若調(diào)運方案中的某一空格的檢驗數(shù)為1,則在該空格的閉回路上調(diào)整單位運量而使運費增加1,注意這是指單位運費，而不是總運費。7?運輸問題中，調(diào)運方案的調(diào)整應(yīng)在檢驗數(shù)為負(fù)值的點所在的閉回路內(nèi)進(jìn)行，并且被選中負(fù)值應(yīng)為絕對值最大，這樣會令每次調(diào)整的幅度最大，費用降低最快。8?供大于求的不平衡運輸問題，供求關(guān)系為乂。＞甘，這種情況在實際問題中很多。ii求解0—1整數(shù)規(guī)劃的方法是隱枚舉法，它僅是其中的一種方法。填空題知識點表上作業(yè)法中初始方案均為可行解，即為可行方案，但不保證是最優(yōu)方案。表上作業(yè)法中，每一次調(diào)整，“出基變量”的個數(shù)為1個，但其影響的卻不只一個變量發(fā)生變化。所有物資調(diào)運問題，應(yīng)用表上作業(yè)法最后均能找到一個最優(yōu)解，且只有一個唯一的最優(yōu)解。一般講，在給出的初始調(diào)運方案中，最接近最優(yōu)解的是差值法,所以將其結(jié)果稱為近似最優(yōu)解。表上作業(yè)法中，閉回路的構(gòu)成要素為“所有基格+1個空格”,如果少于這個數(shù)目則無法求解。當(dāng)供應(yīng)量大于需求量，欲化為平衡問題，可虛設(shè)一需求點，并令其相應(yīng)運價為最大與最小運量之差，將不足量補上，使供需平衡。在運輸問題中，調(diào)整量的確定應(yīng)選擇偶數(shù)轉(zhuǎn)角點中最小運量，再依次進(jìn)行調(diào)整方案。下列說法正確的有：表上作業(yè)法也是從尋找初始基可行解開始的；當(dāng)一個調(diào)運方案的檢驗數(shù)全部為正值時，當(dāng)前方案一定是最佳方案；表上作業(yè)法中一張供需平衡表對應(yīng)一個基可行解。這些結(jié)論可以從任意問題中得到驗證。運輸問題的求解結(jié)果中可能出現(xiàn)的是：唯一最優(yōu)解；無窮多最優(yōu)解；退化解，不可能出現(xiàn)無可行解。對于供過于求的不平衡運輸問題，下列說法是正確的：仍然可以應(yīng)用表上作業(yè)法求解；在應(yīng)用表上作業(yè)法之前，應(yīng)將其轉(zhuǎn)化為平衡的運輸問題；可以虛設(shè)一個需求地點，令其需求量為二、下列知識點可出簡答題簡答：下表中給出的調(diào)運方案能否作為表上作業(yè)法求解時的初始解，為什么?X銷量X產(chǎn)量B1B2B3B4產(chǎn)量A16511A254211A3538銷量5997答：表中存在以非零元素為頂點的閉回路，不能作為初始方案簡答：判斷表中給出的調(diào)運方案能否作為表上作業(yè)法求解時的初始解，為什么?B1B2B3B4B5B6A3030AQ203050A31030102575A42020銷量204030105025答：不可作為初始方案。因為表中填有數(shù)字的方格數(shù)少于m+n=9，不能形成回路，無法求解。四、下列知識點可出計算題1.用表上作業(yè)法求給出的運輸問題的最優(yōu)解甲乙丙丁產(chǎn)量11067124216059935410104

銷量5246解：用表上作業(yè)法求給出的運輸問題的最優(yōu)解甲乙丙丁產(chǎn)量11067124216059935410104銷量5246甲乙丙丁產(chǎn)量112142369344銷量5246在最優(yōu)調(diào)運方案下的運輸費用最小為118。給出如下運輸問題運\^肖B1B2B3B4產(chǎn)量Al5310490A2169640A320105770銷量305080402001）應(yīng)用最小元素法求其初始方案；2）應(yīng)用位勢法求初始方案的檢驗數(shù)，并檢驗該方案是否為最優(yōu)方案解： （1）初始方案B1BoB3B4產(chǎn)量A1504090A23010040Ao7070一銷量305080402）檢驗表B1B2B3B4uA63-1Arj12A32395-3v0485E基變量檢驗數(shù)全部非負(fù)，該方案為最優(yōu)方案。Al211347A2103595A378127銷量2341010^19求初始方案，并檢驗是否最優(yōu)。解：運\銷B1B2B3B4產(chǎn)量Al22113547A210332595A37821527A4MMMM5銷量23410檢驗：B1B2B3B4uA114A263A378A4204v j——I檢驗數(shù)均為0當(dāng)前解為最優(yōu)解，Z*=55。第七章一、以下知識點可出單選題和填空題單選題知識點：對于一個有n項任務(wù)需要有n個人去完成的分配問題，其解中取值為1的變量數(shù)為n個，二者是一一一對應(yīng)關(guān)系。2．用分枝定界法求極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界，即較小。在整數(shù)規(guī)劃問題當(dāng)中，純整數(shù)規(guī)劃要求全部變量必須都為整數(shù)，這個要求非常絕對。在下列整數(shù)規(guī)劃問題中，分枝定界法和割平面法都可以解決的問題是純整數(shù)規(guī)劃，對于線性規(guī)劃是不適用的。已知整數(shù)規(guī)劃問題p，其相應(yīng)的松馳問題記為p'若問題p'無可行解，則問題P。無可行解,不存在唯一最優(yōu)解等情形。—般講，對于某一問題的線性規(guī)劃與該問題的整數(shù)規(guī)劃可行域的關(guān)系存在前者大于后者，其最優(yōu)解值亦同。7?求解純整數(shù)規(guī)劃的方法是割平面法，每次割去一部分非整數(shù)部分。在0-1整數(shù)規(guī)劃中變量的取值可能是0或1，只有這兩類。填空題知識點在應(yīng)用匈牙利法求解分配問題時，最終求得的分配元應(yīng)是獨立零元素，即選中的元素都是0。在0-1整數(shù)規(guī)劃中變量的取值可能是1或0，它們分別表示兩種狀態(tài)。分枝定界法一般每次分枝數(shù)量為個2個，從某一非整數(shù)開始分起。一般講，對于同一問題，線性規(guī)劃最優(yōu)解與整數(shù)規(guī)劃最優(yōu)解的關(guān)系是前者優(yōu)于后者。即前者的值大于后者。用割平面法求解整數(shù)規(guī)劃問題時，若某個約束條件中有不為整數(shù)的系數(shù)，則需在該約束兩端擴大適當(dāng)倍數(shù)，將其化為整數(shù)，然后求解。關(guān)于分配問題，下列說法正確的有:分配問題是一個高度退化的運輸問題;可以用表上作業(yè)法求解分配問題；匈牙利法所能求解的分配問題，要求規(guī)定一個人只能完成一件工作，同時一件工作也只給一個人做，這些都表現(xiàn)在問題的要求和求解當(dāng)中。對于某一整數(shù)規(guī)劃可能涉及到的解題內(nèi)容為：求其松弛問題；在其松弛問題中增加一個約束方程；應(yīng)用單純形或圖解法；割去部分非整數(shù)解；多次切割，這對于整數(shù)規(guī)劃問題的求解會常常遇到。二、下列知識點可出名詞解釋和簡答題概念：純整數(shù)規(guī)劃：如果要求所有的決策變量都取整數(shù)，這樣的問題成為純整數(shù)規(guī)劃問題。概念：混合整數(shù)規(guī)劃：在線性規(guī)劃問題中，如果要求部分決策變量取整數(shù)，則稱該問題為混合整數(shù)規(guī)劃。簡答：下列整數(shù)規(guī)劃問題maxZ=20xt+10x2+10x3'2xi+20x2+4x3=15s.v6xi+20x2+4x3=20、X],x2,x3^0且為整數(shù)說明能否用先求解相應(yīng)的線性規(guī)劃問題然后四舍五入的辦法來求得該整數(shù)規(guī)劃的一個可行解。答：不考慮整數(shù)約束，求解相應(yīng)線性規(guī)劃得最優(yōu)解為X=10/3,x=x=0，用四舍五人法時，令x=3,x=x=0，其中第2個約束無法滿足，故不可行。因為整數(shù)解也是可行解，必須保證滿足所有約束條件，這是必須的。三、下列知識點可出計算題有四項工作要甲、乙、丙、丁四個人去完成．每項工作只允許一人去完成。每個人只完成其中一項工作，已知每個人完成各項工作的時間如下表。問應(yīng)指派每個人完成哪項工作，使總的消耗時間最少?IIIW甲廠(15)1821IIIW甲廠(15)182124'15乙1923(22)1818丙6(7)16196丁L192123(17)17解：9=L26 9-5 4 01 10 136 0一01025 94 3 00 9 135 022400632130丄工作人、\IIIIII甲15182124乙19232218丙671619丁19212317分配方案 甲一I,乙一III,丙一II,丁一W第17頁共21頁最短時間為15+22+7+17=61若某鉆井隊要從以下10個可供選擇的井位中確定5個鉆井探油。使總的鉆探費用為最小。若10個井位的代號為S,S.…，S相應(yīng)的鉆探費用為C,C，…C，并且井位選擇要滿足下列限制12101210條件：（1） 在s，s，S中至多只能選擇兩個；（2） 在S，s中至少選擇一個；（3）在s，s，S，S中至少選擇兩個。563678試建立這個問題的整數(shù)規(guī)劃模型解：設(shè)x（j=1,???,10）為鉆井隊在第i個井位探油jminZ=￡c.x.用分枝定界法求解下列整數(shù)規(guī)劃問題：（提示:可采用圖解法）maxZ=40x+90x12'9xi+7x2=6s.甘7xi+20x2M70[xt,x2>0且為整數(shù)解：第十章一、以下知識點可出單選題和填空題單選題知識點：最短路問題的計算是從符合某一條件開始逐步推算的，這個條件是0WfWc,其他情形都是錯誤的。 ——r關(guān)于可行流，以下敘述不正確的是：可行流的流量大于零而小于容量限制條件，這種情況不可能存在。關(guān)于最小樹，敘述正確的是：最小樹是一個網(wǎng)絡(luò)中連通所有的點，而權(quán)數(shù)最少的圖，這是最基

本的。關(guān)于圖論中的圖，以下敘述不正確的是：圖論中的邊表示研究對象，點表示研究對象之間的特定關(guān)系，正確的是應(yīng)該將其掉過來。最大流問題中，對于一個可行流，VV有向邊上的流量f必須滿足的條件之一是OWfWc,可以取其最大和最小值。 ij ij ijij填空題知識點最小樹的算法關(guān)鍵是把最近的某