運(yùn)籌學(xué)復(fù)習(xí)資料全套

運(yùn)籌學(xué)復(fù)習(xí)資料一、問答題（5選1）：1、運(yùn)籌學(xué)的主要內(nèi)容有哪些？運(yùn)籌學(xué)為什么在美國被稱為管理科學(xué)，此名稱合理嗎？答：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有決策依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。運(yùn)籌學(xué)的研究內(nèi)容包括規(guī)劃論、圖與網(wǎng)絡(luò)分析、存貯論、排隊(duì)論、對策論、決策論。規(guī)劃論主要解決兩大問題：如何有效利用現(xiàn)有的人力、物力去完成更多的任務(wù)；對于給定的任務(wù)或者目標(biāo)。用最少的人力或物力如何去完成。圖與網(wǎng)絡(luò)分析主要解決生產(chǎn)組織、計(jì)劃管理以及工程施工中的工序安排、工期控制、資源合理調(diào)配問題。決策論研究決策過程中方案的選擇、度量和概率值選取問題。最終獲得最優(yōu)策略、最優(yōu)方案。定量分析技術(shù)作為管理工具，在美國的許多企業(yè)得到廣泛的應(yīng)用，量化管理或者精確管理是美國企業(yè)管理的重點(diǎn)，運(yùn)籌學(xué)在美國被稱為管理科學(xué)。此名稱合理。2、運(yùn)籌學(xué)解決實(shí)際問題的過程可分為哪幾個(gè)階段?答：運(yùn)籌學(xué)解決實(shí)際問題的過程可分為5個(gè)階段：（1）提出并形成問題。要解問題，首先需要提出問題，明確問題的實(shí)質(zhì)及關(guān)鍵所在，這就要求對系統(tǒng)進(jìn)行深入的調(diào)查和分析，確定問題的界限，選準(zhǔn)問題的目標(biāo)。（2）建立模型。運(yùn)籌學(xué)模型是一個(gè)能有效地達(dá)到一定目標(biāo)（或多個(gè)目標(biāo)）行動(dòng)的系統(tǒng)，因此，目標(biāo)一經(jīng)認(rèn)定，就要用數(shù)學(xué)語言描述問題，建立目標(biāo)函數(shù)，分析問題所處的環(huán)境，確定約束條件，探求與問題有關(guān)的決策變量等，并選用合適的方法，建立運(yùn)籌學(xué)模型。（3）分析并求解模型。根據(jù)所建模型的性質(zhì)及其數(shù)學(xué)特征，選擇適當(dāng)?shù)那蠼夥椒?。?）檢驗(yàn)并評(píng)價(jià)模型。模型分析和計(jì)算得到結(jié)果以后，尚需按照它能否解決實(shí)際問題，主要考慮達(dá)成目標(biāo)的情況，選擇合適的標(biāo)準(zhǔn)，并通過一定的方法對模型結(jié)構(gòu)和一些基本參數(shù)進(jìn)行評(píng)價(jià)，以檢驗(yàn)它們是否準(zhǔn)確無誤，否則就要考慮改換或修正模型，增減計(jì)算過程中所用到的資料或數(shù)據(jù)。（5）應(yīng)用或?qū)嵤┠Ｐ偷慕?。?jīng)過反復(fù)檢查以后，最終應(yīng)用或?qū)嵤┠Ｐ偷慕?，就是供給決策者一套有科學(xué)依據(jù)的并為解決問題所需要的數(shù)據(jù)、信息或方案，以輔助決策者在處理問題時(shí)作出正確的決策和行動(dòng)方案。3、試述線性規(guī)劃模型建模的基本步驟及線性規(guī)劃模型的構(gòu)成要素的特征。答：①建?；静襟E：確定決策變量、確定目標(biāo)函數(shù)、確定約束條件。②線性規(guī)劃模型的構(gòu)成要素及特征：決策變量，是規(guī)劃問題中要確定的未知量,用來表示規(guī)劃問題中用數(shù)量表示的方案\措施，可以由決策者決定和控制。目標(biāo)函數(shù)，是決策變量的函數(shù)，反映決策者對于規(guī)劃規(guī)劃問題結(jié)果的要求。約束條件，指決策變量取值時(shí)受到的各種資源條件的限制,通常表達(dá)為含決策變量的等式或者不等式。4、試述線性規(guī)劃與對偶規(guī)劃之間存在的關(guān)系。答：線性規(guī)劃問題具有對偶性，即任何一個(gè)求極大值的線性規(guī)劃問題，都有一個(gè)求極小值的線性規(guī)劃問題與之對應(yīng)，反之亦然。如果把其中一個(gè)叫做原問題，則另一個(gè)就叫做它的對偶問題，并稱這互相聯(lián)系的兩個(gè)問題為一對對偶問題。根據(jù)對偶理論，在解原問題的同時(shí)，也可以得到對偶問題的解，并且還可以提供影子價(jià)格等有價(jià)值的信息。5、什么是資源的影子價(jià)格，它同相應(yīng)的市場價(jià)格之間有何區(qū)別？答：在一對對偶問題（P）和（D）中，若（P）的某個(gè)約束條件的右端常數(shù)bi增加1個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值Z﹡的改變量yi﹡成為第i個(gè)約束條件的影子價(jià)格。如果原規(guī)劃模型屬于在一定資源約束條件下，按一定的生產(chǎn)消耗生產(chǎn)一組產(chǎn)品并尋求總體效益（如利潤）目標(biāo)函數(shù)最大化問題，那么其對偶模型屬于對本問題中每一資源以某種方式進(jìn)行估價(jià)以便得出與最優(yōu)生產(chǎn)計(jì)劃相一致的一個(gè)企業(yè)的最低總價(jià)值。該對偶模型中資源的估價(jià)表現(xiàn)為相應(yīng)的資源的影子價(jià)格。影子價(jià)格不是市場價(jià)格，它是根據(jù)企業(yè)本身的資源情況bi、消耗系數(shù)aij和產(chǎn)品的利潤cj計(jì)算出來的一種價(jià)格，是新增資源所創(chuàng)造的價(jià)值，是邊際價(jià)格。不同的企業(yè)，即使是相同的資源，其影子價(jià)格也不一定相同。就是同一個(gè)企業(yè)，在不同的生產(chǎn)周期，資源的影子價(jià)格也不完全一樣。企業(yè)決策者可以將企業(yè)資源的影子價(jià)格與市場價(jià)格相比較，買賣這種資源，使企業(yè)獲利或降低成本，此時(shí)該資源的影子價(jià)格也將發(fā)生變化，直到影子價(jià)格與市場價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。影子價(jià)格是一種機(jī)會(huì)成本。二、建模題（只要求建立模型）1、資源的合理利用問題。P7一般提法：某廠計(jì)劃在下一生產(chǎn)周期內(nèi)生產(chǎn)B1,B2,…Bn種產(chǎn)品，要消耗A1,A2,…Am種資源，已知每件產(chǎn)品所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤如表所示，問如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤最大？設(shè)決策變量xj表示下一個(gè)周期產(chǎn)品Bj(j=1,2,…n)的產(chǎn)量，則此問題的數(shù)學(xué)模型可歸結(jié)為：求xj，使得2、生產(chǎn)組織與計(jì)劃問題。P8一般提法：某工廠用機(jī)床A1,A2,…Am加工B1,B2,…Bn種零件。在一個(gè)周期內(nèi)，各機(jī)床可能工作的機(jī)時(shí)（臺(tái)時(shí)），工廠必須完成各種零件的數(shù)量、各機(jī)床加工每個(gè)零件的時(shí)間（機(jī)時(shí)/個(gè)）和加工每個(gè)零件的成本（元/個(gè)）如表所示，問如何安排各機(jī)床的生產(chǎn)任務(wù)，才能完成加工任務(wù)，又使總成本最低？3、合理配料問題。P11一般提法：某飼養(yǎng)場用n種飼料B1,B2,…Bn配置成含有m種營養(yǎng)成分A1,A2,…Am的混合飼料，其余資料如表所示。問應(yīng)如何配料，才能既滿足需要，又使混合飼料的總成本最低？4、運(yùn)輸問題。P175設(shè)xij表示由產(chǎn)地Ai運(yùn)往銷地Bj(i=1,2,…m;j=1,2,….n)的運(yùn)量，則當(dāng)產(chǎn)銷平衡時(shí)，其模型如下：當(dāng)產(chǎn)大于銷時(shí)，其模型是：當(dāng)產(chǎn)小于銷時(shí)，其模型是：5、合理下料問題。P247一般提法：設(shè)用某型號(hào)的圓鋼下零件A1,A2,…,Am的毛坯。在一根圓鋼上下料的方式有B1,B2,…Bn種，每種下料方式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？設(shè)：xj

表示用Bj(j=1.2…n)種方式下料的圓鋼根數(shù)，則這一問題的數(shù)學(xué)模型為：求xj，使得：6、0-1整數(shù)規(guī)劃問題。P267例1一般模型nmaxZ=∑cixi；i=1n∑aijxj≤bi（i=1，2，…，m）；j=1s.t.xj=0,1（j=1，2，…，n）。7、目標(biāo)規(guī)劃P228例2課件：例三一般形式課本例二：已知一個(gè)生產(chǎn)計(jì)劃的線性規(guī)劃模型為：其中目標(biāo)函數(shù)為總利潤，x1,x2為產(chǎn)品A、B產(chǎn)量?，F(xiàn)有下列目標(biāo)：1、要求總利潤必須超過2500元；2、考慮產(chǎn)品受市場影響，為避免積壓，A、B的生產(chǎn)量不超過60件和100件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并用圖解法求解。解：以產(chǎn)品A、B的單件利潤比2.5：1為權(quán)系數(shù)，模型如下：三、計(jì)算題：1、單純形法。P51例1。例1：將線性規(guī)劃問題化為典式,并列初始單純形表解：先引入松馳變量x1、x2、x3，將問題化為典式取初始可行基

此時(shí)問題已是關(guān)于基的典式，故可直接作初始單純形表，由表Ⅰ可知，初始基可行解（0，0，170，100，150），初始目標(biāo)函數(shù)值再進(jìn)行第二步迭代，由表Ⅱ可知，新的基可行解（0，30，110,10,0），相應(yīng)的目標(biāo)函數(shù)再進(jìn)行第三步迭代，由表Ⅲ可知，檢驗(yàn)數(shù)已全部非正，于是判定已求得最優(yōu)解（50/7，200/7，540/7，0,,0），相應(yīng)的目標(biāo)函數(shù)最優(yōu)值序號(hào)1018000Ⅰ000170100150521002301015001Z01018000Ⅱ0018110103023/5010-2/57/5001-3/51/51001/5Z-54032/5000-18/5Ⅲ01018540/750/7200/7001-23/711/71005/7-3/7010-1/72/7Z-4100/7000-32/7-6/72、某廠準(zhǔn)備生產(chǎn)A、B、C三種產(chǎn)品，它們都要消耗勞動(dòng)力和原材料，已知有關(guān)數(shù)據(jù)如下表：ABC資源限制勞動(dòng)力63545原材料34530單件利潤（元）415(1)

試建立線性規(guī)劃模型，求使該廠獲利最大的生產(chǎn)計(jì)劃。(2)

原材料增加1個(gè)單位,能夠使最優(yōu)目標(biāo)函數(shù)值增加或減少多少?解：（1）設(shè)決策變量分別表示A、B、C三種產(chǎn)品的產(chǎn)量，則此問題的數(shù)學(xué)模型為:引入松馳變量將問題化為標(biāo)準(zhǔn)型選初始可行基。令非基變量得初始基可行解。列單純形表序號(hào)C41500CBXBbx1x2x3x4x5Ⅰ00x4x5453063510345*00Z04

1

500Ⅱ05x4x31563*-101-13/54/5101/5Z-301-300-1Ⅲ45x1x3531-1/301/3-1/3011-1/52/5Z-350-8/30-1/3-2/3由上表知，最優(yōu)解為X*=（5，0，3，0，0）T，目標(biāo)函數(shù)最優(yōu)值Z*=35。即最優(yōu)生產(chǎn)計(jì)劃為：A產(chǎn)品生產(chǎn)5單位，C產(chǎn)品生產(chǎn)3單位，B產(chǎn)品生產(chǎn)0單位。（2）寫出此問題線性規(guī)劃的對偶規(guī)劃，由上表可知對偶規(guī)劃的最優(yōu)解為Y*=（1/3，2/3）。根據(jù)對偶理論，對偶規(guī)劃的最優(yōu)解就是原規(guī)劃中變量的影子價(jià)格，勞動(dòng)力和原材料的影子價(jià)格分別為1/3，2/3。因此，原材料增加1個(gè)單位，按最優(yōu)生產(chǎn)計(jì)劃安排生產(chǎn)可以多獲利2/3個(gè)單位。3、某公司在計(jì)劃期內(nèi)要安排生產(chǎn)A、B兩種產(chǎn)品（假設(shè)市場銷路很好）。生產(chǎn)單位產(chǎn)品的利潤以及所需的勞動(dòng)力、設(shè)備臺(tái)時(shí)以及原材料的消耗資料由下表給出。產(chǎn)品A產(chǎn)品B資源限制勞動(dòng)力設(shè)備原材料9434510360（工時(shí)）200（臺(tái)時(shí)）300（千克）單位產(chǎn)品利潤70120⑴

試求使該公司獲利最大的生產(chǎn)方案。⑵

設(shè)備增加1臺(tái)時(shí)，能夠使最優(yōu)目標(biāo)函數(shù)增加或減少多少？解：⑴設(shè)A、B兩種產(chǎn)品的產(chǎn)量分別是X1、X2，此生產(chǎn)問題的線性規(guī)劃模型是：用單純形法求解，首先引入松馳變量x3、x4、x5，將線性規(guī)劃化成標(biāo)準(zhǔn)型，取松馳變量x3、x4、x5為基變量，求得初始基可行解X=（0，0，360，200，300）。列出單純形表，根據(jù)規(guī)則在表中求解。序號(hào)C70120000CBXBbX1X2X3X4X5Ⅰ000X3X4X53602003009410045010310001Z070120000Ⅱ00120X3X4X224050307.8010-0.42.5011-0.50.31000.1Z-360034000-12Ⅲ070120X3X1X284202400

-2.12

-3.121.1610

0.4

0.4-0.201-0.12

-0.120.16Z-4280000-13.6-5.2由于最終表中所有的檢驗(yàn)數(shù)都已經(jīng)成為負(fù)數(shù)或者零,于是得到最優(yōu)解:目標(biāo)函數(shù)最優(yōu)值（2）寫出此問題的線性規(guī)劃的對偶規(guī)劃，求出對偶規(guī)劃的最優(yōu)解，根據(jù)對偶理論，對偶規(guī)劃的最優(yōu)解就是原規(guī)劃中變量的影子價(jià)格，勞動(dòng)工時(shí)、設(shè)備臺(tái)時(shí)和原材料的影子價(jià)格分別為0，13.6，5.2。因此，設(shè)備每增加1臺(tái)時(shí)，按最優(yōu)計(jì)劃安排生產(chǎn)可以多獲利13.6元。4、對偶問題。作業(yè)P136（9）（10）（11）（9）已知線性規(guī)劃問題.①寫出其對偶問題；②已知原問題的最優(yōu)解為3，2，0，試根據(jù)互補(bǔ)松弛定理，直接求出對偶問題的最優(yōu)解；（3）如果上述規(guī)劃中的第一個(gè)約束為資源約束，寫出這種資源的影子價(jià)格。解：①原問題的對偶問題為②由于＞0，＞0，由互補(bǔ)松馳定理得其對應(yīng)的對偶問題的約束條件為0，即所以對偶問題的最優(yōu)解為③，第一種資源的影子價(jià)格為4（10）已知線性規(guī)劃問題其對偶問題的最優(yōu)解為，試根據(jù)對偶理論求出原問題的最優(yōu)解。解：此LP問題的對偶問題為將代入對偶問題的約束條件（1）（2）為嚴(yán)格不等式，由互補(bǔ)松馳定理推知，。又因。故原問題的兩個(gè)約束條件應(yīng)取等式，有解得，故原問題的最優(yōu)解為（0，0，4，4），目標(biāo)函數(shù)最優(yōu)值為（11）已知線性規(guī)劃問題①寫出其對偶問題；②已知原問題的最優(yōu)解為1，1，2，0試根據(jù)對偶理論，直接求出對偶問題的最優(yōu)解。解：①對偶規(guī)劃為②將X*=（1，1，2，0）T代入原方程的約束條件則最后一個(gè)約束為松約束，所以又由于，，，由互補(bǔ)松馳定理知，其對偶問題的約束方程必為等式，即所以有即對偶問題的最優(yōu)解為（2，2，1，0）5、運(yùn)輸問題。P177例1。作業(yè)P213。2（1）⑴P177例1。⑵作業(yè)P213。2（1）已知運(yùn)輸問題的產(chǎn)銷平衡表與單位運(yùn)價(jià)表如表所示，試用表上作業(yè)法分別求最優(yōu)解（表中M代表充分大的正數(shù)）。銷地產(chǎn)地B1B2B3B4產(chǎn)量A137645A224322A343853銷量3322解：單位運(yùn)價(jià)銷地B1B2B3B4產(chǎn)量產(chǎn)地A1①◎②②5，4，2，03764A2②×××2，02432A3×③××3，04385銷量3，1，03，02，02，0（x22,x12,x11,x21）為一個(gè)閉回路，σ22=（4+3）-（7+2）=-2＜0（x23,x13,x11,x21）為一個(gè)閉回路，σ23=（3+3）-（6+2）=-2＜0（x24,x14,x11,x21）為一個(gè)閉回路，σ24=（2+3）-（4+2）=-1＜0（x31,x11,x12,x32）為一個(gè)閉回路，σ31=（4+7）-（3+3）=5＞0（x33,x13,x12,x32）為一個(gè)閉回路，σ33=（8+7）-（6+3）=7＞0（x34,x14,x12,x32）為一個(gè)閉回路，σ34=（5+7）-（4+3）=5＞0單位運(yùn)價(jià)銷地B1B2B3B4產(chǎn)量產(chǎn)地A1③◎◎②53764A2◎×②×22432A3×③××34385銷量3322X11*=3,X12*=0,X13*=0,X14*=2,X21*=0,X23*=2,X32*=3,其余Xij*=0，目標(biāo)函數(shù)的最優(yōu)值為Z*=3×3+0×7+0×6+2×4+0×2+2×3+3×3=32.6、用匈牙利法求解分配問題。P285、7（1）（2）（1）已知效益矩陣為79101213121617（cij）=1516141511121516解：791012－702350234（cij）=13121617－121045104415161415－141201120011121516－1101450144－1◎234√◎1231◎442◎0042◎?3〈422◎??1442√?033√◎134√01012◎44√202222◎?3〈44400??33√0011√√?1◎12◎2244?◎◎?11此時(shí)，獨(dú)立零元素的個(gè)數(shù)m＝4。于是已求得最優(yōu)解X13=X22*=X34*=X41*=1，其余Xij*=0。目標(biāo)函數(shù)最優(yōu)值Z﹡＝10×1+12×1+15×1+11×1＝48(2)已知效益矩陣為38210387297（cij）=64275842359106910解：382103－2160810407087297－26507553064（cij）=64275－2420533004284235－262013500029106910－63403422023－1－2－1－1◎4?7?0427053◎64√310423◎?42302425??◎25020222?23√00001√?427◎31◎423◎2425?2◎2◎???1此時(shí)，獨(dú)立零元素的個(gè)數(shù)m＝5。于是已求得最優(yōu)解X15*=X23*=X32*=X44*=X51*=1，其余Xij*=0。目標(biāo)函數(shù)最優(yōu)值Z﹡＝3×1+2×1+4×1+3×1+9×1＝217、最短路徑問題。解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始，第一階段（C

→D）：

C

有三條路線到終點(diǎn)Df1

(C1

)=1；

f1(C2

)=3；

f1

(C3

)=4第二階段（B

→C）：

B

到C

有六條路線。d(

B1,C1

)+

f1

(C1

)3+14f2

(

B1

)=mind(

B1,C2

)+

f1

(C2

)=min3+3=min6=4d(

B1,C3

)+

f1

(C3

)1+45最短路線為B1→C1

→D路長4d(

B2,C1

)+

f1

(C1

)2+13f2

(

B2

)=mind(

B2,C2

)+

f1

(C2

)=min3+3=min6=3d(

B2,C3

)+

f1

(C3

)1+45最短路線為B2→C1

→D路長3第三階段（

A

→

B

）：

A

到B

有二條路線。d(A,

B1

)＋

f2

(

B1

)2+4f3

(A)=min=min=min｛6,7｝=6d(A,

B2

)＋

f2

(

B2

)4+3所以：最短路線為A→B1→C1

→D。路長6解：整個(gè)計(jì)算過程分四個(gè)階段，從最后一個(gè)階段開始，第一階段（D

→E）：

D

有兩條路線到終點(diǎn)E。顯然有

f1

(D1

)=5；

f1(D2

)=2第二階段（C

→D）：

C

到D有三條路線。d(

C1,D1

)+

f1

(D1

)3+58f2

(

C1

)=mind(

C1,D2

)+

f1

(D2

)=min9+2=min11=8d(