线性规划模型的求解及应用 毕业论文.docx
《线性规划模型的求解及应用 毕业论文.docx》由会员分享，可在线阅读，更多相关《线性规划模型的求解及应用 毕业论文.docx（21页珍藏版）》请在冰点文库上搜索。
毕业论文（设计）
课题名称 线性规划模型的求解及应用
学 院 理 学 院
专 业 数学与应用数学（S）
班 级 2010级 数学2班
指导教师
学生姓名
佳木斯大学教务处
word文档可自由复制编辑
线性规划模型的求解及应用
佳木斯大学理学院数学系
2014年6月
摘 要
线性规划是运筹学的一个重要分支，它辅助人们进行科学管理，是国际应用数学、经济、计算机科学界所关注的重要研究领域.线性规划主要研究有限资源最佳分配问题，即如何对有限的资源进行最佳地调配和最有利地使用，以便最充分发挥资源的效能来获取最佳的经济效益.
线性规划运用数学语言描述某些经济活动的过程，形成数学模型，以一定的算法对模型进行计算，为制定最优计划方案提供依据.其解决问题的关键是建立符合实际情况的数学模型，即线性规划模型.在各种经济活动中，常采用线性规划模型进行科学、定量分析，安排生产组织与计划，实现人力物力资源的最优配置，获得最佳的经济效益.目前，线性规划模型被广泛应用与经济管理、交通运输、工农业生产等领域.
本文主要介绍线性规划的两种基本解法即图解法和单纯形法，并讨论了这两种方法的优缺点和在一些实际问题中的应用.
关键词:
线性规划；图解法；单纯形法；数学模型；应用
Abstract
Linearprogrammingisanimportantbranchofoperationsresearch,whichassistpeopletoscientificmanagementisanimportantareaofresearchinternationallyappliedmathematics,economics,computersciencecommunity'sconcerns.Themainstudyoflinearprogrammingoptimalallocationoflimitedresources,namelyhowtolimitedresourcesoptimallydeployandmostadvantageouslyusedinordertomostfullyeffectiveresourcestogetthebestvalueformoney.
Linearprogrammingusingmathematicallanguagetodescribetheprocessofcertaineconomicactivities,theformationofmathematicalmodelstoacertainalgorithmtocalculatethemodeltoprovideabasisfortheformulationoftheoptimalplanfor.Thekeytosolvetheproblemistocreateamathematicalmodelinlinewiththeactualsituation,namelylinearprogrammingmodel.Invariouseconomicactivities,oftenusinglinearprogrammingmodelforscientific,quantitativeanalysis,organizationandplanningforproductiontoachievetheoptimalallocationofhumanandmaterialresources,togetthebestvalueformoney.Atpresent,thelinearprogrammingmodeliswidelyusedineconomicmanagement,transportation,industrialandagriculturalproductionandotherfields.
Thispaperdescribestwobasicsolutionthatgraphicalmethodforlinearprogrammingandthesimplexmethod,anddiscusstheadvantagesanddisadvantagesofbothmethodsandapplicationsinanumberofpracticalproblems.
Keywords:
LinearProgramming；Graphicmethod;simplexmethod;mathematicalmodel;Application
目 录
摘 要...............................................................................................................................................
Abstract...........................................................................................................................................
第1章 绪论...................................................................................................................................
1.1线性规划的基本概念.........................................................................................................
1.1.1线性规划简介............................................................................................................
1.1.2线性规划由来的时间简史.........................................................................................
1.2线性规划的研究目的及意义.............................................................................................
第2章 线性规划问题的数学模型...............................................................................................
2.1线性规划模型的建立.........................................................................................................
2.2线性规划模型的求解方法.................................................................................................
2.2.1图解法.........................................................................................................................
2.2.2单纯形法.....................................................................................................................
第3章 线性规划在实际问题中的应用.......................................................................................
3.1线性规划在企业管理中的应用.........................................................................................
3.1.1线性规划在企业管理中的应用范围........................................................................
3.1.2如何实现线性规划在企业管理中的应用................................................................
3.2线性规划在企业生产计划中的应用..................................................................................
3.3线性规划在运输问题中的应用..........................................................................................
结论...................................................................................................................................................
参考文献...........................................................................................................................................
第1章 绪论
1.1线性规划的基本概念
1.1.1线性规划简介
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：
一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：
在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.
1.1.2线性规划由来的时间简史
法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意.
1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视.
1947年美国数学家G.B.Dantzing提出求解线性规划的单纯型法，为这门学科奠定了基础.
1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力.
1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖.
50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法.例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等.
线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展，出现了许多线性规划软件，如
MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题.
1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法.
1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法.用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50.现已形成线性规划多项式算法理论.50年代后线性规划的应用范围不断扩大.建立线性规划模型的方法
第2章 线性规划问题的数学模型
2.1线性规划模型的建立
线性规划是合理利用、调配资源的一种应用数学的方法.它的基本思路是在满足一定的约束条件下，使预定的目标达到最优.它的研究内容可归纳为两个方面：
一是系统的任务资源数量已定，精细安排，用最少的资源去实现这个任务；二是资源数量已定，如何合理利用、调配，使任务完成的最多.前者是求极小，后者是求极大.
线性规划的一般定义如下：
对于求取一组变量 Xj（j=1,2,…,n），使之既满足线性约束条件，又使具有线性特征的目标函数取得极值的一类最优化问题称为线性规划问题.线性规划模型建立需具备以下条件：
一是最优目标.问题所要达到的目标能用线性函数来描述，且能够使用极值 （最大或最小） 来表示.二是约束条件.达到目标的条件是有一定限制的，这些限制可以用决策变量的线性等式或线性不等式来表示.三是选择条件，有多种方案可以供选择，以便从中找出最优方案.
线性规划问题的一般数学模型如下：
max（或𝑚𝑖𝑛）𝑍=𝑐1𝑥1+𝑐2𝑥2⋯+𝑐𝑛𝑥𝑛
（1）
a11x1+a12x2+…+a1nxn≤（=,≥）𝑏1
a21x1+a22x2+…+a2nxn≤（=,≥）𝑏2
s.t.
⋮ ⋮ ⋮
（2）
am1x1+a𝑚2x2+…+a𝑚nxn≤（=,≥）𝑏𝑚
𝑥1x2⋯⋯𝑥𝑛>0（<0）
𝑥j（j=1,2,…,𝑛）
𝑐j（j=1,2,…,𝑛）
称为决策变量
称为目标函数系数
𝑏j（𝑗=1,2,…,𝑛） 称为约束右端系数
𝑎𝑖j（𝑖=1,2,…,𝑛,𝑗=1,2,…,𝑛）
称为约束系数
其中式
（1）为目标函数，式
（2）称为约束条件.
由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：
（1）标准形式
maxz=c1x1+c2x2+×××+cnxn
ï
ìa11x1+
a12x2+
×××+
a1nxn= b1
a
ï21x1+
a22x2+
×××+
a2nxn= b2
í ×××
ïax+
×××
a x+
×××+
a x= b
ïm11
m22
mnn m
（2）Σ记号简写式
ïîxj³0 （j=1,×××,n）
n
maxz=åcjxj
j=1
å
ìn
ï
íj=1
aijxj
=bi
（i=1,2,...,m）
（3）矩阵形式
îï xj³0
（j=1,2,...,n）
maxz=CX
ìAX=b
î
íX³0
式中𝐶=（𝑐1,…,𝑐𝑛）,𝑋=（𝑥1,…,𝑥𝑛）'
éa11
a12
...
a1nù
êa
A=ê21
ê...
a
...
...
...
a2
..
êa
a
...
a
（4）向量形式
ú
éb1ù
êbú
é0ù
ê0ú
22 nú,b=ê
2ú,0=êú
.ú ê...ú
ú êbú
ê...ú
ê0ú
ëm1 m2
mnû
ë3û ëû
maxz=CX
å
ìn
ï
íj=1
pjxj=b
î
ïX³0
式中C,X,b,0的含义与矩阵的表达式相同，而
𝑝𝑗=[𝑎𝑖𝑗,𝑎2𝑗,⋯,𝑎𝑚𝑗]（𝑗=1,2,⋯,𝑛）
即A=（𝑝1,𝑝2,⋯,𝑝𝑛）
将非标准形式化为标准形式的情况（3种基本情况）
（1）目标函数为求极小值
minZ=CX,则作Z’=-CX,即maxZ’=-CX
（2）右端项小于0
只需要将两端同乘（-1），不等号改变方向，然后再将不等式改为等式
（3）约束条件为不等式
若约束条件为“≤”则在不等式左侧增加一个非负松驰变量，使其转化为“＝”；
若约束条件为“³”，则在不等式左侧减去一个非负剩余变量（也称松驰变量），使其转化为“＝”.
2.2线性规划模型的求解方法
2.2.1图解法
线性规划可以在一定条件下合理安排人力、物力等资源,使经济效果达到最好.一般来说,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题.满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.然而图解法不适合解大规模的线性规划的问题，局限性比较大.但对于只有两个或者三个变量的线性规划问题,可以用图解法求最优解,也就是作出约束条件的可行域,利用图解的方法求出最优解,其特点是过程简洁、图形清晰，简单易懂.下面仅做只有两个变量的线性规划问题.
只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：
（1）以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系.由变量的非负性约束性可知，满足该约束条件的解均在第一象限内.
（2）图示约束条件，找出可行域（所有约束条件共同构成的图形）.
（3）画出目标函数等值线，并确定函数增大（或减小）的方向.
（4）可行域中使目标函数达到最优的点即为最优解.
下面举出一个实例来说明：
例1．某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有56m3，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木料如下表所示.每生产一张圆桌可获利60元,生产一个衣柜可获利100元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?
产品
木料（单位m3）
第一种
第二种
圆桌
0.18
0.08
衣柜
0.09
0.28
解：
设生产圆桌x张,生产衣柜y个,利润总额为z元,则由已知条件得到的线性规划模型为：
max𝑧=60𝑥+100𝑦,
𝑠.𝑡.0.18𝑥+0.009𝑦£72,
0.08x+0.28y£56,
x³0,y³0.
图2-1
这是二维线性规划，可用图解法解，先在xy坐标平面上作出满足约束条件的平面区域,即可行域S，如上图所示.再作直线l:
60x+100y=0,即l:
3x+5y=0,把直线l平移至
l1的位置时,直线经过可行域上点M,且与原点距离最远,此时z=60x+100y取最大值，为了得到M点坐标
ì0.18x+0.09y=72
í
解方程组
î0.08x+0.28y=56
,得;
于是知M点坐标为（350,100），从而得到使利润总额最大的生产计划，即生产圆桌
350张,生产衣柜100个,能使利润总额达到最大值31000元.
这表明，当资源数量已知,经过合理制定生产计划,可使效益最好,这就是用图解法解线性规划来解决生产计划安排的问题之一.
2.2.2单纯形法
单纯形是美国数学家G.B.丹齐克于1947年首先提出来的.它的理论根据是：
线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到.顶点所对应的可行解称为基本可行解.单纯形法的基本思想是：
先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进
的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行.因基本可行解的个数有限，故经有限次转换必能得出问题的最优解.如果问题无最优解也可用此法判别.
1953年美国数学家G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法.其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数.这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量.
1954年美国数学家C.莱姆基提出对偶单纯形法.单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止.对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解.在迭代过程中始终保持基解的对
偶可行性，而使不可行性逐步消失.
本节内容只对一般单形法的进行探讨.下面举出一个实际例子来做介绍
例：
求下列线性规划问题的最优解
maxz=5x1+2x2
ì30x1+ 20x2
£160
ï5x+ x £15
í
ï 1 2
ï x1 £4
解：
化为标准形式
ïîx1³0
x2³0
maxz=5x1+2x2+0×x3+0×x4+
升级会员 