1、 - 1 - 数学规划课程设计 题目 通讯设备分配问题 姓名 班级 学号 - 2 - 1. 课程设计评价参考标准及得分 序号 指标 分值 得分 1 所选题目应用价值与难度 20 2 综合应用数学专业知识解决实 际问题的能力 30 3 与学分相适应的工作量和难 度，有一定的创新 30 4 图标美观，参考文献，格式合 适等 20 论 文 成 绩 指导教师签名 - 3 - 通讯设备分配问题 摘要：摘要：数学规划是运筹学的一个重要组成部分，它是近几十年里发展起来的一门新兴科 学。随着电子计算机的普及与发展，它在自然科学，社会科学，工程技术和现代管理中得到 了广泛的应用，日益受到人们的重视。而作为数学规
2、划中的一个重要分支的动态规划，是一 种解决复杂系统优化问题的方法， 是目前解决多阶段决策过程问题的基本理论之一。 由于动 态规划不是一种特定的算法， 因而它不像线性规划那样有自己标准的数学表达式和统一的求 解方法，而必须对具体问题进行具体的分析处理。因此其更具有实用价值，解决了我们现实 生活中许多实际问题。实践证明，动态规划在工程技术，经济管理，工业生产，军事以及现 代控制工程等领域都有广泛的应用，并获得显著效果。在本文中，我们主要介绍的运用动态 规划的思想，利用计算机软件 Excel,解决资源分配问题，就是一个现实生活中动态规划的运 用实例，同时，又充分利用计算机技术，使计算更为便捷有效，从
3、而更方便的解决了实际问 题。 关键词：关键词：数学规划；动态规划；多阶段决策过程问题；计算机软件 Excel；资源分配问 题 - 4 - 一引言一引言 正所谓资源分配，即是将数量一定的或若干种，诸如：材料，设备，人力， 资金，时间等资源，合理地分给若干个使用者，而是目标函数最大。在此处，由 于分配的资源过多， 且目标函数是非线性函数， 可将其看成一个多阶段决策问题， 利用动态规划的方法求解。在动态规划方法求解时，通常以把资源分配给一个或 几个使用者的过程作为一个阶段，把规划问题中的变量取为决策变量，将累计的 量或递推过程变化的量选为状态变量。 二二问题阐述问题阐述 某邮局有 4 套通讯设备准备
4、分给甲乙丙三个地区， 事先调查了各地原有生产 活动情况，在此基础上对各种分配方案的经济效益进行了估计，得下表 1（附录） 的数据，例如：甲区原有生产活动的收益为 38 万元，当新增加一套通讯设备时 总收益为 41 万元，其他类推。试求 4 套设备的分配方案，使 3 地区总利益最大。 三三模型模型的的建立建立和求解和求解 3.1 3.1 模型的建立模型的建立 首先我们对设备的分配规定一个顺序，即先考虑分配给甲区，其次乙区，最 后丙区，但分配时必须保证邮电局德宗受益最大。 将问题按分配过程分为 3 个阶段，根据动态规划逆序算法，可设： （1） 阶段数 t=1,2,3(即甲，乙，丙 3 个地区的编号
5、分别为 1，2，3)； （2） 状态变量 dk:表示分配给第 k 个地区至第 3 地区的设备套数（即第 k 阶段初尚未分配的设备套数） ； （3） 决策变量 Xk：表示分配给第 k 个地区的设备套数； （4） 状态转移方程：dk+1=dk-Xk； （5） Rt（Xk） ：表示 Xk台设备分配到第 k 个地区所得的收益值，它由表 1 查 得； （6） Ft(dk):表示将dk台设备分配到第k个地区至第 3地区所得的最大收益 - 5 - 值，因而可得出递推方程： Ft(dk)= max Rt（Xk） +Ft+1（dk- Xk） (k=1,2,3； t=1,2,3； Xk=0， 1，2，3，4) F
6、4(d4)=0 3.2 3.2 模型的求解模型的求解 运用动态规划的思想，利用穷举的方法以及计算机软件 Excel，进行模型求 解。根据问题分析中的相关公式，此处，为方便，令 Jt（dk, Xk）= Rt（Xk）+Ft+1 （dk- Xk） 。 求解步骤： （1）根据表 1 数据，将 Rt（Xk）输入 A4：F7 来构建电子表格，如图 1（附 录中）所示。例如：将 R2（2）=50 输入到单元格 D6 中； （2）在 B11：F11 中的各单元各内输入 0，因为对所有的 dk都有 F4(dk k)=0； （3） 在第 1820 行，设置计算指令求出 Jt（dk, Xk） ，此处使用 Excel 中的 HLOOKUP 命令来查找 Rt（Xk）(在第 5 行至第 7 行)和 Ft+1（dk- Xk）(在第 11 行至 第 14 行)的值。例如，要计算 J3（3, 1） ，需要将下列公式输入单元格 I18 中： =HL
