有约束条件下的整数规划模型及其应用(2)
时间:2018-10-07 17:50 来源:毕业论文 作者:毕业论文 点击:次
4.3.1 基本假设 20 4.3.2 符号说明 21 4.4模型建立及求解 21 4.4.1 预测本届会议参会人数，确定需要预订的各类客房的总量 21 4.4.2 选择宾馆，预定客房 24 4.4.3 预订会议室以及制定租车方案和绘制行车路线 28 4.4.4 制定租车方案 30 4.4.5 绘制行车路线 30 4.5 模型推广 32 结 论 33 致 谢 34 参考文献35 附录A 第4章中的相关原始数据 36 附录B 文中的lingo程序 38 1 引言 1.1 研究整数规划的背景及意义 一般来说，在有些线性规划问题中，我们得出的最优解往往是分数和小数，然而，在实际生活问题中，由于问题本身具有的特殊性，一般要求我们求出来的部分变量的最优解必须是整数。比如：当我们研究的变量代表客运站的个数或者是某个厂机器的台数时，自然而然，题目中已经隐含了该变量的取值应为整数。而这种变量的全部或者部分取整数的线性规划一般统称为整数线性规划 （简称为“IP”问题）。其中，变量全部取整数的线性规划称为纯整数线性规划。而只要求一部分变量取整数的线性规划称为混合整数线性规划。另外，在严格意义的层面上讲，每一个整数规划问题都应该被看做是非线性的，因为，整数规划的函数是由一些离散的点构成，而这些离散的彼此之间是分来的，并不能用直线或者曲线连接起来。然而，从研究整数规划（最优化）问题的观点看，相比较而言，忽略这种技术细节会显的更有意义。这就是说，我们将一个整数问题归结为线性，然后将部分变量的限制条件放松后函数仍然会是严格线性的，否则，称问题是非线性的。而这样的分类基础为以后研究整数规划问题的解法提供了重要的理论基础。 上述研究意义层面上的整数规划（最优化）并不是一个新的数学议题，只不过，在20世纪40年代末到50年代初运筹学被广泛应用之前，所谓研究的整数规划问题多数是纯数学问题，比如我们经常在概率统计上遇到的在一个平面图形中，在使用最少的颜色的前提下区分任意两个公用同一边界段区域的问题，以及N个平面能把一个三文空间最多分出多少块数的问题。令人惋惜的是，和连续数学不同，整数规划很少有统一的理论产生，而我们研究的只不过是一些特殊的情况罢了。 然而，随着时间的推移，由于实际问题的复杂性以及计算的繁杂性，逐渐地，人们更多的是希望通过计算机来完成这些繁琐冗杂的计算，这个时候整数规划（最优化）这个“桥梁”就变得至关重要。慢慢地，相关研究人员和专家认识到了求解全部或若干决策变量为整数的最优化模型的必要。自此，各种应用领域的重要问题都被开发出相关的整数模型。如果追本溯源的话，我们不难发现，第一个求解线性的整数规划问题的模型是1958年由Gomory研究出来的。 作为纯整数规划重要的一部分，0-1整数最优化具有广泛的应用背景，比如求最小价值，这类问题说的是对于一个总体积为V的背包，总共有N件物品，求选出哪几件物品，使背包的价值最小。求解这类问题是我们通常会引进0-1变量（逻辑变量），从而可以将“是”用1表示，而“非”用0表示。而逻辑变量又是整数中使用最活跃的那部分，他可以将类似“白天”和“黑夜”、“成功”与“失败”等相互对立事件数量化，然后将这种问题的0-1变量放到同一个整数规划模型中来研究。帮助管理者们回答管理中的一些二元决策问题。除此之外，道路工作者所关心的线路设计问题、厂址选择以及人员安排等等，都可以化为0-1规划问题解决，由于有了这种需求，将整数规划问题一般化、模型化变得尤为重要。 (责任编辑：qin) |