第1章優(yōu)化設計優(yōu)化是運用專門的方法來確定最優(yōu)的本錢，并對某一問題或某一過程的設計進展有效求解的方法。在進展工業(yè)決策時，這一技術是主要的定量分析工具之一。在紡織廠以及許多其它工業(yè)工程的設計、建立、操作和分析中所涉及的大部分問題均可運用優(yōu)化方法進展求解。§1.1引言1.1.1概述在人類活動中，要辦好一件事〔指規(guī)劃、設計等〕，都期望得到最稱心、最好的結果或效果。為了實現(xiàn)這種期望，必需有好的預測和決策方法。方法對頭，事半功倍，反之那么事倍功半。優(yōu)化方法就是各類決策方法中普遍采用的一種方法。優(yōu)化設計運用的開展歷史，閱歷了由疑心、提高認識到實際收效，從而引起寬廣工程界日益注重的過程。從國際范圍看，早期設計師習慣于傳統(tǒng)設計方法和閱歷設計。傳統(tǒng)設計由于專業(yè)實際和計算工具的限制，設計者只能根據閱歷和判別先制定設計方案，隨后再對給定的方案進展系統(tǒng)分析和校核，往往要經幾代人的不斷研制、實際和改良，才干使某類產品到達較稱心的程度。由于產品設計質量要求日益提高和設計周期要求日益縮短，傳統(tǒng)設計已越來越顯得不能順應工業(yè)開展的需求。設計師為了掌握優(yōu)化設計方法，需求在優(yōu)化實際、建模和計算機運用等方面進展知識更新。70年代到80年代，計算機價錢大幅度下降，年輕一代設計師茁壯生長，優(yōu)化設計運用的誘人威力，市場競爭日益激化，作為產品開發(fā)和更新的第一關如何極大地縮短設計周期、提高設計質量和降低設計本錢已成為企業(yè)生存的生命線，從從而引起寬廣企業(yè)和設計師的高度注重。特別是CAD/CAM以及CIMS〔計算機集成制造系統(tǒng)〕的開展，使優(yōu)化設計成為當代不可短少的技術和環(huán)節(jié)。用優(yōu)化設計方法來改造傳統(tǒng)設計方法已成為競相研討和推行并可帶來艱苦變革的開展戰(zhàn)略，優(yōu)化設計在設計領域中開辟了新的途徑。在紡織工藝過程設計和工廠操作中的典型問題有很多〔也許是無限多〕求解方法。優(yōu)化是在各種高效定量分析方法中找到一個最優(yōu)的方法。計算機及其相關軟件的開展使計算變得可行而且更加有效。近年來，為了普及和推行運用優(yōu)化技術，曾經將各種優(yōu)化計算程序組成運用非常方便的程序包，并已開展到建立最優(yōu)化技術的專家系統(tǒng)，這種系統(tǒng)能協(xié)助運用者自動選擇算法，自動運算以及評價計算結果，用戶只需很少的優(yōu)化數(shù)學實際和程序知識，就可有效地處理實踐優(yōu)化問題。雖然如此，但最優(yōu)化的實際和計算方法至今還未非常完善，有許多問題仍有待進一步研討探求?？梢灶A測，隨著現(xiàn)代技術的迅速開展，最優(yōu)化技術必將獲得更廣泛、更有效的運用，它也必將到達更完善、更深化的進展。1.1.2優(yōu)化的作用為什么工程師對優(yōu)化感興趣呢？用優(yōu)化的方法做出的決策比直接決策可以多得到多少效益呢？工程師們的任務是改良設備的初始設計，并且對曾經安裝運用的設備盡能夠地強化其操作性能，以到達產量最大、本錢最小、能耗最小等目的。在工廠操作中，一部分效益來自于工廠操作性能的提高，例如添加高價值產品的產量〔或減少污染物的產量〕、降低能耗、提高過程的效率、延伸開工時間。優(yōu)化還能降低維護費用，減少設備損耗，并提高人員的利用率。此外，還有無形的效益來自于工廠操作者、工程師和管理人員之間的相互配合。系統(tǒng)地識別一個過程或消費線的目的、約束和自在度是非常有益的，它可以產生如下效益，如改良設計的質量、更快更確切地發(fā)現(xiàn)并處理問題以及更快地做出決議。由于在過程模型中所用的數(shù)據和數(shù)學表達式存在一些不確定性，因此對于優(yōu)化的運用能否有風險，仍存在著爭論。當然，這樣的爭論是有益的。工程師們在把優(yōu)化技術用于一些問題時必需做出某種判別，這些問題中含有與其相關的、不確定的、但是值得思索的問題。即必需從準確和適用兩個觀念來思索問題，這是由于工廠的操作參數(shù)和周圍的環(huán)境并非一成不變。在某些情況下會在確定優(yōu)化的同時參與某些統(tǒng)計的特征去分析產量預測的不確定程度，這能夠是一種可行的分析方法。當過程模型是理想的，且對輸入和運用的參數(shù)僅僅知道一個大約時，必需慎重對待優(yōu)化的結果，它可以提供優(yōu)化的上限。另一種對優(yōu)化設計中不確定性參數(shù)影響的評價方法是敏感性分析。通常，過程變量的優(yōu)化值是不隨給定的參數(shù)而變化的〔敏感性較差〕。因此，具有確切值的參數(shù)并不是尋覓優(yōu)化條件的關鍵。1.1.3優(yōu)化的范圍和層次優(yōu)化可以運用在一個公司的恣意層次上，其運用范圍包括復雜的組合車間、某個車間內分布的設備、單個安裝及某個安裝中的子系統(tǒng)、甚至更小的個體。優(yōu)化問題存在于任何層次上，因此，優(yōu)化問題可以包括整個公司、某一個車間、一個過程、單個的單元操作、單元操作中的某個安裝或者其中的某個中間系統(tǒng)。而其分析的復雜性那么包括只能了解大致的特征或者只能檢查到瞬間的概略，這依賴于所設定的結果、可供利用的準確數(shù)據和進展優(yōu)化所需的時間。在一個典型的工廠中，優(yōu)化可用于管理、過程設計和安裝規(guī)范、車間操作等。由于輕紡工廠的復雜性，要對一個指定的工廠進展徹底的優(yōu)化，任務量是很大的。不能進展徹底優(yōu)化時，經常會依賴于“不完全優(yōu)化〞，這是一種特殊的“子優(yōu)化〞變形。子優(yōu)化是一種操作或一個問題的某一方面進展的優(yōu)化，在優(yōu)化中忽略了一些要素，這些要素對工廠的系統(tǒng)或過程有著直接或間接的影響。由于以下緣由，子優(yōu)化通常是很必要的，這些緣由有的是思索了經濟性和適用性，有的那么是由于時間或人員的限制，以及急于得到答案的難度等。當建立問題存在難度，或者沒有現(xiàn)成的技術可以得到全部問題的合了解時，子優(yōu)化通常是很有用的。在大多數(shù)實踐情況下，子優(yōu)化至少提供了一個合理的技術以到達最優(yōu)。不過，各個子優(yōu)化的元素沒有必要保證使整個系統(tǒng)到達全局最優(yōu)。子系統(tǒng)目的能夠與全局目的并不一致或不吻合。§1.2紡織最優(yōu)化設計概念紡織的最優(yōu)化設計，就是在一定的加工條件下，在對加工工藝、加工設備以及產品的性態(tài)或其它要素的限制〔約束〕范圍內，選取某些設計變量，設計實驗方案，建立目的函數(shù)并使其獲得最優(yōu)值的一種新的設計方法。設計變量、目的函數(shù)和約束條件這三者在設計空間〔以設計變量為坐標軸組成的實空間〕的幾何表示中構成設計問題。優(yōu)化設計的普經過程可以用圖1-1來表示。相對于常規(guī)設計來說，最優(yōu)化設計是一次革新。圖1-1優(yōu)化設計的普經過程1.2.1設計變量和目的函數(shù)1設計變量在設計過程中進展選擇并最終必需確定的各項獨立參數(shù)，稱為設計變量。在選擇過程中它們是變量，但這些變量一旦確定以后，設計對象也就完全確定。最優(yōu)化設計是研討怎樣合理地優(yōu)選這些設計變量值的一種現(xiàn)代設計方法。在紡織加工中，常用的獨立參數(shù)有工藝參數(shù)、設備與零部件的規(guī)格、原資料的力學和物理特性、產品的規(guī)格性能等等。在這些參數(shù)中，凡是可以根據設計要求事先給定的，那么不是設計變量，而稱為設計常量。只需那些需求在設計過程中優(yōu)選的參數(shù)，才可看成是最優(yōu)化設計中的設計變量。設計變量的數(shù)目稱為最優(yōu)化設計的維數(shù)，如有n個設計變量，那么稱為n維設計問題，只需兩個設計變量的二維設計問題可用圖1-2所示的平面直角坐標表示；有三個設計變量的三維設計問題可用圖1-3所表示的空間直角坐標表示。在圖1-2中，當設計變量，分別取不同值時，那么可得到在坐標平面上不同的相應點，每一個點表示一種設計方案。假設用向量表示這個點，即為二維向量〔1-1〕同樣，在圖1-3中，每一個設計方案表示為三維空間的一個點，并可用三維向量來表示該點〔1-2〕圖1-2二維設計問題圖1-3三維設計問題在普通情況下，假設有個設計變量，把第個變量記為，那么其全部設計變量可用維向量的方式表示成〔1-3〕這種以個獨立變量為坐標軸組成的維向量空間是一個維實空間，用表示，假設其中恣意兩向量又有內積運算，那么稱維歐式空間，用表示。當向量中的各分量都是實變量那么稱決議了維歐氏空間中的一個點，并用符號表示。在最優(yōu)化設計中由各設計變量的坐標軸所描畫的這種空間就是所謂的“設計空間〞，它是一個重要概念。圖1-3給出了一個具有三個設計變量的設計空間。決議這個空間的三個坐標軸分別描畫三個設計變量。通常，設計變量的個數(shù)要比3多得多，并且很難用圖象表示，這時的維空間又稱為超越空間。設計空間中的一個點就是一種設計方案，如圖1-4所示。圖1-4在三變量〔三維〕設計空間中設計方案的探求設計空間中的某點是由各設計變量所組成的向量決議的，點決議了一種設計方案，另一種設計方案點(+1)那么由另一種設計變量所組成的向量確定。最優(yōu)化設計中常采用的直接探求法〔或稱直接搜索法〕，就是在相鄰的設計點間做一系列定向的設計改動〔挪動〕。由點到點〔+1〕間的典型挪動情況可由下式給出〔1-4〕向量決議挪動的方向，標量決議挪動的步長。設計空間的維數(shù)表征了設計的自在度，設計變量愈多，那么設計的自在度愈大、可供選擇的方案愈多、設計愈靈敏，但難度愈大、求解亦愈復雜。普通，含有2～10個設計變量的為小型設計問題；10～50個為中大型設計問題；50個以上的為大型設計問題。目前曾經處理200個設計變量的大型最優(yōu)化設計問題。在紡織中的工藝優(yōu)化問題，根本上都是小型設計問題。2目的函數(shù)在最優(yōu)化設計中，可將所追求的設計目的〔最優(yōu)目的〕用設計變量的函數(shù)方式表達出來，這一過程稱為建立目的函數(shù)。目的函數(shù)是設計中預期要到達的目的，它表達為各設計變量的函數(shù)表達式〔1-5〕它代表設計的某項最重要的特征，例如上面所提到的加工工藝、設備規(guī)格、原料和產品的性能以及本錢等。目的函數(shù)是設計變量的標量函數(shù)。最優(yōu)化設計的過程就是優(yōu)化設計變量使目的函數(shù)到達最優(yōu)值，或找到目的函數(shù)的最小值〔或最大值〕的過程。在最優(yōu)化設計問題中，可以只需一個目的函數(shù)，稱為單目的函數(shù)，如式〔1-5〕所示。當在同一設計中要提出多個目的函數(shù)時，這種問題稱為多目的函數(shù)的最優(yōu)化問題。在普通的紡織最優(yōu)化設計中，多目的函數(shù)的情況較多，設計的綜合效果愈好，但問題的求解亦愈復雜。對于多目的函數(shù)，可以將它們分別獨立地列出來〔1-6〕也可以把幾個設計目的綜合到一同，建立一個綜合的目的函數(shù)表達式，即〔1-7〕實驗中，目的函數(shù)中的某些單目的函數(shù)之間能夠存在著矛盾，這時用一個目的函數(shù)表示多目的函數(shù)，表示所要求特性的加權和。把多目的函數(shù)轉化成單目的函數(shù)求解，目的函數(shù)為〔1-8〕—表示j項目的的加權因子。加權因子是個非負系數(shù)，由設計者根據該項目的在最優(yōu)化設計中所占的重要程度等情況選定。所選擇的各項目的的加權因子，應能客觀的反映該項最優(yōu)化設計所追求的總目的，使總目的的綜合效果到達最優(yōu)。1.2.2約束條件和可行域如前所述，目的函數(shù)取決于設計變量，而在很多實踐問題中設計變量的取值范圍是有限制的或必需滿足一些條件。在最優(yōu)化設計中，這種對設計變量的取值時的限制條件，稱為約束條件或設計約束。約束條件可以用數(shù)學等式或不等式來表示。不等式約束的方式為或，其中，式中為不等式約束的數(shù)目。等式約束表示等式約束數(shù)應少于設計變量數(shù)，等式約束對設計變量的約束很嚴，起著降低設計自在度的作用。在優(yōu)化設計中，由于引入了約束條件，因此只需滿足約束條件的設計方案，才是可行的設計方案。從幾何概念看一個不等式約束條件，把設計空間劃分為兩部分：一部分滿足約束條件即；另一部分不滿足約束條件即；兩部分的分界限〔或面〕即稱為約束線〔或面〕。如圖1-5所示的二維設計平面中可以直觀了解這個概念，在約束線不滿足約束條件的一側畫陰影線表示這部分不符合約束要求。圖1-5約束線在設計空間中，滿足設計要求的一切約束所構成的空間，稱為可行域。在可行域中，任一點都是可行點。當設計變量均為延續(xù)變量時，可行點有無窮多個。優(yōu)化設計過程就是在可行域中沿著目的函數(shù)值不斷改善的方向去搜索出最好的解。優(yōu)化方法的巧妙和威力就是用有限次搜索找出最好點，這種點稱最優(yōu)點或最優(yōu)解，用表示,如圖1-6所示。(a)(b)(c)(d)圖1-6可行域的幾種情況1.2.4最優(yōu)化設計的數(shù)學模型選取設計變量，列出目的函數(shù)、給定約束條件后構造最優(yōu)化設計的數(shù)學模型。如前所述，任何一個最優(yōu)化問題均可歸結為如下的描畫，即在滿足給定的約束條件〔決議維空間中的可行域〕下，選取適當?shù)脑O計變量，使其目的函數(shù)到達最優(yōu)值。其數(shù)學表達式〔數(shù)學模型〕為：求設計變量在滿足約束條件的條件下，使目的函數(shù)到達最優(yōu)值。目的函數(shù)的最優(yōu)值普通可用最小值〔或最大值〕的方式來表示，因此，最優(yōu)化設計的數(shù)學模型可簡化表示為〔1-9〕數(shù)學模型的建立，既可以用實際推導的方法，也可以用實驗的方法，現(xiàn)舉例闡明建立數(shù)學模型的過程。例1-1要用薄木板制造一體積為5的存放廢品的貨箱，由于存放的貨物要求其長度不小于2。為了使耗費的木板最少并減少質量，問應如何選取貨箱的長、寬和高？解顯然，木板的耗費量與貨箱的外表積成正比，假設貨箱不帶上蓋，那么目的函數(shù)為約束條件為所以其數(shù)學模型為如有一個等式約束，那么原那么上可以消去一個設計變量。當然，這時被消去的那個設計變量必需以顯示的方式表達出來。在上述問題中，由等式約束條件得，代入目的函數(shù)后原問題的數(shù)學方式可簡化為即設計變量由三個減為兩個，現(xiàn)實上，當和確定后，根據等式條件，即可確定。建立最優(yōu)化設計的數(shù)學模型以后，即可選擇適宜的最優(yōu)化方法解題，求目的函數(shù)的最優(yōu)解?！?.3優(yōu)化方法的數(shù)學根底1.3.1方導游數(shù)和梯度1方導游數(shù)偏導數(shù)是沿平行于坐標軸的多個特殊方向的變化率。對于函數(shù)沿恣意給定方向的變化率，那么需采用方導游數(shù)的概念。

該二元函數(shù)，由點沿著與軸正向夾角的方向S變到點，如圖1-7所示。于是函數(shù)的增量為點到的間隔那么在點沿S方向的方導游數(shù)為〔1-10〕可見，方導游數(shù)是函數(shù)在某點沿給定方向的變化率，可看成偏導數(shù)的推行。即：〔1-11〕得〔1-12〕式中——S的方向余弦三元函數(shù)的函數(shù)情況：假設S方向與各坐標軸方向間夾角分別為，那么函數(shù)在點沿S方向的方導游數(shù)為〔1-13〕多元函數(shù)的方導游數(shù)可寫為〔1-14〕式中，——某方向S的n個方向角例1-2設目的函數(shù)求在點沿S方向的方導游數(shù)，向量S的方向為解由于故可見，假設取不同的值而點不變，那么方導游數(shù)的值不同。2梯度方導游數(shù)描畫函數(shù)在某點給定方向的變化率。普通在同點的不同方向函數(shù)的變化率不同。尋優(yōu)要使路程最短。那么，哪個方向上的變化率最大？如何找到？下面引入梯度的概念。梯度是函數(shù)對各個設計變量的偏導數(shù)所組成的列向量，并以符號或表示，即〔1-15〕梯度方向是指函數(shù)值增長最快的方向。梯度的模為即函數(shù)的最大變化率。沿方向函數(shù)值的變化率最大，即可最速上升；沿方向函數(shù)值的變化率最小，即可最速下降；目的函數(shù)等值線上某點的法線方向即為函數(shù)某點的梯度方向。例1-3求函數(shù)在點和點的梯度。解由定義知：點的梯度為：如圖1-8所示，同心圓方案是函數(shù)的等值線，圖1-8梯度的求法在點作與軸夾角成的向量就是該點的梯度。梯度方向是等值線上該點切線的法線方向。點的梯度為闡明在的梯度為0，即為函數(shù)的極值點。假設函數(shù)在某點有極值，那么該點的梯度為0。1.3.2多元函數(shù)的泰勒公式及Hessian矩陣目的函數(shù)為一元函數(shù)時，在點附近假設存在1到n+1階導數(shù)，那么可展開成如下泰勒公式〔1-16〕用簡單函數(shù)在對原函數(shù)作部分逼近。假設取前二項〔展開式〕即用不斷線逼近，假設取展開式的前三項那么表示用曲線逼近。對二元函數(shù)同樣可以展開成泰勒公式。設目的函數(shù)在點附近的泰勒公式，假設只取到二次項時為0〔1-17〕寫成向量矩陣方式〔1-18〕可簡寫為〔1-19〕式中，——函數(shù)在點的梯度列向量這是函數(shù)在點的二階偏導數(shù)矩陣，稱Hessian為矩陣，用表示。〔為對稱矩陣〕即2×2陣。n元函數(shù)的Hessian矩陣可寫為〔1-20〕n元函數(shù)有n個變量，所以它的Hessian矩陣是n×n對稱矩陣。n元函數(shù)的泰勒展開式為〔1-21〕泰勒展開式對討論多元函數(shù)的極值問題很方便。假設已找到，使〔1-22〕只能說是多元函數(shù)的駐點，不知道能否是極值點，更不知道是極大點還是極小點。但由于，故有，表達式的右半部為二次型函數(shù)，此式闡明要判別一個函數(shù)的駐點是極大點還是極小點，可以經過判別一個特定二次型是正定還是負定來決議。多元函數(shù)用泰勒公式展開式作部分逼近，取到二次項時，函數(shù)為二次型。多元函數(shù)用泰勒展開式作部分逼近，當取到二次項時，函數(shù)為二次型。因此在求目的函數(shù)的最優(yōu)解時，常把某一給定點函數(shù)近似地用二次函數(shù)替代，使分析問題簡化。1.3.3二次型函數(shù)及正定矩陣判別二次型是指含有n個變量的二次齊次多項式寫成矩陣方式令那么上式記為假設式中為常系數(shù)，那么稱為二次型函數(shù)或實二次型。A稱為二次型矩陣。由于，所以，那么A稱為對稱矩陣，因此二次型矩陣都是對稱矩陣。正定判別：假設A陣左上角的主子行列式全大于零，那么A正定；反之，假設A正定，A陣左上角的主子行列式全大于零。二次型函數(shù)的一些性質：〔1〕非零向量X，假設，是正定的?！?〕非零向量X，假設，是負定的。1.3.4多元函數(shù)的極值對于多元函數(shù)，有極值的必要條件是梯度，根據的條件可求點的詳細值。但是還無法確定是極值還是駐點，即使是極值還不能斷定是極大值還是極小值，這時用泰勒展開二次型。多元目的函數(shù)在駐點附近，用泰勒公式的二次項近似表示，那么有在點的領域內，假設對一切有：或，那么點為極小點。當，那么點為極大點。當當，那么點為鞍點。也可以由Hessian矩陣〔由二次型系數(shù)構成〕斷定：當正定，為極小；當負定，為極大；當不定，為鞍點。正定的充要條件為矩陣A的順序主子式取全大于零。例1-4如有函數(shù)試求極值點，并判別性質。解1〕先求解駐點。得到即駐點〔1，1〕2〕再利用Hessian矩陣判別駐點能否為極值點。二階偏導于是Hessian矩陣為多階主子式為即Hessian矩陣為正定。故駐點〔1，1〕是極小值點，故函數(shù)的極小值。1.3.5函數(shù)的凸性以及凸函數(shù)的判別條件函數(shù)有單峰函數(shù)和多峰函數(shù)，因此求得極值點無法斷定是全域還是部分最優(yōu)解，需經過研討凸性來處理。凸性這個概念在優(yōu)化實際和運用中非常有用。1一元函數(shù)凸性設一元函數(shù)，假設函數(shù)曲線上恣意兩點的連線，永遠不在曲線的下面，如圖1-9〔a〕所示，那么函數(shù)稱為凹函數(shù)，相反那么稱為凸函數(shù)，如圖1-9〔b〕所示。(a)(b)圖1-9函數(shù)的凸性概念上面的曲線均有：〔1-23〕或這是線段的表達式。當時，；當時，，所以在0～1范圍。凸函數(shù)的表達式為〔1-24〕2多元函數(shù)的凸性設為n維歐氏空間中的一個集合，假設其中恣意兩點，之間連線上一切的點都在這個集合中，那么稱這種集合為n維歐氏空間的一個凸集。圖1-10(a)是二維空間的一個凸集，而(b)不是凸集。(a)凸集(b)非凸集圖1-10二維空間的凸集與非凸集設是上的函數(shù)，假設對任何實數(shù)對上的恣意兩點恒有(1-25)那么函數(shù)就是定義在凸集上的一個凸函數(shù)。上式假設不帶“＝〞為“<〞，那么為嚴厲凸函數(shù)。？3凸函數(shù)的判別條件〔1〕假設函數(shù)在上具有延續(xù)一階導數(shù)，而又是內部的一個凸集，那么為上凸函數(shù)的充要條件是不等式恒成立。〔2〕假設函數(shù)在上具有延續(xù)二階導數(shù)，而又是內部的一個凸集，那么為上的凸函數(shù)的充要條件是：的Hessian矩陣〔二階導矩陣〕為半正定。用Telan二次項展開式近似表達，對恣意Telan展開式為即由判別條件可知上式左邊應大于或等于零，必需使即此二次型應為半正定，即Hessian矩陣為半正定。假設Hessian矩陣為正定，既上式換為，那么為嚴厲的凸函數(shù)。例1-5某紡織廠的技術經濟分析簡化而得的目的函數(shù)為判別此函數(shù)能否為凸函數(shù)。解利用Hessian矩陣判別，只需證明其Hessian矩陣是非負定即可。將代入Hessian矩陣，得該Hessian矩陣的各階主子式的值為故Hessian矩陣為正定，所以為嚴厲的凸函數(shù)。留意：對于高階多元目的函數(shù)，很難判別能否為凸函數(shù)。另外，目的函數(shù)也經常是多極值函數(shù)，所以求得的極值點不一定是全局點?！?.4一維優(yōu)化方法1.4.1概述對一維〔也稱一元或單變量〕函數(shù)尋求其極值點就是一維優(yōu)化方法中限制最優(yōu)解問題，稱一維搜索方法。搜索方法是數(shù)學迭代解法，它把搜索范圍不斷減少向最優(yōu)點逼近，當滿足收斂準那么后，即可求得最優(yōu)解。在設計空間中選定一個初始設計點，然后從這一點出發(fā)，按照某一優(yōu)化方法所規(guī)定的原那么，確定初始搜索方向，沿這個方向尋求最優(yōu)步長，得一個目的函數(shù)值有所改良的設計點。然后以點作為新的始點，再構造此點的新的搜索方向，求新的最優(yōu)步長，求得改良的設計點。反復這種過程，得到目的函數(shù)值不斷改良的點列：等點，最后可以到達滿足所規(guī)定的收斂準那么或終止準那么要求的實際最優(yōu)點的近似最優(yōu)點。這種尋覓最優(yōu)點的反復過程稱為數(shù)值迭代方法。迭代過程的每一步格式，普通可以寫成如下方式：，式中——第k步迭代點，即優(yōu)化過程中所到達的第k次設計點。——從第k次設計點出發(fā)的搜索方向。——從第k次設計點出發(fā)，沿方向進展搜索的最優(yōu)步長?！獜牡趉次設計點出發(fā)，以為步長沿方向進展搜索所得到的新點。一維搜索方法包括分析方法〔微分法〕和數(shù)值迭代法，數(shù)值迭代法又分為直接法(黃金分割法和對分法)和間接法〔不需求求導數(shù)的二次插值法和需求求導數(shù)的三次插值法〕。1.4.2單峰函數(shù)在給定區(qū)間內僅有一個極小點的函數(shù)稱單峰函數(shù)，圖1-11為單峰函數(shù)的幾種情況。圖1-11三種單峰函數(shù)〔1〕必位于內，放棄段，將搜索區(qū)間縮為?！?〕必位于內，放棄段，將搜索區(qū)間縮為?！?〕當在內，將搜索區(qū)間縮為。下面引見初始單峰區(qū)間確實定及算法。在這里我們只引見一種方法——進退法，也稱外推法，是一種經過比較函數(shù)值大小來確定單峰區(qū)間的方法。恣意給定初始點和步長h，算出和點的函數(shù)值。

假設，闡明，將步長添加一倍，取，見圖1-12(a)。假設，闡明，需改動尋查方向，即將步長符號改為負，得點，見圖1-12(b)，以此類推，直至函數(shù)值添加為止。圖1-12進退法確定單峰區(qū)間假設，那么將步長再加大一倍，有〔圖1-12(a)〕或〔圖1-12(b)〕即每跨一步的步長為前一次步長的2倍，直至函數(shù)值添加為止。如圖1-12(a)中有那么單峰區(qū)間為。對于圖1-12(b)，有那么單峰區(qū)間為。利用進退法，普通總可找到單峰區(qū)間中的3個點，即2個端點和中間某一個點。對于后面要引見的二次插值法中要利用3個點的信息，其他方法只需利用2個端點信息。1.4.3黃金分割法黃金分割法也稱0.618法，是經過對黃金分割點函數(shù)值的計算和比較，將初始區(qū)間逐次進展減少，直到滿足給定的精度要求，即求得一維極小點的近似解。知的單峰區(qū)間為。為了減少區(qū)間，在內按一定規(guī)那么對稱地取2個內部點和，并計算和。能夠有三種情況，如圖1-13所示。圖1-13黃金分割法圖1-13(a)經過一次函數(shù)比較，區(qū)間減少一次為[a，x2]。在新的區(qū)間內，保管一個好點和，下一次只需再按一定規(guī)那么，在新區(qū)間內找另一個與對稱的點，計算，與比較，如此反復。圖1-13(b)淘汰，產生新的單峰區(qū)間[x，b]。圖1-13(c)可歸納入上面任一種情況處置。黃金分割法的關鍵是如何不斷找出區(qū)間內的2個對稱點，保證極小點不會丟掉，且收斂快。設初始區(qū)間長度為l，第一次區(qū)間縮短率為，那么縮短后的區(qū)間長度為。第二次區(qū)間縮短時，在區(qū)間中取點，經比較后又得新區(qū)間。由對稱性可知，區(qū)間的長度為，那么本次區(qū)間縮短率為令這兩次縮短率相等，即，使方程〔1-26〕解方程，得合理的根為由此可知，黃金分割法的均勻縮短率為0.618，即每經過一次函數(shù)值比較，都是淘汰本次區(qū)間的0.382倍。根據上式，黃金分割法的取點規(guī)那么是〔1-27〕〔1-28〕為了使最終區(qū)間收斂到給定收斂精度內，區(qū)間的縮短次數(shù)N必需滿足〔1-29〕即〔1-30〕由于實踐問題的需求和函數(shù)形狀的不同，經常需求不同的收斂準那么確定最優(yōu)點。對于直接法，有以下幾種收斂準那么：〔1〕區(qū)間絕對精度；〔2〕區(qū)間相對精度；〔3〕函數(shù)值絕對精度；〔4〕函數(shù)值相對精度。黃金分割法特點：〔1〕不用要求可微，只需利用函數(shù)值大小的比較，即可很快地找到；〔2〕除了第一次減少區(qū)間要計算兩個點及其函數(shù)值以外，其他每次只需計算一個點及其函數(shù)值；〔3〕可靠性好。黃金分割法可運用到染色等眾多過程中，例如在其它條件不變的情況下，優(yōu)選乳化劑的參與量或水的適宜參與量等。例1-6假設某廠為消費一種含有特殊香味得毛織物，現(xiàn)決議在原毛染色中參與某種香型資料，假設其參考添加量為0.1％～0.15％，現(xiàn)經過實驗確定其最正確添加量。解按黃金分割法安排實驗，先在含優(yōu)區(qū)間[0.1%,1.5%]的0.618處取值做第一實驗點，那么該實驗得第一次實驗點為第二實驗點為比較兩次實驗效果，假設好于，那么舍去不包括點的以外部分，在留下部分再找出點的對稱點，，上述實驗點的過程如圖1-14所示。圖1-14第一、第二、第三實驗點確定的表示圖比較第二次和第一次實驗的結果，假設仍是第一次的實驗效果好，那么去掉以外的部分。在留下的至區(qū)間內繼續(xù)找出的對稱點作為第四實驗點。假設點比點的實驗效果好，那么舍去到這一段，在留下的部分內繼續(xù)找出的對稱點,為第五實驗點，見圖1-15。圖1-15第四、第五實驗點確定的表示圖按同樣的方法繼續(xù)下去，直到獲得稱心的實驗效果為止。假設在上述實驗中的效果比還好，并且比較稱心，那么可確定香料的添加量為0.76％是最優(yōu)添加量。1.4.4對分法1中心對分法中心對分法是利用目的函數(shù)的一階導數(shù)來判別最優(yōu)點的存在區(qū)間，利用目的函數(shù)的一階導數(shù)，取中心對分點，由目的函數(shù)的正負，淘汰區(qū)間的一半，如圖1-16所示。知，而故淘汰區(qū)間[a，x1]，留下區(qū)間[x1，b]，令趨于。再取，求，直至，那么有。圖1-16中心對分法求解圖對分法特點：一階可微，且每計算一次，可淘汰區(qū)間的一半，收斂很快；當用于無目的函數(shù)式的優(yōu)化實驗時，每實驗一次要判別下一次實驗應淘汰的區(qū)間。2兩點對分法知極小點區(qū)間[a，b]，在其中點左右取2個對稱點x1和x2〔見圖1-17〕，且有圖1-17兩點對分法求解圖〔1-31〕〔1-32〕其中為一個小的正值，應使有明顯差別。如圖情況，，淘汰區(qū)間，留下區(qū)間，即，令。反復上述過程，直至。方法特點：不要求一階可微，但每淘汰一次區(qū)間需計算2個點及其目的函數(shù)值；每次可淘汰本次區(qū)間的將近一半，其大小取決于值?？捎糜谟心康暮瘮?shù)的設計和無目的函數(shù)的優(yōu)化實驗中。例1-7，知初始極限值區(qū)間[a，b]＝[0.0，1.0]，收斂精度要求在初始區(qū)間的10％以內，即。解法一用古典極值法〔即求導方法〕。由解得故x*為極大點解法二用中心對分法。知由x1=(a+b)/2=0.5，可淘汰區(qū)間[0,0.5]，留下區(qū)間[0.5,1]。計算x2=(0.5+1.0)/2=0.75，故準確解x*＝0.75，f(x*)=0.5625。解法三用兩點對分法。知L0=1.0，取δ＝0.001，計算x1和x2由于f2>f1，淘汰[0,0.4995]，留下新區(qū)間[0.4995,1.0]。第二次計算點為：由于，淘汰[0.4995,x3]，留下新區(qū)間[x3,1.0]。第三次計算點為：由于，淘汰，留下新區(qū)間，此時，已接近要求精度。取最終區(qū)間的中點x*＝(0.74925+0.875125)/2=0.8121875作為近似極大點，f(x*)=0.558632715。方法比較：解法一僅需計算一次導數(shù)，即可求得準確解。解法二計算了2次導數(shù)，求得了準確解。解法三計算了6次目的函數(shù)，取最后區(qū)間的中點作為近似極大點，與準確解比較，尚有較大誤差。可見解法三的計算次數(shù)多，但不要求可微。1.4.5二次插值法二次插值法是多項式逼近法的一種，利用目的函數(shù)在假設干點的信息和函數(shù)值，構成一個與目的函數(shù)相接近的低次插值多項式，然后求該多項式的最優(yōu)解作為原函數(shù)的近似最優(yōu)解。隨著區(qū)間的逐次減少，多項式的最優(yōu)點與原函數(shù)最優(yōu)點之間的間隔逐漸減少，直到滿足一定精度要求時終止迭代。

設目的函數(shù)f(x)在三點上的函數(shù)值分別為，二次插值多項式為多項式在插值點的函數(shù)值應與目的函數(shù)的函數(shù)值相等，滿足：〔1-33〕求得〔1-34〕為求極小點，將3個系數(shù)代入插值多項式，令一階導數(shù)為零，有〔1-35〕將〔1-34〕中的b、c代入式〔1-35〕〔1-36〕式中由于初始區(qū)間較大，第一次構造的多項式極小點的近似解是達不到預期精度的，需求經過幾次逼近計算來減少區(qū)間，使構造的點列不斷接近目的函數(shù)的極小點。區(qū)間減少的原那么如圖1-18所示。圖1-18二次插值區(qū)間減少的四種情況〔1〕，以為新區(qū)間，令x1、x2不變；〔2〕，以為新區(qū)間，令，x3不變；〔3〕，以為新區(qū)間，令，x1不變；〔4〕，以為新區(qū)間，令，x2、x3不變。二次插值法收斂準那么：〔1〕相繼兩次的二次插值函數(shù)極小點、之間間隔小于給定精度時，即：及〔2〕及上述兩種方式實踐上是絕對精度和相對精度。

二次插值法特點：〔1〕二次插值法只需求延續(xù)，不要求其一階可微。〔2〕收斂速度比黃金分割法快，但可靠性不如黃金分割法好，程序也較長?！?〕如p(x)的相鄰兩個迭代點重合，那么產生死循環(huán)。§1.5無約束最優(yōu)化方法和約束最優(yōu)化方法1.5.1無約束最優(yōu)化方法概述1研討無約束優(yōu)化方法的意義對于一個n維目的函數(shù)，假設在沒有任何限制條件下尋求它的極小點，稱無約束極小化問題或無約束優(yōu)化問題。數(shù)學上表達為大量實踐問題都是有約束的，研討無約束優(yōu)化方法的意義在于：〔1〕一類功能很強、運用方便的有約束優(yōu)化方法，往往能將有約束問題轉化成無約束問題，易于采用無約束優(yōu)化方法求解?！?〕有些問題在不很接近最優(yōu)解時可先作無約束問題求解，然后采用有約束方法求出最優(yōu)解。〔3〕有些實踐問題本身是無約束的，或把有些約束問題經過模型變換可以轉化為無約束問題求解?！?〕對于多維無約束問題來說，古典極值實際中令一階導數(shù)為零，但要求二階可微，且要判別Hessian矩陣為正定才干求得極小點，這種方法有實際意義，但無適用價值。和一維問題一樣，假設多元函數(shù)F(X)不可微，亦無法求解。但古典極值實際是無約束優(yōu)化方法開展的根底。2多維無約束優(yōu)化方法的分類目前已研討出很多種無約束優(yōu)化方法，它們的主要不同點在于構造搜索方向上的差別。概括起來，可分為直接法和間接法兩大類，其詳細分類如表1-1所示。1.5.2坐標輪換法1方法概述坐標輪換法的根本構思是將一個n維優(yōu)化問題轉化為依次沿n個坐標方向反復進展一維搜索問題。這種方法的本質是把n維問題的求優(yōu)過程轉化為對每個變量逐次進展一維求優(yōu)的循環(huán)過程。每次一維搜索時，只允許個變量的一次改動，其他(n-1)個變量固定不變。故坐標輪換法也常稱單變量法或變量交錯法。2迭代過程〔1〕任選初始點，搜索方向〔2〕以為初始點，沿e1作正向試探性移步，步長取。假設試探勝利，沿此方向一維搜索；否那么，沿坐標的負方向試探。假設正負方向試探均失敗，那么迭代點不動，轉入下一步。〔3〕以為沿e2方向作為一維搜索的新起點，按步驟〔2〕進展，得點。以此類推，進展完一輪一維搜索后，得?！?〕以作為第二輪的初始點，反復步驟〔2〕和〔3〕，得第二輪搜索的終點，相繼進展第三、第四輪等的搜索?！?〕假設從某輪的起始點出發(fā)，依次沿n個坐標軸的正負方向試探均失敗，那么縮短初始試探步長，前往(2)。當初始步長縮減到足夠小，滿足時，迭代終止。3方法特點〔1〕計算量少，程序簡單，但計算效率較低，特別在維數(shù)很高時很費機時，故僅適用于n較少〔n<10〕的目的函數(shù)求優(yōu)。〔2〕改動初始點重新迭代，可防止出現(xiàn)病態(tài)。4算法盒圖見圖1-19。圖1-19坐標輪換法算法盒圖例1-8坐標輪換法求目的函數(shù)的無約束最優(yōu)解，初始點解第一輪輪迭代1〕沿向一維搜索2〕求：求得以為新起點，沿方向一維搜索求同理得到：3〕判別繼續(xù)進展第二輪迭代計算前往到1〕反復循環(huán)1.5.3鮑威爾法鮑威爾法是以共軛方向為根底的收斂較快的直接法之一，是一種非常有效的算法。在無約束方法中許多算法都是以共軛方向作為搜索方向，它具有許多特點。根據構造共軛方向的原理不同，可以構成不同的共軛方向法。1共軛方向法的概念〔1〕定義設A為n階對稱正定矩陣，假設有兩個n維矢量S1和S2，滿足：那么稱矢量S1和S2對矩陣A共軛，共軛矢量的方向稱共軛方向，即S1和S2是在A度量意義下的正交。可見，S1和S2本來不相交，而與S1正交，與S2正交。假設A＝E，那么有，變成直角坐標方向，即對單位矩陣E的正交。推行到n個n維矢量的情形。設有n個不為零的n維不同矢量，如滿足下面的兩個條件：那么稱n個n維矢量是對A共軛的。〔2〕共軛方向與函數(shù)極小點的關系設有普通二維二次正定函數(shù)其等直線是同心橢圓族，見圖1-20。圖1-20同心橢圓族特性從出發(fā)，沿S1方向作一維搜索，得最優(yōu)點〔與橢圓相切〕；再從另一初始點出發(fā)，仍沿S1方向作一維搜索，得最優(yōu)點〔也與橢圓相切〕，設與連線的方向為S2，那么S2必過橢圓族的中心，即X*點，且S1和S2必與A正交。2搜索方向1964年，鮑威爾提出這種算法，其根本思想是用迭代點的目的函數(shù)值來構造共軛方向，然后從任一初始點開場，逐次沿共軛方向作一維搜索求極小點。并在以后的實際中進展了改良。其詳細構造過程如下所述。任選初始點，然后與坐標輪換法一樣，分別沿坐標方向e1，e2，…，en作一維搜索，依次求得近似極小點、、…、。每作完一次搜索，銜接初始點和最后一個點構造新的方向，并判別能否要交換原來的某一方向。3迭代過程〔1〕任選初始點，給定精度，k=1，取初始方向組為坐標單位矢量，即：〔2〕

沿諸方向作n次一維搜索，依次確定各最優(yōu)步長，使得到點列〔3〕收斂準那么判別：假設或對于一切i=1,2,…,n滿足那么迭代終了。否那么轉下一步。〔4〕計算各點的函數(shù)值，并找出相鄰兩點函數(shù)值之差最大者，以標志，即及與之對應的兩個點和，并以表示該兩點的連線所指方向。〔5〕計算映射點及函數(shù)值、、，判別能否成立。假設兩者或其中之一成立，那么轉入下步。否那么轉入步驟〔7〕。〔6〕令k=k+1，計算新一輪的初始點和方向組為并前往步驟〔2〕?！?〕產生第n+1個新方向并在該方向上作一維搜索求最優(yōu)步長，使得此方向上的極小點〔8〕令，前往步驟〔2〕。1.5.4最速下降法〔梯度法〕和共軛梯度法1最速下降法〔梯度法〕〔1〕方法概述根本思想：任一點的負梯度方向是函數(shù)值在該點下降最快的方向。將n維問題轉化為一系列沿負梯度方向用一維搜索方法尋優(yōu)的問題，利用負梯度作為搜索方向，故稱最速下降法或梯度法。收斂準那么為〔2〕迭代過程1〕任選初始點，給定收斂精度。2〕求迭代點的負梯度方向。對迭代點，k=0,1,2,…，求的梯度：計算梯度的模確定負梯度的單位向量3〕進展一維搜索。以為起點，沿方向作一維搜索求最優(yōu)步長，使于是得下一個迭代點4〕當?shù)c滿足收斂準那么時，迭代終了。否那么，令，前往步驟2〕?！?〕梯度法動態(tài)迭代圖，見圖1-21。圖1-21梯度法動態(tài)迭代圖例1-9求的極小值，初始點收斂精度解1〕給定初始點，允差置2〕計算迭代點的梯度和方向原函數(shù)梯度為：點的為梯度的負方向為3〕最優(yōu)步長因子，由迭代公式令求得4〕迭代計算梯度模5〕判別不滿足精度要求，以為起點從2)反復，直到為止。2共軛梯度法為抑制梯度法中先快后慢之缺乏引入共軛梯度概念，共軛梯度法最早是由Fletcher和Reeves〔1964〕提出的。假設是二階的，并且在每一個搜索方向上被準確的最小化，那么它具有最多在次迭代中收斂的理想特性，這是由于它的搜索方向共軛。這種方法僅僅比最速下降法增大了很少的計算量，但卻顯示出較大的改良。它結合了當前梯度向量的信息以及前一次迭代的梯度向量信息，來求得一個新的搜索方向。可以利用當前梯度和原搜索梯度的線性組合來計算新的搜索方向。這種方法的優(yōu)點是在每步計算中僅僅需求存儲少量信息，所以能被運用到大型問題上。〔1〕原理利用目的函數(shù)的梯度確定共軛方向，使得計算簡便而效果又好。設目的函數(shù)〔1-37〕其中，的二階導數(shù)矩陣；是常數(shù)向量，；是常數(shù)，在次迭代計算中從出發(fā)求〔一維搜索〕。如圖1-22所示，，求最優(yōu)步長因子。圖1-22共軛梯度法的原理在兩點處函數(shù)的梯度分別為：兩式相減為〔1-38〕為簡便，令所以為使下一次搜索方向對A共軛，需有代入，那么得〔1-39〕由此式可見，它不含矩陣A，只需求出相應點得梯度，便可求得與共軛的方向。即共軛方向只與相鄰兩迭代點的梯度有關。〔2〕共軛梯度方向的構成假設在第次迭代中點的負梯度知，其方向為，那么構成的共軛方向應滿足與假設為實對稱矩陣，方向為共軛方向。那么：令共軛方向表示成在迭代點的負梯度向量與前一迭代搜索方向兩者的線性組合，即〔1-40〕式中：要使求出的與共軛，故稱為共軛系數(shù)。共軛系數(shù)的求法：將〔1－40〕代入式〔1－39〕得〔1-41〕由于相鄰兩次迭代的負梯度方向與線性無關且正交，即是一正交系，故有或〔1-42〕式〔1－41〕可簡化為〔1-43〕即〔1-44〕式中：、分別為點、梯度的模。〔3〕迭代步驟1〕任選初始點給定計算精度和輸入維數(shù)，計算，令，取2〕用一維搜索求的最優(yōu)解，即并計算在處的梯度3〕終止判別假設迭代終止，否那么轉4)4〕判別？是：那么令并轉1)否：假設，轉5)5〕計算共軛方向，計算6〕令轉2)〔4〕共軛梯度法算法盒圖，見圖1-23。例1-10用共軛梯度法求函數(shù)的最小值。解1〕取將代入，求，得，那么2〕求同前處置求得特點：快！只求兩點就找到1.5.5阻尼牛頓法和DFP變尺度法1阻尼牛頓法〔1〕方法概述牛頓法是求函數(shù)極值的最古老算法之一。其根本思想是在點的鄰域內用一個二次函數(shù)去近似替代原目的函數(shù)，然后求二次函數(shù)的極小點作為下一個迭代點，經過不斷構造二次函數(shù)和迭代計算，使迭代點逼近函數(shù)的極小點。阻尼牛頓法是在原始牛頓法根底上進展修正，能保證每次迭代點的函數(shù)值都有所下降?！?〕阻尼牛頓法迭代過程1〕選一個好的初始點，給定收斂精度，令。2〕計算的梯度方向：及其模。3〕檢驗收斂準那么。假設，輸出，，否那么轉入下一步。4〕計算點的，并求其逆矩陣。5〕確定牛頓方向，，并沿此方向作一維搜索求步長，使

6〕計算迭代點：，令k=k+1，前往步驟2)?！?〕方法特點1〕初始點應選在附近，有一定難度。2〕雖然每次迭代都不會使函數(shù)值上升，但不能保證每次下降。3〕假設迭代點的Hessian矩陣為奇特，那么無法求逆矩陣，不能構造牛頓方向。4〕不僅要計算梯度，還要求海賽矩陣及其逆矩陣，計算量和存儲量大。此外，對于二階不可微的F(X)也不適用。雖然阻尼牛頓法有上述缺陷，但在特定條件下它具有收斂最快的優(yōu)點，并為其他的算法提供了思緒和實際根據。2DFP變尺度法〔1〕方法概述梯度法的最大優(yōu)點是初始點可任選，且開場幾次迭代，目的函數(shù)值下降很快，其主要缺陷是迭代點接近極小點時，對二次正定函數(shù)收斂也非常慢。牛頓法的最大優(yōu)點是對二次正定函數(shù)迭代一次即收斂，但也有不少缺陷。人們自然會想到，能否汲取這兩種方法之長，努力抑制它們的缺陷，來建立更好的算法。DFP變尺度法就是這樣的算法之一。這種算法首先有戴維頓〔Davidon〕于1959年提出，又于1963年由弗萊徹〔Fletcher〕和鮑威爾加以開展和完善，成為現(xiàn)代公認的較好的算法之一。DFP法是基于牛頓法的思想又作了重要改良。這種算法僅用到梯度，不用計算海賽陣及其逆矩陣，但又能使搜索方向逐漸逼近牛頓方向，具有較快的收斂速度?！?〕迭代過程1〕任選初始點，計算收斂精度，維數(shù)n；2〕給定變尺度矩陣初值〔單位矩陣〕，令，置k=0；3〕求探求方向和最優(yōu)步長因子4〕進展一維搜索，求下一個迭代點5〕檢驗能否滿足，假設滿足，那么即為極小點，停頓迭代。否那么轉下一步；6〕檢查迭代次數(shù)，假設，那么，轉向步驟2)，假設那么進展下一步；7〕構造新的探求方向為此應計算、、然后令轉步驟3)。1.5.6線性規(guī)劃——單純形法線性規(guī)劃是運用最廣的優(yōu)化技術之一，也可以說是一種最有效的優(yōu)化技術。目的函數(shù)和約束函數(shù)都是線性函數(shù)的最優(yōu)化問題，稱為線性規(guī)劃或線性優(yōu)化問題。線性規(guī)劃是數(shù)學規(guī)劃中的一個比較成熟的分支。在消費方案、工程預算和經濟管理領域內運用非常廣泛。同時，線性規(guī)劃算法也可作為求解非線性有約束優(yōu)化問題的子問題的工具，如可行方向法中可行方向的搜索就是采用線性規(guī)劃方法。下面是在工廠管理中出現(xiàn)的線性規(guī)劃例子：1〕按進度表安排員工，使一周中每天的勞動人數(shù)都很充足，并且要讓工人的稱心程度和勞動消費率盡能夠的高；2〕選擇即將要消費的產品，充分利用現(xiàn)有的資源，并在當前的價錢下獲取最大的利潤；3〕找到一個工廠車間到倉庫的分配方式，在有限的才干下使本錢最??；4〕在思索到利潤、競爭對手出標和操作約束條件的情況下，使競標勝利。當用數(shù)學言語表述時，一切這些問題都隱含了許多變量、等式和不等式。一個處理方案不僅要滿足一切的約束條件，而且必需完成目的函數(shù)的極值要求，例如利潤最大或本錢最小。利用現(xiàn)代軟件，可以建立并處理帶有數(shù)千個變量和約束條件的線性問題。1線性規(guī)劃的規(guī)范方式與解線性規(guī)劃的數(shù)學模型同樣由設計變量、目的函數(shù)和約束條件組成，不過其中的約束條件除變量非負性限制外都采用等式約束。線性規(guī)劃問題的普通方式為〔1-45〕其矩陣方式為〔1-46〕式中，AX=B——約束方程；B——常數(shù)向量；A——系數(shù)矩陣。普通情況下，應有,由于當m=n時約束方程只需一個獨一的解，不存在可供選擇的其他解，不存在優(yōu)化問題。當時，約束方程有無窮多組解，線性規(guī)劃就是要從這無窮多組解中尋覓一個使目的函數(shù)極小化的最優(yōu)解。在線性規(guī)劃的數(shù)學模型中，約束條件主要是等式約束，不等式約束僅限于變量的非負約束。對于其他方式的不等式約束，可以經過引入松弛變量的方法將其轉化為等式約束。例如,對于約束條件可經過引人松弛變量，變換為假設原來問題中的某些變量并不要求非負，那么可將其變換為兩個非負變量之差。經過上述處置后,線性規(guī)劃問題總能變換為式(1-32)或式(1-33)所示的線性規(guī)劃的規(guī)范方式。例1-11某車間消費甲、乙兩種產品。消費甲種產品每件需求資料9kg、3個工時、4kw電能，可獲利60元。消費乙種產品每件需用資料4kg、10個工時、5kw電能，可獲利120元。假設每天能供應資料360kg，有300個工時，能供200kw電能，那么每天消費甲、乙兩種產品各多少件才可以獲得最大的利潤。設每天消費的甲、乙兩種產品分別為、件,那么此問題的數(shù)學模型如下引入松弛變量、、，將其轉換為規(guī)范方式該問題的解如圖1-24所示。在約束方程中，假設令n-m個變量為0，就可求得另外m個不全為0的解。于是這m個不全為0的解和n-m個為0的解共同組成一個解向量，稱為線性規(guī)劃問題的根本解。其中m個不全為0的變量稱為根本變量，其他n-m個為0的變量稱為非根本變量。在系數(shù)矩陣中，任取m列可以構成一個根本解，可知一個線性規(guī)劃問題的根本解的個數(shù)等于陳列組合數(shù)圖1-24二維線性規(guī)劃問題的圖解法由圖可以看出，線性規(guī)劃的約束邊境為一組直線或平面，由這些直線和平面構成的可行域是一個封鎖的凸多邊形或凸多面體。這個凸多邊形或凸多面體的每一個頂點對應該線性規(guī)劃問題的一個根本可行解。因此線性規(guī)劃問題的最優(yōu)解必定在這些頂點上獲得。實踐上，線性規(guī)劃解法就是一種關于根本可行解的迭代算法，或者說是一種可行域頂點轉換的算法。2根本可行解及其轉換既然線性規(guī)劃問題的最優(yōu)解必定在約束條件所圍成的凸多邊形或凸多面體的頂點上獲得，而每一個頂點都是線性規(guī)劃問題的一個根本可行解，那么線性規(guī)劃問題的求解可歸結為找出目的函數(shù)值下降的根本可行解的過程。這樣，求解線性規(guī)劃問題需求處理以下兩個問題：①根本可行解的求解；②新的根本可行解應使目的函數(shù)有較大的下降?！?〕根本解及其轉換1〕根本解的產生根據根本解的定義，對由系數(shù)矩陣和常數(shù)向量組成的如下增廣矩陣〔1-47〕進展一系列初等變換，將其中系數(shù)矩陣的m列依次變?yōu)榛蛄繒r，滿足約束方程的一個根本解便產生了。假設經m次主元變換后，將增廣矩陣的前m列變?yōu)槿缦聠挝蛔泳仃嚒?-48〕約束方程變換為如下的正那么方程＝〔1-49〕那么,對應的根本解為〔1-50〕其中，前m個變量為根本變量，后n-m個變量為非根本變量。假設變換后的常數(shù)項均為非負，即，那么此根本解是一個根本可行解?？梢?，得到一個根本解或根本可行解的方法，都是對增廣矩陣進展高斯消元變換。消元變換的根本公式為上式闡明了對轉軸變量以為轉軸元素的轉軸變換或消元變換。2〕解的轉換在式(1-48)的增廣矩陣中，將某一非根本變量對應的恣意一個系數(shù)作為轉軸變換的轉軸元素，進展另一次消元變換，又可得到一個新的增廣矩陣和相應的根本解。這種變換實踐上是一種非根本變量和根本變量的轉換，也是從一組根本解向另一組根本解的轉換。但是這樣的變換并不能保證變換后的常數(shù)向量為非負。也就是說，假設原來的解是一個根本可行解，不能保證變換后的解也是一個根本可行解?！?〕根本可行解的轉換——規(guī)那么(選擇轉軸行)要使變換后所得的根本解為可行解，還要研討這樣的方法，即如何使某個選定的變量進入根本變量，來交換另一個如今還在根本變量中的，構成新的根本可行解。當曾經得到一組可行解，即，假設要求把選進根本變量的下一組根本解是可行解的話，那么在系數(shù)矩陣第k列一切系數(shù)中不能取任何負值的軸元素，否那么將使轉軸變換后的對應元素為負值，結果對應的必將是負的，它就不是可行解的一個元素。因此，第一個要求是，假設,那么必需叫才可選做轉軸元素進展轉軸運算，用替代。這個過程是反復進展轉軸運算，直到從某個正值變成0，而從0變成某個正值為止。根據原來的正那么方式方程組(1-49)，由于要求由非根本變量變成根本變量，其值將由0變成某一正值，這將引起原來各根本變量取值的變化〔1-52〕假設式〔1-52〕是可行解，且又是其中的一個根本變量,那么在中必然有一個(假定它是)是0，其他皆為正。當然這個變量就應從根本變量中排除出去。這就是說，只需取式〔1-52〕中各差值的最小者為0時，才干保證使其他各差值皆為正。所以，由可知，只需保證才干使進入可行解的根本變量，將置換出去。同時，由于非負，對又有的要求。此時，上式中的就是進展轉軸運算時應取的轉軸元素。這就是所謂的選擇轉軸行的規(guī)那么。假想象使取代成為可行解中的根本變量，所選的轉軸行或轉軸元素要滿足條件〔1-53〕在例1-11中，可得一組可行解、為非根本變量，、、為根本變量。思索將變換為根本變量，由于最小者為，故取調出行(第1行)為轉軸行，取調出行與調入列(第1列)相交處的元素為轉軸元素，作轉軸變換，使取代成為根本變量，從而得到一組新的根本可行解。〔3〕初始根本可行解的建立初始根本可行解可經過三種方法獲得：1〕經過對增廣矩陣進展消元變換得到，這是一種較繁瑣的方法；2〕當約束條件全部為不等式約束，且常數(shù)向量均大于零時，引入松弛變量，并選取松弛變量作為根本變量，就可得到一個根本可行解〔例1-11〕；3〕假設除變量非負約束條件外，其他約束均為等式約束而無法引入松弛變量時，可引入人工變量，并構造以人工變量之和為輔助目的函數(shù)的輔助線性規(guī)劃問題，即〔1-54〕式中，為引入的人工變量。假設不等式約束條件右端項是負值，它所對應的松弛變量就不能作為根本可行解的根本變量，所以上述方法并不是總能勝利的。這時需引入人工變量，經過變換再將它從根本變量中交換出去，詳細作法舉例闡明如下。例1-12對線性規(guī)劃問題引入松弛變量、、、，將問題變換為規(guī)范方式：由于中的系數(shù)為-1，而常數(shù)項為3500，所以不能進入根本可行解的根本變量中。為此需引入一個非負的人工變量，將約束條件變?yōu)橛纱艘鹨粋€問題，就是要保證最后能把從最優(yōu)解中排除出去。為了做到這一點，可以給一個很大的系數(shù)，對于極小值問題它應取正值(對于極大值問題取負值)。而只需F(X)還沒有到達極值，運算過程還可以繼續(xù)進行下去。在給一個很大的系數(shù)后，目的函數(shù)中將添加一項給。因此，只需還不為零，目的函數(shù)就沒有到達極小(大)值。這樣，該線性規(guī)劃問題變?yōu)?取=1000)。初始根本可行解為對此輔助規(guī)劃問題進展消元變換，當輔助目的函數(shù)值等于0時，所得輔助線性規(guī)劃問題的前n個變量的值便構成了線性規(guī)劃問題的一個初始根本可行解。3最優(yōu)解的搜索——最速變化規(guī)那么(選擇轉軸列)經過規(guī)那么可以實現(xiàn)從一個根本可行解到另一個根本可行解的變換。為了經過根本可行解的變換盡快找到最優(yōu)解，進展根本可行解變換應向著目的函數(shù)值有較大下降的方向進展，這可經過最速變化規(guī)那么來實現(xiàn)。對于由前m個變量為根本變量組成的根本可行解〔1-55〕目的函數(shù)可以寫成〔1-56〕將上式對應的根本可行解變換，得到另一組根本可行解，它的根本變量中包含有，即〔1-57〕其中的，所對應的目的函數(shù)為〔1-58〕令〔1-59〕那么〔1-60〕式中為相對價值系數(shù)?！?-61〕顯然，對極小化問題，應有，即r是負值。只需r仍是負值，那么目的函數(shù)還沒有到達極小值，還有下降的趨勢，就還可以進展轉軸運算，生成另一組可行解。一旦r為正，即可停頓轉軸運算，對應的可行解就是最優(yōu)解。也能夠有幾組都為負值。對極小化問題應取〔1-62〕式中，這樣可以使目的函數(shù)獲得最大下降。根據式〔1-62〕的正負性判別能否獲得最優(yōu)解的方法稱為最速變化規(guī)那么。在求解極小點過程中，先利用約束條件方程組解出可行解，再用最速變化規(guī)那么對其檢驗，從中找出最優(yōu)解。計算時，也可以直接把目的函數(shù)和約束條件同時列為轉軸運算方程組。采用邊計算可行解，邊校驗目的函數(shù)值的變化情況的方法來求最優(yōu)解。這時，對于極小化問題，只需〔1-63〕中的系數(shù)有一個或幾個是負值，就闡明目的函數(shù)值還可以減小，就應把對應于的變量選進可行解的根本變量中去。規(guī)那么和最速變化規(guī)