運(yùn)籌學(xué)第02章線性規(guī)劃的對偶理論

1、第二章 線性規(guī)劃的對偶理論(Duality Theory)線性規(guī)劃的對偶問題 對偶問題的基本性質(zhì) 對偶問題的經(jīng)濟(jì)解釋-影子價格對偶單純形法靈敏度分析WinQSB軟件應(yīng)用第一節(jié) 線性規(guī)劃的對偶問題 【例2-1】第一章例1-1中討論了某企業(yè)利用三種資源生產(chǎn)甲乙兩種產(chǎn)品的生產(chǎn)計(jì)劃問題，得到其線性規(guī)劃問題為： 對偶性是線性規(guī)劃問題的最重要的內(nèi)容之一。每一個線性規(guī)劃(LP)問題必然有與之相伴而生的另一個線性規(guī)劃問題，即任何一個求 max z 的LP都有一個求 min w 的LP。其中的一個問題叫“原問題”，另一個稱為“對偶問題” 。一、對偶問題的提出下面從另一個角度來討論這個問題： 假定該企業(yè)決定自己不

2、生產(chǎn)產(chǎn)品，而將現(xiàn)有的資源轉(zhuǎn)讓或出租給其他企業(yè)，那么該如何確定資源的轉(zhuǎn)讓價格？ 分析問題： 1、定價不能太高，否則買方無法接受，并且對買方來說，其目的是越低越好 ； 2、定價不能太低，否則企業(yè)不愿意放棄生產(chǎn)、出讓資源 合理的價格應(yīng)是對方用最少的資金購買該企業(yè)的全部資源，而該企業(yè)所獲得的利潤又不低于自己組織生產(chǎn)時所獲得的利潤。 解：設(shè)分別用 y1、y2和 y3 代表單位時間(h)設(shè)備、每公斤材料A、材料B的出讓代價，根據(jù)假設(shè)有以下對應(yīng)關(guān)系：y1y2y3 則該企業(yè)出租或轉(zhuǎn)讓所有資源所獲得的收入，也即對方企業(yè)需要支付的資金為： 企業(yè)用1臺時設(shè)備和3公斤材料A可生產(chǎn)一件甲產(chǎn)品，盈利90元，其出售這些數(shù)量

3、的資源得到的利潤不能少于90元，則有： 同理，用1臺時設(shè)備、2公斤材料A 、5公斤材料B可生產(chǎn)一件乙產(chǎn)品，盈利70元，出售這些數(shù)量資源得到的利潤不能少于70元，則有：綜上分析，可得到線性規(guī)劃模型為： （LP2） 對偶問題二、對稱形式下對偶問題的一般形式 滿足下列條件的線性規(guī)劃問題稱為具有對稱形式：其變量均具有非負(fù)約束，其約束條件當(dāng)目標(biāo)函數(shù)求極大時均取“”號，當(dāng)目標(biāo)函數(shù)求極小時均取“”號。 對稱形式的線性規(guī)劃問題的原問題為：用矩陣形式表示為：對偶問題的一般形式為: 上述模型簡記為： 用矩陣形式表示，對偶問題為： 將上述對稱形式下線性規(guī)劃的原問題與對偶問題進(jìn)行比較，可以列出如下表所示的對應(yīng)關(guān)系：

4、決策變量約束條件約束條件決策變量約束條件的右端項(xiàng)向量目標(biāo)函數(shù)中的價格系數(shù)向量C目標(biāo)函數(shù)中的價格系數(shù)向量b約束條件的右端項(xiàng)向量b約束條件系數(shù)矩陣(A的轉(zhuǎn)置)約束條件系數(shù)矩陣A目標(biāo)函數(shù)目標(biāo)函數(shù)對偶問題原 問 題 若原問題為求極小形式的對稱形式線性規(guī)劃問題，對偶問題應(yīng)該具有什么形式？ 原問題對偶問題若一個線性規(guī)劃問題是另一個線性規(guī)劃問題的對偶問題，則它們互為對偶問題。 對偶問題的對偶問題是原問題。9070 x1 x2 16y1 111636y2323665y305659070原問題對偶問題對偶問題 【例2-2】 寫出下述線性規(guī)劃問題的對偶問題 例中目標(biāo)函數(shù)為max，若為對稱形式，則約束條件應(yīng)為“”號

5、，所有變量均應(yīng)0。 非對稱形式三、非對稱形式的原對偶問題關(guān)系1目標(biāo)函數(shù)為求極大，故約束條件應(yīng)均為“”號約束b兩邊乘-1：將c寫成兩個不等式約束：2變量均有非負(fù)約束令：則：原問題對偶問題原問題對偶問題A約束系數(shù)矩陣約束系數(shù)矩陣的轉(zhuǎn)置b約束條件的右端項(xiàng)向量目標(biāo)函數(shù)中的價格系數(shù)向量C目標(biāo)函數(shù)中的價格系數(shù)向量約束條件的右端項(xiàng)向量目標(biāo)函數(shù) Max z=CX目標(biāo)函數(shù) Min w=YTb約束條件決策變量決策變量約束條件m個=n個=n個00無約束m個00無約束原問題對偶問題【例2-3】寫出下列線性規(guī)劃問題的對偶問題第二節(jié) 對偶問題的基本性質(zhì) 一、單純形法計(jì)算的矩陣描述(P)(D)對稱形式原線性規(guī)劃問題加上松弛

6、變量后為：其中，Xs=(xn+1,xn+2,，xn+m )為松弛變量，I為mm 單位矩陣。 本節(jié)的討論先假定原問題及對偶問題為對稱形式線性規(guī)劃問題，即原問題為： 設(shè)B是一個可行基，也稱基矩陣，若將系數(shù)矩陣 A 分為(B,N)兩塊，這里 N 是非基變量的系數(shù)矩陣，對應(yīng)于基 B 的變量為XB，其它非基變量用XN 表示。即: 同時也將 C 分為兩塊(CB ,CN )，CB 是目標(biāo)函數(shù)中基變量 XB 的系數(shù)行向量，CN 是目標(biāo)函數(shù)中非基變量XN 的系數(shù)行向量。0CNCB j INBbXs0XsXNXB基變量非基變量初始單純形表 將為塊后的數(shù)據(jù)放入單純形表，得：用 左乘上表第3行得：I0用 左乘下表第3

7、行，加上表第4行得： j XBCBXsXNXB非基變量基變量最終單純形表j XBCBXsXNXB非基變量基變量最終單純形表I0 由上表可以看出，若此時得到的是最優(yōu)解，則各檢驗(yàn)數(shù)應(yīng)滿足：非基變量 XN 的檢驗(yàn)數(shù)：松弛變量 XS 的檢驗(yàn)數(shù)：基 變 量 XB 的檢驗(yàn)數(shù)： 由上三個檢驗(yàn)數(shù)可以看出，它們都有乘子 ，稱它為單純乘子，用符號表示為：討論：(1)(2) 將(1)(2)式合并，可以可以得到：(3) 1.初始表中單位陣在迭代后單純形表中對應(yīng)的位置就是B-1； 2.對于原問題的任意可行解，各松弛變量檢驗(yàn)數(shù)的相反數(shù)恰好是其對偶問題的一個可行解，且兩者具有相同的目標(biāo)函數(shù)值。 上面(3)式可以寫為： 將

8、同時右乘 b 得： 從上述分析可以得到如下結(jié)論：j XBCBXsXNXB非基變量基變量最終單純形表I0即：二、對偶問題的基本性質(zhì)1、對稱性：對偶問題的對偶問題是原問題。對偶定義對偶定義 2、弱對偶性：設(shè) 和 分別是問題（P）和（D）的可行解，則恒有:即： 推論：原問題任一可行解的目標(biāo)函數(shù)值是其對偶問題目標(biāo)函數(shù)值的下界；反之對偶問題任一可行解的目標(biāo)函數(shù)值是其原問題目標(biāo)函數(shù)值的上界。 推論：如原問題有可行解且目標(biāo)函數(shù)值無界(具有無界解)，則其對偶問題無可行解；反之對偶問題有可行解且目標(biāo)函數(shù)值無界，則其原問題無可行解 注：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對偶問題無可行解時，其原問題或具有無界解或無可行解，反之

9、亦然。 推論：若原問題有可行解而其對偶問題無可行解，則原問題目標(biāo)函數(shù)值無界；反之，對偶問題有可行解而其原問題無可行解，則對偶問題的目標(biāo)函數(shù)值無界 3、最優(yōu)性 若 和 分別是P 和D的可行解且 ，則 和 分別是問題P和D的最優(yōu)解。4、強(qiáng)對偶性 若一對對偶問題P 和D都有可行解，則它們都有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值必相等。 推論：若P和D的任意一個有最優(yōu)解，則另一個也有最優(yōu)解，且目標(biāo)函數(shù)的最優(yōu)值相等 5、互補(bǔ)松弛性 在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。也即： cj9070000CBXBb

10、x1x2x3x4x570 x212013-1090 x1410-2100 x55 00 -1551j00-30-200若 ，即 ，則有 若 ，則有 ，即 cj9070000CBXBbx1x2x3x4x570 x212013-1090 x1410-2100 x55 00 -1551j00-30-200若 ，則有 若 ，則 【例2-4】線性規(guī)劃問題為：若已知原問題的最優(yōu)解為 X * =（0,0,4），z*=12 試求對偶問題的最優(yōu)解。解：相應(yīng)的對偶問題為：（a）（b）（c）將X* =（0, 0, 4）代入原問題中，有下式：根據(jù)互補(bǔ)松弛條件，必有y*1= y*2=0。代入對偶問題 (c)式，y3 =

11、3。因此，對偶問題的最優(yōu)解為Y*=(0, 0, 3)，w =12（a）（b）（c）第三節(jié) 對偶問題的經(jīng)濟(jì)解釋 影子價格 在單純形法的迭代過程中，目標(biāo)函數(shù)z=CBB-1b和檢驗(yàn)數(shù) CN-CBB-1N中都有單純乘子YT=CBB-1 ，那么Y的經(jīng)濟(jì)意義是什么？ 從上節(jié)對偶問題的基本性質(zhì)看出，當(dāng)線性規(guī)劃原問題求得最優(yōu)解 時，其對偶問題也得到最優(yōu)解 ，且代入各自的目標(biāo)函數(shù)后有: 式中，bi 是線性規(guī)劃原問題約束條件的右端項(xiàng)，它代表第 i 種資源的擁有量。 設(shè)B是問題 P的最優(yōu)基：當(dāng)bi 變?yōu)閎i+1 時（其余右端項(xiàng)不變，也不影響B(tài)） 目標(biāo)函數(shù)最優(yōu)值變?yōu)椋簩?bi 求偏導(dǎo)數(shù)得：其經(jīng)濟(jì)意義是：在其它條件不變

12、的情況下，單位資源變化所引起的目標(biāo)函數(shù)的最優(yōu)值的變化。即 y*i 表示 z* 對 bi 的變化率。 由此可以看出， yi 表示對第 i 種資源的估價，這種估價不同于資源的市場價格，是根據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價，它是針對具體企業(yè)的具體產(chǎn)品而存在的一種特殊價格，為區(qū)別起見，稱它為“影子價格”。 一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當(dāng)估價，這種估價直接涉及到資源的最有效利用。正確理解影子價格，可幫助決策者分析經(jīng)濟(jì)活動，作出有利決策。 第四節(jié) 對偶單純形法一、對偶單純形法的基本思路設(shè) （P）則 （D）化為標(biāo)準(zhǔn)型:（P）（D）設(shè)B為(P)的

13、一個基，記A=(B, N)，C=(CB, CN)，X=(XB, XN)T（P）的標(biāo)準(zhǔn)型可寫為：（P）（D）（D）的標(biāo)準(zhǔn)型可寫為：則標(biāo)準(zhǔn)型的數(shù)學(xué)模型可用單純形表表示為：cjCBCN0CBXBB-1bIB-1NB-1j0CN-CBB-1N-CBB-1-YTs1-YTs2-YT 若B為(P)的可行基，則 XB=B-1b 為(P)的一個基可行解，相應(yīng)的檢驗(yàn)數(shù)為0，CN-CBB-1N，-CBB-1。 令YT=CBB-1，代入(D)的約束條件中，可發(fā)現(xiàn)檢驗(yàn)數(shù)行恰為對偶問題的一組基解的相反數(shù)。確定初始單純形表j 0 ?b i 0 ?尋找新的基解單純形法單純形表人工變量法計(jì)算結(jié)束是否否是單純形法對偶單純形法

14、在單純形表中進(jìn)行迭代時，在 b 列中得到的是原問題的基可行解，此時檢驗(yàn)數(shù)行得到的是對偶問題的一個基解。 通過逐步迭代，當(dāng)對偶問題得到基可行解時，所有檢驗(yàn)數(shù)均不大于0，此時原問題取得最優(yōu)解。0-20-3000j15-15005x5001-2014x1900-131012x2700-300100j131005065x501801/302/3112x190120-1/311/304x300007090j1005065x50120102336x40160011116x30 x5x4x3x2x1bXBCB0007090Cj 根據(jù)對偶問題的對稱性，若保持對偶問題的解是基可行解，而原問題在非可行解的基礎(chǔ)上通

15、過逐步迭代得到基可行解，此時也就得到了原問題的最優(yōu)解。 對偶單純形法的基本思路： 如果存在一個對偶問題的可行基B，即對j=1,2,n，有 或，這時只要有，即原問題的解為可行解，則兩者均為最優(yōu)解。否則保持對偶問題為可行解，找出原問題的相鄰基解，判別是否有 ，循環(huán)進(jìn)行，直到使原問題也為可行解，從而兩者均為最優(yōu)解。 與單純形法的標(biāo)準(zhǔn)形相比，這里沒有對右端項(xiàng)不大于零的要求，因此，在得到的單純型表中 b 列的值(B-1b)i 不一定非負(fù)。 若所有的(B-1b)i非負(fù)，則X為(P)的基可行解，此時X為(P)的最優(yōu)解，Y為(D)的最優(yōu)解；若存在某一個或幾個的(B-1b)i0，則X不是(P)的可行解，需在保證

16、 Y 為(D)的基可行解的前提下進(jìn)行迭代，直至找到(P)的一個可行解。 注：對偶單純形法不是對對偶問題使用單純形法，而是求解線性規(guī)劃的另一有效方法。它之所以被稱為“對偶單純形法”，是因?yàn)樵摲椒ㄔ谇蠼膺^程中是以對偶原理和單純形法原理為理論依據(jù)的。二、對偶單純形法的計(jì)算步驟1、建立初始單純形表 000100010001xnxsxm+1xmxrx1bCB2、最優(yōu)性判斷 檢查 b 列的數(shù)字，若都為非負(fù)，檢驗(yàn)數(shù)都為非正，則已得到最優(yōu)解，停止計(jì)算； 若 b 列有負(fù)數(shù)，其中某負(fù)數(shù)對應(yīng)的行沒有負(fù)數(shù),則問題無可行解 若 b 列有負(fù)數(shù)，而且所有負(fù)數(shù)對應(yīng)的行都有負(fù)數(shù)，則轉(zhuǎn)入下一步。3、基變換確定離基變量 為了使下一

17、個表中第r行基變量為正值，因而只有對應(yīng)的非基變量才可以考慮作為進(jìn)基的變量。為了使下一個表中對偶問題的解仍為可行解，令:稱 為主元素， 為進(jìn)基的變量。迭代因?yàn)榭偞嬖?，令，其對?yīng)變量為離基的變量。確定進(jìn)基變量 對新的基再檢查是否所有。如果是，找到了兩者的最優(yōu)解；如為否，回到第2步再循環(huán)進(jìn)行。 重復(fù)2-3步?！纠?-5】用對偶單純形法求解下述線性規(guī)劃問題： 解：先將問題改寫為：約束條件（a），(b)兩端乘以“-1”得：Cj-16-36-6500CBXBby1y2y3y4y50y4-90-1-30100y5-70-1-2-501j-36y20y5j-36y2-16y1j-16-36-65301/310

18、-1/30-10-1/30-5-2/3100-40-65-1203010152-32001-5-1100-5-4-12所以，原問題最優(yōu)解為 ：Y*=（30 , 20 , 0 , 0 , 0） 其對偶問題的最優(yōu)解為： X*= (4 , 12)【練習(xí)】用對偶單純形法求解下述線性規(guī)劃問題： 解：將模型轉(zhuǎn)化為:Cj-2-3-400CBXBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301j0 x4-2x1j-3x2-2x1j-2-3-4-10-5/21/21-1/221-1/23/20-1/2000-4-10-111/5107/5-1/5-2/52/501-1/5-2/51/

19、500-9/5-8/5-1/5所以，原問題最優(yōu)解為 ：X*=（11/5 , 2/5 , 0 , 0 , 0） 其對偶問題的最優(yōu)解為： Y*= (8/5 , 1/5)第五節(jié) 靈敏度分析 靈敏度分析研究的就是模型的變化對線性規(guī)劃問題最優(yōu)基或最優(yōu)解的影響程度，主要包括以下兩個問題： 參數(shù)在什么范圍內(nèi)變化時，原最優(yōu)基和最優(yōu)解不變？ 模型發(fā)生變化時，最優(yōu)基和最優(yōu)解會如何變化？ 線性規(guī)劃問題中的參數(shù)往往是一些估計(jì)和預(yù)測的數(shù)字，當(dāng)市場條件發(fā)生變化時，會影響到模型參數(shù)的變化，如： cj 值的變化； aij 隨工藝技術(shù)條件的改變而改變； 資源投入情況改變，資源限制量 bi 會隨之改變； 方法：將個別參數(shù)的變化直

20、接在計(jì)算得到最優(yōu)解的最終單純形 表上反映出來，并進(jìn)行檢查和分析。引進(jìn)人工變量，編制新單純形表，重新計(jì)算非可行解非可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解最優(yōu)解或最優(yōu)基不變可行解可行解一、 價值系數(shù)cj 的變化分析 線性規(guī)劃目標(biāo)函數(shù)中變量系數(shù) Cj 的變化僅僅影響到檢驗(yàn)數(shù)的變化j，所以將 Cj 的變化直接反映到最終單純形表中。 結(jié)論或繼續(xù)計(jì)算的步驟對偶問題原問題表2-8 在最終單純形表中，只可能出現(xiàn)如表2-8中的前兩種情況之一： 若最終表中所有檢驗(yàn)數(shù)仍然均不大于0，即對偶問題取得可行解，出現(xiàn)表2-8中第一種情況，問題的最優(yōu)基和最優(yōu)解不變； 若出現(xiàn)

21、大于0的檢驗(yàn)數(shù)，即出現(xiàn)表2-8中第二種情況，則需使用單純形法繼續(xù)迭代求得最優(yōu)解。 【例2-6】在上述第一章例1-1的某企業(yè)的例子中： 若甲產(chǎn)品的利潤降至85元/件，而乙產(chǎn)品的利潤增至95元/件時，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃有何變化；第一章例1-1的某企業(yè)的例子，其相應(yīng)的數(shù)學(xué)模型為：若發(fā)生變化的 Cj 是非基變量的價值系數(shù)，則檢驗(yàn)數(shù)為：若發(fā)生變化的 Cj 是基變量的價值系數(shù)，則檢驗(yàn)數(shù)為： 若甲產(chǎn)品的利潤不變，則乙產(chǎn)品的利潤在什么范圍內(nèi)變化時，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化。 解：(1)將甲、乙產(chǎn)品的利潤變化直接反映到最終單純形表中，得：因變量 x4 的檢驗(yàn)數(shù)大于零，故需繼續(xù)用單純形法迭代計(jì)算得： 即

22、該企業(yè)隨產(chǎn)品甲、乙的利潤變化應(yīng)調(diào)整為生產(chǎn)甲3件，乙13件。cj8595000CBXBbx1x2x3x4x595x212013-1085x1410-2100 x55 00 -1551j00-115100cj 8595000CBXBbx1x2x3x4x595x285x10 x4j100-311/51301001/531010-1/500-850-290707090-30-20（2）設(shè)產(chǎn)品乙的利潤為（70+）元，反映到最終單純形表中，得表: 為使上表中的解仍為最優(yōu)解，應(yīng)有：解得: 即乙產(chǎn)品的利潤 c2 的變化范圍應(yīng)滿足：cj9070+000CBXBbx1x2x3x4x570+x212013-1090

23、 x1410-2100 x55 00 -1551j00-30-3-20+0二、資源限量bi 的變化分析 當(dāng)右端項(xiàng)發(fā)生變化后，會引起單純形表中b 列數(shù)字的變化，此時可能出現(xiàn)表中第一或第三種情況： 出現(xiàn)表2-8中第一種情況時，問題最優(yōu)解不變； 出現(xiàn)表2-8中第三種情況時，用對偶單純形法找最優(yōu)解。 【例2-7】在某企業(yè)的例子中： (1)若設(shè)備和材料 B 的現(xiàn)有資源不變，而材料 A 的現(xiàn)有資源增加到51公斤時，分析企業(yè)最優(yōu)計(jì)劃的變化； (2)材料 A 和 B 的現(xiàn)有資源不變，則設(shè)備的現(xiàn)有資源在什么范圍內(nèi)變化時，問題的最優(yōu)基不變？ 當(dāng)發(fā)生變化后，最終單純形表中原問題的解相應(yīng)地變化為:解：將其反映到最終單

24、純形表中得： 因上表中原問題為非可行解，用對偶單純形法繼續(xù)計(jì)算得表： cj9070000CBXBbx1x2x3x4x570 x2-3013-1090 x11910-2100 x580 00 -1551j00-30-200cj9070000CBXBbx1x2x3x4x50 x490 x10 x5j30-1-310161110065050010-20-9000由此該的最優(yōu)計(jì)劃改為只生產(chǎn)甲產(chǎn)品16件。設(shè)設(shè)備每天可用能力為(16+)小時，因有： 將其反映到最終單純形表中，其b 列數(shù)字為： 解得-41/3。即設(shè)備的能力應(yīng)在1249/3小時之間。 當(dāng)b0時問題的最優(yōu)基不變，即： 三、增加一個新變量的分析

25、【例2-8】在某企業(yè)的例子中，設(shè)企業(yè)又計(jì)劃推出新型號的產(chǎn)品丙，生產(chǎn)一件所需設(shè)備臺時及材料A、B分別為1小時、4公斤、3公斤，該產(chǎn)品的預(yù)期利潤為115元件，試分析該種產(chǎn)品是否值得投產(chǎn)；如投產(chǎn)，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃有何變化？1.計(jì)算： 2.計(jì)算新的 增加一個變量在實(shí)際問題中反映為增加一種新的產(chǎn)品。其分析步驟為： 3.若 ，原最優(yōu)解不變，只需將計(jì)算得到的 和 直接寫入最終單純形表中；若 ，則按單純形法繼續(xù)迭代計(jì)算找出最優(yōu)解。 解：設(shè)該企業(yè)生產(chǎn)丙產(chǎn)品 x6 件，根據(jù)題意有c6115，P6(1，4，3)T。則相應(yīng)的技術(shù)系數(shù)向量為：將其反映到最終單純形表中得表： cj9070000115CBXBbx1x2

26、x3x4x5x670 x212013-10-190 x1410-21020 x55 00 -15518j00-30-2005，故用單純形表繼續(xù)迭代計(jì)算得表： 故該新的最優(yōu)生產(chǎn)計(jì)劃應(yīng)為生產(chǎn)甲產(chǎn)品 11/4件，乙產(chǎn)品 101/8件，丙產(chǎn)品5/8件cj9070000115CBXBbx1x2x3x4x5x670 x290 x1115x6jcj9070000115CBXBbx1x2x3x4x5x670 x212013-10-190 x1410-21020 x55 00 -15518j00-30-20055/800-15/85/81/81101/8019/8-3/81/8011/4107/4-1/4-1/

27、4000-165/8-185/8-5/80四、技術(shù)系數(shù)aij 的變化分析 【例2-9】在某企業(yè)的例子中，進(jìn)行工藝改進(jìn)后若甲產(chǎn)品每件需設(shè)備、材料A和材料B變?yōu)?臺時、2公斤和0公斤，該產(chǎn)品的利潤變?yōu)?00元件，試重新確定企業(yè)的最優(yōu)生產(chǎn)計(jì)劃。1.計(jì)算： 引起矩陣A的變化 若xj 在最終單純形表中為非基變量，則： 若xj在最終單純形表中為基變量，則可能出現(xiàn)第四種情況。此時，需要引進(jìn)人工變量，編制新的單純形表，重新計(jì)算。2.計(jì)算新的 從而判斷是否需要迭代尋找最優(yōu)解。 解：先將生產(chǎn)消耗變化后的新產(chǎn)品甲看作是一種新產(chǎn)品，生產(chǎn)量為 ，仿本節(jié)三的步驟直接計(jì)算 和 并反映到最終單純形表中。其中：將其反映到最終單

28、純形表中： cj9010070000CBXBbx1x1x2x3x4x570 x2120113-1090 x14100-2100 x55 0-50 -1551j0300-30-200因 已變換為 ，故用單純形法將 替換出基變量中的 ，得:cj9010070000CBXBbx1x1x2x3x4x5100 x190 x10 x5j120113-104100-2106500500100-30-120100變量x4對應(yīng)檢驗(yàn)數(shù)大于零，沒得到最優(yōu)解，用單純形法迭代：cj9010070000CBXBbx1x1x2x3x4x5100 x1160111000 x44100-2100 x565 005 001j-1

29、00-30-10000該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃為只生產(chǎn)工藝改進(jìn)后的甲產(chǎn)品16件。五、增加一個約束條件的分析 增加一個約束條件在實(shí)際問題中相當(dāng)增添一道工序。分析的方法是先將原問題最優(yōu)解的變量值代入新增的約束條件，如滿足，說明新增的約束未起到限制作用，原最優(yōu)解不變。否則，將新增的約束直接反映到最終單純形表中再進(jìn)一步分析。 【例2-10】仍以某企業(yè)為例，設(shè)甲乙產(chǎn)品生產(chǎn)完后，還需經(jīng)過一道環(huán)境試驗(yàn)工序。甲產(chǎn)品每件須環(huán)境試驗(yàn)2小時，乙產(chǎn)品每件1.5小時，又環(huán)境試驗(yàn)工序擁有資源為24小時。試分析增加該工序后企業(yè)的最優(yōu)生產(chǎn)計(jì)劃。 解：環(huán)境試驗(yàn)工序的約束條件：原問題最優(yōu)解不是本例的最優(yōu)解 將標(biāo)準(zhǔn)化后的約束條件以x6

30、為基變量，反映到最終單純形表中得表: cj90700000CBXBbx1x2x3x4x5x670 x212013-10090 x1410-21000 x5500 -155100 x62421.50001j00-30-2000將最優(yōu)解 x1 =4，x2 =12 代入新的約束條件，得： 進(jìn)行變換，得：cj90700000CBXBbx1x2x3x4x5x670 x212013-10090 x1410-21000 x5500 -155100 x6-200-0.5-0.501j00-30-2000原問題為非可行解，用對偶單純形法迭代計(jì)算得表: cj90700000CBXBbx1x2x3x4x5x670 x290 x10 x50 x4j1601400-2010-3002-1500-200110400110-200-1000-40 添加環(huán)境試驗(yàn)工序后，該企業(yè)的最優(yōu)生產(chǎn)計(jì)劃為甲產(chǎn)品生產(chǎn)9/4件，乙產(chǎn)品生產(chǎn)13件。 cj90700000CBXBbx1x2x3x4x5x670 x290 x10 x30 x4jcj90700000CBXBb