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

1、第五章第五章 線性規(guī)劃線性規(guī)劃 對于多于兩個決策變量的線性規(guī)劃問題，可以用什么方法呢？求線性規(guī)劃問題的圖解法雖然直觀簡便，求線性規(guī)劃問題的圖解法雖然直觀簡便，但對多于兩個變量的情況就不能適用了但對多于兩個變量的情況就不能適用了. 這就是我們要學(xué)習(xí)的用表格法表格法解線性規(guī)劃問題.1.線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(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)若約束條件不等式是“”加一個松弛變量加一個松弛變量(2)若約束條件不等式是“”減一個多余變量減一個多余變量 (3)若有一個變量kxslkxxxlxsx可令其中0，0.非負(fù)變量非負(fù)變量非負(fù)變量非負(fù)變量.例例1 將5.1節(jié)問題1中的線性規(guī)劃問題化為標(biāo)準(zhǔn)型 0, 0210534001041802621212121xxxxxxxx約束條件目標(biāo)函數(shù) 212231maxxxZ 解 分

3、別對前三個約束條件引入松弛變量，得標(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ù)為變量個數(shù)加表格中的列數(shù)為變量個數(shù)加1，行數(shù)為方程個數(shù)加，行數(shù)為方程個數(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，則無最優(yōu)解；否則，將重復(fù)第二步，第三步，第四步直到找到最優(yōu)解.