數(shù)學(xué)1108徐祖儀(線性規(guī)劃求解算法研究)

1、摘要 線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用最廣泛的一個(gè)分支本文主要是針對(duì)線性規(guī)劃問題的相關(guān)算法進(jìn)行了綜述和原理的講解分別闡述了線性規(guī)劃的發(fā)展歷程和線性規(guī)劃的數(shù)學(xué)模型,詳細(xì)研究了單純形法和內(nèi)點(diǎn)法的主要原理和算法,并為后續(xù)研究提供了一個(gè)借鑒方向最后給出了線性規(guī)劃問題的原-對(duì)偶內(nèi)點(diǎn)算法,通過數(shù)值實(shí)驗(yàn)表明該算法具有很好的收斂性與穩(wěn)定性關(guān)鍵詞:線性規(guī)劃,單純形法,內(nèi)點(diǎn)法，原-對(duì)偶內(nèi)點(diǎn)法Abstract Linear programming is widely applied in all branches of Operation ResearchThis paper mainly describes the rel

2、evant algorithm of linear programming problem and explains their principleThe development of linear programming and the mathematical model of linear programming algorithm are described respectivelyThe main principles of simplex method and interior point methods are analyzed in detail which provide a

3、 reference direction for the follow-up study Finally,we give numerical examples about the primal- dual interior point algorithm for linear programming,the numerical experiment results show that the algorithm has perfect convergence and stabilityKey words：Linear programming,simplex method, Interior p

4、oint methods, Primal-dual interior point method 目錄1. 引言11.1 課題背景11.2 發(fā)展?fàn)顩r11.3 課題內(nèi)容22. 線性規(guī)劃問題和數(shù)學(xué)模型22.1 線性規(guī)劃問題及其表示22.2 線性規(guī)劃基本定理32.3 約束標(biāo)準(zhǔn)型線性規(guī)劃問題42.4 將一般問題轉(zhuǎn)化為約束標(biāo)準(zhǔn)型4241 目標(biāo)函數(shù)是求最小值4242 約束方程為不等式4243模型中的某些變量沒有非負(fù)限制53. 單純形法63.1 單純形法的基本原理63.2 單純形算法計(jì)算步驟73.3 MATLAB中求解線性規(guī)劃問題83.4 應(yīng)用實(shí)例93.5 單純形法的進(jìn)一步討論123.5.1 一般線性規(guī)劃問題

5、的2階段單純形算法123.5.2 退化情形的處理124. 內(nèi)點(diǎn)法134.1 內(nèi)點(diǎn)法的基本原理135. 原-對(duì)偶內(nèi)點(diǎn)算法155.1 基本原理155.2 算法的具體步驟155.3 應(yīng)用實(shí)例16參考文獻(xiàn)191. 引言1.1 課題背景 線性規(guī)劃是運(yùn)籌學(xué)中應(yīng)用廣泛的一個(gè)重要分支，是合理利用、調(diào)配資源的一種應(yīng)用數(shù)學(xué)方法在日常的生產(chǎn)實(shí)踐中，如何取得最大的經(jīng)濟(jì)效益是我們十分重視的問題要提高經(jīng)濟(jì)效益一般可以通過兩種途徑：一是改進(jìn)技術(shù)，例如改善生產(chǎn)工藝，使用新設(shè)備和新型原材料二是改進(jìn)生產(chǎn)組織與計(jì)劃，即合理安排人力物力資源而線性規(guī)劃的基本思路就是在滿足一定的約束條件下，使預(yù)定的目標(biāo)達(dá)到最優(yōu)它研究的內(nèi)容可大致分為兩個(gè)

6、方面：一是在一定的資源條件下，如何分配能使任務(wù)完成得最好如最高產(chǎn)量、最大利潤(rùn)等問題；二是任務(wù)量一定時(shí)，如何統(tǒng)籌安排，以最少的資源完成這項(xiàng)任務(wù)如最低成本、最短距離等問題前者和后者分別是求極大值和極小值問題總之, 線性規(guī)劃就是在一定限制條下, 求目標(biāo)函數(shù)極值的問題自1947年丹捷格研究出線性規(guī)劃問題的求解算法單純形法之后，線性規(guī)劃在理論上趨向成熟，在實(shí)用中日益廣泛與深入特別是隨著計(jì)算機(jī)技術(shù)的發(fā)展，線性規(guī)劃的適用領(lǐng)域更為廣泛，它已成為人們?yōu)楹侠砝糜邢拶Y源制定最佳決策的重要工具 1.2 發(fā)展?fàn)顩r 線性規(guī)劃求解算法的研究和發(fā)展經(jīng)歷了3個(gè)重要時(shí)期，每一個(gè)時(shí)期的發(fā)展都受到極大的關(guān)注自1947年丹捷格提出了

7、單純形法，憑著成熟的算法理論和完善的算法，它統(tǒng)治線性規(guī)劃長(zhǎng)達(dá)30多年單純形法的基本原理是從一個(gè)初始解出發(fā)，通過反復(fù)迭代改進(jìn)現(xiàn)有的解，直到得到需要的最優(yōu)解單純形法以它簡(jiǎn)單、實(shí)用的特點(diǎn)成為目前常用的方法 然而，在1972年有數(shù)學(xué)家揭示了單純形算法的時(shí)間復(fù)雜度可能是指數(shù)型的問題從計(jì)算復(fù)雜性來看，單純形算法不是一種好算法于是很多計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家對(duì)線性規(guī)劃是否存在多項(xiàng)式算法十分感興趣 1979年前蘇聯(lián)數(shù)學(xué)家哈奇揚(yáng)提出了計(jì)算復(fù)雜性為的橢球算法，它是第1個(gè)理論上優(yōu)于單純形法的所謂多項(xiàng)式時(shí)間算法，但遺憾的是廣泛的數(shù)值試驗(yàn)表明橢球算法的計(jì)算比單純形方法差 1984年，印度數(shù)學(xué)家卡瑪卡爾提出了另一個(gè)計(jì)算復(fù)雜性

8、為的多項(xiàng)式時(shí)間算法，這個(gè)算法從理論和數(shù)值上都優(yōu)于橢球算法，因而受到學(xué)術(shù)界的高度重視此后，許多學(xué)者致力于改進(jìn)和完善這一算法，得到了許多改進(jìn)算法這些算法運(yùn)用不同的思想方法均獲得通過可行區(qū)域內(nèi)部的迭代點(diǎn)列，因此統(tǒng)稱為解線性規(guī)劃問題的內(nèi)點(diǎn)算法雖然內(nèi)點(diǎn)算法的理論比較成熟，但因?yàn)槌跏純?nèi)點(diǎn)難以找到，所以應(yīng)用起來還是有難度，內(nèi)點(diǎn)算法的研究也始終停留在理論上1989年，Renato D.C.Monteiro和I.Adler給出了求解線性規(guī)劃一個(gè)原-對(duì)偶內(nèi)點(diǎn)法其迭代次數(shù)為,計(jì)算復(fù)雜性為,這是目前理論上最好的求解線性規(guī)劃的多項(xiàng)式算法由于該算法對(duì)初始點(diǎn)的要求很嚴(yán)格這就給數(shù)值實(shí)驗(yàn)帶來更大的困難 為了克服內(nèi)點(diǎn)算法的不足，

9、從20世紀(jì)年90代開始學(xué)者著重于線性規(guī)劃的不可行內(nèi)點(diǎn)算法的研究不可行內(nèi)點(diǎn)算法又稱之為外點(diǎn)算法， 1.3 課題內(nèi)容近十年來, 隨著計(jì)算機(jī)和算法理論的發(fā)展, 準(zhǔn)確快速地解決大規(guī)模線性規(guī)劃問題已成為可能提到線性規(guī)劃算法，人們最先想到的是單純形法和內(nèi)點(diǎn)法單純形法是實(shí)際應(yīng)用中使用最普遍的一種線性規(guī)劃算法，而研究者們已證明在最壞的情況下單純形法的計(jì)算復(fù)雜度是指數(shù)級(jí)的，內(nèi)點(diǎn)算法的計(jì)算復(fù)雜度是多項(xiàng)式時(shí)間的把兩種算法相提并論，要么是這兩種算法都已經(jīng)非常完備，要么都有需改進(jìn)之處顯然不屬于前者，即兩者都有需要改進(jìn)之處本文分析了線性規(guī)劃問題，給出了求解線性規(guī)劃問題的單純形法和內(nèi)點(diǎn)法最后給出了線性規(guī)劃問題的原-對(duì)偶內(nèi)點(diǎn)

10、算法, 數(shù)值實(shí)驗(yàn)表明該算法具有很好的收斂性與穩(wěn)定性2. 線性規(guī)劃問題和數(shù)學(xué)模型2.1 線性規(guī)劃問題及其表示 線性規(guī)劃問題可表示為如下形式： s.t. 上面各式中，是個(gè)獨(dú)立變量 式（2.1）是線性規(guī)劃問題的目標(biāo)函數(shù)目標(biāo)函數(shù)極小值的線性規(guī)劃問題也可以轉(zhuǎn)換為與之等價(jià)的求目標(biāo)函數(shù)極大值的線性規(guī)劃問題 式（2.2)式（2.5)是線性規(guī)劃問題的約束條件式（2.2)有個(gè)不等式約束；式（2.3)有個(gè)不式約束；式（2.4)有個(gè)不等式約束約束的總個(gè)數(shù)為所有約束的右端參數(shù)規(guī)定為非負(fù)數(shù)，即，式（2.5)是線性規(guī)劃問題的變量非負(fù)性約束條件 目標(biāo)函數(shù)和約束條件都為線性函數(shù)，所以稱為線性規(guī)劃問題線性規(guī)劃問題是在一組線性規(guī)劃

11、條件的限制下，求一線性目標(biāo)函數(shù)最大或最小值的問題 變量滿足約束條件式（2.2)式（2.5)的一組值稱為線性規(guī)劃問題的一個(gè)可行解所有可行解構(gòu)成的集合稱為線性規(guī)劃問題的可行區(qū)域使目標(biāo)函數(shù)取得極值的可行解稱為最優(yōu)解在最優(yōu)解處目標(biāo)函數(shù)的值稱為最優(yōu)值有些情況下可能不存在最優(yōu)解通常有兩種情況： (1)根本沒有可行解，即給定的約束條件之間是相互排斥的，可行區(qū)域?yàn)榭占?(2)目標(biāo)函數(shù)沒有極值，也就是說在維空間中的某個(gè)方向上，目標(biāo)函數(shù)值可以無限增大，而仍滿足約束條件，此時(shí)目標(biāo)函數(shù)值無界 下面給出線性規(guī)劃問題的一個(gè)具體例子 （2.6） s.t （2.7） 例子中，這個(gè)問題的解為 ；最優(yōu)值為16下面將詳細(xì)討論如火

12、如何求解2.2 線性規(guī)劃基本定理 使約束條件式（2.2)式（2.5)中的某n個(gè)約束以等號(hào)滿足的可行解稱為線性規(guī)劃問題的基本可行解若，則基本可行解中至少有個(gè)分量為0，也就是說，基本可行解中最多有個(gè)分量非零線性規(guī)劃基本定理：如果線性規(guī)劃問題有最優(yōu)解，則必有一基本可行最優(yōu)解上述定理的重要意義在于，它把一個(gè)最優(yōu)化問題轉(zhuǎn)化為一個(gè)組合問題，即在式（22)式（2.5)式的個(gè)約束條件中，確定最優(yōu)解應(yīng)滿足其中哪個(gè)約束條件的問題由此可知，只要對(duì)各種不同的組合進(jìn)行測(cè)試，并比較每種情況下的目標(biāo)函數(shù)值，就能找到最優(yōu)解 2.3 約束標(biāo)準(zhǔn)型線性規(guī)劃問題當(dāng)線性規(guī)劃問題中沒有不等式約束式(2.2)和式(2.4)，而只有等式約束

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

14、要將所有非基本變量都置為0，從約束方程式中解出滿足約束的基本變量的值，可求得一個(gè)基本可行解2.4 將一般問題轉(zhuǎn)化為約束標(biāo)準(zhǔn)型2.4.1目標(biāo)函數(shù)是求最小值若要求目標(biāo)函數(shù)實(shí)現(xiàn)極小化，即這時(shí)只需將目標(biāo)函數(shù)最小化變換為求目標(biāo)函數(shù)最大化，即令于是得到必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但它們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)2.4.2 約束方程為不等式 需要把(22)或(24)形式的不等式約束轉(zhuǎn)換為等式約束具體做法是引入松弛變量，利用松弛變量的非負(fù)性將不等式轉(zhuǎn)化為等式松馳變量記為，共有個(gè)在求解過程中，應(yīng)當(dāng)將松弛變量與原來變量同樣對(duì)待求解結(jié)束后，拋棄松弛變量注意松弛變量前的符號(hào)由相應(yīng)的原不等式的方向所確

15、定為了進(jìn)一步構(gòu)造標(biāo)準(zhǔn)型約束，還需要引入m個(gè)人工變量，記為至此，原問題已經(jīng)變換為等價(jià)的約束標(biāo)準(zhǔn)型線性規(guī)劃問題例2.1 將下列不等式約束轉(zhuǎn)換為標(biāo)準(zhǔn)型約束 解：引入松弛變量 引入人工變量 2.4.3 模型中的某些變量沒有非負(fù)限制若某個(gè)變量可正可負(fù)，這時(shí)可以令 ，其中，即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號(hào)限制的變量，當(dāng)然的符號(hào)取決于和的相對(duì)大小，這樣就可以滿足標(biāo)準(zhǔn)型的要求3. 單純形法3.1 單純形法的基本原理單純形算法的基本思想就是從一個(gè)基本可行解出發(fā)，進(jìn)行一系列的基本可行解的變換每次變換將一個(gè)非基本變量與一個(gè)基本變量互調(diào)位置，且保持當(dāng)前的線性規(guī)劃問題是一個(gè)與原問題完全等價(jià)的標(biāo)準(zhǔn)線性規(guī)劃問題單純形表

16、：為基本變量， 為非基本變量基本變量下標(biāo)集為B=1,2,m； 非基本變量下標(biāo)集為N=m+1,m+2,n；當(dāng)前基本可行解為（）表格 3-1 當(dāng)前單純形表xm+1xm+2xnzc0cm+1cm+2cnx1b1a1m+1a1m+2a1nx2b2a2m+1a2m+2a2nMMxmbmamm+1amm+2amn 單純形算法的第1步：選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量查看單純形表的第1行（也稱之為z行）中標(biāo)有非基本變量的各列中的值，依次讓每一非基本變量從當(dāng)前值開始增加，同時(shí)保持其余非基本變量仍為0；然后考察變化結(jié)果，看目標(biāo)函數(shù)值是增加還是減小考察的目的是選出使目標(biāo)函數(shù)增加的非基本變量作為入基變量容

17、易看出z行中的正系數(shù)非基本變量都滿足要求單純形算法的第2步：選取離基變量在單純形表中考察由第1步選出的入基變量所相應(yīng)的列在基本變量變?yōu)樨?fù)值之前，查看入基變量可以增到多大如果入基變量所在的列與基本變量所在行交叉處的表元素為負(fù)數(shù)，那么該元素將不受任何限制，相應(yīng)的基本變量只會(huì)越變?cè)酱笕绻牖兞克诹械乃性囟际秦?fù)值，則目標(biāo)函數(shù)無界，說明已經(jīng)得到了問題的無界解如果選出的列中有一個(gè)或多個(gè)元素為正數(shù)，那么就要弄清是哪個(gè)數(shù)限制了入基變量值的增加顯然，這一受限的增加量可以用入基變量所在列的元素（稱為主元素）來除主元素所在行的“常數(shù)列”（最左邊的列）中元素而得到所得到數(shù)值越小說明受到限制越多因此，應(yīng)該選取受

18、到限制最多的基本變量作為離基變量，才能保證將入基變量與離基變量互調(diào)位置后，仍滿足約束條件 單純形算法的第3步：轉(zhuǎn)軸變換轉(zhuǎn)軸變換的目的是將入基變量與離基變量互調(diào)位置給入基變量一個(gè)增值，使之成為基本變量；同時(shí)修改離基變量，讓入基變量所在列中離基變量所在行的元素值減為零，并使之成為非基本變量單純形算法的第4步：轉(zhuǎn)回并重復(fù)第1步，進(jìn)一步改進(jìn)目標(biāo)函數(shù)值不斷重復(fù)上述過程，直到z行的所有非基本變量系數(shù)都變成負(fù)值為止這表明目標(biāo)函數(shù)不可能再增加了3.2 單純形算法計(jì)算步驟 單純形算法的計(jì)算過程可以用單純形表的形式歸納為一系列基本矩陣運(yùn)算主要運(yùn)算為轉(zhuǎn)軸變換，該變換類似解線性方程組的高斯消去法中的消元變換 單純形算

19、法計(jì)算步驟如下： 步驟1：選入基變量 如果所有，則當(dāng)前基本可行解為最優(yōu)解，計(jì)算結(jié)束否則，取相應(yīng)的非基本變量為入基變量 步驟2：選離基變量 對(duì)于步驟1選出的入基變量，如果所有，則最優(yōu)解無界，計(jì)算結(jié)束否則,計(jì)算選取基本變量為離基變量 新的基本變量下標(biāo)集為新的非基本變量下標(biāo)集為 步驟3：作轉(zhuǎn)軸變換 新單純形表中各元素變換如下 （31） （32） （33） （34） 步驟4：轉(zhuǎn)步驟13.3 MATLAB中求解線性規(guī)劃問題MATLAB解決的線性規(guī)劃問題的標(biāo)準(zhǔn)形式為：min s.t. 其中f、x、b、beq、lb、ub為向量，A、Aeq為矩陣其它形式的線性規(guī)劃問題都可經(jīng)過適當(dāng)變換化為此標(biāo)準(zhǔn)形式Matlab

20、優(yōu)化工具箱中有現(xiàn)成函數(shù)linprog對(duì)的LP問題求解函數(shù) linprog 的調(diào)用格式 x = linprog(f,A,b) %求min f ' *x subto 線性規(guī)劃的最優(yōu)解 x = linprog(f,A,b,Aeq,beq) %等式約束，若沒有不等式約束，則A= ，b= x = linprog(f,A,b,Aeq,beq,lb,ub) %指定x的范圍，若沒有等式約束 ，則Aeq= ，beq= x,fval = linprog() % 返回目標(biāo)函數(shù)最優(yōu)值，即fval= f ' *x3.4 應(yīng)用實(shí)例例31 用單純形法求解以下線性規(guī)劃問題解： ；基本變量為；非基本變量為； 畫

21、出單純形表，如表3-2表格 3-2 單純形表z0-13-273-1212-24010-438 該問題的一個(gè)明顯的基本可行解是 惟一的一個(gè)值為正的行元素是3，它所在列中有2個(gè)正元素，即4和3由于，應(yīng)該選取為離基變量；入基變量取值為3 解離基變量所相應(yīng)的方程將入基變量用離基變量表示為再將其代入其他基本變量和所在的行中消去,得到代入目標(biāo)函數(shù)得到形成新單純形表如表3-3表格 2 新單純形表3-3z91/2-3/4-2105/21/423-1/21/401-5/2-3/48在上面的單純形表中，惟一的值為正的z行元素是非基本變量相應(yīng)的列，其值因此，選取非基本變量作為入基變量它所在列中有惟一的正元素，即基本

22、變量相應(yīng)行的元素因此，選取為離基變量再經(jīng)步驟3的轉(zhuǎn)軸變換得到新單純形表如表3-4所示表格 3-4 新單純形表2z11-1/5-4/5-12/542/51/104/551/53/102/5111-1/210新單純形表z行的所有非基本變量系數(shù)都變成負(fù)值，求解過程結(jié)束整個(gè)問題的解可以從最后一張單純形表的常數(shù)列中讀出目標(biāo)函數(shù)的最大值為11；最優(yōu)解為:例32 用MATLAB求解下面線性規(guī)劃問題 min subt 解：先根據(jù)MATLAB中解決的線性規(guī)劃問題的標(biāo)準(zhǔn)形式，寫出相應(yīng)的f、x、b、beq、lb、ub等向量以及A、Aeq矩陣，若沒有以 代替，再調(diào)用linprog函數(shù)求解在Matlab命令窗口或者M(jìn)文

23、件中輸入以下程序：>>clc>>clear>>f = -5; -4; -6;>>A = 1 -1 1;3 2 4;3 2 0;>>b = 20; 42; 30;>>lb = zeros(3,1);>>x,fval = linprog(f,A,b,lb)結(jié)果為：x = %最優(yōu)解 00000 150000 30000fval = %最優(yōu)值 -78000035 單純形法的進(jìn)一步討論 351 一般線性規(guī)劃問題的2階段單純形算法引入人工變量后的線性規(guī)劃問題與原問題并不等價(jià)，除非所有都是0 為了解決這個(gè)問題，在求解時(shí)必須分

24、2個(gè)階段進(jìn)行第一階段用一個(gè)輔助目標(biāo)函數(shù)替代原來的目標(biāo)函數(shù)這個(gè)線性規(guī)劃問題稱為原線性規(guī)劃問題所相應(yīng)的輔助線性規(guī)劃問題對(duì)輔助線性規(guī)劃問題用單純形算法求解如果原線性規(guī)劃問題有可行解，則輔助線性規(guī)劃問題就有最優(yōu)解，且其最優(yōu)值為0，即所有都為0在輔助線性規(guī)劃問題最后的單純形表中，所有均為非基本變量劃掉所有相應(yīng)的列，剩下的就是只含和的約束標(biāo)準(zhǔn)型線性規(guī)劃問題了換句話說，單純形算法第一階段的任務(wù)就是構(gòu)造一個(gè)初始基本可行解第二階段的目標(biāo)是求解由第一階段導(dǎo)出的問題此時(shí)要用原來的目標(biāo)函數(shù)進(jìn)行求解如果在輔助線性規(guī)劃問題最后的單純形表中，不全為0，則原線性規(guī)劃問題沒有可行解從而原線性規(guī)劃問題無解352 退化情形的處理用

25、單純形算法解一般的線性規(guī)劃問題時(shí)，可能會(huì)遇到退化的情形，即在迭代計(jì)算的某一步中，常數(shù)列中的某個(gè)元素的值變成0，使得相應(yīng)的基本變量取值為0如果選取退化的基本變量為離基變量，則作轉(zhuǎn)軸變換前后的目標(biāo)函數(shù)值不變?cè)谶@種情況下，算法不能保證目標(biāo)函數(shù)值嚴(yán)格遞增，因此，可能出現(xiàn)無限循環(huán)考察下面的由Beale在1955年提出的退化問題的例子按照2階段單純形算法求解該問題將出現(xiàn)無限循環(huán)Bland提出避免循環(huán)的一個(gè)簡(jiǎn)單易行的方法在單純形算法迭代中，按照下面的2個(gè)簡(jiǎn)單規(guī)則就可以避免循環(huán)規(guī)則1：設(shè)，取為入基變量規(guī)則2：設(shè)取為離基變量算法leave(col)已經(jīng)按照規(guī)則2選取離基變量選取入基變量的算法enter(objr

26、ow) 中只要加一個(gè)break語句即可4 內(nèi)點(diǎn)法 41 內(nèi)點(diǎn)法的基本原理 內(nèi)點(diǎn)法中有一個(gè)懲罰函數(shù)，用于描述凸集與單純形法不同，它通過遍歷內(nèi)部可行區(qū)域來搜索最優(yōu)解 線性規(guī)劃問題描述如下： (4.1)與（4.1）對(duì)應(yīng)的對(duì)數(shù)型懲罰函數(shù)為： (4.2)這里是一個(gè)小的正參數(shù)，常被稱作“懲罰因子”當(dāng)趨近于0時(shí)，將趨近于（41）的解 懲罰函數(shù)的梯度為： (4.3)是原始函數(shù)的梯度，且是的梯度 除了原始變量x，我們還引入了拉格朗日乘子（有時(shí)也稱松弛變量）： (4.4)（4.4）有時(shí)被稱為擾動(dòng)互補(bǔ)條件，類似于KKT條件中的互補(bǔ)松弛我們?cè)噲D找到那些使得懲罰函數(shù)梯度為0的對(duì)比（4.3）與（4.4）我們?nèi)菀椎玫揭粋€(gè)關(guān)

27、于梯度的等式： (4.5)其中，是限制條件的雅克比矩陣 （45）式意味著的梯度應(yīng)該位于限制條件梯度所張成的子空間中對(duì)（44）和（45）應(yīng)用牛頓法我們得到：其中，是的黑塞矩陣，是的的對(duì)角矩陣 因?yàn)椋?.1）和（4.4），所以在每次迭代時(shí)都必須滿足，所以可以通過選擇合適的來計(jì)算：5 原-對(duì)偶內(nèi)點(diǎn)算法51 基本原理 考慮如下線性規(guī)劃問題的標(biāo)準(zhǔn)型（P)及其對(duì)偶（DP）這里A是的矩陣，且總假設(shè)A為行滿秩矩陣，b和c分別是m維和n維向量，z是對(duì)偶問題中加入的n維松弛變量對(duì)原問題和對(duì)偶問題做出下面的假設(shè)：集合S、T都是非空，其定義如下：且定義為了給出算法，先考慮初始點(diǎn)的選取 令和恒滿足下列式子： (5.1)

28、原對(duì)偶內(nèi)點(diǎn)算法要求初始點(diǎn)滿足如下準(zhǔn)則： (5.2)這里，是歐式范數(shù)52 算法的具體步驟步驟1：選取初始點(diǎn)且滿足（5.2）式，其中和同時(shí)滿足（51）；給定終止誤差步驟2：若對(duì)偶間隙，則停，為（P）的近似解；否則轉(zhuǎn)步驟3；步驟3：令，計(jì)算；步驟4：轉(zhuǎn)步驟253 應(yīng)用實(shí)例例51 考慮如下線性規(guī)劃（P）及其對(duì)偶（DP）（DP)中為引入的松弛變量給出一組初始解運(yùn)算結(jié)果見圖1例52 考慮如下線性規(guī)劃（P）及其對(duì)偶（DP）（DP)中為引入的松弛變量給出一組初始解運(yùn)算結(jié)果見圖1用MATLAB編程例51與例52詳細(xì)的計(jì)算結(jié)果見圖1 圖1原對(duì)偶內(nèi)點(diǎn)算法數(shù)值結(jié)果 由運(yùn)算結(jié)果可以看出，例51中x越來越趨于最優(yōu)解，原問題的目標(biāo)值也趨于f=5例52中x越來越趨于最優(yōu)解，原問題的目標(biāo)值也趨于具體程序如下： clear all clc n=3;delt=05316;wucha=0001; A=1 1 2;2 1 3; c=2;1;4; x0=15;05;05; y0=-4;2; z0=2;3;6; k=1;e=1;1;1;x(:,k)=x0; % 將x 賦值給x 的第k 列