工程最佳化設計與MATLAB實現:《工程最佳化設計與MATLAB實現》作 -百科知識中文網

圖書信息1

《工程最佳化設計與MATLAB實現》以簡潔、完整的基本理論為基礎，以實用、多角度的工程實例為對象，以MATLAB語言為工具，介紹了最佳化設計的理論及套用。主要內容包括：最佳化設計基本模型；最佳化設計的數學基礎知識；線性規劃；一維搜尋方法；無約束最佳化問題、有約束最佳化問題的經典算法；啟發式最佳化算法，包括蟻群算法、粒子群最佳化算法、遺傳算法、模擬退火算法和人工神經網路算法；MATLAB最佳化工具箱函式及套用；最佳化算法工程套用實例。

《工程最佳化設計與MATLAB實現》可作為高等工科院校有關專業最佳化設計方面的教材和教學參考書，也可供有關專業師生和工程技術人員參考。

圖書目錄

第1章緒論

1.1 最最佳化問題的提出

1.2 最最佳化問題的分類

1.3 最佳化模型的圖形表示

1.4 有限元法引例

1.5 多學科設計最佳化集成軟體iSIGHT簡介

第2章最佳化設計的數學基礎

2.1 向量與矩陣的範數

2.1.1 向量的範數

2.1.2 矩陣的範數

2.2 方嚮導數與梯度

2.2.1 方嚮導數

2.2.2 梯度

2.3 函式的泰勒級數展開

2.4 無約束最佳化問題的極值條件

2.5 凸集與凸函式

2.5.1 凸集

2.5.2 凸函式

2.6 有約束最佳化問題的極值條件

2.6.1 等式約束最佳化問題的極值條件

2.6.2 不等式約束最佳化問題的極值條件

習題

第3章線性規劃

3.1 線性規劃的標準形式

3.2 單純形法

3.2.1 基本解與基本可行解

3.2.2 基本可行解的轉換

3.2.3 單純形法的計算步驟

3.2.4 單純形法列表計算

3.3 單純形法的MATLAB程式及實例

3.4 改進的單純形法

3.4.1 改進的單純形法的基本思想

3.4.2 改進的單純形法的計算步驟

3.5 改進的單純形法的MATLAB程式及實例

習題

第4章一維搜尋方法

4.1 確定初始單峰區間的方法——進退法

4.1.1 進退法原理

4.1.2 進退法程式框圖及MATLAB程式

4.2 黃金分割法

4.2.1 黃金分割法的基本原理

4.2.2 黃金分割法的計算方法

4.2.3 黃金分割法的計算框圖和MATLAB程式

4.3 拉格朗日插值多項式

4.3.1 線性插值

4.3.2 二次函式插值

4.3.3 n次拉格朗日插值多項式

4.4 插值與擬合的其他方法

4.4.1 差商與牛頓插值

4.4.2列維爾插值法

4.4.3 曲線擬合的最小二乘法

4.4.4 正交多項式及其在曲線擬合中的套用

4.5 一元及多元非線性方程求根

4.5.1 一元非線性方程求根

4.5.2 多元非線性方程組求根

習題

第5章無約束最佳化問題的導數解法

5.1最速下降法

5.1.1 最速下降法的基本原理

5.1.2 最速下降法的MATLAB程式

5.2 牛頓法

5.2.1 牛頓法的基本原理

5.2.2 阻尼牛頓法

5.2.3 阻尼牛頓法的MATLAB程式

5.3 共軛梯度法

5.3.1共軛方向的概念

5.3.2 共軛方向與函式極值的關係

5.3.3 共軛梯度法的幾種形式

5.3.4 共軛梯度法的MATLAB程式

5.4 變尺度法

5.4.1 變數的尺度

5.4.2 變尺度矩陣的建立

5.4.3 變尺度法的MATLAB程式

習題

第6章無約束最佳化問題的直接解法

6.1 坐標輪換法

6.1.1 坐標輪換法的基本原理

6.1.2 搜尋方向與步長的確定

6.1.3 坐標輪換法的MATLAB程式

6.2 單形替換法

6.2.1 單形替換法（一）

6.2.2 單形替換法（二）

6.2.3 單形替換法的MATLAB程式

6.3 鮑威爾法

6.4 鮑威爾法的MATLAB程式及實例

習題

第7章約束最佳化問題的直接解法

7.1 隨機方向法

7.1.1 隨機方向法的基本原理

7.1.2 隨機方向法的步驟

7.1.3 隨機方向法的MATLAB程式

7.2 復合形法

7.2.1複合形法的步驟

7.2.2 複合形法的MATLAB程式

7.3 可行方向法

7.3.1 可行方向法的搜尋策略

7.3.2 Zoutendijk可行方向法

7.3.3 Rosen可行方向法

7.3.4 Rosen可行方向法的MATLAB程式

習題

第8章約束最佳化問題的間接解法

8.1罰函式法

8.1.1 內點罰函式法

8.1.2 外點罰函式法

8.1.3 混合罰函式法

8.2 增廣乘子法

8.2.1拉格朗日乘子法

8.2.2 等式約束的增廣乘子法

8.2.3 不等式約束的增廣乘子法

習題

第9章多目標函式最佳化設計

9.1 多目標最佳化問題

9.1.1 多目標最佳化問題的數學模型

9.1.2 多目標最佳化設計解的類型

9.2 多目標最佳化問題的求解方法

9.2.1 線性組合法

9.2.2 理想點法

9.2.3 乘除法

第10章最最佳化問題的啟發式算法

10.1 蟻群算法

10.2 粒子群最佳化算法

10.2.1 粒子群最佳化算法的基本原理

10.2.2 用粒子群算法求解函式最佳化問題

10.3 遺傳算法

10.3.1 遺傳算法的基本原理

10.3.2混合遺傳算法

10.3.3 十進制編碼遺傳算法

10.3.4 用遺傳算法求解TSP問題

10.4 模擬退火算法

10.5 人工神經網路算法

10.5.1 人工神經網路的特徵及分類

10.5.2 BP網路

10.5.3 Hopfield神經網路模型

第11章 MATLAB最佳化工具箱簡介

11.1 MATLAB常用內部數學函式

11.2 MATLAB最佳化工具箱的主要函式

11.2.1 MATLAB求解最佳化問題的主要函式

11.2.2 最佳化函式控制參數

11.3 線性規劃問題

11.4 一元和多元函式的最佳化問題

11.4.1 一元函式的最佳化問題

11.4.2 多元函式的無約束最佳化問題

11.4.3 多元函式的有約束最佳化問題

11.4.4 二次規劃問題

11.5 半無限約束多元函式最佳化問題

11.6 多目標最佳化問題

11.6.1 理想點法

11.6.2 線性加權和法

11.6.3 最大最小法

11.6.4 目標達到法

11.7 最小二乘法在最佳化及數據擬合中的套用

11.7.1 有約束線性最小二乘

11.7.2 最小二乘法數據（曲線）擬合之一

11.7.3 最小二乘法數據（曲線）擬合之二

11.7.4 最小二乘法數據（曲線）擬合之三

11.8 非線性方程的求解

11.8.1 一元非線性方程的解

11.8.2 非線性方程組的解

第12章工程最佳化設計實例

12.1 平面連桿機構的最佳化設計

12.1.1 曲柄搖桿機構最佳化設計數學模型

12.1.2 曲柄搖桿機構最佳化設計的MATLAB程式及運行結果

12.2 凸輪最佳化設計

12.2.1 凸輪型線最佳化設計目標函式

12.2.2 最佳化函式約束條件

12.2.3 凸輪機構最佳化設計的MATLAB程式及計算實例

12.3 螺栓連線的最佳化設計

12.3.1 螺栓連線受力分析

12.3.2 螺栓連線的設計變數、目標函式及約束條件

12.3.3 螺栓連線的最佳化數學模型

12.3.4 螺栓連線最佳化設計的MATLAB程式及運行結果

12.4 圓柱齒輪傳動的最佳化設計

12.4.1 模糊綜合評判的一般流程

12.4.2 圓柱齒輪傳動最佳化設計的目標函式和設計變數

12.4.3 圓柱齒輪傳動最佳化設計的約束條件

12.4.4 最優截集水平值γ的確定

12.4.5 圓柱齒輪傳動最佳化設計的MATLAB程式及計算結果

12.5 圓柱螺鏇彈簧的最佳化設計

12.5.1 圓柱螺鏇彈簧最佳化設計的數學模型

12.5.2 圓柱螺鏇彈簧最佳化設計實例

12.6 軸的最佳化設計

12.6.1 扭轉軸的最佳化設計

12.6.2 圓形等截面軸的最佳化設計

12.6.3 車床主軸的最佳化設計

12.7 桁架的最佳化設計

12.7.1 靜定桁架的最佳化設計

12.7.2 三桿桁架的最佳化設計

12.8 換熱器的最佳化設計

12.8.1 換熱器最佳化設計（一）

12.8.2 換熱器最佳化設計（二）

12.9 基於最佳化方法的常微分方程邊值問題數值解

12.9.1 基於MATLAB函式的求解方法

12.9.2 求解兩點邊值問題的打靶法

12.9.3 邊界層微分方程組及相似解

12.9.4 流函式方程和溫度方程的求解

12.10 含間隙機械系統的參數最佳化設計

12.10.1 力學模型及運動微分方程

12.10.2 系統的分岔和通向混沌的道路

12.10.3 系統最佳化設計的MATLAB程式

參考文獻

圖書信息2

內容簡介

本書以工程實例為背景，以MATLAB語言為工具，較全面地介紹了最佳化設計的理論及套用。本書主要內容包括：最佳化設計基本模型；最佳化設計數學基礎知識；一維搜尋方法；無約束最佳化問題、有約束最佳化問題的經典算法；啟發式最佳化算法，包括蟻群最佳化、粒子群最佳化算法、遺傳算法、模擬退火算法、禁忌算法和人工神經網路算法；MATLAB最佳化工具箱函式及套用；最佳化算法工程套用實例及MATLAB基礎知識。書中配有完整的MATLAB程式。本書可作為高等工科院校有關專業最佳化設計方面課程的教材和教學參考書，也可供有關專業的師生和工程技術人員參考。

前言

最佳化設計是一門古老而新興的理論，既有著很強的套用背景，又有著堅實的數學基礎。它的數學基礎可以追溯到牛頓（Newton,1642-1727) 、萊布尼茨（W.Leibniz,1646-1716）創立的微積分理論。最佳化設計與運籌學有著密切的聯繫，前者是後者在非線性規劃方向的延伸和發展。最佳化設計主要研究連續函式在有約束和無約束條件下單目標函式或多目標函式的最優值問題，而運籌學主要研究經濟活動和軍事活動中能用數量來表達的有關策劃、管理方面的問題。隨著科學技術和生產的發展，運籌學已滲入到多個領域，其本身也在不斷發展，包含了多個數學分支，如數學規劃（又包含線性規劃、非線性規劃、整數規劃、組合規劃等）、圖論、網路流、決策分析、排隊論、可靠性數學理論、庫存論、對策論、搜尋論、模擬等。在運籌學方面，我國著名科學家錢學森、許國志、數學家華羅庚等作出了重要貢獻。1956年錢學森和許國志共同創建了中國第一個運籌學研究組織。從20世紀60年代開始，華羅庚持續近20年在全國範圍內推廣優選法和統籌法，產生了巨大的經濟效益。其中優選法採用的黃金分割搜尋方法也是最佳化設計中一維搜尋常用的一種方法。各種啟發式（heuristic）算法或智慧型算法，如遺傳算法、蟻群算法、粒子群算法、神經網路算法等不但能解決連續函式的最佳化問題，也能解決離散函式的最佳化問題，它們將最佳化設計與運籌學緊密結合起來。

廣義來說最佳化設計採用的方法是搜尋的方法，傳統的最佳化設計方法主要採用線搜尋方法，而啟發式最佳化方法採用多方位的隨機搜尋方法。對非線性函式來說，在極值點附近可以用二次函式來逼近，若存在極小值，則極值點附近的函式值均大於極值點處的函式值。求連續函式極值的問題，一部分人可能會想到用求導數的方法來解決，另一部分人可能不採用求導數的方法，而直接用比較的方法來確定搜尋區間和極小值。與求導數的方法相比，直接搜尋法是最佳化設計中更基礎的方法。從最佳化設計的數學模型來分，最佳化設計問題可分為有約束的最佳化問題和無約束的最佳化設計問題；而從求解方法來分，最佳化設計方法可分為基於導數的方法和直接搜尋方法。隨機方向法、複合型法、鮑威爾法、可行方向法均屬於直接搜尋法，值得注意的是遺傳算法、蟻群算法、粒子群算法等啟發式算法均含有隨機方向法的基本內涵。

最佳化設計廣泛套用於航空、汽車、化工、電力、建築、機械製造等眾多領域，由於最佳化問題的多樣性，相應出現了多種最佳化設計方法，每一種方法都有其自身的特點和適用範圍，在實際套用中，特別對於大型最佳化設計問題，不應以一次計算結果或一種方法得出的結果作為最終的最優結果。

最佳化設計是以工程設計問題為背景，將最最佳化原理與計算技術相結合的產物。不論是從學習的角度還是從套用的角度，實踐都是非常重要的，實踐既是學習的終點又是學習的起點。本書特彆強調理論與實踐的結合。實踐包括多個方面，最基本的是通過簡單的例子用手工演算來驗證算法，然後是通過編程利用計算機實現和驗證最佳化算法，最後是針對工程設計問題建立最佳化設計模型，選擇合適的最佳化算法解決設計問題。MATLAB不但是實現數值計算的計算機高級語言，同時也是解決多種工程和數學問題的仿真軟體。本書以MATLAB語言作為程式設計語言和實踐環境，針對每一種算法編寫了學習程式，方便讀者學習。這些程式主要為驗證最佳化算法而設計，讀者可以以此為基礎編寫自己的程式。MATLAB本身包含有命令格式和GUI格式的最佳化工具箱，並隨著版本的升級不斷加入新的最佳化算法。本書第11章簡要介紹了MATLAB最佳化工具箱命令格式的各種最佳化函式，最佳化工具箱函式為實現最佳化設計提供了極大的方便，但從學習的角度來說，應儘可能自己編程以便深刻領會和掌握所學的最佳化算法。

本書修訂版保持了原書的內容，對部分內容作了修訂，完善了各章習題。本書配有電子教案，需要者可與清華大學出版社聯繫。

本書由張永恆主編並統稿，蔡慧林、褚衍東審閱，何瑋、馬斌、朱凌雲（蘭州交通大學）、嚴軍（西北師範大學）參加編寫。第1章、第12.1~12.3節由張永恆編寫；第9章和第12.10節由何瑋編寫；第5、6、7章由馬斌編寫；第2、4、8章由朱凌雲編寫；第3、10、11章和第12.4~12.9節由嚴軍編寫；習題由張永恆、馬斌、朱凌雲編寫。在編寫過程中，張鵬、劉金平、程明、周志勇、寧珍、劉軍強、唐強完成了部分程式的調試工作，在此表示感謝。在編寫過程中參考了網路中有關作者的資料在此一併表示感謝。

由於作者水平有限，書中一定有不少錯誤和缺點，敬請廣大讀者提出寶貴意見。

部分章節

第3章線性規劃線性規劃問題是最最佳化理論的重要分支，也是最基本的內容，許多實際問題抽象成數學模型後，都可以歸結為線性規劃問題。自從1947年G.B.Dantzig 提出求解線性規劃的單純形法以來，線性規劃在理論上趨向成熟，在實用中日益廣泛與深入。特別是隨著計算機技術及數值計算方法的發展，線性規劃的套用領域更為廣泛。3.1 線性規劃的標準形式例1-1和例1-2所述問題的數學模型的共同特點是目標函式和約束條件均為線性，設計變數非負。例1-1中的約束條件既含有不等式約束也含有等式約束，而例1-2中的約束條件僅含“≤”的約束。歸納起來，線性規劃問題的一般形式為目標函式：???max? (?min?)f(x)=c?1x?1+c?2x?2+…+c?nx?n?? 約束條件：a?11x?1+a?12x?2+…+a?1nx?n≤(=,≥)b?1a?21x?1+a?22x?2+…+a?2nx?n≤(=,≥)b?2?a?m1x?1+a?m2x?2+…+a?mnx?n≤(=,≥)b?mx?j≥0, j=1,2,…,n, m<n線性規劃問題的常規求解方法是利用矩陣的初等變換，求解時引進非負的鬆弛變數(對“≥”的約束稱為剩餘變數)將不等式約束轉化為等式約束，也就是將線性規劃問題的一般形式變為標準形式。因此，線性規劃問題數學模型的標準形式為線性目標函式加上等式及變數非負的約束條件。用數學表達式表述為???min(max)? c?1x?1+c?2x?2+…+c?nx?n?S.T.? a?11x?1+a?12x?2+…+a?1nx?n=b?1 a?21x?1+a?22x?2+…+a?2nx?n=b?2 ? a?m1x?1+a?m2x?2+…+a?mnx?n=b?m x?j≥0, j=1,2,…,n, m<n??用矩陣表示為???min? (?max?) c??T?x?s.t.? Ax=b x?j≥0, j=1,2,…,n (3-1) ??因此，例1-1的模型化成標準形式為???min? f(x)=x?1+x?2+x?3+x?4+x?5+0x?6+0x?7+0x?8+0x?9 +0x?10+0x?11+0x?12+0x?13+0x?14?s.t. ?x?1+x?2+x?3+x?4+x?5+x?6=18 -3x?1-4x?2+5x?3-4x?4-6x?5+x?7=-80 -3x?1+x?8=-5 -4x?2+x?9=-15 4x?1+x?10=35 4x?2+x?11=40 5x?2+x?12=30 4x?4+x?13=40 6x?5+x?14=35 x?j≥0, j=1,2,…, 14?? 例1-2的模型化成標準形式為???max? f(x)=220x?1+250x?2+0x?3+0x?4+0x?5+0x?6?s.t.? x?1+x?2+x?3=1200 2x?1+x?2+x?4=1800 x?1+x?5=800 x?2+x?6=1000 x?j≥0, j=1,2,…, 6??3.2 單純形法在學習單純形法之前需要了解以下兩個基本概念。極點：若凸集S中的點x，不能成為S中任何線段的內點，則稱x為S的極點。單純形：若一個凸集僅包含有限個極點，則稱此凸集為單純形。單純形法是求解線性規劃問題的有效方法。線性規劃問題的可行域是n維向量空間?R??n 中的多面凸集，如果存在最優解，則最優解必在該凸集的某極點處達到。極點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑑別，看是否為最優解。若不是，則按照一定法則轉換到另一改進的基本可行解,再鑑別。若仍不是，則再轉換,按此重複進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解，也可用此法判別。3.2.1 基本解與基本可行解在緒論中提到過，如果目標函式是一元線性函式f(x),x∈[a,b]，則f(x)的最大值（或最小值）必在x的端點上取得。而對多元線性規劃問題來說，這一結論也是成立的，即f(x)的最大值或最小值在由約束條件構成的求解域的頂點上取得。線性規劃問題屬於有約束最佳化（規劃）問題，約束條件由等式線性約束和變數非負條件構成。基本解是只滿足線性約束條件的解，而基本可行解是既滿足等式線性約束又滿足變數非負要求的解。因此線性規劃問題的解可通過求解線性等式約束方程來獲得。下面先通過一個例子來說明單純形法的基本原理及求解過程。【例3-1】用單純形法求解下面的線性規劃問題：???max? f(x)=2x?1+x?2-2x?3?s.t.? x?1+x?2+2x?3≤5 x?1+3x?2-x?3≤3 x?1,x?2,x?3≥0?? 解： (1) 先用MATLAB線性規劃函式求解，其計算程式如下： %ch31_li1clc;close all;f=-\2\];A=\1\];b=\;xl=\;\=linprog(f,A,b,\,\,xl)計算結果為 x= 3.4696 0.0000 0.4696fval= -6.0000 (2) 手算求解引入鬆弛變數，將所給問題化成線性規劃標準形式:???max? f(x)=2x?1+x?2-2x?3+0x?4+0x?5?s.t.? x?1+x?2+2x?3+x?4+0x?5=5 x?1+3x?2-x?3+0x?4+x?5=3 x?1,x?2,x?3,x?4,x?5≥0??將上式約束方程用矩陣表示：??11 21013-101x?1x?2x?3x?4x?5=53 (3-2) ?? 由於方程個數少於變數個數，因此有無窮多個解。但若取其中3個變數的解為零，則可得到確定的解，並且按這種取法得到的解是有限的，對本問題來說可有10個不同的解。套用MATLAB編程檢索這10個解的部分結果如下： ----------l=1-----j=1, k=2------------ x(1,2)=6.000000,-1.000000A=1 1 1 3y=11----------l=2-----j=1, k=3------------x(1,3)=3.666667,0.666667AA=1 2 1 -1y=6.0000----------l=3-----j=1, k=4------------ x(1,4)=3.000000,2.000000AA=1 1 1 0y=6----------l=4-----j=1, k=5------------ x(1,5)=5.000000,-2.000000AA=1 0 1 1y=10從中可以看出，雖然這些解都是基本解，但並不都是基本可行解。並且?x??1=3.6667,?x??3=0.6667 和?x??1=3.0,?x??4=2.0都是最優基本可行解。挑選基本解的程式如下： %ch1_li1_1clc;clear all;b=\';A1=\1 1 2 1 0 1 3 -1 0 1\];f=\2 0 0\];l=0;for j=1:5 for k=1:5if(j~=k&&j<k)AA=\A1(1,j), A1(1,k) A1(2,j), A1(2,k)\];if det(AA)~=0 l=l+1; x=inv(AA)?b;fprintf('---------l= %d-----j= %d, k= %d-----------\n x(%d,%d)= %f,%f',l,j,k,j,k,x(1),x(2)) AA y=f(j)?x(1)+f(k)?x(2)endendendend下面通過初等變換或消元法求解例3-1。如果約束條件中變數的係數組成的矩陣是滿秩的，則對應的變數為基本變數，其係數矩陣稱為基矩陣。求解時應選擇基本變數和基矩陣進行初等變換。由式（3-2）可知，選擇鬆弛變數x?4,x?5為基本變數，對應的係數組成的矩陣為基矩陣將會帶來很大方便。令非基本變數x?1,x?2,x?3均為零，則得到x?4=5, x?5=3。將該結果代入目標函式中，得??f(x)=2×0+1×0-2×0+0×5+0×3=0??這一結果似乎沒有帶來什麼益處，因為對目標函式沒有絲毫影響。但是通過觀察可以發現，如果將變數x?1由0變成正值，用其替換其中一個基本變數，則目標函式增加最多，因為變數x?1的係數最大。這是將非基本變數選進基本變數的一個原則。接下來的問題是將原來的基本變數x?4,x?5中的哪一個移出，使其成為非基本變數。解決這一問題要藉助約束條件，如果仍舊保持x?2,x?3為零，並去掉方程中非基本變數x?2,x?3及其係數，則約束方程為??110101x?1x?4x?5=53 (3-3) ??分別選x?1, x?4和x?1, x?5為基本變數考察解的情況。以x?1, x?4為基本變數，同時令x?5=0，結果為x?1=3, x?4=2, f=6; 再以x?1, x?5為基本變數，同時令x?4=0，結果為x?1=5, x?5=-2, f=10. 第二種方案是不可取的，因為解x?1=5, x?5=-2不是基本可行解，只是基本解。也就是說應該選擇變數x?5移出基本變數表。為了說明進基變數的係數列向量元素與右端項元素的關係，將x?1分別替換x?4和x?5的情況用下面的模型進行分析。用x?1替換x?4的約束方程為??a?110a?211x?1x?5=b?1b?2??選a?11為消元主元，結果為??1001x?1x?5=b?1/a?11b?2-a?21b?1a?11??從而得??x?1=b?1/a?11, x?5=b?2-a?21b?1a?11 (3-4) ??用x?1替換x?5的約束方程為??1a?110a?21x?4x?1=b?1b?2 (3-5) ??選a?21為消元主元，結果為??1001x?4x?1=b?1-a?11b?2a?21b?2a?21 (3-6) ??從而得??x?4=b?1-a?11b?2a?21, x?1=b?2/a?21 (3-7) ??觀察式（3-4）和式（3-7) ，注意到當??x?1=?min?b?ia?i1=?min?51,31=b?2a?21=31=3 (3-8) ??時，可得到基本可行解，否則x?1的取值不能使所有基本變數的取值成為基本可行解，如式（3-4) . 出基變數與式（3-8）有著必然的聯繫。式（3-8）中最小比值對應的右端項元素或係數行下標對應的基本變數就是出基變數，且比值分母係數下標就是進基變數對應的主消元元素。驗證式（3-3）可知，變數x?5為被替換出的變數，與計算結果一致。由此可見，目標函式與約束條件配合，約束方程求解完成後，將基本變數結果代入目標函式中，通過比較非基本變數係數大小決定進基變數（此時認為非基本變數取值不為零）。對求最大值問題，係數較大的非基本變數為進基變數；對於最小值問題，係數較小的非基本變數為進基變數。確定了進基變數後，則計算右端項與進基變數在約束方程中列係數向量對應元素的比值，比值小者的行下標對應的基本變數為出基變數。下面對單純形法進行更一般的說明。將式(3-1)中的約束矩陣A按列表示:??A=[p?1 p?2 … p?n]??p?i(i=1,2,…,n)是m×1的向量，p?i的分量是各約束方程中與設計變數x?i對應的係數。設矩陣A的秩為m，將設計變數x分解為基本變數和非基本變數，即x=[x?E x?N]??T?,相應地，係數矩陣A也分解為兩部分，一部分為基矩陣，用E表示；另一部分為非基矩陣，用N表示。於是A=[E N],E=[p?1 p?2 … p?m], N=[p?m+1 p?m+2 … p?n]。式(3-1)中的約束條件重新表示為??[E N]x?Ex?N=b(3-9)??即??Ex?E+Nx?N=b??上式兩端左乘E?-1並移項，得??x?E=E?-1b-E?-1Nx?N (3-10) ??x?N的分量為自由變數，它們取不同的值，就會得到方程組的不同解。特別地，如果令x?N=0，則得到??x=x?Ex?N=E?-1b0 (3-11) ??稱解x為方程組Ax=b的一個基本解。如果E?-1b≥0，則稱??x=x?Ex?N=E?-1b0??為滿足約束條件的基本可行解（非負的基本解）. 3.2.2 基本可行解的轉換基本可行解的轉換就是在得到了某組基本可行解後，如何進一步改進獲得更好的解，最終達到最優基本可行解。從3.2.1節的分析可知，獲得改進的解是在滿足約束條件的前提下使目標函式值增加（對於最大值問題）或使目標函式值減小（對於最小值問題）的解。設已經獲得一組基本可行解：??x? (0) =E?-1b0??其對應的目標函式值記為f?0。設x=x?Ex?N是另一組基本可行解，將其代入目標函式中，得??f=c??T?x=c??T??E c??T??Nx?Ex?N=c??T??Ex?E+c??T??Nx?N=c??T??E(E?-1b-E?-1Nx?N)+c??T??Nx?N=c??T??EE?-1b+(c??T??N-c??T??EE?-1N)x?N=f?0+∑nj=m+1(c?j-c??T??EE?-1p?j )x?j=f?0+∑nj=m+1(c?j-z?j)x?j (3-12) ?? 如果每次將一個非基本變數轉換為基本變數，並假定求目標函式的最大值，那么由式（3-12) 可知，選擇求和項中係數c?j-z?j>0最大者對應的非基本變數進入基本變數，當該變數取正值時，可使目標函式增加最多。如果所有非基本變數的係數c?j-z?j不再有正值，則說明非基本變數的進基運算不會再使目標函式值增加，此時就終止計算，輸出最優結果。非基本變數轉換為基本變數後，則要將上一輪疊代中的一個基本變數轉換為非基本變數，判斷出基本變數表的條件由約束方程的消元計算格式給出。設x?k為進基變數，不失一般性，認為x?k替換x?r，在約束方程中相應地用p?k替換p?r, p?k=[a′?1k a′?2k … a′?mk]??T?, p?r=[a′?1r a′?2r … a′?mr]??T?，新的基矩陣為E?(1)。為表示清楚起見，將p?k標記為p?(k)?r，其元素相應地表示為p?(k)?r=[a′?(k)?1r a′?(k)?2r … a′?(k)?mr]??T?。因此基矩陣E?(1)表示為??E?(1)=[p?1 p?2 … p?(k)?r … p?m]=10…a′?(k)?1r…001…a′?(k)?2r…0??????…a′?(k)?rr…0????00…a′?(k)?mr…1?? 變數x?k由零變為正值後，新的方程組的解為??x′?E=E?-1?(1)b′ (3-13) ??其中，基矩陣E?(1)的逆陣為??E?-1?(1)=10…-a′?(k)?1ra′?(k)?rr…001…-a′?(k)?2ra′?(k)?rr…0??????…1a′?(k)?rr…0????00…-a′?(k)?mra′?(k)?rr…1 (3-14) ?? 這裡認為初始基矩陣為單位陣。在基矩陣中用p?k替換p?r，就是將p?k放在第r列的位置上。對於式（3-14）所示的矩陣，其逆矩陣只有第r列的元素髮生變化，對角線上的元素為相應元素的倒數，該列上其他元素等於原來的元素取反再除以對角線上的元素。式（3-13）的解為??x?(k)?r=b′?ra′?(k)?rr (3-15) x?(k)?i=b′?i-a′?(k)?irb′?ra′?(k)?rr=b′?i-a′?(k)?irx?(k)?r, i=1,2,…, m,i≠r (3-16) ?? 由於設計變數非負，並假設設計變數在約束方程中的係數和右端項元素均大於零，因此x? (k)?r≥0自然滿足；而式（3-16）中的變數非負意味著??b′?i-a′?(k)?irb′?ra′?(k)?rr≥0??即??b′?ia′?(k)?ir-b′?ra′?(k)?rr≥0 (3-17) ??當??θ=x?k=b′?ra′?(k)?rr=?min? b′?ia′?(k)?ir,a′?(k)?ir>0 (3-18) ??時，則能保證用x?k替換x?r使所有基本變數非負。線上性規劃中，通常稱??σ?j=c?j-z?j (3-19) ??為判別數或檢驗數。對極小化問題，進基變數x?k的下標與σ?k=c?k-z?k=?min?j(c?j-z?j)項的下標“k”對應，非基本變數x?k的引入使目標函式?f=f?0+∑nj=m+1σ?jx?j?增加最多（最大值問題），或減少最多（最小值問題）。出基變數x?E?r的下標與θ=b′?ra′?rk=?min?b′?ia′?ik,a′?ik>0項的下標“r”對應。式（3-18）和式（3-19）是單純形法求解線性規劃問題的重要判別式和檢驗規則。3.2.3 單純形法的計算步驟套用單純形法求解時，首先要了解怎樣求得初始基本可行解，又怎樣從一個基本可行解轉到鄰近的另一個基本可行解，又怎樣檢驗得到的基本可行解是不是最優解。下面通過例題3-2說明這些問題。【例3-2】用單純形法求下述問題的最優解：???min? z=-6x?1+3x?2-2x?3?s.t.? 2x?1+x?2+x?3≤6 x?1+x?3≤2 x?1,x?2,x?3≥0?? 解：首先引入鬆弛變數x?4,x?5，把數學模型化為標準形式：???min? z=-6x?1+3x?2-2x?3+0x?4+0x?5?s.t.? 2x?1+x?2+x?3+x?4+0x?5=6 x?1+0x?2+x?3+0x?4+x?5=2 x?1,x?2,x?3,x?4,x?5≥0?? 引入鬆弛變數後，變數總數n=5，約束方程數m=2（不含變數大於等於零的約束），因此有n-m=3個非基本變數，並令其為零進行求解。一個簡單的做法就是選鬆弛變數x?4,x?5為基本變數，因為其係數列向量為單位基向量E=p?4 p?5=1001。將基本變數用右端列向量和非基本變數表示，得??x?4=6-2x?1-x?2-x?3x?5=2-x?1-x?3??令非基本變數x?1=x?2=x?3=0，則基本解為??x?4=6, x?5=2??記初始基本解為??x?(0)=\??T??? 此解又滿足式x?j≥0,j=1,2,…,5，因此，x?(0)是基本可行解，它對應著凸可行域的一個頂點。一般來說，對於約束條件全為“≤b?i”形式(i=1,2,…,m)的線性規劃問題，通過引入鬆弛變數，可較容易地找到一個初始基本可行解。下一步，將初始基本可行解x?(0)=\??T?代入目標函式表達式中，得??z=-6×0+3×0-2×0+0×6+0×2=0?? 非基本變數x?1=x?2=x?3=0對應的目標函式值z=0，為找出進基變數，將x?4,x?5代入原式得??z=-6x?1+3x?2-2x?3+c?4(6-2x?1-x?2-x?3)+c?5(2-x?1-x?3)=6c?4+2c?5+(-6-2×c?4-c?5)x?1+(3-c?4)x?2+(-2-c?4-c?5)x?3=\1001]62]+\-\1001]211101]x?1x?2x?3]=c??T?EE?-1b+(c??T??N-c??T??EE?-1N)x?N=-6x?1+3x?2-2x?3?? 由上式看出，x?1增加1個單位，目標函式值z下降6個單位；x?2增加1個單位，z增加3個單位；x?3增加1個單位，z值下降2個單位。如果使x?1和x?3成為正值，都能使目標函式向極小方向改善，那么當前解不是最優解。選擇的進基變數應是使目標函式改善最大的非基本變數進基。由前面的分析看到，在目標函式中，應選擇有負係數，且負係數絕對值最大的非基本變數進基。例3-2中，目標函式中x?1的係數為-6，所以x?1應選為進基變數。這是因為當x?1由當前的零變為正值時，使目標函式下降最大。出基變數的選擇也不是任意的，原則是要保證變數滿足非負條件。為此，要考察約束條件。這兩個方程均有變數x?1要從0上升為正值，要從x?4和x?5這兩個變數中選擇一個出基（即從當前值下降到0) ，而另兩個非基本變數x?2和x?3還要保持為零。由式??x?4=6-2x?1-x?2-x?3x?5=2-x?1-x?3??得??x?4=6-2x?1x?5=2-x?1?? x?1從0變為正值時，x?4和x?5可從當前值下降為0，但不能成為負值（因為變數要滿足非負條件）。由上式可以看出，x?1取x?1=θ??min? =?min? b?ia?i1=21=2時，x?4和x?5均為非負 (x?4=2>0, x?5=0) ，且θ??min? 使x?5=0，因此選x?5為出基變數。已經確定了進基變數x?1和出基變數x?5，就可進行新的消元求解。繼續求解下面的方程：??0x?5+x?2+x?3+x?4+2x?1=6x?5+0x?2+x?3+ 0x?4+x?1=2?? 此時，令非基本變數x?2=x?3=x?5=0，求x?1和x?4的解。為了下面便於說明建立單純形表的過程，用初等變換（消元）求解上面的方程，結果為??-2x?5+x?2-x?3+x?4+0x?1=2x?5+0x?2+x?3+0x?4+x?1=2??解得??x?1=2, x?4=2?? 再將x?1和x?4用約束方程的非基本變數表示，得??x?4=2-x?2+x?3+2x?5x?1=2-x?3-x?5??將其代入目標函式，得??z=-6(2-x?3-x?5)+3x?2-2x?3+c?4(2-x?2+x?3+2x?5)+c?5x?5??整理得??z=-6×2+c?4×2+(3-c?4)x?2+(-2+6+c?4)x?3+(c?5+6+2c?4)x?5??由於所有非基本變數的係數均為非負，沒有進一步可使目標函式減少的非基本變數，因此疊代結束，最優解為x?1=2,x?2=0,x?3=0,f=-12. 根據3.2.2節的介紹及上面的計算，單純形法的一般步驟可歸納如下。 (1) 把線性規劃問題的約束方程組表達成標準形方程組，然後找出一個基本可行解作為初始基本可行解。對等式約束或“≥b?i”形式的約束，如果不易得出初始基本可行解，則需

工程最佳化設計與MATLAB實現

基本信息

圖書信息1

內容簡介

圖書目錄

圖書信息2

內容簡介

前言

目錄

部分章節

相關詞條

MATLAB

車輛工程仿真與分析：基於MATLAB的實現

MATLAB基礎及套用

MATLAB 6.5輔助最佳化計算與設計

MATLAB控制系統仿真與設計

MATLAB神經網路套用設計

詳解MATLAB在統計與工程數據分析中的套用

線性代數實踐及MATLAB入門

相關搜尋

熱門詞條