運籌學(xué)2對偶問題課件_第1頁
運籌學(xué)2對偶問題課件_第2頁
運籌學(xué)2對偶問題課件_第3頁
運籌學(xué)2對偶問題課件_第4頁
運籌學(xué)2對偶問題課件_第5頁
已閱讀5頁,還剩80頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

Chapter2對偶問題DualProblem1.線性規(guī)劃的對偶模型

DualModelofLP2.對偶性質(zhì)

Dualproperty3.對偶單純形法

DualSimplexMethod4.靈敏度分析

SensitivityAnalysis運籌學(xué)OperationsResearch在線性規(guī)劃問題中,存在一個有趣的問題,即每一個線性規(guī)劃問題都伴隨有另一個線性規(guī)劃問題,稱它為對偶線性規(guī)劃問題?!纠?.1】某企業(yè)用四種資源生產(chǎn)三種產(chǎn)品,工藝系數(shù)、資源限量及價值系數(shù)如下表:產(chǎn)品資源ABC資源限量Ⅰ986500Ⅱ547450Ⅲ832300Ⅳ764550每件產(chǎn)品利潤1008070

建立總收益最大的數(shù)學(xué)模型。【解】設(shè)x1,x2,x3分別為產(chǎn)品A,B,C的產(chǎn)量,則線性規(guī)劃數(shù)學(xué)模型為:現(xiàn)在從另一個角度來考慮企業(yè)的決策問題。假如企業(yè)自己不生產(chǎn)產(chǎn)品,而將現(xiàn)有的資源轉(zhuǎn)讓或出租給其它企業(yè),那么資源的轉(zhuǎn)讓價格是多少才合理?價格太高對方不愿意接受,價格太低本單位收益又太少。合理的價格應(yīng)是對方用最少的資金購買本企業(yè)的全部資源,而本企業(yè)所獲得的利潤不應(yīng)低于自己用于生產(chǎn)時所獲得的利潤。這一決策問題可用下列線性規(guī)劃數(shù)學(xué)模型來表示。這是一個線性規(guī)劃數(shù)學(xué)模型,稱這一線性規(guī)劃問題是前面生產(chǎn)計劃問題的對偶線性規(guī)劃問題或?qū)ε紗栴}。生產(chǎn)計劃的線性規(guī)劃問題稱為原始線性規(guī)劃問題或原問題?!纠?.2】某人根據(jù)醫(yī)囑,每天需補(bǔ)充A、B、C三種營養(yǎng),A不少于80單位,B不少于150單位,C不少于180單位。此人準(zhǔn)備每天從六種食物中攝取這三種營養(yǎng)成分。已知六種食物每百克的營養(yǎng)成分含量及食物價格如下表,試建立此人在滿足健康需要的基礎(chǔ)上花費最少的數(shù)學(xué)模型。

營養(yǎng)成分

六需要量80B24930251215≥150C1872134100≥180食物單價(元/100g)0.50.40.80.90.30.2

含量食物【解】設(shè)xj為每天第j種食物的用量,數(shù)學(xué)模型為現(xiàn)有一制藥廠要生產(chǎn)一種包含A、B、C三種營養(yǎng)成分的合成藥,如何制定價格,使得此藥既要暢銷又要產(chǎn)值最大。設(shè)yi(i=1,2,3)為第i種營養(yǎng)成分的單價,則由后面的對偶性質(zhì)可知:原問題和對偶問題的最優(yōu)值相等,故有即yi是第i種資源的變化率,說明當(dāng)其它資源供應(yīng)量bk(k≠i)不變時,bi增加一個單位時目標(biāo)值Z增加yi個單位。例如,第一種資源的影子價格為y1=2,第二種資源的影子價格為y2=2,即當(dāng)?shù)谝环N資源增加一個單位時,Z增加2個單位,當(dāng)?shù)诙N資源增加一個單位時,Z增加2個單位。企業(yè)可利用影子價格調(diào)節(jié)生產(chǎn)規(guī)模。例如,目標(biāo)函數(shù)Z表示利潤(或產(chǎn)值),當(dāng)?shù)趇種資源的影子價格大于零(或高于市場價格)時,表示有利可圖,企業(yè)應(yīng)購進(jìn)該資源擴(kuò)大生產(chǎn)規(guī)模,當(dāng)影子價格等于零(或低于市場價格),企業(yè)不能增加收益,這時應(yīng)將資源賣掉或出讓,縮小生產(chǎn)規(guī)模。應(yīng)當(dāng)注意,是在最優(yōu)基B不變的條件下有上述經(jīng)濟(jì)含義,當(dāng)某種資源增加或減少后,最優(yōu)基B可能發(fā)生了變化,這時yi的值也隨之變化。在例2.1中,原問題的最優(yōu)解X=(24.24,0,46.96)對偶問題的最優(yōu)解Y=(10.6,0.91,0,0)最優(yōu)值z=w=5712.12分析:1.y1=10.6說明在現(xiàn)有的資源限量的條件下,增加一個單位第一種資源可以給企業(yè)帶來10.6元的利潤;如果要出售該資源,其價格至少在成本價上加10.6元。2.y3=0說明增加第三種資源不會增加利潤,因為第三種資源還有沒有用完。問題:1.第三、四種資源的售價是多少,是否不值錢?2.如果要增加利潤,企業(yè)應(yīng)增加哪幾種資源,各增加多少后再進(jìn)行調(diào)整?【例2.3】寫出下列線性規(guī)劃的對偶問題【解】這是一個對稱形式的線性規(guī)劃,設(shè)Y=(y1,y2),則有從而對偶問題為對偶變量yi也可寫成xi的形式。【例2.4】寫出下列線性規(guī)劃的對偶問題【解】這是一個對稱形式的線性規(guī)劃,它的對偶問題求最小值,有三個變量且非負(fù),有兩個“≥”約束,即原問題(或?qū)ε紗栴})對偶問題(或原問題)目標(biāo)函數(shù)(max)目標(biāo)函數(shù)系數(shù)(資源限量)約束條件系數(shù)矩陣A(AT)目標(biāo)函數(shù)(min)資源限量(目標(biāo)函數(shù)系數(shù))約束條件系數(shù)矩陣ATA)變

量n個變量第j個變量≥0第j個變量≤0第j個變量無約束約

束n個約束第j個約束為≥第j個約束為≤第j個約束為=約

束m個約束第i個約束≤第i個約束≥第i個約束為=變

量m個變量第i個變量≥0第i個變量≤0第i個變量無約束表2-1【例2.5】寫出下列線性規(guī)劃的對偶問題【解】目標(biāo)函數(shù)求最小值,應(yīng)將表2-1的右邊看作原問題,左邊是對偶問題,原問題有3個約束4個變量,則對偶問題有3個變量4個約束,對照表2-1的對應(yīng)關(guān)系,對偶問題為:本節(jié)以實例引出對偶問題;介紹了如何寫對稱與非對稱問題的對偶問題;1.您應(yīng)該會寫任意線性規(guī)劃的對偶問題;2.深刻領(lǐng)會影子價格的含義,學(xué)會用影子價格作經(jīng)濟(jì)活動分析。作業(yè):教材P74T2.3(1)(2)TheEndofSection2.1對偶性質(zhì)Exit返回首頁它與下列線性規(guī)劃問題是等價的:再寫出它的對偶問題。它與下列線性規(guī)劃問題是等價的即是原問題。由表2-1知,它的對偶問題是3/14/2023【性質(zhì)2】弱對偶性設(shè)X°、Y°分別為(LP)與(DP)的可行解,則【證】因為X°、Y°是可行解,故有AX°≤b,X°≥0及Y°A≥C,Y°≥0,將不等式AX°≤b兩邊左乘Y°得Y°AX°≤Y°b再將不等式Y(jié)°A≥C兩邊右乘X°,故CX°≤Y°AX≤Y°b這一性質(zhì)說明了兩個線性規(guī)劃互為對偶時,求最大值的線性規(guī)劃的任意目標(biāo)值都不會大于求最小值的線性規(guī)劃的任一目標(biāo)值,不能理解為原問題的目標(biāo)值不超過對偶問題的目標(biāo)值。得CX°≤Y°AX°3/14/2023由這個性質(zhì)可得到下面幾個結(jié)論:(1)(LP)的任一可行解的目標(biāo)值是(DP)的最優(yōu)值下界;(DP)的任一可行解的目標(biāo)是(LP)的最優(yōu)值的上界;(2)在互為對偶的兩個問題中,若一個問題可行且具有無界解,則另一個問題無可行解;(3)若原問題可行且另一個問題不可行,則原問題具有無界解。注意上述結(jié)論(2)及(3)的條件不能少。一個問題有可行解時,另一個問題可能有可行解(此時具有無界解)也可能無可行解。3/14/2023【性質(zhì)3】最優(yōu)準(zhǔn)則定理設(shè)X°與Y°分別是(LP)與(DP)的可行解,則當(dāng)X°、Y°是(LP)與(DP)的最優(yōu)解當(dāng)且僅當(dāng)CX°=Y°b.【證】若X°、Y°為最優(yōu)解,B為(LP)的最優(yōu)基,則有Y°=CBB-1,并且當(dāng)CX°=Y°b時,由性質(zhì)1,對任意可行解有即Y°b是(DP)中任一可行解的目標(biāo)值的下界,CX°是(LP)中任一可行解的目標(biāo)值的上界,從而X°、Y°是最優(yōu)解。3/14/2023【性質(zhì)4】還可推出另一結(jié)論:若(LP)與(DP)都有可行解,則兩者都有最優(yōu)解,若一個問題無最優(yōu)解,則另一問題也無最優(yōu)解。【證】設(shè)(LP)有最優(yōu)解X°,那么對于最優(yōu)基B必有C-CBB-1A≤0與-CBB-1≤0,即有Y°A≥C與Y°≥0,這里Y°=CBB-1,從而Y°是可行解,對目標(biāo)函數(shù)有由性質(zhì)3知Y°是最優(yōu)解。由性質(zhì)4還可推出另一結(jié)論:若(LP)與(DP)都有可行解,則兩者都有最優(yōu)解,若一個問題無最優(yōu)解,則另一問題也無最優(yōu)解。3/14/2023性質(zhì)5告訴我們已知一個問題的最優(yōu)解時求另一個問題的最優(yōu)解的方法,即已知Y°求X°或已知X°求Y°。Y°XS=0和YSX°=0兩式稱為互補(bǔ)松弛條件。將互補(bǔ)松弛條件寫成下式由于變量都非負(fù),要使求和式等于零,則必定每一分量為零,因而有下列關(guān)系:3/14/2023(1)當(dāng)yi°>0時,,反之當(dāng)時yi°=0;注意:對于非對稱形式,性質(zhì)5的結(jié)論仍然有效?!纠?.6】已知線性規(guī)劃的最優(yōu)解是,求對偶問題的最優(yōu)解。3/14/2023的最優(yōu)解是,求對偶問題的最優(yōu)解?!窘狻繉ε紗栴}是因為X1≠0,X2≠0,所以對偶問題的第一、二個約束的松弛變量等于零,即解此線性方程組得y1=1,y2=1,從而對偶問題的最優(yōu)解為Y=(1,1),最優(yōu)值w=26。3/14/2023【例2.7】已知線性規(guī)劃的對偶問題的最優(yōu)解為Y=(0,-2),求原問題的最優(yōu)解?!窘狻繉ε紗栴}是由y2≠0得=0,由得x2=0,原問題的約束條件變?yōu)?解此方程組得原問題最優(yōu)解:X=(-5,0,-1)T,minZ=-12。3/14/2023【例2.8】證明下列線性規(guī)劃無最優(yōu)解:【證】容易看出X=(4,0,0)是一可行解,故問題可行。對偶問題將三個約束的兩端分別相加得,而第二個約束有y2≥1,矛盾,故對偶問題無可行解,因而原問題為無界解,即無最優(yōu)解。3/14/2023【性質(zhì)6】(LP)的檢驗數(shù)的相反數(shù)對應(yīng)于(DP)的一組基本解.其中第j個決策變量xj的檢驗數(shù)的相反數(shù)對應(yīng)于(DP)中第j個松弛變量的解,第i個松弛變量的檢驗數(shù)的相反數(shù)對應(yīng)于第i個對偶變量yi的解。反之,(DP)的檢驗數(shù)(注意:不乘負(fù)號)對應(yīng)于(LP)的一組基本解。證明略。3/14/2023【例2.9】線性規(guī)劃(1)用單純形法求最優(yōu)解;(2)寫出每步迭代對應(yīng)對偶問題的基本解;(3)從最優(yōu)表中寫出對偶問題的最優(yōu)解;(4)用公式Y(jié)=CBB-1求對偶問題的最優(yōu)解?!窘狻浚?)加入松弛變量x4、x5后,單純形迭代如表2-2所示。3/14/2023表2-2XBx1x2x3x4x5b(1)x4x52*1-102410012→4λj6↑-2100

(2)x1x510-1/21/2*131/2-1/20113→λj01↑-5-30

(3)x1x21001460-11246λj00-11-2-2

3/14/2023最優(yōu)解X=(4,6,0),最優(yōu)值Z=6×4-2×6=12;(2)設(shè)對偶變量為y1、y2,松弛變量為y3、y4、y5,Y=(y1、y2、y3、y4、y5),由性質(zhì)6得到對偶問題的基本解(y1、y2、y3、y4、y5)=(-λ4,-λ5,-λ1,-λ2,-λ3),即表2-2(1)中λ=(6,-2,1,0,0),則Y(1)=(0,0,-6,2,-1)表2-2(2)中λ=(0,1,-5,-3,0),則Y(2)=(3,0,0,-1,5)表2-2(3)中λ=(0,0,-11,-2,-2),則Y(3)=(2,2,0,0,11)3/14/2023(1)因為表2-2(3)為最優(yōu)解,故

Y(3)=(2,2,0,0,11)為對偶問題最優(yōu)解;(1)表2-2(3)中的最優(yōu)基

B-1為表2-2(3)中x4,x5兩列的系數(shù),即CB=(6,-2),因而3/14/2023本節(jié)您學(xué)了六個對偶性質(zhì);這些性質(zhì)是研究原問題與對偶問題解的對應(yīng)關(guān)系;表2-3也許對您了解這些性質(zhì)有幫助。表2-3一個問題max另一個問題min有最優(yōu)解有最優(yōu)解性質(zhì)4無最優(yōu)解無最優(yōu)解無最優(yōu)解性質(zhì)4無界解(有可行解)無可行解性質(zhì)2無可行解無界解(有可行解)應(yīng)用已知最優(yōu)解通過解方程求最優(yōu)解性質(zhì)5已知檢驗數(shù)檢驗數(shù)乘以-1求得基本解性質(zhì)63/14/2023試一試:判斷下列結(jié)論是否正確,如果不正確,應(yīng)該怎樣改正?1.任何線性規(guī)劃都存在一個對應(yīng)的對偶線性規(guī)劃.2.原問題第i個約束是“≤”約束,則對偶變量yi≥0.3.互為對偶問題,或者同時都有最優(yōu)解,或者同時都無最優(yōu)解.4.對偶問題有可行解,則原問題也有可行解.5.原問題有多重解,對偶問題也有多重解.6.對偶問題有可行解,原問題無可行解,則對偶問題具有無界解.7.原問題無最優(yōu)解,則對偶問題無可行解.8.若某種資源影子價格為零,則該資源一定有剩余.9.對偶問題不可行,原問題可能無界解.10.原問題與對偶問題都可行,則都有最優(yōu)解.11.原問題具有無界解,則對偶問題不可行.12.對偶問題具有無界解,則原問題無最優(yōu)解.13.若X*、Y*是原問題與對偶問題的最優(yōu)解,則X*=Y*.14.在資源優(yōu)化的線性規(guī)劃問題中,若某一資源有剩余,則該資源影子價格為零.

3/14/2023作業(yè):教材P75T2.4、2.6、2.5TheEndofSection2.2對偶單純形法Exit3/14/2023設(shè)原問題是(記為LP):對偶問題是(記為DP):根據(jù)對偶性質(zhì)6,可以構(gòu)造一個求線性規(guī)劃的另一種方法,即對偶單純形法。對偶單純形法的計算步驟:對偶單純形法的條件是:初始表中對偶問題可行,即極大化問題時λj≤0,極小化問題時λj≥0。3/14/2023(1)將線性規(guī)劃的約束化為等式,求出一組基本解,因為對偶問題可行,即全部檢驗數(shù)λj≤0(max)或λj≥0(min),當(dāng)基本解可行時,則達(dá)到最優(yōu)解;若基本解不可行,即有某個基變量的解bi<0,則進(jìn)行換基計算;(2)先確定出基變量。行對應(yīng)的變量xl出基;(3)再選進(jìn)基變量。求最小比值(4)求新的基本解,用初等變換將主元素alk化為l,k列其它元素化為零,得到新的基本解,轉(zhuǎn)到第一步重復(fù)運算。3/14/2023【例2.10】用對偶單純形法求解【解】先將約束不等式化為等式,再兩邊同乘以(-1),得到用對偶單純形法,迭代過程如下頁或看演示(請啟用宏)。3/14/2023表2-43/14/2023應(yīng)當(dāng)注意:(1)用對偶單純形法求解線性規(guī)劃是一種求解方法,而不是去求對偶問題的最優(yōu)解;(2)初始表中一定要滿足對偶問題可行,也就是說檢驗數(shù)滿足最優(yōu)判別準(zhǔn)則;(3)最小比值中的絕對值是使得比值非負(fù),在極小化問題時λj≥0,分母aij<0這時必須取絕對值。在極大化問題中,λ≤j0分母aij<0,總滿足非負(fù),這時絕對值符號不起作用,可以去掉。如在本例中將目標(biāo)函數(shù)寫成這里λj≤0在求θk時就可以不帶絕對值符號。3/14/2023(4)對偶單純形法與普通單純形法的換基順序不一樣,普通單純形法是先確定進(jìn)基變量后確定出基變量,對偶單純形法是先確定出基變量后確定進(jìn)基變量;(5)普通單純形法的最小比值是其目的是保證下一個原問題的基本解可行,對偶單純形法的最小比值是其目的是保證下一個對偶問題的基本解可行;(6)對偶單純形法在確定出基變量時,若不遵循規(guī)則,任選一個小于零的bi對應(yīng)的基變量出基,不影響計算結(jié)果,只是迭代次數(shù)可能不一樣。3/14/2023【例2.12】用對偶單純形法求解求解過程見演示(鏈接到Excel文件,需啟用宏)。3/14/2023例2.12可用性質(zhì)6及性質(zhì)2來說明,表(2)的第2行對應(yīng)于對偶問題的第2列(相差一個負(fù)號),檢驗數(shù)行對應(yīng)于對偶問題的常數(shù)項(相差一個負(fù)號),比值對應(yīng)于對偶問題的比值失效也說明即對偶問題具有無界解,由性質(zhì)2知原問題無可行解。3/14/2023本節(jié)利用對偶性質(zhì)6:原問題的檢驗數(shù)與對偶問題的基本解的對應(yīng)關(guān)系,介紹了一種特殊線性規(guī)劃的求解方法—對偶單純形法。1.對偶單純形法的應(yīng)用條件;2.出基與進(jìn)基的順序;3.如何求最小比值;4.最優(yōu)解、無可行解的判斷。作業(yè):教材P76T2.7TheEndofSection3靈敏度分析Exit3/14/2023線性規(guī)劃的靈敏度分析也稱為敏感性分析,它是研究和分析參數(shù)(cj,bi,aij)的波動對最優(yōu)解的影響程度,主要研究下面兩個方面:(1)參數(shù)在什么范圍內(nèi)變化時,原最優(yōu)解或最優(yōu)基不變;(2)當(dāng)參數(shù)已經(jīng)變化時,最優(yōu)解或最優(yōu)基有何變化。當(dāng)模型的參數(shù)發(fā)生變化后,可以不必對線性規(guī)劃問題重新求解,而用靈敏度分析方法直接在原線性規(guī)劃取得的最優(yōu)結(jié)果的基礎(chǔ)上進(jìn)行分析或求解,既可減少計算量,又可事先知道參數(shù)的變化范圍,及時對原決策作出調(diào)整和修正。2.4.1價值系數(shù)cj的變化分析為使最優(yōu)解不變,求cj的變化范圍。3/14/2023設(shè)線性規(guī)劃其中Am×n,線性規(guī)劃存在最優(yōu)解,最優(yōu)基的逆矩陣為檢驗數(shù)為要使最優(yōu)解不變,即當(dāng)cj變化為后,檢驗數(shù)仍然是小于等于零,即這時分cj是非基變量和基變量的系數(shù)兩種情況討論。3/14/2023一、cj是非基變量xj的系數(shù)即cj的增量不超過cj的檢驗數(shù)的相反數(shù)時,最優(yōu)解不變,否則最優(yōu)解就要改變。所以3/14/2023二、ci是基變量xi的系數(shù)因ci∈CB,所以每個檢驗數(shù)λj中含有ci,當(dāng)ci變化為ci+后λj同時變化,這時令令3/14/2023要使得所有,則有【例2.13】線性規(guī)劃(1)求最優(yōu)解;(2)分別求c1,c2,c3的變化范圍,使得最優(yōu)解不變。3/14/2023【解】(1)加入松弛變量x4,x5,x6,用單純形法求解,最優(yōu)表如表2-6所示。表2-6Cj113000bCBXBx1x2x3x4x5x60x40-201-1-151x111001-153x301100115λj0-300-1-2

最優(yōu)解X=(5,0,15);最優(yōu)值Z=50。3/14/2023(2)x2為非基變量,x1、x3為基變量,則c2變化范圍是:對于c1:表2-6是x1對應(yīng)行的系數(shù)只有一個負(fù)數(shù),有兩個正數(shù)c1的變化范圍是:3/14/2023對于c3:表2-6中x3對應(yīng)行Δc3無上界,即有Δc3≥-2,c3的變化范圍是。3/14/2023對c3的變化范圍,也可直接從表2-6推出,將c3=3寫成分別計算非基變量的檢驗數(shù)并令其小于等于零。3/14/2023得Δc3≥-2,同理,用此方法可求出c2和c1的變化區(qū)間。,要使、同時小于等于零,解不等式組2.4.2資源限量bi變化分析為了使最優(yōu)基B不變,求bi的變化范圍。設(shè)br的增量為Δbr,b的增量為原線性規(guī)劃的最優(yōu)解為X,基變量為XB=B-1b,要使最優(yōu)基B不變,即要求,3/14/2023因為3/14/2023所以當(dāng)令3/14/2023因而要使得所有必須滿足這個公式與求的上、下限的公式類似,比值的分子都小于等于零,分母是B-1中第r列的元素,大于等于比值小于零的最大值,小于等于比值大于零的最小值。當(dāng)某個時,可能上界或無下界。【例2.14】求例2.13的b1,b2,b3分別在什么范圍內(nèi)變化時,原最優(yōu)基不變。3/14/2023【解】解:由表2-6知,最優(yōu)基B、B-1及分別為對于b1:比值的分母取B-1的第一列,這里只有β11=1,而β21=β31=0,則3/14/2023Δb1無上界,即Δb1≥-5,因而b1在內(nèi)變化時最優(yōu)基不變。對于b2:比值的分母取B-1的第二列,,則即b2在[15,25]上變化時最優(yōu)基不變。3/14/2023對于b3:比值的分母取B-1的第三列,有故有在[0,20]上變化時最優(yōu)基不變。靈敏度分析方法還可以分析工藝系數(shù)aij的變化對最優(yōu)解的影響,對增加約束、變量或減少約束、變量等情形的分析,下面以一個例子來說明這些分析方法。若線性規(guī)劃模型是一個生產(chǎn)計劃模型,當(dāng)求出cj或bi的最大允許變化范圍時,就可隨時根據(jù)市場的變化來掌握生產(chǎn)計劃的調(diào)整。3/14/2023【例2.15】考慮下列線性規(guī)劃求出最優(yōu)解后,分別對下列各種變化進(jìn)行靈敏度分析,求出變化后的最優(yōu)解。(1)將目標(biāo)函數(shù)改為;(1)改變右端常數(shù)為:3/14/2023(3)改變目標(biāo)函數(shù)x3的系數(shù)為c3=1;(4)改變目標(biāo)函數(shù)中x2的系數(shù)為c2=2;(5)改變x2的系數(shù)為(6)改變約束(1)為(7)增加新約束(8)增加新約束3/14/2023【解】加入松弛變量x4、x5、x6,用單純形法計算,最優(yōu)表如2-7所示。表2-7Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/70-1/74/7010x60-200-111λj0-31/70-2/7-20/70

3/14/2023最優(yōu)解X=(1,0,2,0,0,1),最優(yōu)值Z=10,最優(yōu)基(1)等價于,即將cj改變?yōu)椋ǎ?,1,-4),其中c1=-2、c3=-4是基變量的系數(shù),c2=1是非基變量的系數(shù),求得檢驗數(shù)3/14/2023這里表2-7的解不是最優(yōu),將上述檢驗數(shù)代替表2-7的檢驗數(shù),再單純形法繼續(xù)迭代,計算結(jié)果如表2-8所示。3/14/2023表2-8cj-21-4000bCBXBx1x2x3x4x5x6-4x305/711/73/702-2x112/70-1/74/7010x60-200-111λj031/702/720/70

1x2017/51/53/5014/5-2x110-2/5-1/52/501/50x60014/52/51/5033/5λj00-31/5-3/51/50

1x2-3/2121/2005/20x55/20-1-1/2101/20x6-1/2031/20113/2λj-1/20-6-1/200

3/14/2023最優(yōu)解(2)基變量的解為基本解不可行,將求得的XB代替表2-7中的常數(shù)項,用對偶單純形法求解,其結(jié)果見表2-9所示。3/14/2023表2-9Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022/72x112/70-1/74/706/70x60-200-11-2λj0-31/70-2/7-20/70

4x30011/71/145/1417/72x1100-1/73/71/74/7-1x201001/2-1/21λj000-2/7-9/14-31/14

3/14/2023最優(yōu)解(3)由表2-7容易得到基變量x3的系數(shù)c3的增量變化范圍是,而c3=1在允許的變化范圍之外,故表2-7的解不是最優(yōu)解。非基變量的檢驗數(shù)x4進(jìn)基,用單純形法計算,得到表2-10。3/14/2023表2-10XBx1x2x3x4x5x6

bx305/711/73/702x112/70-1/74/701x60-200-111λj0-16/701/7-11/70

x405713014x11110103x60-200-111λj0-3-10-20

最優(yōu)解為X=(3,0,0,14,0,1)‘,最優(yōu)值z=6。3/14/2023(4)c2是非基變量x2的系數(shù),由表2-11知,由-1變?yōu)?時,或直接求出x2的檢驗數(shù)從而最優(yōu)解不變,即X=(1,0,2,0,0,1)。3/14/2023(5)這時目標(biāo)函數(shù)的系數(shù)和約束條件的系數(shù)都變化了,同樣求出λ2判別最優(yōu)解是否改變。x2進(jìn)基,計算結(jié)果如表2-11所示3/14/2023表2-11Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11-10-1/74/7010x60300-111λj050-2/7-20/70

x30011/73/702

x1100-1/75/211/34/3

x20100-1/31/3

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論