第2章對(duì)偶問題

第2章對(duì)偶問題判斷下列說法是否正確：對(duì)偶問題的對(duì)偶問題一定是原問題；根據(jù)對(duì)偶問題的性質(zhì)，當(dāng)原問題為無界解時(shí)，其對(duì)偶問題無可行解，反之，當(dāng)對(duì)偶問題無可行解時(shí)，其原問題具有無界解；已知為線性規(guī)劃的對(duì)偶問題的最優(yōu)解，若>0，說明在最優(yōu)生產(chǎn)計(jì)劃中的i種資源已完yy**ii全耗盡；已知為線性規(guī)劃的對(duì)偶問題的最優(yōu)解，若＝0，說明在最優(yōu)生產(chǎn)計(jì)劃中第i種資源一yy**ii定有剩余；若某種資源的影子價(jià)格等于k，在其它條件不變的情況下，當(dāng)改種資源增加5個(gè)單位時(shí)，相應(yīng)的目標(biāo)函數(shù)值將增大5k；在線性規(guī)劃問題的最優(yōu)解中，如某一變量x為非基變量，則在原來問題中，無論改變它在j目標(biāo)函數(shù)中的系數(shù)c或在各約束中的相應(yīng)系數(shù)a，反映到最終單純形表中，除該列數(shù)jij字有變化外，將不會(huì)引起其它列數(shù)字的變化。簡(jiǎn)答題、試述對(duì)偶單純形法的優(yōu)點(diǎn)及其應(yīng)用的上局限性。、試述對(duì)偶單純形法的步驟。、試解釋對(duì)偶解的經(jīng)濟(jì)含義和影子價(jià)格在市場(chǎng)決策中的作用。間有何區(qū)別？以及研究影子價(jià)格的意義是什、什么是資源的影子價(jià)格？同相應(yīng)的市場(chǎng)價(jià)格之么？:判斷下列說法是否正確，為什么？（a）如果線性規(guī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解；也一定無可行解；管原問題是求極大或極小，原問題可行（b）如果線性規(guī)劃的對(duì)偶問題存在可行解，則其原問題（c）在互為對(duì)偶的一對(duì)原問題和對(duì)偶問題中，不解的目標(biāo)函數(shù)都一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)。k，在其5k嗎？若某種資源的影子價(jià)格等于他條件不變的情況下，當(dāng)該種資源增加5個(gè)單位時(shí)，相應(yīng)的目標(biāo)函數(shù)最大值將增加已知y*為某線性規(guī)劃問題的對(duì)偶問題最優(yōu)解中的第i分量，若y*＝0，能否肯定在最優(yōu)生產(chǎn)ii計(jì)劃種第i種資源一定有剩余？寫出對(duì)偶問題寫出下列線性規(guī)劃問題的對(duì)偶問題maxZ10x2xx312

xx2x101234xxx20123x,x,x0123寫出下列線性規(guī)劃問題的對(duì)偶問題maxZ2xx3xx4123x2xxx512342xx3x4123xxx1134x,x0,x,x無約束1324寫出下列線性規(guī)劃問題的對(duì)偶問題minZ3x2x3x4x4123x2x3x4x31234x3x4x522x3x7x4x2341234x0,x0,x,x無約束1423寫出下列線性規(guī)劃問題的對(duì)偶問題minZ5x6x7x312x5x3x151235x6x10x20123xxx5123x0,x0,x無約束123寫出下列線性規(guī)劃問題的對(duì)偶問題maxZ2xx5x3122x3x5x21233xx7x31x6x52313x,x,x0123寫出下列線性規(guī)劃問題的對(duì)偶問題maxZxxx3122xx5x12123x2x7x6123x6x413x,x,x0123寫出下列線性規(guī)劃問題的對(duì)偶問題minZ4x2x3x1232xx5x6123x2x7x4123xx213x無約束,x0,x0123寫出下列線性規(guī)劃問題的對(duì)偶問題：MinZ2x2x4x1232x3x5x21233xx7x3s.t.123x4x6x5123x,x,x0123寫出下列線性規(guī)劃問題的對(duì)偶問題：MinZx2x3x1232xx3x11233xx2x51xx3x4x1,x,0,x無限制s.t.2312323寫出下列線性規(guī)劃問題的對(duì)偶問題：MaxZ2xx4x1232x3xx11233xxx4s.t.123xx413x10,x0,x無限制23寫出下列線性規(guī)劃問題的對(duì)偶問題：MaxZ2x7x5xx3x12345x5x4x6x2x512345s.t.2x3xx2x6x912345x0,x無限制51~4寫出下面線性規(guī)劃問題的對(duì)偶問題maxz5x2x12xx3122x3x51x,x0212寫出下面線性規(guī)劃問題的對(duì)偶問題maxz5x6x12x2x512x5x312x無限制,x012設(shè)有原始問題maxz3x2x5x312x2xx5601233x2x420約束條件：13x4x40012x,x,x0123寫出以上原始問題的對(duì)偶問題。寫出下面線性規(guī)劃問題的對(duì)偶問題minzmncxijiji1j1i1,m,nxaijij1j1,n,mxbijji1x0i1,,m;j1,,nij如下線性規(guī)劃模型：minZxxxxxx12345xx416xx812xx1023xx7約束條件：34xx1245xx456x,x,x,x,x,x0123456寫出以上原始問題的對(duì)偶問題，在通過對(duì)偶問題求出原始問題的最優(yōu)解。對(duì)偶單純形法試用對(duì)偶單純形法求解下列線性規(guī)劃問題。minZxx122xx412x7x713x,x012試用對(duì)偶單純形法求解下列線性規(guī)劃問題。minZ8x16x12x123x4x2122x4x313x,x,x0123試用對(duì)偶單純形法求解下列線性規(guī)劃問題。minZ50x40x123x2x35125x6x60132x3x3012x,x012試用對(duì)偶單純形法求解下列線性規(guī)劃問題。minZx2x3x312xxx4123xx2x8123xx223x,x,x0123試用對(duì)偶單純形法求解下列線性規(guī)劃問題。minZ2x2x12x4xx8123x2x2x6123x,x,x0123試用對(duì)偶單純形法求解下列線性規(guī)劃問題。minZ3x2xx4x41232x4x5xx012343xx7x2x212345x2xx6x151234x,x,x,x01234用對(duì)偶單純形法求解：minZxxxxxx123456xx416xx812xx1023xx7約束條件：34xx1245xx456x,x,x,x,x,x0123456用對(duì)偶單純形法求解：minz2x3x122x3x3012x2x1012xx012x5,x012用對(duì)偶單純形法求解minz4x12x18x312x3x3132x3x5約束條件：23x,x,x0123．考慮線性規(guī)劃問題：MaxZ5x2x3x3x5x2x3012123s.t.x5x6x40123x,x,x0123（1）寫出對(duì)偶問題；（2）求解對(duì)偶問題通過對(duì)偶問題求下面問題的最有解minz5x6x3x3125x5x3x50123xxx201237x6x9x301235x5x5x351232x4x15x1012312x10x9012x10x2023x,x,x0123用單純形法求解下面的線性規(guī)劃問題：(2)MinZ3x2xx4x4(1)MinZ5x2xx1232x4x5xx01235x2xx41xx23x2447x323123s.t.6x3x5x10..st125x2xx6x151x,x,x0231234x,x,x,x01231234．用對(duì)偶單純形法證明下面的線性規(guī)劃問題無解：MinZ3x2xx123xxx6123xx4s.t.13xx32x,x,x03123設(shè)有線性規(guī)劃問題minz2x3x122x3x3012x2x1012xx012x5,x012（1）用圖解法解以上問題(2)寫出它的對(duì)偶問題用大M方法解下面的問題，再?gòu)淖顑?yōu)表格中求對(duì)偶解。maxz5x2x3x312x5x2x30123約束條件：x5x6x40123x,x,x0123已知線性規(guī)劃問題x3xx81242xx612約束條件：xxx6234xxx9123x,x,x,x01234要求：（1）寫出其對(duì)偶問題；（2）已知原問題最優(yōu)解為X*2,2,4,0，試根據(jù)對(duì)偶理T論，直接求出對(duì)偶問題的最優(yōu)解。考慮問題maxz8x6x12xx3/512xx2約束條件：12x,x012用圖解法證明原始問題和對(duì)偶問題都沒有可行域。因此。當(dāng)一個(gè)問題不可行時(shí)，它的對(duì)偶問題不一定無界。靈敏度分析已知線性規(guī)劃問題maxZ5x5x13x312xx3x2012312x4x10x90123x,x,x0123先用單純形法求出最優(yōu)解，然后分析在下列各種條件下，最優(yōu)解分別有什么變化？（1）第一個(gè)約束條件的右端項(xiàng)常數(shù)由20變?yōu)?0；（2）第二個(gè)約束條件的右端項(xiàng)常數(shù)由90變?yōu)?0；（3）目標(biāo)函數(shù)中3x的系數(shù)由13變?yōu)?；10（4）x的系數(shù)列向量由變?yōu)椋?2512x3x5x50；（5）增加一個(gè)約束條件12310x5x10x100（6）將原第二個(gè)約束條件改變?yōu)?23、某廠準(zhǔn)備生產(chǎn)三種產(chǎn)品A、B、C，需消耗勞動(dòng)力和原料兩種資源，其有關(guān)數(shù)據(jù)如下表：?jiǎn)挝幌漠a(chǎn)品資源ABC資源限量勞動(dòng)力63415554530原料單位利潤(rùn)33（1）用單純形法總利潤(rùn)最的大生產(chǎn)計(jì)劃。（2）分別求出料的影子價(jià)格。若原料不夠，可到市場(chǎng)上購(gòu)買，市場(chǎng)價(jià)格為0.8元/單位。問是否要購(gòu)進(jìn)，最多可購(gòu)進(jìn)多少？總利潤(rùn)增加多少？（3）當(dāng)產(chǎn)品A、C的單位利潤(rùn)在何范圍變化時(shí)，最優(yōu)生產(chǎn)計(jì)劃不變？確定勞動(dòng)力和原（4）勞動(dòng)力可減少多少二不改變最優(yōu)計(jì)劃？2xx3x10（5）現(xiàn)需增加電力的限制條件，試求出最優(yōu)的生產(chǎn)方案。123、已知線性規(guī)劃問題maxZ2xxx123xxx6123x2x412x,x,x0123用單純形法求解的最優(yōu)表如下：cj2－1100x50bCB2XBX1X5x110x21x31x4160311110z=500－3－1－20j試說明分別發(fā)生下列變化時(shí)，最優(yōu)解分別有什么變化？（1）目標(biāo)函數(shù)變?yōu)閙axZ2x3xx；12363變?yōu)椋?4x2x2（2）約束條件的右端項(xiàng)由（3）增加一個(gè)約束條件。12．一個(gè)最大化的線性規(guī)劃問題有四個(gè)非負(fù)變量，三個(gè)“”型約束條件，其最優(yōu)表為：Xx1xxxxx6B2345bx7012/312/3014/3x4x6x02-1001-1/3410/31111/301/301/3024/304/301/3j（1）列出此問題的對(duì)偶問題；（2）寫出對(duì)偶問題的最優(yōu)解。全部約束條件都是“”的最大化問題，它的最優(yōu)表如下：．有一Xxxxxx12345bB011/2-1/202x210-1/83/803/2x1x5001-214001/41/40j其中x，x是決策變量，1x，x，x是松弛變量。3452（1）在保持最優(yōu)解基不變的情況下，若要把一個(gè)約束條件的右端項(xiàng)擴(kuò)大，用擴(kuò)大哪一個(gè)？為什么？最大擴(kuò)大多少？求出新的目標(biāo)函數(shù)值；c,c是目標(biāo)函數(shù)中x和x的系數(shù)，求使最優(yōu)基變量（x,x,x）保持最優(yōu)（2）設(shè)1212152c/c的范圍。性的比值12．一個(gè)工廠利用三種原料能生產(chǎn)五種產(chǎn)品，其有關(guān)數(shù)據(jù)如下表：可利用材料數(shù)量（千萬件材料所用材料數(shù)（千克）克）原材料ABCDE甲乙丙0.510.500.550.500.51.51120.5111110.5萬件產(chǎn)品利潤(rùn)41051010.5（萬元）（1）確定一種最優(yōu)生產(chǎn)計(jì)劃；c,c做靈敏度分析；（2）對(duì)目標(biāo)函數(shù)的系數(shù)14b,b做靈敏度分析；（3）對(duì)約束條件中的12（4）如果引進(jìn)新產(chǎn)品F要用原料甲、乙、丙分別為0.5，1，0.5（千克）。而每單位F可得利潤(rùn)10萬元，（5）如果又增加煤耗不允許超過20噸的限制，而生產(chǎn)每單位A，B，C，D，E產(chǎn)品分別需要煤3，2，1，2，1（噸），問是否需要改變?cè)瓉淼淖顑?yōu)方案？問：產(chǎn)品是否有利于投產(chǎn)？它的利潤(rùn)多少時(shí)才有利于投產(chǎn)？已知線性規(guī)劃問題maxz2xxx312xxx6123約束條件：x2x412x,x,x0123先用單純形法求解，在分析在下列條件單獨(dú)出現(xiàn)的情況下最優(yōu)解的變化。（a）目標(biāo)函數(shù)變?yōu)閙axz2x3xx12363（b）約束右端項(xiàng)由變?yōu)?4（c）增加一個(gè)新的約束條件x2x213已知線性規(guī)劃問題maxz3x2x12x2x6122xx812xx112x22x,x012已知用單純形法求的最有解的單純形表如下表所示。試分析在下列各種條件單獨(dú)出現(xiàn)的情況下，最優(yōu)解將如何變化。x1x2xx4x5x630112/3-1/3-1-1/32/31002300x4/310/