目 录
摘要..2
关键词..2
一、前言...5
二、方法介绍...5
(一)、图解法 5
(二)、单纯形法 5
(三)、改进单纯形法 5
(四)、对偶单纯形法 5
三、问题的选取6
四、实例分析...6
(一)图解法6
(二)单纯形法6
五、结论6
六、结束语7
参考文献..9
致谢....10
一、前言
线性规划,是辅助人们科学的对日常生活与工作进行管理的一种数学方法,是运筹学的重要组成部分,是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。它广泛应用于当今社会的许多领域。本篇论文旨在从生活中发现问题,并用线性规划进行行之有效的解决,从而体现出运筹学对于解决日常生活中的大部分问题起着十分重要的作用,同我们的日常生活息息相关、密不可分。
这篇论文中选取的例子均来源于日常生活中。在这个越来越讲究速度与质量的社会,生产与生活中越来越讲究高效与低成本,从而对事件处理的高效方法的需求越来越多,也加快了人们对高效方法的探求,在经验充足技术熟练的情况下,就会追求对事物本身每一个元素的组合方式,组合方式的不同就会造成不同的结果,为了追寻最优的结果,往往会探求最优质的组合方式以期得到最佳的结果。所选取的例子来自于我们日常生活中再熟悉不过的文印社,对于名片的打制,在工作熟练的情况下,将名片排列于A4原纸上,不同的排列都会对成本以及收益造成直接的影响。那么,如何降低成本,提高收益,便成了这篇论文讨论的关键。
二、方法介绍
求解线性规划问题的基本方法是单纯形法。为了提高解题速度,又有改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。在面对只有两个变量的线性规划问题时,我们也可以采用图解法进行求解。这种方法仅仅只适用于线性规划问题中只有两个变量的问题。它的特点是直观而易于理解,但实用价值不大。介绍的方法之中,由于篇幅有限,将选取图解法与单纯形法进行实例的介绍。
(一)、图解法
该方法需要建立坐标系,将约束条件在图上表示;确立满足条件的解的范围;绘制出目标函数的图形,最终确定最优解。
通过对它的熟悉与掌握,会为我们之后学习其它方法带来不错的启示,如:
1、在我们求解线性规划的问题时,根据求解的方式、模型的选择不同,出现的解的情况会有这几种:唯一最优解、无穷多最优解、无界解以及无可行解。
2、若线性规划可行域存在,则可行域是一个凸集;
3、若线性规划问题的最优解存在,则最优解或最优解之一(如果有无穷多的话)一定能够在可行域(即凸集)的某个顶点找到;
4、我们的求解思路是:在凸集中找寻到任一顶点,然后由此计算出顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值更优,如果为否,则该顶点就是最优解的点之一,否则转到比这个点的目标函数值更优的另一顶点,重复上述过程,一直到找出使目标函数值达到最优的顶点为止。
(二)、单纯形法
单纯形法是用于求解线性规划问题的基本方法。基本思想是首先找出一个基可行解,将其进行鉴别,看其是否为最优解;如果不是,就按照一定的法则,转换到另一个改进的基可行解,再次鉴别,按照这种方法重复进行。由于基可行解的个数有限,于是经过有限次的转换必然能够得出所求问题的最优解,如果问题无最优解也可用此法判别。