運籌學(xué)——對偶問題-文庫吧資料
2025-08-07 15:22本頁面
【正文】 ???????????????????1311341313131341b33b9bbB???????0303131134bb解：設(shè) b變?yōu)?(b1,9)T 若 B－ 1b≥0則 解得 9/4≤b1≤9 第四節(jié) 靈敏度分析 增加一個變量 若企業(yè)在計劃期內(nèi)，有新的產(chǎn)品可以生產(chǎn)，則在知道新產(chǎn)品的單位利潤 Cn+1，消耗量 Pn+1=(a1n+1,a2n+1,… ,amn+1)T時，可以在最優(yōu)表中補充一列，其中前 m行可以由 B－ 1Pn+1得到，而檢驗數(shù)行可以由δn+1=+1CBB1Pn+1計算得到。最優(yōu)解為 X＊ =(B1b,0)；否則，若 bi的變化使 B1b中某些分量小于 0，則目前基成了不可行基。 第四節(jié) 靈敏度分析 右端資源常數(shù) b發(fā)生改變 當(dāng) b中某個分量 bi發(fā)生改變時，將影響所在基變量的取值 XB=B1b。 2 3 3 0 0 x1 x2 x3 x4 x5 1 0 1 4/3 1/3 0 1 2 1/3 1/3 1 2 x1 x2 2 3 0 0 1 5/3 1/3 CB XB b δj(cjzj) 例：對于下例問題，討論 c3范圍 第四節(jié) 靈敏度分析 價值系數(shù) C發(fā)生改變 CB中某個 Ci發(fā)生變化時，則會影響所有非基變量的檢驗數(shù)，且 δN＝cNCBB1N，若 ci的變化滿足 δN≤0，則目前解還是最優(yōu)；否則就不是最優(yōu)，繼續(xù)單純形迭代就可以求得新的最優(yōu)解。 第二類： 為保持目前最優(yōu)基還是最優(yōu)，系數(shù) A、 b、 C的允許變化范圍是什么。?????????????????0x,x,x,x3x 4xx2 x xxs t .9x3xM in W43214213212139。 對偶單純形法思路： 先找到一個對偶可行基，然后保持基的對偶可行性，逐步迭代直至最終達(dá)到基的可行性。 最優(yōu)基： 當(dāng)基 B對應(yīng)的基本可行解是最優(yōu)解時，稱基 B為最優(yōu)基。 ?若生產(chǎn)過程中某種資源未得到充分利用 ,則該種資源的影子價格為零；又當(dāng)某種資源的影子價格不為零時，表明該種資源在生產(chǎn)過程中已耗費完畢。 yi的值相當(dāng)于在給定的生產(chǎn)條件下， bi每增加一個單位時目標(biāo)函數(shù) Z的增量。W*=5 ??????????????????????????0x,x,xbxaxaxabxaxaxabxaxaxas t .xcxcxcM a x Zn21mnmn2m21m12n2n2221211n1n212111nn2211??????? ??????????????????????????0y,y,ycyayayacyayayacyayayas t .ybybybM i n Wm21nmmn22n11n2mm22221121mm1221111mm2211??????? 原問題 對偶問題 ??????????????),2,1( 0),2,1( bas t .M a x Zi1ij1njxmixxcjnjjnjjj????????????????),2,1( 0),2,1( cas t .M i n Wj1ij1miynjyybimiimiii??第三節(jié) 影子價格 影子價格： yi*是資源 bi的價值一種度量，即對第 i種資源的的估價，這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價格，稱它為 “ 影子價格 ” ?影子價格是不穩(wěn)定的，它隨企業(yè)的產(chǎn)品結(jié)構(gòu)、技術(shù)狀況的變化而變化。故有 ?????????3 x2x43x x*5*1*5*1求解得 x1*=1,x5*=1。 第二節(jié) 對偶問題的基本性質(zhì) 例：已知下述線性規(guī)劃問題的對偶問題的最優(yōu)解為Y*＝（ 4/5,3/5,） Z*=5。 ?????????????0x,x,x1x x2x2xxx s t .xxM a x Z3213213212121 y2yM in W ?????????st.證：首先看到該問題存在可行解，例如X=(0,0,0)。 ??????????????????????????0x,x,xbxaxaxabxaxaxabxaxaxas t .xcxcxcM a x Zn21mnmn2m21m12n2n2221211n1n212111nn2211??????? ??????????????????????????0y,y,ycyayayacyayayacyayayas t .ybybybM i n Wm21nmmn22n11n2mm22221121mm1221111mm2211??????? **2*1myyy**2*1nxxx設(shè) X＝（ x1*,x2*,… ,xm*） T Y＝（ y1*,y2*,… ,ym*） T 分別為原問題和對偶問題的最優(yōu)解。 或具有無界解或無可行解 第二節(jié) 對偶問題的基本性質(zhì) 最優(yōu)性準(zhǔn)則： 如果 和 分別為原問題和對偶問題的可行解，且有 ),2,1(? njx j ?? ),2,1(? miy i ???????miiinjjj ybxc11??),2,1(? njx j ?? ),2,1(? miy i ??則 是原問題的最優(yōu)解， 是其對偶問題的最優(yōu)解 第二節(jié) 對偶問題的基本性質(zhì) ： 若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的目標(biāo)函數(shù)值相等。 推論 3：若原始問題可行，則其目標(biāo)函數(shù)無界的充要條件是對偶問題沒有可行解。0x,x。0x,x。建模如下： ??????????????0x,x124x 61 4x82xx.x32xMax Z21212121 st 問應(yīng)如何安排計劃使該工廠獲利最多？ y1 y2 y3
試題試卷相關(guān)推薦
鄂ICP備17016276號-1