《現(xiàn)代庫存管理：模型、算法與Python實現(xiàn)》 課件 第15、16章 承諾服務(wù)模型、某食品企業(yè)Z的分銷網(wǎng)絡(luò)庫存優(yōu)化實戰(zhàn)

現(xiàn)代庫存管理：模型、算法與Python實現(xiàn)第15章承諾服務(wù)模型15.1承諾服務(wù)模型的需求規(guī)劃問題

15.1承諾服務(wù)模型的需求規(guī)劃問題

15.2需求上界的構(gòu)造與計算

15.2需求上界的構(gòu)造與計算

15.2需求上界的構(gòu)造與計算例：以下圖的生產(chǎn)裝配網(wǎng)絡(luò)為對象，計算給定服務(wù)水平為0.95的情況下，每個節(jié)點的需求上界#定義數(shù)據(jù)存儲路徑

data_dir=

'../../data/tree_example/'

#讀取網(wǎng)絡(luò)的節(jié)點數(shù)據(jù)

node_df=pd.read_csv(data_dir+

'assembly_node_df.csv')

#讀取網(wǎng)絡(luò)的邊數(shù)據(jù)

edge_df=pd.read_csv(data_dir+

'assembly_edge_df.csv')

#讀取網(wǎng)絡(luò)的需求數(shù)據(jù)

demand_df=pd.read_csv(data_dir+

'assembly_demand_df.csv')15.2需求上界的構(gòu)造與計算例：數(shù)據(jù)概況節(jié)點信息表’node_df’：’lt’：節(jié)點的單級提前期’hc’：單位持貨成本’sla’：對客戶承諾的服務(wù)時間node_idlthcsla0C180.4685565NaN1B111.994935NaN2C270.271441NaN3C330.632656NaN4B280.861130NaN5A33.7657402.0邊信息表’edge_df’：’predecessor’：上游節(jié)點’successor’：下游節(jié)點’quantity’：生產(chǎn)配比predecessorsuccessorquantity0C1B111B1A12C2B123C3B214B2A1需求信息表’demand_df’：只有節(jié)點A為需求節(jié)點，mean為14.558117，std為2.89212915.2需求上界的構(gòu)造與計算假設(shè)庫存共享效應(yīng)系數(shù)為2，服務(wù)水平系數(shù)取標(biāo)準(zhǔn)正態(tài)分布的0.95分位數(shù)。相當(dāng)于假設(shè)需求服從正態(tài)分布，同時模型僅覆蓋0.95分位數(shù)以下的需求波動

pooling_factor=

2

tau=

0.9515.2需求上界的構(gòu)造與計算具體代碼如下：#調(diào)用第10章確定上游節(jié)點的函數(shù)得到每個節(jié)點的上游節(jié)點列表

pred_dict=find_predecessors_dict(edges=edge_df[['predecessor',

'successor']].values)

#生產(chǎn)配比

qty_dict={(pred,succ):qtyforpred,succ,qtyinedge_df.values}

#需求節(jié)點的需求及標(biāo)準(zhǔn)差

mu_dict=dict(zip(demand_df['node_id'],demand_df['mean']))

sigma_dict=dict(zip(demand_df['node_id'],demand_df['std']))

#各節(jié)點自身需求所對應(yīng)的需求波動系數(shù)

ksigma_dict={node:0

fornodeinnode_df['node_id']}

ksigma_dict.update({node:norm.ppf(tau)*sigma

fornode,sigmainsigma_dict.items()})

#初始化涉及到向下傳遞的字典

network_mu_dict={node:0

fornodeinnode_df['node_id']}

#首先將需求節(jié)點的信息加入到字典中

network_mu_dict.update({node:mufornode,muinmu_dict.items()})

constant_dict={node:v**pooling_factorfornode,vinksigma_dict.items()}15.2需求上界的構(gòu)造與計算具體代碼如下：#將網(wǎng)絡(luò)的邊反向

reverse_edges=[(j,i)fori,jin

edge_df[['predecessor','successor']].values]

#計算拓?fù)渑判?/p>

ts=TopologicalSort(reverse_edges)

reverse_topo_sort=ts()

fornodeinreverse_topo_sort:

#如果節(jié)點有上游節(jié)點，則將自身的需求信息傳遞給上游節(jié)點

iflen(pred_dict[node])>

0:

forpredinpred_dict[node]:

constant_dict[pred]+=(qty_dict[pred,node]**pooling_factor)\

*constant_dict[node]

network_mu_dict[pred]+=qty_dict[pred,node]*network_mu_dict[

node]

#在全部節(jié)點傳遞完成后，計算需求波動系數(shù)

volatility_constant_dict={node:np.power(v,1

/pooling_factor)

fornode,vinconstant_dict.items()}

volatility_constant_df=pd.DataFrame.from_dict(

volatility_constant_dict,orient='index').reset_index().rename(

columns={'index':'node_id',0:'volatility_constant'})

network_mu_df=pd.DataFrame.from_dict(

network_mu_dict,orient='index').reset_index().rename(

columns={'index':'node_id',0:'mean'})15.2需求上界的構(gòu)造與計算具體代碼如下：lt_dict=dict(zip(node_df['node_id'],node_df['lt']))

cum_lt_dict=cal_cum_lt(edge_df[['predecessor','successor']].values,lt_dict)

cum_lt_df=pd.DataFrame.from_dict(

cum_lt_dict,orient='index').reset_index().rename(

columns={'index':'node_id',0:'cum_lt'})

node_df=node_df.merge(cum_lt_df,on='node_id',how='left')

print(node_df)#定義離散化的時間顆粒度

time_unit=

1

#根據(jù)節(jié)點和對應(yīng)的累計提前期，生成index

node_list=node_df['node_id'].tolist()

idx=[(node,ct)fornodeinnode_list

forctinnp.arange(0,cum_lt_dict[node]+time_unit,time_unit)]

idx=pd.MultiIndex.from_tuples(idx,names=['node_id','time'])

demand_bound_df=pd.DataFrame(index=idx).reset_index()

demand_bound_df=demand_bound_df.merge(

volatility_constant_df,on=['node_id'],how='left')

demand_bound_df=demand_bound_df.merge(

network_mu_df,on=['node_id'],how='left')

#根據(jù)對應(yīng)的CT，計算對應(yīng)的安全庫存量，以及需求上界

demand_bound_df['ss_qty']=demand_bound_df['volatility_constant']*np.power(

demand_bound_df['time'],1

/pooling_factor)

demand_bound_df['demand_bound']=demand_bound_df['mean']*demand_bound_df[

'time']+demand_bound_df['ss_qty']

print(demand_bound_df.head())15.2需求上界的構(gòu)造與計算結(jié)果如下：node_idtimevolatility_constantmeanss_qtydemand_bound0C104.75712914.558170.0000000.0000001C114.75712914.558174.75712919.3152472C124.75712914.558176.72759735.8438323C134.75712914.558178.23959051.9139424C144.75712914.558179.51425867.74672815.2需求上界的構(gòu)造與計算不同服務(wù)時間下的策略及成本比較：

根據(jù)計算得到的demand_bound_df，查找出每個節(jié)點不同覆蓋時間的安全庫存量，計算出總庫存成本，接下來考慮三種比較有代表性的策略：只在最下游設(shè)置安全庫存。該策略將安全庫存全部前置到需求節(jié)點，即只持有成品庫存。其好處是將所有節(jié)點安全庫存的覆蓋時間全部匯聚在需求節(jié)點，這樣可以最大化安全庫存在“時間維度”的共享效應(yīng)。其劣勢是完全忽視了安全庫存在“空間”維度的共享效應(yīng)按照單級的方法設(shè)置安全庫存。該策略下，每個節(jié)點都根據(jù)自身的提前期按照單級的方式計算安全庫存。其好處是計算簡單，但它完全沒有考慮到網(wǎng)絡(luò)中安全庫存的共享效應(yīng)，也忽略了節(jié)點之間持貨成本的差異，沒有對安全庫存進(jìn)行全網(wǎng)絡(luò)優(yōu)化網(wǎng)絡(luò)最優(yōu)的安全庫存。該策略通過優(yōu)化所有節(jié)點的服務(wù)時間，在保證需求節(jié)點的承諾服務(wù)時間的條件下，充分挖掘網(wǎng)絡(luò)中安全庫存“空間維度”和“時間維度”的共享效應(yīng)，最小化網(wǎng)絡(luò)的總安全庫存成本15.2需求上界的構(gòu)造與計算不同服務(wù)時間下的策略及成本比較：只在最下游設(shè)置安全庫存：前面計算過，節(jié)點A的累計提前期為14天，它的承諾服務(wù)時間為2天，如果只在節(jié)點A上設(shè)置安全庫存，它的覆蓋時間CT=14-2=12天，其他節(jié)點的覆蓋時間都為0，經(jīng)計算該策略的安全庫存成本為62.06使用單級的方法設(shè)置安全庫存：在該策略下，需求節(jié)點A的覆蓋時間等于自身提前期減去其sla，其他節(jié)點的覆蓋時間都是自身提前期，該策略的安全庫存總成本為57.34網(wǎng)絡(luò)最優(yōu)的安全庫存策略：本章的后續(xù)內(nèi)容將介紹如何優(yōu)化承諾服務(wù)模型。這里先直接給出該網(wǎng)絡(luò)下每個節(jié)點的最優(yōu)覆蓋時間：{’B2’:10,’B1’:0,’C1’:8,’C2’:7,’A’:2,’C3’:0}。根據(jù)給出的最優(yōu)覆蓋時間，可以得到最優(yōu)的安全庫存策略及其成本51.43可以看出，相比于前兩種方法，最優(yōu)的安全庫存策略能夠顯著降低庫存成本15.3承諾服務(wù)模型的優(yōu)化算法動態(tài)規(guī)劃算法：例：對下圖樹網(wǎng)絡(luò)中的節(jié)點進(jìn)行排序步驟2可能出現(xiàn)多種選擇，因此得到的排序可能不唯一

得到一組符合要求的排序：[’D1’,’D2’,’C2’,’A1’,’A2’,’C1’,’B’]那么該樹網(wǎng)絡(luò)中每個節(jié)點對應(yīng)的排序標(biāo)記為：{’A1’:4,’A2’:5,’B’:7,’C1’:6,’C2’:3,’D1’:1,’D2’:2}15.3承諾服務(wù)模型的優(yōu)化算法動態(tài)規(guī)劃算法：

A1B{A1}A2B{A2}B\{A1,A2,C1,C2}C1B{C1,D1,D2}C2B{C2}D1C1{D1}D2C1{D2}15.3承諾服務(wù)模型的優(yōu)化算法動態(tài)規(guī)劃算法：

15.3承諾服務(wù)模型的優(yōu)化算法求解樹網(wǎng)絡(luò)上的最優(yōu)成本：

15.3承諾服務(wù)模型的優(yōu)化算法求解樹網(wǎng)絡(luò)上的最優(yōu)成本：

15.3承諾服務(wù)模型的優(yōu)化算法基于分段線性函數(shù)近似的混合整數(shù)規(guī)劃算法：

15.3承諾服務(wù)模型的優(yōu)化算法基于分段線性函數(shù)近似的混合整數(shù)規(guī)劃算法：

15.3承諾服務(wù)模型的優(yōu)化算法基于分段線性函數(shù)近似的混合整數(shù)規(guī)劃算法：安全庫存量的分段線性近似結(jié)構(gòu)圖：15.3承諾服務(wù)模型的優(yōu)化算法基于分段線性函數(shù)近似的混合整數(shù)規(guī)劃算法：基于分段線性近似后的目標(biāo)函數(shù)帶入到承諾服務(wù)模型中，得到近似后的優(yōu)化模型：：

現(xiàn)代庫存管理：模型、算法與Python實現(xiàn)第16章某食品企業(yè)Z的分銷網(wǎng)絡(luò)庫存優(yōu)化實戰(zhàn)16.1背景介紹企業(yè)Z是一家大型國際食品制造商：公司在中國建成了三級供應(yīng)網(wǎng)絡(luò)，有一個工廠，南北兩個區(qū)域大倉，北方區(qū)域大倉下轄三個分銷中心，南方區(qū)域大倉下轄五個分銷中心，由分銷中心向各區(qū)域的客戶進(jìn)行履約目前公司供應(yīng)網(wǎng)絡(luò)的庫存管理主要采用單級的策略，每個倉采用覆蓋自身提前期的目標(biāo)庫存策略來管理庫存企業(yè)的發(fā)展趨勢和轉(zhuǎn)型需求：搭建了一套智慧供應(yīng)鏈管理系統(tǒng)，將數(shù)據(jù)、算法和人工協(xié)作有機結(jié)合，加強供應(yīng)網(wǎng)絡(luò)的全局協(xié)同能力旨在研發(fā)一套分銷網(wǎng)絡(luò)的全局安全庫存優(yōu)化模型與算法，嵌入到其供應(yīng)鏈管理系統(tǒng)當(dāng)中16.1背景介紹挑選公司旗下的7個核心SKU，以這7個SKU的數(shù)據(jù)來探究如下兩個問題：從全局優(yōu)化的角度，這7個SKU的安全庫存應(yīng)該分別布局在哪些倉，以及相應(yīng)的量應(yīng)該是多少？全局優(yōu)化后的安全庫存策略相比于當(dāng)前策略，能否顯著降低總安全庫存成本？研究方法步驟：將Z公司的分銷網(wǎng)絡(luò)建立成一個樹網(wǎng)絡(luò)對網(wǎng)絡(luò)進(jìn)行分析并建立相應(yīng)的承諾服務(wù)模型利用動態(tài)規(guī)劃算法求解最優(yōu)的安全庫存策略并分析其價值16.2數(shù)據(jù)導(dǎo)入及預(yù)處理#導(dǎo)入網(wǎng)絡(luò)分析包

importnetworkxasnx

#導(dǎo)入數(shù)據(jù)分析包

importnumpyasnp

importpandasaspd

importmatplotlib.pyplotasplt

fromcollectionsimportdefaultdict

#導(dǎo)入第14章介紹過的幾個算法

fromchapter14_network_basicimportfind_predecessors_dict,find_successors_dict,\

cal_cum_lt,cal_demand_bound

importwarnings

warnings.filterwarnings('ignore')#定義數(shù)據(jù)路徑

data_dir=

'../../data/food/'

#讀取分銷網(wǎng)絡(luò)的邊數(shù)據(jù)

edge_df=pd.read_csv(data_dir+

'edge_data.csv')

#讀取各SKU的生產(chǎn)時間數(shù)據(jù)

production_time_df=pd.read_csv(data_dir+

'production_time_data.csv')

#讀取各節(jié)點的特征數(shù)據(jù)

feature_df=pd.read_csv(data_dir+

'feature_data.csv')

#讀取需求節(jié)點（DC）的需求數(shù)據(jù)

demand_df=pd.read_csv(data_dir+

'demand_data.csv')16.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集概況：edge_df表：分銷網(wǎng)絡(luò)的邊信息表’predecessor’：上游節(jié)點’successor’：下游節(jié)點’transport_time’：從上游節(jié)點到下游節(jié)點所需運輸時間’quantity’：配比在分銷網(wǎng)絡(luò)中上下游只是運輸傳送關(guān)系，配比均為1predecessorsuccessortransport_timequantity0F000RDC001311F000RDC002212RDC001DC004113RDC001DC008214RDC001DC010315RDC002DC003116RDC002DC005217RDC002DC007118RDC002DC006319RDC002DC0092116.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集概況：利用NetworkX，對Z企業(yè)的分銷網(wǎng)絡(luò)進(jìn)行可視化展示：16.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集概況：production_time_df表：7個SKU的生產(chǎn)時間sku_idproduction_time0SKU00031SKU00132SKU00213SKU00314SKU00425SKU00536SKU006316.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集概況：feature_df表：各個SKU在各節(jié)點（工廠，RDC和DC）的持貨成本’hc’：持貨成本’sla’：對客戶承諾的服務(wù)時間’unit_id’：一個節(jié)點與一個SKU的組合node_idsku_idhcslaunit_id0DC003SKU0000.841DC003_SKU0001DC004SKU0000.871DC004_SKU0002DC005SKU0000.881DC005_SKU0003DC006SKU0000.884DC006_SKU0004DC007SKU0000.894DC007_SKU00016.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集概況：demand_df表：從歷史銷量數(shù)據(jù)中統(tǒng)計得到的各SKU在各個需求節(jié)點（各個DC）的需求均值和標(biāo)準(zhǔn)差node_idsku_idmeanstdunit_id0DC003SKU000108.767138146.382985DC003_SKU0001DC003SKU00191.416757142.366810DC003_SKU0012DC003SKU002129.607221209.291639DC003_SKU0023DC003SKU00397.410929174.465898DC003_SKU0034DC003SKU00492.281828139.159005DC003_SKU00416.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集預(yù)處理：以SKU’SKU000’為例將’SKU000’的相關(guān)數(shù)據(jù)提取出來，并進(jìn)行預(yù)處理，計算出每個節(jié)點的累計提前期計算每個節(jié)點覆蓋時間的需求上界及安全庫存量，計算周期服務(wù)水平為0.95對應(yīng)的需求上界將后續(xù)要反復(fù)使用的數(shù)據(jù)轉(zhuǎn)換成字典格式數(shù)據(jù)集預(yù)處理代碼如下：sku=

'SKU000'

#將sku對應(yīng)的需求信息提取出來

sku_demand_df=demand_df[demand_df['sku_id']==sku]

#分銷網(wǎng)絡(luò)的配比均為1

qty_dict={(pred,succ):qforpred,succ,qin

edge_df[['predecessor','successor','quantity']].values}

16.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集預(yù)處理代碼：#根據(jù)sku對應(yīng)的生產(chǎn)加工時間，計算每個節(jié)點的累計提前期

sku_production_time=int(production_time_df[

production_time_df['sku_id']==sku][

'production_time'])

lt_dict=dict(zip(edge_df['successor'],edge_df['transport_time']))

lt_dict.update({'F000':sku_production_time})

lt_df=pd.DataFrame.from_dict(

lt_dict,orient='index').reset_index().rename(

columns={'index':'node_id',0:'lt'})

cum_lt_dict=cal_cum_lt(edge_df[['predecessor','successor']].values,lt_dict)

cum_lt_df=pd.DataFrame.from_dict(

cum_lt_dict,orient='index').reset_index().rename(

columns={'index':'node_id',0:'cum_lt'})

#將sku對應(yīng)的節(jié)點屬性表讀取出來，并將提前期與累計提前期合并到一張表上，方便分析

sku_node_df=feature_df[feature_df['sku_id']==sku]

sku_node_df=sku_node_df.merge(lt_df,on='node_id',how='left')

sku_node_df=sku_node_df.merge(cum_lt_df,on='node_id',how='left')

print(sku_node_df)16.2數(shù)據(jù)導(dǎo)入及預(yù)處理數(shù)據(jù)集預(yù)處理代碼：#累計提前期

cum_lt_dict=dict(zip(sku_node_df['node_id'],sku_node_df['cum_lt']))

#提前期

lt_dict=dict(zip(sku_node_df['node_id'],sku_node_df['lt']))

#每個節(jié)點對應(yīng)覆蓋時間的安全庫存量

ss_ct_dict={(node,time):ssfornode,time,ssin

sku_demand_bound_df[['node_id','time','ss_qty']].values}

#持貨成本

hc_dict=dict(zip(sku_node_df['node_id'],sku_node_df['hc']))

#sla

sla_df=sku_node_df[sku_node_df['sla'].notna()]

sla_dict=dict(zip(sla_df['node_id'],sla_df['sla']))#將sku對應(yīng)的節(jié)點屬性表讀取出來，并將提前期與累計提前期合并到一張表上，方便分析

sku_node_df=feature_df[feature_df['sku_id']==sku]

sku_node_df=sku_node_df.merge(lt_df,on='node_id',how='left')

sku_node_df=sku_node_df.merge(cum_lt_df,on='node_id',how='left')

print(sku_node_df)16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略對網(wǎng)絡(luò)中的節(jié)點進(jìn)行排序：找到滿足除了根節(jié)點之外，每個節(jié)點至多有一個相鄰節(jié)點在該節(jié)點之后的序列defsort(graph):

#將圖轉(zhuǎn)化成無向圖

un_di_graph=graph.to_undirected()

#計算圖中節(jié)點總數(shù)

nodes_num=len(un_di_graph.nodes())

sorted_list=[]

#如果還有節(jié)點未被加入排序，則繼續(xù)

whilelen(sorted_list)<nodes_num:

#調(diào)用NetworkX計算節(jié)點的度數(shù)

degree_dict={node:vfornode,vinun_di_graph.degree()}

#將最多只有一個節(jié)點與其相鄰的節(jié)點加入排序

border_nodes=[nodefornode,degreeindegree_dict.items()if

degree<=

1]

sorted_list.extend(border_nodes)

#從圖中移除已排序的節(jié)點

un_di_graph.remove_nodes_from(border_nodes)

returnsorted_list

sorted_list=sort(graph)

print(sorted_list)16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

defget_parent_dict(graph,sorted_list):

un_di_graph=graph.to_undirected()

#找到每個節(jié)點相鄰的節(jié)點集合

neighbors_dict={node:list(un_di_graph.neighbors(node))

fornodeinun_di_graph.nodes()}

#對節(jié)點進(jìn)行標(biāo)號，方便查詢排序先后

labeled_dict={node:ifori,nodeinenumerate(sorted_list)}

parent_dict={}

fornodeinsorted_list:

#對于每個節(jié)點，用c表示在該節(jié)點之后的相鄰節(jié)點

c=

0

forneighborinneighbors_dict[node]:

iflabeled_dict[neighbor]>labeled_dict[node]:

c+=

1

#找到在該節(jié)點之后的相鄰節(jié)點后，將其記錄

parent_dict[node]=neighbor

#如果超過1，說明排序有誤

ifc>

1:

raise

Exception('wronglabel')

returnparent_dict

parent_dict=get_parent_dict(graph,sorted_list)16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略判斷每個節(jié)點應(yīng)該使用哪一類成本函數(shù)：定義函數(shù)classif_node用于判斷節(jié)點應(yīng)當(dāng)使用哪種成本函數(shù)，并記錄每個節(jié)點的子樹信息defclassify_node(graph,edge_df,sorted_list):

#定義上下游字典

pred_dict=find_predecessors_dict(

edges=edge_df[['predecessor','successor']].values)

succ_dict=find_successors_dict(

edges=edge_df[['predecessor','successor']].values)

un_di_graph=graph.to_undirected()

neighbors_dict={node:list(un_di_graph.neighbors(node))

fornodeinun_di_graph.nodes()}

labeled_dict={node:ifori,nodeinenumerate(sorted_list)}

to_eva_f_list=[]

to_eva_g_list=[]

fornodeinsorted_list:

forneighborinneighbors_dict[node]:

iflabeled_dict[neighbor]>labeled_dict[node]:

ifneighborinsucc_dict[node]:

#如果p(j)在節(jié)點j下游，則將節(jié)點標(biāo)記為使用f成本函數(shù)

to_eva_f_list.append(node)

16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略判斷每個節(jié)點應(yīng)該使用哪一類成本函數(shù)：定義函數(shù)classif_node用于判斷節(jié)點應(yīng)當(dāng)使用哪種成本函數(shù)，并記錄每個節(jié)點的子樹信息elifneighborinpred_dict[node]:

#如果p(j)在節(jié)點j上游，則將節(jié)點標(biāo)記為使用g成本函數(shù)

to_eva_g_list.append(node)

else:

raise

Exception('wrong')

#記錄子樹信息

sub_pred_dict={node:[pforpinpred_dict[node]

iflabeled_dict[p]<labeled_dict[node]]

fornodeinsorted_list}

sub_succ_dict={node:[sforsinsucc_dict[node]

iflabeled_dict[s]<labeled_dict[node]]

fornodeinsorted_list}

returnto_eva_f_list,to_eva_g_list,sub_pred_dict,sub_succ_dict

to_eva_f_list,to_eva_g_list,sub_pred_dict,sub_succ_dict=classify_node(

graph,edge_df,sorted_list)16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略數(shù)據(jù)準(zhǔn)備并初始化動態(tài)規(guī)劃表：代碼如下S_index={

node:np.arange(0,min(sla_dict.get(node,9999),cum_lt_dict[node])+

1)

fornodeinsorted_list}

SI_index={node:np.arange(0,cum_lt_dict[node]-lt_dict[node]+

1)

fornodeinsorted_list}

CT_index={node:np.arange(0,cum_lt_dict[node]+

1)fornodeinsorted_list}on_hand_cost={(node,CT):hc_dict[node]*ss_ct_dict[node,CT]

fornodeinsorted_listforCTinCT_index[node]}#cost_record記錄出每個節(jié)點，每種策略組合（S，SI）下的成本

cost_record=defaultdict(dict)

#f_cost記錄在給定S的情況下，p(j)在節(jié)點下游的節(jié)點的子樹上的最小庫存成本

f_cost={(node,S):-float('inf')fornodeinto_eva_f_listforSin

S_index[node]}

#f_argmin記錄f_cost的最小庫存成本所對應(yīng)的SI

f_argmin={(node,S):-float('inf')fornodeinto_eva_f_listforSin

S_index[node]}

#g_cost記錄在給定SI的情況下，p(j)在節(jié)點上游的節(jié)點的子樹上的最小庫存成本

g_cost={(node,SI):-float('inf')fornodeinto_eva_g_listforSIin

SI_index[node]}

#g_argmin記錄g_cost的最小庫存成本所對應(yīng)的S

g_argmin={(node,SI):-float('inf')fornodeinto_eva_g_listforSIin

SI_index[node]}16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

defevaluate_f(node,S):

#測試全部可能的SI

to_test_SI=np.arange(max(0,S-lt_dict[node]),

cum_lt_dict[node]-lt_dict[node]+

1)

forSIinto_test_SI:

#計算當(dāng)前策略組合下的覆蓋時間

CT=SI+lt_dict[node]-S

#計算當(dāng)前策略組合下的庫存成本

#首先是自身庫存成本

cost_record[node][S,SI]=on_hand_cost[node,CT]

#如果節(jié)點有上游節(jié)點，那么需要加總上游節(jié)點子樹對應(yīng)的成本

iflen(sub_pred_dict[node])>

0:

forpredinsub_pred_dict[node]:

cost_record[node][S,SI]+=min(

[f_cost[pred,s]forsinS_index[pred]ifs<=SI])

#如果節(jié)點有下游節(jié)點，那么需要加總下游節(jié)點子樹對應(yīng)的成本

iflen(sub_succ_dict[node])>

0:

forsuccinsub_succ_dict[node]:

cost_record[node][S,SI]+=min(

[g_cost[succ,si]forsiinSI_index[succ]ifsi>=S])

#找到給定S情況下的最優(yōu)的SI

cost_SI_dict={si:cost_record[node][S,si]forsiinto_test_SI}

best_SI=min(cost_SI_dict,key=cost_SI_dict.get)

#將成本記錄到f_cost，將最優(yōu)的SI記錄到f_argmin

f_cost[node,S]=cost_SI_dict[best_SI]

f_argmin[node,S]=best_SI16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

defevaluate_g(node,SI):

#測試全部可能的S

to_test_S=np.arange(0,min(sla_dict.get(node,9999),

SI+lt_dict[node])+

1)

forSinto_test_S:

#計算當(dāng)前策略組合下的覆蓋時間

CT=SI+lt_dict[node]-S

#計算當(dāng)前策略組合下的庫存成本

#首先是自身庫存成本

cost_record[node][S,SI]=on_hand_cost[node,CT]

#如果節(jié)點有上游節(jié)點，那么需要加總上游節(jié)點子樹對應(yīng)的成本

iflen(sub_pred_dict[node])>

0:

forpredinsub_pred_dict[node]:

cost_record[node][S,SI]+=min(

[f_cost[pred,s]forsinS_index[pred]ifs<=SI])

#如果節(jié)點有下游節(jié)點，那么需要加總下游節(jié)點子樹對應(yīng)的成本

iflen(sub_succ_dict[node])>

0:

forsuccinsub_succ_dict[node]:

cost_record[node][S,SI]+=min(

[g_cost[succ,si]forsiinSI_index[succ]ifsi>=S])

#找到給定SI情況下的最優(yōu)的S

cost_S_dict={s:cost_record[node][s,SI]forsinto_test_S}

best_S=min(cost_S_dict,key=cost_S_dict.get)

#將成本記錄到g_cost，將最優(yōu)的S記錄到g_argmin

g_cost[node,SI]=cost_S_dict[best_S]

g_argmin[node,SI]=best_S16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略根據(jù)排序，遍歷計算最優(yōu)成本#遍歷節(jié)點，除了最后一個節(jié)點外

fornodeinsorted_list[:-1]:

#如果p(j)在節(jié)點下游，則對于所有可能的S，計算f函數(shù)

ifnodeinto_eva_f_list:

forSinS_index[node]:

evaluate_f(node,S)

#如果p(j)在節(jié)點上游，則對于所有可能的S，計算g函數(shù)

ifnodeinto_eva_g_list:

forSIinSI_index[node]:

evaluate_g(node,SI)

#對于排序中最后一個節(jié)點，對于所有可能的SI，計算g函數(shù)

end_node=sorted_list[-1]

forSIinSI_index[end_node]:

evaluate_g(end_node,SI)16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略

end_g_cost_dict={si:g_cost[end_node,si]forsiinSI_index[end_node]}

end_node_SI=min(end_g_cost_dict,key=end_g_cost_dict.get)

end_node_S=g_argmin[end_node,end_node_SI]16.3應(yīng)用動態(tài)規(guī)劃算法求解最優(yōu)策略使用回溯法找到最優(yōu)策略：#定義最優(yōu)策略字典

opt_sol={'S':{},'SI':{},'CT':{}}

#將最后一個節(jié)點的最優(yōu)值存貯在最優(yōu)策略中

opt_sol['SI'][end_node]=end_node_SI

opt_sol['S'][end_node]=end_no