計(jì)算機(jī)算法設(shè)計(jì)與分析--第8章 線性規(guī)劃與網(wǎng)絡(luò)流-文庫吧
2025-09-17 14:35 本頁面
【正文】 約束轉(zhuǎn)換為等式約束。具體做法是，引入 松弛變量 ，將不等式轉(zhuǎn)化為等式，且引入的松弛變量具有非負(fù)性 。 ?在求解過程中，應(yīng)當(dāng)將松弛變量與原來變量同樣對(duì)待。求解結(jié)束后，舍棄松弛變量。 2021年 11月 12日 16 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?設(shè)不等式約束形式為： ?引入一個(gè)松弛變量 s： ?使用 來表示與第 i個(gè)不等式關(guān)聯(lián)的松弛變量： ?等式左邊的變量稱為基本變量，等式右邊的變量稱為非基本變量。 injjij bxa ???101??? ??sxabsnjjiji01??? ??? ? innjjijiin xxabxinx ?2021年 11月 12日 17 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?一個(gè)例子 最大化： 滿足約束： 0,10834124272353253232532???????????xxxxxxxxxxx532 23 xxxz ????2021年 11月 12日 18 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?引入松弛變量 ， ， ，得到標(biāo)準(zhǔn)型： 最大化： 滿足約束： 4x1x 6x532 23 xxxz ????0,,83410421223765432153263245321????????????xxxxxxxxxxxxxxxxx2021年 11月 12日 19 標(biāo)準(zhǔn)型的元組表示 ?標(biāo)準(zhǔn)型的元組表示： ?N表示非基本變量下標(biāo)的集合； ?B表示基本變量下標(biāo)的集合； ?b表示由等式約束中的常數(shù)項(xiàng)組成的列向量； ?c表示目標(biāo)函數(shù)中非基本變量系數(shù)組成的行向量； ?v表示目標(biāo)函數(shù)中的常數(shù)項(xiàng)； ? 是一個(gè)矩陣，由所有等式約束中非基本變量 前系數(shù)的負(fù)值確定 ),,( vcbABNBif orxabxxcvzNjjijiiNjjj?????????)( ijaA?2021年 11月 12日 20 單純形表 ?標(biāo)準(zhǔn)型線性規(guī)劃的單純形表： x2 x3 x5 z 0 1 3 2 x1 7 3 1 2 x4 12 2 4 0 x6 10 4 3 8 532 23 xxxz ????0,,83410421223765432153263245321????????????xxxxxxxxxxxxxxxxx2021年 11月 12日 21 單純形算法 ?第 1步： 選 取 入基變量 。 ?選出使目標(biāo)函數(shù)增加的非基本變量作為 入基變量 。 ?查看單純形表的第 1行（也稱之為 z行）中標(biāo)有非基本變量的各列中的值，選擇系數(shù)為正的變量作為入基變量。 ?本例中，選取 x3作為入基變量。 2021年 11月 12日 22 單純形算法 ?第 2步： 選取 離基變量 。 ? 在單純形表中考察由第 1步選出的入基變量所相應(yīng)的列。 ? 如果入基變量所在的列與基本變量所在行交叉處的表元素為負(fù)數(shù)，那么該元素將不受任何限制，相應(yīng)的基本變量只會(huì)越變越大。 ? 如果入基變量所在列的所有元素都是負(fù)值，則目標(biāo)函數(shù)無界，已經(jīng)得到了問題的無界解。 ? 如果選出的列中有一個(gè)或多個(gè)元素為正數(shù)，要弄清是哪個(gè)數(shù)對(duì)入基變量值的增加限制更大。 ? 受限的增加量可以用入基變量所在列的元素（稱為 主元素 ）來除主元素所在行的 “ 常數(shù)列 ” 元素而得到。所得到數(shù)值越小說明受到限制越多。 ? 應(yīng)該選取受到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調(diào)位臵后，仍滿足約束條件。 ? 本例中，應(yīng)該選取 x4為離基變量。 2021年 11月 12日 23 單純形算法 ?第 3步：轉(zhuǎn)軸變換（主元操作） ?將入基變量與離基變量互調(diào)位臵。 ?解離基變量所相應(yīng)的方程，將入基變量 x3用離基變量 x4表示為： 423 41213 xxx ???2021年 11月 12日 24 單純形算法 ?再將其代入其他基本變量所在的行中消去 x3 ， ?將其代入目標(biāo)函數(shù)得到 ?形成新單純形表 542654218432512412510xxxxxxxx????????542 243219 xxxz ????x2 x4 x5 z 9 1/2 3/4 2 x1 10 5/2 1/4 2 x3 3 1/2 1/4 0 x6 1 5/2 3/4 8 2021年 11月 12日 25 ?第 4步： 轉(zhuǎn)回并重復(fù)第 1步，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值。 ? 不斷重復(fù)上述過程，直到新單純形表中 z行的所有非基本變量系數(shù)都變成負(fù)值為止。這表明目標(biāo)函數(shù)不可能再增加了，求解過程結(jié)束。 ? 整個(gè)問題的解可以從最后一張單純形表的常數(shù)列中讀出 。 ?目標(biāo)函數(shù)的最大值為 11； ?最優(yōu)解為： x*=(0,4,5,0,0,11) x=(4,5,0) x1 x4 x5 z 11 1/5 4/5 12/5 x2 4 5/2 1/10 4/5 x3 5 1/5 3/10 2/5 x6 11 1 1/2 10 單純形算法 2021年 11月 12日 26 ? 任何約束標(biāo)準(zhǔn)型線性規(guī)劃問題，只要將所有非基本變量都臵為 0，從約束方程式中解出滿足約束的基本變量的值，可求得一個(gè) 基本可行解 。 ? 單純形算法的基本思想就是從一個(gè)基本可行解出發(fā)，進(jìn)行一系列的 基本可行解的變換，每次變換都使基本可行解的目標(biāo)值不小于（通常是大于）前一次迭代中的目標(biāo)值 。 ? 每次變換將一個(gè)非基本變量與一個(gè)基本變量互調(diào)位臵，且保持當(dāng)前的線性規(guī)劃問題是一個(gè)與原問題 完全等價(jià)的標(biāo)準(zhǔn)線性規(guī)劃問題 。 單純形算法 2021年 11月 12日 27 ? ?? ?? ?????????????????????????elieilejieijijeieiileelleljejleleeaaaaaaadoeNje a c hf o rbabbdolBie a c hf o rn t sc o n s
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1