资源描述：
《《运筹学研究生辅导课件》动态规划例1求解下列整数规划的最优解》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、例1求解下列整数规划的最优解:maxZ=4旺+5x2+6x33兀i+4兀2+5花W10x.^0(j=l,2,3),x.为整数.解(1)建立动态规划模型：阶段变量：将给每一个变量®赋值看成一个阶段，划分为3个阶段，且阶段变量k=123.设状态变量耳表示从第£阶段到第3阶段约束右端最大值，则5.=10.设决策变量Xk表示第k阶段赋给变量无的值（k=1,2,3）•状态转移方程：$2=6-3心$3=$2一4兀2・阶段指标:终G,X,）=4xpU2（S2，兀2）=5兀2,“3（*，兀3）=6兀3・基本方程；人（》）=may{蘇（吐，无）+/如
2、（昭J}v—（"321）ak丿4（$4）=其中q—3,ci-）—4,=5.（1）用逆序法求解：当k=3时，厶（归）=m習_{6心+尤（为）}=map_{6兀}‘忖o吝用而j3g{0丄2,3,4,5,6,7,&9,10}・卜］表示不超过兀的最大整数。因此，当$3=0,1,2,3,4时,兀3=0；当®=5,6,7,&9时，花可取0或1；当归=1°时，心可取°，1，2,由此确定厶（*）•现将有关数据列入表4.1中表4」中.6x3+f4(s4)厶(S3)*兀301200001000200030004000506616066170661806
3、6190661100612122当k=2时，有/2C2）max（）02W亍X{5x2+/；（53）}max{5七+厶（①-化）}，FT而$2W{0,1,2,3,4,5,6,7,8,9,10}。所以当52=0,1,2,3时,x2=0；当s2=4,5,6,7时,当R=1时，有max{4坷+乙（$
4、—3兀
5、）},max{4x,+/；（^）}=0WW—兀2=0或1；当52=8,9,10时勺=0,1,2。由此确定/；（52）o现将有关数据列入表4.2屮.5x2+厶（6-4x2）*（町）*兀3©01200+000010+000120+00023
6、0+000340+05+051050+65+060560+65+060670+65+060780+65+010+0102090+65+610+01115100+125+610+012（）10表4.2•A（以）=而$
7、=10,故无
8、只能取0,1,2,3,由此确定/；（5（）o现将有关数据列入表4.3中。表4.34西+Z（6-3西）/（sj*S2°123100+124+68+512+01324按计算顺序反推，由表4.3可知，当对=2时,£6）取得最大值13.又由》=4查表4.2得吃*=1,及$3=0,再由表4.1查得无3=0・因此,最
9、优解为x；=2,x；=l,兀；=0,最优解】11axZ=13・例5用动态规划方法解下列非线性规划问题maxz=兀].兀孑•兀3[X]+兀2+尤3WC[旺>0i=1,2,3解：解决这一类静态规划问题，需要人为地赋予时间概念，从而将该问题转化为多阶段决策过程。按问题的变量个数划分阶段，把它看作一个三阶段决策问题，B1,2,3设状态变量为$1，$2，$3，$4并记『We兀2，兀3为决策变量$2+兀1二$1WcOWxiWsiV3（兀3）=兀3，各指标函$3=兀3$3+兀2=$2X3=S300兀2冬$2V1（%1）=XV2（兀2）=兀2取问
10、题中的变量无1，状态转移方程为：允许决策集合为：各阶段指标函数为：数以乘积方式结合，最优指标函数加（》）表示从第£阶段初始状态以出发到第3阶段所得到的最大值，则动态规划基本方程为：jk©k）=max[坯（耳）•办+1（»+J]k=3,2,,lJ心5（»）九（”4）=1用逆序解法由后向前依次求解：□时，/；（»）=max[v3（x3）•/；（54）]=max（x3）=5-3X3WD3G3）X3F3/2（52）=max[v2（x9）-/^（53）]=max（x；・$3）=max[x；-（^2-x2）]x?g（59）-"OSxoS乃巧—_
11、令力2（$2，兀2）=^22（$2一兀2）用经典解析法求极值点：解得:-=2花*-3xf=0^-^=2s2-6x2dx2d2h2dxldx22=_2孔<0—$232_2所以x2=~S2是极大值点。.2兀=_s3一厶（6）=（扌吐）$（»-£吐）=寺雋/1（^1）=max［v1（x1）-/2（J2）］=max•刍成）=max［兀］•刍（旺一兀J3］“€/）］（£］）0"口1270“《127令伽,州）=坷—（5,-X,）3会=敖宀）+談宀）2（_1）=。解得:兀］=}1兀1=$1（舍）d2hx12912?2424荷二厉⑶-西）（-1）-
12、方（必-切+方恥7）=方d2h,dx：召=£$[=_方几＜0所以兀1=—S］是极大值点。4£/、_14z1、3_1/A（5i）=—5*1（5iS］）=S］11412741641由于印未知，所以对S1再求极值，踝W"）賈雲监时）显然S］
