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

1、1 .用圖解法解決以下線性規(guī)劃問題，指出問題是否具有唯一的最優(yōu)解、無窮多的最優(yōu)解、沒有邊界解或沒有可行的解。2 .使下列線性規(guī)劃問題成為標(biāo)準(zhǔn)形式。(1)解：令3 .分別用圖解法解決以下線性規(guī)劃問題，對(duì)比地指出單純形表中的各化學(xué)基的可行解對(duì)應(yīng)于圖解法中的可執(zhí)行區(qū)域的哪個(gè)頂點(diǎn)。解：圖解法：?jiǎn)渭冃畏ǎ簩⒃瓉淼膯栴}標(biāo)準(zhǔn)化：日本電視臺(tái)10500q.q對(duì)應(yīng)圖式化的點(diǎn)ps乙級(jí)聯(lián)賽乙級(jí)聯(lián)賽x1x2x3x40x3934103o點(diǎn)0x485201八月五日ps0105000x3五分之二十一0十四/五1三分之五三分之二c點(diǎn)10x1八月五日1五分之二0五分之一4ps-16010-25x2三分之二01五月十四日三分之十四

2、b點(diǎn)10x1110七分之一七分之二ps三十五之二00五月十四日二十五/十四最佳解是(1，3/2，0，0 )，最佳值z(mì)=35/2。簡(jiǎn)單型法程序：找到可轉(zhuǎn)換為標(biāo)準(zhǔn)線性規(guī)劃問題的初始可能解，列出初始簡(jiǎn)單的表。最優(yōu)性檢查求cj-zj，如果所有值都小于0，則表中的解為最優(yōu)解，否則，找到最大值的列，求bi/aij，最小4 .寫出下列線性規(guī)劃問題的對(duì)偶問題。(1)(2)5 .提出線性規(guī)劃問題要求： (1)寫對(duì)偶問題(2)已知元問題的最佳解是，根據(jù)對(duì)偶理論直接求對(duì)偶問題的最佳解。解：(1)(2)第四個(gè)約束取等號(hào)，根據(jù)互補(bǔ)弛豫定理求對(duì)偶問題的最佳解是：最佳值min w=16。弱對(duì)偶性推理：(1)原問題的任意可行

3、解的目標(biāo)函數(shù)值是對(duì)偶問題的目標(biāo)函數(shù)值的下限，相反，對(duì)偶問題的任一可行解的目標(biāo)函數(shù)值是其原問題的目標(biāo)函數(shù)值的上限(2)原問題有可能解，且目標(biāo)函數(shù)值沒有界限(沒有界限解)時(shí)，其對(duì)偶問題沒有可能解，相反對(duì)偶問題有可能解，目標(biāo)函數(shù)值沒有界限時(shí)，其原問題沒有可能解。注意：這一點(diǎn)的性質(zhì)的反向不成立，當(dāng)對(duì)偶問題沒有可行的解時(shí)，其原問題或者沒有可行的解時(shí)，反向也是如此。(3)如果原問題有可執(zhí)行的解，對(duì)偶問題沒有可執(zhí)行的解，則原問題的目標(biāo)函數(shù)值是無限的，相反對(duì)偶問題有可執(zhí)行的解，如果原問題沒有可執(zhí)行的解，則對(duì)偶問題的目標(biāo)函數(shù)值是無限的。強(qiáng)對(duì)偶性(或?qū)ε级ɡ?如果有原問題和對(duì)偶問題可能的解，兩者就有最佳解，這些最

4、佳解的目標(biāo)函數(shù)值相等?；パa(bǔ)弛豫性在線性規(guī)劃問題的最優(yōu)解中，如果某個(gè)約束條件所對(duì)應(yīng)的對(duì)偶變量值不為零，則約束條件取嚴(yán)格方程，反之，如果約束條件取嚴(yán)格不等式，則對(duì)應(yīng)的對(duì)偶變量必定為零。影子價(jià)格資源市場(chǎng)價(jià)格是其價(jià)值的客觀表現(xiàn)，比較穩(wěn)定，但其影響價(jià)格依賴資本資源的利用狀況是未知數(shù)。 企業(yè)的生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況發(fā)生了變化，造成了資源的影響花子的價(jià)格也會(huì)變。影子的價(jià)格是邊際價(jià)格。資源的陰影價(jià)格實(shí)際上也是機(jī)會(huì)的成本。 隨著資源的購買，影子的價(jià)格也隨之上漲與此同時(shí)，影子的價(jià)格達(dá)到和市場(chǎng)價(jià)格同等水平之前，是平衡的。當(dāng)生產(chǎn)過程中的資源未被一盞茶利用時(shí)，該資源的影子價(jià)格為零或成為資源影子的價(jià)格不為零的情況下，表

5、示這個(gè)資源在生產(chǎn)中被消耗著。影子的價(jià)格反映了簡(jiǎn)單表中各檢驗(yàn)數(shù)的經(jīng)濟(jì)意義。一般來說線性規(guī)劃問題的解決是確定資源的最佳分配方案，而對(duì)偶問題的解決是確定資源的恰當(dāng)評(píng)價(jià)，這一評(píng)價(jià)關(guān)系到直接資源的最有效利用對(duì)偶簡(jiǎn)單型法：確定標(biāo)準(zhǔn)化的線性規(guī)劃問題置換化學(xué)基變量，bi低于0中的最小列，求(cj-zj)/aij，求aij0，求最小值，對(duì)應(yīng)的xi是置換化學(xué)基，如果所有的bi大于0，則找住的最佳解7下表顯示了各產(chǎn)地和各銷售地的產(chǎn)量和銷售量，以及從各產(chǎn)地到各銷售地的單位運(yùn)輸價(jià)格，使用表作業(yè)法求出了最佳解。基本上請(qǐng)注意，可能的解的數(shù)量一定要從矩陣變量的數(shù)量中減去1銷售地產(chǎn)地b1b2b3b4產(chǎn)量a141468a2125

6、08a3.a337514銷售額。656320解：(一)決定初步方案；西北角法：銷售地產(chǎn)地b1b2b3b4產(chǎn)量a1628a2358a3.a3134銷售額。656320尺最小元素：銷售地產(chǎn)地b1b2b3b4產(chǎn)量a1538a2538a3.a3134銷售額。656320沃格爾法：銷售地產(chǎn)地b1b2b3b4產(chǎn)量處罰數(shù)12342125081162a3.a337514124431銷售額。656320列給予懲罰數(shù)數(shù)兒12111211311418 .下表列出了運(yùn)輸問題及其解決辦法(1)表示的解是最佳解嗎？ 請(qǐng)用電位法驗(yàn)證。(2)當(dāng)價(jià)值系數(shù)c24從1變?yōu)?時(shí)，所給出的解還是最佳解？ 否則

7、，求最佳解。(3)所有價(jià)值系數(shù)增加1，最佳解會(huì)變化嗎？ 為什么？(4)所有價(jià)值系數(shù)乘以2，最佳解會(huì)變化嗎？ 為什么？銷售地產(chǎn)地b1b2b3b4產(chǎn)量a14146853a212611082a3.a33751431銷售額。856322解： (1)銷售地產(chǎn)地b1b2b3b4產(chǎn)量psa141468053a2126110182a3.a337514131銷售額。856322日本電視臺(tái)0140空間檢查的數(shù)量如下460125所有檢驗(yàn)數(shù)均為零以上，該方案為最佳方案。(2)當(dāng)價(jià)值系數(shù)c24從1變?yōu)?時(shí)66-2-145因?yàn)闄z查數(shù)不到零，所以這個(gè)方案不是最合適的方案。五(-2 )三(二)8(2)二(-2 )3(-2 )

8、一(二)調(diào)整位置：358213空間檢查的數(shù)量如下461225所有檢驗(yàn)數(shù)均在零以下，該方案為最佳方案。的雙曲正切值。(3)不變更，不影響檢查數(shù)的大小。(4)不變更、不影響檢查數(shù)的符號(hào)。解的最優(yōu)性檢驗(yàn)：1 .閉合回路法：尋找各個(gè)非基本變量的閉合回路，依次加減檢查數(shù)進(jìn)行加法運(yùn)算，如果所有檢查數(shù)的值都不是負(fù)的話，這個(gè)可能的解就是最佳解。2 .電勢(shì)法(對(duì)偶變量法):計(jì)算增加勢(shì)列ui和勢(shì)行vj的電勢(shì)，ui vj=指定基本可行解的對(duì)應(yīng)運(yùn)費(fèi)，其中一個(gè)值為0，計(jì)算其他數(shù)名的值，計(jì)算記入表的檢驗(yàn)數(shù)，計(jì)算與某個(gè)非基本變量對(duì)應(yīng)的運(yùn)費(fèi)(檢查數(shù)全部是經(jīng)過非基底變量處理的值，在處理過程中應(yīng)用基底變量)解的改良：1.將檢測(cè)常

9、數(shù)小于0的xi作為置換化學(xué)基(取最小的)2 .找到該xi的閉合回路，以xi為首逆時(shí)針方向?qū)Χc(diǎn)進(jìn)行編號(hào)3 .在所有的雙位數(shù)頂點(diǎn)中，將運(yùn)輸量最少的頂點(diǎn)作為xi的變換變量找到4 .基數(shù)頂點(diǎn)的運(yùn)輸量減少xj，雙位數(shù)頂點(diǎn)的運(yùn)輸量減少xj，新獲得方案5 .進(jìn)行解的最優(yōu)性檢查9 .公司決定用1000萬元的全新產(chǎn)品發(fā)展基金開發(fā)a、b、c三種全新產(chǎn)品。 據(jù)預(yù)測(cè)，開發(fā)a、b、c三種全新產(chǎn)品的投資利潤(rùn)分別為5%、7%、10%。 由于全新產(chǎn)品研發(fā)存在一定的風(fēng)險(xiǎn)，公司經(jīng)過研究，決定了下一個(gè)優(yōu)先順序目標(biāo)第一，a產(chǎn)品至少投資300萬元其次，為了分散投資風(fēng)險(xiǎn)，任何全新產(chǎn)品的發(fā)展投資都不超過發(fā)展基金總額的35%。第三，應(yīng)至少

10、留下10%的開發(fā)基金，以備急用第四，最大化總投資利潤(rùn)。正在建構(gòu)投資分配方案的目標(biāo)計(jì)劃模型。解、a、b、c三種全新產(chǎn)品的研發(fā)投資額分別為萬元，目標(biāo)規(guī)劃模式如下：pl是優(yōu)先級(jí)因子，關(guān)系l越小越具有絕對(duì)優(yōu)先級(jí)，另一個(gè)是相對(duì)優(yōu)先級(jí)，用加權(quán)系數(shù)表示目標(biāo)規(guī)劃的一般形式minpld或d- (為什么d或d-，min的d為零，即不等式大于零時(shí)為d-)； 應(yīng)該滿足的絕對(duì)制約和目標(biāo)制約xj0，d，d-0目標(biāo)規(guī)劃的圖解法：首先繪制絕對(duì)約束的可能結(jié)構(gòu)域，根據(jù)優(yōu)先級(jí)優(yōu)先考慮某個(gè)目標(biāo)約束，在min系數(shù)中隨著d或d-的增大曲線移動(dòng)，直到最后繪制最佳10 .用切平面法求解下列整數(shù)規(guī)劃(1)解：引入松弛變量，使問題成為標(biāo)準(zhǔn)形式，

11、用簡(jiǎn)單形式解決松弛問題。ps1100q.qps西班牙乙級(jí)聯(lián)賽x1x2x3x40x36【2】11030x42045015ps11001x131二分之一二分之一060x480【3】-21八分之三ps0二分之一二分之一01x1五分之三10五分之六六分之一1x2八分之三01二分之三三分之一ps00六分之一六分之一在非整數(shù)解變量中，分?jǐn)?shù)部分找到最大的基變量(x2)，并描述此行的約束請(qǐng)將上式中的所有常數(shù)分成整數(shù)和正分?jǐn)?shù)之和如果將公式中的分?jǐn)?shù)項(xiàng)移動(dòng)到公式的右端，將整數(shù)項(xiàng)移動(dòng)到公式的左端，則切削平面約束如下引入松弛變量后，剖切平面方程如下：ps11000ps西班牙乙級(jí)聯(lián)賽x1x2x3x4x51x1五分之三10

12、五分之六六分之一01x2八分之三01二分之三三分之一00x5二分之三00(-1/3 )三分之一1ps00六分之一六分之一0日本航空二分之一二分之一1x10100-1五分之二1x240101-20x320011-3ps0000二分之一最佳解是，最佳值是s4=0，最優(yōu)解不獨(dú)特嗎？11 .用分支定界法求解以下整數(shù)規(guī)劃：(1)解：最佳解(3，1 )，最佳值z(mì)=7。12 .匈牙利解法：見教科書第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最大短路長(zhǎng)度為19。 最短路的是0129，0329，0349，01249，0779。如圖14 .該圖所示，起點(diǎn)可分別提供10和15個(gè)單位，收獲點(diǎn)能夠接收10和25個(gè)單位并且能夠