【正文】 當(dāng)非基變量都為零時(shí) ， 可以得到 XB=B1b。 對(duì)偶單純形法 ? 設(shè)原問(wèn)題為 max z=CX AX=b X≥0 又設(shè) B是一個(gè)基 。 ? 根據(jù)對(duì)偶問(wèn)題的對(duì)稱(chēng)性 ， 可以這樣考慮：若保持對(duì)偶問(wèn)題的解是基可行解 ， 即 cj?CBB1Pj≤0， 而原問(wèn)題在非可行解的基礎(chǔ)上 ， 通過(guò)逐步迭代達(dá)到基可行解 ， 這樣也得到了最優(yōu)解 。 ? 通過(guò)逐步迭代 ， 當(dāng)在檢驗(yàn)數(shù)行得到對(duì)偶問(wèn)題的解也是基可行解時(shí) ，根據(jù)性質(zhì) (2)、 (3)可知 ， 已得到最優(yōu)解 。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的正則解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解。 由單純性表知 : 故線性規(guī)劃最優(yōu)解 X*=（ 107/4,31/2,0,0,0,0， 55/4)T 目標(biāo)函數(shù)最優(yōu)值 Z*= 對(duì)偶單純形法的基本思想 ? 從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行 (正則解 )，但它對(duì)應(yīng)著一個(gè)對(duì)偶基可行解（ 檢驗(yàn)數(shù)非正 ），所以也可以說(shuō)是從一個(gè)對(duì)偶基可行解出發(fā)；然后檢驗(yàn)原規(guī)劃的正則解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)正則解，此正則解對(duì)應(yīng)著另一個(gè)對(duì)偶基可行解（檢驗(yàn)數(shù)非正）。得 maxZ = 3 x1十 2 x2十 x3 8 x1十 2 x2十 10 x3 ＋ x4 ＝ 300 10 x1十 5 x2十 8 x3 ＋ x5＝ 400， s新產(chǎn)品 V需用設(shè)備 A一 4臺(tái)時(shí)， B一 4臺(tái)時(shí)，C一 l2臺(tái)時(shí)，單位產(chǎn)品盈利 ，如 A,B,C設(shè)備臺(tái)時(shí)不增加，分別回答這兩種新產(chǎn)品投產(chǎn)在經(jīng)濟(jì)上是否合算 ? (4）對(duì)產(chǎn)品工藝重新迸行設(shè)計(jì)，改進(jìn)結(jié)構(gòu)，改進(jìn)后生產(chǎn)每件產(chǎn)品 I，需用設(shè)備 A一 9臺(tái)時(shí)，設(shè)備 B一 12臺(tái)時(shí)，設(shè)備 C一 4臺(tái)時(shí)，單位產(chǎn)品盈利 ，問(wèn)這對(duì)原計(jì)劃有何影響 ? Ⅰ Ⅱ Ⅲ 設(shè)備有效臺(tái)時(shí)（每月） A B C 8 10 2 2 5 13 10 8 10 300 400 420 單位產(chǎn)品利潤(rùn)（千元） 3 2 解 設(shè)產(chǎn)品 Ⅰ 、 Ⅱ 、 Ⅲ 的產(chǎn)量分別為 x1， x2， x3 ，其數(shù)學(xué)模型為 maxZ=3 x1十 2 x2十 x3 8 x1十 2 x2十 10 x3 ≤300 10 x1十 5 x2十 8 x3 ≤ 400， s x1 ,x2 ≥ 0。 2x1 3x2 +x4= 100。 ? maxZ = 10x1 + 18x2 。 （ 5） 利用影子價(jià)格分析工藝改變后對(duì)資源的影響 前例中 ， 使煤炭節(jié)約 2%， 則帶來(lái)的收益為 y2*b2 . x1 + 5x2 +x5= 150。 5x1 + 2x2 +x3=170。 而 y2*= 57/7比原來(lái)增大了 ， 說(shuō)明第二種資源更緊缺了 。 m б B= CB— ∑ a ijyi= 18－ (2 0 + 1 32/7 + 4 6/7) =100. i=1 說(shuō)明產(chǎn)品 B所能提供的單件利潤(rùn)大于其隱含成本，相對(duì)價(jià)值系數(shù)б B0，故產(chǎn)品 B值得投產(chǎn)。 x1 、 x2 ≥ 0. 計(jì)算產(chǎn)品 A和 B的相對(duì)價(jià)值系數(shù)： m б A= CA— ∑ a ijyi i=1 =10 — (1 0 + 2 32/7 ＋ 3 6/7 ) = — 12/7 0。 2x1 + 3x2 ≤100。 б 0， 產(chǎn)品所能提供的單件利潤(rùn)小于其隱含成本， 產(chǎn)品不值得投產(chǎn)； б 0，產(chǎn)品 B所能提供的單件利潤(rùn)大于其隱含成本，產(chǎn)品值得投產(chǎn) 產(chǎn)品單件消耗資源 A B 影子價(jià)格鋼材煤機(jī)時(shí)1 22 13 4032/76/7單件利潤(rùn)（萬(wàn)元） 10 18 例 MaxZ = 10x1 + 18x2。 式中： cj表示單位 j種產(chǎn)品的價(jià)值 （ 或利潤(rùn) ） m ∑ a ijyi i=1 表示生產(chǎn)第 j種產(chǎn)品所消耗的各項(xiàng)資源的影子價(jià)格的總和 ，它可以稱(chēng)為第 j種產(chǎn)品的 隱含成本 ， 檢驗(yàn)數(shù) б j 稱(chēng)作是第 j種產(chǎn)品的 相對(duì)價(jià)值系數(shù) 。 3） 隨著資源的買(mǎi)進(jìn)和賣(mài)出 ， 它的影子價(jià)格也將發(fā)生變化 ， 直到影子價(jià)格與市場(chǎng)價(jià)格保持同等水平時(shí) ， 才處于平衡狀態(tài) 。 因此 ， 企業(yè)的決策者可以 把本企業(yè)資源的影子價(jià)格與當(dāng)時(shí)的市場(chǎng)價(jià)格進(jìn)行比較 。 不同的企業(yè) ， 即使是相同的資源 （ 例如鋼材 ） ， 其影子價(jià)格也不一定相同 。 這樣不斷調(diào)整 、 補(bǔ)充 ，真正實(shí)現(xiàn)資源的合理利用 。 2） 對(duì)影子價(jià)格為零的資源 ， 企業(yè)的管理者也不應(yīng)忽視 ， 這種資源對(duì)該企業(yè)來(lái)說(shuō)是相對(duì)富裕的 。 影子價(jià)格在經(jīng)濟(jì)管理中的應(yīng)用很多 （ 1） 影子價(jià)格能指示企業(yè)內(nèi)部挖潛的方向 1） 影子價(jià)格越高的資源 ， 表明它對(duì)目標(biāo)增益影響越大 ， 同時(shí)也表明這種資源對(duì)該企業(yè)來(lái)說(shuō)越稀缺和越貴重 ， 企業(yè)的管理者就應(yīng)該重視對(duì)這種資源的管理 ， 通過(guò)挖潛革新 、 降低消耗或及時(shí)補(bǔ)充該種資源 ， 以保證給企業(yè)帶來(lái)較大的收益 。 影子價(jià)格隨具體情況而異 ， 在完全市場(chǎng)經(jīng)濟(jì)的條件下 ， 當(dāng)某種資源的市場(chǎng)價(jià)低于影子價(jià)格時(shí) ， 企業(yè)應(yīng)買(mǎi)進(jìn)該資源用于擴(kuò)大生產(chǎn)；而當(dāng)某種資源的市場(chǎng)價(jià)高于企業(yè)影子價(jià)格時(shí) ， 則企業(yè)的決策者應(yīng)把已有資源賣(mài)掉 。 這種估價(jià)是針對(duì)具體工廠的具體產(chǎn)品而存在的一種特殊價(jià)格 ， 稱(chēng)它為 “ 影子價(jià)格 ” 。 ? 第 1章中例 1的影價(jià)格及其經(jīng)濟(jì)解釋。 比原來(lái)的增加 。 從圖 21可看到 ， 設(shè)備增加一臺(tái)時(shí) ， 代表該約束條件的直線由 ① 移至 ①′ ， 相應(yīng)的最優(yōu)解由 (4 ， 2) 變?yōu)?(4 ， ) ， 目 標(biāo) 函 數(shù)z=2 4+3 =， 即比原來(lái)的增大 。 ? 第 1章中例 1的影價(jià)格及其經(jīng)濟(jì)解釋。 ? 第 1章中例 1的影價(jià)格及其經(jīng)濟(jì)解釋。 因 y1， y2≥0；原問(wèn)題的兩個(gè)約束條件應(yīng)取等式 ， 故有 x1*+3x5*=4， 2x1*+x5*=3 求解后得到 x1*=1,x5*=1；故原問(wèn)題的最優(yōu)解為 X*=(1， 0， 0， 0， 1)T； w*=5 定理 5 若 X , Y分別為 (P) , (D)的可行解，則 X , Y為最優(yōu)解的充要條件是 ? ?? ????????00XCYAAXbY同時(shí) 成立 證 : (必要性） 原問(wèn)題 對(duì)偶問(wèn)題 ???????0,.ssXXbXAXtsCXZM a x???????0,.ssYYcYYAtsYbWM i nbXAX s ?? CYYA s ??? ?AXbX s ?? ? ?CYAY s ??YbYXY A X s ?? CXXYY A X s ??0?? XYYX ss y1 yi ym ym+1 ym+j yn+m x1 xj xn xn+1 xn+i xn+m 對(duì)偶問(wèn)題的變量 對(duì)偶問(wèn)題的松弛變量 原始問(wèn)題的變量 原始問(wèn)題的松弛變量 xjym+j=0 yixn+i=0 (i=1,2,…,m。試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解 。 ? 上述問(wèn)題的對(duì)偶問(wèn)題為 min w=2y1+y2 y12y2≥1 y1+ y2≥1 y1 y2≥0 y1， y2≥0 由第 1約束條件 ， 可知對(duì)偶問(wèn)題無(wú)可行解；原問(wèn)題雖然有可行解 ， 但無(wú)最優(yōu)解 。 一對(duì)對(duì)偶問(wèn)題的關(guān)系，有且僅有下列三種： 1. 都有最優(yōu)解，且目標(biāo)函數(shù)最優(yōu)值相等； 2. 兩個(gè)都無(wú)可行解； 3. 一個(gè)問(wèn)題無(wú)界，則另一問(wèn)題無(wú)可行解。 證明： (1) 當(dāng) X*和 Y*為原問(wèn)題和對(duì)偶問(wèn)題的一個(gè)可行解 有 bAX ?* CAY ?*bYAXY *** ? *** CXAXY ?bYAXYCX **** ??原問(wèn)題目標(biāo)函數(shù)值 對(duì)偶問(wèn)題目標(biāo)函數(shù)值 所以原問(wèn)題的目標(biāo)函數(shù)值有上界，即可找到有限最優(yōu)解；對(duì)偶問(wèn)題有下界，也存在有限最優(yōu)解。 證明：對(duì)任 X，有 CX? b y =C X X最優(yōu) ? 推論 (P), (D)都有可行解，則必都有最優(yōu)解。 原問(wèn)題簡(jiǎn)記為 (P)，對(duì)偶問(wèn)題簡(jiǎn)記為 (D) 對(duì)偶關(guān)系對(duì)應(yīng)表 原問(wèn)題 對(duì)偶問(wèn)題 目標(biāo)函數(shù)類(lèi)型 Max Min 目標(biāo)函數(shù)系數(shù) 目標(biāo)函數(shù)系數(shù) 右邊項(xiàng)系數(shù) 與右邊項(xiàng)的對(duì)應(yīng)關(guān)系 右邊項(xiàng)系數(shù) 目標(biāo)函數(shù)系數(shù) 變量數(shù)與約束數(shù) 變量數(shù) n 約束數(shù) n 的對(duì)應(yīng)關(guān)系 約束數(shù) m 變量數(shù) m 原問(wèn)題變量類(lèi)型與 ? 0 ? 對(duì)偶問(wèn)題約束類(lèi)型 變量 ? 0 約束 ? 的對(duì)應(yīng)關(guān)系 無(wú)限制 ＝ 原問(wèn)題約束類(lèi)型與 ? ? 0 對(duì)偶問(wèn)題變量類(lèi)型 約束 ? 變量 ? 0 的對(duì)應(yīng)關(guān)系 ＝ 無(wú)限制 對(duì)偶問(wèn)題的基本性質(zhì) 定理 1 對(duì)偶問(wèn)題的對(duì)偶就是原問(wèn)題 Max W’=Yb . YA≤C Y≥0 Min Z’=CX . AX≥b X ≥0 Max Z=CX . AX ≤b X ≥0 Min W=Yb . YA ≥C Y≥0 對(duì)偶的定義 對(duì)偶的定義 定理 2 (弱對(duì)偶定理 ) 分別為 (P), (D)的可行解，則有 C ? b X ， y X y 證明：由 A X ? b, y ?0 有 yA X ? b y 由 A y ? C, X ?0 有 y A X ? C X 所以 C X ? y A X ? yb 推論 (P)有可行解 , 但無(wú)有限最優(yōu)解，則 (D)無(wú) 可行解。 x1≥5 x2≥4 x3≥4 x4≥3 x5≥3 x6≥2 x7≥2 x x x x x x x7 ≥0 x1＋ x2≥14 x2＋ x3≥13 x3＋ x4≥11 x4＋ x5≥10 x5＋ x6≥9 x6＋ x7≥7 x7＋ x1≥7 Minz= x1+ x2 +x3+ x4+ x5 + x6 + x7 2．監(jiān)理工程師年耗費(fèi)的總成本 (4 7/12+7 5/12） min（ x1+ x2 +x3+ x4+ x5 + x6 + x7） 4 線性規(guī)