最優(yōu)化方法課件：1-1最優(yōu)化問題的數(shù)學(xué)模型與基本概念

1、 第一章 最優(yōu)化問題概述 最優(yōu)化技術(shù)是一門較新的學(xué)科分支。它是在本世紀(jì)五十年代初在電子計(jì)算機(jī)廣泛應(yīng)用的推動(dòng)下才得到迅速發(fā)展，并成為一門直到目前仍然十分活躍的新興學(xué)科。最優(yōu)化所研究的問題是在眾多的可行方案中怎樣選擇最合理的一種以達(dá)到最優(yōu)目標(biāo)。 1 最優(yōu)化問題的數(shù)學(xué)模型與基本概念 數(shù)學(xué)模型就是對(duì)現(xiàn)實(shí)事物或問題的數(shù)學(xué)抽象或描述。 建立數(shù)學(xué)模型時(shí)要盡可能簡單，而且要能完整地描述所研究的系統(tǒng)，具體建立怎樣的數(shù)學(xué)模型需要豐富的經(jīng)驗(yàn)和熟練的技巧。即使在建立了問題的數(shù)學(xué)模型之后，通常也必須對(duì)模型進(jìn)行必要的數(shù)學(xué)簡化以便于分析、計(jì)算。 建立最優(yōu)化問題數(shù)學(xué)模型的三要素： （1）決策變量和參數(shù)。 決策變量是由數(shù)學(xué)模型

2、的解確定的未知數(shù)。參數(shù)表示系統(tǒng)的控制變量，有確定性的也有隨機(jī)性的。 （2）約束或限制條件。 由于現(xiàn)實(shí)系統(tǒng)的客觀物質(zhì)條件限制，模型必須包括把決策變量限制在它們可行值之內(nèi)的約束條件，而這通常是用約束的數(shù)學(xué)函數(shù)形式來表示的。 （3）目標(biāo)函數(shù)。 這是作為系統(tǒng)決策變量的一個(gè)數(shù)學(xué)函數(shù)來衡量系統(tǒng)的效率，即系統(tǒng)追求的目標(biāo)。 解：決定圓柱體表面積大小有兩個(gè)決策變量：圓柱體底面半徑r、高h(yuǎn)。 問題的約束條件是所鑄圓柱體重量與球重相等。即 例1.把半徑為1的實(shí)心金屬球熔化后，鑄成一個(gè)實(shí)心圓柱體，問圓柱體取什么尺寸才能使它的表面積最??？則得數(shù)學(xué)模型： s.t. Subject to. 問題目標(biāo)是圓柱體表面積最小。即

3、min 即 即 此時(shí)圓柱體的表面積為 分別對(duì)r.h.求偏導(dǎo)數(shù),并令其等于零.有:利用在高等數(shù)學(xué)中所學(xué)的Lagrange乘子法可求解本問題 例2.多參數(shù)曲線擬合問題 已知兩個(gè)物理量x和y之間的依賴關(guān)系為: 其中 和 待定參數(shù),為確定這些參數(shù),對(duì)x.y測得m個(gè)實(shí)驗(yàn)點(diǎn):試將確定參數(shù)的問題表示成最優(yōu)化問題.解:很顯然對(duì)參數(shù) 和 任意給定的一組數(shù)值,就由上式確定了 y關(guān)于x的一個(gè)函數(shù)關(guān)系式,在幾何上它對(duì)應(yīng)一條曲線,這條曲線不一定通過那m個(gè)測量點(diǎn),而要產(chǎn)生“偏差”.將測量點(diǎn)沿垂線方向到曲線的距離的平方和作為這種“偏差”的度量.即顯然偏差S越小,曲線就擬合得越好,說明參數(shù)值就選擇得越好，從而我們的問題就轉(zhuǎn)化

4、為5維無約束最優(yōu)化問題。即： 例3.（混合飼料配合）以最低成本確定滿足動(dòng)物所需營養(yǎng)的最優(yōu)混合飼料。下面舉一個(gè)簡化了的例子予以說明。 設(shè)每天需要混合飼料的批量為100磅，這份飼料必須含：至少0.8%而不超過1.2%的鈣;至少22%的蛋白質(zhì);至多5%的粗纖維。假定主要配料包括石灰石、谷物、大豆粉。這些配料的主要營養(yǎng)配料每磅配料中的營養(yǎng)含量鈣蛋白質(zhì)纖維每磅成本（元）石灰石谷物大豆粉0.380 0.00 0.000.001 0.09 0.020.002 0.50 0.08 0.0164 0.0463 0.1250解:根據(jù)前面介紹的建模要素得出此問題的數(shù)學(xué)模型如下:設(shè) 是生產(chǎn)100磅混合飼料所須的石灰石

5、、谷物、大豆粉的量（磅）。成分為：例4：兩桿桁架的最優(yōu)設(shè)計(jì)問題。由兩根空心圓桿組成對(duì)稱的兩桿桁架，其頂點(diǎn)承受負(fù)載為2p，兩支座之間的水平距離為2L，圓桿的壁厚為B，桿的比重為，彈性模量為E，屈曲強(qiáng)度為。求在桁架不被破壞的情況下使桁架重量最輕的桁架高度h及圓桿平均直徑d。 受力分析圖圓桿截面圖桁桿示意圖解：桁桿的截面積為 ：桁桿的總重量為：負(fù)載2p在每個(gè)桿上的分力為：于是桿截面的應(yīng)力為： 此應(yīng)力要求小于材料的屈曲極限，即 圓桿中應(yīng)力小于等于壓桿穩(wěn)定的臨界應(yīng)力。由材料力學(xué)知：壓桿穩(wěn)定的臨界應(yīng)力為由此得穩(wěn)定約束： 另外還要考慮到設(shè)計(jì)變量d和h有界。 從而得到兩桿桁架最優(yōu)設(shè)計(jì)問題的數(shù)學(xué)模型： 例5 （

6、運(yùn)輸問題） 設(shè)有位于不同城市的m個(gè)電視機(jī)廠A1，A2，Am，其產(chǎn)量分別為a1，a2，am（臺(tái)），其產(chǎn)品供應(yīng)n個(gè)城市B1，B2，Bn。每個(gè)城市的需要量分別為b1，b2，bn（臺(tái)）。假定產(chǎn)需平衡，即=miia1=niib1=已知從Ai到Bj的運(yùn)費(fèi)單價(jià)為cij（元/臺(tái)）（i=1,2, m；j=1,2, n）。問由每個(gè)廠到每個(gè)城市的運(yùn)輸量各為多少時(shí)，即既能保證需要量，又能使總運(yùn)費(fèi)最少？ 解 設(shè)由Ai到Bj的運(yùn)輸量為xij（臺(tái)）（i=1,2, m；j=1,2, n），則要求總運(yùn)費(fèi) 達(dá)到最小，其中要滿足的約束條件為： =ai， i=1,2, m； =bj， j=1,2, n=minjijijxc11=nj

7、ijx1=miijx1綜上，可把所得到的線性規(guī)劃問題記為=,2,1;,2,1,0,2,1,2,1,.,min1,111mjnixnjbxmiaxtsxcijmijijnjiijminjijij例6、選址問題A1A3B2B4B3B1A2Ai: 可建倉庫地點(diǎn)，容量ai ,投資費(fèi)用bi ，建2個(gè)Bj: 商店，需求dj ( j=14 )Cij: 倉庫 i 到商店 j 的單位 運(yùn)費(fèi)問：選擇適當(dāng)?shù)攸c(diǎn)建倉庫，在滿足商店需求條件下，總費(fèi)用最小。解：設(shè)xi ( i=1,2,3)為是否在 Ai 建倉庫 yij ( i=1,2,3, j=14)由 i倉庫向 j商店運(yùn)貨量y11 + y21 = d1y12 + y22

8、 + y32 = d2y23+ y33 = d3y14 + y24 + y34 = d4x1 + x2 + x3= 2y11 + y12 + y14 a1x1y21 + y22 + y23 + y24a2x2y32 + y33 + y34 a3x3xi 為01， yij 0混合整數(shù)規(guī)劃A1A3B2B4B3B1A2例7：某市場營銷調(diào)查指派問題市場營銷調(diào)查公司有3個(gè)新客戶需要進(jìn)行市場調(diào)查，目前正好有3個(gè)人沒有其他工作，由于他們的對(duì)不同市場的經(jīng)驗(yàn)和能力不同，估計(jì)他們完成不同任務(wù)所需時(shí)間如下表。公司面臨的問題是如何給每個(gè)客戶指派一個(gè)項(xiàng)目主管（代理商），使他們完成市場調(diào)查的時(shí)間最短。預(yù)計(jì)完成時(shí)間 客戶項(xiàng)

9、目主管1231231096151814953 設(shè)xij=1表示指派主管i完成第j項(xiàng)市場調(diào)查，否則xij=0則問題的數(shù)學(xué)模型為：min f= 10 x11+15x12+9x13+9x21+18x22+5x23+6x31+14x32+3x33 x11+x12+x13 = 1 x21+x22+x23 = 1 x31+x32+x33 = 1 x11+x21+x31 = 1 x12+x22+x32 = 1 x13+x23+x33 = 1 xij0，i=1，2，3；j=1，2，3指派問題（Assignment problem） 指派問題是01整數(shù)規(guī)劃問題。在實(shí)踐中經(jīng)常會(huì)遇到：有m項(xiàng)任務(wù)要m個(gè)人去完成（每人

10、只完成一項(xiàng)工作），在分配過程中要充分考慮各人的知識(shí)、能力、經(jīng)驗(yàn)等，應(yīng)如何分配才能使工作效率最高或消耗的資源最少？這類問題就屬于指派問題。引入01變量xij例8（非線性方程組的求解） 解非線性方程組是相當(dāng)困難的一類問題，由于最優(yōu)化方法的發(fā)展，對(duì)解非線性方程組提供了一種有力的手段。解非線性方程組=0),(0),(0),(21212211nnnnxxxfxxxfxxxf在方程組有解的情況下等價(jià)于下列函數(shù)的最小值點(diǎn)：),(),(min211221nniinxxxfxxxF= 目標(biāo)函數(shù)不等式約束等式約束 稱滿足所有約束條件的向量 為可行解，或可行點(diǎn)，或容許解，全體可行解的集合稱為可行集或容許集，記為 。 若 是連續(xù)函數(shù)，則 是閉集。最優(yōu)化問題的一般數(shù)學(xué)模型 在可行集中找一點(diǎn) ，使目標(biāo)函數(shù) 在該點(diǎn)取最小值，即滿足： 的過程即為最優(yōu)化的求解過程。 稱為問題的最優(yōu)點(diǎn)或最優(yōu)解， 稱為最優(yōu)值。 定義1：整體（全局）最優(yōu)解：若 ，對(duì)于一切 ，恒有 則稱 是最優(yōu)化問題的整體最優(yōu)解。定義2：局部最優(yōu)解：若 ，存在某鄰域 ，使得對(duì)于一切 ，恒有