運籌學動態(tài)規(guī)劃ppt課件-閱讀頁
2025-05-18 18:35本頁面
【正文】 1 | 2 | 3 k = 1， s1 = 0， c1 = 1，則 s2 = d1 1 = 0 | 1 | 2 | 3 d1 s1 [(4+10d1) 第 48頁 共 64頁 某廠生產三種產品，其重量及利潤關系表 45所示。問如何安排運輸使總利潤最大？ 產品種類 重量（噸 /件） 利潤（元 /件） 1 2 3 2 4 3 80 180 130 例 47 背包問題 表 45 第 49頁 共 64頁 方法一 正向遞歸方法 （見書 P110） 方法二 逆向遞歸方法 第 50頁 共 64頁 按裝運產品種類，問題分 3個階段 sk ： 可用于裝載第 k種產品的載重量 dk ： 裝載第 k種產品的件數(shù) ak 、 ck 分別表示單件第 k 種貨物的重量及利潤 解： 基本方程為： ??????? ??6,0)()}(m a x {)(14411ssfsfdcsf kkkkkkkkkk dass ??? 1:狀態(tài)轉移方程kkkkk dcdsv ?),(0 ≤ sk≤ 6 階段指標函數(shù) 第 51頁 共 64頁 d3 s3 c3d3 f3(s3) d*3 0 1 2 0,1,2 0 0 0 3,4,5 0 130 130 1 6 0 130 260 260 2 k = 3， a3 = 3 第 52頁 共 64頁 d2 s2 c2d2 + f3(s3) f2(s2) d*2 0 1 0,1,2 0+0 0 0 3 0+130 130 0 4,5 0+130 180+0 180 1 6 0+260 180+0 260 0 k = 2， a2 = 4， s3 = s2 4d2 s3 0， 1， 2 3， 4， 5 6 d3 0 1 2 f3(s3) 0 130 260 第 53頁 共 64頁 d1 s1 c1d1 + f2(s2) f1(s1) d*1 0 1 2 3 6 0+260 80+180 160+0 240+0 260 0， 1 k = 1， a1 = 2， s1 = 6 s2 0， 1， 2 3 4， 5 6 d2 0 0 1 0 f3(s3) 0 130 180 260 第 54頁 共 64頁 綜上可得最優(yōu)決策如下： 裝載能力 sk 載重量 dk 單位重量 ak 6 6 6 0 0 2 2 4 3 最大利潤為 260元。問應如何分配設備，使總利潤最大？ 表 46（單位：萬元） 第 56頁 共 64頁 按產品種類順序，問題分 4個階段。圖示如下： 解： 第 57頁 共 64頁 sk ： 可分配給第 k種產品的設備總量 dk ： 分配給第 k種產品的設備數(shù)量 基本方程為： ?????????? ??6,0)(,1,0)}(),(m a x{)(15511ssfsdsfdsvsfkkkkkkkkk?kkk dss ??? 1:狀態(tài)轉移方程0 ≤ sk≤ 6 ),( kkk dsv階段指標函數(shù) 見 表 46 第 58頁 共 64頁 k = 4 時， S4 = { 0， 1， 2， 3， 4， 5， 6 } d4 s4 v4(s4,d4) f4（ s4） d*4 0 1 2 3 4 5 6 0 0 0 0 1 0 28 28 1 2 0 28 47 47 2 3 0 28 47 65 65 3 4 0 28 47 65 74 74 4 5 0 28 47 65 74 80 80 5 6 0 28 47 65 74 80 85 85 6 利潤表 第 59頁 共 64頁 d3 s3 v3(s3,d3) + f4(s4) f3(s3) d*3 0 1 2 3 4 5 6 0 0+0 0 0 1 0+28 18+0 28 0 2 0+47 18+28 39+0 47 0 3 0+65 18+47 39+28 61+0 67 2 4 0+74 18+65 39+47 61+28 78+0 89 3 5 0+80 18+74 39+65 61+47 78+28 90+0 108 3 6 0+85 18+80 39+74 61+65 78+47 90+28 95+0 126 3 s4 0 1 2 3 4 5 6 d4 0 1 2 3 4 5 6 f4(s4) 0 28 47 65 74 80 85 k = 3 時， S3 = { 0， 1， 2， 3， 4， 5， 6 } 利潤表 第 60頁 共 64頁 d2 s2 v2(s2,d2) + f3(s3) f2(s2) d*2 0 1 2 3 4 5 6 0 0+0 0 0 1 0+28 25+0 28 0 2 0+47 25+28 45+0 53 1 3 0+67 25+47 45+28 57+0 73 2 4 0+89 25+67 45+47 57+28 65+0 92 1， 2 5 0+108 25+89 45+67 57+47 65+28 70+0 114 1 6 0+126 25+108 45+89 57+67 65+47 70+28 73+0 134 2 s3 0 1 2 3 4 5 6 d3 0 0 0 2 3 3 3 f3(s3) 0 28 47 67 89 108 126 k = 2 時， S2 = { 0， 1， 2， 3， 4， 5， 6 } 利潤表 第 61頁 共 64頁 d1 s1 v1(s1,d1) + f2(s2) f1(s1) d*1 0 1 2 3 4 5 6 6 0+134 20+114 42+92 60+73 75+53 85+28 90+0 134 0， 1， 2 s2 0 1 2 3 4 5 6 d2 0 0 1 2 1,2 1 2 f2(s2) 0 28 53 73 92 114 134 k = 1 時， S1 = { 6 } 利潤表 第 62頁 共 64頁 綜上可得最優(yōu)決策如下： 設備總數(shù) sk 投資設備數(shù) dk 6 6 4 1 0 2 3 1 最大利潤為 134萬元
教學課件相關推薦
鄂ICP備17016276號-1