运筹学思想方法及应用全套教学课件.pptx

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;第三章 动态规划;动态规划（Dynamic Programming）同前面介绍过的线性规划方法不同，它不是一种算法，而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术。由于动态规划不是一种特定的算法，因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则，动态规划必须对具体问题进行具体的分析处理。动态规划在工程技术、经济管理等各个领域都有着广泛的应用，并且获得了显著的效果。;3.1 最短路径问题 3.2 贝尔曼最优化原理 3.3 WinQSB软件应用;动态规划是解决多阶段决策问题的一种方法. 1951年，美国数学家贝尔曼（R.Bellman，1920～1984）研究了一类多阶段决策问题的特征，提出了解决这类问题的基本原理。在研究、解决了某些实际问题的基础上，他于1957年出版了《动态规划》这一名著。本章将简要介绍动态规划的思想方法及其应用。;动态规划解决问题的基本思路是：把整体比较复杂的大问题划分成一系列较易于解决的小问题，通过逐个求解，最终取得整体最优解。这种“分而治之，逐步调整”的方法，在一些比较难以解决的复杂问题中已经显示出优越性。经过半个世纪的发展，动态规划解决问题的方法已经广泛应用于经济、管理、军事、生物、工程等诸多领域，并取得了很好效果。;所谓多阶段决策过程是指这样一类活动过程：一个决策过程可以分为若干个相互联系的阶段，每个阶段都需要作一定的决策，但是每个阶段最优决策的选择不能只是孤立地考虑本阶段所取得的效果如何，必须把整个过程中的各个阶段联系起来考虑，要求所选择的各个阶段决策的集合——策略，能使整个过程的总效果达到最优。;3.1 最短路径问题 ;3.1 最短路径问题 ;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.1 最短路径问题;3.2 贝尔曼最优化原理 ;3.2 贝尔曼最优化原理 ;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.2 贝尔曼最优化原理;3.3 WinQSB软件应用;本节结合最短路径问题、背包问题介绍WinQSB软件的应用，其他问题的求解可参考本章参考文献. 求解动态规划问题，需要调用WinQSB软件中的子程序“Dynamic Programming”. 方法：点击“开始”“程序”“WinQSB”“Dynamic Programming”,屏幕显示如图3.3所示. 该程序有3个子模块：最短路问题（Stagecoach Problem）,背包问题（Knapsack Problem）,生产与存储问题（Production and Inventory Scheduling）. ; 3.3 WinQSB软件应用;1.最短路问题 【例3.3】用WinQSB软件求解例3.1. 解（1）调用WinQSB软件中的子程序“Dynamic Programming”， 建立新问题. 在图3.3中选择第一项，输入标题和站点数. （2）输入数据. 按照图3.1从左到右将相邻站点间的距离输入表 3.1中，其中 ;（3）求解.点击菜单栏“Solve and Analyze” “Solve the Problem”,得到图3.4. 再点击“Solve”键，得到计算结果，见表3.2. 可见由起点到终点的最短路径为 ;表 3.2 ;2. 背包问题 背包问题的一般提法是：设有一位旅行者携带背包去登山，已知他所能承受的背包质量为a ;【例3.4】已知1T的集装箱最大载重量为800kg.现有5种物品各10件可供选择装箱，其中单位物品重量、价值见表3.3. 求价值最大的装载方案. 表3.3;（2）按表3.4形式输入数据：第1列为物品名称，第2列为物品限量及集装箱最