系統(tǒng)工程第8章-系統(tǒng)優(yōu)化

系統(tǒng)工程

第八章系統(tǒng)優(yōu)化

31August2023PPT

1本章學(xué)習(xí)目標(biāo)1.了解最優(yōu)化問題的基本概念2.學(xué)會(huì)建立最優(yōu)化問題的數(shù)學(xué)模型3.掌握線性規(guī)劃及單純形法4.掌握動(dòng)態(tài)規(guī)劃及逆序解法5.了解非線性規(guī)劃31August2023PPT

2章節(jié)框架

8.1最優(yōu)化問題概述

8.2線性規(guī)劃

8.3動(dòng)態(tài)規(guī)劃

8.4非線性規(guī)劃

本章小結(jié)

思考與練習(xí)題

參考答案31August2023PPT

38.1最優(yōu)化問題概述最優(yōu)化理論與方法最優(yōu)化理論是一個(gè)重要的數(shù)學(xué)分支，它所研究的問題是在眾多的方案中什么樣的方案最優(yōu)以及怎樣找出最優(yōu)方案。最優(yōu)化理論與方法在第二次世界大戰(zhàn)后迅速發(fā)展，成為一門新興學(xué)科，并且隨著科學(xué)技術(shù)的進(jìn)步和現(xiàn)代化生產(chǎn)的發(fā)展，越來越受到人們的重視，其發(fā)展日趨成熟。

31August2023PPT

4

在滿足約束條件的解中確定使目標(biāo)函數(shù)達(dá)到最大或最小值的問題就是最優(yōu)化問題，最優(yōu)化問題的一般數(shù)學(xué)模型為：

目標(biāo)函數(shù)約束條件8.1最優(yōu)化問題概述31August2023PPT

5

模型由三個(gè)要素組成：

(1)變量,又稱為決策變量，是問題中要確定的未知量，用以表明最優(yōu)化問題中的用數(shù)量表示的方案、措施，可以由決策者決定和控制。

(2)目標(biāo)函數(shù),它是決策變量的函數(shù)，按優(yōu)化目標(biāo)的不同分別在這個(gè)函數(shù)前加上max或min。

(3)約束條件,指決策變量取值時(shí)受到的各種資源條件的限制，通常表達(dá)為含決策變量的等式或不等式。8.1最優(yōu)化問題概述31August2023PPT

68.2

線性規(guī)劃

8.2.1線性規(guī)劃模型

8.2.2單純形法31August2023PPT

78.2.1線性規(guī)劃模型

約束條件和目標(biāo)函數(shù)都是呈線性關(guān)系的就叫線性規(guī)劃。線性規(guī)劃是最優(yōu)化理論的一個(gè)重要分支，它是研究如何在多項(xiàng)互相競(jìng)爭(zhēng)的活動(dòng)中間最優(yōu)地分配各項(xiàng)有限的資源的一種數(shù)學(xué)方法。線性規(guī)劃研究的問題主要有兩類：一類是已經(jīng)給定可用的資源的數(shù)量，如何運(yùn)用這些資源來完成最大量的任務(wù)；另一類是已經(jīng)給定一項(xiàng)任務(wù)，研究如何統(tǒng)籌安排，才能以最少量的資源去完成這項(xiàng)任務(wù)。31August2023PPT

88.2.1線性規(guī)劃模型

對(duì)于一類最優(yōu)化問題，如果同時(shí)滿足如下條件：（1）按問題的不同，要求實(shí)現(xiàn)決策變量的線性函數(shù)（即目標(biāo)函數(shù)）最大化或最小化。（2）存在一組用線性等式或線性不等式表示的約束條件。（3）每一個(gè)問題都用一組決策變量表示某一方案，一般這些變量取值是非負(fù)的。我們將滿足上述條件的問題稱為線性規(guī)劃問題，簡(jiǎn)稱為L(zhǎng)P。31August2023PPT

98.2.1線性規(guī)劃模型

一般線性規(guī)劃的數(shù)學(xué)模型具有如下形式:

31August2023PPT

10用矩陣和向量形式來描述時(shí)，上述模型可寫為：其中8.2.1線性規(guī)劃模型31August2023PPT

118.2.1線性規(guī)劃模型

為了求解問題的方便，常將多種線性規(guī)劃問題統(tǒng)一變換為標(biāo)準(zhǔn)形式:31August2023PPT

128.2.2單純形法

單純形法是應(yīng)用最早也是最廣泛的一種求解線性規(guī)劃問題的行之有效的方法。其基本思想是：從可行域中某個(gè)基可行解出發(fā)，每次用一個(gè)非基變量來取代一個(gè)基變量，也就是把一個(gè)非基變量從0增加到某一個(gè)正數(shù)，而把相應(yīng)的一個(gè)基變量從一個(gè)正數(shù)變成0，使得每一個(gè)新的解有可能改進(jìn)目標(biāo)函數(shù)值，經(jīng)過一次次迭代，目標(biāo)函數(shù)值一步步改進(jìn)，當(dāng)使目標(biāo)函數(shù)達(dá)到最大值時(shí)，線性規(guī)劃就得到了最優(yōu)解。31August2023PPT

138.2.2單純形法單純形法的基本步驟(1)找出初始可行基，確定初始基可行解，建立初始單純形表，一般先取松弛變量為基變量。(2)檢驗(yàn)各非基變量的檢驗(yàn)數(shù)，若

,則可得到最優(yōu)解，停止計(jì)算；否則轉(zhuǎn)入步驟3。(3)在中，若有某個(gè)對(duì)應(yīng)的系數(shù)列向量

0，則此問題無界，停止計(jì)算；否則，轉(zhuǎn)入步驟4。(4)根據(jù)，確定為調(diào)入變量，按最小比值規(guī)則計(jì)算確定為調(diào)出變量。轉(zhuǎn)入步驟5。31August2023PPT

14(5)用加減消元法化主元為１，同列其他系數(shù)為０，把所對(duì)應(yīng)的列向量變?yōu)椋簩⒘兄械膿Q為，得到新的單純形表，重復(fù)步驟2-5，直到終止。

8.2.2單純形法31August2023PPT

15解決線性規(guī)劃問題的一般步驟如下：(1)明確問題的目標(biāo)，劃定決策實(shí)施的范圍，建立線性目標(biāo)函數(shù)；(2)選定決策變量，一組決策變量就是一個(gè)決策方案；(3)建立約束條件，每個(gè)約束條件均為決策變量的線性函數(shù)；(4)線性規(guī)劃模型求解；(5)線性規(guī)劃模型及其解的特性分析，如靈敏度分析等。8.2.2單純形法31August2023PPT

168.3動(dòng)態(tài)規(guī)劃

8.3.1動(dòng)態(tài)規(guī)劃概述

8.3.2多階段決策問題

8.3.3動(dòng)態(tài)規(guī)劃模型31August2023PPT

17

動(dòng)態(tài)規(guī)劃是美國(guó)數(shù)學(xué)家貝爾曼（R.Bellman）等人于20世紀(jì)50年代提出的解決多階段決策過程最優(yōu)化問題的一種數(shù)學(xué)方法，并根據(jù)多階段決策問題的特點(diǎn)提出了解決這類問題的“最優(yōu)化原理”，研究了許多實(shí)際問題，最終建立了數(shù)學(xué)規(guī)劃的一個(gè)新分支——?jiǎng)討B(tài)規(guī)劃(Dynamicprogramming)，簡(jiǎn)稱為DP?？梢愿鶕?jù)時(shí)間變量是離散的還是連續(xù)的，把動(dòng)態(tài)規(guī)劃問題分為離散決策過程和連續(xù)決策過程；根據(jù)決策過程的演變是確定性的還是隨機(jī)性的，動(dòng)態(tài)規(guī)劃問題又可分為確定性的決策過程和隨機(jī)性的決策過程，即離散確定性，離散隨機(jī)性，連續(xù)確定性，連續(xù)隨機(jī)性四種決策過程模型。8.3.1動(dòng)態(tài)規(guī)劃概述31August2023PPT

188.3.2多階段決策問題

把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，這種解決多階段決策最優(yōu)化的過程為動(dòng)態(tài)規(guī)劃方法。31August2023PPT

198.3.3動(dòng)態(tài)規(guī)劃模型動(dòng)態(tài)規(guī)劃的概念(1)階段(Stage)(2)狀態(tài)(State)(3)決策(Policy)(4)策略(Strategy)(5)狀態(tài)轉(zhuǎn)移方程(Statetransformequation)(6)指標(biāo)函數(shù)(Indexfunction)31August2023PPT

20常見的指標(biāo)函數(shù)形式：(a)求和型指標(biāo)函數(shù)(b)乘積型指標(biāo)函數(shù)8.3.3動(dòng)態(tài)規(guī)劃模型31August2023PPT

218.3.3動(dòng)態(tài)規(guī)劃模型

動(dòng)態(tài)規(guī)劃的基本思想：對(duì)最優(yōu)策略來說，無論過去的狀態(tài)和決策如何，由前面諸決策所形成的狀態(tài)出發(fā)，相應(yīng)的剩余決策序列必構(gòu)成最優(yōu)子策略。也就是說，最優(yōu)策略后部的子策略總是最優(yōu)的。逆序解法：根據(jù)動(dòng)態(tài)規(guī)劃的基本思想可知，尋求最短路線的方法，就是從最后一段開始，用由后向前逐步遞推的方法，求出各點(diǎn)到點(diǎn)的最短路線。最后求出由點(diǎn)到點(diǎn)的最短路線，這種解法稱為逆序解法。31August2023PPT

228.3.3動(dòng)態(tài)規(guī)劃模型建立動(dòng)態(tài)規(guī)劃模型的過程中必須注意：（1）要解決的實(shí)際問題應(yīng)由幾個(gè)相互聯(lián)系的階段組成，而每個(gè)階段始點(diǎn)往往存在幾個(gè)可供選擇的不同狀態(tài)，對(duì)每一階段都必須進(jìn)行決策，同時(shí)要求能寫出狀態(tài)移動(dòng)方程，有些實(shí)際問題階段的組成并不明顯，需要仔細(xì)地觀察和人為地劃分，對(duì)每一種狀態(tài)可根據(jù)決策變量取值所對(duì)應(yīng)的成本大小做出決策，進(jìn)而找出最優(yōu)策略(最低成本)；（2）在動(dòng)態(tài)規(guī)劃求解中不可避免的需要確定問題的策略，子策略和指標(biāo)函數(shù)。一般來說，要解決的問題不同，策略和子策略的內(nèi)容也不同，而指標(biāo)函數(shù)的含義也隨問題的改變而改變；31August2023PPT

238.4非線性規(guī)劃

8.4.1非線性規(guī)劃概念

8.4.2二次規(guī)劃31August2023PPT

248.4.1非線性規(guī)劃概念

在實(shí)際問題中存在一類特殊的最優(yōu)化問題，他們的目標(biāo)函數(shù)或約束條件中包含有自變量的非線性函數(shù)，則將這一類特殊的規(guī)劃問題稱為非線性規(guī)劃，簡(jiǎn)記為（NP）。非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個(gè)方法都有自己特定的適用范圍。非線性規(guī)劃是線性規(guī)劃的進(jìn)一步發(fā)展和繼續(xù)。許多實(shí)際問題如設(shè)計(jì)問題、經(jīng)濟(jì)平衡問題都屬于非線性規(guī)劃的范疇。非線性規(guī)劃擴(kuò)大了數(shù)學(xué)規(guī)劃的應(yīng)用范圍，同時(shí)也給數(shù)學(xué)工作者提出了許多基本理論問題，使數(shù)學(xué)中的如凸分析、數(shù)值分析等也得到了發(fā)展。

31August2023PPT

25

非線性規(guī)劃問題模型的一般形式：一般將不帶有約束的極小化問題稱為無約束極小化問題；根據(jù)約束條件是否是等式，還可以將非線性規(guī)劃問題分為等式約束下的極小化問題和不等式約束下的極小化問題。8.4.1非線性規(guī)劃概念31August2023PPT

26Kuhn-Tucher條件：若是問題(8-12)的局部最優(yōu)解，且為正則點(diǎn)，則存在向量，使下述條件成立：8.4.1非線性規(guī)劃概念31August2023PPT

278.4.1非線性規(guī)劃概念

對(duì)于一個(gè)實(shí)際問題，在把它歸結(jié)成非線性規(guī)劃問題時(shí)，一般要注意：（1）確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認(rèn)什么是問題的可供選擇的方案，并用一組變量來表示它們。（2）提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實(shí)際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運(yùn)用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。（3）給出價(jià)值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或“壞”的價(jià)值標(biāo)準(zhǔn)，并用某種數(shù)量形式來描述它。（4）尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。31August2023PPT

288.4.1非線性規(guī)劃概念非線性規(guī)劃的Matlab解法

Matlab中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式

31August2023PPT

298.4.2二次規(guī)劃

求解約束極值問題比求解無約束極值困難得多，為了簡(jiǎn)化工作，常采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及將復(fù)雜問題變換為簡(jiǎn)單問題等方法。在下面主要介紹約束極值問題中的一類特殊問題：二次規(guī)劃問題。所謂二次規(guī)劃問題，就是非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，同時(shí)約束條件又全是線性的。二次規(guī)劃問題是非線性規(guī)劃問題中比較簡(jiǎn)單的一類，較容易求解，同時(shí)它和線性規(guī)劃問題也有直接聯(lián)系，因此在實(shí)際中常將很多方面的問題抽象成二次規(guī)劃的模型來求解。31August2023PPT

30

二次規(guī)劃的數(shù)學(xué)模型?？梢员硎鋈缦?/p>

8.4.2二次規(guī)劃31August2023PPT

318.4.2二次規(guī)劃

求解二次規(guī)劃的方法的步驟：

(1)將庫(kù)恩-塔克條件中的第一個(gè)條件應(yīng)用于二次規(guī)劃，并用代替庫(kù)恩-塔克條件中的即可得到

(2)若在式中引入松弛變量,則得到如下等式：

(3)將庫(kù)恩-塔克條件中第二個(gè)條件應(yīng)用于二次規(guī)劃，與上式聯(lián)立，31August2023PPT

32(4)聯(lián)立求解式和，若求得的解也滿足式和，則此時(shí)得到的解就為二次規(guī)劃問題的解。得到初始基本可行解8.4.2二次規(guī)劃31August2023PPT

33將上述問題修正后得到如下線性規(guī)劃問題：

8.4.2二次規(guī)劃31August2023PPT

34本章小結(jié)

本章首先通過幾個(gè)例子介紹了什么是最優(yōu)化問題，提出了最優(yōu)化問題數(shù)學(xué)模型的一般形式并解釋了模型的各個(gè)組成要素。其次介紹了最優(yōu)化問題的幾個(gè)重要分支，包括線性規(guī)劃、動(dòng)態(tài)規(guī)劃和非線性規(guī)劃。內(nèi)容包括線性規(guī)劃的定義、線性規(guī)劃模型、線性規(guī)劃模型的標(biāo)準(zhǔn)形式、單純形法；多階段決策問題的定義、動(dòng)態(tài)規(guī)劃的概念、動(dòng)態(tài)規(guī)劃模型、基本思想和逆序解法求解動(dòng)態(tài)規(guī)劃問題；非線性規(guī)劃的定義、凸函數(shù)的概念和判斷條件、Kuhn-Tucher條件、二次規(guī)劃問題的模型及其解法。通過本章的學(xué)習(xí)，要求了解最優(yōu)化問題的基本概念，學(xué)會(huì)如何分析實(shí)際問題建立最優(yōu)化問題的數(shù)學(xué)模型，并且選擇適當(dāng)?shù)姆椒ㄇ蠼庾顑?yōu)化問題。重點(diǎn)包括如何把一般形式的線性規(guī)劃模型轉(zhuǎn)變?yōu)闃?biāo)準(zhǔn)形式、如何運(yùn)用單純形法求解線性規(guī)劃問題、建立動(dòng)態(tài)規(guī)劃方程、逆序法求解動(dòng)態(tài)規(guī)劃問題、非線性規(guī)劃問題中比較簡(jiǎn)單的二次規(guī)劃問題的模型的建立及求解。31August2023PPT

35思考與練習(xí)題試述最優(yōu)化問題的數(shù)學(xué)模型的結(jié)構(gòu)及各要素的特征。什么是線性規(guī)劃問題的標(biāo)準(zhǔn)形式，如何將一個(gè)非標(biāo)準(zhǔn)型的線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式。試述單純形法的基本思想和計(jì)算步驟。試述動(dòng)態(tài)規(guī)劃的最優(yōu)化原理，動(dòng)態(tài)規(guī)劃方法的基本思想和動(dòng)態(tài)規(guī)劃基本方程的結(jié)構(gòu)。如何判斷一個(gè)函數(shù)是否為凸函數(shù)。31August2023PPT

36思考與練習(xí)題

6.某工廠生產(chǎn)甲、乙兩種產(chǎn)品，單位產(chǎn)品的銷售價(jià)格和所需要的原料的數(shù)量、原料的供應(yīng)量及單價(jià)如表8-1所示，問：工廠應(yīng)如何安排生產(chǎn)，才能使所獲利潤(rùn)最大？建立該線性規(guī)劃問題的數(shù)學(xué)模型。表8-1原料的供應(yīng)量及單價(jià)甲乙日供應(yīng)量

原料單價(jià)（百元/kg）原料A(kg)621801原料B(kg)4104002原料C(kg)