资源分配的挑战及应对方案

资源分配问题一般描述如下:将一定数量的若干种资源,全部分配给若干使用者,如何分配才能使效益最佳?【例8-2】就属于典型的资源分配问题,建模和求解过程如下:

视频-8．3．1资源分配问题-1-模型

解:

本题属于离散确定性动态规划问题,由于已知初始状态,可用逆序解法求解。

(1)建立动态规划模型。

①阶段变量:按工厂的数量将问题划分为三个阶段,k＝3,2,1;

②状态变量:Sk表示从第k个工厂到第n个工厂可以获得的设备数量,即设备分配给第k个工厂前,剩余的设备数量。

③决策变量:xk表示在k阶段Sk状态下,分配给第k个工厂的设备数量,0≤xk≤Sk。

④状态转移方程:Sk＋1＝Sk－xk。

⑤阶段函数:Pk(xk)。

⑥最优函数:fk(Sk)表示Sk套设备分配给第k到第n个工厂后,获得的最大利润。

⑦动态规划基本方程为:

视频-8．3．1资源分配问题-2-求解

(2)求解。

第一步,当k＝3时,甲、乙工厂分配结束,剩余的设备给丙,因此S3＝x3,状态可能集为S3＝{0,1,2,3,4,5}。最优函数为:

当x3＝0时,S3＝0,f3(0)＝P3(0)＝7;

当x3＝1时,S3＝1,f3(1)＝P3(1)＝12;

当x3＝2时,S3＝2,f3(2)＝P3(2)＝15;(www.xing528.com)

当x3＝3时,S3＝3,f3(3)＝P3(3)＝18;

当x3＝4时,S3＝4,f3(4)＝P3(4)＝20;

当x3＝5时,S3＝5,f3(5)＝P3(5)＝23。

第二步,当k＝2时,甲工厂分配结束,剩余的设备给乙和丙,因此S2＝S1－x3,状态可能集为S2＝{0,1,2,3,4,5}。最优函数为:

当S2＝0时,f2(0)＝max{P2(0)＋f3(0)}＝max{5＋7}＝12;

当S2＝1时,f2(1)＝max{P2(0)＋f3(1),P2(1)＋f3(0)}＝max{5＋12,17＋7}＝24;

当S2＝2时,f2(2)＝max{P2(0)＋f3(2),P2(1)＋f3(1),P2(2)＋f3(0)}＝max{5＋15,17＋12,20＋7}＝29;

当S2＝3时,f2(3)＝max{P2(0)＋f3(3),P2(1)＋f3(2),P2(2)＋f3(1),P2(3)＋f3(0)}＝max{5＋18,17＋15,20＋12,22＋7}＝32;

当S2＝4时,f2(4)＝max{P2(0)＋f3(4),P2(1)＋f3(3),P2(2)＋f3(2),P2(3)＋f3(1),P2(4)＋f3(0)}＝max{5＋20,17＋18,20＋15,22＋12,23＋7}＝35;

当S2＝5时,f2(5)＝max{P2(0)＋f3(5),P2(1)＋f3(4),P2(2)＋f3(3),P2(3)＋f3(2),P2(4)＋f3(1),P2(5)＋f3(0)}＝max{5＋23,17＋20,20＋18,22＋15,23＋12,24＋7}＝38。

第三步,当k＝1时,设备尚未分配,因此S1＝5。

最优函数为:

当S1＝5时,f1(5)＝max{P1(0)＋f2(5),P1(1)＋f2(4),P1(2)＋f2(3),P1(3)＋f2(2),P1(4)＋f2(1),P1(5)＋f2(0)}＝max{0＋38,10＋35,15＋32,20＋29,23＋24,25＋12}＝49。

第四步,反向追踪,寻找最优方案。

f1(5)＝P1(3)＋f2(2)＝P1(3)＋P2(1)＋f3(1)＝P1(3)＋P2(1)＋P3(1)＝20＋17＋12＝49;

最优分配方案是,甲、乙、丙工厂分别为3台、1台和1台设备,利润最大49万元。