大學運籌學課程知識點總結(jié)

1、1 .用圖解法解決以下線性規(guī)劃問題，指出問題是否具有唯一的最優(yōu)解、無窮多的最優(yōu)解、沒有邊界解或沒有可行的解。2 .使下列線性規(guī)劃問題成為標準形式。(1)解：令3 .分別用圖解法解決以下線性規(guī)劃問題，對比地指出單純形表中的各化學基的可行解對應于圖解法中的可執(zhí)行區(qū)域的哪個頂點。解：圖解法：單純形法：將原來的問題標準化：日本電視臺10500q.q對應圖式化的點ps乙級聯(lián)賽乙級聯(lián)賽x1x2x3x40x3934103o點0x485201八月五日ps0105000x3五分之二十一0十四/五1三分之五三分之二c點10x1八月五日1五分之二0五分之一4ps-16010-25x2三分之二01五月十四日三分之十四

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

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

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

5、示這個資源在生產(chǎn)中被消耗著。影子的價格反映了簡單表中各檢驗數(shù)的經(jīng)濟意義。一般來說線性規(guī)劃問題的解決是確定資源的最佳分配方案，而對偶問題的解決是確定資源的恰當評價，這一評價關(guān)系到直接資源的最有效利用對偶簡單型法：確定標準化的線性規(guī)劃問題置換化學基變量，bi低于0中的最小列，求(cj-zj)/aij，求aij0，求最小值，對應的xi是置換化學基，如果所有的bi大于0，則找住的最佳解7下表顯示了各產(chǎn)地和各銷售地的產(chǎn)量和銷售量，以及從各產(chǎn)地到各銷售地的單位運輸價格，使用表作業(yè)法求出了最佳解?；旧险堊⒁猓赡艿慕獾臄?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 .下表列出了運輸問題及其解決辦法(1)表示的解是最佳解嗎？ 請用電位法驗證。(2)當價值系數(shù)c24從1變?yōu)?時，所給出的解還是最佳解？ 否則

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

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

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

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

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

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