动态规划例1 求解下列整数规划的最优解.doc

《动态规划例1 求解下列整数规划的最优解.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、例1求解下列整数规划的最优解：解（1）建立动态规划模型：阶段变量：将给每一个变量赋值看成一个阶段，划分为3个阶段，且阶段变量k=1,2,3.设状态变量表示从第阶段到第3阶段约束右端最大值，则设决策变量表示第阶段赋给变量的值.状态转移方程：阶段指标：基本方程；其中（1）用逆序法求解：当时，而表示不超过的最大整数。因此，当时，；当时，可取0或1；当时，可取0，1，2，由此确定现将有关数据列入表4.1中表4.1中.01201234500000060000060000016789100000066666126666

2、1211112当时，有而。所以当时，；当时，；当时。由此确定。现将有关数据列入表4.2中.表4.20120123456789100+00+00+00+00+00+60+60+60+60+60+125+05+05+05+05+05+65+610+010+010+00000566610111200001000210012305670510当时,有而故只能取0,1,2,3,由此确定。现将有关数据列入表4.3中。表4.30123100+124+68+512+01324按计算顺序反推，由表4.3可知,当及例5用动态规

3、划方法解下列非线性规划问题解：解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，k=1，2，3设状态变量为s1，s2，s3，s4并记s1≤c取问题中的变量x1，x2，x3为决策变量状态转移方程为：s3=x3s3+x2=s2s2+x1=s1≤c允许决策集合为：x3=s30≤x2≤s20≤x1≤s1各阶段指标函数为：v1（x1）=x1v2（x2）=x22v3（x3）=x3，各指标函数以乘积方式结合，最优指标函数fk（sk）表示

4、从第k阶段初始状态sk出发到第3阶段所得到的最大值，则动态规划基本方程为：用逆序解法由后向前依次求解：k=3时，x3*=s3k=2时，令h2（s2，x2）=x22（s2－x2）用经典解析法求极值点：解得：x2=0（舍）所以是极大值点。k=1时，令解得：x1=s1（舍）所以是极大值点。由于s1未知，所以对s1再求极值，显然s1=c时，f1（s1）取得最大值反向追踪得各阶段最优决策及最优值：s1=c所以最优解为：例6用动态规划方法解下列非线性规划问题解：按变量个数将原问题分为三个阶段，阶段变量k=1，2，3；选

5、择xk为决策变量；状态变量sk表示第k阶段至第3阶段决策变量之和；取小区间长度Δ=1，小区间数目m=6/1=6，状态变量sk的取值点为：状态转移方程：sk+1=sk－xk；允许决策集合：Dk（sk）=｛xk

6、0≤xk≤sk｝k=1，2，3xk，sk均在分割点上取值；阶段指标函数分别为：g1（x1）=x12g2（x2）=x2g3（x3）=x33，最优指标函数fk（sk）表示从第k阶段状态sk出发到第3阶段所得到的最大值，动态规划的基本方程为：k=3时，s3及x3取值点较多，计算结果以表格形式给出，见表6.1-

7、6.3所示。表6.1计算结果fx3s3x3f3(s3)x3*01234560123456018276412521601827641252160123456表6.2计算结果fx2s2x2f3(s2－x2)f2(s2)x2*0123456012345600000001×01×11×81×271×641×1252×02×12×82×272×643×03×13×83×274×04×14×85×05×16×00018276412800,111112表6.3计算结果fx1s1x12f2(s1－x1)f1(s1)x1*0

8、123456601×644×279×816×125×036×01082由表6.3知，x1*=2，s1=6，则s2=s1－x1*=6－2=4，查表6.2得：x2*=1，则s3=s2－x2*=4－1=3，查表6.1得：x3*=3，所以最优解为：x1*=2，x2*=1，x3*=3，f1(s1)=108。上面讨论的问题仅有一个约束条件。对具有多个约束条件的问题，同样可以用动态规划方法求解，但这时是一个多维动态规划问题，解法上比较繁琐一些。例7某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置

9、不同数量的销售点每月可得到的利润如表6.4所示。试问在各地区如何设置销售点可使每月总利润最大。表6.4利润值地区销售点01234123000161210251714302116322217解：如前所述，建立动态规划数学模型：将问题分为3个阶段，k=1，2，3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+1=sk－xk，其中s1=4；允许决