1、第四章 線性規(guī)劃,引言,什么是線性規(guī)劃 如果最優(yōu)化問題三要素中的目標(biāo)函數(shù)和約束條件都是線性的，則該最優(yōu)化問題稱為線性規(guī)劃問題 線性規(guī)劃的應(yīng)用和發(fā)展 線性規(guī)劃（Linear Programming，簡寫成LP）是最優(yōu)化理論和方法中的重要領(lǐng)域之一。其理論上的完整性、方法上的有效性以及應(yīng)用上的廣泛性，較其他分支都成熟的多，同時很多實際問題都可以轉(zhuǎn)化為線性規(guī)劃來解決 線性規(guī)劃的要點就是在滿足線性約束條件的前提下，使預(yù)定的線性目標(biāo)函數(shù)達到最優(yōu)?，F(xiàn)在線性規(guī)劃已不僅僅是一種數(shù)學(xué)方法，在理論上，它啟發(fā)了諸如對偶、凸性等最優(yōu)化理論的核心概念，在實際中更是大量被運用于經(jīng)濟學(xué)和管理學(xué)領(lǐng)域，成為科學(xué)決策的一個有效手段

2、 喬治丹齊格（G. B. Dantzig）被認(rèn)為是線性規(guī)劃之父。自從1947年他提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在應(yīng)用上也日益深入，成為科學(xué)與工程領(lǐng)域廣泛應(yīng)用的數(shù)學(xué)模型。特別是在計算機能處理海量約束條件和設(shè)計變量的線性規(guī)劃問題之后，線性規(guī)劃就更加受到青睞,線性規(guī)劃的典型實例,運輸問題 設(shè)有兩個建材廠C1和C2，每年沙石的產(chǎn)量分別為35萬噸和55萬噸，這些沙石需要供應(yīng)到W1、W2和W3三個建筑工地，每個建筑工地對沙石的需求量分別為26萬噸、38萬噸和26萬噸，各建材廠到建筑工地之間的運費（萬元/萬噸）如表所示，問題是應(yīng)當(dāng)怎么調(diào)運才能使得總運費最少？,線性規(guī)劃的典型實例

3、,運輸問題 問題分析 假設(shè)xij代表建材廠Ci運往建筑工地Wj的數(shù)量（萬噸），則各建材廠和工地之間的運量可以用下表來表示 目標(biāo)函數(shù)即為總運費 建材廠C1、 C2的輸出量應(yīng)分別為建材廠C1、 C2的產(chǎn)量 各工地的沙石需求量應(yīng)當(dāng)為從各建材廠接收到沙石的總量 運輸量xij為一非負(fù)值,線性規(guī)劃的典型實例,運輸問題 數(shù)學(xué)模型 線性規(guī)劃問題的特征 均可以用一組設(shè)計變量來表示一種實施方案 每個問題都有一定的約束條件，這些條件可以用一組線性等式或者線性不等式表達 在上述前提下，一般都有一個目標(biāo)函數(shù)，該函數(shù)用于衡量方案的優(yōu)劣，可以表達為設(shè)計變量的一個線性函數(shù)，我們的目的一般為使得目標(biāo)函數(shù)達到最大值或者最小值,線

4、性規(guī)劃問題的標(biāo)準(zhǔn)型,線性規(guī)劃問題的一般標(biāo)準(zhǔn)型 根據(jù)線性規(guī)劃的定義，線性規(guī)劃問題即求取設(shè)計變量x=x1, x2, xnT的值，在線性約束條件下使得線性目標(biāo)函數(shù)達到最大，線性規(guī)劃問題的一般標(biāo)準(zhǔn)型為： 其中，ci 、aij 、bi 為給定的常數(shù) 線性規(guī)劃問題的標(biāo)準(zhǔn)型的特點 目標(biāo)函數(shù)為設(shè)計變量的線性函數(shù)，且需要極大化； 約束條件為設(shè)計變量的一組線性等式，也稱為約束方程組； 設(shè)計變量x1, x2, xn都有非負(fù)限制。,線性規(guī)劃問題的標(biāo)準(zhǔn)型,線性規(guī)劃問題的矩陣標(biāo)準(zhǔn)型 利用向量或矩陣符號，線性規(guī)劃問題的標(biāo)準(zhǔn)型還可以用矩陣形式表達： 其中 為n維行向量 為mn維矩陣 為m維列向量 為n維列向量 是指其各分量,

5、線性規(guī)劃問題的標(biāo)準(zhǔn)型,不同類型的非標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型的方法 問題為極小化目標(biāo)函數(shù) 設(shè)原有線性規(guī)劃問題為極小化目標(biāo)函數(shù) 則可設(shè) 將極小化目標(biāo)函數(shù)問題轉(zhuǎn)化為極大化目標(biāo)函數(shù)問題 約束條件為不等式 如果原有線性規(guī)劃問題的約束條件為不等式，則可增加一個或減去一個非負(fù)變量，使約束條件變?yōu)榈仁?，增加或減去的這個非負(fù)變量稱為松弛變量。例如，假如約束為 則可以在不等式的左邊增加一個非負(fù)變量xn+1，使不等式變?yōu)榈仁?如果約束為 則可在不等式的左邊減去一個非負(fù)變量xn+1， 使不等式變?yōu)榈仁?模型中的某些變量沒有非負(fù)限制 若對某個變量xj并無限制，取值可正可負(fù)，這時可設(shè)兩個非負(fù)變量 和 ，令 注意到，因為對原設(shè)計變

6、量進行了代換，還需要將代換式代入目標(biāo)函數(shù)和其他約束條件做相應(yīng)的代換，這樣就可以滿足線性規(guī)劃標(biāo)準(zhǔn)型對變量非負(fù)的要求,線性規(guī)劃問題的標(biāo)準(zhǔn)型,例子 將線性規(guī)劃模型標(biāo)準(zhǔn)化 將目標(biāo)函數(shù)兩邊乘上-1轉(zhuǎn)化為求極大值 原問題的約束條件中的前兩個條件均為不等式，在第一個不等式的左邊加上一個松弛變量x4，在第二個不等式的左邊減去一個松弛變量x5，將兩者轉(zhuǎn)化為等式約束 原問題對設(shè)計變量x3沒有非負(fù)限制，故在此引入非負(fù)變量 和 ，令 經(jīng)過上述步驟整理后的標(biāo)準(zhǔn)型為,線性規(guī)劃問題中解的概念,概述 為了幫助分析線性規(guī)劃求解過程，先介紹線性規(guī)劃解的概念。仍然考慮式(4-2)中的線性規(guī)劃的矩陣標(biāo)準(zhǔn)型： 求解上述線性規(guī)劃問題實際

7、上就是要求出向量x=x1,x2,xnT使其滿足Ax=b和x0，且目標(biāo)函數(shù)f達到最大值，這個向量稱為線性規(guī)劃問題的解。 當(dāng)求解Ax=b時，假設(shè)獨立方程的個數(shù)為m個，設(shè)計變量的維數(shù)為n，根據(jù)線性代數(shù)的知識，如果m=n，則方程有唯一解，無優(yōu)化的自由度；如果mn，方程個數(shù)大于未知數(shù)的個數(shù)，則有些約束可能不能被滿足，上述兩類問題不在我們探討的范圍之列，也就是我們僅討論mn的情況，在這個前提下，方程將有無窮多組解，如果需要直接從這無窮多組解中找出一個非負(fù)解使得目標(biāo)函數(shù)取得最大值是很難的 下面將分步驟詳細(xì)分析如何獲得這個線性規(guī)劃問題的解，同時介紹在這類問題中的幾個概念,線性規(guī)劃問題中解的概念,基本解 如果線

8、性規(guī)劃問題的解存在，則它必定是滿足Ax=b的有限多個“基本解”中選出的，那么我們的第一個任務(wù)就是找出滿足方程Ax=b的基本解 假設(shè)獨立方程的個數(shù)為m個，故Ax=b的系數(shù)矩陣A的秩為m，于是A中必有m個列向量是線性無關(guān)的，不妨假設(shè)A中的前m個列向量線性無關(guān)，則這m個列向量可以構(gòu)成矩陣A的m階非奇異子矩陣，用矩陣B表示： B是一個m階的滿秩方陣，稱B為線性規(guī)劃問題的基，其每一個列向量Pj稱為基向量，基向量所對應(yīng)的設(shè)計變量稱為基變量，記為 A中其余n-m個列向量則構(gòu)成非基矩陣，用矩陣N表示： 非基矩陣N的每一個列向量稱為非基向量，非基向量所對應(yīng)的設(shè)計變量稱為非基變量，記為,線性規(guī)劃問題中解的概念,基

9、本解 根據(jù)上述分析，可以將方程組Ax=b轉(zhuǎn)化為 于是有 上式稱為約束方程組Ax=b的一個基本解， 一般來說，如果線性規(guī)劃問題中有n個設(shè)計變量，在Ax=b中有m個約束方程(nm)，則基本解的數(shù)量小于或等于 基本解不是線性規(guī)劃問題的解，而是僅滿足約束方程組的解,線性規(guī)劃問題中解的概念,可行解、可行域 上面的分析僅考慮了約束方程組Ax=b，下面進一步考慮線性規(guī)劃問題的非負(fù)約束。我們稱既滿足約束方程組Ax=b，又滿足非負(fù)約束x0的解為線性規(guī)劃問題的可行解，即可行解滿足線性規(guī)劃問題的所有約束。可行解的集合稱為可行域，記作： 基本可行解 特別的，若線性規(guī)劃問題的基本解能夠滿足線性規(guī)劃問題中的非負(fù)約束，即：

10、 則稱該解xB為基本可行解，簡稱基可行解，稱B為可行基?；尚薪獾臄?shù)量不會超過 個。顯然，基本可行解一定是可行解，基可行解是可行域中一種特殊的解 最優(yōu)解 能使得線性規(guī)劃問題的目標(biāo)函數(shù)值達到最大的可行解稱為最優(yōu)解。線性規(guī)劃問題中的最優(yōu)解，一定可以在基可行解中找到，而基可行解的數(shù)量是有限的，因而這就在理論上保證了可以在有限的步驟之內(nèi)求出線性規(guī)劃問題的最優(yōu)解。,線性規(guī)劃問題中解的概念,實例 線性規(guī)劃標(biāo)準(zhǔn)型為 于是 取矩陣A的線性無關(guān)列P1和P2構(gòu)成2階非奇異子矩陣 ，B1是線性規(guī)劃問題的一個 基矩陣，與其對應(yīng)的基變量為x1和x2，即 ，相應(yīng)的非基矩陣和非基變量分別為 令非基變量x3=0，可以求出對應(yīng)

11、基矩陣B1的基本解為 ，基矩陣B1解向量的各分量均為非負(fù)，故是線性規(guī)劃問題的基本可行解。如果這個解可以使得目標(biāo)函數(shù)取得最大值則該解為最優(yōu)解。是否最優(yōu)解的判斷方法將在后續(xù)的章節(jié)中探討。 若取矩陣A的后兩個線性無關(guān)列P2和P3，構(gòu)成線性規(guī)劃的另一個基矩陣 用相同的方法進行分析，可知，此時的基變量為x2和x3，非基變量為x1，于是令x1=0，可以得到對應(yīng)基矩陣B2的一組基本解為： ，由于對應(yīng)基矩陣B2解向量的第二個分量即x3為負(fù)，故該解不是線性規(guī)劃問題的基本可行解 由理論分析可知，該線性規(guī)劃問題基本解的個數(shù)為3個，也就是還可以選取P1和P3構(gòu)成基矩陣B3，求取該問題的第三個基本解，只要有一個基矩陣，

12、就可以求出一個對應(yīng)的基本解，至于該基本解是否基本可行解和最優(yōu)解則需要進一步判斷。,線性規(guī)劃問題的圖解法,用圖解法求解如下二維線性規(guī)劃問題 分析可行域 引入平面直角坐標(biāo)系，以x1作為橫軸，以x2作為縱軸，由于線性規(guī)劃問題滿足非負(fù)條件x1, x20，故問題的探討局限在平面直角坐標(biāo)系的第一象限 分析x1-2x24，取直線x1-2x2=4，則直線上的點和直線以上的區(qū)域滿足該不等式 分析x1+2x28，取直線x1+2x2=8，則直線上的點和直線以下的區(qū)域滿足不等式 于是可行域為四邊形ACBO內(nèi)的區(qū)域（包括邊界上的點），在圖中用陰影表示 分析最優(yōu)解 分析目標(biāo)函數(shù)f =x1+x2，可以將其改寫成為x2=-x

13、1+ f 可以發(fā)現(xiàn)改寫后的方程是以f為參量，以-1為斜率的一 族平行的直線，這些平行線越向右上方移動，離原點 越遠(yuǎn)，對應(yīng)的目標(biāo)函數(shù)值就越大。當(dāng)直線運動到經(jīng)過 點C時，即不能再繼續(xù)向上移動，否則將脫離線性規(guī) 劃問題的可行域，故線性規(guī)劃問題在點C達到最大值,線性規(guī)劃問題求解的單純形法,理論基礎(chǔ) 稱T(B)為對應(yīng)于基B的單純形表，b0j (j=1,2n)稱為檢驗數(shù) 線性規(guī)劃問題最優(yōu)解的判定 若T(B)中所有檢驗數(shù)b0j 0 (j=1,2n) ，則xB=B-1b-B-1NxN是最優(yōu)解。 若T(B)中有某一個檢驗數(shù)b0,m+s 0 ，且在該列中的bi,m+s0 (i=1,2,m)， 則線性規(guī)劃問題無最優(yōu)

14、解,線性規(guī)劃問題求解的單純形法,單純形迭代(步驟1) 建立初始單純形表T(B)，確定T(B)中的樞點（Pivot）項 確定進基變量 在所有b0j0的檢驗數(shù)中，選出最小的一個b0s，對應(yīng)的非基變量為xs , 此時，即已確定xs為進基變量，即下一次的迭代中將以xs作為進基變量 確定出基變量 取 （若有幾個相同的最小者，則取基變量下標(biāo)最小者）記 此時， 即已確定出基變量為xr 確定樞點項 由確定出基變量時所得的結(jié)論，可知，brs即被稱為樞點項，此時，需要對樞點項brs進行標(biāo)注，例如右上角加*號或者用括號括起來等方式，以便于后面的討論和分析,線性規(guī)劃問題求解的單純形法,單純形迭代(步驟2) 調(diào)換基變量

15、，構(gòu)造新基，構(gòu)造新的單純形表 確定新基 對單純形表進行變換 目的是使得下一步對基 的單純形表 進行適當(dāng)?shù)淖儞Q，使得向量 變?yōu)閱挝幌蛄浚词沟梅至縝rs取1，其它分量取0，在這個過程中運用的是Gauss-Jordan消元法，Gauss-Jordan消元法實際上就是下述兩次變換 第一次變換，使brs=1 為了使brs=1，只需將原表數(shù)用brs去除第r行各數(shù)，得新表第r行各數(shù)，即 第二次變換，使bis=0(0ir m) 為使新表中bis=0(0ir m) ，需將原表中第i行減去第r行相應(yīng)數(shù)的 倍，得新表第i行的數(shù)，即 換基后，新基 仍是一個可行基，且目標(biāo)函數(shù)值增加,線性規(guī)劃問題求解的單純形法,單純形

16、迭代(重復(fù)上述1,2過程) 按照上面步驟(1)(2)進行重復(fù)迭代，循環(huán)操作，以求得最優(yōu)解 特別注意 需要特別注意的是，如果基B對應(yīng)的單純形表T(B)中檢驗數(shù)有負(fù)數(shù)b0s0 ，且對應(yīng)的如下列向量非正，即： 那么，目標(biāo)函數(shù)無上界，即無最優(yōu)解。,線性規(guī)劃問題求解的單純形法,用單純形法求解線性規(guī)劃問題 將上述問題轉(zhuǎn)化為線性規(guī)劃標(biāo)準(zhǔn)型 確定A和Pi 確定xB1初始基、初始基矩陣B1、非基變量等 確定一個基本解,線性規(guī)劃問題求解的單純形法,確定初始單純形表 構(gòu)建初識單純形表如表所示，從行的角度說，表中的每一行代表一個約束方程（把目標(biāo)函數(shù)也看做是約束方程放在第一行）。從列的角度講，對于約束方程而言，表中的第

17、一列即為約束方程右邊的值，而對于目標(biāo)函數(shù)f則是填寫根據(jù)當(dāng)前基計算出來的目標(biāo)函數(shù)值。而其他的每一列則對應(yīng)于一個變量。 例如例題中的目標(biāo)函數(shù)為f=4x1+3x2，則改寫成f-4x1-3x2=0，故表的第一行右端系數(shù)為0，Value處填0，x1和x2處分別填-4和-3。而對于約束方程3x1+4x2+x3=12，其方程右端的值為12，故在Value處填12，在對應(yīng)變量的位置填3、4和1。 由例題求初始基可行解的過程可知，如果線性規(guī)劃標(biāo)準(zhǔn)型的向量b的每一個分量均為正的話，當(dāng)令所有的松弛變量為基時，總是可以找到一組基本可行解。這時每個基本變量的值等于其方程右端的常數(shù)。由于此時目標(biāo)函數(shù)的系數(shù)全都為零，所以對

18、應(yīng)的目標(biāo)函數(shù)值也為零。我們的目的就是要使用單純形法，通過變換運算，在每次迭代的最后，使得當(dāng)前基本變量對應(yīng)的矩陣B形成一個單位陣，并且目標(biāo)函數(shù)中對應(yīng)于基本變量的系數(shù)變?yōu)榱?。具有這種性質(zhì)的表稱之為規(guī)范型,初始單純形表,線性規(guī)劃問題求解的單純形法,單純形迭代 對單純形表進行判別 在單純形表4-3的檢驗數(shù)存在負(fù)數(shù)，即b01=-4、b03=-3，則可知基B1對應(yīng)的解不滿足最優(yōu)解條件，又b01、b03對應(yīng)的列向量中的分量有非負(fù)數(shù)，所以需要進行換基迭代。 確定進基變量、出基變量和樞點項 在兩個非負(fù)檢驗數(shù)中，取最小者b01=-4，b01對應(yīng)設(shè)計變量x1所在列，故x1為進基變 量，標(biāo)記進基變量所在列的符號s=1

19、；設(shè)計變量x1對應(yīng)的列向量為 ，3個分量b11=3、b21=3、b31=4均為正數(shù)，需要分別計算表單純形表中 的值，有 即選擇的是 ，于是r=3，樞點項為b31，樞點項所在行對應(yīng)的變量為x5，故出基變量為x5。我們把樞點項用括號括起來如表所示,標(biāo)記樞點項,線性規(guī)劃問題求解的單純形法,調(diào)換基變量，構(gòu)造新的基矩陣B2和單純形表 出基變量為x5，進基變量為x1，于是新的基矩陣 使得當(dāng)前基變量對應(yīng)的矩陣B2形成一個單位陣，并且目標(biāo)函數(shù)中對應(yīng)于基本變量的系數(shù)變?yōu)榱?，結(jié)果如表所示 在得到新的單純形表之后，一次迭代完成。 我們需要進行判斷是否進行再次迭代，采用的方法和上一次的迭代完全相同。,Gauss-Jo

20、rdan消元,線性規(guī)劃問題求解的單純形法,二次迭代 經(jīng)過與一次迭代完全相同的步驟，得到單純形表 在該單純形表中，檢驗數(shù)已沒有負(fù)數(shù)，故最新的基矩陣所對應(yīng)的基本可行解即是線性規(guī)劃問題的最優(yōu)解了。此時線性規(guī)劃問題的最優(yōu)解為： 對應(yīng)的目標(biāo)函數(shù)的極值為,二次迭代單純形表,一般情況下線性規(guī)劃問題求解的思路,何時使用大M法 我們可以看到在上面的例子中，不等式約束均有“”的形式，這樣才可以通過將非負(fù)松弛變量加到（而不是減去）每個不等式的左端，將不等式轉(zhuǎn)化為等式，這時，我們將所加的松弛變量作為初始基變量，所得到的基矩陣為一單位陣，可以很容易的獲得一個初始基本可行解進行單純形法的迭代。 但是在一般情況下，線性規(guī)劃

21、問題的約束條件存在等式和不等式，同時不等式也存在“”和“”，注意到當(dāng)約束方程組中含有“=”約束時，我們不需要加入非負(fù)松弛變量，當(dāng)約束方程組中含有“”約束時，我們需要減去一個非負(fù)松弛變量，在這兩種情況下就無法形成單位陣作為初始的基矩陣進行求解，即不能順利得到一個初始基本可行解，從而造成了迭代的困難。 于是我們需要找到一種系統(tǒng)處理方法，能夠比較方便的在各種約束條件下都能找到線性規(guī)劃問題的初始可行基本解使得單純形算法在任何約束下均有效。此時，我們需要用到人工變量，而將人工變量用于單純形求解中的算法主要有大M法和兩階段方法,線性規(guī)劃問題求解的大M法,大M法的求解原理 大M法的原理是，先將線性規(guī)劃問題變

22、換成標(biāo)準(zhǔn)型，然后將新的非負(fù)變量加到具有“=”或者“”類型約束的方程的左端，于是用這些新的變量作為基變量就可以構(gòu)成一個初始可行基。我們?nèi)藶榧尤氲倪@些非負(fù)變量就稱為人工變量。人工變量與松弛變量不同，它沒有明確的物理意義，只是為了獲得一個初始可行基而設(shè)置的。 但是對任何一個約束增加非負(fù)變量之后與原約束就是矛盾的，為了解決這個矛盾，使得新增加的變量對任一可行解無影響，我們在目標(biāo)函數(shù)中給新增加的變量賦以一個很大的負(fù)系數(shù)（因為線性規(guī)劃的標(biāo)準(zhǔn)型為目標(biāo)函數(shù)求極大），這個系數(shù)通常用M來表示，因而這個方法又叫大M法。在目標(biāo)函數(shù)中使用一個大的“-M”是迫使新的變量為零，否則目標(biāo)函數(shù)將遠(yuǎn)不能達到極大值。,線性規(guī)劃問題

23、求解的大M法,使用大M法求解線性規(guī)劃問題 引入人工變量x4和x5到約束等式的左邊 單純形法求解 首先取x4和x5作為初始基變量 令非基變量x1=x2= x3=0，得到一個基本解 解的各分量均為非負(fù)，故該基本解為線性規(guī)劃的一個基本可行解。故可用單純形法開始迭代。,線性規(guī)劃問題求解的大M法,單純形迭代 按照單純形法，構(gòu)造初始單純形表，注意其中含有M項，但這并不影響求解過程 上表并非單純形表的規(guī)范性，因為目標(biāo)函數(shù)對應(yīng)于基變量x4和x5的系數(shù)不為零，故我們采用矩陣的行變換將上表轉(zhuǎn)化為規(guī)范型 然后和單純形法一致，經(jīng)過迭代得到最終單純形表為 上表3中，檢驗數(shù)已沒有負(fù)數(shù)，故已經(jīng)求出線性規(guī)劃問題的的最優(yōu)解,線

24、性規(guī)劃問題求解的兩階段法,兩階段法的原理 兩階段也是用以解決具有“=”或者“”類型約束的線性規(guī)劃問題的初始可行解問題。顧名思義，該方法分為兩個階段進行： 第一階段 先引入松弛變量和人工變量，而目標(biāo)函數(shù)則由人工變量的和組成。這一步的工作是用單純形法把目標(biāo)函數(shù)對應(yīng)的所有的人工變量的值變?yōu)榱?。若第一階段最優(yōu)解對應(yīng)的目標(biāo)函數(shù)的最優(yōu)值為零，則所有人工變量一定都取零值，說明原問題存在基可行解，可以進行第二階段的計算；否則，原問題無可行解，停止計算。 第二階段 用原問題的的目標(biāo)函數(shù)代替人工目標(biāo)函數(shù)，用第一階段獲得的基本可行解作為該階段迭代的初始點進行單純形的換基迭代。,線性規(guī)劃問題求解的兩階段法,用二階段法

25、求解線性規(guī)劃問題 化為標(biāo)準(zhǔn)型 在原問題的不等式約束中分別加入松弛變量x4和x5，將上述問題化為標(biāo)準(zhǔn)型 在上述標(biāo)準(zhǔn)型問題中，由于不存在單位陣基矩陣，故我們需要引入人工變量人為的構(gòu)造出單位陣基矩陣，故我們采用兩階段法。,線性規(guī)劃問題求解的兩階段法,第一階段 構(gòu)造輔助問題，加入人工變量x6和x7，并將目標(biāo)函數(shù)表示稱為人工變量的和，目的就是為了構(gòu)造單位陣，輔助問題的形式如下： 我們用單純形法對該問題進行求解，可見，由于加入了人工變量，使得現(xiàn)在的輔助問題的約束方程組中形成了單位陣，即我們選取x4、x6和x7為基變量的話，基矩陣即是一個單位陣，然后在輔助問題的初始單純形表的基礎(chǔ)上將其轉(zhuǎn)換成為規(guī)范型如下 于

26、是在上述表的基礎(chǔ)上進行單純形迭代，以求出輔助問題的最優(yōu)解,線性規(guī)劃問題求解的兩階段法,第一階段 單純形迭代 一次迭代后的單純形表為 二次迭代后的單純形表為 檢驗數(shù)均非負(fù)，故輔助問題最優(yōu)解 此時，目標(biāo)函數(shù)最優(yōu)值 ，且人工變量已全部出基。故第一階段結(jié)束，轉(zhuǎn)入第二階段,線性規(guī)劃問題求解的兩階段法,第二階段 求解原線性規(guī)劃問題。這時以在第一階段篩選出來的基變量構(gòu)成基矩陣作為原線性規(guī)劃 問題的初始可行基，并將輔助問題的最優(yōu)解刪去人工變量的兩列，作為原線性規(guī)劃問題 的初始可行解，然后進行單純形算法的換基迭代 在這個問題中，初始可行基為： 初始可行解為： 在單純形表中刪去人工變量x6和x7這兩列，把第1行換

27、成原問題的目標(biāo)函數(shù)（消去基變量以后）的系數(shù)得到下表 可以看出，基變量x4，x2和x3沒有構(gòu)成單位陣，此時先要進行線性變化，例如在本例中就需要將f所在行減去x2所在行和x3所在行的和，之后得到新表就可以繼續(xù)換基迭代,線性規(guī)劃問題求解的兩階段法,第二階段 換基迭代，由上頁新表可知檢驗數(shù)b01為唯一的負(fù)數(shù)，故進基變量為x1，而在進基變量x1所在列中只有b11元素為正，進而確定樞點元素為b11，故出基變量為x4，然后使用Gauss-Jordan消元法結(jié)果如表所示，此時檢驗數(shù)已經(jīng)全部非負(fù)，故已找到該問題的最優(yōu)解 根據(jù)表上的數(shù)據(jù)可知，目標(biāo)函數(shù)的最大值在最優(yōu)解x*處取得：,線性規(guī)劃問題的MATLAB求解,M

28、ATLAB標(biāo)準(zhǔn)型 MATLAB標(biāo)準(zhǔn)型和前面理論知識講解中有所不同， 在上述模型中，有一個需要極小化的目標(biāo)函數(shù)f，以及需要滿足的約束條件 假設(shè)x為n維設(shè)計變量，且線性規(guī)劃問題具有不等式約束m1個，等式約束m2個，那么：c、x、lb 和ub 均為n維列向量，b為m1維列向量，beq為m2維列向量，A為m1n維矩陣，Aeq為m2n維矩陣 注意事項 MATLAB標(biāo)準(zhǔn)型是對目標(biāo)函數(shù)求極小，如果遇到是對目標(biāo)函數(shù)求極大的問題，在使用MATLAB求解時，需要在函數(shù)前面加一個負(fù)號轉(zhuǎn)化為對目標(biāo)函數(shù)求極小的問題； MATLAB標(biāo)準(zhǔn)型中的不等式約束形式為“”，如果在線性規(guī)劃問題中出現(xiàn)“”形式的不等式約束，則我們需要在

29、兩邊乘以(-1)使其轉(zhuǎn)化為MATLAB中的“”形式。如果在線性規(guī)劃問題中出現(xiàn)了“”的約束形式，則我們需要通過添加松弛變量使得不等式約束變?yōu)榈仁郊s束 之后，我們只需要將所有的約束（包括不等式約束和等式約束）轉(zhuǎn)化為矩陣形式的即可,線性規(guī)劃問題的MATLAB求解,將問題轉(zhuǎn)化為MATLAB標(biāo)準(zhǔn)型 原問題是對目標(biāo)函數(shù)求極大，故添加負(fù)號使目標(biāo)變?yōu)椋簃in f=-4x1+2x2-x3 原問題中存在“”的約束條件，故添加負(fù)號使其變?yōu)?x1-2x2+2x3-8 將約束整理為矩陣形式 用MATLAB表達則為,c=-4; 2; -1;%將目標(biāo)函數(shù)轉(zhuǎn)化為求極小 A=2 -1 1; 8 -2 2; b=12; -8;

30、%不等式約束系數(shù)矩陣 Aeq=-2 0 1; 1 1 0;beq=3; 7;%等式約束系數(shù)矩陣 lb=0; 0; 0;ub=Inf; Inf; Inf %對設(shè)計變量的邊界約束,線性規(guī)劃問題的MATLAB求解,函數(shù)調(diào)用格式 MATLAB優(yōu)化工具箱中求解線性規(guī)劃問題的命令為linprog，其函數(shù)調(diào)用方法有多種形式如下所示 x = linprog(c,A,b) x = linprog(c,A,b,Aeq,beq) x = linprog(c,A,b,Aeq,beq,lb,ub) x = linprog(c,A,b,Aeq,beq,lb,ub,x0) x = linprog(c,A,b,Aeq,beq

31、,lb,ub,x0,options) x = linprog(problem) x,fval = linprog(.) x,fval,exitflag = linprog(.) x,fval,exitflag,output = linprog(.) x,fval,exitflag,output,lambda = linprog(.),線性規(guī)劃問題的MATLAB求解,輸入?yún)?shù) MATLAB工具箱中的linprog函數(shù)在求解線性規(guī)劃問題時，提供的參數(shù)為：模型參數(shù)、初始解參數(shù)和算法控制參數(shù)。 模型參數(shù)x、c、lb、ub、b、beq、A和Aeq在MATLAB標(biāo)準(zhǔn)型中已經(jīng)介紹了其具體物理意義和獲得方法

32、x0為線性規(guī)劃問題的初始解，該設(shè)置僅在中型規(guī)模算法中有效，而在默認(rèn)的大型規(guī)模算法和單純形算法中，MATLAB將忽略一切初始解。 options為包含算法控制參數(shù)的結(jié)構(gòu)變量，我們可以通過optimset命令對這些具體的控制參數(shù)進行設(shè)置，例如下述格式 options = optimset(param1,value1,param2,value2,.) 該命令格式創(chuàng)建一組控制參數(shù)結(jié)構(gòu)變量options，將參數(shù)的具體值賦給單引號之間的參數(shù)，任何未被指定的參數(shù)將被賦值為，參數(shù)值為的具體的含義是將該組控制參數(shù)傳遞給優(yōu)化函數(shù)時將使用MATLAB提供的默認(rèn)值 在線性規(guī)劃問題中可以用到的設(shè)置參數(shù)如下一頁的表所示,

33、線性規(guī)劃問題的MATLAB求解,線性規(guī)劃問題的MATLAB求解,輸出參數(shù) linprog函數(shù)返回的輸出參數(shù)有x、fval、exitflag、lambda和output。 輸出參數(shù)x為線性規(guī)劃問題的最優(yōu)解 輸出參數(shù)fval為線性規(guī)劃問題在最優(yōu)解x處的函數(shù)值 輸出參數(shù)exitflag返回的是優(yōu)化函數(shù)計算終止時的狀態(tài)指示，說明算法終止的原因，其取值和其代表的具體原因如表所示,線性規(guī)劃問題的MATLAB求解,輸出參數(shù) 輸出參數(shù)output是一個返回優(yōu)化過程中相關(guān)信息的結(jié)構(gòu)變量，其屬性如表所示 輸出參數(shù)lambda是返回線性規(guī)劃問題最優(yōu)解x處的拉格朗日乘子的一個結(jié)構(gòu)變量,其總維數(shù)等于約束條件的個數(shù)，其非

34、零分量對應(yīng)于起作用的約束條件，其屬性如表所示。,線性規(guī)劃問題的MATLAB求解,命令詳解 x = linprog(c,A,b) 該函數(shù)調(diào)用格式求解線性規(guī)劃問題 x = linprog(c,A,b,Aeq,beq) 該函數(shù)調(diào)用格式求解線性規(guī)劃問題 即該函數(shù)調(diào)用格式解決的是既含有線性等式約束，又含有線性不等式約束的線性規(guī)劃問題，如果在線性規(guī)劃問題中無線性不等式約束，則可以設(shè)A=以及b= x = linprog(c,A,b,Aeq,beq,lb,ub) 該函數(shù)調(diào)用格式求解線性規(guī)劃問題 即在線性規(guī)劃問題的求解過程中進一步考慮了對設(shè)計變量的約束，其中l(wèi)b和ub均是和設(shè)計變量維數(shù)相同的列向量，如果對設(shè)計變

35、量沒有上界約束，可以設(shè)置ub(i) = Inf，如果沒有下界約束則可以設(shè)置lb(i) = -Inf，和(2)類似，如果問題中沒有等式約束，則可以設(shè)Aeq=以及beq=,線性規(guī)劃問題的MATLAB求解,命令詳解 x = linprog(c,A,b,Aeq,beq,lb,ub,x0) 在前面調(diào)用方法的基礎(chǔ)上設(shè)置線性規(guī)劃問題求解的初始解為x0，該參數(shù)僅在使用有效集算法時生效，否則當(dāng)使用默認(rèn)的內(nèi)點算法時，將忽略任何初始點，即參數(shù)無效。 x = linprog(c,A,b,Aeq,beq,lb,ub,x0,options) 用options指定的優(yōu)化參數(shù)進行最小化?？梢允褂胦ptimset來設(shè)置這些參數(shù)

36、 x,fval = linprog(.) 在優(yōu)化計算結(jié)束之時返回線性規(guī)劃問題在解x處的目標(biāo)函數(shù)值fval。 x,fval,exitflag = linprog(.) 在優(yōu)化計算結(jié)束之時返回exitflag值，描述函數(shù)計算的退出條件。 x,fval,exitflag,output = linprog(.) 在優(yōu)化計算結(jié)束之時返回返回結(jié)構(gòu)變量output x,fval,exitflag,output,lambda = linprog(.) 在優(yōu)化計算結(jié)束之時返回線性規(guī)劃問題最優(yōu)解x處的拉格朗日乘子lambda,線性規(guī)劃問題的MATLAB求解,用MATLAB求解線性規(guī)劃問題,c=-1;-1;%目標(biāo)函

37、數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù) A=1 -2;1 2;%線性不等式約束 b=4;8; lb=0;0;%設(shè)計變量的邊界約束，由于無上界，故設(shè)置ub=Inf;Inf; ub=Inf;Inf; x,fval=linprog(c,A,b,lb,ub) Optimization terminated. x = 6.0000 1.0000 fval = -7.0000,線性規(guī)劃問題的MATLAB求解,用MATLAB求解線性規(guī)劃問題,c=-4;-3; %目標(biāo)函數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù) A=3 4;3 3;4 2;%線性不等式約束 b=12;10;8; lb=0;0;

38、 %設(shè)計變量的邊界約束，由于無上界，故設(shè)置ub=Inf;Inf ub=Inf;Inf; x,fval,exitflag=linprog(c,A,b,lb,ub) x = 0.8000 2.4000 fval = -10.4000 exitflag = 1,線性規(guī)劃問題的MATLAB求解,用MATLAB求解線性規(guī)劃問題,c=-1;-3;1; %目標(biāo)函數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù) Aeq=1 1 2;-1 2 1;%線性等式約束 beq=4;4; lb=0;0;0;%設(shè)計變量的邊界約束，由于無上界，故設(shè)置ub=Inf;Inf;Inf ub=Inf;Inf;Inf; x,fval

39、,exitflag=linprog(c,Aeq,beq,lb,ub) Optimization terminated. x = 1.3333 2.6667 0.0000 fval = -9.3333 exitflag = 1,線性規(guī)劃問題的MATLAB求解,用MATLAB求解線性規(guī)劃問題,c=-3;1;1;%目標(biāo)函數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù) A=1 -2 1;4 -1 -2;%線性不等式約束 b=11;-3; Aeq=-2 0 1;%線性等式約束 beq=1; lb=0;0;0;%設(shè)計變量的邊界約束，由于無上界，故設(shè)置ub=Inf;Inf;Inf ub=Inf;Inf;I

40、nf; x,fval,exitflag,output,lambda=linprog(c,A,b,Aeq,beq,lb,ub) Optimization terminated. x = 4.0000 1.0000 9.0000 fval = -2.0000 exitflag = 1,線性規(guī)劃問題的MATLAB求解,生產(chǎn)計劃問題 問題的提出 某工廠需要生產(chǎn)A、B兩種產(chǎn)品以滿足市場的需求。這兩種產(chǎn)品的生產(chǎn)均需要經(jīng)過兩道工藝流程。每生產(chǎn)1kg的A產(chǎn)品在第一道工藝流程耗時4小時，在第二道工藝流程耗時6小時；每生產(chǎn)1kg的B產(chǎn)品在第一道工藝流程耗時6小時，在第二道工藝流程耗時8小時，由于生產(chǎn)計劃的要求，可

41、供用的第一道工藝流程工時為240小時，第二道工藝流程工時為480小時。 在化學(xué)品生產(chǎn)的過程中一般會伴隨著副產(chǎn)品的生產(chǎn)，該工廠在生產(chǎn)B產(chǎn)品的同時，會產(chǎn)出副產(chǎn)品C，每生產(chǎn)1kg的B產(chǎn)品會產(chǎn)生2kg的副產(chǎn)品C，而不需外加任何費用，由于副產(chǎn)品C的利用率問題，使得產(chǎn)品C中的一部分可盈利，其他部分只能報廢。 根據(jù)核算，出售1kg的A產(chǎn)品可盈利600元，出售1kg的B產(chǎn)品可以盈利1000元，出售1kg的C產(chǎn)品可以盈利300元，而報廢1kg的C產(chǎn)品需要虧損200元。 經(jīng)市場預(yù)測，在計劃期內(nèi)，產(chǎn)品C最大銷售量為50kg，此時，應(yīng)當(dāng)如何安排A、B兩種產(chǎn)品的產(chǎn)量，使該工廠的預(yù)計總盈利可以達到最大。,線性規(guī)劃問題的M

42、ATLAB求解,生產(chǎn)計劃問題 問題分析 在本例中，重點是設(shè)計變量的選取方法。因為副產(chǎn)品C的出現(xiàn)和限制銷售量使得問題顯得稍復(fù)雜。如果我們用x1和x2分別代表產(chǎn)品A和產(chǎn)品B的產(chǎn)量，作為該問題的設(shè)計變量，由于產(chǎn)品C的產(chǎn)量為2x2，且如果2x2大于50的話，其小于50的部分會產(chǎn)生盈利，但其超出的部分會產(chǎn)生虧損，即產(chǎn)品C的單位利潤會在300和-200之間變化，在這個前提下，總利潤和產(chǎn)量之間就產(chǎn)生了非線性關(guān)系，我們會發(fā)現(xiàn)在確定目標(biāo)函數(shù)和約束條件時比較困難。于是，我們需要另辟蹊徑，尋求設(shè)計變量的選擇方法，解決這個問題。 由于MATLAB為線性規(guī)劃的求解打開了方便之門，于是我們的選擇設(shè)計變量的余地就很大，在兩

43、個設(shè)計變量難以解決的前提下，我們可以設(shè)置多個設(shè)計變量，使得目標(biāo)函數(shù)和約束條件均為線性。,線性規(guī)劃問題的MATLAB求解,生產(chǎn)計劃問題 問題解答 從產(chǎn)品C的約束出發(fā)，既然C產(chǎn)品可能產(chǎn)生盈利，也可能產(chǎn)生虧損，則設(shè)置相應(yīng)的設(shè)計變量來表示其產(chǎn)生盈利的部分和產(chǎn)生虧損的部分，即產(chǎn)品C的銷售量和報廢量，故在這個原則下，我們得到問題的設(shè)計變量為： 產(chǎn)品A的產(chǎn)量： x1 產(chǎn)品B的產(chǎn)量： x2 產(chǎn)品C的銷售量：x3 產(chǎn)品C的報廢量：x4 于是產(chǎn)品C的產(chǎn)量即為其銷售量和報廢量之和，即x3+ x4 將預(yù)計總盈利作為該問題的目標(biāo)函數(shù) C是伴隨產(chǎn)品B出現(xiàn)的，其數(shù)量之間滿足的約束關(guān)系 C的最大銷量為50kg 每道工藝流程的

44、總工時是確定的，例如第一道工藝， 生產(chǎn)x1kg的A耗時4x1小時，生產(chǎn)x2kg的B要6x2小時， 其總和必須小于240小時；對第二道工藝流程的分 析也一樣,線性規(guī)劃問題的MATLAB求解,生產(chǎn)計劃問題 線性規(guī)劃數(shù)學(xué)模型 由上述結(jié)果可知，當(dāng)A產(chǎn)品的產(chǎn)量為22.5kg，B產(chǎn)品的產(chǎn)量為25kg時，該工廠預(yù)計盈利的最大值為5.35萬元，其中伴隨B產(chǎn)品產(chǎn)生的C產(chǎn)品恰好為50kg，為可銷售的最大值。,c=-600;-1000;-300;200; A=2 3 0 0;3 4 0 0;0 0 1 0; b=120;240;50; Aeq=0 -2 1 1; beq=0; lb=0;0;0;0; ub=Inf;

45、Inf;Inf;Inf; x,fval=linprog(c,A,b,Aeq,beq,lb,ub) Optimization terminated. x = 22.5000 25.0000 50.0000 0.0000 fval = -5.3500e+004,線性規(guī)劃問題的MATLAB求解,連續(xù)投資問題 問題的提出 某機構(gòu)現(xiàn)在擁有資本200萬元，為了獲取更大的收益，該機構(gòu)決定將這200萬元進行投資，以期最大回報，現(xiàn)在共有四個方案可供選擇，投資的方式為每年初將機構(gòu)持有的所有資本都用于投資。 方案1：從第1年到第4年的每年年初都需要投資，次年末回收本利1.15 方案2：第3年初投資，到第5年末收回本

46、利1.25，最大投資額為80萬元 方案3：第2年初投資，到第5年末收回本利1.40，最大投資額為60萬元 方案4：每年初投資，每年末收回本利1.06 那么應(yīng)該采用何種投資組合策略，使得該機構(gòu)5年末的總資本最大,線性規(guī)劃問題的MATLAB求解,連續(xù)投資問題 問題分析 由于方案有4種可選，且每種開始投資的期限一般也不相同，故選擇設(shè)計變量時需要考慮這兩個因素，最直觀的選法是令xij為第i年初投資方案j的資金數(shù)，此時，設(shè)計變量可以用下表來表示：,線性規(guī)劃問題的MATLAB求解,連續(xù)投資問題 問題解答 在第1年時，將所有的100萬元用于投資，可選方案1和方案2 由于在第1年年末投資方案4的資金在第1年年

47、末即收回本利1.06，故該部分資金即1.06x14可用于第2年的投資，即 方案3的最大投資額為60萬元 可用于第3年投資的資本數(shù)來源于第1年投資方案1收回的本利1.15x11和第2年投資方案4收回的本利1.11x24，故 方案2的最大投資額為80萬元 可用于第4年投資的資本數(shù)來源于第2年投資方案1收回的本利1.15x21和第3年投資方案4收回的本利1.11x34，故 可用于第5年投資的資本數(shù)來源于第3年投資方案1收回的本利1.15x31和第4年投資方案4收回的本利1.11x44，故,線性規(guī)劃問題的MATLAB求解,連續(xù)投資問題 問題解答 通過上述連續(xù)投資方式，在第5年末可以獲得的本利資本總和為

48、： 我們的目的就是選擇最佳的投資策略，極大化目標(biāo)函數(shù)f的值 線性規(guī)劃數(shù)學(xué)模型,線性規(guī)劃問題的MATLAB求解,連續(xù)投資問題 由運行結(jié)果可知，采取上述最佳投資方案之后，在第5年末所得到的總資本數(shù)為 287.5萬元。,c=0;0;0;-1.40;0;0;-1.25;0;-1.15;0;-1.06; Aeq=1 1 0 0 0 0 0 0 0 0 0; 0 1.06 -1 -1 -1 0 0 0 0 0 0; 1.15 0 0 0 1.06 -1 -1 -1 0 0 0; 0 0 1.15 0 0 0 0 1.06 -1 -1 0 0 0 0 0 0 1.15 0 0 0 1.06 -1; beq=200;0;0;0;0; lb=0;0;0;0;0;0;0;0;0;0;0; ub=Inf;Inf;Inf;60;Inf;Inf;80;Inf;Inf;Inf;Inf; x,f