運籌學II知識講解

1、運 籌 學 I I運籌學 （II）一、填空題1表 1 為用單純形法計算時某一步的表格，已知該線性規(guī)劃的目標函數(shù)為max z 5x1 3x2 ，約束形式為 ， x3，x4 為松弛變量，表中解代入目標函數(shù)后得 z10表1x1x2x3x4x3 2c011/5x1 ade01c j z jb-1fg1）a，b，c，d，e，f，g（ 2）表中給出的解為 （提示：最優(yōu)解，滿意解，可行解）。2影子價格是一種 ，它相當于在資源得到最優(yōu)利用的生產(chǎn)條件下， bi 每增加一個單位時目標函數(shù) z 的增量。3若原問題及其對偶問題均具有可行解，則兩者均具有 ，且它們最優(yōu)解的目標函數(shù)值 。4動態(tài)規(guī)劃中的狀態(tài)必須具備 。二、

2、判斷題1. 線性規(guī)劃問題的每一個基解對應可行域的一個頂點。（ ）2. 對偶問題的對偶問題一定是原問題。（ ）3. 表上作業(yè)法實質(zhì)上就是求解運輸問題的單純形法。（ ）4. 對一個動態(tài)規(guī)劃問題，應用順推法或逆推法可能會得到不同的最優(yōu)解。（5. 求圖的最小支撐樹以及求圖中一點至另一點的最短路問題，都可以歸結(jié)為求解整數(shù) 規(guī)劃問題。（ ）三、簡答題1. 簡述動態(tài)規(guī)劃方法的基本思想。答：動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會有許 多可行解。每一個解都對應于一個值，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治 法類似，其基本思想也是將待求解問題分解成若干個子問題，先求解子問題

3、，然后從這些子 問題的解得到原問題的解。與分治法不同的是，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到 子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數(shù)目太多，有 些子問題被重復計算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時再找 出已求得的答案，這樣就可以避免大量的重復計算，節(jié)省時間。我們可以用一個表來記錄所 有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入 表中。2. 簡述不確定型決策方法中的樂觀準則。答：也稱折衰決策法，決策者確定一個樂觀系數(shù)（ 0.5， 1），運用樂觀系數(shù)計算出各方 案的樂觀期望值，并選擇期望值最大的方案。四

4、、計算題1. 用圖解法求解下列線性規(guī)劃問題，并指出問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無 界解或無可行解。max z 4x1 8x22x1 2x2 10st. x1 x2 8x1, x2 02. 已知線性規(guī)劃問題：min z 2x1 x2 2x3x1x2x3 4st. x1x2kx3 6x10,x20,x3無約束（1）寫出其對偶問題，并求對偶問題的最優(yōu)解；（2）求 k 的值。3. 已知運輸問題的產(chǎn)銷地、產(chǎn)銷量及各產(chǎn)銷地間的單位運價如下表所示，試據(jù)此列出其數(shù)學模型。表2產(chǎn)地銷地甲乙丙產(chǎn)量11016321521422407322243416銷量128204. 用隱枚舉法求解下列 01規(guī)劃問題：mi

5、n z 2x1 5x2 3x3 4x44x1 x2 x3 x4 02x1 4x2 2x3 4x4 4 st.x1 x2 x3 x4 1xi 0或1 (i 1, ,4)5. 用匈牙利法求解下述指派問題，已知效率矩陣為：3 8 2 10 38729764275842359 10 6 9 10五、建模題某糖果廠用原料 A、B、C 加工成三種不同牌號的糖果甲、乙、丙。已知各種牌號糖果 中 A、B、C 的含量、原料成本、各種原料每月的限制用量，三種牌號糖果的單位加工費及 售價如表 3 所示：表3甲乙丙原料成本（元/kg）每月限制用量（kg）A60%15%2.002000B1.502500C20%60%50%1.001200加工費（元/kg）0.500.400.30售價（元/kg）3.402.852.25若該糖果廠建立生產(chǎn)計劃的目標優(yōu)先級為：p1