摘要：背包问题是算法设计分析中的经典问题， 本文给出了一种求解整数背包问题的爬山解法，提出了一个解决此类问题的数学模型。并以具体实例详细描述算法基本思想，通过仿真模拟得出最优解。数值实验表明，该算法简便易行，在其适用范围内具有计算复杂度低等优点。
关键字：线性规划；背包问题；整数规划
1、引言
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料；二是生产组织与计划的改进，即合理安排人力物力资源。线性规划所研究的是在一定条件下，合理安排人力物力等资源，使经济效果达到最优。一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。文章根据线性规划问题在现实生活中的意义进行相关讨论与探究，介绍了线性规划问题产生的背景、特点和实际运用情况，以及线性规划问题在经济生活中运用的意义。
2、线性规划简介
20世纪50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。
线性规划问题的求解可以通过运行Lingo软件来完成。Lingo软件的特色在于其内置建模语言，提供十几个内部函数，而且执行速度非常快。
一般地，使用LINGO求解运筹学问题可以分为以下两个步骤来完成：
（1）根据实际问题，建立数学模型，即使用数学建模的方法建立优化模型；
（2）根据优化模型，利用LINGO来求解模型。主要是根据LINGO软件，把数学模型转译成计算机语言，借助于计算机来求解。
3、线性规划问题在实际中的应用
（1）背包问题的求解
1.1背包问题的定义
已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi，假定将物品i的一部分xi放入背包就会得到pixi的效益，这里，0<=xi<=1，pi>0。采用不同的装包方法将会得到不同的装入背包物品的总效益。由于背包容量是M，因此要求所有选中要装入背包的物品总重量不得超过M，如果这n件物品的总重量不超过M，则把所有物品装入背包自然获得最大效益，如果这些物品的总重量大于M，则需要选取最优解。
1.2背包问题的数学模型
背包问题的数学模型如下：
其中，①式是目标函数，②和③是约束条件。满足约束条件的任一集合（x1，x2...xn）是一个可行解，使目标函数取得最大值的可行解即是最优解。当约束条件xi为正整数时称为整数背包问题，当约定x只取0或1时称为0-1背包问题。
（2）背包问题的仿真模拟
2.1问题的提出
一个人要想旅行必须作好出发前的准备，才不会有危险。
登山队员，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相器材，通信器材等，每种物品的重量及重要性系数见表1登山队员可携带的最大量为25kg，試选择该队员所应携带的物品.
2.2模型的建立
若xi=1表示应携带物品i；若xi=0表示该队员不应携带物品I
因此模型可表达为：
目标函数：Max：Z=20x1+15x2+18x3+14x4+8x5+4x6+10x7
约束条件：s.t.5x1+5x2+2x3+6x4+12x5+2x6+4x7≤25
xi=1或 0，i=1，2，3，4，5，6，7
2.3对模型的计算、分析
对问题进行分析后得到上述模型，现拟利用lingo软件对模型进行求解。将模型输入到lingo软件中，运行软件即得解。
4、结语
整数背包问题的应用十分广泛，对该问题的求解方法的研究无论是在理论上还是实践中都具有一定的意义，在现实生活中类似的问题还有很多，比如管理中的资源分配，集装箱的货物装运，物流公司的货物发配，以及工厂里的材料下料问题等，不胜枚举。本文讨论的求解学习效益问题构成了整数背包问题的一个应用类，其数学模型及算法可以推广，此程序实用性很强，可以用lingo轻而易举地解决该类型的其它一些问题。同时我们对这一算法的性能和计算复杂度与几种求解背包问题的经典方法进行了对比实验，结果表明，本文提出的爬山算法是求解背包问题的有效方法。
参考文献：
[1]唐加冕，周京徽.线性规划问题在经济生活中的应用[J].商业经济，2011（19）：10-11.
[2]王孝通，徐冠雷，周红进.线性规划模型建模和分析管理[J].系统工程理论与实践，2015，09：2387-2393.
作者简介：刘晓彤（1990—），男，山西吕梁人，山西财经大学2015（管理科学与工程）学术硕士研究生，研究方向：创业过程与企业孵化.
推荐访问： 线性规划 日常管理