運籌學第五章動態(tài)規(guī)劃(已修改)
2025-05-12 12:05 本頁面
【正文】 第五章 動態(tài)規(guī)劃 動態(tài)規(guī)劃簡介 動態(tài)規(guī)劃所解決的問題 ： 多階段問題 動態(tài)規(guī)劃的核心 。 動態(tài)規(guī)劃的應用。 動態(tài)規(guī)劃的優(yōu)缺點。 核心 : 在于將問題公式化，也可以說，動態(tài)規(guī)劃是將多階段決策問題進行公式化的一種技術。 應用 :工程、軍事和商業(yè)等領域 優(yōu)缺點 :適用范圍廣，模型算法一體化，方便編程。一方面是大量的中間計算結果要求記錄，造成對內存的較大需求；另一方面是由于沒有統(tǒng)一的標準模型，使得動態(tài)規(guī)劃的應用難度增加 。 圖 例 動態(tài)規(guī)劃的基本概念和模型 動態(tài)規(guī)劃的基本概念 下面結合實例來介紹動態(tài)規(guī)劃的基本概念： 【 例 】 如圖 ， 在處有一水庫 ， 現需從點鋪設一條管道到點 ， 弧上的數字表示與其相連的兩個地點之間所需修建的渠道長度 ， 請找出一條由到的修建線路 ， 使得所需修建的渠道長度最短 。 【 例 】 未來四個月里 ， 利用一個倉庫經銷某種商品 。 該倉庫的最大容量為 1000件 ， 每月中旬定購商品 ， 并于下月初取到訂貨 。 據估計：今后四個月這種商品的購價和售價 ， 如 表 51所 示 。 假定商品在第一個月初開始經銷時倉庫已經存有該種商品 500件 ， 每月市場不限 ， 問：應如何計劃每個月的訂購與銷售數量 ， 使這四個月的總利潤最大 (不考慮倉庫的存儲費用 )？ 表 51 今后四個月這種商品的購價和售價 月份 購價 售價 1 10 12 2 8 9 3 11 13 4 15 17 kqkpk記作： 動態(tài)規(guī)劃基本概念 記作： k()kkdsks記作： 1 ( , ( ) )k k k k ks T s d s? ?記作： 記作： ()kn kPs記作： ( , ( ))kn k kn kv s P s， ()kkfs允許決策集 ()kkDs 最優(yōu)函數 動態(tài)規(guī)劃的模型 一般地 ， 動態(tài)規(guī)劃模型包括 (1)至 (6)中所提到的諸要素 。 很顯然 ， 要建立動態(tài)規(guī)劃問題的模型 ， 一般可按以下 步驟 來進行： (1) 把問題的過程劃分為恰當的個 階段 ， 引入階段變量 ； nk(2) 正確選擇狀態(tài)變量 ，使它既能描述過程的演變，又能滿足無后效性，同時給出狀態(tài)可能集 ； kskS(3) 確定決策變量 及每個階段的允許決策集 ； ()kkds ()kkDs(6) 寫出最優(yōu)函數 。 (4) 寫出狀態(tài)轉移方程； (5) 指出階段指標及指標函數； 動態(tài)規(guī)劃的原理與求解 動態(tài)規(guī)劃的最優(yōu)化原理 下面我們先研究一下例 。 最短路線問題有一個 重要特性 ：如圖 有 ? ?111 2 11 2 2 2 1 1 2 2( ) ( )3 2 3()( ) m in ( ) m in ( , ( ) ) ( )()d A D AA B f Bf A A B f B v A d A f sA B f B??????? ? ? ??????? ?2 1 2 11 1 3 12 1 2 1 2 1 3 2( ) ( )1 2 3 2()( ) m in m in ( , ( ) ) ( )() d B D BB C f Cf B v B d B f sB C f C ????? ? ??????? ?2 2 2 22 1 3 12 2 2 2 3 2 2 2 2 2 3 2( ) ( )2 3 3 3()( ) m in ( ) m in ( , ( ) ) ( )()d B D BB C f Cf B B C f C v B d B f sB C f C??????? ? ? ??????? ?2 3 2 33 1 3 12 3 3 2 3 2 2 3 2 3 3 2( ) ( )3 3 3 3()( ) m in ( ) m in ( , ( ) ) ( )()d B D BB C f Cf B B C f C v B d B f sB C f C??????? ? ? ??????2 1 1( , ( ) )s T A d A?1 1 1 2{ , }B C B C21()DB?3 2 1 2 1( , ( ) )s T B d B?3 2 2 2 2( , ( ) )s T B d B?2 2 2 1 2 2 2 3( ) { , , }D B B C B C B C?3 2 3 2 3( , ( ) )s T B d B?2 3 3 1 3 2 3 3( ) { , , }D B B C B C B C?1 1 2 3( ) { , , }D A A B A B A B?? ?3 1 3 11 1 4 13 1 3 1 3 1 4 4( ) ( )1 2 4 2()( ) m in m in ( , ( ) ) ( )() d C D
物理相關推薦
鄂ICP備17016276號-1