運(yùn)籌學(xué)判斷題.課件

1、運(yùn)籌判斷復(fù)習(xí)第1頁，共17頁。判斷:線性規(guī)劃的每一個(gè)基解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)單純形法計(jì)算中，如不按最小比值原則選取換出變量，則在下一個(gè)解中至少有一個(gè)基變量的值為負(fù)單純形法的迭代計(jì)算是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一可行解線性規(guī)劃模型增加一個(gè)約束條件,可行域的范圍一般將縮小,減少一個(gè)約束條件,可行域一般將擴(kuò)大.第2頁，共17頁。若LP模型的可行域非空有界，則其頂點(diǎn)中必存在最優(yōu)解若可行域是空集，則表明存在矛盾的約束條件。用單純形法求LP問題，若最終表上非基變量的檢驗(yàn)數(shù)均為非正，則該模型一定有唯一最優(yōu)解。對(duì)于取值無約束的變量xj,通常令xj=xj-xj在用單純形法求得的最優(yōu)解中有可能出現(xiàn)xj0

2、,xj0第3頁，共17頁。凡具備優(yōu)化、限制、選擇條件且能將條件用關(guān)于決策變量的線性表達(dá)式表示出來的問題可以考慮用線性規(guī)劃模型處理用單純形法求解LP時(shí)，無論是極大化問題還是極小化問題，用來確定基變量的最小比值原則相同。若X是某LP的最優(yōu)解，則X必為該LP可行域的某一個(gè)頂點(diǎn)用單純形法求解LP問題，若最終表上非基變量的檢驗(yàn)數(shù)均嚴(yán)格小于零，則該模型一定有唯一的最優(yōu)解。單純形法通過最小比值法選取換出變量是為了保持解的可行性。第4頁，共17頁。對(duì)一個(gè)有n個(gè)變量m個(gè)約束的標(biāo)準(zhǔn)型的線性規(guī)劃問題，其可行域的頂點(diǎn)恰好為Cnm個(gè)。圖解法同單純形法雖然求解的形式不同，但從幾何上解釋，兩者是一致的。一旦一個(gè)人工變量在迭

3、代中變?yōu)榉腔兞亢?，該變量及相?yīng)列的數(shù)字可以從單純形表中刪除，而不影響計(jì)算結(jié)果。若X1，X2分別是某一線性規(guī)劃問題的最優(yōu)解，則 也是該線性規(guī)劃問題的最優(yōu)解，其中 為正的實(shí)數(shù)。第5頁，共17頁。判斷:任何線性規(guī)劃問題存在并具有唯一的對(duì)偶問題.已知y*i為線性規(guī)劃的對(duì)偶問題的最優(yōu)解,如果y*i=0,說明在最優(yōu)生產(chǎn)計(jì)劃中第i種資源一定有剩余.已知y*i為線性規(guī)劃的對(duì)偶問題的最優(yōu)解,如果y*i0,說明在最優(yōu)生產(chǎn)計(jì)劃中第i種資源已經(jīng)完全耗盡.第6頁，共17頁。判斷:若線性規(guī)劃的原問題有無窮多最優(yōu)解,則其對(duì)偶問題也一定具有無窮多解.根據(jù)對(duì)偶的性質(zhì),當(dāng)原問題無界解時(shí),其對(duì)偶問題無可行解,反之,當(dāng)對(duì)偶問題無可

4、行解,其原問題具有無界解.若線性規(guī)劃問題的原問題存在可行解，則對(duì)偶問題也一定存在可行解若線性規(guī)劃的原問題和其對(duì)偶問題都具有可行解，則該線性規(guī)劃問題一定具有有限最優(yōu)解.第7頁，共17頁。判斷:運(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求解結(jié)果也可能出現(xiàn)下列四種情況之一：有惟一最優(yōu)解，有無窮多最優(yōu)解，無界解，無可行解。表上作業(yè)法實(shí)質(zhì)上就是求解運(yùn)輸問題的單純形法。如果運(yùn)輸問題單位運(yùn)價(jià)表的某一行（或某一列）元素分別乘上一個(gè)常數(shù)K，最優(yōu)方案將不會(huì)發(fā)生變化。當(dāng)所有產(chǎn)地產(chǎn)量和銷地的銷量均為整數(shù)值時(shí),運(yùn)輸問題的最優(yōu)解也為整數(shù)值。第8頁，共17頁。判斷:在運(yùn)輸問題中,只要任意給出一組含(m+n-1)個(gè)非零xij的且

5、滿足 就可以作為一個(gè)初始基可行解.按最小元素法(或伏格爾法)給出的初始基可行解,從每一空格出發(fā)可以找出且能找出惟一的閉回路。如果運(yùn)輸問題單位運(yùn)價(jià)表的某一行（或某一列）元素分別加上一個(gè)常數(shù)K，最優(yōu)方案將不會(huì)發(fā)生變化。如果在運(yùn)輸問題或轉(zhuǎn)運(yùn)問題模型中,Cij都是從產(chǎn)地i到銷地j的最小運(yùn)輸費(fèi)用,則運(yùn)輸問題同轉(zhuǎn)運(yùn)問題將得到相同的最優(yōu)解第9頁，共17頁。判斷題:線性規(guī)劃問題是目標(biāo)規(guī)劃問題的一種特殊形式正偏差變量取正值，負(fù)偏差變量取負(fù)值；目標(biāo)規(guī)劃模型中，應(yīng)同時(shí)包含系統(tǒng)約束（絕對(duì)約束）與目標(biāo)約束；目標(biāo)規(guī)劃模型中存在的約束條件則該約束是系統(tǒng)約束。第10頁，共17頁。判斷:用分支定界法求一個(gè)極大化的整數(shù)規(guī)劃時(shí),任

6、何一個(gè)可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界.用分支定界法求一個(gè)極大化的整數(shù)規(guī)劃時(shí),當(dāng)?shù)玫蕉嘤谝粋€(gè)可行解時(shí),通常可以任取一個(gè)作為下界值,再進(jìn)行比較和剪枝.用割平面求純整數(shù)規(guī)劃時(shí),要求包括松弛變量在內(nèi)的全部變量必須取整數(shù).用割平面求整數(shù)規(guī)劃時(shí),構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)解。第11頁，共17頁。判斷：整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問題的解的目標(biāo)函數(shù)值。指派問題數(shù)學(xué)模型的形式同運(yùn)輸問題十分相似，故也可以用表上作業(yè)法求解。分枝定界法在需要分枝時(shí)必須滿足：一是分枝后的各子問題必須容易求解；二是各子問題解的集合必須覆蓋原問題的解。0-1規(guī)劃的隱枚舉法是分枝定界的特例。

7、第12頁，共17頁。判斷題1.動(dòng)態(tài)規(guī)劃模型中,問題的階段數(shù)目等于問題中子問題的數(shù)目;2.動(dòng)態(tài)規(guī)劃中,定義狀態(tài)時(shí)應(yīng)保證在各個(gè)階段中所做決策的相互獨(dú)立性;3.動(dòng)態(tài)規(guī)劃的最優(yōu)性原理保證了從某一狀態(tài)開始的未來決策獨(dú)立于先前已作出的決策;4.對(duì)于一個(gè)動(dòng)態(tài)規(guī)劃問題,應(yīng)用順推或逆推解法可能會(huì)得到不同的結(jié)果；5.假如一個(gè)線性規(guī)劃問題含有5個(gè)變量和3個(gè)約束條件，則用動(dòng)態(tài)規(guī)劃求解時(shí)將劃分為3個(gè)階段，每個(gè)階段的狀態(tài)將由一個(gè)五維的向量組成；6.動(dòng)態(tài)規(guī)劃問題的基本方程是將一個(gè)多階段的決策問題轉(zhuǎn)化為一系列具有遞推關(guān)系的單階段的決策問題。第13頁，共17頁。判斷題:圖論中的圖不僅反映了研究對(duì)象之間的關(guān)系，而且是真實(shí)圖形的寫照，以因而對(duì)圖中點(diǎn)與點(diǎn)的相對(duì)位置、點(diǎn)與點(diǎn)連線的長(zhǎng)短曲直等都要嚴(yán)格注意。在任一圖G中，當(dāng)點(diǎn)集V確定后，樹圖是G中邊數(shù)最少的連通圖。連通圖G的支撐樹是取圖G的點(diǎn)和G的所有邊組成的樹。第14頁，共17頁。Dijkstra算法要求邊的長(zhǎng)度非負(fù)。最小割集等于最大流。求最小樹可用破圈法。在最短路問題中，發(fā)點(diǎn)到收點(diǎn)的最短路長(zhǎng)是唯一的。最大流問題是找從發(fā)點(diǎn)到收點(diǎn)的路，使得通過這條路的流量最大。容量Cij是弧(i,j)的實(shí)際通過量?？尚辛魇亲畲罅鞯某湟獥l件是不存在發(fā)點(diǎn)到收點(diǎn)的增廣鏈。第15頁，