對(duì)偶單純形與線性規(guī)劃模型.doc

第二章 對(duì)偶規(guī)劃和靈敏度分析與實(shí)驗(yàn)第二章 對(duì)偶規(guī)劃和靈敏度分析與實(shí)驗(yàn)2.1 對(duì)偶理論線性規(guī)劃的對(duì)偶理論不僅在理論上而且在實(shí)踐上都是十分重要的。 原問題與對(duì)偶問題的關(guān)系（原問題）s.t.定義對(duì)偶問題為s.t. 使用向量與矩陣表示形式為 對(duì)偶規(guī)劃的要點(diǎn)：（1） min變成max；（2） 價(jià)值系數(shù)與右端向量互換； （3） 系數(shù)矩陣轉(zhuǎn)置；（4） 按規(guī)則添上不等號(hào)。 使用下表歸納為從正面看是原問題，旋轉(zhuǎn)為對(duì)偶問題如下： wi 原關(guān)系Max y對(duì)偶關(guān)系Min z 考慮標(biāo)準(zhǔn)形的線性規(guī)劃 （） 把其中的等式約束變成不等式約束，可得其對(duì)偶問題是其中w1和w2分別表示對(duì)應(yīng)約束Axb和-Ax-b的對(duì)偶變量組，令w=w1-w2，則上述問題可表示成為 () 線性規(guī)劃的原問題和對(duì)偶問題的關(guān)系，其變換形式歸納為下表的對(duì)應(yīng)關(guān)系原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)min z目標(biāo)函數(shù)max y變量 n個(gè) m個(gè)約束條件00無約束=約束條件 m個(gè) n個(gè)變量00=無約束約束條件右端項(xiàng)目標(biāo)函數(shù)變量的系數(shù)目標(biāo)函數(shù)變量的系數(shù)約束條件右端項(xiàng)對(duì)偶問題的實(shí)際應(yīng)用經(jīng)濟(jì)背景解釋原問題和對(duì)偶問題的關(guān)系模型2.1 （營(yíng)養(yǎng)問題） 某工廠所用的營(yíng)養(yǎng)品由幾種配料組成，要求這種營(yíng)養(yǎng)品必須含有m種不同的營(yíng)養(yǎng)成分，并且每份營(yíng)養(yǎng)品中第i種營(yíng)養(yǎng)成分的含量不能低于。已知每單位的第j種配料中所含第i種營(yíng)養(yǎng)成分的量為，每單位的第j 種配料的價(jià)格為。試確定在保證營(yíng)養(yǎng)需要的條件下，使工廠所配制的營(yíng)養(yǎng)品費(fèi)用最小的配方法。建立模型原問題解：設(shè)表示第j種配料的使用量，則為第j種配料含有第i種營(yíng)養(yǎng)成份的數(shù)量。根據(jù)模型要求，營(yíng)養(yǎng)品中第i種營(yíng)養(yǎng)成份的含量不能低于，那么使用數(shù)學(xué)表達(dá)式來表示此約束為 , i=1，2,，m (2.1)并且考慮到非負(fù)約束為 , j=1，2,，n.分析目標(biāo)函數(shù)，由于第j種配料單位的價(jià)格為，則為第j種配料總價(jià)格為。這樣，營(yíng)養(yǎng)品的總費(fèi)用為 (2.2)綜上所述，已得到工廠希望在保證營(yíng)養(yǎng)價(jià)值的前提下，使?fàn)I養(yǎng)品的費(fèi)用最省的營(yíng)養(yǎng)問題歸結(jié)為下面的線性規(guī)劃問題： s.t. , i=1，2,，m (2.3) , j=1，2,，n. 對(duì)偶問題的經(jīng)濟(jì)解釋 假定某公司想把這m種營(yíng)養(yǎng)成分分別制成單一的產(chǎn)品銷售給工廠。顯然，為了保證銷路，價(jià)格不能太高，若含一個(gè)單位的第i種營(yíng)養(yǎng)成分的產(chǎn)品定價(jià)為wi (wi0)，因?yàn)闋I(yíng)養(yǎng)品中，第j種配料每單位的價(jià)格為cj，而它所含第i種營(yíng)養(yǎng)成分的量為aij，現(xiàn)要用aij (i=1,m) 個(gè)單位的第i種產(chǎn)品才能代替它，因此為使工廠愿意采用產(chǎn)品來代替原來的營(yíng)養(yǎng)品，必須使產(chǎn)品的價(jià)格滿足下面的不等式。 。 由于每份營(yíng)養(yǎng)品中必須含有bi個(gè)單位的第i種營(yíng)養(yǎng)成分，因此這樣一份代營(yíng)養(yǎng)品的價(jià)格就是 。 對(duì)于工廠來說，問題是如何確定每種營(yíng)養(yǎng)品的售價(jià)wi，使在滿足價(jià)格的約束條件下，使y達(dá)到最大，從而使公司的利潤(rùn)最大，即對(duì)偶規(guī)劃為 2.2 對(duì)偶問題的基本性質(zhì)1對(duì)稱性 對(duì)偶問題的對(duì)偶是原問題。2弱對(duì)偶性 設(shè)x和w分別是問題（P）和（D）的可行解，則 (2.4)3無界性 問題（P）和（D）同時(shí)有最優(yōu)解的充分必要條件是它們同時(shí)有可行解。而且若其中有一個(gè)問題無界，則另一個(gè)問題無解。4強(qiáng)對(duì)偶性 設(shè)x*和w*分別為（P）和（D）的可行解，則它們分別為 （P）和（D）的最優(yōu)解當(dāng)且僅當(dāng) cTx*=(w*)Tb (2.5)5互補(bǔ)松弛性 設(shè)x*和w*分別為原問題（P）和對(duì)偶問題（D）的可行解，則它們分別為（P）和（D）的最優(yōu)解當(dāng)且僅當(dāng)， ，；，。 (2.6) 使用矩陣形式，可得x*和w*的互補(bǔ)松弛性條件: w*(Ax*b)=0 ， (cw*A)x*=0 (2.6)歸納：一對(duì)對(duì)偶規(guī)劃的最優(yōu)解滿足互補(bǔ)松弛性，如果將等式約束看成是起作用（臨界）約束，把自由變量看成非起作用約束。那么有下面結(jié)論，設(shè)一對(duì)偶規(guī)劃都有可行解，若原規(guī)劃某一約束是某個(gè)最優(yōu)解的非起作用（臨界）約束，則它的對(duì)偶約束一定是對(duì)偶規(guī)劃所有最優(yōu)解的起作用約束。6唯一性 問題（P）有非退化的最優(yōu)基本可行解，那么其對(duì)偶規(guī)劃(D)有唯一的最優(yōu)解。7對(duì)偶變量的經(jīng)濟(jì)解釋 假定所討論的是下面的線性規(guī)劃問題 （P）其中b表示某工廠所擁有的m種資源的總量，aij表示生產(chǎn)每件第j種產(chǎn)品需消耗第i種資源的量，該問題的實(shí)際背景是在資源有限的條件下安排生產(chǎn)，以使效益最大。影子價(jià)格 設(shè)有一個(gè)工業(yè)系統(tǒng)，它擁有種不同生產(chǎn)工廠，生產(chǎn)種社會(huì)所需的產(chǎn)品。已知一年內(nèi)社會(huì)對(duì)第種產(chǎn)品的最低需求量為，一年內(nèi)一家第類生產(chǎn)工廠的運(yùn)行成本為，生產(chǎn)第種產(chǎn)品的數(shù)量為，那么，在保證滿足社會(huì)對(duì)種產(chǎn)品的需求量的前提下，每種類型工廠各應(yīng)投入多少家運(yùn)行，才能保證成本最??？設(shè)為投入運(yùn)行的第類工廠數(shù)量，則設(shè)最優(yōu)解為，對(duì)應(yīng)的最優(yōu)基，對(duì)偶最優(yōu)解為，則最優(yōu)值：若現(xiàn)在社會(huì)對(duì)第種產(chǎn)品的最低需求量出現(xiàn)變化，改變量為，且此時(shí)最優(yōu)基解不變，即仍是最優(yōu)基，不變，則z的增量為，那么當(dāng)改變量趨于時(shí)，有即是增加一個(gè)單位時(shí)，必須增加的成本，亦即一個(gè)單位的的最低價(jià)格為，稱為“影子價(jià)格”。若使用矩陣與向量形式來說明。設(shè)B是問題（P）的最優(yōu)基，由最優(yōu)值知 （記）, 則 (2.7)故可以看作當(dāng)?shù)趇種資源從原來的量bi增加一個(gè)單位時(shí)，目標(biāo)函數(shù)最優(yōu)值的增加值。 經(jīng)濟(jì)學(xué)家通常把w*稱為影子價(jià)格，也就是針對(duì)收益最大的產(chǎn)品生產(chǎn)安排，對(duì)資源所作的一種價(jià)格估計(jì)。即當(dāng)某種資源的市場(chǎng)價(jià)格低于影子價(jià)格時(shí)，工廠買進(jìn)該種資源安排生產(chǎn)將使收益增加；反之，工廠把該種資源賣出去將顯得更為合適。例2.1某企業(yè)利用三種原料生產(chǎn)兩種產(chǎn)品。三種原料的月供應(yīng)量，生產(chǎn)一噸產(chǎn)品所消耗各種原料的數(shù)量及單位產(chǎn)品價(jià)格如下表所示。設(shè)生產(chǎn)的產(chǎn)品均可在市場(chǎng)銷售，企業(yè)應(yīng)如何安排月生產(chǎn)計(jì)劃，使總收益最大。產(chǎn)品單位產(chǎn)品消耗原料原料月供應(yīng)量（噸）單位產(chǎn)品價(jià)格（萬元噸）2.4 1.8設(shè)計(jì)劃生產(chǎn)產(chǎn)品的數(shù)量為（噸月），則所討論的問題的數(shù)學(xué)模型為。如果另一個(gè)公司想從該企業(yè)購買這三種原料，那么這三種原料的價(jià)格應(yīng)是多少，雙方才能都是合理的呢？建立對(duì)偶模型：設(shè)原料的價(jià)格為（萬元噸），顯然，應(yīng)有。由原問題的條件，生產(chǎn)一噸產(chǎn)品需消耗噸原料，噸原料，噸原料，可獲得收益為2.4萬元。因此若將生產(chǎn)一噸產(chǎn)品的這些原料賣出所得的收益為（萬元）它必須不少于生產(chǎn)一噸產(chǎn)品所得的收益，對(duì)于該企業(yè)才是合算的。所以應(yīng)有對(duì)于產(chǎn)品，可類似得到同時(shí)，若買方（公司）欲購買該工廠的全部原料，則應(yīng)付出萬元（這也是該工廠賣出全部原料的總收益）。從買方角度應(yīng)使總支出盡可能的少。因此，可得到線性規(guī)劃問題不難看出問題（P）與問題（D）互為對(duì)偶問題。問題（P）的第個(gè)約束對(duì)應(yīng)于對(duì)偶變量，問題（D）的最優(yōu)解稱為原料的影子價(jià)格。為了理解影子價(jià)格的含義，先求解問題（P）。為此，先將問題（P）標(biāo)準(zhǔn)化，得問題（P）有初始可行基，由出發(fā)利用單純形方法可求得問題（P）的最優(yōu)基，對(duì)應(yīng)的單純形法列表表示，如下表所示。 由此可得，問題（P）的最優(yōu)解和最優(yōu)值表中松弛變量，表明原料還有42噸未被使用。同時(shí)，根據(jù)上表，立刻得到對(duì)偶問題（D）的最優(yōu)解（單位：萬元）和最優(yōu)值(萬元)這表明：只有當(dāng)該企業(yè)出讓這批原料所獲總收益與利用這批原料生產(chǎn)產(chǎn)品所獲得的總收益相等時(shí)，出讓這批原料才是合理的。但應(yīng)注意：“影子價(jià)格”并不是該原料的市場(chǎng)實(shí)際價(jià)格，而是在取得最大收益時(shí)，收益對(duì)于原料的邊際收益值。實(shí)際上，由上表可得故上式亦可寫成所以，當(dāng)企業(yè)獲最大收益時(shí)（這時(shí)，），有這表明：當(dāng)增加一單位時(shí)，邊際收益為零。這是因?yàn)樵瓎栴}的最優(yōu)解中，即原料尚有42噸未用完，再增加一單位（相當(dāng)于減少原料的供應(yīng)量一個(gè)單位）對(duì)總收益沒有影響。但增加一單位時(shí)（這相當(dāng)于原料的供應(yīng)量由240（噸）減少到239（噸），總收益將減少0.12萬元?；蛘哒f，當(dāng)企業(yè)取得最大收益時(shí)，增加一單位原料的供應(yīng)量，將使總收益增加0.12萬元。對(duì)于原料可類似分析。以上分析對(duì)管理人員提供了十分有用的信息，例如，當(dāng)原料的市場(chǎng)實(shí)際價(jià)格為0.1萬元，低于影子價(jià)格萬元時(shí)，企業(yè)管理者可購入原料以增加收益。同樣，對(duì)于原料，盡管市場(chǎng)價(jià)格很便宜，但由于影子價(jià)格，也不應(yīng)考慮再購入原料。由此看出，影子價(jià)格確實(shí)可為企業(yè)提供管理決策的參考信息。使用LINDO計(jì)算上述例。! Exampl 2.4!MAX 2.4X1 + 1.8X2 !SUBJECT TO!1) X1 + X2 = 1502) 2X1 + 3X2 = 2403) 3X1 + 2X2 = 300END 從LINDO菜單下選用SOLVE命令并進(jìn)行靈敏度分析，可得解為：2.6 LINDO軟件求解與靈敏度分析， 例2.2（工件加工任務(wù)分配問題） 某車間有兩臺(tái)機(jī)床甲和乙，可用于加工三種工件，假定這兩臺(tái)機(jī)床的可用臺(tái)時(shí)數(shù)分別為700和800，三種工件的數(shù)量分別為300，500和400，且已知用不同機(jī)床加工單位數(shù)量的不同工件所屬的臺(tái)時(shí)數(shù)和加工費(fèi)用（表2.1），問怎樣分配機(jī)床的加工任務(wù)，才能既滿足加工工件的要求，又使總加工費(fèi)用最低？ 表2.1機(jī)床類型單位工件所需加工臺(tái)時(shí)單位工件的加工費(fèi)用可用工件I工件II工件III工件I工件II工件III臺(tái)時(shí)數(shù)甲0.41.11.013910700乙0.51.21.311128800解：這三種工件既可在機(jī)床甲上加工，也可以在機(jī)床乙上加工，各種工件在機(jī)床甲和乙上的加工數(shù)量就是需要解決問題。 設(shè)在甲機(jī)床上加工的工件，和的數(shù)量分別為x1, x2和x3，在乙機(jī)床上加工工件,和的數(shù)量分別為x4, x5, x6，則根據(jù)這三種工件的數(shù)量限制，有再由機(jī)床甲和乙的可用總臺(tái)時(shí)限制，有而總加工費(fèi)用 綜合上述各約束條件，可得該問題的數(shù)學(xué)模型如下： s.t. 此例的LINDO輸入模型為：! Example ! MIN 13 X1 + 9 X2 + 10 X3 + 11 X4 + 12 X5 + 8 X6 !SUBJECT TO!1) X1 + X4 = 3002) X2 + X5 = 5003) X3 + X6 = 4004) 0.4 X1 + 1.1 X2 + X3 = 7005) 0.5 X4 + 1.2 X5 + 1.3 X6 = 800END !從LINDO菜單下選用SOLVE命令中若不進(jìn)行靈敏度分析，則可得解為：從LINDO菜單下選用SOLVE命令并進(jìn)行靈敏度分析，可得解為：從LINDO軟件為此例編制的程序求解與進(jìn)行靈敏度分析比較，可知靈敏度分析在此例中，可以獲得更多的信息，更加充分地認(rèn)識(shí)原問題和對(duì)偶問題的解在靈敏度分析中得重要作用。例23（廠址選擇問題） 考慮A，B，C三地，每地都出產(chǎn)一定數(shù)量的原料，也消耗一定數(shù)量的產(chǎn)品（見表2.2），已知制成每噸產(chǎn)品需3噸原料，各地之間的距離為AB：150km，AC：100km，BC：200km。假定每萬噸原料運(yùn)輸1km的運(yùn)價(jià)是5000元，每萬噸產(chǎn)品運(yùn)輸1km的運(yùn)價(jià)是6000元。由于地區(qū)條件的差異，在不同地點(diǎn)設(shè)廠的生產(chǎn)費(fèi)用也不同，問怎樣在何處設(shè)廠，規(guī)模多大，才能使總費(fèi)用最?。苛硗?，由于其它條件限制，在B處建廠的規(guī)模（生產(chǎn)的產(chǎn)品數(shù)量）不能超過5萬噸。表2.2地 點(diǎn)年產(chǎn)原料(萬噸)年銷產(chǎn)量(萬噸)生產(chǎn)費(fèi)用(萬元/萬噸)A207150B1613120C240100 解：令為由i地運(yùn)到j(luò)地的原料數(shù)量（萬噸），為由i地運(yùn)往j地的產(chǎn)品數(shù)量（萬噸），i,j=1,2,3（分別表示A，B，C三地），據(jù)題意有 由于，又因都是非負(fù)，從而有，這樣可將此方程略去。若設(shè)為第i處的設(shè)廠規(guī)模（年產(chǎn)產(chǎn)品數(shù)量，萬噸），則有 從而得到 將x11,x22和x33消去，并考慮y21+y225和變量非負(fù)條件，得約束條件如下：目標(biāo)函數(shù)為（包括原材料運(yùn)輸費(fèi)、產(chǎn)品運(yùn)輸費(fèi)和生產(chǎn)費(fèi)）：此例的LINDO輸入模型為：! Exampl 2.2! MIN 75 X12 + 75 X21 + 50 X13 + 50 X31 + 100 X23 + 100 X32 +150 Y11 + 240Y12 +210 Y21 +120 Y22 + 160 Y31 + 220 Y32 !SUBJECT TO!1) 3 Y11 + 3 Y12 + X12 + X13 - X21 -X31 = 202) 3 Y21 + 3 Y22 - X12 + X21 + X23 -X32 = 163) 3 Y31 + 3 Y32 - X13 - X23 + X31 +X32 = 244) Y11 + Y21 + Y31 = 75) Y12 + Y22 + Y32 = 136) Y21 + Y22 = 5END !從LINDO菜單下選用SOLVE命令中若不進(jìn)行靈敏度分析，可得解。從LINDO菜單下選用SOLVE命令并進(jìn)行靈敏度分析，可得解。從LINDO軟件為此例編制的程序求解與進(jìn)行靈敏度分析比較，可知靈敏度分析在此例中，可以獲得更多的信息，更加充分地認(rèn)識(shí)原問題和對(duì)偶問題的解在靈敏度分析中得重要作用。例2.4 最佳連續(xù)投資方案 某部門在今后五年內(nèi)考慮下列項(xiàng)目投資，已知項(xiàng)目1從第一年到第四年每年年初需要投資，并于次年末回收本利115%；項(xiàng)目2第三年年初需要投資，到第五年末能回收本利125%，但規(guī)定最大投資額不超過4萬元；項(xiàng)目3第二年年初需要投資，到第五年末能回收本利140%，但規(guī)定最大投資額不超過3萬元；項(xiàng)目4 五年內(nèi)每年年初可購買公債，于每年末歸還，并加利息6%。該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項(xiàng)目每年的投資額。使到第 5年末擁有的資金的本利總額為最大？模型建立：這是一個(gè)與時(shí)間有關(guān)的連續(xù)投資問題，在此對(duì)該問題是將五年情況總體地靜態(tài)考慮，不是按時(shí)間去動(dòng)態(tài)地考慮。設(shè)表示第年年初投資給項(xiàng)目的資金額度（單位：萬元），則各年的投資限制為第一年：第二年：年初擁有的資本額為，因此有；第三年：年初擁有的資金額為，因此有；同樣的分析可得：第四年：；第五年：本問題是要制定投資方案使第五年末該部門擁有的資金額最大，即整理上述分析結(jié)果，本問題可表示為下面的數(shù)學(xué)問題滿足約束條件上述模型中出現(xiàn)的函數(shù)都是線性函數(shù)，即為線性規(guī)劃模型。此例的LINDO輸入模型為： MAX 1.4Y23 + 1.25 Y32 + 1.15Y41 + 1.06Y54 SUBJECT TO 2) Y11 + Y14 = 10 3) Y11 -0.06Y14 +Y12 + Y23 + Y24 = 10 4) -0.15Y11-0.06Y14 + Y21 +Y23 -0.06Y24 + Y31 +Y32 +Y34 = 10 5) -0.15Y11-0.06Y14 -0.15Y21 +Y23 -0.06Y24 + Y31 +Y32 -0.06Y34+Y41+Y44 = 10 6) -0.15Y11-0.06Y14 -0.15Y21 +Y23 -0.06Y24 -0.15Y31 +Y32-0.06Y34+Y41-0.06Y44 +Y54= 10 7) Y23=3 8) Y32=4 END 從LINDO菜單下選用SOLVE命令并進(jìn)行靈敏度分析，則可得解。2.7 投資的收益和風(fēng)險(xiǎn)組合問題98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽A題 介紹使用多目標(biāo)規(guī)劃來建立數(shù)學(xué)模型。此數(shù)學(xué)模型反映了可以通過數(shù)學(xué)轉(zhuǎn)化成線性規(guī)劃的模型。市場(chǎng)上有種資產(chǎn)（如股票、債券、）供投資者選擇，某公司有數(shù)額為的一筆相當(dāng)大的資金可用作一個(gè)時(shí)期的投資。公司財(cái)務(wù)分析人員對(duì)這種資產(chǎn)進(jìn)行了評(píng)估，估算出在這一時(shí)期內(nèi)購買的平均收益率為，并預(yù)測(cè)出購買的風(fēng)險(xiǎn)損失率為，考慮到投資越分散，總的風(fēng)險(xiǎn)越小，公司確定，當(dāng)用這筆資金購買若干種資產(chǎn)時(shí)，總體風(fēng)險(xiǎn)可用所投資的中最大的一個(gè)風(fēng)險(xiǎn)來度量。購買要付交易費(fèi)，費(fèi)率為，并且當(dāng)購買額不超過給定值時(shí)，交易費(fèi)按購買計(jì)算（不買當(dāng)然無須付費(fèi)）。另外，假定同期銀行存款利率是，且既無交易費(fèi)又無風(fēng)險(xiǎn)。） 當(dāng)時(shí)的相關(guān)數(shù)據(jù)如下：(元)281103212198234.552256.540試給該公司設(shè)計(jì)一種投資組合方案，即用給定的資金，有選擇的購買若干種資產(chǎn)或存銀行生息，使凈收益盡可能大，而總體風(fēng)險(xiǎn)盡可能小。） 試就一般情