包裝物流系統(tǒng)優(yōu)化方法(已修改)
2025-01-08 23:15 本頁面
【正文】 專 業(yè)：包裝工程 Email: 包裝物流技術(shù) 第 5章 包裝物流系統(tǒng)優(yōu)化方法 概述 多段圖問題 節(jié)約里程法 背包問題（貨物配載問題） 0/1背包問題 矩陣連乘積問題 凸多邊形最優(yōu)三角剖分 ? 物流系統(tǒng)規(guī)劃所關(guān)注的問題是如何合理、有效地利用或配置各種資源（勞動(dòng)力、材料、設(shè)備、資金），使實(shí)現(xiàn)預(yù)定目標(biāo)所需的費(fèi)用最?。ɑ蛸Y源最少），或者所獲得的收益最大。 ? 物流系統(tǒng)的規(guī)劃一般都可以用 優(yōu)化模型 來表達(dá)。其基本思想是在滿足一定的約束條件下，使預(yù)定的目標(biāo)值達(dá)到最優(yōu)。 ? 物流系統(tǒng)規(guī)劃的數(shù)學(xué)基礎(chǔ)主要是運(yùn)籌學(xué)理論，常用的方法包括線性規(guī)劃、整數(shù)規(guī)劃、動(dòng)態(tài)規(guī)劃等。 概述 多階段決策問題 ：求解的問題可以劃分為一系列相互聯(lián)系的階段，在每個(gè)階段都需要做出決策，且一個(gè)階段決策的選擇會(huì)影響下一個(gè)階段的決策，從而影響整個(gè)過程的活動(dòng)路線，求解的目標(biāo)是選擇各個(gè)階段的決策是整個(gè)過程達(dá)到最優(yōu)。 1 2 k + 1 Nx0x1x2xkxk + 1xN 1xNu0u1ukuN 1 如圖所示，對(duì)于中間的任意一段，例如 第 k+1段 作出相應(yīng)的“決策” (或控制 )uk后，才能確定該段 輸入狀態(tài) 與 輸出狀態(tài) 間的關(guān)系，即從 xk變化到 xk+1的狀態(tài)轉(zhuǎn)移規(guī)律。在選擇好每一段的“決策” (或控制 ) uk以后，那么整個(gè)過程的狀態(tài)轉(zhuǎn)移規(guī)律從 x0經(jīng) xk一直到 xN也就被完全確定。全部“決策”的總體，稱為“策略”。 Dynamic Programming 動(dòng)態(tài)規(guī)劃 動(dòng)態(tài)最優(yōu)的核心是 最優(yōu)性原理 。它首先將一個(gè)多階段決策問題轉(zhuǎn)化為一系列單階段決策問題，然后從最后一段狀態(tài)開始逆向遞推到初始段狀態(tài)為止的一套求解最優(yōu)策略的完整方法。 最優(yōu)性原理： 一個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)，即無論其初始狀態(tài)及其初始決策如何，其以后諸決策對(duì)以第一個(gè)決策所形成的狀態(tài)作為初始狀態(tài)而言，必須構(gòu)成最優(yōu)策略。 B A C I I’ II II’ 動(dòng)態(tài)規(guī)劃算法的依據(jù)是最優(yōu)化原理 (最優(yōu)子結(jié)構(gòu)性質(zhì) ) 一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去的狀態(tài)和決策如何，余下的決策必須相對(duì)于前一決策所產(chǎn)生的狀態(tài)構(gòu)成最優(yōu)決策序列。簡(jiǎn)言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的，問題的最優(yōu)解可以通過其子問題的最優(yōu)解構(gòu)成。 無后效性： 在多段決策過程中，每一段 (如第 k+1段 )的輸出狀態(tài) (xk+1)都僅僅與該段的決策 (uk)及該段的初始狀態(tài) (xk)有關(guān)；而與其前面各段的決策及狀態(tài)的轉(zhuǎn)移規(guī)律無關(guān)。 （ 1）劃分階段 ： 按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。 （ 2）選擇狀態(tài) ： 將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來。 （ 3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程 ： 狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。 （ 4）寫出規(guī)劃方程（包括邊界條件） ： 動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。 動(dòng)態(tài)規(guī)劃算法的基本步驟 常見的動(dòng)態(tài)規(guī)劃問題 （ 1）多段圖問題（配送路徑優(yōu)化問題） （ 2）節(jié)約里程問題（配送路徑優(yōu)化問題） （ 3）背包問題（貨物配裝、裝箱問題） （ 4）矩陣連乘積問題 （ 5）數(shù)字三角形問題 （ 6）最長(zhǎng)不下降子序列 （ 7）最長(zhǎng)公共子序列 （ 8）最大子段和 （ 9）多邊形游戲 （ 10）資源分配問題 ………. 多段圖問題 1 2 3 4 5 8 7 6 11 10 9 12 s t 9 7 3 2 4 2 2 7 1 11 11 8 6 5 4 3 5 6 5 2 4 V1 V2 V3 V4 V5 ? 多段圖 G＝ (V, E)是 — 個(gè)有向圖。 ? 它具有如下特性： – 圖中的結(jié)點(diǎn)被劃分成 k≥2 個(gè)不相交的集合 Vi,1≤i≤k, 其中 V1和 Vk分別只有一個(gè)結(jié)點(diǎn) s (源點(diǎn) ) 和 t (匯點(diǎn) )。 – 圖中所有的邊 u,v均具有如下性質(zhì)：若 u∈Vi ，則 v ∈V i+1 ,1≤i≤k,且每條邊 u, v均附有成本 c(u, v)。 – 從 s到 t的一條路徑成本是這條路徑上邊的成本和。 – 多段圖問題 (multistage graph problem)是求由 s到 t的最小成本路徑。 ? 證明最優(yōu)化原理對(duì)多段圖成立： – 假設(shè) s,v2,v3,…,v k1,t是一條由 s到 t的最短路徑 – 再假設(shè)從源點(diǎn) s開始，已作出了到結(jié)點(diǎn) v2的決策，因此 v2就是初始決策所產(chǎn)生的狀態(tài) – 如果把 v2看成是原問題的一個(gè)子問題的初始狀態(tài)，解決這個(gè)子問題就是找出一條由 v2到 t的最短路徑 – 這條最短路徑顯然是 v2,v3,…,v k1,t – 如果不是，設(shè) v2,q3,…,q k1,t由 v2到 t的一條更短路徑，則s,v2,q3,…,q k1,t是一條比路徑 s,v2,v3,…,v k1,t更短的由 s到 t的路徑。這與假設(shè)矛盾，因此最優(yōu)性原理成立。 （一）多段圖問題的最優(yōu)化原理證明 （二）求解多段圖問題的動(dòng)態(tài)規(guī)劃算法 （ 1）遞推公式法（多段圖 向前處理 的算法） 設(shè) P(i, j)是一條從 Vi中的節(jié)點(diǎn) j到匯點(diǎn) t的最小成本路徑 ， COST(i,j)表示這條路徑的成本，根據(jù) 向前處理 方法有： )},1(),({m in)ji,(,1liCOS TljcCOS TEljVl i??????? ?邊的成本 例子中 5段圖的實(shí)現(xiàn)計(jì)算步驟： ?COST(4,9)=4 ?COST(4,10)=2 ?COST(4,11)=5 1 2 3 4 5 8 7 6 11 10 9 12 s
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1