《最優(yōu)化方法》最優(yōu)化方法概述

2024/8/29最優(yōu)化方法1最優(yōu)化方法2024/8/29最優(yōu)化方法2研究內(nèi)容：在有限種或無限種可行方案中挑選最優(yōu)方案，構(gòu)造尋求最優(yōu)解的計算方法研究目的：主要解決最優(yōu)計劃、最優(yōu)分配、最優(yōu)決策、最佳設(shè)計、最佳管理等最優(yōu)化問題。應(yīng)用領(lǐng)域：科學(xué)工程、國防、交通、管理、經(jīng)濟、金融、計算機等。最優(yōu)化方法概述2024/8/29最優(yōu)化方法3

最優(yōu)化方法(OptimizationTechniques)隸屬于運籌學(xué).

運籌學(xué)（OperationsResearch）是用數(shù)學(xué)方法研究各種系統(tǒng)的最優(yōu)化問題，應(yīng)用數(shù)學(xué)模型求得合理利用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。數(shù)學(xué)規(guī)劃又包括線性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃，目標(biāo)規(guī)劃和動態(tài)規(guī)劃等，是運籌學(xué)的主要內(nèi)容.背景知識2024/8/29最優(yōu)化方法4

運籌學(xué)這一名詞最早出現(xiàn)于1938年。當(dāng)時英，美等國盟軍在與德國的戰(zhàn)爭中遇到了許多錯綜復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題難以解決，比如防空雷達(dá)的布置問題護(hù)航艦隊的編隊問題為了應(yīng)付上述各種復(fù)雜問題，英美等國逐批召集不同專業(yè)背景的科學(xué)家，在三軍組織了各種研究小組，研究的問題都是軍事性質(zhì)的，這些研究小組運用系統(tǒng)優(yōu)化的思想，應(yīng)用數(shù)學(xué)技術(shù)分析軍事問題，取得了非常理想的效果。2024/8/29最優(yōu)化方法5

二次大戰(zhàn)以后，在軍事運籌小組中工作過的一部分科學(xué)家開始轉(zhuǎn)入民用部門，他們把對軍事系統(tǒng)最優(yōu)化的研究成果拓展到各種民用系統(tǒng)的研究上。

1947年美國數(shù)學(xué)家G.B.Dantzig在研究美國空軍資源配置時,提出了求解線性規(guī)劃的有效方法—單純形法。二十世紀(jì)五十年代初，應(yīng)用計算機求解線性規(guī)劃獲得成功。至五十年代末，一些工業(yè)先進(jìn)國家的大型企業(yè)已經(jīng)較普遍地使用運籌學(xué)方法解決在生產(chǎn)經(jīng)營管理中遇到的實際問題，并取得了良好的效果，至六十年代中期，運籌學(xué)開始應(yīng)用于一些服務(wù)性行業(yè)和公用事業(yè)。2024/8/29最優(yōu)化方法6

我國運籌學(xué)的研究始于五十年代中期，當(dāng)時由錢學(xué)森教授將運籌學(xué)從西方國家引入我國，以華羅庚教授為首的一大批科學(xué)家在有關(guān)企事業(yè)單位積極推廣和普及運籌學(xué)方法，在建筑，紡織，交通運輸，水利建設(shè)和郵電等行業(yè)都有不少應(yīng)用。關(guān)于郵遞員投遞的最佳路線問題就是由我國年輕的數(shù)學(xué)家管梅谷于1962年首先提出的，在國際上統(tǒng)稱為中國郵遞員問題。我國運籌學(xué)的理論和應(yīng)用研究在較短時間內(nèi)趕上了世界水平。2024/8/29最優(yōu)化方法7學(xué)習(xí)本課程所需的數(shù)學(xué)知識向量、向量的模（范數(shù)）、向量的運算、線性相關(guān)與無關(guān)、基.

矩陣的運算及性質(zhì)、矩陣的秩、特征值、正定性。

向量函數(shù)、連續(xù)性、可微性、梯度、向量函數(shù)（多元函數(shù)）的Taylor定理2024/8/29最優(yōu)化方法8課程基本內(nèi)容線性規(guī)劃無約束最優(yōu)化方法約束最優(yōu)化方法多目標(biāo)最優(yōu)化方法2024/8/29最優(yōu)化方法9學(xué)習(xí)要求及考評掌握主要的優(yōu)化模型的數(shù)學(xué)計算方法，可以應(yīng)用數(shù)學(xué)軟件解決最優(yōu)化問題。考評：大作業(yè)（作業(yè)+小論文）

2024/8/29最優(yōu)化方法10參考書目主要參考書目：理論方面：(1)解可新、韓健，《最優(yōu)化方法》，天津大學(xué)出版社,2004(2)何堅勇，《最優(yōu)化方法》,清華大學(xué)出版社，2007計算方面：(3)曹衛(wèi)華，郭正，《最優(yōu)化技術(shù)方法及MATLAB的實現(xiàn)》，化學(xué)工業(yè)出版社，2005(4)朱德通，《最優(yōu)化模型與實驗》,同濟大學(xué)出版社，2003

其它參考書：(5)盧名高、劉慶吉編著，《最優(yōu)化應(yīng)用技術(shù)》，石油工業(yè)出版社,2002(6)唐煥文，秦學(xué)志,《實用最優(yōu)化方法》，大連理工大學(xué)出版社，2004(7)錢頌迪，《運籌學(xué)》，清華大學(xué)出版社，1990(8)袁亞湘、孫文瑜著，《最優(yōu)化理論與方法》，科學(xué)出版社，2005

2024/8/29最優(yōu)化方法11線性規(guī)劃的基本概念

線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃的圖解法線性規(guī)劃問題的標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型線性規(guī)劃的解線性規(guī)劃的基本原理2024/8/29最優(yōu)化方法12問題的提出：在生產(chǎn)管理的經(jīng)營活動中，通常需要對“有限的資源”尋求“最佳”的利用或分配方式。有限資源：勞動力、原材料、設(shè)備或資金等最佳：有一個標(biāo)準(zhǔn)或目標(biāo)，使利潤達(dá)到最大或成本達(dá)到最小。有限資源的合理配置有兩類問題如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大；在生產(chǎn)或經(jīng)營的任務(wù)確定的條件下，合理的組織生產(chǎn)，安排經(jīng)營活動，使所消耗的資源數(shù)最少。線性規(guī)劃問題及其數(shù)學(xué)模型2024/8/29最優(yōu)化方法13有一正方形鐵皮，如何截取x使容積為最大？xa此為無約束極值問題問題的提出2024/8/29最優(yōu)化方法14

為了完成一項任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個過程就是規(guī)劃。2024/8/29最優(yōu)化方法15規(guī)劃確定型隨機型靜態(tài)規(guī)劃動態(tài)規(guī)劃線性規(guī)劃非線性規(guī)劃

整數(shù)規(guī)劃非整數(shù)規(guī)劃整數(shù)規(guī)劃非整數(shù)規(guī)劃規(guī)劃類型2024/8/29最優(yōu)化方法16例１:某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時間，以及該廠每周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）

3020160設(shè)備（臺）

5115

已知該廠生產(chǎn)每噸甲、乙藥品的利潤分別為5萬元和2萬元。但根據(jù)市場需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應(yīng)超過4噸。問該廠應(yīng)如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤最大？2024/8/29最優(yōu)化方法17

定義:

x1為生產(chǎn)甲種藥品的計劃產(chǎn)量數(shù)，

x2為生產(chǎn)乙種藥品的計劃產(chǎn)量數(shù)。

目標(biāo)：要使總利潤最大化maxz=5x1+2x2

約束：每周資源總量的限制，

30x1+20x2≤1605x1+x2≤15甲種藥品每周產(chǎn)量不應(yīng)超過4噸的限制x1≤4計劃生產(chǎn)數(shù)不可能是負(fù)數(shù)，x1≥0x2≥0每噸產(chǎn)品的消耗

每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺）

5115單位利潤(萬元)

5２2024/8/29最優(yōu)化方法18

數(shù)學(xué)模型為每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺）5115單位利潤(萬元)5２這是一個如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大的數(shù)學(xué)規(guī)劃問題。在滿足一組約束條件的限制下，尋求決策變量x1，x2的決策值，使目標(biāo)函數(shù)達(dá)到最大值。2024/8/29最優(yōu)化方法19例２：某化工廠根據(jù)一項合同要求為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特種產(chǎn)品。已知甲、乙兩種原料都含有A、B、C三種化學(xué)成分，兩種原料分別所含三種化學(xué)成分的百分比含量，以及按合同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示：已知甲、乙兩種原料的成本分別是每公斤3元和2元，廠方希望總成本達(dá)到最小，問如何配置該產(chǎn)品？

原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155化學(xué)成分2024/8/29最優(yōu)化方法20定義

x1，x2分別為每公斤產(chǎn)品中甲，乙兩種原料的數(shù)量，目標(biāo)：使總成本最小化minz=3x1+2x2約束：配料平衡條件，x1+x2=1產(chǎn)品中A、B、C三種化學(xué)成分的最低含量

12x1+3x2≥4

2x1+3x2≥2

3x1+15x2≥5非負(fù)性條件x1≥0,x2≥0

原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分2024/8/29最優(yōu)化方法21數(shù)學(xué)模型：

原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分這是一個原料配制問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。滿足一組約束條件的同時，尋求變量x1和x2的值使目標(biāo)函數(shù)取得最小值。2024/8/29最優(yōu)化方法22例３:某鐵器加工廠要制作100套鋼架，每套要用長為2.9米，2.1米和1.5米的圓鋼各一根。已知原料長為7.4米，問應(yīng)如何下料，可使材料最??？

分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出8種不同的下料方案：圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料頭（米）00.10.20.30.80.91.１1.4

問題歸納為如何混合使用這8種不同的下料方案，來制造100套鋼架，且要使剩余的余料總長為最短。2024/8/29最優(yōu)化方法23

設(shè)表示用第j種下料方案下料的原料根數(shù)，j=1,2…,8,目標(biāo)：使余料總長度最小化minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8約束：三種規(guī)格圓鋼根數(shù)x1+2x2+x4+x6=100

2x3+2x4+x5+x6+3x7=1003x1+x2+2x3+3x5+x6+4x8=100非負(fù)取整條件xj≥0(j=1,2…8)且取整數(shù)圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104余料（米）00.10.20.30.80.91.１1.42024/8/29最優(yōu)化方法24

數(shù)學(xué)模型

s.t.

這是一個下料問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。滿足一組約束條件的同時，尋求變量x1至x8的值,使目標(biāo)函數(shù)取得最小值。圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料頭（米）00.10.20.30.80.91.11.4且為整數(shù)2024/8/29最優(yōu)化方法25問題中總有未知的變量，需要我們?nèi)ソ鉀Q。

要求：有目標(biāo)函數(shù)及約束條件，一般有非負(fù)條件存在，由此組成規(guī)劃數(shù)學(xué)模型。

如果在規(guī)劃問題的數(shù)學(xué)模型中，變量是連續(xù)的（數(shù)值取實數(shù)）其目標(biāo)函數(shù)是有關(guān)線性函數(shù)（一次方），約束條件是有關(guān)變量的線性等式或不等式，這樣，規(guī)劃問題的數(shù)學(xué)模型是線性的。反之，就是非線性的規(guī)劃問題。2024/8/29最優(yōu)化方法26

與規(guī)劃問題有關(guān)的數(shù)學(xué)模型總有兩部分組成：

約束條件：反映了有限資源對生產(chǎn)經(jīng)營活動的種種約束，或者生產(chǎn)經(jīng)營必須完成的任務(wù)；目標(biāo)函數(shù)：反映生產(chǎn)經(jīng)營者在有限資源條件下希望達(dá)到的生產(chǎn)或經(jīng)營的目標(biāo)。2024/8/29最優(yōu)化方法272.線性規(guī)劃的一般數(shù)學(xué)模型

線性規(guī)劃模型的特征：（1）用一組決策變量x1，x2，…,xn表示某一方案，且在一般情況下，變量的取值是非負(fù)的。（2）有一個目標(biāo)函數(shù)，這個目標(biāo)函數(shù)可表示為這組變量的線性函數(shù)。（3）存在若干個約束條件，約束條件用決策變量的線性等式或線性不等式來表達(dá)。（4）要求目標(biāo)函數(shù)實現(xiàn)最大化（max）或最小化（min）。滿足上述4個特征的規(guī)劃問題稱為線性規(guī)劃問題。2024/8/29最優(yōu)化方法28通常稱為決策變量，為價值系數(shù)，為消耗系數(shù),為資源限制系數(shù)。線性規(guī)劃的模型的一般形式:目標(biāo)函數(shù)

滿足約束條件min(max)2024/8/29最優(yōu)化方法29線性規(guī)劃問題的求解方法圖解法單純形法兩個變量、直角坐標(biāo)三個變量、立體坐標(biāo)適用于任意變量、但需將一般形式變成標(biāo)準(zhǔn)形式求解方法2024/8/29最優(yōu)化方法30

線性規(guī)劃圖解法的基本步驟（1）建立以x1,x2為坐標(biāo)軸的直角坐標(biāo)系，畫出線性規(guī)劃問題的可行域,（2）求目標(biāo)函數(shù)z=C1x1+C2x2的梯度▽z=（c1,c2）,（3）任取等值線

C1x1+C2x2=z0,沿梯度▽z正方向平移,

（若是極小化問題，則沿負(fù)梯度方向－▽z平移），求等直線將離未離可行域時與可行域的交點。（4）若交點存在，則該點坐標(biāo)就是最優(yōu)解X*

。2024/8/29最優(yōu)化方法31例⑴⑵⑶⑷2024/8/29最優(yōu)化方法32012345678123456⑴⑵⑶⑷作圖∴最優(yōu)解：x1=4x2=2有唯一最優(yōu)解，Z=14x2

x1(42)⑴⑵⑶⑷▽z=(2,3)2024/8/29最優(yōu)化方法33例4:利用例1說明圖解法的主要步驟，例1的數(shù)學(xué)模型為2024/8/29最優(yōu)化方法34O51015x1x1=4x2101AB(2,5)C▽z5x1+x2=1530x1+20x2=1605x1+2x2=52024/8/29最優(yōu)化方法35例5：max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8

x1≥0,x2≥0可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860x1x22024/8/29最優(yōu)化方法362.圖解法的幾種可能結(jié)果

(1）有唯一最優(yōu)解（2）有無窮多最優(yōu)解（3）無界解（或稱無最優(yōu)解）無界解是指線性規(guī)劃問題的最優(yōu)解無界。若是極大化問題，則可使目標(biāo)函數(shù)值z→+∝,

極小化問題則可使目標(biāo)函數(shù)值z→-∝，有無界解的線性規(guī)劃問題的可行域通常是無界區(qū)域，但反之則不必然。2024/8/29最優(yōu)化方法37

例

例⑴⑵⑶無窮多最優(yōu)解⑴⑵無界解x1x1x2

x2

2024/8/29最優(yōu)化方法38（4）無可行解某些線性規(guī)劃問題的可行域是空集，既不存在滿足所有約束條件的點，這時問題無可行解，當(dāng)然更談不上最優(yōu)解了。在實際中出現(xiàn)這種情況可以認(rèn)為資源條件無法滿足人們的要求，既不存在可行方案。

（3）無界解（或稱無最優(yōu)解）無界解是指線性規(guī)劃問題的最優(yōu)解無界。若是極大化問題，則可使目標(biāo)函數(shù)值z→+∝,

極小化問題則可使目標(biāo)函數(shù)值z→-∝，有無界解的線性規(guī)劃問題的可行域通常是無界區(qū)域，但反之則不必然。2024/8/29最優(yōu)化方法39復(fù)習(xí)規(guī)劃--為了完成一項任務(wù)或達(dá)到一定的目的，怎樣用最少的人力、物力去完成或者用最少的資源去完成較多的任務(wù)或達(dá)到一定的目的，這個過程就是規(guī)劃。線性規(guī)劃線性規(guī)劃圖解法的基本步驟（1）建立以x1,x2為坐標(biāo)軸的直角坐標(biāo)系，畫出線性規(guī)劃問題的可行域,

（2）求目標(biāo)函數(shù)z=C1x1+C2x2的梯度▽z=（c1,c2）,

（3）任取等值線C1x1+C2x2=z0,沿梯度▽z正方向平移,

（若是極小化問題，則沿負(fù)梯度方向－▽z平移），求等直線將離未離可行域時與可行域的交點。（4）若交點存在，則該點坐標(biāo)就是最優(yōu)解X*。2024/8/29最優(yōu)化方法401.標(biāo)準(zhǔn)線性規(guī)劃模型

(1)線性規(guī)劃問題的標(biāo)準(zhǔn)形式：

其中(1.1)為目標(biāo)函數(shù)，(1.2)為約束條件，(1.3)為非負(fù)條件，為稱呼方便，有時將(1.3)也稱為約束條件。（1.2）

（1.3）

線性規(guī)劃的標(biāo)準(zhǔn)形式（1.1）2024/8/29最優(yōu)化方法41其中C=(c1,c2,…,cn)稱為價值向量，

X=(x1,x2,…,xn)T為決策變量向量，

Pj=(a1j,a2j,…,amj)T為決策變量xj所對應(yīng)的消耗系數(shù)向量，

b=(b1,b2,…,bm)T為資源向量。(2)緊湊格式：(3)向量格式：2024/8/29最優(yōu)化方法42其中為m×n階矩陣(4)矩陣格式：C=(c1,c2,…,cn)，

X=(x1,x2,…,xn)T，

b=(b1,b2,…,bm)T。2024/8/29最優(yōu)化方法432.非標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)化（1）極大化與極小化：原目標(biāo)函數(shù)(2)

線性不等式與線性等式：其中xn+i

為非負(fù)松弛變量，其中xn+k

為非負(fù)剩余變量。2024/8/29最優(yōu)化方法44

(3)非負(fù)變量與符號不受限制的變量若xi的符號不受限制，則可引進(jìn)非負(fù)變量xi1,xi2，令xi=xi1-xi2，使線性規(guī)劃里所有的變量都轉(zhuǎn)化為有非負(fù)限制的變量。(4)右端項有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如bi<0，則把該等式約束兩端同時乘以－1，得到：－ai1x1－ai2x2－

…－ainxn

=－bi

。2024/8/29最優(yōu)化方法45例6:將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型

符號不受限制解:令,可將目標(biāo)函數(shù)化為min型，令,其中2024/8/29最優(yōu)化方法46考慮一個標(biāo)準(zhǔn)的線性規(guī)劃問題：標(biāo)準(zhǔn)型線性規(guī)劃的解其中Ｃ為n維行向量，

Ｘ是n維列向量，

ｂ是m維列向量，

Ａ是m×n階矩陣，假定滿足m≤n，且Ｒ(Ａ)=m.2024/8/29最優(yōu)化方法47矩陣

矩陣A的秩

R(A)--就是

A中不等于0的子式的最高階數(shù).矩陣的逆--對于n階矩陣A，如果有一個n階矩陣B使得AB=BA=E，則稱矩陣A與矩陣B互逆，記作2024/8/29最優(yōu)化方法48

(2)最優(yōu)解:使目標(biāo)函數(shù)（1.4)達(dá)到最優(yōu)值的可行解稱為最優(yōu)解，最優(yōu)解常用X*

表示。

(3)基:若Ｂ是Ａ中m×m階非奇異矩陣，即|Ｂ|≠0，則稱Ｂ是線性規(guī)劃問題的一個基。可行解集稱為線性規(guī)劃問題的可行域。線性規(guī)劃問題解的概念：

(1)可行解:滿足約束條件(1.5)，(1.6)的解稱為線性規(guī)劃問題的可行解。2024/8/29最優(yōu)化方法49一個線性規(guī)劃的基通常不是唯一的?但是基的個數(shù)也不會超過Cnm

個?一旦確定了線性規(guī)劃的基，則相應(yīng)的基向量、基變量和非基變量也就確定。若Ｂ是線性規(guī)劃問題的一個基，那么Ｂ一定是由m個線性無關(guān)的列向量組成，不失一般性，可設(shè)稱為基向量，與基向量Pj相對應(yīng)的變量xj(j=1,2，…，m)稱為基變量。2024/8/29最優(yōu)化方法50(4)基本解。設(shè)B是線性規(guī)劃的一個基，若令n-m個非基變量等于0，則所得的方程組ＡＸ=b的解稱為線性規(guī)劃問題的一個基本解（簡稱基解）。有一個基就可以求得一個基本解。由基的有限性可知，基本解的個數(shù)也不會超過Cnm

個?

由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。(5)基本可行解。滿足非負(fù)條件的基本解稱為基本可行解(簡稱基可行解)。與基本可行解對應(yīng)的基成為可行基。當(dāng)基本可行解中有一個或多個基變量是取零值時，稱此解為

退化的基本可行解。2024/8/29最優(yōu)化方法51

線性規(guī)劃問題各種解的關(guān)系的示意圖

可行解

基本解基本可行解2024/8/29最優(yōu)化方法52例7：求下列約束方程所對應(yīng)的線性規(guī)劃的所有基本解，基本可行解。解：化為標(biāo)準(zhǔn)形式后為2×4階矩陣。且R(A)=2,所以該線性規(guī)劃基的個數(shù)≤=6個

若令非基變量，約束方程組為可得對應(yīng)的基本解是一個基本可