mm05-規(guī)劃模型.ppt

1、數(shù)學(xué)建模,規(guī)劃模型,1,數(shù) 學(xué) 建 模,從自然走向理性之路,數(shù)學(xué)建模,2,規(guī)劃模型,第五講 規(guī)劃模型,【主要內(nèi)容】 介紹線性規(guī)劃模型、非線性規(guī)劃模型及動態(tài)規(guī)劃模型 【主要目的】 了解規(guī)劃問題的建模與求解，重點在模型的建立與結(jié)果的分析,數(shù)學(xué)建模,3,規(guī)劃模型,線性規(guī)劃模型(Linear Programming) 建立模型 線性規(guī)劃問題：求多變量線性函數(shù)在線性約束條件下的 最優(yōu)值 線性規(guī)劃問題的一般形式：,數(shù)學(xué)建模,4,規(guī)劃模型,線性規(guī)劃問題的標(biāo)準(zhǔn)形式：,數(shù)學(xué)建模,5,規(guī)劃模型,說明 任意線性規(guī)劃問題可化為標(biāo)準(zhǔn)形式。具體方式如下： 1. 目標(biāo)函數(shù)標(biāo)準(zhǔn)化 ： 2. 約束條件標(biāo)準(zhǔn)化 ： 假設(shè)約束條件中

2、有不等式約束 或 引入新變量 （稱為松弛變量），則以上兩式等價于以下兩式：,數(shù)學(xué)建模,6,規(guī)劃模型,3. 自由變量標(biāo)準(zhǔn)化 若變量 xj 無約束，可引入兩個新變量 ，令 故以下我們只考慮標(biāo)準(zhǔn)形式。,數(shù)學(xué)建模,7,規(guī)劃模型,矩陣形式表示 一般要求，,數(shù)學(xué)建模,8,規(guī)劃模型,例1 某工廠制造A,B兩種產(chǎn)品，制造產(chǎn)品A每噸需用煤9噸，用電4千瓦，3個工作日；制造產(chǎn)品B每噸需用煤5噸，用電5千瓦，10個工作日。已知制造產(chǎn)品A和B每噸分別獲利7000元和12000元?，F(xiàn)該廠只有煤360噸，電200千瓦，工作日300個可以利用，問A,B兩種產(chǎn)品各應(yīng)生產(chǎn)多少噸才能獲利最大？ 解 x1, x2 分別表示A, B

3、兩種產(chǎn)品的計劃生產(chǎn)數(shù)（單位：噸），f 表示利潤（單位：千元），則 f = 7 x1 + 12 x2,數(shù)學(xué)建模,9,規(guī)劃模型,耗煤量為 9 x1 + 5 x2 耗電量為 4 x1 + 5 x2 耗工作日 3x1 + 10 x2 于是得到線性規(guī)劃模型為：,數(shù)學(xué)建模,10,規(guī)劃模型,例2 設(shè)某工廠有甲、乙、丙、丁四個車間，生產(chǎn)A、B、C、D、E、F六種產(chǎn)品，根據(jù)機(jī)車性能和以前的生產(chǎn)情況，得知生產(chǎn)每單位產(chǎn)品所需各車間的工作時數(shù)、每個車間在一個季度工作時數(shù)的上限以及產(chǎn)品的價格，如下表所示。問：每種產(chǎn)品每季度各應(yīng)生產(chǎn)多少，才能使這個工廠每季度生產(chǎn)總值達(dá)到最大？,數(shù)學(xué)建模,11,規(guī)劃模型,數(shù)學(xué)建模,12,規(guī)

4、劃模型,解 以 x1 x6 分別表示每季度生產(chǎn)產(chǎn)品A、B、C、D、E、F的單位數(shù)，于是它們需滿足 目標(biāo)函數(shù)為,數(shù)學(xué)建模,13,規(guī)劃模型,引入松弛變量x7 x10 ，化成標(biāo)準(zhǔn)型,數(shù)學(xué)建模,14,規(guī)劃模型,線性規(guī)劃問題求解 1. 可行域幾何特征 滿足約束條件的解稱為可行解，所有可行解構(gòu)成的集合稱為可行域，滿足目標(biāo)式的可行解稱為最優(yōu)解。 線性規(guī)劃問題的可行域是一個凸多邊形； 線性規(guī)劃問題如果存在最優(yōu)解，則最優(yōu)解必在可行域的頂點處達(dá)到。,數(shù)學(xué)建模,15,規(guī)劃模型,2. 單純形法 基本思想：從可行域的一個頂點（基本可行解）出發(fā)，轉(zhuǎn)換到另一個頂點，并且使目標(biāo)函數(shù)值逐步減小，有限步后可得到最優(yōu)解。,數(shù)學(xué)建模

5、,16,規(guī)劃模型,整數(shù)規(guī)劃 自變量取整數(shù)的線性規(guī)劃稱為整數(shù)（線性）規(guī)劃。 割平面法，分支定界法,數(shù)學(xué)建模,17,規(guī)劃模型,01規(guī)劃 例3 （MCM-88B）要把七 種不同規(guī)格的包裝箱裝到兩輛鐵 路平板車上去，各包裝箱寬、高 均相同，但厚度（厘米）與重量 （公斤）不同。下表給出各包裝箱的厚度、重量及數(shù)量。 每輛平板車有10.2米長的地方可用來裝包裝箱，載重40噸。由 于當(dāng)?shù)刎涍\限制，對C5 , C6 , C7 類包裝箱總數(shù)有一個特別限制：該 類箱子總厚度不超過302.7（厘米）。試把包裝箱裝到平板車上去使 得浪費空間最小。,數(shù)學(xué)建模,18,規(guī)劃模型,1. 問題分析 題中所有的包裝箱共重89噸，而

6、兩輛平板車只能載80噸，因此不能都裝下，問題是裝哪些箱子，使剩余空間最小。,數(shù)學(xué)建模,19,規(guī)劃模型,2. 模型建立 設(shè) xij = 第i 輛車裝 Cj 類箱子的個數(shù)， i =1,2 j =1, ,7 自然約束： 箱數(shù)約束： 重量約束： 厚度約束： 特別約束：,數(shù)學(xué)建模,20,規(guī)劃模型,目標(biāo)函數(shù) 例4 分工問題 某車間有四項工作需要完成，現(xiàn)已找到四個人做這些工作，經(jīng)過試用，得到這四個人做每一項工作的相對生產(chǎn)率指數(shù)，列表如下 。 假定每個人只能分派一項工作，并希望分派后總的生產(chǎn)率最高，應(yīng)如何分派工作？,數(shù)學(xué)建模,21,規(guī)劃模型,令,數(shù)學(xué)建模,22,規(guī)劃模型,每個人做一項工作 每項工作有一人做 目

7、標(biāo)函數(shù),數(shù)學(xué)建模,23,規(guī)劃模型,非線性規(guī)劃模型 (Nonlinear Programming) 例5 飛行管理問題（CUMCM95A) 在高空中一個邊長為160公里的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行。區(qū)域內(nèi)每架飛機(jī)的位置和速度均由計算機(jī)記錄其數(shù)據(jù)。當(dāng)一架欲進(jìn)入該區(qū)域的飛機(jī)到達(dá)區(qū)域邊緣時，要立即計算并判斷其是否會與區(qū)域內(nèi)的飛機(jī)碰撞。如果會碰撞，則要計算如何調(diào)整各架（包括新進(jìn)入的）飛機(jī)飛行的方向角，以避免碰撞?，F(xiàn)假定條件如下：,數(shù)學(xué)建模,24,規(guī)劃模型,不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于8公里； 每架飛機(jī)飛行方向角調(diào)整的幅度不應(yīng)超過30度； 所有飛機(jī)飛行速度均為800公里/小時； 欲進(jìn)

8、入飛機(jī)在到達(dá)區(qū)域邊緣時，與區(qū)域內(nèi)飛機(jī)的距離應(yīng)在60公里以上； 最多需考慮6架飛機(jī)； 不必考慮飛機(jī)離開此區(qū)域后的狀況。 請你建立數(shù)學(xué)模型，對以下數(shù)據(jù)進(jìn)行計算（方向角誤差不超過0.01度），要求飛機(jī)飛行方向角調(diào)整的幅度盡量小。（數(shù)據(jù)略）,數(shù)學(xué)建模,25,規(guī)劃模型,模型建立與求解 模型一：設(shè)第 i 架飛機(jī)在調(diào)整時的 方向角為i ,調(diào)整角度為 i （ i 1，2，6）。設(shè)任意兩架飛機(jī)在區(qū)域內(nèi)的最短距離為dij(i , j )，那么問題的非線性規(guī)劃模型為,數(shù)學(xué)建模,26,規(guī)劃模型,解法：能量梯度法、懲罰函數(shù)法、序列無約束最小 化方法、逐步逼近搜索法等 模型二： 模型三：,數(shù)學(xué)建模,27,規(guī)劃模型,利用相

9、對運動的方法得到以上模型，再簡化為線性規(guī)劃問題求解。,數(shù)學(xué)建模,28,規(guī)劃模型,動態(tài)規(guī)劃模型(Dynamic Programming) 動態(tài)規(guī)劃是解決多階段決策過程最優(yōu)化的一種方法。多階段決策問題，是指一個問題可以分為若干個階段， 每一階段需要做出決策，而一個階段的決策，常常會影響下一個階段的決策。要在各個階段決定一個最優(yōu)決策， 使整個系統(tǒng)達(dá)到最佳的效果。 通過以下一個典型例子，說明如何建立動態(tài)規(guī)劃模型。,數(shù)學(xué)建模,29,規(guī)劃模型,例6 最短路線問題,數(shù)學(xué)建模,30,規(guī)劃模型,先引入幾個概念 狀態(tài)每一階段的起點位置 決策由一個狀態(tài)變到另一個狀態(tài)的選擇 xk 第 k 階段的狀態(tài)，稱為狀態(tài)變量 u

10、k（ xk ）從 xk 出發(fā)所作出的決策，稱為決策變量 Dk（ xk ）第 k 階段中所有允許決策的集合 狀態(tài)轉(zhuǎn)移方程 xk+1 = Tk ( xk , uk ) dk ( xk , uk ）從狀態(tài) xk 出發(fā)，采取決策uk ，轉(zhuǎn)移到狀態(tài) xk+1 的效益 fk（ xk ）從狀態(tài) xk 出發(fā)到終點的最優(yōu)效益,數(shù)學(xué)建模,31,規(guī)劃模型,最短路問題的動態(tài)規(guī)劃最優(yōu)化原理 : 假設(shè)一條最短路線經(jīng)過狀態(tài) xk ，那么，這條路線上從 xk 到終點的一段，是從 xk 出發(fā)到終點的所有路線中最短的。 逆序法（回溯法）： 從后向前逐步求出各點到終點的最佳路線，最后得到由起點到終點的最短路線。,數(shù)學(xué)建模,32,規(guī)

11、劃模型,最短路問題的動態(tài)規(guī)劃模型，歸納為下述遞推公式： 從最后一段開始，k = 4 , 有三個狀態(tài)D1 , D2 , D3 , k = 3 ，有4 個狀態(tài)Ci , i =1,2,3,4 . 每個狀態(tài)有兩個決策可選擇。分別計算各狀態(tài)出發(fā)到終點的效益 f 3 ( Ci )：,數(shù)學(xué)建模,33,規(guī)劃模型,最短路徑： 最短路徑：,數(shù)學(xué)建模,34,規(guī)劃模型,最短路徑： 最短路徑：,數(shù)學(xué)建模,35,規(guī)劃模型, k = 2 時,有兩個狀態(tài)B1 ,B2，每個狀態(tài)有3個決策可選。 最短路徑：,數(shù)學(xué)建模,36,規(guī)劃模型,最短路徑： 或者 k = 1 時， 最短路徑： 路徑長為： 14,數(shù)學(xué)建模,37,規(guī)劃模型,Bellman 動態(tài)規(guī)劃最優(yōu)化原理 整個過程的最優(yōu)策略應(yīng)具有性質(zhì)：無論過去的狀態(tài)和決策如何，對當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。,數(shù)學(xué)建模,38,規(guī)劃模型,動態(tài)規(guī)劃的特點是將問題按時間或空間特征而分成若干個階段，從而將整個決策過程轉(zhuǎn)化為多階段的決策問題。 對某些靜態(tài)決策問題可以引入時間因素，將問題轉(zhuǎn)化為多階段的決策問題，然后利用動態(tài)規(guī)劃方法求解。以上最短路問題的解決就是這樣的一個例子，以下再舉一個例子。,數(shù)學(xué)建模,39,規(guī)劃模型,資源分配問題 設(shè)有某種資源總數(shù)量為 a ，用于生產(chǎn) n 種產(chǎn)品。如果分配數(shù)量 xk 用于生產(chǎn)第 k 種產(chǎn)品，其效益為 g