基于单纯形法的LINGO求解一般指派问题的探讨

/CHINAMANAGEMENTINFORMATIONIZATION CHINAMANAGEMENTINFORMATIONIZATION //CHINAMANAGEMENTINFORMATIONIZATION CHINAMANAGEMENTINFORMATIONIZATION //CHINAMANAGEMENTINFORMATIONIZATION CHINAMANAGEMENTINFORMATIONIZATION //CHINAMANAGEMENTINFORMATIONIZATION CHINAMANAGEMENTINFORMATIONIZATION / !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! [收稿日期]2007-09-18 最优路径:0→5→3→2→0 0→6→9→4→7→8→1→0 回路总开销:28 四、结 论 本文在VC环境下编程,实现了绿色运输的路径优化 问的遗传算法,程序在VC7.0中调试通过,并通过实例 分析得出用VC实现遗传算法具有可行性和有效性。可见, 在VC环境下使用绿色运输的路径优化遗传算法程序,能 够很好地解决实际问题,真正实现对路径优化问题的分 析。 主要参考文献 [1]叶萍.绿色供应链管理的系统研究[J].经济经纬,2005,(2). [2]弓晋丽,程志敏.物流配送路径优化问题遗传算法的实现[J].物 流科技,2005,(12). [3]任春玉,王晓博.基于改进遗传算法的 TSP问题优化研究[J].物 流科技,2006,(9). [4]周涛.基于改进遗传算法的 TSP问题研究 [J].微电子学与计算 机,2006,(10). 中 国 管 理 信 息 化 ChinaManagementInformationization 2008年3月 第11卷第6期 Mar.,2008 Vol.11,No.6 基于单纯形法的LINGO求解一般指派问题的探讨 刘 勇,陈国东,周 游 (成都理工大学 信息管理学院,成都 610059) [摘 要]本文首先介绍一般指派问题的数学模型和求解方法,然后详细给出利用单纯形法求解一般指派问题的步 骤,并设计了基于单纯形法的指派问题算法流程,最后通过LINGO对指派问题的应用实例进行了求解。运行结果 明:LINGO软件程序设计灵活,能快速准确求解指派问题。 [关键词]指派问题;单纯形法;LINGO [中图分类号]F270.7;F224.0 [文献标识码]A [文章编号]1673-0194(2008)06-0086-02 1 引 言 在日常生活和企业生产经营管理工作中,经常面临着 给人分派工作、给机床指派加工任务等一般指派问题。指 派问题的主要研究方法是定量化、系统化和模型化方法, 特别是运用各种数学模型和技术来解决这类问题。在实际 中遇到的问题一般规模比较大,即使建立了模型,找到了 求解的方法,对于庞大的计算量也是望而却步。“工欲善其 事,必先利其器”,有一个方便的求解最优化问题的工具极 为重要。LINGO是一个利用线性规划和非线性规划来简洁 地阐述、解决和分析复杂问题的简便工具,其特点是程序 执行速度快,易于输入、修改、求解和分析数学规划问题, 对于线性规划(LP)、二次规划(QP)、非线性规划(NLP)问 题,LINGO工具可以给出解决相应问题的方案。本文力图 利用LINGO工具,探讨求解一般指派问题。 2 一般指派问题的数学模型 一般指派问题 (AssignmentProblem)是指有m项任 务,需要有n个人来承担,由于各人的专长不同,各人完成 的任务不同,导致其效率也各不相同。因此,需要科学地指 派任务,使完成m项任务所消耗的总资源最少(或总体效 益最优)。根据m、n之间的数量关系,指派问题可分为3种 情况进行论述。 第一,当m=n时,即为每个人都被指派一项任务; 第二,当m>n时,即任务的数量大于人的数量。这时 可虚设(m-n)个人构成一个m×m的效率矩阵,并且这(m- n)个人在执行m项任务时的成本最高; 第三,当m0,j=m+1,⋯,n中,若有某个σk对应xk 的系数列向量Pk≤0,则此问题是无界的,停止计算。否则, 转入下一步。 Step4根据maxσj=σk(σj>0),确定xk为换入变量, 按θ规则计算: θ=min bi aik aik># $0=blalk 可确定xl为换出变量。转入下一步。 Step5以alk为主元素进行迭代 (即用高斯消去或称 旋转运算),把xk所对应的列向量 Pk= a1k a2k⋯ alk⋯ amk % & & & & & & & & & & & & & & ’ ( ) ) ) ) ) ) ) ) ) ) ) ) ) ) * 转换为 0 0⋯ 1⋯ % & & & & & & & & & & & & ’ ( ) ) ) ) ) ) ) ) ) ) ) ) *0 将XB列中的xl换为xk,得到新的单纯形表。重复 Step2~Step5,直到终止。 4 LINGO程序实现 例 4个工人被分派做4项工作,

规定

关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定

每人只能做一 项工作,每项工作只能一个人做,现设每个工人做每项工 作所消耗的时间如表1,求总耗时最少的分派方案。 表1 工作效率表 LINGO程序求解过程如下: Step1构造两个集合。 sets: !4个工人,4个工作的分配问题; Person/1..4/; Job /1..4/; Assign(Person,Job):c,x; endsets Step2构造目标函数。 min=@sum(Assign:c*x); Step3构造约束条件。 @for(Person(i):@sum(Job(j):x(i,j))=1); @for(Job(j):@sum(Person(i):x(i,j))=1); Step4求解结果。 LINGO采用单纯形方法,经过7次迭代,得出全局最 优解70,指派矩阵为: 1000 0001 0010 0100 + , , , , , , ,, - . / / / / / / // 0 ,指派安排如下:工作 1→工人1,工作2→工人4,工作3→工人3,工作4→工人 2,总耗时为70。 5 结 语 通过本实例可以看出,LINGO是一个利用线性规划 和非线性规划来简洁地阐述、解决和分析复杂问题的简便 工具。其特点是程序执行速度快,易于输入、修改、求解和 分析数学规划问题。另外,用单纯形法求解线性规划问题 所需的迭代次数主要取决于约束条件的个数。现在一般的 线性规划问题都是应用单纯形法标准软件在计算机上求 解。 主要参考文献 [1]甘应爱,田丰等.运筹学[M].北京:清华大学出版社,1990. [2]黄雍检.Matlab在经济管理中的应用[J].湖南大学学报:自然科 学版,2005,32(2):121-124. [3]白国仲,陈雯,苏芳荔等.基于特殊需要的指派问题[J].华中师范 大学学报:自然科学版,2006,40(3):305-309. ⋯ ⋯ ⋯ ⋯ 工作1 工作2 工作3 工作4 工人1 15 18 21 24 工人2 19 23 22 18 工人3 26 17 16 19 工人4 19 21 23 17 企业管理信息化 87