资源分配问题的求解方法要点.doc
《资源分配问题的求解方法要点.doc》由会员分享,可在线阅读,更多相关《资源分配问题的求解方法要点.doc(24页珍藏版)》请在咨信网上搜索。
1、资源分配问题的求解方法【摘要】资源分配问题就是将一种或几种资源(原材料、资金、机器设备等)以最优的方式分配给若干个使用者,以获得最大的效益。它可以是静态规划问题,也可以通过构造动态规划模型求解。本文通过用单纯形法求解线性规划问题,用隐枚举法、LINGO软件求解 0-1 规划问题,以及用逆序递推算法求解动态规划问题。这几种算法的最终目的都是用来求解资源分配的最优值问题。【关键词】资源分配;线性规划;0-1规划;动态规划The Method of Solving the Resource Allocation Problem【Abstract】Resource allocation problem
2、 is one or several resources( raw materials, machinery, equipment, etc.)assigned to several users by best way to get maximum benefit. It is a static planning problem, and can also through structural dynamic programming model to solve. This paper solves linear programming problem by using simplex met
3、hod, 0-1 programming problem by using the implicit enumeration method, LINGO software method, and dynamic programming problem by using reverse recursive algorithm. The ultimate goal of this several algorithms is to solve the optimal value problem of the resources allocation.【Key Word】Resource alloca
4、tion; Linear Programming; 0-1 programming; Dynamic programming目录 1 引言12 线性规划12.1 模型的建立12.2 求解方法22.3 实例 133 0-1规划53.1 模型的建立53.2 求解方法63.3 实例 284 动态规划104.1 模型的建立104.2 求解方法104.3 实例 3125 结论14参考文献15附录16致谢181 引言人们奋斗所争取的一切,都同他们的利益有关。资源分配问题关系着人们的利益能否实现,因而一直是政治经济学研究的中心课题之一。在近几年,随着社会经济的发展,资源分配问题已经广泛存在于社会各个领域,并
5、且已经成为制约我国改革、发展、稳定的焦点问题。如何在满足各使用者的基础上,将有限资源进行最佳分配,使得生产成本最低、投资最省、产量最高、利润最大,以最大限度地提高效益,是资源分配问题中亟待解决的难题,所以资源分配的求解方法就给解决这种问题带来了很大的方便。线性规划是运筹学中研究较早,理论和算法比较成熟的分支之一,它主要研究在线性等式(或不等式)的限制条件下,使某一线性目标函数取得最大值(或最小值)的问题,并且求解有统一而简单的方法即单纯形法。但在许多问题中,决策变量必须为整数,例如当决策变量是分配的人数、购买的设备数、投入的车辆数时,它们一般必须为非负整数时才有意义。在这种情况下,常需要应用整
6、数规划进行优化。0-1整数规划是整数规划的特殊情况,也是最广泛的整数规划,用0-1整数规划求解时有时会更容易。有时源分配问题上也可以使用动态规划求解,动态规划是解决多阶段决策过程最优化问题的一种方法,这种方法就是把它看成一个时间轴,在时间的推移过程中,在每个时间阶段选择适当的决策,以使整个系统达到最优。本文不仅介绍了线性规划、0-1规划、和动态规划几种求解资源分配的方法,还介绍了求解线性规划的方法单纯形法、求解0-1规划的方法隐枚举法和LINGO软件法、以及求解动态规划的方法逆序递推法等几种算法的模型、求解的具体步骤和所对应的实例。通过对本文的这几种求解方法的介绍,基本上就可以使不同的资源分配
7、问题得到更好更快的解答。2 线性规划2.1 模型的建立线性规划是运筹学中最基本且范围最广的分支,它最主要是应用于合理的进行各种资源的分配,以取得最佳的效果。对于这类需要种不同的原材料生产种不同的产品的资源分配问题,一般是已知每种原材料的库存量,每种产品所需的各种原材料的分量,以及生产每种产品能获得多少利益1。这类资源分配问题只要运用线性规划就可以解决。 表1 产品原材料产品库存量原材料利润这种线性规划问题的数学模型为: 这里为由目标函数的系数组成的向量, 和 分别为不等式约束条件的系数矩阵和右端向量, 和 分别为等式约束条件的系数矩阵和右端向量,当约束条件没有等式时, 和 就用空矩阵 表示,
8、和分别是变量的下界和上界约束。满足全部约束条件的一组决策变量 ,称为此线性问题的可行解,而使目标函数达到问题要求的最优值(或)的可行解称为线性规划问题的最优解。2.2 求解方法单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进的更好的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行,经过反复迭代,直到目标函数值达到最大值(或最小值),就得到了最优解。可以用图形表示为:单纯形法的思路最优解核心是:变量迭代找出一个初始基本可行解是否最优转移到另一个基本可行解是否循环结束 图1单纯形法的一般解题步骤
9、可归纳如下2: (1) 把线性规划问题的约束方程组表达成典式方程组,找一个初始的可行基;(2) 求出对应的典式及检验数向量; (3) 求; (4) 若,停止,已找到最优解(5) 若,停止,原问题无界;(6) 求;(7) 以代替得到新的基,转第(2)步;用单纯形法解题时,可通过单纯形表求得最优解。2.3 实例1某工厂可生产甲、乙两种产品,需消耗煤、电、油三种资源。现将有关数据列表如下: 表2 产品资源甲乙资源限量煤 9 4 360 电 4 5 200油 3 10 300单位产品价格 7 12 试拟订使总收入最大的生产计划方案。解:决策变量:甲、乙产品的计划产量,记为,;目标函数:总收入,记为,则
10、;为体现对其求极大化,在的前面冠以极大号;约束条件:分别来自资源煤、电、油限量的约束和产量非负的约束,表示为:其标准形式为其中,为松弛变量。用单纯形表解题: 表3 7 12 00 0 94 1 0 0 36090 4 5 0 1 0 200 40 3 10 0 0 1 30030 0 0 0 0 1 0 240 0 0 1 5020 1 0 0 301000 00 0 0 1 84 1 0 0 20 0 1 0 24由单纯形表求得的最优解为;所以最优解为。3 01规划 3.1 模型的建立整数规划指的是决策变量为非负整数值的一类线性规划,在实际问题的应用中,整数规划模型对应着大量的生产计划或活动
11、安排等决策问题,整数规划的解法主要有分枝定界解法及割平面解法。0-1整数规划是整数规划的特例,其数学模型的目标函数、约束条件与线性规划相同,所不同的是如果整数线性规划问题的所有决策变量仅限于取0或1两个值,则称此问题为0-1整数规划,简称为0-1规划,把只能取0或1值的变量称为0-1变量。其一般的数学模型为3 :其中为0-1变量,也称二进制变量、逻辑变量。仅取值0或1这个条件可由下述约束条件所代替。,为整数,它和一般整数线性规划的约束条件形式是一致的。另一种形式为4:引进0-1变量:及资源单位数向量:则可建立与实际相应数学模型: 这两种是常见的0-1规划模型,可用隐枚举法求解,有时为了求解更加
12、快捷、方便则通常用LINGO软件求解。3.2 求解方法(1) 隐枚举法求解 解0-1型整数规划最容易想到的方法,和一般整数规划的情形一样,就是穷举法,基本上此法可以从所有变量等于零出发(初始点),然后依次指定一些变量取值为1,直到获得一个可行解,于是把第一个可行解记作迄今为止最好的可行解,再重复,依次检查变量为0,1的各种组合,对迄今为止最好的可行解加以改进,直到获得最优解。这就需要检查变量取值的个组合。对于变量个数较大(例如),这几乎是不可能的。而隐枚举法就是在此基础上改进的,通过加入一定的过滤条件,使运算次数减少,从而较快的求得最优解。因此常设计一些方法,只检查变量取值的组合的一部分,就能
13、求到问题的最优解,这样的方法称为隐枚举法。其解题关键是寻找可行解,产生过滤条件(满足目标函数值优于计算过的可行解目标函数值的约束条件)。一般步骤为:1)、用试探法求出一个可行解,以它的目标值作为当前最好的值;2)、增加过滤条件;3)、将 按由小大排列。最小化问题反之。(2) 用LINGO求解5LINGO:Linear Interactive and General Optimizer 即“交互式的线性和通用优化求解器”,它是一种专门用于求解最优化问题的软件。1)程序语言说明: LINGO程序以“MODEL”开始,以“END”结束,它们之间由语句组成,并且每个语句都是以分号“;”结尾。 在LIN
14、GO中语句顺序不重要,程序中不区分大小写,变量必须以字母开头,以开头的都是函数的调用。 LINGO已假定所有变量非负,可用限定变量取值范围的函数BIN(X)(限定X为0或1)、GIN(X)(限定X为整数)、FREE(X)(取消对X的符号限制)、BND(L,X,U)(限制)改变变量的非负假定。2)逻辑运算符:#AND#(与),#OR#(或),#NOT#(非),#EQ#(等于)、#NE#(不等于)、#GT#(大于)、#GE#(大于等于)、#LT#(小于)、#LE#(小于等于)。3)利用 LINGO 对上面第二种模型进行编程求解,其部分程序语句如下(省略号处表示有部分程序语句省略): 模型的设置部分
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 资源 分配 问题 求解 方法 要点
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。