用表格法解線性規(guī)劃問(wèn)題

18.3用表格法解線性規(guī)劃問(wèn)題新知一、線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式：新知線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式的特點(diǎn)：（1）目標(biāo)函數(shù)為最大值形式；（2）約束條件用等式表示，且等式右端的常數(shù)為非負(fù)數(shù)；（3）決策變量非負(fù)。新知線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式的方法：（1）對(duì)于目標(biāo)函數(shù)，如果是則令就得到新知線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式的方法：（2）對(duì)于約束條件，如果有則在不等式（或等式）兩邊同乘以“-1”新知線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式的方法：（3）對(duì)于約束條件中的不等式，如果是≤，則在左端加上一個(gè)變量使其成為等式；如果是≥，則在左端減去一個(gè)變量使其成為等式。添加的變量稱(chēng)為人工變量。人工變量不產(chǎn)生效益，所以規(guī)定其在目標(biāo)函數(shù)中系數(shù)為0例題解析例1將18.1例1中的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式：例題解析例1將18.1例1中的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式：解用x1,x2分別取代x,y,則標(biāo)準(zhǔn)形式為：因?yàn)椤?所以加上人工變量。例題解析例2將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形式：例題解析解令z’=-z，則標(biāo)準(zhǔn)形式為：因?yàn)椤?所以減去人工變量。練習(xí)1練習(xí)2新知表格法解線性規(guī)劃問(wèn)題解:(1)建表把目標(biāo)函數(shù)和約束方程轉(zhuǎn)換成表格：新知第2,3行是約束方程的系數(shù)和常數(shù)項(xiàng)，第4行的數(shù)是目標(biāo)函數(shù)的系數(shù)，第一列是人工變量。341025010010120045新知（2）確定換入變量考慮第4行中的正數(shù)，因?yàn)?>4，將”5”所在列的決策變量x1定位換入變量。341025010010120045新知（3）確定換出變量將b所在列的數(shù)除以變量x1所在列中對(duì)應(yīng)的數(shù)341025010010120045將較小商數(shù)對(duì)應(yīng)的除數(shù)“2”所在行的人工變量x4定為換出變量。新知（4）進(jìn)行變換，消元變量x1所在行和列的交叉點(diǎn)的數(shù)是2，為了方便消元，將“2”變成“1”。所以這行的數(shù)都除以“2”.341025010010120045150新知（4）進(jìn)行變換，消元將第2,4行中x1所在列的數(shù)都化為0341025000045150將第3行的所有數(shù)乘以“-3”，分別與第2行中對(duì)應(yīng)的數(shù)相加，所得結(jié)果替換第2行。0100將第3行的所有數(shù)乘以“-5”，分別與第4行中對(duì)應(yīng)的數(shù)相加，所得結(jié)果替換第4行。0-250++因第4行中還有正數(shù),故重復(fù)（2）~（5）步驟。直到第4行中不再有正數(shù)為止。新知（5）重復(fù)操作，得出最優(yōu)解11000001500-250新知（5）重復(fù)操作，得出最優(yōu)解11000001500-250確定換入變量考慮第4行中的正數(shù)，因?yàn)?/p>

，將””所在列的決策變量x2定位換入變量。新知（5）重復(fù)操作，得出最優(yōu)解11000001500-250確定換出變量將b所在列的數(shù)除以變量x1所在列中對(duì)應(yīng)的數(shù)將較小商數(shù)對(duì)應(yīng)的除數(shù)“”所在行的人工變量x3定為換出變量。進(jìn)行變換，消元變量x2所在行和列的交叉點(diǎn)的數(shù)是

，為了方便消元，將“”變成“1”。所以這行的數(shù)都除以.新知（5）重復(fù)操作，得出最優(yōu)解11000001500-250140新知（5）重復(fù)操作，得出最優(yōu)解400001500-2501將第3,4行中x2所在列的數(shù)都化為0將第2行的所有數(shù)乘以“”，分別與第3行中對(duì)應(yīng)的數(shù)相加，所得結(jié)果替換第3行。將第3行的所有數(shù)乘以“”，分別與第4行中對(duì)應(yīng)的數(shù)相加，所得結(jié)果替換第4行。030++0-310新知（5）重復(fù)操作，得出最優(yōu)解4001300-310100此時(shí)第4行不再有正數(shù)第2,3行中行與列的同一決策變量交叉處為1決策變量x1和x2所在行的最后一個(gè)數(shù)就是最優(yōu)解新知