第7章 动态规划实验

第7章动态规划实验基础知识使用Lingo软件求解动态规划问题利用WinQSB

软件求解动态规划问题使用MATLAB软件求解动态规划问题基础知识

动态规划是解决多阶段决策过程最优化问题的一种数学方法。20世纪50年代初，美国数学家贝尔曼（Bellman）等人提出了解决多阶段决策问题的最优性原理，从而创建了解决最优化问题的一种新方法——动态规划。该方法将多阶段决策问题转换成一系列互相联系的单阶段问题，然后逐个解决。动态规划是现代管理中重要的决策方法，可以解决最优路径、资源分配、库存、生产过程优化和设备更新等许多实际问题。动态规划模型包含的要素（1）阶段：把所给定问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序求解。阶段的划分，一般是按照时间或空间的自然特征来划分的，将问题的过程转化为多阶段决策过程。（2）状态：表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。状态是某阶段做出决策的出发点和依据，且有无后效性。（3）决策：表示当过程处于某一阶段的某个状态时，可以做出不同的决定，从而确定下一阶段的状态。（4）策略：是按一定顺序排列的决策组成的集合。（5）状态转移方程：是确定过程由一个状态到另一个状态的演变过程。（6）指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标为指标函数；指标函数的最优值为最优值函数。基础知识

基础知识

使用Lingo软件求解动态规划问题

实验目的（1）熟悉使用Lingo软件求解最短路径问题、背包问题和生产与储存问题。（2）通过使用Lingo软件求解动态规划问题，进一步熟悉Lingo软件的基本命令及语法。实验内容例7.1（最短路径问题）网络图如图7-1所示，求由起点A到讫点E的最短路径。使用Lingo软件求解动态规划问题

利用Lingo软件求解的步骤如下所示。(1)打开Lingo软件，在编辑窗口中输入下列代码：使用Lingo软件求解动态规划问题

(2)单击“LINGO”菜单中的“Solve”选项或单击工具栏中的按钮，求解该模型，得到下列结果。从运算结果可知，在图7-1中，起点A到讫点E的最短路径长度为8。模型结果中的F(1)，F(2)，…，F(10)表示各点到讫点E的最短距离。使用Lingo软件求解动态规划问题

使用Lingo软件求解动态规划问题

利用Lingo软件求解的步骤如下所示。sets:goods/A,B,C/:c,w,x;endsets

data:c=346;b=20;w=405070;enddata

max=@sum(goods:w*x);@sum(goods:c*x)<=b;@for(goods:@gin(x));(1)在Lingo软件编辑窗口中输入下列代码：(2)单击“LINGO”菜单中的“Solve”选项或单击工具栏中的按钮，求解该模型，得到下列结果。由运行结果可知，A、B、C三种货物装入背包的数量分别为4、2和0，最大价值为260元。使用Lingo软件求解动态规划问题

例7.3（生产与储存问题）某工厂要对一种产品制订下一年四个季度的生产计划，据估计，在下一年中，各季度市场对于该产品的需求量和每个季度生产单位产品的成本如表7-1所示。每个季度生产能力所允许的最大生产批量不超过6个单位；每个季度末未售出的产品，每单位需付库存费0.5万元。假定第一季度的初始库存量为0，第四季度末库存量为0。试问：该厂应如何安排各个季度的生产与储存，才能在满足市场需要的条件下，使总成本最小？使用Lingo软件求解动态规划问题

使用Lingo软件求解动态规划问题

利用Lingo软件求解的步骤如下所示。Model:sets:quarter/1..4/:c,x,e,d,s;endsetsdata:d=2324;c=2343;e=0.50.50.50.5;a=6;enddatamin=@sum(quarter:c*x+e*s);@for(quarter(i)|i#lt#4:s(i+1)=s(i)+x(i)-d(i));s(1)=0;s(4)+x(4)-d(4)=0;@for(quarter:x<=a);End(1)在Lingo软件编辑窗口中输入下列代码：(2)单击“LINGO”菜单中的“Solve”选项或单击工具栏中的按钮，求解该模型，得到下列结果使用Lingo软件求解动态规划问题

由运行结果可知，该工厂在下一年的四个季度依次生产6个单位、1个单位、0个单位和4个单位的产品，库存量为0个单位、4个单位、2个单位和0个单位。最小总成本为30万元。利用WinQSB软件求解动态规划问题

用WinQSB

软件求解动态规划问题时调用“DynamicProgramming”模块，该模块中有三个子块，能求解最短路径问题、背包问题和生产与储存问题，其他动态规划问题可以转化成上面三类问题进行求解。WinQSB

软件求解动态规划问题是基于表格的建模方式的，因此可以展示求解步骤。实验目的（1）熟悉用WinQSB

软件求解最短路径问题、背包问题和生产与储存问题的求解方法与步骤。（2）熟悉用WinQSB

软件求解设备更新问题的方法。（3）通过用WinQSB

软件求解动态规划问题，进一步理解动态规划问题的理论知识。利用WinQSB软件求解动态规划问题

实验内容例7.4利用WinQSB

软件求解例7.1。(1)选择“开始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜单命令，生成对话框，选择求解问题类型（见图7-2），单击“OK”按钮。(2)选择“Edit”→“NodeNames”菜单命令，弹出对话框（见图7-3），更改节点名，再单击“OK”按钮，得到图7-4所示的数据输入窗口，输入节点间距离。图7-2选择求解问题类型图7-3更改节点名对话框图7-4数据输入窗口利用WinQSB软件求解动态规划问题

(3)选择“SolveandAnalyze”→“SolvetheProblem”菜单命令，弹出对话框（见图7-5），选择起点和讫点。图7-5起、讫点选择对话框(4)单击图7-5所示对话框中的“Solve”按钮，得到模型结果（见图7-6）。图7-6模型结果由图7-6可知，起点A到讫点E的最短路径A→B1→C1→D2→E，最短距离为8。图7-5起、讫点选择对话框图7-6模型结果利用WinQSB软件求解动态规划问题

例7.5某单位计划购买一台设备在今后4年内使用。可以在第1年年初购买该设备，连续使用四年，也可以在任何一年年末将设备卖掉，于下年年初更换新设备。表7-2所示为各年年初购置新设备的价格，表7-3所示为设备的维护费及卖掉旧设备的回收费。如何确定设备的更新策略，可以使4年内的总费用最少？利用WinQSB软件求解动态规划问题

利用WinQSB软件求解动态规划问题

(1)选择“开始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜单命令，生成对话框（见图7-8），选择求解问题的类型。(2)单击图

7-8所示的“OK”按钮，输入节点间弧的权重（见图7-9）。图7-8例7.5动态规划类型选择对话框图7-9输入权重数据利用WinQSB软件求解动态规划问题

（3）选择“SolveandAnalyze”→“SolvetheProblem”菜单命令，弹出对话框（见图7-10），选择起点和讫点。（4）单击图7-10所示的“Solve”按钮，得到例7.5的模型结果（见图7-11）。由图7-11所示的结果可知，第1年年初购置新设备后在第1年年末将设备卖掉，在第2年年初再买进新设备一直用到第4年年末将其卖掉。在这种设备更新方案下，4年内的总费用最少，最少费用为2.6。图7-10例7.5的起、讫点选择对话框图7-11例7.5的模型结果利用WinQSB软件求解动态规划问题

例7.6利用WinQSB

软件求解例7.2。（1）选择“开始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜单命令，生成对话框（见图7-12），选择求解问题的类型，单击“OK”按钮。（2）在WinQSB

软件的编辑窗口中输入模型（见图7-13）。（3）选择“SolveandAnalyze”→“SolvetheProblem”菜单命令求解，得到例7.6的模型结果（见图7-14）。由模型结果可知，A、B、C三种货物装入背包的数量分别为4、2和0，最大价值为260元。图7-12例7.6的动态规划类型选择对话框图7-13例7.6的数据编辑窗口图7-14例7.6的模型结果利用WinQSB软件求解动态规划问题

例7.7（生产与储存问题）某工厂要对一种产品制订下一年四个季度的生产计划，据估计，在下一年中，各季度市场对于该产品的需求量如表7-5所示。假设该厂生产每批产品的固定成本为3万元，若不生产则为0；每单位产品成本为1万元，每个季度生产能力所允许的最大生产批量不超过6个单位；每个季度末未售出的产品，每单位需付库存费0.5万元。还假定第一季度的初始库存量为0，第四季度末库存量为0。试问：该厂应如何安排各季度的生产与储存，才能在满足市场需要的条件下使总成本最小？利用WinQSB软件求解动态规划问题

(1)选择“开始”→“程序”→“WinQSB”→“DynamicProgramming”→“File”→“NewProblem”菜单命令，生成对话框（见图7-15），选择求解问题的类型，单击“OK”按钮。(2)在WinQSB

软件的编辑窗口中输入模型（见图7-16）。(3)选择“SolveandAnalyze”→“SolvetheProblem”菜单命令求解，得到例7.7的模型结果（见图7-17）。由模型结果可知，该厂在下一年的四个季度依次生产5个单位、0个单位、6个单位和0个单位的产品，库存量为3个单位、0个单位、4个单位和0个单位，最小总成本为20.5万元。图7-15例7.7的动态规划类型选择对话框图7-16例7.7的数据输入窗口图7-17例7.7的模型结果使用MATLAB软件求解动态规划问题

对于动态规划问题，MATLAB软件优化工具箱没有提供求解的函数，因此需要依据相关的算法自行编写程序，进行动态规划问题的求解。本节利用Floyd算法求解动态规划问题中的最短路径问题；用逆序算法求解背包问题和生产与储存问题。实验目的（1）熟悉用MATLAB软件求解最短路径问题、背包问题和生产与储存问题的基本命令和M文件的编写。（2）通过用MATLAB软件求解动态规划问题，进一步理解动态规划问题的理论知识。使用MATLAB软件求解动态规划问题

实验内容例7.8用MATLAB软件求解例7.1。function[D,path]=DPexample1()a=[0,3,5,4,inf,inf,inf,inf,inf,inf;inf,0,inf,inf,1,5,inf,inf,inf,inf;inf,inf,0,inf,8,4,6,inf,inf,inf;inf,inf,inf,0,4,4,2,inf,inf,inf;inf,inf,inf,inf,0,inf,inf,4,2,inf;inf,inf,inf,inf,inf,0,inf,6,9,inf;inf,inf,inf,inf,inf,inf,0,7,5,inf;inf,inf,inf,inf,inf,inf,inf,0,inf,1;inf,inf,inf,inf,inf,inf,inf,inf,0,2;inf,inf,inf,inf,inf,inf,inf,inf,inf,0];A=1;E=10;n=size(a,1);D=a;path=zeros(n,n);i=0;k=1;r(k)=A;p=path(A,E);while(i==0)ifp~=Ek=k+1;r(k)=p;p=path(p,E);elser(k+1)=E;

i=1;endendm=size(r);short_path=rshort_path_length=D(1,10)fori=1:nforj=1:nifD(i,j)~=infpath(i,j)=j;endendendfork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);path(i,j)=path(i,k);endendendend(1)打开MATLAB软件，创建一个新的“.m”文件，在编辑窗口中输入下列代码：使用MATLAB软件求解动态规划问题

(1)选择“Debug”→“R