第三版運(yùn)籌學(xué)總復(fù)習(xí)1課件

2023/8/91⒉求解LP問題時(shí)可能出現(xiàn)哪幾種結(jié)果？求解LP問題有可能出現(xiàn)4種結(jié)果，即：⑴有唯一最優(yōu)解；⑵有無窮多最優(yōu)解；⑶有無界解；⑷無可行解。⒊什么是LP問題的標(biāo)準(zhǔn)型式，如何將非標(biāo)準(zhǔn)型的LP問題轉(zhuǎn)化為標(biāo)準(zhǔn)型？LP問題的標(biāo)準(zhǔn)型是：⑴目標(biāo)函數(shù)取極大值；⑵約束條件取“=”號(hào)；2023/8/21⒉求解LP問題時(shí)可能出現(xiàn)哪幾種結(jié)果？求解12023/8/92⑶資源系數(shù)必須≥0；⑷決策變量必須≥0

對(duì)于任意一個(gè)非標(biāo)準(zhǔn)的LP問題，可采取如下方法，將其變換為標(biāo)準(zhǔn)型：⑴若目標(biāo)函數(shù)為求極小值minz=CX，則令z’=－z，便可得到maxz’=－CX；⑵如果某約束條件的右端項(xiàng)（資源系數(shù)）<0，則該約束條件兩端同時(shí)乘“－1”，使其≥0；⑶如果約束條件為“≤”不等式，則在不等式的左端加入一個(gè)非負(fù)的松弛變量，使其變?yōu)榈仁剑?023/8/22⑶資源系數(shù)必須≥0；對(duì)于任22023/8/93⑷如果約束條件為“≥”不等式，則在不等式的左端減去一個(gè)非負(fù)的剩余變量，使其變?yōu)榈仁?；⑸若xj≤0，則令x’j=－xj，代入標(biāo)準(zhǔn)型，則有x’j≥0；⑹若xj的正負(fù)不限，則令xj=x’j－x”j，而x’j≥0，x”j≥0。⒋試述LP問題的基解、基可行解、可行解、最優(yōu)解的概念以及上述解之間的相互關(guān)系。2023/8/23⑷如果約束條件為“≥”不等32023/8/94⑴基解：在約束方程組②中，令所有非基變量Xm+1=xm+2=…=xn=0，此時(shí)，方程組②有唯一解XB=(x1,x2,…,xm)T，將此解加上非基變量取0的值有X=(x1,x2,…xm,0,0,…,0)T，稱X為L(zhǎng)P問題的基解。2023/8/24⑴基解：在約束方程組②中，令所有非基變量42023/8/95⑵基可行解：滿足非負(fù)約束條件③的解；⑵可行解：滿足約束條件②和③的解；⑷最優(yōu)解：使目標(biāo)函數(shù)①達(dá)到最大值的可行解；⒌試述單純形法的計(jì)算步驟，如何在單純形表上判別問題是具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解或無可行解。在單純形表中，如果所有檢驗(yàn)數(shù)σj≤0，基變量中不存在非零的人工變量，非基變量中也不存在等于零的檢驗(yàn)數(shù)，此時(shí)的解為唯一最優(yōu)解；如果在單純形表中，雖然所有檢驗(yàn)數(shù)σj≤0，但存在某非基變量的檢驗(yàn)數(shù)等于零，此時(shí)的解為無窮多最優(yōu)解；2023/8/25⑵基可行解：滿足非負(fù)約束條件③的解；52023/8/96如果在單純形表中，所有檢驗(yàn)數(shù)σj≤0，基變量中存在非零的人工變量，此時(shí)的解為無可行解；如果在單純形表中，某檢驗(yàn)數(shù)σj>0，而對(duì)應(yīng)的Pj≤0，此時(shí)的解為無界解。⒍如果LP問題的標(biāo)準(zhǔn)型式變換為求目標(biāo)函數(shù)的極小化minz，則用單純形法計(jì)算時(shí)，如何判別問題已得到最優(yōu)解。2023/8/26如果在單純形表中，所有檢驗(yàn)數(shù)σj≤0，62023/8/97

如果LP問題的標(biāo)準(zhǔn)型式變換為求目標(biāo)函數(shù)的極小化minz，則在用單純形法計(jì)算時(shí)，用檢驗(yàn)數(shù)σj≥0判斷問題是否得到最優(yōu)，方法同極大化。⒎在確定初始可行基時(shí)，什么情況下要在約束條件中增添人工變量，在目標(biāo)函數(shù)中假定人工變量前的系數(shù)為（-M），其作用是什么？2023/8/27如果LP問題的標(biāo)準(zhǔn)型式變換72023/8/98當(dāng)規(guī)劃模型化為標(biāo)準(zhǔn)型后，當(dāng)其約束條件的系數(shù)矩陣中不存在單位矩陣時(shí)，需再添加新的人工變量。在一個(gè)LP問題的約束條件中加入人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)取值不受影響，假定人工變量在目標(biāo)函數(shù)中的系數(shù)為（-M，M為任意大正數(shù)），這樣目標(biāo)函數(shù)在實(shí)現(xiàn)最大化的過程中，必須把人工變量換出，否則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最大化。2023/8/28當(dāng)規(guī)劃模型化為標(biāo)準(zhǔn)型82023/8/99⒏什么是單純形法計(jì)算的兩階段法，為什么要將計(jì)算分兩個(gè)階段進(jìn)行，以及如何根據(jù)第一階段的計(jì)算結(jié)果來判定第二階段的計(jì)算是否需繼續(xù)進(jìn)行。MaxZ=-Mx6-Mx7MinZ=Mx6+Mx7因?yàn)椤癕”是一個(gè)很大的正數(shù)，是人們的一種想象，而計(jì)算機(jī)卻不知道這個(gè)很大的正數(shù)到底有多大，為避免計(jì)算發(fā)生錯(cuò)誤，對(duì)添加人工變量后的LP問題分兩階段來計(jì)算，稱兩階段法。第一階段：求解一個(gè)目標(biāo)函數(shù)僅含人工變量，且為最小化的LP問題，其兩種可能結(jié)果：2023/8/29⒏什么是單純形法計(jì)算的92023/8/910目標(biāo)函數(shù)最優(yōu)值為0，如果是這一結(jié)果，則去掉人工變量轉(zhuǎn)入第二階段；如果目標(biāo)函數(shù)最優(yōu)值不為0，則原問題無可行解，停止計(jì)算。第二階段：去掉第一階段中的人工變量，將第一階段得到的最優(yōu)解作為初始可行解，利用單純型法繼續(xù)迭代，直至終止。2023/8/210目標(biāo)函數(shù)最優(yōu)值為0，如果是這一102023/8/911

判斷下列說法是否正確圖解法同單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。LP模型中增加一個(gè)約束條件，可行域的范圍一般將縮小，減少一個(gè)約束條件，，可行域的范圍一般將擴(kuò)大。LP問題的每一個(gè)基解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)。如LP問題存在最優(yōu)解，則最優(yōu)解一定對(duì)應(yīng)可行域邊界上的一個(gè)點(diǎn)?！獭痢獭?023/8/211√×√√112023/8/912e)對(duì)取值無約束的變量xj，通常xj=x’j-x”j，其中x’j≥0，x”j≥0

√，在用單純形法求得的最優(yōu)解有可能同時(shí)出現(xiàn)x’j>0，x”j>0。×為什么說是錯(cuò)誤的?請(qǐng)看下面的例題：將下列的LP問題變換成標(biāo)準(zhǔn)型，并用單純形法求解。MaxZ=-2x1-x2+3x3st.x1+x2+x3+x4=7x1-x2+x3-x5=2-3x1+x2+2x3+x6=5x3=x3'-x3''x3'>=0x3''>=02023/8/212e)對(duì)取值無約束的變量xj，通常xj=x122023/8/913解：⑴用x3’-x3”替換x3，其中x3’，x3”≥0；⑵第一個(gè)約束條件左端加入一松弛變量x4；⑶第二個(gè)約束條件左端減去一剩余變量x5，再加上一個(gè)人工變量x6；⑸令z’=-z，把minz改為maxz’，即可得到該問題的標(biāo)準(zhǔn)型（規(guī)范型）：⑷第三個(gè)約束條件左端加上一個(gè)人工變量x7；2023/8/213解：⑴用x3’-x3”替換x3，其中x3132023/8/914解：用兩階段法求解第一階段的LP問題為：用單純形法求解，先將其化為標(biāo)準(zhǔn)型2023/8/214解：用兩階段法求解第一階段的LP問題為：142023/8/915用兩階段法求解，第一階段求解過程如下：cj000000-1-1cBxBbx1x2x3’x3”x4x5x6x70x47111-11000-1x621-1[1]-10-110-1x75-312-20001cj-zj-203-30-1000x45020011-100x3’21-11-10-110-1x71-5[3]0002-21cj-zj-530002-300x413/310/30001-1/31/3-2/30x3’7/3-2/301-10-1/31/34/30x21/3-5/31000[2/3]-2/31/3cj-zj000000-1-12023/8/215用兩階段法求解，第一階段求解過程如下：c152023/8/916第二階段，去掉人工變量，回歸到原問題：cj-2-13-300cBxBbx1x2x3’x3”x4x50x413/310/30001-1/33x3’7/3-2/301-10-1/3-1x21/3-5/31000[2/3]cj-zj-5/310007/30x49/2[5/2]1/200103x3’5/2-3/21/21-1000x51/2-5/23/20001cj-zj11/2-7/20000-2x19/511/5002/503x3’37/404/51-13/500x547/4020011cj-zj0-23/500-11/502023/8/216第二階段，去掉人工變量，回歸到原問題：c162023/8/917從上述最后一單純形表知，所有σj≤0，基變量中也不存在人工變量，故為最優(yōu)解，即X*=(x1,x2,x3’,x3”)=(1.8,0,37/4,0)，可以證明，對(duì)取值無約束的變量xj，如果令xj=x’j-x”j，其中x’j≥0，x”j≥0，在用單純形法求得的最優(yōu)解不可能同時(shí)出現(xiàn)x’j>0，x”j>0。2023/8/217從上述最后一單純形表知，所有σj≤0，基172023/8/918f)用單純形法求解標(biāo)準(zhǔn)型式的LP問題時(shí)，與σj>0對(duì)應(yīng)的變量都可以被選作換入變量。g)單純形法計(jì)算中，如不按最小比值原則選取換出變量，則在下一步解中至少有一個(gè)基變量的值為負(fù)。h)單純形法計(jì)算中，選項(xiàng)取最大正檢驗(yàn)數(shù)σk對(duì)應(yīng)的變量xk作為換入變量，將使目標(biāo)函數(shù)值得到最快√√2023/8/218√√182023/8/919的增長(zhǎng)。i)一旦一個(gè)人工變量在迭代中變?yōu)榉腔兞亢?，該變量及相?yīng)的數(shù)字可以從單純形表中刪除，而不影響計(jì)算結(jié)果。j)LP問題的任一可行解都可以用全部基可行解的線性組合表示。n)單純形法的迭代過程是從一個(gè)可行解轉(zhuǎn)換到目標(biāo)函數(shù)值更大的另一個(gè)可行解?！痢獭痢桃?yàn)楫?dāng)目標(biāo)函數(shù)取minz時(shí)就不是得到最快的增長(zhǎng)。只有當(dāng)該LP問題有唯一最優(yōu)解時(shí)才成立。2023/8/219的增長(zhǎng)。192023/8/920O)線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基可行解；×

為什么是錯(cuò)誤的？因?yàn)榛尚薪狻倏尚薪?。見P18。2023/8/220O)線性規(guī)劃問題的可行解202023/8/921第二章復(fù)習(xí)思考題⒉試從經(jīng)濟(jì)上解釋對(duì)偶問題及對(duì)偶變量的含義。如果把LP的原問題看作是在現(xiàn)有各項(xiàng)資源條件的限制下，企業(yè)如何確定生產(chǎn)方案，使預(yù)期目標(biāo)達(dá)到最優(yōu)。原問題的變量是生產(chǎn)方案的決策變量。對(duì)偶問題則是從另一角度提出問題，即如果其他公司想把企業(yè)的資源收買過去，他要付出多大的代價(jià)，才有可能使得企業(yè)放棄生產(chǎn)活動(dòng)。對(duì)偶變量是資源出讓的代價(jià)。2023/8/221第二章復(fù)習(xí)思考題⒉試從經(jīng)濟(jì)上解釋對(duì)偶問212023/8/922⒊根據(jù)原問題同對(duì)偶問題之間的對(duì)應(yīng)關(guān)系，分別找出兩個(gè)問題之間、解以及檢驗(yàn)數(shù)之間的對(duì)應(yīng)關(guān)系。原問題同對(duì)偶問題之間的對(duì)應(yīng)關(guān)系見后面兩表有唯一解的對(duì)偶問題的解是原問題最終單純形表中非基變量的檢驗(yàn)數(shù)。2023/8/222⒊根據(jù)原問題同對(duì)偶問題之間的對(duì)應(yīng)關(guān)系，分222023/8/923原問題與對(duì)偶問題間的關(guān)系如下表所示:Maxz2023/8/223原問題與對(duì)偶問題間的關(guān)系如下表所示:232023/8/9242023/8/224242023/8/925從第二章對(duì)偶問題的基本性質(zhì)看出，當(dāng)線性規(guī)劃原問題求得最優(yōu)解xj*（j=1，…，n）時(shí)，其對(duì)偶問題也得到最優(yōu)解yi*（i=1，…，m），且代入各自的目標(biāo)函數(shù)后有：式中bi是線性規(guī)劃原問題約束條件的右端項(xiàng)，它代表第i種資源的擁有量；而對(duì)偶變量yi*的意義代表在資源最優(yōu)利用條件下對(duì)第i種資源的估價(jià)。這種估價(jià)不是資源的市場(chǎng)價(jià)格，而是根據(jù)資源在生產(chǎn)中作出的貢獻(xiàn)而作的估價(jià)，它與資源的緊缺度有關(guān)，某種資源越緊缺，這種估價(jià)便越高，若有剩余，這種估價(jià)便為0，為了將其與市場(chǎng)價(jià)格相區(qū)別，稱這種估價(jià)為影子價(jià)格。⒋什么是資源的影子價(jià)格，同相應(yīng)的市場(chǎng)價(jià)格之間有何區(qū)別，以及研究影子價(jià)格的意義。2023/8/225從第二章對(duì)偶問題的基本性質(zhì)看出，當(dāng)線性規(guī)252023/8/926影子價(jià)格的經(jīng)濟(jì)解釋⑴資源的市場(chǎng)價(jià)格是已知數(shù)，相對(duì)比較穩(wěn)定，而它的影子價(jià)格則有賴于資源的利用情況，是隨企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況的變化而變化的未知數(shù)。⑵影子價(jià)格是一種邊際價(jià)格，對(duì)上式z求bi的偏導(dǎo)數(shù)得這說明yi*的值相當(dāng)于在資源得到最優(yōu)利用的生產(chǎn)條件下，bi（第i種資源擁有量）每增加一個(gè)單位時(shí)目標(biāo)函數(shù)z的增量。2023/8/226影子價(jià)格的經(jīng)濟(jì)解釋⑴資源的市場(chǎng)價(jià)格是已知262023/8/927⒌試述對(duì)偶單純形法的計(jì)算步驟，它的優(yōu)點(diǎn)及應(yīng)用上的局限性。對(duì)偶單純形法的計(jì)算步驟如下表所示：2023/8/227⒌試述對(duì)偶單純形法的計(jì)算步驟，它的優(yōu)點(diǎn)272023/8/928對(duì)偶單純形法計(jì)算步驟根據(jù)線性規(guī)劃問題列出初始單純形表b列數(shù)據(jù)均≥0?所有檢驗(yàn)數(shù)＜0?xl所在行所有alk≥0?以alk為主元素,按原單純形法進(jìn)行迭代運(yùn)算,即重復(fù)上述步驟停止計(jì)算已得到最優(yōu)解是否是否2023/8/228對(duì)偶單純形法計(jì)算步驟根據(jù)線性規(guī)劃問題b列282023/8/929對(duì)偶單純形法優(yōu)缺點(diǎn)分析

初始解可以是非可行解(如原例初始解x4=-3,x5=-4就非可行解),只要檢驗(yàn)數(shù)為負(fù)數(shù),就可進(jìn)行基變換,不需加人加變量,可簡(jiǎn)化計(jì)算

當(dāng)變量數(shù)多于約束條件數(shù)時(shí),用對(duì)偶單純形法計(jì)算可減少計(jì)算工作量,因此對(duì)變量少,而約束條件很多的LP問題,可將其變換為對(duì)偶問題求解

在靈敏度分析和整數(shù)規(guī)劃的割平面法求解中用對(duì)偶單純形法可使問題的處理簡(jiǎn)化

對(duì)大多數(shù)LP問題,很難找到一個(gè)適合用對(duì)偶單純形法的初始可行基對(duì)偶單純法優(yōu)點(diǎn)此法的局限性2023/8/229對(duì)偶單純形法優(yōu)缺點(diǎn)分析初292023/8/930⒍將aij，bi，cj的變化分別直接反映到最終單純形表中，表中原問題和對(duì)偶問題的解各自將會(huì)出現(xiàn)什么變化，有多少種不同情況以及如何去處理。見第2章第五節(jié)P63～P70。⒎判斷下列說法是否正確任何LP問題存在并具有唯一的對(duì)偶問題。