離散動態(tài)規(guī)劃與Bellman代數(shù)作者簡介

秦裕瑗，1924年生于揚州。1950年畢業(yè)于上海大同大學數(shù)學系。先后任教子同濟大學、武漢測繪學院和武漢科技大學。主要講授高等數(shù)學、泛函分析、動態(tài)規(guī)劃。組合最優(yōu)化和運籌學等十多門課程。 1882年被評為教授。1992年起享受國務院政府特殊津貼。曾任華中工學院等三所大學的兼職教授。先后應邀在美國、加拿大、聯(lián)邦德國、民主德國、波蘭、捷克斯洛伐克和奧地利等7個國家的14所大學進行學術演講或?qū)W術交流。1989年9月-1990年2月。經(jīng)奧地利國家科學部批準。任Graz技術大學客座教授，授課一學期，講授自己的英文專著。1989年獲湖北省人事廳與省教育委員會授予的湖北省優(yōu)秀教師獎，1990年列入世界數(shù)學家名冊，1992年獲國務院頒發(fā)的“作出突出貢獻”政府特殊津貼證書，1993年獲國家教委科技進步三等獎，1995年獲國家測繪局授予的科技貢獻二等獎（第二作者）。發(fā)表學術論文40余篇。出版的著作有《嘉量原理——有限型多階段決策問題的一個新處理》、OptimunPath Problems in Networks、《運籌學簡明教程》（與秦明復合編、第二版為普通高等教育“十一五”國家級規(guī)劃教材）、《一元代數(shù)方程縱橫談》；譯著有[德]Roth·高等數(shù)學。第二卷（與鄧立生合作）、第三卷、第四卷三個分冊，[德]W·戴根·K·包美爾·微積分題解。上、下卷；另有一本《最優(yōu)路問題——極優(yōu)代數(shù)方法》已送審。

第一部分 基礎理論

第1章 離散動態(tài)規(guī)劃的基本公理系統(tǒng)與Bellman代數(shù)

1.1 策略優(yōu)化問題及最優(yōu)化原理

1.1.1 兩個例題

1.1.2　最優(yōu)化原理

1.2 對最優(yōu)化原理的討論

1.2.1 策略的代數(shù)結(jié)構(gòu)

1.2.2 策略優(yōu)劣的比較

1.2.3 Bellman公理

1.3 動態(tài)規(guī)劃的基本公理系統(tǒng)與求解公式

1.3.1 Bellman半環(huán)

1.3.2 基本公理系統(tǒng)

1.3.3 求解公式

1.4 幾個重要的代數(shù)系統(tǒng)

1.4.1 Bellman半環(huán)的基本性質(zhì)

1.4.2　強優(yōu)選準域

1.4.3 Bellman代數(shù)

1.5 實數(shù)集上一些代數(shù)系統(tǒng)舉例

1.5.1 實數(shù)集上的Bellman半環(huán)的例

1.5.2 實數(shù)集上的強優(yōu)選準域與Bellman代數(shù)的例

1.5.3 幾個非強優(yōu)選準域的例子

1.6 四類最優(yōu)策略

1.7 圖論模型及三個基本問題

1.7.1 決策與策略的圖形表示

1.7：2 動態(tài)規(guī)劃問題的分類 三個基本問題

1.8 關于Bellman代數(shù)的注記

參考文獻

第2章 決策數(shù)確定型問題

2.1 基本概念

2.2 遞推公式Ⅰ

2.3 問題Ⅰ的（?。┚仃嚹Ｐ?

2.4 問題Ⅰ的圖論模型

2.4.1 圖論模型

2.4.2 數(shù)字例

2.5 賦值多階段有向圖中求解所有最優(yōu)路及其長度的程序

2.6 資源分配問題

2.6.1 問題的一般討論

2.6.2 數(shù)字例 摹矩陣法

2.6.3摹多項式法

2.7　計數(shù)Bellman半環(huán)

參考文獻

第3章 決策數(shù)簡單不確定型問題

3.1 引言

3.2 最優(yōu)化原理和遞推公式Ⅱ

3.3 問題Ⅱ的兩種模型

3.3.1　矩陣模型

3.3.2 圖論模型

3.4　兩種計算公式

3.4.1 逆序遞推公式與計算表

3.4.2 順序遞推公式與計算表

3.4.3 數(shù)字例

3.5 基本庫存問題

3.5.1 一般問題的討論

3.5.2 數(shù)字例

3.6 基本設備更新問題 數(shù)字例

3.7 矩陣連乘式最優(yōu)結(jié)合方式的算法

3.8 賦值上三角有向圖中求解所有最短路及其長度的程序

3.9 工程計劃的統(tǒng)籌問題

參考文獻

第4章 決策數(shù)不確定型問題

4.1 圖論模型

4.2 網(wǎng)絡的基本代數(shù)性質(zhì)

4.2.1 基本性質(zhì)

……

第二部分　理論推廣

第5章　基本公理系統(tǒng)的第一類推廣

第6章　基本公理系統(tǒng)的第二類推廣

第三部分　應用問題

第7章　匹配優(yōu)化問題

第8章　數(shù)學物理方法中的應用

附錄　組合圖論與抽象代數(shù)的基本知識

參考文獻

本書建立了一個與最優(yōu)化原理足夠貼近的代數(shù)系統(tǒng)。叫做Bellman半環(huán)，從而建立了離散動態(tài)規(guī)劃的基本公理系統(tǒng)，證明了Bellman代數(shù)（包括極大代數(shù)和極小代數(shù)）是最優(yōu)化原理成立的一個充分條件。

全書分三個部分共8章，以原理為基礎，以Bellman代數(shù)為工具，討論離散動態(tài)規(guī)劃的基礎理論、算法和應用?；竟硐到y(tǒng)能夠推廣為一般公理系統(tǒng)，用以討論k階優(yōu)化解問題、多目標非劣解問題，并建立匹配優(yōu)化原理，得到了關于路和匹配的多種優(yōu)化問題的求解公式。本書表明，離散動態(tài)規(guī)劃是一門既具有公理化基礎又具有代數(shù)工具的、專門討論決策優(yōu)化學問的應用數(shù)學分支。

本書可作為應用數(shù)學、管理科學等專業(yè)研究生學習教材和專業(yè)人員的參考書籍。

本項目以串并混合型離散制造系統(tǒng)為研究對象，主要開展了變動作業(yè)計劃約束下系統(tǒng)整體預防性維護活動的動態(tài)調(diào)度研究。首先，通過分析離散制造系統(tǒng)系統(tǒng)層維護調(diào)度的參數(shù)構(gòu)成、基本輸入和狀態(tài)轉(zhuǎn)移等需求，研究建立了基于役齡遞減和故障率遞增的設備層混合式修復非新規(guī)則，實現(xiàn)了設備層的維護調(diào)度建模。然后，基于組成本理論和動態(tài)規(guī)劃方法，分析了變動作業(yè)計劃對組成本及動態(tài)調(diào)度過程的約束機制，建立了機會維護下離散制造系統(tǒng)整體的動態(tài)維護調(diào)度策略。之后，結(jié)合設備層的維護調(diào)度模型，研究了不同配置型式下設備提前或延期維護的節(jié)余成本的計算方法，完成了系統(tǒng)層維護調(diào)度目標函數(shù)的構(gòu)建，實現(xiàn)了系統(tǒng)層維護調(diào)度策略的分階段的動態(tài)優(yōu)化。最后，分別以八設備串行離散制造系統(tǒng)和三階段四設備串并混合型離散制造系統(tǒng)為仿真測試平臺，通過仿真分析展示了本研究維護調(diào)度策略的具體決策過程，同時通過與其他兩種維護調(diào)度策略，即所有作業(yè)區(qū)間設備都提前維護的策略和所有作業(yè)區(qū)間設備都延期維護的策略進行對比分析，進一步驗證了本研究維護調(diào)度策略和優(yōu)化模型的有效性。 本研究的動態(tài)維護調(diào)度理論融入了變動作業(yè)計劃約束，不僅對提高離散制造系統(tǒng)的維護調(diào)度水平具有現(xiàn)實意義，而且促進了維護調(diào)度和作業(yè)調(diào)度兩個研究領域的交叉與耦合。在本項目預定研究計劃的基礎上，項目組還進行了拓展研究，開展了多種維護技術下的多設備離散制造系統(tǒng)的維護調(diào)度研究以及考慮產(chǎn)線緩沖區(qū)條件下的多設備系統(tǒng)的維護調(diào)度研究，并取得了一系列的研究成果。 通過項目組研究成員3年來的共同努力，項目組最終完成了項目研究報告一份，發(fā)表和錄用期刊論文16篇，其中SCI/EI論文12篇，包括《Reliability Engineering and System Saftety》、《European Journal of Operational Research》、《Computers and Industry Engineering》等國際知名SCI期刊論文3篇。此外，執(zhí)行期間項目組還組織或參與了制造系統(tǒng)維護相關的學術會議2次，培養(yǎng)博碩士生6名。 2100433B

以串并混合型離散制造系統(tǒng)為研究對象，開展變動作業(yè)計劃約束下系統(tǒng)整體預防性維護活動的動態(tài)調(diào)度研究。首先，通過分析系統(tǒng)層維護調(diào)度的參數(shù)構(gòu)成、基本輸入和狀態(tài)轉(zhuǎn)移等需求，研究建立基于役齡遞減和故障率遞增的混合式修復非新規(guī)則，實現(xiàn)設備層的維護調(diào)度建模。然后，基于組成本理論和動態(tài)規(guī)劃方法，分析變動作業(yè)計劃對組成本及動態(tài)調(diào)度過程的約束機制，建立機會維護下系統(tǒng)整體的動態(tài)維護調(diào)度策略。之后，結(jié)合設備層的維護調(diào)度模型，研究不同配置下設備提前或延期維護的節(jié)余成本的計算方法，完成系統(tǒng)層維護調(diào)度目標函數(shù)的構(gòu)建，實現(xiàn)系統(tǒng)層維護調(diào)度策略的分階段的動態(tài)優(yōu)化。最后，以三階段四設備組成的離散機械制造系統(tǒng)為測試床，通過仿真運行和對比分析，驗證本研究維護調(diào)度策略和優(yōu)化模型的有效性。本研究的動態(tài)維護調(diào)度理論融入變動作業(yè)計劃約束，不僅對提高離散制造系統(tǒng)的維護調(diào)度水平具有現(xiàn)實意義，而且將促進維護調(diào)度和作業(yè)調(diào)度兩個研究領域的交叉與耦合。

動態(tài)規(guī)劃就是解決多階段決策最優(yōu)化問題的一種思想方法。

樹形動態(tài)規(guī)劃階段

將所給問題的過程，按時間或空間特征分解成若干相互聯(lián)系的階段，以便按次序去求每階段的解。

樹形動態(tài)規(guī)劃狀態(tài)

各階段開始時的客觀條件叫做狀態(tài)。

樹形動態(tài)規(guī)劃決策

當各段的狀態(tài)取定以后，就可以做出不同的決定，從而確定下一階段的狀態(tài)，這種決定稱為決策。

樹形動態(tài)規(guī)劃策略

由開始到終點的全過程中，由每段決策組成的決策序列稱為全過程策略，簡稱策略。

樹形動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程

前一階段的終點就是后一階段的起點，前一階段的決策選擇導出了后一階段的狀態(tài)，這種關系描述了由k階段到k 1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。