計算機算法分析與設(shè)計

1、第八章 線性規(guī)劃與網(wǎng)絡(luò)流,理解線性規(guī)劃算法模型 掌握解線性規(guī)劃問題的單純形算法 理解網(wǎng)絡(luò)與網(wǎng)絡(luò)流的基本概念 掌握網(wǎng)絡(luò)最大流的增廣路算法 掌握網(wǎng)絡(luò)最大流的預(yù)流推進算法 掌握網(wǎng)絡(luò)最小費用流的消圈算法 掌握網(wǎng)絡(luò)最小費用流的最小費用路算法 掌握網(wǎng)絡(luò)最小費用流的網(wǎng)絡(luò)單純形算法,學(xué)習(xí)要點,線性規(guī)劃問題和單純形算法,線性規(guī)劃問題及其表示 線性規(guī)劃問題可表示為如下形式： s.t.,線性規(guī)劃問題和單純形算法,變量滿足約束條件(8.2)-(8.5)式的一組值稱為線性規(guī)劃問題的一個可行解。 所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的可行區(qū)域。 使目標(biāo)函數(shù)取得極值的可行解稱為最優(yōu)解。 在最優(yōu)解處目標(biāo)函數(shù)的值稱為最優(yōu)值。

2、有些情況下可能不存在最優(yōu)解。 通常有兩種情況： 根本沒有可行解，即給定的約束條件之間是相互排斥的，可行區(qū)域為空集； 目標(biāo)函數(shù)沒有極值，也就是說在n維空間中的某個方向上，目標(biāo)函數(shù)值可以無限增大，而仍滿足約束條件，此時目標(biāo)函數(shù)值無界。,線性規(guī)劃問題和單純形算法,這個問題的解為 (x1, x2, x3, x4) = (0, 3.5, 4.5, 1)；最優(yōu)值為16。,線性規(guī)劃基本定理,約束條件(8.2)-(8.5)中n個約束以等號滿足的可行解稱為線性規(guī)劃問題的基本可行解。若nm，則基本可行解中至少有n-m個分量為0，也就是說，基本可行解中最多有m個分量非零。 線性規(guī)劃基本定理：如果線性規(guī)劃問題有最優(yōu)解

3、，則必有一基本可行最優(yōu)解。 上述定理的重要意義在于，它把一個最優(yōu)化問題轉(zhuǎn)化為一個組合問題，即在(8.2) -(8.5)式的m+n個約束條件中，確定最優(yōu)解應(yīng)滿足其中哪n個約束條件的問題。 由此可知，只要對各種不同的組合進行測試，并比較每種情況下的目標(biāo)函數(shù)值，直到找到最優(yōu)解。,線性規(guī)劃基本定理,Dantzig于1948年提出了線性規(guī)劃問題的單純形算法。 單純形算法的特點是： 只對約束條件的若干組合進行測試，測試的每一步都使目標(biāo)函數(shù)的值增加； 一般經(jīng)過不大于m或n次迭代就可求得最優(yōu)解。,約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法,當(dāng)線性規(guī)劃問題中沒有不等式約束(8.2)和(8.4)式，而只有等式約束(8.3

4、)和變量非負約束(8.5)時，稱該線性規(guī)劃問題具有標(biāo)準(zhǔn)形式。 為便于討論，不妨先考察一類更特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問題。這一類線性規(guī)劃問題中，每一個等式約束中，至少有一個變量的系數(shù)為正，且這個變量只在該約束中出現(xiàn)。 在每一約束方程中選擇一個這樣的變量，并以它作為變量求解該約束方程。這樣選出來的變量稱為左端變量或基本變量，其總數(shù)為m個。剩下的n-m個變量稱為右端變量或非基本變量。,約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法,這一類特殊的標(biāo)準(zhǔn)形式線性規(guī)劃問題稱為約束標(biāo)準(zhǔn)型線性規(guī)劃問題。 雖然約束標(biāo)準(zhǔn)型線性規(guī)劃問題非常特殊，但是對于理解線性規(guī)劃問題的單純形算法是非常重要的。 稍后將看到，任意一個線性規(guī)劃問題可

5、以轉(zhuǎn)換為約束標(biāo)準(zhǔn)型線性規(guī)劃問題。,約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法,約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法,任何約束標(biāo)準(zhǔn)型線性規(guī)劃問題，只要將所有非基本變量都置為0，從約束方程式中解出滿足約束的基本變量的值，可求得一個基本可行解。 單純形算法的基本思想就是從一個基本可行解出發(fā)，進行一系列的基本可行解的變換。 每次變換將一個非基本變量與一個基本變量互調(diào)位置，且保持當(dāng)前的線性規(guī)劃問題是一個與原問題完全等價的標(biāo)準(zhǔn)線性規(guī)劃問題。 基本可行解x=(7,0,0,12,0,10)。 單純形算法的第1步：選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量。,約束標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形算法,查看單純形表的第1行（也稱之為z行）中標(biāo)有非基本變量的各列中的值。 選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量。 z行中的正系數(shù)非基本變量都滿足要求。 在上面單純形表的z行中只有1列為正，即非基本變量相應(yīng)的列，其值為3。 選取非