优化方法-线性规划

《优化方法-线性规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划数学教研室石鸿雁引言线性规划是数学规划的一个重要分支，历史比较悠久，理论比较成熟，方法较为完善。线性规划的思想最早可以追溯到1939年，当时的苏联数学家、经济学家（康特罗维奇）在《生产组织与计划中的数学方法》一书中提出了类似线性规划的模型，以解决下料问题和运输问题，并给出了“解决乘数法”的求解方法。然而，他们的长期工作未被人们知道。由于战争的需要，美国的经济学家T.C.Koopmans（库普曼斯）重新独立的研究运输问题，并很快看到了线性规划在经济学中应用的意义。在这之后，线性规划也被广泛地应用于军事、经济等方面。由于他们在这方面的突出贡献，康特罗维奇和库普曼斯联合得到1

2、975年诺贝尔经济学奖。引言对线性规划贡献最大的是美国数学家G.B.Dantig(丹捷格)，他在1947年提出了求解线性规划的单纯形法（SimpleMethod），并同时给出了许多很有价值的理论，为线性规划奠定了理论基础。在1953年，丹捷格又提出了改进单纯形法，1954年Lemke(兰母凯)提出了对偶单纯形法（dualsimplexmethod）。在1976年，R.G.Bland提出避免出现循环的方法后，使线性规划的理论更加完善。但在1972年，V.Klee和G.Minmty构造了一个例子，发现单纯形法的迭代次数是指数次运算，不是好方法——并不是多项式算法（多项式算法被认为是

3、好算法），这对单纯形法提出了挑战。引言1979年，前苏联青年数学家（哈奇扬）提出了一种新算法——椭圆算法，是一个多项式算法，这一结果在全世界引起了极大轰动，被认为是线性规划理论上的历史突破。然而在实际计算中，椭球算法的计算量与单纯形算法差不多，因此，椭球算法并不实用。1984年，在美国的贝尔实验室工作的印度数学家N.Karmarkar(卡玛卡尔)又提出了一个多项式算法——Karmarkar算法，Karmarkar算法本质上属于内点法，这种算法不仅在理论上优于单纯形算法，而且也显示出对求解大规模线性规划问题的巨大潜力。此外，1980年前后，形成求解线性规划的有效集法（active

4、setmethod），在理论上有效集法与单纯形法是等价的，但解决问题的侧重点不同，因此各有优缺点，起着相互补充的作用。引言由于很多非常重要的实际问题都是线性的，即使不是至少能够用线性函数很好地近似，所以线性规划的研究是很有价值的。另一方面，线性规划方面的工作与非线性规划领域相比更为成熟。目前，线性规划方法的发展已被用来求解非线性模型，所以掌握线性规划的理论和解法是本课程的重要目标之一。线性规划（LP）A1A2B1B2B3工地运价（元/万块）砖厂506070601101601947年美国数学家Dantzig单纯形法理论基础1979年苏联数学家哈奇安椭球法理论上的突破1984年美国

5、数学家KarmarkarKarmarkar算法大规模1.问题与模型1.1.数学模型例1.设有A1，A2两个工厂，产量分别为23万块和27万块砖，供应三个工地B1，B2，B3，其需求量分别为17万块、18万块和15万块，而自产地到各工地的运价见表，问应如何调运，才能使总运费最小？圆桌0.180.086衣柜0.090.2810产品利润木料第一种第二种[解]设xijAi运往Bj的运量（万块）minS=50x11+60x12+70x13+60x21+110x22+160x23S.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+

6、x23=15xij≥0,i=1,2、j=1,2,3例2.某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3,第二种有56m3，生产圆桌和衣柜所需木料如下表。每生产一个桌子可获利润6元，生产衣柜可获利润10元。木料厂在现有木料的条件下，圆桌和衣柜各生产多少，才能使利润最大？[解]设生产圆桌x1个，衣柜x2个maxS=6x1+10x2s.t.0.18x1+0.09x2≤720.08x1+0.28x2≤56x1,x2≥0线性规划问题：约束条件及目标函数均为未知量的线性函数，求目标函数的最大或最小值问题。１.2图解法（只限于两个变量）maxS=c1x1+c2x2s.t.a1

7、1x1+a12x2≤b1a21x1+a22x2≤b2x1,x2≥0在平面上取一直角坐标系，它的两个坐标分别是x1,x2,把满足第一个方程的x1,x2看作平面的一个点，那么这个点应在什么地方呢？平面被直线a11x1+a12x2=b1划分为两个平面，这个点一定在两个半平面的某一个上面。所有满足约束条件的点就构成一个区域K。现在，我们就是要在K中找一点（x10,x20），使目标函数达到最大。a21x1+a22x2=b2a11x1+a12x2=b1c1x1+c2x2=hA我们知道，把h作为参数的方程