线性规划在数学建模中的应用文档格式.docx
《线性规划在数学建模中的应用文档格式.docx》由会员分享，可在线阅读，更多相关《线性规划在数学建模中的应用文档格式.docx（13页珍藏版）》请在冰点文库上搜索。
研究线性规划在数学建模中的现实意义有很多，因为一个数学理论要想应用到现实中去就必须要建立数学模型去解决。
而线性规划作为运筹学中的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。
因此，研究线性规划在数学建模中的应用就可以将数学理论更好的，更有效的，更完美的运用到现实生活中去，为我们的生活提供便利。
第二章线性规划理论简述
2.1理论的渊源及演进过程
（1）线性规划理论发展的萌芽期
法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提可解的问题会有一个简单多边形的可行域出线性规划的想法，但未引起注意。
二十几年后，1939年联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。
此后的十几年中，线性规划只是作为一个还不成形的思想并未引起世界的重视。
（2）线性规划理论发展的成长期
1947年美国数学家G.B.Dantzing提出求解线性规划的单纯形法，为这门学科奠定了基础。
同年，1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用围和解题能力。
1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。
（3）线性规划理论发展的成熟期
50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。
例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。
线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。
由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。
1979年联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。
1984年美国贝尔实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。
用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。
现已形成线性规划多项式算法理论。
由于单纯形法是求解线性规划模型的常用方法，并且其在求解线性规划模型上使用相当广泛，因此国外对于单纯形法的研究成果可体现国外对线性规划在数学建模中的研究进程。
2.2国外有关研究的综述
1983年，S.Smale再次给出了Borgwardt在1982年证明的单纯形法平均多项式时间复杂类似的结果，这些结果都表明此算法虽然在最坏情况下是“差”算法，但是，它的平均复杂性是“好”的。
1992年，J.J.Forrest和D.Goldfarb给出了steepest.edge规则的若干变形和与之相应的递推公式，数值实验结果表明单纯形法与当时正处于发展势头强劲之际的点法确实存在不分高低和难分伯仲的竞争状态。
2002年，R.E.Bixby在“Solvingreal-worldlinearprograms:
adecadeandmoreofprogress”文章中总结了对偶单纯形法从20世界90年代以后的新进展，并指出它已经成为最有效的求解线性规划问题的方法之一【1】。
2.3国研究的综述
国有关学者们对于单纯形法的各方面研究成果也不计其数，依照目前已经公开发表的资料来看：
郭秀英在“线性规划单纯形法迭代法则的改进”【2】文章中提出一种当进、出变量唯一不变时的可减少迭代次数的判断进、出变量的新法则，并验证了其有效性。
晓杰在“生产问题中单纯形解法的改进”【3】文章中针对线性规划在生产问题中的具体应用模型，结合线性规划的三个参数之间的某些关系以及他们对非基变量检验数的影响，提出一种通过某些特定变量的进出基运算可以达到简化单纯形求解运算的可行方法。
吕林霞等人在“线性规划模型的单纯形法初始可行基选择研究”【4】文章中提出可以利用矩阵初等行变换来直接判断和寻找问题初始可行基的一种可行方法。
劲松等再“含自由变量LP问题的改进单纯形法”【5】文章中针对含自由变量的LP问题，通过研究自由变量在其迭代过程中的运算规律，提出一种改进算法并且验证了其可以提高运算速度和节省存贮空间的有效性。
董兵等再“一种改进的单纯形最优化法”【6】文章中给出了一种求解法获得的的基解仍然非原问题可行，也非对偶可行的一类规划问题初始可行的一般方法。
震等在“单纯形法的计算机程序化算法改进”【7】文章中，通过其对计算机程序所作的改进工作，使得单纯形法在空间上和时间上的复杂度效率均降到。
2.4本人对以上综述的评价
从资料上来看虽然线性规划模型理论起源于国外，但是其在国得到了较好的发展。
其中国学者在简化单纯形法的求解过程方面贡献卓著，而外国学者在讨论哪种方法是求解线性规划模型的最优方法上做了深入的研究。
第二章线性规划在数学建模中的应用
2.1线形规划在物流运输模型中的应用
现在物流业面临的新问题是：
（1）认定所给问题确实是一个线性规划问题；
（2）把它建立起线性数学模型；
（3）并能够完成具体实务的全部工作。
第一个问题实质上是具体实务究竟满足什么条件才能应用线性规划的方法。
一般地说，必须有：
①一定要满足将目标表为最小化或最大化的要求；
②一定要有达到目标的不同方法，且必须要有选择的可能性；
③要求的目标是有限制条件的；
④必须将约束条件用数学表示为线性等式或线性不等式，并将目标函数化为线性函数。
实例2.1：
车辆调度问题
物流部门承接的运输千万种，并往往是几十种物资同时调运。
为此，只有一种物资的数学模型求最优调运方案方法，在多种物质运输情况下就不能直接使用。
原因是：
在调度汽车去完成运输任务时，免不了要出现空驶现象。
例如某车队有一天要完成如表2所示的运输任务，各地问的距离如表3，问应怎样安排汽车去完成这些任务才能做到最省?
分析：
满车路线和方向显然是固定的，但空车的路程、方向却没有固定。
如把木材从火车站运到建筑工地卸下后，空车即可去火车站装煤，也可去文具公司装纸。
空车的走法不同，空驶的数当然也不同，这就产生了车辆调度问题。
车辆调度问题主要解决的是：
怎样安排车辆去完成所有的运输任务并使空驶的数最小。
物资调运问题是“怎样才能使物资运输的数最小”；
这就是说把空车看成是一批货物（卸几吨货物就看成是几吨空车），则把车辆调度问题转化为物资调运问题。
把空车看成是货物，其发、收（产、销）点及发、收（产、销）量按如下的方法决定：
（1）若某点的卸货总量大于装货总量，则该点是空车的发点，其发量等于卸货总量与装货总量之差。
如学校卸货总量为4，装货为0，故学校是发点，发量为4。
（2）若某点装货总量大于卸货总量，则该点是空车的收点，其收量也是二者之差。
（3）如果某点的卸货总量等于装货总量，如此点不存在空车则不予考虑。
为此，车辆调度问题可作为物资调运问题来处理。
即空车的流向应怎样才能使车辆调度合理?
其主要步骤如下：
①确定空车的收发点和收发量，并列表；
②确定空车调运的数学模型，并求解；
③根据所得解并结合具体情况合理调派车辆。
解：
收点：
火车站、文具公司、粮店；
发点：
建筑工地、钢厂、学校。
表1运输任务
起点
终点
建筑工地
钢厂
学校
火车站
9
5
8
文具公司
3
7
4
粮店
10
13
表2运输任务
货物
装货点
卸货点
车数
木材
煤
2
纸
面粉
表3空车收发运距
运距（单位）
空车收点
空车数量
空车发送
6
约束条件为：
用单纯形法的程序在计算机上可得：
钢厂、学校分别向火车站发2t空车，建筑工地向文具公司和粮店发2t空车。
空车吨公里数最小是：
2.2利用线性规划模型在经济生活中的应用
星星规划问题是经济数学的一个重要分支，在实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学忠的一些分支中的问题也可以转化为线性规划问题来计算，因此线性规划问题在最有化学科中占有重要地位。
表4各种产品的资源消耗量
产品
劳动力/工时
设备台时
原材料（kg）
劳动成本（元/kg）
产值
（元/kg）
A
15
20
30
260
472
B
49
180
512
C
25
45
385
544
资源限额
8000
12000
15000
120000
实例2：
单位生产成本最大增值问题
某工厂在计划期要生产三种A，B，C产品，假定产品畅销，已知生产的固定成本为10000元，即生产期固定资产损耗量。
并且生产单位所需要的劳动力、设备台时、原材料、变动成本以及差值如表4所示。
厂方规定总生产成本不要超过130000元，问应该如何安排生产才能使得产出率最大？
建立数学模型：
设工厂在计划期生产A，B，C三种产品的数量分别为
，
显然成本产出率的表达式是：
（1）
且A，B，C三种产品的数量受4种资源量的限制：
劳动力量的限制：
（2）
设备台时的限制：
（3）
原材料的限制：
（4）
变动成本的限制：
（5）
此外A，B，C三种产品的产量不能为负数，即
。
综上所述，本文的问题就是在条件
（2）至（5）以及未知数非负的条件下求得未知数使得
（1）最大，
（1）成为目标函数。
（2）至（5）称为约束条件，和工业资源配置一样的还有农业生产计划安排问题。
2.3线性规划在现代管理中的应用
表5人工工时及单位产品利润
车间
设备
人工
利润/百元
甲
3.5
乙
D
实例3：
某企业有某企业有两个车间，各生产两种产品，生产这些产品所需的设备台时，人工工时及单位产品利润如下表所示。
现在企业具有设备102台时，人工工时46，计划部门将设备及人工进行如下分配，划部门将设备及人工进行如下分配:
分给甲车间设备台时48，人工工时26;
分给乙车间设备台时54，人工工时20。
问计划部门如此进行分配是否合理?
解设
分别为A,B两种产品的计划产量，
分别为C,D产品的计划产量。
分别建立两个车间的生产组织的数学模型并求解。
甲车间的生产组织模型为
先将模型标准化，再用单纯性法求得最优单纯型矩阵：
由此得甲车间的最优生产方案为：
生产A产品4单位，生产B产品6单位，最大利润为
设备台时和人工工时的影子价格分别为
乙车间的生产组织模型为
先将模型标准化，再用单纯形法求得最优单纯形矩阵
于是原问题的最优解为：
，最优值
由
还可求得三种原料
的影子价格分别为：
可知，现有原料
有剩余，增加此种原料不仅不能增加总利润，相反还会占用工厂的资金。
故工厂决策者可以按不低于市场价格将剩余原料
转让出去，增加收入。
由
可知，原料
增加一吨，最大利润将增加0.12万元。
因此，当该工厂的产品不是国家计划产品，而市场上原料
的实际价格又低于0.12万元/吨时，工厂就可以把一部分资金买进原料
来扩大生产，使利润增加。
反之，当市场上
实际价格大于影子价格时，工厂就应卖出部分原料
，缩小生产规模。
此时生产利润虽然会减少些，但加上卖出原料的收入，总经济收入还是会比原来多一些。
对于原料
也可作类似分析。
第三章结论
综上所述,线性规划理论主要有两大类:
一类是一项任务确定后如何统筹安排,做到以最少的人力、物力资源去完成这项任务;
另一类是在一定量的人力、物力资源条件下,应如何统筹安排使用它们,以发挥最大的效益。
这两类问题是一个问题的两个方面,即寻求整个问题的某种指标的最优解。
求解线性规划的有效方法有:
表上作业法、椭圆算法、卡马卡算法、单纯形法等,各种算法有其特点和优点,但都不能替代理论较完善、实用性强的单纯形法。
如今,线性规划理论的发展非常迅速,已渗透到经济活动的各个领域:
除了生产组织、资源配置、交通运输、节约下料、人事指派、投资决策外,还有城市规划、工农业布局、服务网点、设备利用、仓库储备、环境优化、国防建设等。
随着计算机技术的迅猛发展,线性规划的应用日益广泛。
各种新的算法不断出现,如点法、大步长跟踪算法、鞍面算法等。
在1951年,国际水平只能解约束条件为10个方程的线性规划问题,到了1963年,就能解100010000个方程的线
性规划问题。
1956年,解一个67个方程的线性规划问题要1小时,而到1963年只需28秒。
现在,不仅解题规模大、速度快,而且已有线性规划的专门程序,求解时只要通过计算机调用程序,输入数据,很快便可得出结果。
例如:
给70个人分配70
项不同的任务,共有70!
种方案,是天文数字,要从中找出最优方案,即使用每秒能运算10亿次的大型计算机处理,也要从150年前开始直到太阳熄灭才会有结果。
如果用单纯形软件,在电子计算机上计算,只需要几秒钟便可得出结果。
1984年,美国贝尔实验室的数学家卡玛卡把射影几何原理用于大规模的线性规划问题,取得重大突破,成功地用于美国电报公司改建太平洋沿岸20个国家的庞大网计划,求出了涉及4.2万个因素设计的最小投资数,曾引起轰动。
目前,美国78%的企业应用了线性规划,且成效显著。
在我国,线性规划方法已成为国家重点推广的现代管理方法之一。
升级会员 