,.第二章對偶問題一、選擇1.如果原問題有最優(yōu)解，則其對偶問題也一定具有最優(yōu)解，且有（A）。感謝閱讀AmaxZ=minWBmaxZ<minWCmaxZ>minWDmaxZ與minW無關(guān)精品文檔放心下載2.影子價格Y*cB1是（C）BA、對偶可行解 B、對偶基本可行解 C、對偶最優(yōu)解 D無可精品文檔放心下載行解3．原問題有可行解，其對偶問題有非可行解，則目標(biāo)函數(shù)值（B）A、最優(yōu)B、zzC、z>zD無可行maxmax解4.影子價格是一種（C）A、實際價格

B、市場價格

C、邊際價格

D產(chǎn)品價格資源的市場價格是已知數(shù)，相對比較穩(wěn)定，而它的影子價格則有賴于（c），是未知感謝閱讀數(shù)A 市場的定價 B買賣的多少 C 資源的利用情況 D購感謝閱讀買力6.如果原問題（對偶問題）具有無界解，則其對偶問題（原問題）（D）。感謝閱讀,.A唯一最優(yōu)解B無窮多最優(yōu)解C無界解D無可行解謝謝閱讀影子價格是一種邊際價格，實際上又是一種（A）。A機(jī)會成本B實際成本C市場價格D產(chǎn)品價格精品文檔放心下載9.如果x(j1,,n)是原問題的可行解，y(j1,,m)是其對偶問題的可行解，ji則恒有（A）nmnmnmD無AcxbyBcxbyCcxbyjjiijjiijjiij1i1j1i1j1i1法確定10.如果x(j1,,n)是原問題的可行解，y(j1,,m)是其對偶問題的可行ji解，且有（B），則x(j1,,n)是原問題的最優(yōu)解，y(j1,,m)是其對偶問ji題的最優(yōu)解nmnmAcxbyBcxbyjjiijjiij1i1j1i1nmCcxbyDxyjjiijij1i1n11.如果y0,則axb，其符合（D）定理iijjij1A強(qiáng)對偶性B弱對偶性C最優(yōu)性D互補(bǔ)松弛性感謝閱讀12.如果有mayc,則x0，其符合（D）定理謝謝閱讀ijijji1A強(qiáng)對偶性B弱對偶性C最優(yōu)性D互補(bǔ)松弛性精品文檔放心下載m13.如果x0,則ayc，其符合（D）定理jijiji1A強(qiáng)對偶性B弱對偶性C最優(yōu)性D互補(bǔ)松弛性謝謝閱讀,.14.如果有naxb,則y0，其符合（D）定理感謝閱讀ijjiij1A強(qiáng)對偶性B弱對偶性C最優(yōu)性D互補(bǔ)松弛性謝謝閱讀15.在單純形法中，最終單純形表，原問題的變量對應(yīng)著對偶問題的（A）感謝閱讀A松弛變量B剩余變量C變量D最優(yōu)解在單純形法中，最終單純形表，原問題的松弛變量對應(yīng)著對偶問題的（C）A松弛變量B剩余變量C變量D最優(yōu)解精品文檔放心下載在單純形法中，最終單純形表中，對偶問題的最優(yōu)解由（B）的值組成。感謝閱讀AB-CczD0jjjj靈敏度分析是指對系統(tǒng)或事物因周圍條件變化顯示出來的（A）的分析。A敏感程度B特性C解D狀態(tài)感謝閱讀在敏感性分析中，將參數(shù)變化反應(yīng)到最終單純形表中，原問題與對偶問題都是可行解，則（A）謝謝閱讀A此解仍為問題最優(yōu)解B用單純形法繼續(xù)計算C用對偶單純形法繼續(xù)計算D用人工變量法繼續(xù)計算感謝閱讀靈敏度分析中，增加一個變量在實際問題中反映為增加（B）A一道工序B一種產(chǎn)品C一個約束條件D一個目標(biāo)函數(shù)謝謝閱讀原問題中求目標(biāo)函數(shù)極大化，對偶問題中為求目標(biāo)函數(shù)（A）A極小化B極大化C極值D不能確定精品文檔放心下載原問題中約束條件個數(shù)等于對偶問題中（B）A約束條件個數(shù)B變量個數(shù)C價值系數(shù)個數(shù)D技術(shù)系數(shù)個數(shù)感謝閱讀原問題中變量個數(shù)等于對偶問題中（A）A約束條件個數(shù)B變量個數(shù)C價值系數(shù)個數(shù)D技術(shù)系數(shù)個數(shù)精品文檔放心下載,.24.原問題中約束條件符號為小于等于，對偶問題中約束條件符號為（C）精品文檔放心下載A等于B小于等于C大于等于D大于25.原問題目標(biāo)函數(shù)的系數(shù)是其對偶問題的（D）A目標(biāo)函數(shù)的系數(shù)B價值系數(shù)C技術(shù)系數(shù)D約束條件右端項謝謝閱讀26.原問題約束條件的右端項則是其對偶問題（Ａ ）A目標(biāo)函數(shù)的系數(shù)B價值系數(shù)C技術(shù)系數(shù)D約束條件右端項精品文檔放心下載27.原問題某個約束條件為等式，那么對偶問題相應(yīng)的變量為（D）謝謝閱讀A等于B小于等于C大于等于D自由28.原問題與對偶問題互為對偶，稱為（C）A弱對偶性B強(qiáng)對偶性C對稱性D互補(bǔ)松弛性謝謝閱讀用單純形法求解線性規(guī)劃問題時，在得到原問題的一個基可行解的同時，得到對偶問題的一個（A）。精品文檔放心下載A基解B最優(yōu)解C可行解D非可行解資源的影子價格是買主（B）A最高出價B最低出價C期望價格D市場價格。感謝閱讀,.二、填空1.如果對偶問題具有（無界解），則其原問題無可行解。謝謝閱讀,n)是原問題的可行解，y(j1,,m)是其對偶問題的可行2..如果x(j1,jinm解，則恒有cxby，則此定理稱為（弱對偶性）j1jji1ii,n)是原問題的可行解，y(j1,,m)是其對偶問題的可行3.如果x(j1,jinm解，且有cxby，則x(j1,,n)是原問題的最優(yōu)解，y(j1,,m)jjiijij1i1是其對偶問題的最優(yōu)解，此定理稱為（最優(yōu)性）如果原問題有最優(yōu)解，則其對偶問題也一定具有最優(yōu)解，且有maxZ=minW，此定理稱為（強(qiáng)對偶性）。謝謝閱讀5.在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對應(yīng)的對偶變量一定為零。此定理為（互補(bǔ)松弛性定理）謝謝閱讀6.在線性規(guī)劃問題的對偶問題中，may是生產(chǎn)某種產(chǎn)品所消耗各項資源的影感謝閱讀i1iji子價格的總和，即（產(chǎn)品的隱含成本）7.對線性規(guī)劃問題的求解是確定資源的（最優(yōu)分配方案），而對于對偶問題的求感謝閱讀解則是確定對資源的（恰當(dāng)估價）。8.靈敏度分析中，增加（一個變量）在實際問題中反映為增加一種新的產(chǎn)品。精品文檔放心下載靈敏度分析中，增加（一個約束條件）在實際問題中反映為增加一道工序。精品文檔放心下載,.12.在實際問題中需要研究當(dāng)參數(shù)值連續(xù)變化時，問題的最優(yōu)解如何隨參數(shù)值變化而變化，這樣的問題需要用到（參數(shù)線性規(guī)劃）理論。精品文檔放心下載13.原問題的(變量的個數(shù))對應(yīng)著對偶問題的約束條件的個數(shù)感謝閱讀14.原問題變量的不等式的符號，正對應(yīng)著對偶問題的（約束條件）不等式的符號。感謝閱讀15.原問題約束條件的(右端項)，對應(yīng)著對偶問題目標(biāo)函數(shù)中變量的系數(shù)。感謝閱讀16.原問題的約束條件的不等式符號，（反）對應(yīng)著對偶問題變量的不等式符號。感謝閱讀17.原問題的變量為無約束，對應(yīng)著對偶問題的約束條件是（等式）感謝閱讀18.19.在對偶問題的基本性質(zhì)中，強(qiáng)對偶性應(yīng)用（夾逼定理）進(jìn)行推導(dǎo)。感謝閱讀20.靈敏度分析中，如果市場條件發(fā)生變化，那么反映到線性規(guī)劃模型中是精品文檔放心下載（c 值）發(fā)生變化。j21.對偶約束的經(jīng)濟(jì)解釋就是（產(chǎn)品機(jī)會成本）。22.用單純形法求解線性規(guī)劃問題時，在得到原問題的一個基可行解的同時，在（檢驗數(shù)行）得到對偶問題的一個基解。謝謝閱讀23.原問題的影子價格是當(dāng)該資源增加1單位時引起的（總收入的增量）。謝謝閱讀24.原問題的影子價格是賣主的（內(nèi)控價格）。25.影子價格反映了資源的稀缺性，影子價格越高，則（越稀缺）。謝謝閱讀26.在利潤最大化的生產(chǎn)計劃中，安排生產(chǎn)的產(chǎn)品機(jī)會成本（等于）利潤。感謝閱讀則（n27.互補(bǔ)松弛性定理中，如果y0,axb）iijjij1n）28.互補(bǔ)松弛性定理中，如果axb，則（y0ijjiij1,.0,則（m29.互補(bǔ)松弛性定理中，如果xayc）jijiji1m0)30.互補(bǔ)松弛性定理中，如果ayc，則(xi1ijijj三、判斷1.任何線性規(guī)劃問題存在并具有唯一的對偶問題。（正確）感謝閱讀2.對偶問題的對偶問題一定是原問題。（正確）3.若某種資源的影子價格等于k，在其他條件不變的情況下，當(dāng)某種資源增加5感謝閱讀個單位時，相應(yīng)的目標(biāo)函數(shù)值將增大5k。（不正確）在線性規(guī)劃問題中，對偶變量yi的意義代表一個單位第i種資源的估價。（正確）精品文檔放心下載5.對偶單純形法必須首先化為對偶形式才能進(jìn)行（不正確）精品文檔放心下載對偶問題的性質(zhì)中，無界性指如果原問題具有無界解，則其對偶問題無可行解（正確）感謝閱讀7.影子價格在市場上是已知的。（不正確）8.機(jī)會成本是一個實際的成本。（不正確）在對偶問題的互補(bǔ)松弛性定理中，有naxb,則y0，表明生產(chǎn)過程中謝謝閱讀ijjiij1如果某種資源b 未得到充分利用時，該種資源的影子價格為零。(正確)感謝閱讀i10.在對偶問題的互補(bǔ)松弛性定理中，有y0,則naxb，表明當(dāng)資源的謝謝閱讀iijjij1影子價格不為零時，表明該種資源生產(chǎn)中已經(jīng)耗費(fèi)完畢。（正確）精品文檔放心下載11.對偶單純形法使用的前提是有一個基，其對應(yīng)的基本解滿足，單純形表的檢謝謝閱讀驗數(shù)行全部非正。（不正確）,.對偶單純形法使用的前提是有一個基，其對應(yīng)的基本解滿足，單純形表的變量取值可有負(fù)數(shù)。（不正確）感謝閱讀對偶單純形法使用的前提是有一個基，其對應(yīng)的基本解滿足，單純形表的檢驗數(shù)行全部非正；變量取值可有負(fù)數(shù)。（正確）精品文檔放心下載14.對偶單純形法的計算時，先確定換入基的變量。（不正確）謝謝閱讀15.對偶單純形法的計算時，直到b0時，計算結(jié)束。（正確）精品文檔放心下載r對偶單純形法的計算時，若b0，a0時，則原問題無可行解，對偶問謝謝閱讀r kj題也為無可行解。（不正確）對偶單純形法的計算時，若b0，a0時，則原問題無可行解，對偶問精品文檔放心下載r kj題也為無界解。（正確）18.靈敏度分析是研究使問題的最優(yōu)解或最優(yōu)基保持不變時的參數(shù)值變化范圍。感謝閱讀（正確）19．在互為的一對原問題與對偶問題中，不管原問題是求極大或極小，原問題感謝閱讀可行解的目標(biāo)函數(shù)值一定不超過其對偶問題可行解的目標(biāo)函數(shù)值。（不正確）謝謝閱讀20.21.機(jī)會成本表示減少一件產(chǎn)品所節(jié)省的資源可以增加的利潤。（正確）感謝閱讀22.機(jī)會成本在經(jīng)濟(jì)學(xué)上是一種即虛即實的一種成本。（正確）謝謝閱讀23.機(jī)會成本是指一筆投資在專注于某一方面后所失去的在另外其他方面的投資精品文檔放心下載獲利機(jī)會。（正確）24.在純市場經(jīng)濟(jì)條件下，當(dāng)市場價格低于影子價格的時候，可以賣出這種資源。精品文檔放心下載（不正確）在純市場經(jīng)濟(jì)條件下，當(dāng)市場價格高于影子價格的時候，可以買進(jìn)這種資源。（不正確）感謝閱讀,.26.在線性規(guī)劃問題中，當(dāng)市場條件發(fā)生變化時，a 值就會變化。（不正確）謝謝閱讀ij在線性規(guī)劃問題中，b值則是根據(jù)資源投入后能產(chǎn)生多大經(jīng)濟(jì)效果來決定謝謝閱讀i的一種決策選擇。（正確）28.在靈敏度分析中，當(dāng)原問題和對偶問題都為非可行解時，用兩階段方法，編謝謝閱讀制新的單純形表重新計算。（不正確）在求解對偶問題的最優(yōu)解的時候，可以通過原問題的單純形表的終表求得。（正確）謝謝閱讀30.31.影子價格是對偶規(guī)劃解的一個經(jīng)濟(jì)學(xué)解釋，它能夠告訴決策者，在現(xiàn)有生精品文檔放心下載產(chǎn)情況下，哪種資源最為關(guān)鍵？企業(yè)以什么樣的價格買進(jìn)或賣出某種資源才是合謝謝閱讀適的。（正確）四、名詞解釋1.弱對偶性：如果x(j1,,n)是原問題的可行解，y(j1,,m)是其對偶問jinm題的可行解，則恒有cxby，則此定理稱為弱對偶性。j1jji1ii2.最優(yōu)性：如果x(j1,,n)是原問題的可行解，y(j1,,m)是其對偶問題jinm是原問題的最優(yōu)解，的可行解，且有cxby，則x(j1,,n)jjiijy(j1,,m)是其對偶問題的最優(yōu)解，此定理稱為最優(yōu)性。謝謝閱讀i3.無界性：如果原問題（對偶問題）具有（無界解），則其對偶問題（原問題）精品文檔放心下載無可行解。4.強(qiáng)對偶性：如果原問題有最優(yōu)解，則其對偶問題也一定具有最優(yōu)解，且有感謝閱讀maxZ=minW，此定理稱為強(qiáng)對偶性。5.對偶定理：如果原問題有最優(yōu)解，則其對偶問題也一定具有最優(yōu)解，且有maxZ=minW，此定理稱為對偶定理。精品文檔放心下載6.互補(bǔ)松弛性：在線性規(guī)劃問題的最優(yōu)解中，如果對應(yīng)某一約束條件的對偶變量感謝閱讀,.值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對謝謝閱讀應(yīng)的對偶變量一定為零。此定理為互補(bǔ)松弛性定理。7.基解的互補(bǔ)性：線性規(guī)劃的原問題及其對偶問題之間存在一對互補(bǔ)的基解，其謝謝閱讀中原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變精品文檔放心下載量；這些互相對應(yīng)的變量如果在一個問題的解中是基變量，則在另一問題的解中感謝閱讀是非基變量；將這對互補(bǔ)的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有zw。8.影子價格：在單純形法的每步迭代中有目標(biāo)函數(shù)zncxmby，y的感謝閱讀jjiiij1i1據(jù)資源在生產(chǎn)中做出的貢獻(xiàn)而作的估價，為區(qū)別起見，稱為影子價格。精品文檔放心下載機(jī)會成本是由于資源的稀缺性，考慮了某種用途，就失去了其他被使用而創(chuàng)造價值的機(jī)會，在所有這些其他可能被利用的機(jī)會中，把能獲取最大價值作為項目方案使用這種資源的成本，稱為機(jī)會成本。精品文檔放心下載產(chǎn)品的隱含成本：從影子價格的含義上來考察單純形法的計算。有精品文檔放心下載cCB1Pcmay，其中may是生產(chǎn)一個單位該種產(chǎn)品所消耗各項資ijBjjijiijii1i1源的影子價格的總和，即產(chǎn)品的隱含成本。11.對偶單純形法：則是將單純形法應(yīng)用于對偶問題的計算，基本思想是保持對感謝閱讀偶問題為可行解（這時一般原問題為非可行解）的基礎(chǔ)上，通過迭代，減小目標(biāo)感謝閱讀函數(shù)，當(dāng)原問題也達(dá)到可行解時，即得到了目標(biāo)函數(shù)的最優(yōu)值。感謝閱讀靈敏度分析：是指對系統(tǒng)或事物因周圍條件變化顯示出來的敏感程度的分析。精品文檔放心下載參數(shù)線性規(guī)劃：在實際的線性規(guī)劃問題中，往往需要研究當(dāng)參數(shù)值連續(xù)變化時，問題的最優(yōu)解如何隨參數(shù)值的變化而變化，此類問題為參數(shù)線性規(guī)劃。謝謝閱讀邊際價格是指在其他條件不變的前提下，廠商增加一單位要素投入所增加的產(chǎn)品的價值精品文檔放心下載,.四、簡答1.線性規(guī)劃的原問題與對偶問題的表達(dá)式(一般形式)謝謝閱讀原問題ncxmaxz=j1jjnbiax(=1,…,m)ijjij1s.t.x0(j=1,…,n)j對偶問題mminbyiii1myc(j=1,…,n)aijiji1s.t.y0(i=1,…,m)i2.對偶單純形法的基本思想是什么？答：對偶單純形法基本思想是保持對偶問題為可行解（這時一般原問題為非可行精品文檔放心下載,.解）的基礎(chǔ)上，通過迭代，減小目標(biāo)函數(shù)，當(dāng)原問題也達(dá)到可行解時，即得到了目標(biāo)函數(shù)的最優(yōu)值。感謝閱讀3.影子價格的經(jīng)濟(jì)含義？答：影子價格是對現(xiàn)有資源實現(xiàn)最大效益時的一種估價；影子價格表明資源增加對總效益產(chǎn)生的影響。影子價格不是固定不變的，當(dāng)約束條件、產(chǎn)品利潤等發(fā)生變化時，有可能使影子價格發(fā)生變化。這可以通過靈敏度分析討論。感謝閱讀4.對偶問題的基本性質(zhì)有哪些？1）弱對偶性2）最優(yōu)性3）無界性4）強(qiáng)對偶性5）互補(bǔ)松弛性6）線性規(guī)劃的原問題及其對偶問題之間存在一對互補(bǔ)的基解，其中原問題的松弛變量對應(yīng)對偶問題的變量，對偶問題的剩余變量對應(yīng)原問題的變量；這些互相對應(yīng)的變量如果在一個問題的解中是基變量，則在另一個問題的解中是非基變量；將這對互補(bǔ)的基解分別代入原問題和對偶問題的目標(biāo)函數(shù)有z=w精品文檔放心下載5.根據(jù)對偶問題的性質(zhì)，請?zhí)顚懴卤恚耗繕?biāo)函數(shù)值 原問題可行解 非可行解對偶問題 可行解非可行解答：目標(biāo)函數(shù)值 原問題可行解 非可行解對偶問題 可行解 最優(yōu) zzmax非可行解 zz ——max,.6.對偶單純形法的步驟？答：1）將原線性規(guī)劃問題改寫為目標(biāo)函數(shù)極大化，并化為標(biāo)準(zhǔn)形式感謝閱讀2）列出單純形表3）確定換出基的變量4）確定換入基的變量5）用換入變量替換換出變量得到一個新的基。用新的基再檢查是否所有精品文檔放心下載(i1,,m)0。如果是，找到了問題的最優(yōu)解，如果否，回到第3步再重復(fù)謝謝閱讀i計算。7.靈敏度分析的步驟是什么？1）將參數(shù)的改變計算反映到最終單純形表上來：2）檢查原問題是否仍為可行解；3）檢查對偶是否仍為可行解；4）按下表所列情況得出結(jié)論和決定繼續(xù)計算的步驟。原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解仍為問題最優(yōu)解可行解非可行解用單純形法繼續(xù)迭代求最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解非可行解非可行解引進(jìn)人工變量，編制新的單純形表重新計算8.敏感性分析中c的變化，b的變化，增加一個變量的分析，增加一個約束條感謝閱讀j i件的分析在實際問題中分別代表的什么含義。答：c的變化代表的是價值系數(shù)的變化；jb的變化代表的是資源的限制的變化；i,.增加一個變量的分析相當(dāng)于增加一種新的產(chǎn)品；增加一個約束條件的分析相當(dāng)于在實際問題中增加一道工序。謝謝閱讀9.根據(jù)原問題和對偶問題的對應(yīng)關(guān)系，填寫出下表。原問題（對偶問題） 對偶問題（原問題）目標(biāo)函數(shù)max 目標(biāo)函數(shù)min原問題（對偶問題）目標(biāo)函數(shù)maxn個0變量0無約束目標(biāo)函數(shù)中變量的系數(shù)m個0約束條件0約束條件右端項

對偶問題（原問題）目標(biāo)函數(shù)minn個 約束條件 約束條件右端項m個0變量0無約束目標(biāo)函數(shù)中變量的系數(shù),.10.影子價格在管理決策中的作用?答：1）影子價格不等于市場價格。若影子價格大于市場價格，則應(yīng)買進(jìn)該資源；謝謝閱讀若影子價格小于市場價格，則應(yīng)賣出該資源。2）影子價格反映了資源的稀缺性，感謝閱讀影子價格越高，則越稀缺。11.單純形法中各個檢驗數(shù)的經(jīng)濟(jì)意義是什么？答：從影子價格的含義上來考察單純形法的計算。有B1Pcm，cCayijBjjijii1其中c代表第j種產(chǎn)品的產(chǎn)值，m是生產(chǎn)一個單位該種產(chǎn)品所消耗各項資ayji1iji源的影子價格的總和，即產(chǎn)品的隱含成本。當(dāng)產(chǎn)品產(chǎn)量大于隱含成本時，表明生產(chǎn)該項產(chǎn)品有利，可在計劃中安排，否則用這些資源來生產(chǎn)別的產(chǎn)品更為有利，就不在生產(chǎn)計劃中安排。這就是單純形法中各個檢驗數(shù)的經(jīng)濟(jì)意義。感謝閱讀12.參數(shù)線性規(guī)劃的解法要求？答:當(dāng)問題中有多個參數(shù)變化時，應(yīng)使目標(biāo)函數(shù)z()是的線性函數(shù)。因此有多感謝閱讀個b值變動時，可表為b'ba，式中a可以是任意一個實數(shù)；同樣當(dāng)有多精品文檔放心下載i i i i i個c值變動時，也應(yīng)有關(guān)系式c'ca，式中a可以是任意一個實數(shù)。精品文檔放心下載jjjjj13.靈敏度分析包括哪幾種參數(shù)改變的情況。答：1）分析C的變化范圍2）分析b變化的范圍3）增加一個變量的分析4）jj增加一個約束條件的分析。。線性規(guī)劃的原問題與對偶問題的表達(dá)式(矩陣)原問題:感謝閱讀,.maxzCXAXbs.tX0對偶問題：minwb'YA'YC's.tY015.對偶問題中的互補(bǔ)松弛性定理的實際經(jīng)濟(jì)含義？n答：在對偶問題的互補(bǔ)松弛性定理中有如果axb，則y0，如果y0,ijjiiij1則naxb，這表明生產(chǎn)過程中如果某種資源b未得到充分利用時，該種資精品文檔放心下載ij j i i1源的影子價格為零；又當(dāng)資源的影子價格不為零時，表明該種資源在生產(chǎn)中已經(jīng)精品文檔放心下載耗費(fèi)完畢。16.對偶單純形法應(yīng)用的前提是什么？答：有一個基，其對應(yīng)的基本解滿足1）單純形表的檢驗數(shù)行全部非正（對偶可行）2）變量取值可有負(fù)數(shù)（非可行解）（注）通過矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純形感謝閱讀表。17.靈敏度分析中由參數(shù)a,b,c的變化而引起的最終單純形表上有關(guān)數(shù)字的精品文檔放心下載ij i j變化公式是什么？答：bB1b；,.PB1P；izizmycjcajjjijii118.靈敏度分析分析c的變化范圍的步驟。j答：目標(biāo)函數(shù)中系數(shù)c的變化僅僅影響到檢驗數(shù)（cjzj）的變化，所以將cjj的變化直接反映到最終單純形表中，繼續(xù)進(jìn)行計算。19.靈敏度分析分析b的變化范圍的步驟。i答：b的變化反映到最終單純形表上只引起基變量列數(shù)字變化。 1）按公式感謝閱讀ibB1b，算出b，將其加到基變量列的數(shù)字上。2）由于其對偶問題仍為可行解，故只需檢查原問題是否仍為可行解，再按照下表進(jìn)行計算。感謝閱讀原問題對偶問題結(jié)論或繼續(xù)計算的步驟可行解可行解仍為問題最優(yōu)解非可行解可行解用對偶單純形法繼續(xù)迭代求最優(yōu)解20.靈敏度分析中，增加一個變量的分析的步驟。答：1）計算czcmy*；2）計算P'B1P；3）若0,ajjjjijijjji1只需將P'和的值直接反映到最終單純形表中，原最優(yōu)解不變；若>0，jjj則按單純形表繼續(xù)迭代計算。21.靈敏度分析中，增加一個約束條件的分析的步驟。答：先將原來問題的最優(yōu)解變量取值代入這個新增的約束條件中，如滿足，說明謝謝閱讀新增約束未起到限制作用，原最優(yōu)解不變。否則，將新增約束直接反映到最終表謝謝閱讀中，再進(jìn)行分析。,.22.對偶單純形法的特點答：1)與單純形法不同，對偶單純形法是先確定出基變量，然后才能確定進(jìn)基變量，這不同正是對偶關(guān)系所致。2）初始基解可以是不可行的，只要檢驗數(shù)符合最優(yōu)性條件，就可以進(jìn)行基的轉(zhuǎn)換，不需要增添人工變量，這樣就可使計算大為簡化。3）如果原規(guī)劃的決策變量很少，但約束條件卻較多時，可轉(zhuǎn)用對偶單純形表求解其對偶規(guī)劃，這樣可以簡化計算。4）靈敏度分析中，許多運(yùn)算用對偶單純形法求解比較方便，否則會使問題變得復(fù)雜；但是在一般情況下，大多數(shù)對稱型的線性規(guī)劃及其對偶規(guī)劃，都較難找到一個檢驗數(shù)全部非負(fù)的初始基解。因而在求一般線性規(guī)劃時，較少單獨(dú)使用對偶單純形法。謝謝閱讀23.線性參數(shù)規(guī)劃，求解的主要步驟是什么。答：1）對含參數(shù)t的參數(shù)規(guī)劃，先令t=0，用單純形法求出最優(yōu)解。2）將t直接反映到最優(yōu)單純形表中，并用靈敏度分析的方法進(jìn)行分析。3）當(dāng)t連續(xù)變化時，觀察b列和檢驗數(shù)行各元素的變化。如果b列出現(xiàn)負(fù)分量，則按對偶單純形法消除不可行性；如果檢驗數(shù)出現(xiàn)負(fù)的，則用單純形法進(jìn)行迭代。4）在迭代后的單純形表上，令t繼續(xù)變化，重復(fù)步驟（3），直到b不出現(xiàn)負(fù)值，檢驗數(shù)不出現(xiàn)負(fù)值為止。感謝閱讀,.五、計算1.將原問題化成對偶問題解：2.設(shè)原問題如下，寫出其對偶問題。minZ3x2x3x4x謝謝閱讀1234x2x3x4x31234x3x4x52342x13x27x34x42x0,x014解：對偶問題maxW3y5y2y1 2 3y2y3132yy3y1233y3y7y1234y4y4y123y0,y0,y12

234無約束3寫出下面線性規(guī)劃的對偶問題.(1)minZ18x16x10x123,.x2xx512332xxxS.t1236x3xx1230,x0,xx123解：maxw5y3y6y123y2yy181232yy3y16123y1y2y310y0,y0,y無約束123（2）minZ2x3x5xx4123xx3xx512342x2xx4S.tx134xx62340,x,xx0,x無約束1234maxW5y4y6y123y2y212yy3S.t13y53y2y123yyy11230,y0,y無約束3123.用對偶單純行法求解minZ7x4x12x1232xxx61233x2xx10123xxx3123x,x,x0123解：maxZ7x4x12x1 2 3,.2x xxx612343x2xxx1012351236x0(j1,2,,6)jC7412000jXB1bxxxxxxB123456x62111004x103210105x311100167412000jx45301104x103210103x74300116432800120jX*0,0,10,4,0,7TminZ120大M法求解maxZ3x2x3xx1234x2x3x151232xx5x20s.t.123x12x2x3x410x0(j1,2,3,4)j解：引入人工變量x、x，線性規(guī)劃問題為：5 6maxZ3x2x3xxM(xx)精品文檔放心下載1 2 3 4 5 6CBMM1

x2x3xx1512352xx5xx20s.t.1236x12x2x3x410x0(j1,2,,6)jC32jXB1bxxB12x15125x20216x101243M43M4jx315755x425153x635954M12167M

,.3 1 M Mxxxx345630105001411008M400000115710001055000jx157171002x257370103207000jx52010162x52001123x52100761000103j,.X=(5/2,5/2,5/2,0,0,0);Z=15精品文檔放心下載用對偶單純形法求解線性規(guī)劃問題minzxx1 22xx4s.t.x127x712x,x012c11jCXbxxBB121x21101331x1001132cz00jj表2-4

00xx34711313121313611313原問題的解轉(zhuǎn)變成了可行解，且對應(yīng)的對偶問題的解仍可行（即檢驗數(shù)全為非謝謝閱讀正），因此原問題的最優(yōu)解為21,10T,minzxx31.Xx,xT13121313122.影子價格：下述線性規(guī)劃問題：maxz8x4x6x3x9x12345x2x3x3x3x180(資源1）12345s.t4x3x2xxx270（資源2）12345x3x2xx3x180（資源3）12345x0(j1,5)j已知最優(yōu)解中的基變量為x,x,x,且已知31531311131241169327要求根據(jù)上述信息確定三種資源各自的影子價格。解：YCB1B271664818,187227,62490271(36,27,72)(43,1,83)謝謝閱讀4,1,8.三種資源的影子價格分別為3 3六.綜合題1.靈敏度分析已知線性規(guī)劃問題；用單純形法求解最終的單純形法表如下：x x x1 2 3

,.x x4 52x61110x10035cz0-3jj試說明分別發(fā)生下列變化時，新的最優(yōu)解是什么？（a）目標(biāo)函數(shù)變?yōu)閙axz2x3xx1236 3（b）約束條件右端由4變?yōu)?（c）增添一個新的約束x2x213解：8,10aX33,0,0,0bX3,0,0,0,710,0,8,0,22cX333（a）CBXbxxx1232x611110x10031501-1j2x81023133x10011332004j3

11-1x411-2231343

11-2x5010131313

,.01061038,10,0,0,0最優(yōu)解Z2810046X3333331033（b）b'B1b1147CBXb2-112x311110x703150-3-1j原問題最優(yōu)解不變X3,0,0,0,7Z*6（c）x6,x10代入-x2x362151x2xx2136CBXbxxxx12342x6111110x10031150x2-10206

,.001 1-2 0x x5 600-1P,P,P組成單位矩陣1 5 62x611110010x1003111050x-80-1-3-10160-3-1jθ—3132x10/312/3010x22/308/3051x8/301/316j080X(10/3,0,8/3,0,22/3)Z2xxx2*10/308/328/31232.靈敏度分析已知線性規(guī)劃問題maxZ6x14x13x1231x2xx242123s.tx2x4x601x,x2,x30123用單純形法求解時得到的最終單純形表如下表所示X1X2X3X136160X360-11cz0-90

,.-2 0 02 — —2/3 0 1/34/3 1 -1/31/3 0 -1/3-83 0 -13X4 X54 -1-1 1/2-11 -1/2j j,.當(dāng)約束條件變?yōu)閤4x2x68時，問題的最優(yōu)解如何變化。123解：x4x2x68等價于1/2x2x2x34，因此約束條件只是右端123123項發(fā)生變化，將變化反映到最終單純形表中，并用對偶單純形法迭代得到新的最感謝閱讀優(yōu)解為(52,4,0)，maxZ=368CBXbX1X2X3X4X56x361604-1113x60-11-11/23413476b11/2604CBXbX1X2X3X4X56x761604-1113x-40-11-11/230-90-11-1/2jθ-9-11-x52106-2-41x401-11-1/22,.已知線性規(guī)劃問題maxz2xx5x6x對偶變量12342xxx8y1341s.t.2x2xx2x12y12342x0,j1,,4j其對偶問題的最優(yōu)解為y*4，y*1，試應(yīng)用對偶問題的性質(zhì)，求原問題的最感謝閱讀1 2優(yōu)解。解 原問題的對偶問題為minw8y12y1 22y2y2⑴1212y2⑵s.t.yy5⑶12y2y6⑷12y,y012將y*4，y*1代入，知約束條件⑴、⑵為嚴(yán)格不等式，由互補(bǔ)松弛定謝謝閱讀1 2理，得x*0，x*0。1 2因為y，y0，則原問題的兩個約束條件應(yīng)取等式，即感謝閱讀1 2x*x*8，x*2x*12精品文檔放心下載3 4 3 4聯(lián)立求解得x*x*4，故原問題的最優(yōu)解為謝謝閱讀3 4X*(0,0,4,4),maxz44精品文檔放心下載3.已知線性規(guī)劃問題：,.minZ2xx2xx1x2x34x123s.txkx6x0,1x20,x無3約束123其最優(yōu)解為x5,x0,x1精品文檔放心下載1 2 3（a）求k的值（b）寫出并求其對偶問題的最優(yōu)解解：寫出其對偶問題如下maxw4y6y2yy2y1y21s.t12yky22yy101無約束，2由ZW及互補(bǔ)松弛性質(zhì)得：m因為x1=-5<0,則ayC，即yy2ijij12i1又因為Z=2*(-5)-0+2*(-1)=-12=Wyy2求方程組4y16y21212解得y0,y2,代入求得k112已知線性規(guī)劃問題maxZ10x5x1 2,.3x4x912s.t.5x2x812x,x012用單純形表求得最終表如下所示XxxxxB1234x3/2015143142x1101727100-5/14-25/14j試用靈敏度分析的方法分別判斷：（a)目標(biāo)函數(shù)系數(shù)c或c分別在什么范圍內(nèi)變動，上述最優(yōu)解不變。感謝閱讀1 2（b)約束條件右端項b，b當(dāng)一個保持不變，另一個在什么范圍內(nèi)變化，上述感謝閱讀1 2最優(yōu)基保持不變。解：（a）c25c5001CXxx00BB125x015143142cx1017271100c252c15114714j71c250c251142152571c2c150c15421711414c11010c2CXxxBB12cx012210x101j00105c0c440714224c3204023c20c23147（b）105CXxxBB1232x0121x10100j分析b似變量。1535b12b1417b*B1b1414101281b16777175b1202417b24145b1611615b0161b7171

,.0 0005143141727105c3c2071421427000051431417275142514,.53453b9b*B1b141414142012b292b77772453b0b1591422149b15922b0b222772七．證明題1.已知線性規(guī)劃問題如下，試應(yīng)用對偶理論證明上述線性規(guī)劃問題無最優(yōu)解。感謝閱讀maxZxxx1x2x2123x1,x,2x03123證明：該問題存在可行解，如X=（0,0,0）；又上述問題的對偶問題為：感謝閱讀minw2yyy21y12y1y21s.ty1y20y1,y2012,.由第一個約束條件知對偶問題無可行解，由此可知其原問題無最優(yōu)解。精品文檔放心下載2.已知線性規(guī)劃問題如下，應(yīng)用對偶理論證明該問題最優(yōu)解的目標(biāo)函數(shù)值不大于精品文檔放心下載25。maxZ4x7x2xx2x1x21032131x,x2,x30123證明：寫出其對偶問題，容易看出Y=（0,7/3）是一個可行解，代入目標(biāo)函數(shù)得w=23.3，因有maxZw，故原問題最優(yōu)解不超過25.感謝閱讀minw10y10yy2y1422y13y27s.ty13y22y1,y,y201233.證明弱對偶性證明：設(shè)X、Y分別為(P)、(D)的任一可行解，謝謝閱讀則 CXYb證： X、Y為(P)、(D)的可行解AXbYAXYbCXYbYACYAXCX謝謝閱讀由此可推出：若(P)為無界解，則(D)無可行解；若(D)為無界解，則(P)無可行解。,.4.證明解的最優(yōu)性即：設(shè)X、Y分別為(P)與(D)的可行解，且CXYb謝謝閱讀則 XX* YY*證：故，XX*，YY*證明對偶定理若(P)有最優(yōu)解，則(D)也有最優(yōu)解，且二者最優(yōu)值相等。謝謝閱讀證：對(P)增加松弛變量Xs，化為MaxzCXAXLXbCs.t.sX,X0XsCBB1bB1A設(shè)其最CX優(yōu)基CX為B，BY終表BY為,CXBY,故CXCXBYBY****CCB1Ab其檢驗數(shù)為CCB1A0B0CB1I0sB取YCB1，則Y滿足YACB即Y是(D)的可行解，且YbCB1bz*謝謝閱讀B

0XsB1I0CB1IB,.由性質(zhì)3，YY*。4.證明互補(bǔ)松弛性定理答：證明如果Y0，則AXBmaxzCXminwb'Y已知：原問題:AXb對偶問題：''s.tAYCs.tX0Y0CXCX*BY*BY,CXBY,故CXCX*BY*BY由弱對偶性知道，CXYb，則精品文檔放心下載CXAYXBY,CXBY,又根據(jù)最優(yōu)性CXBY，謝謝閱讀再有CXAYXBY，移項，(AXB)Y0,因Y0，所以AXB感謝閱讀,.茲有線性規(guī)劃問題maxz5x5x13x123xx3x20①s.t.1234x10x90②1230x,x,x123先用單純形法求出最優(yōu)化解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化。精品文檔放心下載⑴約束條件①的右端常數(shù)由20變?yōu)?0；⑵約束條件②的右端常數(shù)由90變?yōu)?0；精品文檔放心下載⑶目標(biāo)函數(shù)中x1變?yōu)?；的系數(shù)由13變?yōu)?；⑷x的系數(shù)列向量由31125⑸增加一個約束條件③2x3x5x50；123⑹將約束條件②改變?yōu)?0x5x10x100。感謝閱讀1 2 3解 將原問題化標(biāo)準(zhǔn)型maxz5x5x13x1 2 3,.x x 3xx20s.t.12341235x,x,x,x,x012345列單純形法求解如表1所示。表1c551300jCXbxxxxxBB123450x201131040x9012410015czj551300j13x2013131130330x70463230103135cz232301330jj5x201131030x101602415czj00250j多重最優(yōu)解，其中之一為Xx,x,xT0,20,0T,maxz100。謝謝閱讀123此時最優(yōu)解為B10B1104141⑴當(dāng)約束條件①的右