計算機算法設(shè)計與分析--第8章線性規(guī)劃與網(wǎng)絡(luò)流-在線瀏覽
2024-12-03 14:35本頁面
【正文】 15 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?對最小化線性規(guī)劃問題，只要將目標(biāo)函數(shù)乘以1即可化為等價的最大化線性規(guī)劃問題。具體做法是，引入 松弛變量 ，將不等式轉(zhuǎn)化為等式，且引入的松弛變量具有非負(fù)性 。求解結(jié)束后，舍棄松弛變量。 injjij bxa ???101??? ??sxabsnjjiji01??? ??? ? innjjijiin xxabxinx ?2021年 11月 12日 17 將一般線性規(guī)劃轉(zhuǎn)換成約束標(biāo)準(zhǔn)型 ?一個例子 最大化： 滿足約束： 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ù)項組成的列向量； ?c表示目標(biāo)函數(shù)中非基本變量系數(shù)組成的行向量； ?v表示目標(biāo)函數(shù)中的常數(shù)項； ? 是一個矩陣，由所有等式約束中非基本變量 前系數(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步： 選 取 入基變量 。 ?查看單純形表的第 1行（也稱之為 z行）中標(biāo)有非基本變量的各列中的值，選擇系數(shù)為正的變量作為入基變量。 2021年 11月 12日 22 單純形算法 ?第 2步： 選取 離基變量 。 ? 如果入基變量所在的列與基本變量所在行交叉處的表元素為負(fù)數(shù)，那么該元素將不受任何限制，相應(yīng)的基本變量只會越變越大。 ? 如果選出的列中有一個或多個元素為正數(shù)，要弄清是哪個數(shù)對入基變量值的增加限制更大。所得到數(shù)值越小說明受到限制越多。 ? 本例中，應(yīng)該選取 x4為離基變量。 ?解離基變量所相應(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ù)值。這表明目標(biāo)函數(shù)不可能再增加了，求解過程結(jié)束。 ?目標(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，從約束方程式中解出滿足約束的基本變量的值，可求得一個 基本可行解 。 ? 每次變換將一個非基本變量與一個基本變量互調(diào)位臵，且保持當(dāng)前的線性規(guī)劃問題是一個與原問題 完全等價的標(biāo)準(zhǔn)線性規(guī)劃問題 。 ?再引入 m個 人工變量 ，記為 zi，構(gòu)造成約束標(biāo)準(zhǔn)型。 ?這個線性規(guī)劃問題稱為原線性規(guī)劃問題所相應(yīng)的輔助線性規(guī)劃問題。 ?單純形算法第一階段的任務(wù)就是構(gòu)造一個初始基本可行解。 ?????miizz12021年 11月 12日 32 2階段單純形算法 ?第二階段： ?第二階段的目標(biāo)是求解由第一階段導(dǎo)出的問題。 2021年 11月 12日 33 ? 用單純形算法解一般的線性規(guī)劃問題時，可能會遇到退化的情形，即在迭代計算的某一步中，常數(shù)列中的某個元素的值變成 0，使得相應(yīng)的基本變量取值為 0。在這種情況下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無限循環(huán)。 規(guī)則 1：設(shè) ，取 xe為入基變量。 ? ?0|m in ?? jcje??????????????? ieialelabablkie 0m i n|m i n2021年 11月 12日 34 提綱 一、線性規(guī)劃問題和單純形算法 二、最大網(wǎng)絡(luò)流問題 三、最小費用流問題 2021年 11月 12日 35 基本概念和術(shù)語 ?網(wǎng)絡(luò) ?G是一個簡單有向圖， G=(V,E)， V={1， 2， … ， n}。如果 (v,w)∈ E，則假定 cap(v,w)＝ 0。一般情況下，滿足 s沒有入邊， t沒有出邊。 2021年 11月 12日 36 基本概念和術(shù)語 ?網(wǎng)絡(luò)流 ?網(wǎng)絡(luò)上的 流 是定義在網(wǎng)絡(luò)的邊集合 E上的一個非負(fù)函數(shù) flow={flow(v,w)}，并稱 flow(v,w)為邊 (v,w)上的流量 。 ?平衡約束 ： 對于中間頂點
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1