毕业设计（论文）-最佳任务分配模型设计.doc

济南大学毕业设计1 前言1.1 课题研究背景随着市场经济的全球化，企业市场竞争变的越来越激励，为了生存，企业的生产规模在不断的扩大，而生产过程中的分工也越来越细，这就要求生产组织对资源分配要有高度的计划性、合理性和经济性，在追求整体的生产效率和效益的同时，也要不断的追求生产成本的最低性。要想达到这样的目的，就要求企业要充分利用现有的人力资源，提出出最经济、最合理的任务分配方案，以减少成本、降低浪费、提高经济效益为目的，才能让企业在经济全球化进程中立于不败之地。运筹学是一门应用分析、量化、优选的方法对经济管理系统中的人、财、物等资源进行统筹安排的学科，它能为决策者提供有定量依据的最优方案，以实现最有效的管理。运筹学前期必修课程包括微积分、线性代数、概率论与数理统计等基础理论知识，在实际应用中，运筹学涉及的面也是很广的。可以说，运筹学是软科学中“硬度”较大的一门学科，兼有逻辑的数学和数学的逻辑的性质，是现代经济管理科学中的基础理论和一种不可缺少的方法、手段和工具；它是抽象的数学理论与丰富多彩的实践相结合的“桥梁”；它为从事生产社会实践和应用科学研究领域的工作人员提供了一套完整的数学方法，也为从事数学等理论研究的科研人员提供了广阔的应用领域。运筹学从确定目标、制定方案、建立模型、制定解法都有一整套严密科学方法。自二战以来，国内外有很多国家都利用运筹学来解决本国的实际问题，在此过程中为各国节省了大量的人力、物力、财力等资源。在这个过程中运筹学也得到了许多的发展和研究，现阶段国内外很多公司都能很好地运用运筹学来解决任务分配问题以及其他问题。从21世纪的发展战略上来看，势必将是计算机的时代。各个领域都将会越来越依赖社会的整体科技创新能力和由此派生出来的知识经济，随着计算机的不断发展，人们逐渐地将计算机知识运用到其中。许多的问题都是依靠科学来建模，而用计算机来对模型进行求解。本次设计就是用运筹学的知识建立的一个任务分配的模型，在掌握数据结构及其算法的基础上，将数据由VB向VC+转变，并在VC+6.0中实现最佳任务分配模型程序的设计和运行。在国外，有很多大公司都将运筹学建模能力与计算机语言结合起来，实现了对现有的资源优化配置和任务的合理分配，从而实现了企业的理想目标。新中国成立后，我国对运筹学也开始逐渐注重，并用运筹学知识为我国解决了许多在管理、决策方面的问题，特别在解决多任务分配问题上，为决策人员节省了宝贵的时间，为企业节省了大量的资源。虽然近几年，运筹学在我国发展比较快，但在运用和解决问题的能力上我们还与发达国家存在一定的差距。比如资源的优化配置程度不高，在生产过程中还有很多不必要的浪费，任务分配不合理等现象还大量存在。1.2 设计的内容与意义假设有n个人，准备承担m项工作（n=m），每个人只能承担一个任务，其中有的人不都能承担个别任务，并且每个人承担每个工作时的费用是已知的，要求制定一个任务分配方案，使所有完成任务所消耗的总费用最少。本选题的目的就是为了解决实际生产过程中的最佳任务分配问题，以运筹学的科学计算法为基础，建立一个任务分配的模型，在掌握数据结构及其算法的基础上，将数据由VB向VC+转变，并用C+语言实现最佳任务分配模型的程序设计，通过运行程序解得我们想要的最佳任务分配方案，以达到对资源及各种项目的优化目的，从而达成理想的目标。通过本次设计，不仅能让我们更多的了解和掌握运筹学的基础知识，还能提高我们分析问题、解决问题的能力；大大地提高了我们的建模能力，进一步掌握了一门新的语言（VC+）和数据结构及其算法。1.3 设计的方法与步骤本次设计所用的主要算法是回溯法，设计的步骤大致可分为八步：（1）确定问题和分析问题；（2）建模；（3）编程；（4）求解模型；（5）界面设计；（6）试调；（7）测试；（8）封装。2 运筹学的应用与发展2.1 运筹学释义与发展历史运筹学一词起源于20世纪30年代，运筹学最早起源于英国。在英国，运筹学一词被称为operational research,据大英百科全书释义，“运筹学是一门应用于管理有组织系统的科学”，“运筹学为掌管这类系统的人提供决策目标和数量分析的工具1”。在美国，运筹学被称为operations research(缩写为O.R.)，可直译为“作业研究”或“运用研究”。其实简单、朴素的运筹学思想在我国古代文献中就有很多记载，例如丁渭主持修复皇宫和田忌赛马等事。在1957年我国从“夫运筹帷幄之中，决胜千里之外”（见史记高祖本纪）中摘取出“运筹”二字，将O.R.正式译作运筹学，它包含运用筹划，以策略取胜等意义，比较恰当地反应了这门学科的性质和内涵。辞海（1979年版）中将有关运筹学的条目释义为：主要研究经济活动与军事活动中能用数量来表达有关运用、策划与管理方面的问题，根据问题的要求，通过数学的分析与运算，做出综合性的合理安排，以达到经济有效地使用人力物力财力等资源。中国企业管理百科全书（1984年版）中的运筹学被释义为：应用分析、试验、量化的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最快最有效的管理1”。运筹学的发展主要是在二战以后，它将活动扩展到了工业和政府部门等相关部门，其发展大致可以分为以下三个阶段1：（1）从1945年到20世纪50年代初，被称为创建时期。特点是：从事运筹学研究的人少，范围不大，运筹学的出版物、学会、研究所等寥寥无几。（2）从20世纪50年代初期到50年代末期，被称是运筹学的成长时期。此阶段的主要特点是：随着电子计算机技术的迅速发展，使得运筹学中一些方法例如单纯形法、线性规划法、动态规划方法等，解决了实际管理系统中的优化问题，促进了运筹学的推广应用和发展。（3）自20世纪60年代以来，被称为是运筹学的普及和迅速发展时期。特点是：运筹学被进一步细分为各个分支，各个专业学术团队都迅速增多，也有了更多的期刊创办，同时运筹学的书籍也大量出版和被更多学校将运筹学课程纳入教学计划之中。2.2 运筹学研究的基本特征基本方法运筹学研究的基本特征科可概括为：系统的整体观念、多学科的综合、以及模型方法的应用1。系统的整体观念可以理解为：具有相互关联、相互制约和相互作用的部门组成的具有某种特定功能的有机整体。因为在运筹的研究过程不是对各个子系统的决策行为进行孤立的评价，而是把相互关联的子系统的决策结合起来考虑，把相互影响和制约的各个方面作为有机的统一体，从系统的整体利益出发，去寻找一个最优化、最协调的方案。多学科的综合可以理解为：由于每个组织或系统的有效管理都涉及很多方面，所以运筹学在研究中吸取了来自各个领域、具有不同经验和技能的专家和学者。这样增强了小组的集体智慧、提出问题和解决问题的能力。这种多学科的协调与配合在研究初期；在分析、确定和解决问题的主要方面，在选定和探索解决问题的途径时，显得非常重要。模型方法的应用是指：各门学科的研究都广泛运用实验的方法，但是运筹学研究系统往往不能在实验室中进行，而是用建立这个问题的数学模型或模拟模型来代替。其中制定决策和提供科学依据是运筹学的核心，建立模型则是运筹方法的精髓。任何一门学科从研究范围上来讲都大致可以分为四个方面：首先，观察现象得到结果和进行观察时所需的方法；其次，理论和模型的建立；再次，讲观察的现象与理论想结合，并从观察到的结果中得到预测；最后，把预测的与先观察到的想比较，并加以证实。而在运筹学中也不例外，我们将运筹学的研究步骤划分为以下六:。（1）表述和分析问题；（2）建立模型；（3）求解模型和优化方案；（4）测试和修正模型；（5）建立对解的有效控制；（6）方案的实施1。3 数据结构与C+界面设计3.1 数据结构与算法当谈论到算法时，很自然的就会涉及到算法所需处理的数据问题，然而，在讨论数据的结构和组织时，如果离开了对此类数据的算法及其运算的研究，那么这个研究是没有意义的。有人将程序描述为：程序=算法+数据结构3.1.1 数据结构定义由数据元素依据某种逻辑关系组织起来的结构我们成为数据结构。这种对数据元素间的关系描述我们称为数据的逻辑结构，数据结构的实现形式是数据的存储结构，就是说它在计算机内的表示；此外，讨论数据结构时必须同时讨论该类在数据上的运算才有意义。下面介绍数据结构中的几个基本概念：（1）数据（data）：笼统地说数据就是计算机加工处理的对象。它分为两类：数值数据（numerical data）和非值数据（non-rical data）。其中，数值数据一般是指整数、实数或复数，它主要用于商务处理、工程计算和工程计算。而非数字数据则包括文字、图像、图形、字符、表格和语音等。（2）数据对象：它是实例或值的集合。（3）数据的逻辑结构：由于数据结构是由数据元素见依据某种数据关系组织起来的，那么，这种数据元素间的逻辑关系的描述我们称之为数据的逻辑结构。用二元组表示为：DS=（D,R） （3.1）其中，D是数据元素的有限集合，R是D中元素序偶的集合。依据数据元素间关系特征的不同，将数据的逻辑结构划分为四类基本逻辑结构，即序列结构或线性结构、集合结构、图状结构和集合结构。3.1.2 算法什么是算法？简单的说就是求解问题的方法；也可以笼统的说成是求解一类问题的任意一种算法；但严格的讲：算法是指对特定问题求解步骤的一种描述，是指令的优先序列。其中算法的特征有五个：（1）输入（input）：可以有零个或多个输入；（2）输出（output）：至少要有一个输出；（3）确定性（definiteness）:每一条指令都要有确定的定义和没有二义性；（4）能行性（effectiveness）每条指令都必须是最基本的，并且它们可以通过执行有限次基本运算来实现；（5）有穷性：算法必须在执行有限步之后停止，不能成为死循环2。3.2 数组数组是数组变量的简称，它是指一组具有相同数据类型的变量的集合。数组中的每一个数据都是一个元素，我们称之为数组元素。数组元素之间都有固定的先后顺序，所以对于数组来说只要知道了它的数组名和下标就可以确定数组元素。由于数组是一种大家都非常熟悉的数据类型，在数据结构讨论中，通常使用数组来描述数据结构的顺序表示，即使用数组来实现数据的顺序存储结构。数组有一个特点就是一旦定义就不能再添加和删除元素。在这里，我们只讲二维数组，二维数组的一般表示为：数据类型 数组名常量表达式1常量表达式2；其中，常量表达式1表示的是数组的行元素，常量表达式2表示的是数组的列元素。二维数组的下标是二维的，可以认为二维数组是每个元素是一维数组的一维数组。二维数组映射到一维存储空间是一般有两种顺序：列优先顺序和行优先顺序。像Pascal、Basic、C和C+等大多数高级语言都是按行优先的顺序存储。在Fortran中就是按列优先顺序存储的。先设有m行n列的二维数组，它的第一个数组元素a00的存储地址为Loc（a00）,每个元素占k个存储单元，那么数组元素aij的存储地址Loc(aij)为:Loc(aij)=Loc(aij)+(i*n+j)*k 其中0im;0jn2 （3.2）3.3 堆栈堆栈简称栈（stack），它是一种限定插入和删除运算只能在同一端进行的线性数据结构。其中允许删除和插入的一端叫做栈顶（top），另一端则称为栈底（bottom）。当栈中没有任何元素时我们称之为空栈。栈的特点是后进先出（LIFO），即若给定栈S=(a0,a1,an_1,）其中a0称为栈底元素，an_1称为栈顶元素。如果在进栈时是从依次进展的话，那么在出栈时恰好相反，从an_1到a0依次出栈。栈的基本运算可包括为：（1）构建一个空栈；（2）判断一个栈是空栈还是满栈；（3）栈的基本操作；即在一个未满战中插入一个新的元素或在一个满栈中删除栈顶元素。当然，在需要时，栈还有很多的算法，如清除一个栈、求栈的长度以及遍历一个栈等等2。栈的抽象数据类型的定义：Stack 数据：可以是零个元素也可以是多个元素的线性序列，它最大允许的长度为MaxStackSize。运算：Void Create（）/后置条件：已构成一个空栈Void Push（const T&x）/前置条件：栈未满；后置条件：新元素x进栈并成为栈顶元素Void Pop（）/前置条件：栈非空；后置条件：从栈中删除栈顶元素T Top（）const /前置条件：栈非空；后置条件：返回栈顶元素的值BOOL IsEmpty（）const /后置条件：若栈为空栈，则返回TRUE，否则返回FALSEBOOL IsFull（）const /后置条件：若栈已满，则返回TRUE，否则返回FALSE2由于数据存储的表示方式有两种：顺序表示和链接表示。所以在堆栈的表示也有两种:堆栈的顺序表示和链接表示。其中顺序表示是存储一维数组时的表示方法，当然他也可以用链接来表示，只是没有这个必要，因为顺序表示比链接表示要简单和方便的多。3.4 回溯法当一个问题的解可以表示成一个n-元组（x0,x1,xn-1）时，要求求出满足约束条件的可行解或进一步求使目标函数取最大（最小）值的最优解时，大部分的问题都可以用回溯法求解。3.4.1 基本术语（1）约束条件；约束条件是指问题在开始时给出的用于判断一个候选问题是否是可行解。当解满足约束条件时我们称它为可行解，把给定的数值函数称之为目标函数，把用来衡量每个可行解的优劣，即使目标函数的取值最大或最小的可行解。（2）显（隐）式约束；将直接明显限定每个取值的约束条件叫做显式约束，将一些隐藏的的约束条件叫做隐式约束。（3）解空间；对于已给定的实例，满足显式约束的所有可能元组组成的问题候选解集，即对于一个问题实例，所有满足显式约束的元组解的集合称为解空间。（4）成本函数；在解决最优化问题时，问题还需给出一个数值函数作为目标函数，我们把这个给出的函数称为成本函数。当判断一个解是不是可行解时，只要看它能不能使成本函数最大或最小即可。3.4.2 状态空间树在讨论问题时，我们可以解的空间描述为一棵树，这个描述问题解空间的树的结构称为状态空间树。图3-1是n=3的一种状态空间树。树的每个结点称为一个问题状态，对于树中的一个问题状态，如果从根到该结点代表一个候选解的话，那么就成该问题的状态为解状态2。如图3.1中，每个叶结点都是解状态。17122351513810161496411图3.1 n=3的空间状态树3.4.3 回溯法思想通过前面的介绍，我们知道用回溯法求解的问题的解的空间是用一颗状态空间树来描述的，那么很显然，我们就可以通过搜索空间状态树的方法来求解状态。其中一种最简单的做法是：使用一种叫树搜索的方法，当访问树中的每一个问题状态结点时，如果是解状态，则用判定函数来确定每个解状态是不是答案状态。如果是最优化问题，还可以在搜索过程中不断的替代可行解，使目标函数最大或最小，以达到最优解。事实上，状态空间树并不需要事先就生成，而只需在求解过程中随着搜索算法的进展，逐步生成空间树的所有结点。如果我们在搜索的过程中使用一个叫做限界函数的布尔函数去限制那些不可能包括的子树答案状态，这样就可以大大的减少访问的树中的结点。综上所述，回溯法是指使用限界函数的深度优先生成的状态空间树中结点的方法。其中由广度优先生成的结点，并使用了限界函数的方法我们称之为分支限界法。3.4.4 回溯法的算法结构设（a0,a1,ak-1）是状态空间树从根到某个问题状态的路径，M( a0,a1,ak-1 )是所有结点Z的集合，它可使得Z中的每个ak都是一条从根到Z的路径，Nk(a0,a1,ak-1)是界限函数，如果上述的结点Z，akM( a0,a1,ak-1 )且Nk(a0,a1,ak-1)，那么需要检测以Z为根的子树，不然将不能生成以Z为根的子树上的所有问题结点。状态空间树的任意一个叶结点X，集合M为空集2。其实回溯法的本质是按照深度优先的方式一个一个地生成状态空间树的结点，并且通过限界函数来检测那些结点是答案的结点，如果不用限界函数检测的话，就变成了穷举法，所以说回溯法的优点就是使用了限界函数剪去了那些不是答案的结点，从而提高了算法的效率。3.5 Visual C+简介计算机科学的每一步发展几乎都是在程序设计语言和软件设计中得到体现。像C+、Objective C、Eiffel、Smalltalk等面向对象程序设计语言是在20世纪80年代才日趋成熟，才被广泛应用到程序设计当中，并且从这以后也有了许多新的发展，归纳起来可分为两大类：一类是纯面向对象的语言；另一类是混合型的面向对象语言，其中C+则属于混合型的面向对象语言。3.5.1 C+的特点与发展C+语言是由AT&T公司的贝尔实验室的Bjarne Stioustrup博士开发的，它是一门高效实用的混合型面向对象的程序设计语言，它最初的设计目标是支持面向对象编程技术和支持抽象形态的类。C+语言有两个部分组成：一是基础部分，它是C+语言的核心，它的核心是C语言，但又不完全等同于C语言，因为在它保留了C语言优点的同时又是C语言的加强版，像C语言的语言能力强、风格简洁、效率高和C语言的函数库都被保留了下来，这也是C+能与C语言得以完美兼容的主要原因。当然，在继承了C语言优点的同时，C+语言对C语言进行了扩充，克服了C语言完全面向过程的缺点，使它变成能完全支持面向对象的程序设计语言。它最大的特点就是能够支持类的概念。同时也支持像派生、继承和多态性等层次结构。类是由用户定义的一种对数据进行封装和对这些数据进行操作的函数。类使得抽象数据类型得以描述。除此之外，；类还为数据提供隐蔽，这就确保了程序的可靠性、稳定性和可维护性。Visual C+的发展经历了Visual C+1.0、Visual C+1.5、Visual C+2.0、Visual C+4.0、Visual C+5.0、Visual C+6.0，随着版本的更新，其功能已日渐完善。3.5.2 C+程序的结构要想编写一个程序，我们必须了解和掌握程序的结构，对C+来说，它程序的基本框架可大致分为三部分：声明区、主函数和函数定义区。（1）声明区声明区的位置是在现有程序的所有函数的外部，但并不是说每个程序都需要有声明区，要视情况而定。它所包含的内容一般有以下几种情况：1.包头文件：如#include；2.宏定义：如#define PI 3.14159；3.函数声明：如int add(int,int)；4.结构体定义:如struct record；5.类定义:如class name；6.条件编译:如#ifdef；7.全局变量声明3。为了使程序的结构清晰，我们一般将声明区放在一个源代码文件中，这个文件就是我们常说的头文件，头文件是系统提供的，用户可以直接调用，当用户需要某些特殊的函数时，也可以自己编写头文件。（2）主函数区每一个程序都是有很多个函数组合而成的，但主函数只有一个，其中主函数区是以main（）函数开始，是整个程序运行的入口。函数中可能包括下面的内容：1.函数调用：如int m=add（x，y）；2.局部变量的声明：int i，j；3.结构控制：if（mn）m=n；4.系统函数调用；5.一般的运算：b=1；6.对象与结构的处理等3。（3）函数定义区程序中除了主函数外，其他的函数差不多都需要用户自己定义，并且定义函数时函数名既不能与系统函数重名也不能与已定义的函数重名。每个函数都是有两个部分组成：函数的说明部分和函数体部分。函数的说明部分主要是定义函数的类型、函数名和函数的参数类型和参数名；函数体部分主要是实现函数的具体功能，它是由一对括起来的语句集合。4 问题的描述及其解决方案随着市场经济的全球化发展，企业的竞争越来越激励，企业要想在竞争中立于不败之地，就要不断的降低自己产品的价格，降低价格的途径可概括为两条：降低原材料的价格和生产成本。如果采用降低原材料价格的方法，那么产品的质量就会下降，这是企业在生产过程中最忌讳的，因为质量是企业生存的根本，所以可以说这个方法是不可行的。那就只有采用第二种方法，降低生产成本。降低成本的方法有很多，其中最主要最有效的方法就是合理分配人员13。怎样才能合理分配人员呢？解决的方法很多，其中用运筹学的知识来求解是最简单最方便的.因为运筹学具有很强的建模能力，它能将人员分配问题变成一个二维的数组模型，通过对二维模型的求解来获得最佳的任务分配方案。4.1 问题的内容与要求（1）问题的主要内容：现假设有n个人，准备去承担m项工作（nm），每个人只能承担一个任务，有的个别任务是有的人不都能承担的，且每个人承担每个任务所需消耗的费用是已知的。要求制定一个任务分配方案，使完成所有任务所消耗总费用最少。（2）要求：要求在VC+环境下做一个输入输出界面，使其能在windows下运行，用户只需在windows环境下启动程序之后，输入自己的人数、任务数和他们每个人做每项工作的所需费用后，点击界面上的输出按钮就能自动链接并启动程序，然后快速地运行出最佳的任务分配方案和消耗的总费用。4.2 问题分析与模型设计通过上面问题的描述可知，参加工作的人数、工作的项目个数和每个人完成每个任务的费用是知到的。那么我们可以通过运筹学的线性关系建立一个二维数组数学模型，它的目标函数可描述为：Min(x1j+x2j+x3j+xnj) 其中n（参加的人数）；jm（任务数） (4.1)现在我们只需求解出目标函数的值并输出相应的解即可，对于这类问题，在以前我们是用人为的科学算法来计算，但只能解决三个、四个人参加的模型，对于多个的如七个、八个的就没法计算了，而现代我们可以将它转变成计算机语言，借助于计算机计算来解决这个问题，这样就好多了。需要注意的是：考虑到有的人不能承担有的任务，我们将他做这项任务所消耗的费用值用设为0，而在程序的设计和运行时我们可以将它视为无穷大，可以直接跳过这个结点执行下一个解。因为每个人在做任何一项任务时，他所耗费用都不可能为0，所以我们可以将不能承担这项任务的人的费用值设为0。4.3 方案设计的步骤上面已经运用运筹学及其相关的知识对现有的问题做了定性分析，再在此基础上我们可以确立各基础变量、相关变量以及各变量之间的关系15。从而建立一个任务分配的数学模型。通过数据结构及其算法寻找求解的算法，在确定用回溯发实现最佳任务分配模型求解后，再利用C+来进行编程。最后利用Vision C+进行界面设计，将界面从原来的dos界面改成更人性化的windows界面。程序设计的具体步骤为：（1）确立问题和分析问题；这一步是系统地分析问题和提出问题，确立一个系统或对现有系统的详细分析开始，通过分析找到影响系统的最主要因素。另外，通过分析，还要明确系统或组织的主要目标，找出系统的主要变量和参数，弄清变化范围、相互关系以及对目标的影响。在问题提出后，还要分析解决该问题的可能性和可行性。一是要确定决策目标，即明确决策的对象是什么，选取上述决策的有效性度量以及在方案比较时这些度量的权衡；二是要辨认哪些因素是决策中的关键因素，在选取这些关键因素时存在哪些资源和环境的限制11。（2）建模；在对问题进行定量分析和表达之后，利用运筹学知识建立一个任务分配的模型，以C+语言为基础，结合数学、数据结构方面的知识来更精确、科学的表述问题，将运筹学模型转变成计算机模型。（3）编程；使用C+语言实现栈的定义、数组的输入、输出和数据结构的解的算法。（4）求解模型；在上述结构语言都实现之后，将他们组合成一个系统，通用输入相应的数据后让模型对其进行求解。（5）界面的设计；建立一个Vision C+的对话框，其中应包含输入、输出、数据显示等控件，并且让这些控件与程序中函数实现调用。（6）调试；将总程序在Vision C+.6.0中运行调试，确保程序的可运行性。（7）程序功能测试；在程序写完后或在写程序之前，我们必须要准备多组数据（已知道分配结果）来对程序进行测试。最后将运行出来结果与理想结果相比较，以此来确定程序的准确性。（8）封装；对程序进行外观包装和编写说明书或使用手册。这种以机代替人的方法已成为现代社会发展的主流，只有充分利用高端的计算机技术对企业的现有资源进行优化配置，才能实现企业预期目标。在生产过程中要以运筹学的建模功能为桥梁，实现科学管理与计算机科学的完美结合，为现代管理学注入新理念和思想。在既保证了质量的同时，又大大的提高了企业的生产效率，从而减少了决策人员和工作人员的工作量。最后达到降低生产运营成本的目的。5 程序设计通过前面的陈述与分析，我们明白了本次设计的要求、目的以及内容。现在的工作就是编写详细的程序，程序设计的整体框架如图5.1。声明区栈的定义编辑文本文档读取数组数据显示数组数据回溯法求解模型界面设计图5.1程序设计的整体框架本程序设计时主要采用的是模块化结构程序设计思想，将模型主要分为栈的定义、数组的实现与输入、数组的显示、算法的实现与输出和界面的设计五大板块。图5.2为本次设计的模块分类。最佳任务分配模型界面设计数组的显示回溯法求解数组实现栈的定义结果的输出算法的实现打开文档数组编程图5.2模型的分类5.1 栈的定义由于栈是所有存储容器中最简单的数据结构，所以在本程序设计时我们也用栈来存储数据结构。栈的一些理论和定义在第四章我们已经介绍了，在这里我们就不在累述了，下面的程序就是本程序对栈的定义和处理。#if !defined(AFX_H_STACK_INCLUDED_)#define AFX_H_STACK_INCLUDED_#include common.h/栈初始条件的定义#define STACK_INIT_SIZE 100/栈初始长度的定义#define STACKINCREMENT 10 /栈每次追加分配长度的定义/定义栈的数据类型（整型）typedef structSElemType *elem;int top;int stacksize;Stack;/栈的各项操作的实现status InitStack(Stack &s)/栈的初始化s.elem=new SElemTypeSTACK_INIT_SIZE;if (!s.elem) return OVERFLOW;s.top=-1; /表示空栈s.stacksize=STACK_INIT_SIZE;return OK;/销毁栈status DestroyStack(Stack &s)delete s.elem;s.top=-1;s.stacksize=0;return OK;/判断栈的存在status ClearStack(Stack &s)/当栈存在时将栈清空，当栈不存在时返回出错信息if (!s.elem) return ERROR;/栈不存在s.top=-1;return OK;/判断栈是否为空栈status StackEmpty(Stack &s)/判断栈空与否，当栈为空栈时返回TRUE，否则返回ERROR./当栈不存在时返回出错信息if (!s.elem) return ERROR;/不是空栈if (s.top0) return TRUE;/空栈return FALSE;/栈的长度的返回int StackLength(Stack s)/返回栈的长度/当栈不存在时返回出错信息if (!s.elem) return ERROR;return s.top+1;/栈顶元素的返回status GetTop(Stack s,SElemType &e)/当栈存在且不是空栈空时返回栈顶元素/当栈不存在或栈为空时返回出错信息if (!s.elem) return ERROR;if (s.top0) return ERROR;e=s.elems.top;return OK;/栈的处理status Push(Stack &s,SElemType e)/当栈存在时对栈进行压缩 /当栈不存在时返回出错信息if (!s.elem) return ERROR;if (s.top+1)=s.stacksize) /如果栈的初始空间已满SElemType *temp=s.elem; int i; /为栈重新分配存储空间s.stacksize+=STACKINCREMENT;s.elem=new SElemTypes.stacksize;if (!s.elem) return OVERFLOW; /当栈分配空间失败时返回出错信息for(i=0;i=s.top;i+) s.elemi=tempi;delete temp;s.top+=1;s.elems.top=e;return OK;/退栈status Pop(Stack &s,SElemType &e)/当栈不存在或栈是空栈时返回出错信息if(!s.elem) return ERROR;/当栈存在且不空时退栈if(s.top0) return ERROR;e=s.elems.top;s.top-=1;return OK;/函数的调用status StackTraverse(Stack s,int (*visit)(SElemType &e)/当栈存在且不空时调用visit函数对栈作由底到头的遍历/当visit函数调用失败返回错误信息int i;if (!s.elem) return ERROR;if (s.top0) return ERROR; /当栈不存在或栈是空栈时返回出错信息for(i=0;i=s.top;i+) visit(s.elemi);return OK;#endif5.2 数组数据的实现与读取由于数组的实现要靠读取文本文档中数据，所以这里我们将两个功能放到一起作为一个整体模块来来实现，但在编写程序时我们是可分为两个板块来写。即：（1） 数组的实现模块本程序中的数组是一个二维数组，我们可以用一个for循环中再嵌套一个for循环来完成。它的程序很简单如下：#include void main()int i,j; /变量数据类型的定义fscanf(flp,%d,%d,&cost.m,&cost.n);/人数与任务数的输入/数组的实现for(i=1;i=cost.m;i+)cost.elemi0=-1;for(j=1;j=cost.n;j+)fscanf(flp,%lf,&cost.elemij); /确定数组变量范围（2）数组数据的读取在C+中，要想读取文本文档中的数据，跟C语言一样主要采用指针的方法读取文本文档，它的程序很简单，只要用一个指针函数指向文本文档就可以了。数字数据的读取程序：#include void main()FILE *flp;flp=fopen(text.txt,r); /打开名为text的文本文档5.3 数组数据的显示在本程序中，数组的显示是在一个静态文本框中输出的，它输出的方法与输入的方法大致一，但也有一些不同的地方。下面的程序就是本程序的数组数据输出函数：#include int i;CString str,ss;Stack s;InitStack(s);/人数和任务数的定义ss.Format(人数: %d,任务数: %dn,cost.m,cost.n);str+=ss;for(i=1;i=cost.m;i+)ss.Format(%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lfn,cost.elemi1,cost.elemi2,cost.elemi3,cost.elemi4,cost.elemi5,cost.elemi6,cost.elemi7,cost.elemi8,cost.elemi9,cost.elemi10); /数组的显示5.4 回溯法求解模型回溯法的本质具体的算法在前面我们已经介绍过了，它主要采用限界函数的深度优先生成的状态空间树中结点。从而达到约束函数的满意解。本程序的具体算法为：/各变量的定义int i,j,count; double v,totalCost; Stack s; /s栈的定义 RList a; InitStack(s); InitRList(a); /初始化job数组 for(j=0;j(MAX_D+1);j+) jobj=FALSE; count=0; /定义已分配工作的计数器 j=0; v=0;totalCost=MAXINT; Push(s,j); dowhile(StackLength(s)cost.m)&(j=cost.m)&(count=cost.n)/存储解向量SaveResult(s,totalCost,v,a); if (totalCostv) totalCost=v; /回溯遍历兄弟 if (StackLength(s)0) /如果栈不空退栈Pop(s,j);jobj=FALSE;if (j!=0) v-=cost.elemStackLength(s)+1j;count-=1; /退栈并恢复数据j+=1;while(StackLength(s)0)|(j(cost.n+1);/判定条件CString str,ss;if (a.top!=-1) /栈不是空栈 for(i=0;i=a.top;i+) for(j=1;jSetDlgItemText(IDC_RESULT,str);/在RESULT文本框输出/AfxMessageBox(str,MB_OK);5.5 数组数据的输出其实在总程序中，我们在简单的设置一个按钮之后，然后用一个相当于指针一样的函数调用按钮的地址就可以了，但在后台却是用前面定义的栈来对数据进行处理的。即将上面用回溯法求解出来的解从栈中释放出来。它的详细程序为：#if !defined(AFX_H_RESULT_INCLUDED_)#define AFX_H_RESULT_INCLUDED_#define INIT_SIZE 1000 /解的数组的初始长度的定义#define ADD_SIZE 5 /解的数组每次追加分配长度的定义#define MAX_D 10 /设置矩阵的空间大小 /定义栈的数据元素的数据类型typedef int SElemType;#include stack.h/实现解的数组的数据类型typedef int ResultMAX_D+1;typedef structResult *elem;int listsize;int top;RList;/*实现解的数组的各项操作*status InitRList(RList &a)/初始化解的数组/当为解的数组分配空间失败时返回出错信息a.elem=new ResultINIT_SIZE;if (!a.elem) return OVERFLOW;a.top=-1;a.listsize=INIT_SIZE;return OK;status ClearRList(RList &a)/将解的数据清空，分配的空间保留if (!a.elem) return ERROR;a.top=-1;return OK;status EnElem(Stack s,RList &a)/将栈中的解加入解的数组/当解的数组已满则为数组重新分配空间int i,j;if (!a.elem) return ERROR; /当空间分配失败时返回出错信息if (a.top=(a.listsize-1) /为数组重新分配空间Result *temp=a.elem;a.listsize+=ADD_SIZE;a.elem=new Resulta.listsize;if (!a.elem) return OVERFLOW;/空间分配失败时返回出错信息for(i=0;i=a.top;i+) /将原数组中的解复制进新的数组for(j=0;j=a.elemi0;j+)a.elemij=tempij; delete temp; /释放临时空间/将栈中的解加入解的数组a.top+=1;for(i=1;iM) return OK;if (vol=M) EnElem(s,r);return OK;ClearRList(r);EnElem(s,r);return OK;status OutputResult(RList r)/格式输出解的数组中的各组解/当解的数组为空时则输出提示-无解int i,j;if (r.top=-1) /空栈coutendlNo Answer !;return OK;for(i=0;i=r.top;i+)coutendl;for(j=1;j=r.elemi0;j+) cout(j,r.elemij);/解的输出return OK;#endif5.6 界面设计在本程序设计中，我们共用到了三个按钮：读入数据（OnTextReaddata）、显示数据（OnGetdata）和任务分配（OnAction），五个静态文本：数据读入显示文本框（OnData）、结果显示文本框（OnResult）、结果显示、指导老师和制作人，除此之外还有一个时间选取器，它的具体布局见图5.3。5.7 程序测试程序的测试就是将预先准备好的知道结果的多组数据输入程序中，看看运行的结果跟标准答案相比较，如果相同，则说明程序设计