1、習(xí)題講解,課程：運籌學(xué) 內(nèi)容：第一章課后習(xí)題解,作業(yè)分類匯總,1、LP問題解四種情況的判別 習(xí)題： 1.1(a)、1.1(b)、1.7(b) 2、LP問題解的基本概念 習(xí)題：1.2(b)、1.3(a) 3、LP問題的標(biāo)準(zhǔn)形式轉(zhuǎn)化 習(xí)題：1.6(a) 4、單純形法的計算 (標(biāo)準(zhǔn)型的系數(shù)矩陣中不包含單位矩陣的情況） 習(xí)題：1.7(b) 5、單純形法計算的向量矩陣描述及特征應(yīng)用 習(xí)題：1.8、1.12 6、現(xiàn)實問題應(yīng)用 習(xí)題：1.13、1.14 7、證明題 習(xí)題：1.16、1.17,END,線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)形式,即：1.目標(biāo)函數(shù)求極大值max z；2.全部是等式約束；3.常數(shù)項非負(fù) （b 0

2、）；4.變量非負(fù) （X 0 ) ；5.nm。,一般形式的線性規(guī)劃數(shù)學(xué)模型轉(zhuǎn)化為標(biāo)準(zhǔn)形式,1.目標(biāo)函數(shù)為求最小值： 作變換，令z=(-z),化為求： max z = -( c1x1 +c2x2 + cnxn ) 2.約束條件為不等式：當(dāng)約束條件為時，加一非負(fù)的松弛變量。 當(dāng)約束條件為時，減一非負(fù)的剩余變量。 注：松弛變量在目標(biāo)函數(shù)中的系數(shù)為0 3.取值無約束的變量：作變換，令xj=xj-xj(xj,xj0),即將其化為兩個非負(fù)變量之差。 4.負(fù)變量 (xj0): 作變換,令xj= - xj ,0 5.常數(shù)項為負(fù)： 約束兩端同乘（-1）即可。,幾種解的基本概念,1.可行解： 滿足系統(tǒng)約束條件和非負(fù)

3、性約束的解X=(x1 ,x2 , xn )T,稱為LP問題的可行解。 2.最優(yōu)解：滿足目標(biāo)函數(shù)值最大的可行解稱為LP的最優(yōu)解。 3.基（本）解：設(shè)B為LP問題的一個基，在系統(tǒng)約束方程組中，令非基變量xm+1= xm+2 =xn =0, 而B是滿秩的，由克萊姆法則，可解出由m個基變量表示的唯一解XB= (x1 ,x2 , xm)T 或X= (x1 ,x2 , xm，0，0)T ，稱X為LP問題的一個基解。 4.基（本）可行解：滿足變量非負(fù)性約束的基解稱為基可行解。,LP問題解四種情況的判別,1、LP問題的解總有四種情況： 唯一最優(yōu)解 無窮多最優(yōu)解 無界解 無可行解 2、判別方式： 圖解法：直觀性

4、強，但有其局限性，只適用于問題中有兩個變量的情況。 單純形法。,圖解法,唯一最優(yōu)解 無窮多最優(yōu)解,無界解 無可行解,單純形法,單純形法計算的矩陣描述,均左乘矩陣B-1,課后題答案,課后題答案,1.2（b）答案：,課后題答案,1.3 答案： 單純形法：圖解法：,課后題答案,1.6（a）答案： 標(biāo)準(zhǔn)形式： 初始單純形表：,課后題答案,1.7（b）答案： 大M法： 兩階段法： 最優(yōu)解為： 因為：30，有非基變量檢驗數(shù)為0，所以該問題有無窮多最優(yōu)解。 且，目標(biāo)函數(shù)最優(yōu)值為Z*=7.,課后題答案,1.8 答案： 最后結(jié)果：a3，b=2, c=4, d=-2, e=2, f=3, g=1, h=0, i=

5、5, j=5, k=-3/2, L=0.,課后題答案,1.12 答案 最后結(jié)果：b=5, c1= 3/2, c2=2, c3 =3,課后題答案,1.13 答案： 解：設(shè)該廠第i個月辦理租借合同，租借j個月，租借面積為xij，則該問題的線性規(guī)劃模型為：,課后題答案,1.14 答案： 解：設(shè)產(chǎn)品在A1B1上生產(chǎn)的數(shù)量記為x111，A1B2 、A1B3 、A2B1 、A2B2 、A2B3依次記為x112，x113，x121，x122，x123，產(chǎn)品在A1B1、A2B1上生產(chǎn)的數(shù)量記作x211，x221，III產(chǎn)品在A2B2上生產(chǎn)的數(shù)量記作x322，建立模型如下：,A1,A2,B1,B3,B2,III （一種方式）,A工序,B工序,I （2*3=6種方式）,II （2種方式）,課后題答案,課后題答案,1.16 答案： 由X*為最優(yōu)解，可得此時：=C-CBB-1A0 (a) X*仍為最優(yōu)解,max z=CX；=C-CBB-1A=(C-CBB-1A)0 (b)一般X*不再是問題的最優(yōu)解。 =(C+)-(CB+B)B-1A=(C-CBB-1A)+(-BB-1A )(c)最優(yōu)解變?yōu)閄*，最優(yōu)值不變。令X*=X/,課后題答案,1.17 答案：