運籌學第五章動態(tài)規(guī)劃

運籌學第五章動態(tài)規(guī)劃

美國數(shù)學家貝爾曼（Richard.Bellman)創(chuàng)始時間上個世紀50年代創(chuàng)始人第2頁,共86頁，2024年2月25日，星期天多階段決策過程的最優(yōu)化第一節(jié)第3頁,共86頁，2024年2月25日，星期天

動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法這類活動可以按時間順序分解成若干個相互聯(lián)系的階段，每個階段都有若干個方案可供選擇多階段決策過程的最優(yōu)化的目標：達到整個活動過程的總體效果最優(yōu)第4頁,共86頁，2024年2月25日，星期天

系統(tǒng)的動態(tài)過程可以按照時間進程分為狀態(tài)相互聯(lián)系而又相互區(qū)別的各個階段，每個階段都要進行決策,目的是使整個過程的決策達到最優(yōu)效果。12n

狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策階段階段階段第5頁,共86頁，2024年2月25日，星期天分類動態(tài)規(guī)劃離散確定型離散隨機型連續(xù)確定型連續(xù)隨機型

根據(jù)決策過程的時間參數(shù)是離散的還是連續(xù)的、過程的演變是確定性的還是隨機性的第6頁,共86頁，2024年2月25日，星期天

動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。

必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應的模型，然后再用動態(tài)規(guī)劃方法去求解。注意：第7頁,共86頁，2024年2月25日，星期天1.生產(chǎn)決策問題：企業(yè)在生產(chǎn)過程中，由于需求是隨時間變化的，因此企業(yè)為了獲得全年的最佳生產(chǎn)效益，就要在整個生產(chǎn)過程中逐月或逐季度地根據(jù)庫存和需求決定生產(chǎn)計劃。多階段決策問題的典型例子：第8頁,共86頁，2024年2月25日，星期天

這時，機器的年完好率為a，即如果年初完好機器的數(shù)量為u，到年終完好的機器就為au,0<a<1。

在低負荷下生產(chǎn)時，產(chǎn)品的年產(chǎn)量h和投入生產(chǎn)的機器數(shù)量u2的關系為

h=h(u2)

假定開始生產(chǎn)時完好的機器數(shù)量為s1。要求制定一個五年計劃，在每年開始時，決定如何重新分配完好的機器在兩種不同的負荷下生產(chǎn)的數(shù)量，使在五年內(nèi)產(chǎn)品的總產(chǎn)量達到最高。

相應的機器年完好率b,0<b<1。

2.機器負荷分配問題：某種機器可以在高低兩種不同的負荷下進行生產(chǎn)。在高負荷下進行生產(chǎn)時，產(chǎn)品的年產(chǎn)量g和投入生產(chǎn)的機器數(shù)量u1的關系為g=g(u1)第9頁,共86頁，2024年2月25日，星期天

不包含時間因素的靜態(tài)決策問題（本質(zhì)上是一次決策問題）也可以適當?shù)匾腚A段的概念，作為多階段的決策問題用動態(tài)規(guī)劃方法來解決。3.線性規(guī)劃、非線性規(guī)劃等靜態(tài)的規(guī)劃問題也可以通過適當?shù)匾腚A段的概念，應用動態(tài)規(guī)劃方法加以解決。第10頁,共86頁，2024年2月25日，星期天4.

最短路問題：給定一個交通網(wǎng)絡圖如下，其中兩點之間的數(shù)字表示距離（或花費），試求從A點到G點的最短距離（總費用最?。?。123456AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第11頁,共86頁，2024年2月25日，星期天第二節(jié)基本概念和基本原理12n

狀態(tài)決策狀態(tài)決策狀態(tài)狀態(tài)決策階段階段階段策略狀態(tài)轉(zhuǎn)移指標函數(shù)基本概念第12頁,共86頁，2024年2月25日，星期天設從甘肅要鋪一條煤氣管道到北京，途中須經(jīng)過三個?。宏兾?、山西、河北，每省設一個中間站。各省建站可供選擇的地點及各段距離如下圖，現(xiàn)要求選擇一條甘肅到北京的鋪管線路使總距離最短?！?○2○3○4○5○6○7○8○9○10北京河北山西陜西甘肅8458961610967738423最短路問題多階段決策問題○1○3○5○8○10路長=21○1○4○6○9○10路長=16每一個階段的決策合在一起構成一個鋪設方案鋪設方案1：鋪設方案2：一個策略每個策略對應一個路長尋找最優(yōu)策略尋找路長最短的鋪設方案策略第13頁,共86頁，2024年2月25日，星期天1、階段：○1○2○3○4○5○6○7○8○9○10北京河北山西陜西甘肅8458961610967738423如最短路問題：問題分成4個階段：通常用k表示階段，是指對整個過程的自然劃分k=1，2，3，412，13，1458，7968，59，69，78，劃分階段的規(guī)則：根據(jù)時間順序或空間特征來劃分階段目的：以便按次序來解優(yōu)化問題線路：第一階段，甘肅陜西第三階段：山西河北線路：k=1：k=3：第14頁,共86頁，2024年2月25日，星期天2、狀態(tài)：第一階段的狀態(tài)：○1第二階段的狀態(tài)：○2○3○4狀態(tài)變量描述各階段狀態(tài)的變量○1○2○3○4○5○6○7○8○9○10北京河北山西陜西甘肅8458961610967738423如最短路問題：sk第k階段的狀態(tài)變量s4第4階段的初始狀態(tài)變量s4=⑧第4階段的初始狀態(tài)為○8Sk={sk}第k階段的狀態(tài)集合S3={s3}={⑤，⑥，⑦}注：n個階段的決策過程有個n+1狀態(tài)變量sn+1,表示sn演變的結果，簡稱為狀態(tài)各階段開始時所處的自然狀況或客觀條件S5={⑩}第15頁,共86頁，2024年2月25日，星期天動態(tài)規(guī)劃中的狀態(tài)應具有以下性質(zhì)：1、能描述過程的特征2、具有無后效性(馬爾可夫性)當某階段的狀態(tài)給定時，這個階段以后過程的演變與該階段以前各階段的狀態(tài)無關3、狀態(tài)是直接或間接可以觀測的第16頁,共86頁，2024年2月25日，星期天3、決策：當一個階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個狀態(tài)，這種選擇手段稱為決策○1○2○3○4○5○6○7○8○9○10北京河北山西陜西甘肅8458961610967738423決策變量描述決策的變量決策第2階段當狀態(tài)為③時的決策變量可取值為：⑤，⑥，⑦={⑤，⑥，⑦}，簡稱為決策允許決策集合第17頁,共86頁，2024年2月25日，星期天4、策略：由各階段的決策組成的序列稱為策略○1○2○3○4○5○6○7○8○9○10北京河北山西陜西甘肅8458961610967738423最短路問題：策略=鋪設方案如{}——允許策略集合最優(yōu)策略：使整個問題達到最優(yōu)效果的策略策略：{}最優(yōu)策略=最短的鋪設路線策略第18頁,共86頁，2024年2月25日，星期天策略：由各階段的決策組成的序列稱為策略原過程：一個n段決策過程，從1到n叫作問題的原過程原過程的一個后部子過程：

對于任意給定的k（1≤k≤n），從第k段到第n段的過程稱為原過程的一個后部子過程原過程的策略原過程的一個后部子過程的策略：第19頁,共86頁，2024年2月25日，星期天○1○2○3○4○5○6○7○8○9○10北京河北山西陜西甘肅8458961610967738423最短路問題：原過程的一個策略：后部子過程的策略后部子過程的策略后部子過程的策略{①→③，③→⑦，⑦→⑨，⑨→⑩}=p1，4（①）{③→⑦，⑦→⑨，⑨→⑩}{⑦→⑨，⑨→⑩}{⑨→⑩}第20頁,共86頁，2024年2月25日，星期天5、狀態(tài)轉(zhuǎn)移方程：是確定過程由一個狀態(tài)到另一個狀態(tài)的演變過程，描述了狀態(tài)轉(zhuǎn)移規(guī)律。sk第k階段的狀態(tài)變量狀態(tài)轉(zhuǎn)移方程：第21頁,共86頁，2024年2月25日，星期天6、指標函數(shù)用于衡量所選定的策略優(yōu)劣的數(shù)量指標稱為指標函數(shù)最優(yōu)策略第22頁,共86頁，2024年2月25日，星期天動態(tài)規(guī)劃的基本原理第23頁,共86頁，2024年2月25日，星期天最優(yōu)化原理：

一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策必構成最優(yōu)策略對最短路問題：A○○B(yǎng)1○F○B(yǎng)2○B(yǎng)3○C1○C2○C3○D2○D1○E2○E1則不論前面A如何到達B，B又如何到達C1第24頁,共86頁，2024年2月25日，星期天對最短路問題：來源于動態(tài)規(guī)劃的最優(yōu)化原理最短路問題的基本方程：k=4,3,2,1由后向前迭代遞推公式第25頁,共86頁，2024年2月25日，星期天建立動態(tài)規(guī)劃模型的步驟

1、劃分階段劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時間”概念，以便劃分階段。

2、正確選擇狀態(tài)變量選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點中尋找。

3、確定決策變量及允許決策集合通常選擇所求解問題的關鍵變量作為決策變量，同時要給出決策變量的取值范圍，即確定允許決策集合。第26頁,共86頁，2024年2月25日，星期天4、確定狀態(tài)轉(zhuǎn)移方程根據(jù)k階段狀態(tài)變量和決策變量，寫出k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應當具有遞推關系。

5、確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基本方程階段指標函數(shù)是指第k

階段的收益，最優(yōu)指標函數(shù)是指從第k階段狀態(tài)出發(fā)到第n階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。

以上五步是建立動態(tài)規(guī)劃數(shù)學模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時必須根據(jù)具體問題具體分析，只有通過不斷實踐總結，才能較好掌握建模方法與技巧。第27頁,共86頁，2024年2月25日，星期天例一、從A

地到D

地要鋪設一條煤氣管道,其中需經(jīng)過兩級中間站，兩點之間的連線上的數(shù)字表示距離，如圖所示。問應該選擇什么路線，使總距離最短？AB1B2C1C2C3D24333321114最短路徑問題第28頁,共86頁，2024年2月25日，星期天

解：整個計算過程分三個階段，從最后一個階段開始。

第一階段（C→D）：C

有三條路線到終點D

。

AB1B2C1C2C3D24333321114DC1C2C3顯然有f1(C1)

=1；

f1(C2)

=3；

f1(C3)

=4

第29頁,共86頁，2024年2月25日，星期天

d(B1,C1)+f1(C1)

3+1f2(B1)=mind(B1,C2

)+f1(C2)

=min3+3

d(B1,C3)+f1(C3)1+44=min6=45第二階段（B→C）：B到C

有六條路線。AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B1→C1→D)第30頁,共86頁，2024年2月25日，星期天

d(B2,C1)+f1(C1)

2+1f2(B2)=mind(B2,C2

)+f1(C2)

=min3+3

d(B2,C3)+f1(C3)1+43=min6=35AB1B2C1C2C3D24333321114DC1C2C3B1B2(最短路線為B2→C1→D)第31頁,共86頁，2024年2月25日，星期天第三階段（

A→B

）：A到B有二條路線。

f3(A)1=d(A,B1)＋f2(B1)＝2＋4＝6

f3(A)2=d(A,B2)＋f2(B2)＝4＋3＝7∴f3(A)

=min=min｛6,7｝=6d(A,B1)＋f2(B1)d(A,B2)＋f2(B2)(最短路線為A→B1→C1→D)AB1B2C1C2C3D24333321114DC1C2C3B1B2A第32頁,共86頁，2024年2月25日，星期天AB1B2C1C2C3D24333321114DC1C2C3B1B2A最短路線為A→B1→C1→D

路長為6第33頁,共86頁，2024年2月25日，星期天練習1：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G53136876368533842221333525664最優(yōu)路線為：A→B1→C2→D1→E2→F2→G

路長＝18求從A到G的最短路徑3第34頁,共86頁，2024年2月25日，星期天k=5，出發(fā)點E1、E2、E3u5(E1)=F1E1F1GAB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643u5(E2)=F2E2F2Gu5(E3)=F2E3F2Gk=6,F1Gf6(F1)=4F2G

,f6(F2)=3第35頁,共86頁，2024年2月25日，星期天k=4，f4(D1)=7

u4(D1)=E2f4(D2)=6

u4(D2)=E2f4(D3)=8

u4(D3)=E2k=2,f2(B1)=13

u2(B1)=C2f2(B2)=16u2(B2)=C3f3(C1)=13

u3(C1)=D1f3(C2)=10

u3(C2)=D1f3(C3)=9

u3(C3)=D1f3(C4)=12

u3(C4)=D3k=3,=minf1(A)=mind1(A,B1)+f2(B1)d1(A,B2)+f2(B2)5+133+16=18k=1,u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2第36頁,共86頁，2024年2月25日，星期天u1(A)=B1u2(B1)=C2u3(C2)=D1u4(D1)=E2u5(E1)=F1E1F1Gu5(E2)=F2E2F2Gu5(E3)=F2E3F2G759

u5(E2)=F2u6(F2)=G最優(yōu)策略AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643第37頁,共86頁，2024年2月25日，星期天求從A到E的最短路徑路線為A→B2→C1→D1→E

，最短路徑為19AB2B1B3C1C3D1D2EC25214112610104312111396581052練習2：1第38頁,共86頁，2024年2月25日，星期天

生產(chǎn)與存儲問題：某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今四個月市場需求預測如下表，又每月生產(chǎn)j個單位產(chǎn)品的費用為

每月庫存i個單位產(chǎn)品的費用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量都是零，試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下，使總費用最小。階段k=1，2，3，4第k階段的狀態(tài)變量ski月1234g(i)需求2324S1={0}，S2={0,1,2,3}，S3={0,1,2,3}，S4={0,1,2,3}=第k個月月初的庫存量第39頁,共86頁，2024年2月25日，星期天

生產(chǎn)與存儲問題某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今后四個月市場需求預測及每月生產(chǎn)j個單位產(chǎn)品的費用如下：

月1234需求2324k=1，2，3，4sk=第k個月月初的庫存量S1={0}S2={0,1,2,3}S3={0,1,2,3}S4={0,1,2,3}={2,3,4,5}每月庫存i個單位產(chǎn)品的費用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量都是零，試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下，使總費用最小。={2,3,4,5}={0,1,2,3}={3}第40頁,共86頁，2024年2月25日，星期天生產(chǎn)與存儲問題某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今四個月市場需求預測如下表，又每月生產(chǎn)j個單位產(chǎn)品的費用為

每月庫存i個單位產(chǎn)品的費用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量都是零，試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下，使總費用最小。i月1234g(i)需求2324k=1，2，3，4sk=第k個月月初的庫存量一個策略=一個生產(chǎn)方案2，5，0，42，3，2，4費用：21（千元）費用：23（千元）最優(yōu)策略：使總費用最小的生產(chǎn)方案第41頁,共86頁，2024年2月25日，星期天

生產(chǎn)與存儲問題某工廠生產(chǎn)并銷售某種產(chǎn)品。已知今四個月市場需求預測如下表，又每月生產(chǎn)j個單位產(chǎn)品的費用為

每月庫存i個單位產(chǎn)品的費用E(i)=0.5i(千元），該廠最大庫存容量為3個單位，每月最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量都是零，試制定四個月的生產(chǎn)計劃，在滿足用戶需求條件下，使總費用最小。階段k=1，2，3，4狀態(tài)變量sk=第k個月月初的庫存量i月1234g(i)需求2324狀態(tài)轉(zhuǎn)移方程：第42頁,共86頁，2024年2月25日，星期天當k=4時，u4(s4)對應的總費用=生產(chǎn)費+庫存費i月1234g(i)需求2324庫存費E(i)=0.5i，最大庫存容量為3個單位，最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量為零012347436.5326215.51第43頁,共86頁，2024年2月25日，星期天當k=3時，i月1234g(i)需求2324庫存費E(i)=0.5i，最大庫存容量為3個單位，最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量為零012301230u3(3)對應的總費用=生產(chǎn)費+庫存費第44頁,共86頁，2024年2月25日，星期天i月1234g(i)需求2324庫存費E(i)=0.5i，最大庫存容量為3個單位，最大生產(chǎn)能力為6個單位，計劃開始和計劃期末庫存量為零023451212.51313.51221123411.51212.51311.5120123811.51212.580301288011.512012347436.5326215.51第45頁,共86頁，2024年2月25日，星期天當k=2時，i月1234g(i)需求2324u2(s2)對應的總費用=生產(chǎn)費+庫存費第46頁,共86頁，2024年2月25日，星期天023451212.51313.51221123411.51212.51311.5120123811.51212.5803012811.51280k=3當k=2時，012334561818.51617165234517.51815.516.5123417012313.51714.515.515.5415313.5017.51516第47頁,共86頁，2024年2月25日，星期天當k=1時，i月1234g(i)需求2324u1(0)對應的總費用=生產(chǎn)費第48頁,共86頁，2024年2月25日，星期天k=2012334561818.51617165234517.51815.516.512341717.51516012313.51714.515.515.5415313.50當k=1時，023452221.52122121.5第49頁,共86頁，2024年2月25日，星期天生產(chǎn)存儲問題的基本方程：第50頁,共86頁，2024年2月25日，星期天最優(yōu)化原理：一個過程的最優(yōu)策略具有這樣的性質(zhì)，即無論初始狀態(tài)及初始決策如何，對于先前決策所形成的狀態(tài)而言，其以后的所有決策必構成最優(yōu)策略最短路問題的基本方程：k=4,3,2,1生產(chǎn)存儲問題的基本方程為：第51頁,共86頁，2024年2月25日，星期天k=n,n-1,n-2,…,3,2,1動態(tài)規(guī)劃的基本方程為：其中opt為最優(yōu)，可取min或max第52頁,共86頁，2024年2月25日，星期天

現(xiàn)有數(shù)量為a（萬元）的資金，計劃分配給n個工廠,用于擴大再生產(chǎn)。假設：xi為分配給第i個工廠的資金數(shù)量（萬元）；gi(xi)為第i個工廠得到資金后提供的利潤值（萬元）。問題是如何確定各工廠的資金數(shù)，使得總的利潤為最大。據(jù)此，有下式：投資分配問題第53頁,共86頁，2024年2月25日，星期天

令：fk(x)=以數(shù)量為x的資金分配給前k

個工廠，所得到的最大利潤值。用動態(tài)規(guī)劃求解，就是求fn(a)的問題。

當k=1

時，f1(x)=g1(x)（因為只給一個工廠）

當1＜k≤n

時，其遞推關系如下：設：y

為分給第k個工廠的資金（其中0≤y≤x

），此時還剩x

－y（萬元）的資金需要分配給前k-1

個工廠,如果采取最優(yōu)策略，則得到的最大利潤為fk－1(x－y),因此總的利潤為：

gk(y)＋fk－1(x－y)

第54頁,共86頁，2024年2月25日，星期天

如果a

是以萬元為資金分配單位，則式中的y只取非負整數(shù)0，1，2，…，x。上式可變?yōu)椋核裕鶕?jù)動態(tài)規(guī)劃的最優(yōu)化原理，有下式：第55頁,共86頁，2024年2月25日，星期天

例題：設國家撥給60萬元投資，供四個工廠擴建使用，每個工廠擴建后的利潤與投資額的大小有關，投資后的利潤函數(shù)如下表所示。

投資利潤0102030405060g1(x)0205065808585g2(x)0204050556065g3(x)0256085100110115g4(x)0254050606570解：依據(jù)題意，是要求f4(60)

。第56頁,共86頁，2024年2月25日，星期天按順序解法計算。第一階段：求f1(x)。顯然有f1(x)＝g1(x)，得到下表

投資利潤0102030405060f1(x)＝

g1(x)0205065808585最優(yōu)策略0102030405060第二階段：求f2(x)。此時需考慮第一、第二個工廠如何進行投資分配，以取得最大的總利潤。第57頁,共86頁，2024年2月25日，星期天最優(yōu)策略為（40，20），此時最大利潤為120萬元。同理可求得其它f2(x)

的值。第58頁,共86頁，2024年2月25日，星期天最優(yōu)策略為（30，20），此時最大利潤為105萬元。第59頁,共86頁，2024年2月25日，星期天最優(yōu)策略為（20，20），此時最大利潤為90萬元。最優(yōu)策略為（20，10），此時最大利潤為70萬元。第60頁,共86頁，2024年2月25日，星期天最優(yōu)策略為（10，0）或（0，10），此時最大利潤為20萬元。

f2(0)

＝0。最優(yōu)策略為（0，0），最大利潤為0萬元。得到下表最優(yōu)策略為（20，0），此時最大利潤為50萬元。第61頁,共86頁，2024年2月25日，星期天

投資利潤0102030405060f2(x)020507090105120最優(yōu)策略(0,0)(10,0)(0,10)(20,0)(20,10)(20,20)(30,20)(40,20)第三階段：求f3(x)。此時需考慮第一、第二及第三個工廠如何進行投資分配，以取得最大的總利潤。第62頁,共86頁，2024年2月25日，星期天最優(yōu)策略為（20，10，30），最大利潤為155萬元。同理可求得其它f3(x)

的值。得到下表第63頁,共86頁，2024年2月25日，星期天

投資利潤0102030405060f3(x)0256085110135155最優(yōu)策略(0,0,0)(0,0,10)(0,0,20)(0,0,30)(20,0,20)(20,0,30)(20,10,30)第四階段：求f4(60)。即問題的最優(yōu)策略。第64頁,共86頁，2024年2月25日，星期天最優(yōu)策略為（20，0，30，10），最大利潤為160萬元。第65頁,共86頁，2024年2月25日，星期天

練習：求投資分配問題得最優(yōu)策略，其中a＝50萬元，其余資料如表所示。

投資利潤01020304050g1(x)02140528085g2(x)015365073100g3(x)02560656870第66頁,共86頁，2024年2月25日，星期天例：某公司打算在3個不同的地區(qū)設置4個銷售點，根據(jù)市場部門估計，在不同地區(qū)設置不同數(shù)量的銷售點每月可得到的利潤如表所示。試問在各地區(qū)如何設置銷售點可使每月總利潤最大。地區(qū)銷售點01234123000161210251714302116322217x1=2，x2=1，x3=1，f3(4)=47

第67頁,共86頁，2024年2月25日，星期天

有一個徒步旅行者，其可攜帶物品重量的限度為a公斤，設有n

種物品可供他選擇裝入包中。已知每種物品的重量及使用價值（作用），問此人應如何選擇攜帶的物品（各幾件），使所起作用（使用價值）最大？物品

12…j…n重量（公斤/件）a1a2…

aj…

an每件使用價值c1c2…cj…

cn

這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。四、背包問題第68頁,共86頁，2024年2月25日，星期天設xj為第j種物品的裝件數(shù)（非負整數(shù)）則問題的數(shù)學模型如下：用動態(tài)規(guī)劃方法求解，令

fx(y)=總重量不超過

y公斤，包中只裝有前k種物品時的最大使用價值。其中y≥0，k

＝1,2,…,n。所以問題就是求fn(a)

第69頁,共86頁，2024年2月25日，星期天其遞推關系式為：當k=1時，有：第70頁,共86頁，2024年2月25日，星期天例題：求下面背包問題的最優(yōu)解物品123重量（公斤）325使用價值8512解：a＝5

，問題是求f3(5)第71頁,共86頁，2024年2月25日，星期天第72頁,共86頁，2024年2月25日，星期天第73頁,共86頁，2024年2月25日，星期天第74頁,共86頁，2024年2月25日，星期天第75頁