《數(shù)學(xué)》基礎(chǔ)模塊上冊(cè)課件5.3解線性規(guī)劃問(wèn)題的表格法

1、第五章第五章 線性規(guī)劃線性規(guī)劃 對(duì)于多于兩個(gè)決策變量的線性規(guī)劃問(wèn)題，可以用什么方法呢？求線性規(guī)劃問(wèn)題的圖解法雖然直觀簡(jiǎn)便，求線性規(guī)劃問(wèn)題的圖解法雖然直觀簡(jiǎn)便，但對(duì)多于兩個(gè)變量的情況就不能適用了但對(duì)多于兩個(gè)變量的情況就不能適用了. 這就是我們要學(xué)習(xí)的用表格法表格法解線性規(guī)劃問(wèn)題.1.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式:nnxcxcxcxcZ.max332211jjnjxcZ1max( 用和式表示為 ), 3 , 2 , 1( , 0), 3 , 2 , 1( ,1njxmibxajijijnj滿足 目標(biāo)函數(shù)目標(biāo)函數(shù)資源系數(shù)資源系數(shù)決策變量決策變量目標(biāo)函數(shù)系目標(biāo)函數(shù)系數(shù)數(shù)2.線性規(guī)劃模型

2、化為標(biāo)準(zhǔn)型步驟線性規(guī)劃模型化為標(biāo)準(zhǔn)型步驟 ：第一步：化目標(biāo)函數(shù)第一步：化目標(biāo)函數(shù)若 nnxcxcxcxcZ.min332211可轉(zhuǎn)化為： ).(max332211nnxcxcxcxcZ第二步：化決策變量第二步：化決策變量(1)若約束條件不等式是“”加一個(gè)松弛變量加一個(gè)松弛變量(2)若約束條件不等式是“”減一個(gè)多余變量減一個(gè)多余變量 (3)若有一個(gè)變量kxslkxxxlxsx可令其中0，0.非負(fù)變量非負(fù)變量非負(fù)變量非負(fù)變量.例例1 將5.1節(jié)問(wèn)題1中的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)型 0, 0210534001041802621212121xxxxxxxx約束條件目標(biāo)函數(shù) 212231maxxxZ 解 分

3、別對(duì)前三個(gè)約束條件引入松弛變量，得標(biāo)準(zhǔn)型. 5 , 2 , 1, 02100053400001041800026543215432154321jxxxxxxxxxxxxxxxxj 目標(biāo)函數(shù) 212231maxxxZ約束條件 1.標(biāo)準(zhǔn)型中的約束條件方程轉(zhuǎn)換成表格的形式標(biāo)準(zhǔn)型中的約束條件方程轉(zhuǎn)換成表格的形式. 5 , 2 , 1, 02100053400001041800026543215432154321jxxxxxxxxxxxxxxxxjx1x2x3x4x5bi6210018041001040035001210表格中的列數(shù)為變量個(gè)數(shù)加表格中的列數(shù)為變量個(gè)數(shù)加1，行數(shù)為方程個(gè)數(shù)加，行數(shù)為方程個(gè)數(shù)

4、加1 5.3.2表格法表格法 2.找初始解組找初始解組 jcBcBX3x4x5x4x5xib1x2x3x21010053040001010401800012600002231當(dāng)當(dāng) ， ，時(shí)，時(shí)， ， ， 顯然這是一組可行解顯然這是一組可行解.我們把它他叫作出初始解組我們把它他叫作出初始解組. 01x02x1803x4004x2105x初始解組初始解組各約束方程的各約束方程的系數(shù)系數(shù) 增加1行(叫做檢驗(yàn)行)和1列(叫做比值列) jcBcBX1x2x3x4x5xibi3x4x5xj21010053040001010401800012600002231檢驗(yàn)數(shù)行檢驗(yàn)數(shù)行比值列比值列檢驗(yàn)數(shù)計(jì)算公式檢驗(yàn)數(shù)

5、計(jì)算公式,1ijmiijjacc 選取檢驗(yàn)數(shù)最大的正數(shù)所在列(記作k列，表中用 表示)然后計(jì)算比值i312200003010070 3.調(diào)整初始解組調(diào)整初始解組 換入 ，換出1x3x21010(4)004000100180001310002231jcBcBX1x2x3x4x5xibi4x5xj 03350013420301x3132661322193063190換入 ，換出2x5x 0300102220100020001310002231jcBcBX1x2x3x4x5xibi4xj 006131x24512581128024891215x411235所以 0 ，當(dāng)前可行解 ， 為最優(yōu)解.j201x,302x0, 0, 0543xxx刪去松弛變量 原線性規(guī)劃當(dāng) 最優(yōu)解為 0, 0, 0543xxx,201x,302x.1280Z jkikakxkx用表格法解題的步驟：用表格法解題的步驟：第一步：建立初始表格；第二步：檢驗(yàn)所有的0，則當(dāng)前有可行解；否則0,且0，則無(wú)最優(yōu)解；否則，將重復(fù)第二步，第三步，第四步直到找到最優(yōu)解.