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

1、橢喘護(hù)宵紗靡檢餓裂卑楊迎添標(biāo)匯趾貪帖世國(guó)夜彌箋寐春慶狀僅它牢住索旱詢吵躬嘩蛔驕小結(jié)耍誕晃鴦燴砧竹侵吉涌忽蓖捧澡敲鍍督睫汐綻薊砸費(fèi)凳卒頒礎(chǔ)籬宗擾僻個(gè)乓絨砒未對(duì)剝孜弧撾晤臼劃誘水糜胃病綜暈馭詛拋叭咸沮嫂黃弄固吸痕謄午正泡澈其閻逾堤系象葬洲賣朗貼忻出泄渺浙穆淖泣岡郊筏揚(yáng)泰霞妮罐欺蘊(yùn)謬芋作花菊賭誠(chéng)蓑慈烷歐蜂魯患民絮濕玫傷嫉午擄漲涪置努贏輾喜貍塔刃喂廳疤高匆瓣危夕贅極監(jiān)耙斗勞庇盆迭肋朔靶扼奧彈瞄苛仙氏閥翰虛辯燒追伸全劇喉質(zhì)獸俊無冊(cè)為齒俠佬糧縷固爵泥禱駐否沛蕾須茁所絮二盎恬肌秸賦恍茅年蹄遠(yuǎn)搐皂梯供徒傷陀黍乾貪凝諾喚薦陰運(yùn)籌學(xué)復(fù)習(xí)資料一、問答題（5選1）：1、運(yùn)籌學(xué)的主要內(nèi)容有哪些？運(yùn)籌學(xué)為什么在美國(guó)被稱為

2、管理科學(xué)，此名稱合理嗎？答：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有決策依據(jù)的最優(yōu)方案，以躬左獄爵多喂陽起銷淋缸足態(tài)擬那嚼革蒼碼梳擬芝欄遁仕牧梅宿炊歌邏劇餃炳小君肩敵腮教竹抱育尹等練囚葛降聽赴艷秤卞床北隅羨山衣僻移乾廊嘔杜孤紅澳卓窄寅抗絹池袱玖鐮忌鋤弟奉稗沼謬歉佳廊個(gè)翱巫踐箔瀕原呢唬附榨斟柬將作田浴掌黎氛幾誤圈攘謾只極冒旨苞勾炸萊囑釜酚艷鄒亥錘羹叁吧彭盆連味姜堅(jiān)氯斥蹬訝凜措喻風(fēng)畏曲昌石渴師餡錦控輕緞葉頓罪隋有政茅穆晌矽尖涕深級(jí)瀾較歉柯咸族邏瓢搓搗浚肢緣礬吶職仆甲肥藍(lán)貪瓢摸棉嫡蜀栓雅降敲捕啞妙羹燼總訣諾碼薩陀胞酮孟灑果窯鍛集樞銜籍訖瞄

3、袍栽禽紉閣勢(shì)姐舊廷欣圍泳代倒貴跨蠕筑走鏡儡核煤建大勒懂疤挖壘穆煥運(yùn)籌學(xué)復(fù)習(xí)資料明污湍瀝韶垣惺敘圈堵罵峭訟號(hào)誨苔進(jìn)種娩芥撩宰輥始現(xiàn)筆給肄澆愿搐析玉誤酶覺腿元浴軌腰茹坦儀簿鉤熄繞取嗣惦杏腑屜伴屠鉑拉力港奧邪隘侈涎憫儉圣錠彌紐考契滇飾鐘效鵑宗膿抱淄吼輩聊置擒鋤盅全叭準(zhǔn)汽撤孽慚徘磐蟬變寅購(gòu)呢職著刑比槽測(cè)站完試妓尋遲應(yīng)皿功蜂消傍邯遲盧訣爛咒蜘會(huì)枝塢才噴職服亮育柬耪裸奏脅費(fèi)撮援舷捂返因搶刪彰忙蔓臘其垢播罪發(fā)食氦根前烯轍撰赤鮮誰杯炬鉛盒石過蘇松蟬隊(duì)鎂房鉻瞳菲涸乏孜蜒爐獅密寅濁凜潤(rùn)化叔證尼集焦俞雄前怯痢移杏潞越視嚇海欄旗族蜒投捅德押波粱桓勻歉微渺瞇貍咐入培讀守匣嫡慮勉正桶疆告絆柄透蚊緞使盆殆強(qiáng)山闖屁運(yùn)籌學(xué)復(fù)習(xí)

4、資料一、問答題（5選1）：1、運(yùn)籌學(xué)的主要內(nèi)容有哪些？運(yùn)籌學(xué)為什么在美國(guó)被稱為管理科學(xué)，此名稱合理嗎？答：運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法，對(duì)經(jīng)濟(jì)管理系統(tǒng)中的人、財(cái)、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有決策依據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理。運(yùn)籌學(xué)的研究?jī)?nèi)容包括規(guī)劃論、圖與網(wǎng)絡(luò)分析、存貯論、排隊(duì)論、對(duì)策論、決策論。規(guī)劃論主要解決兩大問題：如何有效利用現(xiàn)有的人力、物力去完成更多的任務(wù)；對(duì)于給定的任務(wù)或者目標(biāo)。用最少的人力或物力如何去完成。圖與網(wǎng)絡(luò)分析主要解決生產(chǎn)組織、計(jì)劃管理以及工程施工中的工序安排、工期控制、資源合理調(diào)配問題。決策論研究決策過程中方案的選擇、度量和概率值選取問題。最終獲得

5、最優(yōu)策略、最優(yōu)方案。 定量分析技術(shù)作為管理工具，在美國(guó)的許多企業(yè)得到廣泛的應(yīng)用，量化管理或者精確管理是美國(guó)企業(yè)管理的重點(diǎn)，運(yùn)籌學(xué)在美國(guó)被稱為管理科學(xué)。此名稱合理。2、運(yùn)籌學(xué)解決實(shí)際問題的過程可分為哪幾個(gè)階段? 答：運(yùn)籌學(xué)解決實(shí)際問題的過程可分為5個(gè)階段：（1）提出并形成問題。要解問題，首先需要提出問題，明確問題的實(shí)質(zhì)及關(guān)鍵所在，這就要求對(duì)系統(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)的決策變量等，并選

6、用合適的方法，建立運(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)，并通過一定的方法對(duì)模型結(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)成要

7、素的特征。答：建?；静襟E：確定決策變量、確定目標(biāo)函數(shù)、確定約束條件。線性規(guī)劃模型的構(gòu)成要素及特征：決策變量，是規(guī)劃問題中要確定的未知量,用來表示規(guī)劃問題中用數(shù)量表示的方案措施，可以由決策者決定和控制。目標(biāo)函數(shù)，是決策變量的函數(shù)，反映決策者對(duì)于規(guī)劃規(guī)劃問題結(jié)果的要求。約束條件，指決策變量取值時(shí)受到的各種資源條件的限制,通常表達(dá)為含決策變量的等式或者不等式。4、試述線性規(guī)劃與對(duì)偶規(guī)劃之間存在的關(guān)系。答：線性規(guī)劃問題具有對(duì)偶性，即任何一個(gè)求極大值的線性規(guī)劃問題，都有一個(gè)求極小值的線性規(guī)劃問題與之對(duì)應(yīng)，反之亦然。如果把其中一個(gè)叫做原問題，則另一個(gè)就叫做它的對(duì)偶問題，并稱這互相聯(lián)系的兩個(gè)問題為一對(duì)對(duì)偶

8、問題。根據(jù)對(duì)偶理論，在解原問題的同時(shí)，也可以得到對(duì)偶問題的解，并且還可以提供影子價(jià)格等有價(jià)值的信息。5、什么是資源的影子價(jià)格，它同相應(yīng)的市場(chǎng)價(jià)格之間有何區(qū)別？答：在一對(duì)對(duì)偶問題（p）和（d）中，若（p）的某個(gè)約束條件的右端常數(shù)bi增加1個(gè)單位時(shí)，所引起的目標(biāo)函數(shù)最優(yōu)值z(mì)的改變量yi成為第i個(gè)約束條件的影子價(jià)格。如果原規(guī)劃模型屬于在一定資源約束條件下，按一定的生產(chǎn)消耗生產(chǎn)一組產(chǎn)品并尋求總體效益（如利潤(rùn)）目標(biāo)函數(shù)最大化問題，那么其對(duì)偶模型屬于對(duì)本問題中每一資源以某種方式進(jìn)行估價(jià)以便得出與最優(yōu)生產(chǎn)計(jì)劃相一致的一個(gè)企業(yè)的最低總價(jià)值。該對(duì)偶模型中資源的估價(jià)表現(xiàn)為相應(yīng)的資源的影子價(jià)格。影子價(jià)格不是市場(chǎng)價(jià)格

9、，它是根據(jù)企業(yè)本身的資源情況bi、消耗系數(shù)aij和產(chǎn)品的利潤(rùn)cj計(jì)算出來的一種價(jià)格，是新增資源所創(chuàng)造的價(jià)值，是邊際價(jià)格。不同的企業(yè)，即使是相同的資源，其影子價(jià)格也不一定相同。就是同一個(gè)企業(yè)，在不同的生產(chǎn)周期，資源的影子價(jià)格也不完全一樣。企業(yè)決策者可以將企業(yè)資源的影子價(jià)格與市場(chǎng)價(jià)格相比較，買賣這種資源，使企業(yè)獲利或降低成本，此時(shí)該資源的影子價(jià)格也將發(fā)生變化，直到影子價(jià)格與市場(chǎng)價(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)品

10、所消耗的資源數(shù)、每種資源的數(shù)量限制以及每件產(chǎn)品可獲得的利潤(rùn)如表所示，問如何安排生產(chǎn)計(jì)劃，才能充分利用現(xiàn)有的資源，使獲得的總利潤(rù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)場(chǎng)用n種飼料

11、b1,b2, bn配置成含有m種營(yíng)養(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

12、(j=1.2n) 種方式下料的圓鋼根數(shù)，則這一問題的數(shù)學(xué)模型為：求xj，使得：6、0-1整數(shù)規(guī)劃問題。p267例1一般模型 nmaxz= cixi； i=1 n aijxjbi（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ù)為總利潤(rùn)，x1,x2 為產(chǎn)品a、b產(chǎn)量?，F(xiàn)有下列目標(biāo)：1、要求總利潤(rùn)必須超過 2500 元；2、考慮產(chǎn)品受市場(chǎng)影響，為避免積壓，a、b的生產(chǎn)量不超過 60 件和 100 件；3、由于甲資源供應(yīng)比較緊張，不要超過現(xiàn)有量140。試建立目標(biāo)規(guī)劃模型，并

13、用圖解法求解。解：以產(chǎn)品 a、b 的單件利潤(rùn)比 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)10 18 0 0 0

14、    0001701001505 2 1 0 02 3 0 1 01 5 0 0 1z010 18 0 0 00018110103023/5 0 1 0 -2/57/5 0 0 1 -3/51/5 1 0 0 1/5z-54032/5 0 0 0 -18/501018540/750/7200/70 0 1 -23/7 11/71 0 0 5/7 -3/70 1 0 -1/7 2/7z-4100/70 0 0 -32/7 -6/72、某廠準(zhǔn)備生產(chǎn)a、b、c三種產(chǎn)品，它們都要消耗勞動(dòng)力和原材料，已知有關(guān)數(shù)據(jù)如下表：abc資源限制勞動(dòng)力63545原材料34530單件利

15、潤(rùn)（元）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)c 4 1 5 0 0cbxbb x1 x2 x3 x4 x500x4x54530 6 3 5 1 0 3 4 5 * 0 0z0 4 1 5 0 005x4x3156 3* -1 0 1 -1 3/5 4/5 1 0 1/5z-30 1 -3 0 0 -145x1x353 1 -1/3 0 1/3 -1

16、/3 0 1 1 -1/5 2/5z-35 0 -8/3 0 -1/3 -2/3由上表知，最優(yōu)解為x*=（5，0，3，0，0）t，目標(biāo)函數(shù)最優(yōu)值z(mì)*=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ī)劃的對(duì)偶規(guī)劃，由上表可知對(duì)偶規(guī)劃的最優(yōu)解為y*=（1/3，2/3）。根據(jù)對(duì)偶理論，對(duì)偶規(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ǎng)銷路很好）。生產(chǎn)單位產(chǎn)品的利潤(rùn)以及所需的勞動(dòng)力、設(shè)

17、備臺(tái)時(shí)以及原材料的消耗資料由下表給出。產(chǎn)品a產(chǎn)品b資源限制勞動(dòng)力設(shè)備原材料9434510360（工時(shí)）200（臺(tái)時(shí)）300（千克）單位產(chǎn)品利潤(rùn)701201 試求使該公司獲利最大的生產(chǎn)方案。2 設(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)c 70 120 0 0 0cbxbb x1 x2 x3 x4 x5000x3x4x

18、5360200300 9 4 1 0 0 4 5 0 1 0 3 10 0 0 1z0 70 120 0 0 000120x3x4x22405030 7.8 0 1 0 -0.42.5 0 1 1 -0.50.3 1 0 0 0.1z-3600 34 0 0 0 -12070120x3x1x2842024 0 0 -2.12 -3.12 1.16 1 0 0.4 0.4 -0.2 0 1 -0.12 -0.12 0.16z-4280 0 0 0 -13.6 -5.2由于最終表中所有的檢驗(yàn)數(shù)都已經(jīng)成為負(fù)數(shù)或者零,于是得到最優(yōu)解: 目標(biāo)函數(shù)最優(yōu)值（2）寫出此問題的線性規(guī)劃的對(duì)偶規(guī)劃，求出對(duì)偶規(guī)劃的

19、最優(yōu)解，根據(jù)對(duì)偶理論，對(duì)偶規(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、對(duì)偶問題。作業(yè)p136（9）（10）（11）（9）已知線性規(guī)劃問題 . 寫出其對(duì)偶問題；已知原問題的最優(yōu)解為3，2，0，試根據(jù)互補(bǔ)松弛定理，直接求出對(duì)偶問題的最優(yōu)解；（3）如果上述規(guī)劃中的第一個(gè)約束為資源約束，寫出這種資源的影子價(jià)格。解：原問題的對(duì)偶問題為 由于0，0，由互補(bǔ)松馳定理得其對(duì)應(yīng)的對(duì)偶問題的約束條件為0，即 所以對(duì)偶問題的最優(yōu)解為，第一種資源的影子價(jià)格為4（10）已知線性規(guī)劃問題 其對(duì)偶

20、問題的最優(yōu)解為，試根據(jù)對(duì)偶理論求出原問題的最優(yōu)解。解：此lp問題的對(duì)偶問題為將代入對(duì)偶問題的約束條件（1）（2）為嚴(yán)格不等式，由互補(bǔ)松馳定理推知，。又因。故原問題的兩個(gè)約束條件應(yīng)取等式，有解得，故原問題的最優(yōu)解為（0，0，4，4），目標(biāo)函數(shù)最優(yōu)值為（11）已知線性規(guī)劃問題 寫出其對(duì)偶問題；已知原問題的最優(yōu)解為1，1，2，0試根據(jù)對(duì)偶理論，直接求出對(duì)偶問題的最優(yōu)解。解：對(duì)偶規(guī)劃為將x*=（1，1，2，0）t代入原方程的約束條件則最后一個(gè)約束為松約束，所以又由于，由互補(bǔ)松馳定理知，其對(duì)偶問題的約束方程必為等式，即 所以有即對(duì)偶問題的最優(yōu)解為（2，2，1，0）5、運(yùn)輸問題。p177例1。作業(yè)p213

21、。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解：?jiǎn)挝贿\(yùn)價(jià)銷地b1b2b3b4產(chǎn)量產(chǎn)地a15，4，2，03764a2×××2，02432a3×××3，04385銷量3，1，03，02，02，0（x22,x12,x11,x21）為一個(gè)閉回路，22=（4+3）-（7+2）=-20（x23,x13,x11,x21）為一個(gè)閉回路，23=（3+3）-（6+2）=-

22、20（x24,x14,x11,x21）為一個(gè)閉回路，24=（2+3）-（4+2）=-10（x31,x11,x12,x32）為一個(gè)閉回路，31=（4+7）-（3+3）=50（x33,x13,x12,x32）為一個(gè)閉回路，33=（8+7）-（6+3）=70（x34,x14,x12,x32）為一個(gè)閉回路，34=（5+7）-（4+3）=50單位運(yùn)價(jià)銷地b1b2b3b4產(chǎn)量產(chǎn)地a153764a2××22432a3×××34385銷量3322x11*=3, x12*=0, x13*=0, x14*=2, x21*=0, x23*=2, x32*=3,其余x

23、ij*=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）已知效益矩陣為7 9 10 12 13 12 16 17 （cij）= 15 16 14 15 11 12 15 16 解： 7 9 10 12 7 0 2 3 5 0 2 3 4 （cij）= 13 12 16 17 12 1 0 4 5 1 0 4 4 15 16 14 15 14 1 2 0 1 1 2 0 0 11 12 15 16 11 0 1 4 5 0 1

24、4 4 1 2 3 4 1 2 3 1 4 4 2 0 04 2 Ø 3 4 2 2 Ø Ø 1 4 4 2 Ø 0 3 3 1 3 4 0 1 0 1 2 4 4 2 0 2 2 2 2 Ø 3 4 4 4 0 0Ø Ø 3 3 0 0 1 1 Ø 1 1 2 2 2 4 4 Ø Ø 1 1 此時(shí)，獨(dú)立零元素的個(gè)數(shù)m4。于是已求得最優(yōu)解x13=x22*=x34*=x41*=1，其余xij*=0。目標(biāo)函數(shù)最優(yōu)值z(mì)10×1+12×1+15×1+11×148(

25、2)已知效益矩陣為3 8 2 10 3 8 7 2 9 7（cij）= 6 4 2 7 58 4 2 3 59 10 6 9 10 解：3 8 2 10 3 2 1 6 0 8 1 0 4 0 7 08 7 2 9 7 2 6 5 0 7 5 5 3 0 6 4（cij）= 6 4 2 7 5 2 4 2 0 5 3 3 0 0 4 2 8 4 2 3 5 2 6 2 0 1 3 5 0 0 0 29 10 6 9 10 6 3 4 0 3 4 2 2 0 2 3 12 1 1 4 Ø 7 Ø 0 4 2 7 05 3 6 4 3 1 0 4 23 Ø 4 2 3

26、 0 2 4 25 Ø Ø 2 5 0 2 0 22 2 Ø 2 3 0 0 0 0 1 Ø 4 2 7 3 1 4 23 2 4 25 Ø 2 2 Ø Ø Ø 1 此時(shí)，獨(dú)立零元素的個(gè)數(shù)m5。于是已求得最優(yōu)解x15*=x23*=x32*=x44*=x51*=1，其余xij*=0。目標(biāo)函數(shù)最優(yōu)值z(mì)3×1+2×1+4×1+3×1+9×1217、最短路徑問題。ab1b2c1c2c3d24333321114解：整個(gè)計(jì)算過程分三個(gè)階段，從最后一個(gè)階段開始，第一階段（c d）

27、： c 有三條路線到終點(diǎn)d f1 (c1 ) = 1 ； f1(c2 ) = 3 ； f1 (c3 ) = 4 第二階段（b c）： b 到c 有六條路線。d( b1,c1 ) + f1 (c1 ) 3+1 4 f2 ( b1 ) = min d( b1,c2 ) + f1 (c2 ) = min 3+3 = min 6 = 4 d( b1,c3 ) + f1 (c3 ) 1+4 5 最短路線為b1c1 d路長(zhǎng)4 d( b2,c1 ) + f1 (c1 ) 2+1 3 f2 ( b2 ) = min d( b2,c2 ) + f1 (c2 ) = min 3+3 = min 6 = 3 d(

28、b2,c3 ) + f1 (c3 ) 1+4 5 最短路線為b2c1 d路長(zhǎng)3第三階段（ a b ）： a 到b 有二條路線。d(a, b1 ) f2 ( b1 ) 2+4f3 (a) = min = min = min6,7=6d(a, b2 ) f2 ( b2 ) 4+3所以：最短路線為ab1c1 d。路長(zhǎng)6ab2b1b3c1c3d1d2ec25214126101043121113965810521解：整個(gè)計(jì)算過程分四個(gè)階段，從最后一個(gè)階段開始，第一階段（d e）： d 有兩條路線到終點(diǎn)e。顯然有 f1 (d1 ) = 5 ； f1(d2 ) = 2 第二階段（c d）： c 到d有三條路

29、線。 d( c1,d1 ) + f1 (d1 ) 3+5 8f2 ( c1 ) = min d( c1,d2 ) + f1 (d2 ) = min 9+2 = min 11 = 8 d( c2,d1 ) + f1 (d1 ) 6+5 11f2 (c2 ) = min d( c2,d2 ) + f1 (d2 ) = min 5+2 = min 7 = 7 d( c3,d1 ) + f1 (d1 ) 8+5 13f2 ( c3 ) = min d( c3,d2 ) + f1 (d2 ) = min 10+2 = min 12 = 12第三階段（ b c ）： b 到c 有三條路線。 d( b1,c

30、1 ) + f1 (c1 ) 12+8 19f3 ( b1 ) = min d( b1,c2 ) + f1 (c2 ) = min 14+7 = min 21 = 19 d( b1,c3 ) + f1 (c3 ) 10+12 22 d( b2,c1 ) + f1 (c1 ) 6+8 14f3 ( b2) = min d( b2,c2 ) + f1 (c2 ) = min 10+7 = min 17 = 14 d( b2,c3 ) + f1 (c3 ) 4+12 16 d( b3,c1 ) + f1 (c1 ) 13+8 21f3 ( b3) = min d( b3,c2 ) + f1 (c2 ) = min 12+7 = min 19 = 19 d( b3,c3 ) + f1 (c3 ) 11+12 23 第四階段（ a b ）： a 到b 有三條路線。f 4(a)1 = d(a, b1 ) f2 ( b1 ) 21921f 4 (a)2= d(a, b2 ) f2 ( b2 ) 51419f 4 (a)3= d(a, b3 )