#5-运筹学讲义[目标规划、动态规划].ppt

整数规划问题 运输问题模型 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务，已知各条航线的起点、终点城市及每天航班数见表1，假定各条航线使用相同型号的船只，又各城市间的航程天数见表2。 又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求？ 解：公司需配备船只分两部分: 1]载货航程需要的周转船只数: E-D需(17+2)*3=57条船 B-C 需(3+2)*2=10条船 A-F需(7+2)*1=9条船 D-B 需(13+2)*1=15条船 总共需91条船 目标规划( Goal programming ) 目标规划问题及其数学模型 问题的提出： 目标规划是在线性规划的基础上，为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。 目标规划是实行目标管理的有效工具，它根据企业制定的经营目标以及这些目标的轻重缓急次序，考虑现有资源情况，分析如何达到规定目标或从总体上离规定目标的差距为最小。 在许多客观实际问题中，要达到的目标往往不止一个。例如，设计导弹时既要使其射程最远，有要燃料最省，还要精度最高。这类含有多个目标的优化问题称为多目标规划问题。 目标规划是一个新的多目标决策工具，它能把决策者的意愿反映到数学模型中。目标规划不像线性（或非线性）规划那样去直接求目标函数的最大（小）值，而是寻求实际能够达到的值与目标之间的偏差变量的最小值，这些偏差变量表示目标的达成程度。 目标规划问题及其数学模型 例1 某企业计划生产甲，乙两种产品，这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。 解：设甲、乙产品的产量分别为x1，x2，建立线性规划模型： 线性规划模型存在的局限性： 1）要求问题的解必须满足全部约束条件，实际问题中并非所有约束都需要严格满足。 2）只能处理单目标的优化问题。实际问题中，目标和约束可以相互转化。 3）线性规划中各个约束条件都处于同等重要地位，但现实问题中，各目标的重要性即有层次上的差别，同一层次中又可以有权重上的区分。 4）线性规划寻求最优解，但很多实际问题中只需找出满意解就可以。 目标规划怎样解决上述线性规划模型建模中的局限性？ 目标规划问题及其数学模型 ∵正负偏差不可能同时出现，故总有： x1－x2+d--d+ =0 3）设备B必要时可加班及加班时间要控制，目标约束表示为： 上述目标规划模型可以表示为： 用目标规划求解问题的过程： 目标规划应用举例 例 已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2 为产品A、B产量。 动态规划 1 多阶段决策问题 动态规划是解决这样一类最优化问题的专门计算方法，这类问题允许把它的过程（求解）分解为一系列的单级过程（步骤）。 最优化原理：达到系统某种状态的过程无论是怎样的，以这个状态为初始状态的剩余过程的求解仍是最优的规划。也就是说，当系统处于第个状态时，只要最优规划剩余的个过程，便可逐步求出时的最优解。 表示第 个阶段派出的巡逻人数为 时，在该部位的预期损失值过程指标函数 ， 表示从第 个阶段到结束时预期损失值， （1）先考虑D部位 由于 （2）先考虑C，D部位 由于 ，所以有： （3）先考虑B，C，D部位 由于 ，所以 （4）先考虑A，B，C，D部位 由于 所以 由此可见，A，B，C，D四个部位应分别派4人，2人，2人，4人，预期损失值为97。 例2．求从A点到G点的最段路线 解：从A到G分六个阶段：A-B,B-C,C-D,D-E,E-F,F-G （1）第六阶段F-G最短路 （2）第五阶段E-G最短路 第四阶段D-G最短路 第三阶段C-G最短路 第二阶段B-G最短路 第一阶段A-G最短路 所以最短路是：A-B1-C2-D1-E2-F2-G,最短路长为18。 讨论与思考 最优解与?1=0，?2=1的结果相同——学分最多 多目标规划 最优解与?1=1，?2=0的结果相同——课程最少 Lingo解目标规划 方法：按目标的优先级次序，依次用lingo求解。每次求得的值再作为下一次的约束条件。 例1：求解下列目标规划 Lingo代码 min=d31; 2*x1+x2=11; x1-x2+d11-d12=0; x1+2*x2+d21-d22=10; 8*x1+10*x2+d31-d32=56; d12=0; d21+d22=0; 例2：某棉纺车间用甲乙两种棉花混纺生产A、B两种 棉纱，其相关数据如下表： 产品 资源 单耗（kg/km） A B 棉花库存量 甲绵(kg) 0.5 0.3