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

可編輯版/用圖解法求解下列線性規(guī)劃問題,并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是無可行解。2.將下述線性規(guī)劃問題化成標(biāo)準(zhǔn)形式?！?解：令,3.分別用圖解法和單純形法求解下述線性規(guī)劃問題,并對照指出單純形表中的各基可行解對應(yīng)圖解法中的可行域的哪個頂點(diǎn)。解：=1\*GB3①圖解法：=2\*GB3②單純形法：將原問題標(biāo)準(zhǔn)化：Cj10500對應(yīng)圖解法中的點(diǎn)CBBbx1x2x3x40x3934103O點(diǎn)0x48[5]2018/5j0105000x321/50[14/5]1-3/53/2C點(diǎn)10x18/512/501/54j-16010-25x23/2015/14-3/14B點(diǎn)10x1110-1/72/7j35/200-5/14-25/14最優(yōu)解為〔1,3/2,0,0,最優(yōu)值Z=35/2。單純型法步驟：轉(zhuǎn)化為標(biāo)準(zhǔn)線性規(guī)劃問題；找到一個初始可行解,列出初始單純型表；最優(yōu)性檢驗(yàn),求cj-zj,若所有的值都小于0,則表中的解便是最優(yōu)解,否則,找出最大的值的那一列,求出bi/aij,選取最小的相對應(yīng)的xij,作為換入基進(jìn)行初等行變換,重復(fù)此步驟。4.寫出下列線性規(guī)劃問題的對偶問題?！?〔25.給出線性規(guī)劃問題要求：〔1寫出其對偶問題；〔2已知原問題最優(yōu)解為,試根據(jù)對偶理論,直接求出對偶問題的最優(yōu)解。解：〔1〔2因?yàn)?第四個約束取等號,根據(jù)互補(bǔ)松弛定理得：求得對偶問題的最優(yōu)解為：,最優(yōu)值minw=16。弱對偶性的推論：<1>原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界<2>如原問題有可行解且目標(biāo)函數(shù)值無界<具有無界解>,則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)值無界,則其原問題無可行解。注意：本點(diǎn)性質(zhì)的逆不成立,當(dāng)對偶問題無可行解時,其原問題或具有無界解或無可行解,反之亦然。<3>若原問題有可行解而其對偶問題無可行解,則原問題目標(biāo)函數(shù)值無界；反之對偶問題有可行解而其原問題無可行解,則對偶問題的目標(biāo)函數(shù)值無界。強(qiáng)對偶性<或稱對偶定理>若原問題及其對偶問題均具有可行解,則兩者均具有最優(yōu)解,且它們最優(yōu)解的目標(biāo)函數(shù)值相等。互補(bǔ)松弛性在線性規(guī)劃問題的最優(yōu)解中,如果對應(yīng)某一約束條件的對偶變量值為非零,則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式,則其對應(yīng)的對偶變量一定為零。影子價格資源的市場價格是其價值的客觀體現(xiàn),相對比較穩(wěn)定,而它的影子價格則有賴于資源的利用情況,是未知數(shù)。因企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化,資源的影子價格也隨之改變。影子價格是一種邊際價格。資源的影子價格實(shí)際上又是一種機(jī)會成本。隨著資源的買進(jìn)賣出,其影子價格也將隨之發(fā)生變化,一直到影子價格與市場價格保持同等水平時,才處于平衡狀態(tài)。生產(chǎn)過程中如果某種資源未得到充分利用時,該種資源的影子價格為零；又當(dāng)資源的影子價格不為零時,表明該種資源在生產(chǎn)中已耗費(fèi)完畢。影子價格反映單純形表中各個檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案,而對于對偶問題的求解則是確定對資源的恰當(dāng)估價,這種估價直接涉及資源的最有效利用對偶單純型法：轉(zhuǎn)化成標(biāo)準(zhǔn)的線性規(guī)劃問題；確定換入基變量,bi小于0中的最小的那一排,再求〔cj-zj/aij,且aij<0,找出最小值,這對應(yīng)的xi便是換入基,若所有的bi都大于0,則找到了最優(yōu)解7下列表分別給出了各產(chǎn)地和各銷地的產(chǎn)量和銷量,以及各產(chǎn)地至各銷地的單位運(yùn)價,試用表上作業(yè)法求最優(yōu)解。注意要基可行解的個數(shù)一定是行列變量數(shù)減一銷地產(chǎn)地B1B2B3B4產(chǎn)量A141468A212508A337514銷量656320解：〔1確定初始方案西北角法：銷地產(chǎn)地B1B2B3B4產(chǎn)量A1628A2358A3134銷量656320最小元素法：銷地產(chǎn)地B1B2B3B4產(chǎn)量A1538A2538A3134銷量656320沃格爾法：銷地產(chǎn)地B1B2B3B4產(chǎn)量行罰數(shù)1234A141468eq\o\ac<○,3>02253A21250811eq\o\ac<○,5>62A337514124431銷量656320列罰數(shù)121112eq\o\ac<○,2>1131141eq\o\ac<○,5>8.下表給出一個運(yùn)輸問題及它的一個解,試問：〔1表中給出的解是否為最優(yōu)解？請用位勢法進(jìn)行檢驗(yàn)?！?若價值系數(shù)C24由1變?yōu)?,所給的解是否仍為最優(yōu)解？若不是,請求出最優(yōu)解?！?若所有價值系數(shù)均增加1,最優(yōu)解是否改變？為什么？〔4若所有價值系數(shù)均乘以2,最優(yōu)解是否改變？為什么？銷地產(chǎn)地B1B2B3B4產(chǎn)量A14146853A212611082A33751431銷量856322解：〔1銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA141468053A2126110182A337514131銷量856322vj0140空格檢驗(yàn)數(shù)為：460125所有檢驗(yàn)數(shù)均大于等于零,該方案為最優(yōu)方案。〔2若價值系數(shù)C24由1變?yōu)?,66-2-145由于有檢驗(yàn)數(shù)小于零,所以此方案不是最優(yōu)方案。5〔-23〔+28〔+22〔-23〔-21〔+2調(diào)整為：358213空格檢驗(yàn)數(shù)為：461225所有檢驗(yàn)數(shù)均小于等于零,該方案為最優(yōu)方案。。〔3不改變,不影響檢驗(yàn)數(shù)的大小。〔4不改變,不影響檢驗(yàn)數(shù)的符號。解的最優(yōu)性檢驗(yàn)：1.閉回路法：找各個非基變量的閉合回路,依次加減求檢驗(yàn)數(shù),是先減再加,若所有的檢驗(yàn)數(shù)的值都全非負(fù),那么此可行解是最優(yōu)解。2.位勢法〔對偶變量法：增加位勢列ui和位勢行vj；計算位勢,ui+vj=基可行解的對應(yīng)的運(yùn)費(fèi),指定其中某一值為0,算出其他幾位的值,填入表中；計算檢驗(yàn)數(shù),某非基變量對應(yīng)的運(yùn)費(fèi)減對應(yīng)的位勢行和位勢列,若檢驗(yàn)數(shù)全為非負(fù),則為最優(yōu)解?！矙z驗(yàn)數(shù)都是非基變量經(jīng)過處理后的值,處理過程中應(yīng)用的是基變量解的改進(jìn)：1.以檢驗(yàn)數(shù)小于0的xi為換入基〔取最小的那個找此xi的閉合回路,以xi為始沿順逆時針方向把定點(diǎn)依次編號在所有偶數(shù)頂點(diǎn)中,找出運(yùn)輸量最少的頂點(diǎn)作為xi的換出變量將基數(shù)頂點(diǎn)的運(yùn)輸量增加xj,偶數(shù)頂點(diǎn)的運(yùn)輸量減少xj,重新得到一組新的方案進(jìn)行解的最優(yōu)性檢驗(yàn)9.公司決定使用1000萬元新產(chǎn)品開發(fā)基金開發(fā)A,B,C三種新產(chǎn)品。經(jīng)預(yù)測估計,開發(fā)A,B,C三種新產(chǎn)品的投資利潤分別為5%、7%、10%。由于新產(chǎn)品開發(fā)有一定風(fēng)險,公司研究后確定了下列優(yōu)先順序目標(biāo)：第一,A產(chǎn)品至少投資300萬元；第二,為分散投資風(fēng)險,任何一種新產(chǎn)品的開發(fā)投資不超過開發(fā)基金總額的35%；第三,應(yīng)至少留有10%的開發(fā)基金,以備急用；第四,使總的投資利潤最大。試建立投資分配方案的目標(biāo)規(guī)劃模型。解,設(shè)A,B,C三種新產(chǎn)品的開發(fā)投資額分別為萬元,目標(biāo)規(guī)劃模型為：Pl是優(yōu)先因子,關(guān)系為l越小,則有絕對的優(yōu)先性,還有一種是相對的優(yōu)先性,用權(quán)系數(shù)來表示目標(biāo)規(guī)劃的一般格式;min{pld+或d-}〔要明白為什么是寫d+或d-,min里的d是要取值為零的,即若不等式要大于零時,則寫d-；必須要滿足的絕對約束,還有目標(biāo)約束；xj>0,d+,d->0目標(biāo)規(guī)劃的圖解法：先畫絕對約束的可行域,然后按照優(yōu)先性優(yōu)先考慮某個目標(biāo)約束,隨著min系數(shù)中d+或者d-的增大移動曲線,畫出最合適的那條,直到最后10.用割平面法解下列整數(shù)規(guī)劃：〔1解：引進(jìn)松弛變量,將問題化為標(biāo)準(zhǔn)形式,用單純形法解其松弛問題。cj1100CBXBbx1x2x3x40x36[2]11030x42045015j11001x1311/21/2060x480[3]-218/3j01/2-1/201x15/3105/6-1/61x28/301-2/31/3j00-1/6-1/6找出非整數(shù)解變量中分?jǐn)?shù)部分最大的一個基變量〔x2,并寫下這一行的約束：將上式中的所有常數(shù)分寫成整數(shù)與一個正的分?jǐn)?shù)值之和得：將上式中的分?jǐn)?shù)項移到等式右端,整數(shù)項移到等式左端得：得到割平面約束為：引入松弛變量,得割平面方程為：cj11000CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/300x5-2/300[-1/3]-1/31j00-1/6-1/60j/arj1/21/21x10100-15/21x240101-20x320011-3j0000-1/2最優(yōu)解為,最優(yōu)值為4=0,最優(yōu)解不唯一？11.用分支定界法解下列整數(shù)規(guī)劃〔1解：最優(yōu)解〔3,1,最優(yōu)值z=7。匈牙利解法：見課本145頁13.如圖,是一倉庫,是商店,求一條從到的最短路。解：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最短路長為19。最短路為：0129,0329,0349,01249,0789。14.如圖,發(fā)點(diǎn),分別可供應(yīng)10和15個單位,收點(diǎn),可以接收10和25個單位,求