2023/9/161第一章復(fù)習思索題⒈試述LP數(shù)學(xué)模型組成要素及各要素特征。LP數(shù)學(xué)模型組成三要素：一是決議變量；二目標函數(shù)；三是約束條件。各要素特征：⑴決議變量是連續(xù)；⑵決議變量是目標函數(shù)線性函數(shù)；⑶約束條件是含有決議變量線性不等式。1/352023/9/162⒉求解LP問題時可能出現(xiàn)哪幾個結(jié)果？求解LP問題有可能出現(xiàn)4種結(jié)果，即：⑴有唯一最優(yōu)解；⑵有沒有窮多最優(yōu)解；⑶有沒有界解；⑷無可行解。⒊什么是LP問題標準型式，怎樣將非標準型LP問題轉(zhuǎn)化為標準型？LP問題標準型是：⑴目標函數(shù)取極大值；⑵約束條件取“=”號；2/352023/9/163⑶資源系數(shù)必須≥0；⑷決議變量必須≥0

對于任意一個非標準LP問題，可采取以下方法，將其變換為標準型：⑴若目標函數(shù)為求極小值minz=CX，則令z’=－z，便可得到maxz’=－CX；⑵假如某約束條件右端項（資源系數(shù)）<0，則該約束條件兩端同時乘“－1”，使其≥0；⑶假如約束條件為“≤”不等式，則在不等式左端加入一個非負松弛變量，使其變?yōu)榈仁剑?/352023/9/164⑷假如約束條件為“≥”不等式，則在不等式左端減去一個非負剩下變量，使其變?yōu)榈仁?；⑸若xj≤0，則令x’j=－xj，代入標準型，則有x’j≥0；⑹若xj正負不限，則令xj=x’j－x”j，而x’j≥0，x”j≥0。⒋試述LP問題基解、基可行解、可行解、最優(yōu)解概念以及上述解之間相互關(guān)系。4/352023/9/165⑴基解：在約束方程組②中，令全部非基變量Xm+1=xm+2=…=xn=0，此時，方程組②有唯一解XB=(x1,x2,…,xm)T，將此解加上非基變量取0值有X=(x1,x2,…xm,0,0,…,0)T，稱X為LP問題基解。5/352023/9/166⑵基可行解：滿足非負約束條件③解；⑵可行解：滿足約束條件②和③解；⑷最優(yōu)解：使目標函數(shù)①到達最大值可行解；⒌試述單純形法計算步驟，怎樣在單純形表上判別問題是含有唯一最優(yōu)解、無窮多最優(yōu)解、無界解或無可行解。在單純形表中，假如全部檢驗數(shù)σj≤0，基變量中不存在非零人工變量，非基變量中也不存在等于零檢驗數(shù)，此時解為唯一最優(yōu)解；假如在單純形表中，即使全部檢驗數(shù)σj≤0，但存在某非基變量檢驗數(shù)等于零，此時解為無窮多最優(yōu)解；6/352023/9/167假如在單純形表中，全部檢驗數(shù)σj≤0，基變量中存在非零人工變量，此時解為無可行解；假如在單純形表中，某檢驗數(shù)σj>0，而對應(yīng)Pj≤0，此時解為無界解。⒍假如LP問題標準型式變換為求目標函數(shù)極小化minz，則用單純形法計算時，怎樣判別問題已得到最優(yōu)解。7/352023/9/168

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

判斷以下說法是否正確圖解法同單純形法即使求解形式不一樣，但從幾何上了解，二者是一致。LP模型中增加一個約束條件，可行域范圍普通將縮小，降低一個約束條件，，可行域范圍普通將擴大。LP問題每一個基解對應(yīng)可行域一個頂點。如LP問題存在最優(yōu)解，則最優(yōu)解一定對應(yīng)可行域邊界上一個點?！獭痢獭?2/352023/9/1613e)對取值無約束變量xj，通常xj=x’j-x”j，其中x’j≥0，x”j≥0

√，在用單純形法求得最優(yōu)解有可能同時出現(xiàn)x’j>0，x”j>0?！翞楹握f是錯誤?請看下面例題：將以下LP問題變換成標準型，并用單純形法求解。MaxZ=-2x1-x2+3x3st.x1+x2+x3+x4=7x1-x2+x3-x5=2-3x1+x2+2x3+x6=5x3=x3'-x3''x3'>=0x3''>=013/352023/9/1614解：⑴用x3’-x3”替換x3，其中x3’，x3”≥0；⑵第一個約束條件左端加入一松弛變量x4；⑶第二個約束條件左端減去一剩下變量x5，再加上一個人工變量x6；⑸令z’=-z，把minz改為maxz’，即可得到該問題標準型（規(guī)范型）：⑷第三個約束條件左端加上一個人工變量x7；14/352023/9/1615解：用兩階段法求解第一階段LP問題為：用單純形法求解，先將其化為標準型15/352023/9/1616用兩階段法求解，第一階段求解過程以下：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-116/352023/9/1617第二階段，去掉人工變量，回歸到原問題：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/5017/352023/9/1618從上述最終一單純形表知，全部σj≤0，基變量中也不存在人工變量，故為最優(yōu)解，即X*=(x1,x2,x3’,x3”)=(1.8,0,37/4,0)，能夠證實，對取值無約束變量xj，假如令xj=x’j-x”j，其中x’j≥0，x”j≥0，在用單純形法求得最優(yōu)解不可能同時出現(xiàn)x’j>0，x”j>0。18/352023/9/1619f)用單純形法求解標準型式LP問題時，與σj>0對應(yīng)變量都能夠被選作換入變量。g)單純形法計算中，如不按最小比值標準選取換出變量，則在下一步解中最少有一個基變量值為負。h)單純形法計算中，選項取最大正檢驗數(shù)σk對應(yīng)變量xk作為換入變量，將使目標函數(shù)值得到最快√√19/352023/9/1620增加。i)一旦一個人工變量在迭代中變?yōu)榉腔兞亢螅撟兞考皩?yīng)數(shù)字能夠從單純形表中刪除，而不影響計算結(jié)果。j)LP問題任一可行解都能夠用全部基可行解線性組合表示。n)單純形法迭代過程是從一個可行解轉(zhuǎn)換到目標函數(shù)值更大另一個可行解?！痢獭痢桃驗楫斈繕撕瘮?shù)取minz時就不是得到最快增加。只有當該LP問題有唯一最優(yōu)解時才成立。20/352023/9/1621O)線性規(guī)劃問題可行解如為最優(yōu)解，則該可行解一定是基可行解；×

為何是錯誤？因為基可行解≠可行解。見P18。21/352023/9/1622第二章復(fù)習思索題⒉試從經(jīng)濟上解釋對偶問題及對偶變量含義。假如把LP原問題看作是在現(xiàn)有各項資源條件限制下，企業(yè)怎樣確定生產(chǎn)方案，使預(yù)期目標到達最優(yōu)。原問題變量是生產(chǎn)方案決議變量。對偶問題則是從另一角度提出問題，即假如其它企業(yè)想把企業(yè)資源收買過去，他要付出多大代價，才有可能使得企業(yè)放棄生產(chǎn)活動。對偶變量是資源出讓代價。22/352023/9/1623⒊依據(jù)原問題同對偶問題之間對應(yīng)關(guān)系，分別找出兩個問題之間、解以及檢驗數(shù)之間對應(yīng)關(guān)系。原問題同對偶問題之間對應(yīng)關(guān)系見后面兩表有唯一解對偶問題解是原問題最終單純形表中非基變量檢驗數(shù)。23/352023/9/1624原問題與對偶問題間關(guān)系以下表所表示:Maxz24/352023/9/162525/352023/9/1626從第二章對偶問題基本性質(zhì)看出，當線性規(guī)劃原問題求得最優(yōu)解xj*（j=1，…，n）時，其對偶問題也得到最優(yōu)解yi*（i=1，…，m），且代入各自目標函數(shù)后有：式中bi是線性規(guī)劃原問題約束條件右端項，它代表第i種資源擁有量；而對偶變量yi*意義代表在資源最優(yōu)利用條件下對第i種資源估價。這種估價不是資源市場價格，而是依據(jù)資源在生產(chǎn)中作出貢獻而作估價，它與資源緊缺度相關(guān)，某種資源越緊缺，這種估價便越高，若有剩下，這種估價便為0，為了將其與市場價格相區(qū)分，稱這種估價為影子價格。⒋什么是資源影子價格，同對應(yīng)市場價格之間有何區(qū)分，以及研究影子價格意義。26/352023/9/1627影子價格經(jīng)濟解釋⑴資源市場價格是已知數(shù)，相對比較穩(wěn)定，而它影子價格則有賴于資源利用情況，是隨企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)等情況改變而改變未知數(shù)。⑵影子價格是一個邊際價格，對上式z求bi偏導(dǎo)數(shù)得這說明yi*值相當于在資源得到最優(yōu)利用生產(chǎn)條件下，bi（第i種資源擁有量）每增加一個單位時目標函數(shù)z增量。27/352023/9/1628⒌試述對偶單純形法計算步驟，它優(yōu)點及應(yīng)用上不足。對偶單純形法計算步驟以下表所表示：28/352023/9/1629對偶單純形法計算步驟依據(jù)線性規(guī)劃問題列出初始單純形表b列數(shù)據(jù)均≥0?全部檢驗數(shù)＜0?xl所在行全部alk≥0?以alk為主元素,按原單純形法進行迭代運算,即重復(fù)上述步驟停頓計算已得到最優(yōu)解是否是否29/352023/9/1630對偶單純形法優(yōu)缺點分析

初始解能夠是非可行解(如原例初始解x4=-3,x5=-4就非可行解),只要檢驗數(shù)為負數(shù),就可進行基變換,不需加人加變量,可簡化計算

當變量數(shù)多于約束條件數(shù)時,用對偶單純形法計算可降低計算工作量,所以對變量少,而約束條件很多LP問題,可將其變換為對偶問題求解

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

對大多數(shù)LP問題,極難找到一個適適用對偶單純形法初始可行基對偶單純法優(yōu)點此法不足30/352023/9/1631⒍將aij，bi，cj改變分別直接反應(yīng)到最終單純形表中，表中原問題和對偶問題解各自將會出現(xiàn)什么改變，有多少種不一樣情況以及怎樣去處理。