原始对偶单纯形法及其应用开题报告

1. 研究目的与意义

线性规划是应用最为广泛、理论最为成熟的运筹学分支之一。在所有的管理与经营中，都要涉及到资金、人力、物力与时间的消耗。现今超市渠道已经成为市场经济商品流通领域最重要的销售环节之一，促销这种销售形式随着超市业态的蓬勃发展，以其形式的多变性和利益的直观性，逐渐被消费者认知和接受。企业如何优化促销人员配置，使有限的宝贵资源产生最大的效益，这是所有管理者与经营者都非常关心的问题。我们将这类决策问题划分为两个方面:

一是对一定数量可控的资金、人力、物力等资源，如何合理安排使用，使这些资源产生最大效益;二是当某个任务确定之后，如何统筹安排，尽量用最少的资金、人力、物力等资源去完成该项任务。

这两类问题实际上是一个问题的两个方面，即寻找问题的系统最优。线性规划是解决这两类问题的有效方法之一。

人员促销是指企业促销员直接与顾客接触、洽谈、宣传介绍商品和劳务以实现销售目的的活动过程。它是一种古老的、普遍的但又是最基本的销售方式。企业与顾客之间的联系主要通过推销员这个桥梁。推销员、产品、顾客三者结合起来，才能成为统一的人员推销这一运动过程。人员促销具有以下优点:方式灵活；针对性强；及时成交；发展关系；反馈信息。

然而，管理者在拟订促销计划时，不仅要考虑总销售量，而且要考虑利润、销售成本和市场需求等，如何统筹兼顾多种目标，选择合理方案，是十分复杂的问题。

2. 国内外研究现状分析

1.1 理论研究

作为运筹学的一个重要分支，线性规划问题是最早研究、理论较为完整、应用极其广泛的一门数学规划学科。法国数学家j.b.j. fourier和c.瓦莱.普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年，前苏联科学家兼经济学家康托洛维奇发表了《生产组织与计划中的数学方法》一书^[1]，第一次详细的介绍了线性规划问题，也未引起重视。1947年，美国贝尔电话公司工程师g.b.dantzig提出了线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法^[2]，从而使线性规划在理论上趋于成熟，在实际应用中日益广泛与深入。同年，美国数学家j.von诺伊曼提出对偶理论，开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。自此，单纯形算法也取得了巨大的发展，其理论也日趋成熟与完善。虽然单纯形算法的时间复杂性是指数阶的，然而它在实际应用中却取得了显著的效果。后来，borgwardt和smale都证明了单纯形算法的平均运算次数是多项式级的。因而一直以来，不论在理论上还是在实际计算中，单纯形算法都是极其重要的。在1950年到1960年间，线性规划理论得到了进一步的发展和丰富，得到了迅猛的发展。例如，1954年c.lem基提出对偶单纯形法，1954年s.gace和t.saady等人解决了线性规划的灵敏度分析和参数规划问题，1956年a. tucker提出互补松弛定理，1960年g.b.dantzig和p.wolf提出分解算法等。1975年，瑞典皇家科学院把经济科学的诺贝尔奖授予了l.v.kantorovic和t.c.koopmans，以奖励他们对资源最优分配理论的贡献。1979年，l.v.kantorovic^[3]证明了shor，judin和nemirovskii的椭球法。这种方法与逐次迭代的单纯形法是根本不同的，椭球法是在一个多项式的时间限界内找到线性规划的一个最优解。其证明了线性规划问题确实存在多项式时间算法。因此，椭球算法从理论上说是个重要的突破。但遗憾的是椭球法在理论上优越并不能在实践应用中得以实现。

1984年，线性规划领域里出现了自单纯形法以来的另一重大突破，即n.kamarkar的投影尺度法^[4,5,6] ，使线性规划出现了真正的突破。kannarkar提出了一个不仅在理论上具有多项式复杂性界限，而且在求解大型问题上优于单纯形法的算法。与单纯形法沿着可行域的边界寻优不同的是karinarkar算法是从初始内点出发，沿着最速下降方向，从可行域内部逐渐走向最优解，它是从可行域的内部去逼近一个最优解。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。1985年，e.barnes^[7]和r.vanderbei，m.meketon和b.freefman^[8]重新提出用(原来)仿射尺度算法来解标准的线形规划问题，并给出了算法的收敛性证明。因为karinarkar算法不仅具有多项式时间复杂度，而且在求解大规模的优化问题时显示了它的巨大潜力，所以内点法理论发展迅速，从那时起的十多年间，线性规划内点算法的研究与推广成为最优化领域中最令人振奋的研究热点之一。毫不夸张地说，在20世纪40年代发展起来的线性规划，极大地拓宽了最优化的研究和应用领域，并在过去60多年中促进了现代优化理论、算法和应用方面的巨大进步。此后，内点法逐渐发展成一个相当成熟的算法，并且形成了三类经典的内点算法:势函数投影变换法、仿射尺度法、路径跟踪法。adler等人提出了类似的对偶仿射尺度算法^[9]用来解对偶线性规划问题。1987年，m.kojima等人提出并分析了第三种算法，即原始一对偶仿射尺度算法^[10]。

3. 研究的基本内容与计划

本文针对一类企业(带有分公司)促销人员优化配置问题进行研究，以某集团为例，从利润、市场需求、资源(产品)、各分公司申请量、各分公司人员能力状况五个方面的因素运用优化方法建立数学模型，其优化目标是使整个集团的年利润达到最大。即对该集团总部下一年效益值进行线性规划，运用运筹学思想与经济学理论对企业促销人员资源进行优化配置，使其达到该企业的利润最大，资源消耗最少，人员配置最优，给出一个明确的分配方案，向该类企业提供有益的建议。所建立的数学模型在此类企业促销人员的资源配置方面具有广泛的应用。模型的建立主要包括以下几个方面：

问题的提出：以促销人员数量、新促销人员培训数量、销售任务量、商品损失费等为指标设题。

问题分析：对某集团销售计划、人员调配、销售成本等实际状况进行分析。

4. 研究创新点

线性规划是产生较早、影响最深远和应用最广泛的一个运筹学分支。

历经半个多世纪的发展，其理论已日臻成熟，并已成为国民经济，科学技术，管理和工程等诸多领域不可或缺的数学工具。

本文通过文献研究，评述线性规划理论研究进展及国内外学者对线性规划理论的认知，探讨线性规划理论的构建。