优化模型动态规划.ppt

9．1????????＠函数的应用在LINGO编程中，为了使程序更加简明，可阅读性，LINGO中提供了一类＠函数的命令集，主要有＠if,＠sum,＠max,＠min,＠for,＠bin,＠gin,＠bnd,＠free等，应用这些函数可以使程序变得很简明，下面介绍这些函数的应用。＠if：-----------用于分段函数的编程格式：＠if（A，B，C）含义：条件A成立时，取B，否则取C例1．LINGO的编程如下：F=＠if(x1#GE#0#and#x1#LE#70,-505,124);引入决策0-1变量例2．,则第八章动态规划问题及求解8．1多阶段决策问题动态规划是解决这样一类最优化问题的专门计算方法，这类问题允许把它的过程（求解）分解为一系列的单级过程（步骤）。最优化原理：达到系统某种状态的过程无论是怎样的，以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说，当系统处于第个状态时，只要最优规划剩余的个过程，便可逐步求出时的最优解。为了方便讨论动态规划的求解过程，我们把动态规划问题化分为下面几个过程：阶段（stage）：把问题恰当的分为若干个相互联系的阶段；2．状态（State）:它是表示某段的出发位置，是某支路的起点，又是前一段某支路的终点。第个阶段的状态变量应该包含前各阶段决策过程的全部信息，且之后作出的决策与之前的状态和决策无关。3．决策（Decision）:是指某阶段初从给定的状态出发决策者所作出的选择，决策变量表示第个阶段状态为时对方案的选择。决策允许范围记为，4．策略（Policy）:即决策序列。个阶段动态规划问题的策略可记为，当时，表示从阶段开始到最后的决策序列。5．状态转移方程：表明后一阶段和前一阶段之间的阶段状态和决策给定之后，第关系。当第阶段状态就确定了，记为6.指标函数：阶段指标函数----对应于某一阶段状态和从该状态出发的决策的某种指标度量。第阶段指标函数记为；过程指标函数----从某阶段开始到最后过程的指标度量。记为，最优策略值记为7．动态规划基本方程：过程指标函数是各阶段指标函数的函数。8．2动态规划问题的解法例1．设某仓库有12人巡逻守卫，负责4个要害部位，对每个部位可分别派2到4人巡逻，由于巡逻人数不同，各部位预期在一段时间内可能造成的损失也不一样，具体数字见下表。问该卫队应往各部位分别派多少人巡逻才能使预期损失最小？0102ABCD2人3人4人181410383531242221343125把12人派往4个部位看作4个阶段（k=1,2,3,4），每个阶段初可派遣的人数是前面阶段决策的结果，也是本阶段决策的依据。用表示第个阶段的状态变量，用表示第个阶段的决策变量（即在该阶段派出的人数，显然），各阶段可允许的决策集合状态转移方程为用表示第个阶段派出的巡逻人数为时，在该部位的预期损失值过程指标函数添加标题由于添加标题用添加标题表示从第添加标题个阶段到结束时预期损失值，添加标题先考虑D部位添加标题先考虑C，D部位添加标题由于添加标题，所以添加标题添加标题先考虑B，C，D部位添加标题先考虑A，B，C，D部位添加标题由于添加标题由于添加标题，所以添加标题，所以添加标题由此可见，A，B，C，D四个部位应分别派4人，2人，添加标题2人，4人，预期损失值为97。添加标题例5．求从A点到G点的最段路线解：从A到G分六个阶段：A-B,B-C,C-D,D-E,E-F,F-G第六阶段F-G最短路例2（2）第五阶段E-G最短路第四阶段D-G最短路添加标题第三阶段C-G最短路添加标题第二阶段B-G最短路第一阶段A-G最短路所以最短路是：A-B1-C2-D1-E2-F2-G,最短路长为18。例3．求下列非线性规划问题的值，我们分三个阶段，解：要求01分别为第1，2，3阶段的决策变量。02设状态变量为03，显然04阶段指标函数05第三阶段06第二阶段07CBA第一阶段所以最优值为例4设备平行分配某公司根据国家计划的安排拟将某种设备5台分给甲乙丙三个厂,各厂获得这种设备每年可向国家提供的利润如下表:工厂设备台数012345甲037912