大學(xué)運(yùn)籌學(xué)課程知識(shí)點(diǎn)總結(jié)

1、1. 用圖解法求解下列線性規(guī)劃問(wèn)題，并指出問(wèn)題具有惟一最優(yōu)解、無(wú)窮多最優(yōu)解、無(wú)界解還是無(wú)可行解。 2.將下述線性規(guī)劃問(wèn)題化成標(biāo)準(zhǔn)形式。 （1） 解：令， 3.分別用圖解法和單純形法求解下述線性規(guī)劃問(wèn)題，并對(duì)照指出單純形表中的各基可行解對(duì)應(yīng)圖解法中的可行域的哪個(gè)頂點(diǎn)。 解：圖解法：?jiǎn)渭冃畏ǎ簩⒃瓎?wèn)題標(biāo)準(zhǔn)化：Cj10500q對(duì)應(yīng)圖解法中的點(diǎn)CBBbx1x2x3x40x3934103O點(diǎn)0x4852018/5sj0105000x321/5014/51-3/53/2C點(diǎn)10x18/512/501/54sj-16010-25x23/2015/14-3/14B點(diǎn)10x1110-1/72/7sj35/200

2、-5/14-25/14最優(yōu)解為（1,3/2,0,0），最優(yōu)值Z=35/2。單純型法步驟：轉(zhuǎn)化為標(biāo)準(zhǔn)線性規(guī)劃問(wèn)題；找到一個(gè)初始可行解，列出初始單純型表；最優(yōu)性檢驗(yàn)，求cj-zj，若所有的值都小于0，則表中的解便是最優(yōu)解，否則，找出最大的值的那一列，求出bi/aij，選取最小的相對(duì)應(yīng)的xij，作為換入基進(jìn)行初等行變換，重復(fù)此步驟。 4.寫(xiě)出下列線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。（1）（2）5. 給出線性規(guī)劃問(wèn)題要求：（1）寫(xiě)出其對(duì)偶問(wèn)題；（2）已知原問(wèn)題最優(yōu)解為，試根據(jù)對(duì)偶理論，直接求出對(duì)偶問(wèn)題的最優(yōu)解。解：（1）（2）因?yàn)?，第四個(gè)約束取等號(hào)，根據(jù)互補(bǔ)松弛定理得：求得對(duì)偶問(wèn)題的最優(yōu)解為：，最優(yōu)值min w=

3、16。弱對(duì)偶性的推論：(1) 原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界(2) 如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界(具有無(wú)界解)，則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其原問(wèn)題無(wú)可行解。注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題或具有無(wú)界解或無(wú)可行解，反之亦然。(3) 若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界；反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。強(qiáng)對(duì)偶性(或稱對(duì)偶定理) 若原問(wèn)題及其對(duì)偶問(wèn)題均具有可行解，則兩者均具有最優(yōu)解，且它們最

4、優(yōu)解的目標(biāo)函數(shù)值相等。互補(bǔ)松弛性在線性規(guī)劃問(wèn)題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。影子價(jià)格資源的市場(chǎng)價(jià)格是其價(jià)值的客觀體現(xiàn)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影子價(jià)格也隨之改變。影子價(jià)格是一種邊際價(jià)格。資源的影子價(jià)格實(shí)際上又是一種機(jī)會(huì)成本。隨著資源的買(mǎi)進(jìn)賣(mài)出，其影子價(jià)格也將隨之發(fā)生變化，一直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí)，才處于平衡狀態(tài)。生產(chǎn)過(guò)程中如果某種資源未得到充分利用時(shí)，該種資源的影子價(jià)格為零；又當(dāng)資源的影子價(jià)格不

5、為零時(shí)，表明該種資源在生產(chǎn)中已耗費(fèi)完畢。影子價(jià)格反映單純形表中各個(gè)檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。一般說(shuō)對(duì)線性規(guī)劃問(wèn)題的求解是確定資源的最優(yōu)分配方案，而對(duì)于對(duì)偶問(wèn)題的求解則是確定對(duì)資源的恰當(dāng)估價(jià)，這種估價(jià)直接涉及資源的最有效利用對(duì)偶單純型法：轉(zhuǎn)化成標(biāo)準(zhǔn)的線性規(guī)劃問(wèn)題；確定換入基變量，bi小于0中的最小的那一排，再求（cj-zj）/aij，且aij0,d+,d-0目標(biāo)規(guī)劃的圖解法：先畫(huà)絕對(duì)約束的可行域，然后按照優(yōu)先性優(yōu)先考慮某個(gè)目標(biāo)約束，隨著min系數(shù)中d+或者d-的增大移動(dòng)曲線，畫(huà)出最合適的那條，直到最后10.用割平面法解下列整數(shù)規(guī)劃：（1）解：引進(jìn)松弛變量，將問(wèn)題化為標(biāo)準(zhǔn)形式，用單純形法解其松弛問(wèn)題。cj

6、1100qCBXBbx1x2x3x40x36【2】11030x42045015sj11001x1311/21/2060x480【3】-218/3sj01/2-1/201x15/3105/6-1/61x28/301-2/31/3sj00-1/6-1/6找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個(gè)基變量（x2），并寫(xiě)下這一行的約束：將上式中的所有常數(shù)分寫(xiě)成整數(shù)與一個(gè)正的分?jǐn)?shù)值之和得：將上式中的分?jǐn)?shù)項(xiàng)移到等式右端，整數(shù)項(xiàng)移到等式左端得：得到割平面約束為：引入松弛變量，得割平面方程為：cj11000CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/300x5-2/300

7、【-1/3】-1/31sj00-1/6-1/60sj/arj1/21/21x10100-15/21x240101-20x320011-3sj0000-1/2最優(yōu)解為，最優(yōu)值為s4=0，最優(yōu)解不唯一？11.用分支定界法解下列整數(shù)規(guī)劃（1）解：最優(yōu)解（3,1），最優(yōu)值z(mì)=7。12. 匈牙利解法：見(jiàn)課本145頁(yè)13.如圖，是一倉(cāng)庫(kù)，是商店，求一條從到的最短路。解：P=T=0T=T=T=T=T=T=T=T=T=P=T=2T=T=11T=T=7T=T=4T=T=T=13T=11T=T=7T=P=T=4T=T=T=13T=11T=P=T=7T=11T=13T=T=13P=T=11T=T=11T=13T=T=13T=16P=T=11T=13T=P=T=13T=16T=13T=20T=16P=T=13T=19P=T=16T=19P=19最短路長(zhǎng)為19。最短路為：0129，0329，0349，01249，0789。14.如圖，發(fā)點(diǎn)，分別可供應(yīng)10和15個(gè)單位，收點(diǎn)，可以接收10和25個(gè)單位，求最大流，邊上數(shù)為。最大流為2115.如圖所示網(wǎng)絡(luò)中，有向邊旁數(shù)字為，表示容量，表示單位流量費(fèi)用，試求到流值為六的最小費(fèi)用流。解：d(f)=3716.