1、 mathematical model; 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.
2、3 线性规划在运输问题中的应用.结论 .参考文献 .第 1 章绪论1.1 线性规划的基本概念1.1.1 线性规划简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支, 它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称
3、为线性规划问题.满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.1.1.2 线性规划由来的时间简史法国数学家 J.- B.- J.傅里叶和 C.瓦莱普森分别于 1832 和 1911 年独立地提出线性规划的想法，但未引起注意.1939 年苏联数学家 .康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视.1947 年美国数学家 G.B.Dantzing 提出求解线性规划的单纯型法，为这门学科奠定了基础.1947 年美国数学家 J.von 诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域， 扩大了它的应用
4、范围和解题能力.1951 年美国经济学家 T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获 1975 年诺贝尔经济学奖.50 年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法.例如，1954 年 C.莱姆基提出对偶单纯形法，1954 年 S.加斯和 T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956 年 A.塔克提出互补松弛定理，1960 年 G.B.丹齐克和 P.沃尔夫提出分解算法等.线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UM
5、PIRE 等，可以很方便地求解几千个变量的线性规划问题.1979 年苏联数学家 L. G. Khachian 提出解线性规划问题的椭球算法，并证明它是多项式时间算法.1984 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划问题的新的多项式时间算法. 用这种方法求解线性规划问题在变量个数为 5000 时只要单纯形法所用时间的 1/50.现已形成线性规划多项式算法理论.50 年代后线性规划的应用范围不断扩大. 建立线性规划模型的方法第 2 章线性规划问题的数学模型2.1 线性规划模型的建立线性规划是合理利用、调配资源的一种应用数学的方法.它的基本思路是在满足一定的约束条件下，使预定的目
6、标达到最优.它的研究内容可归纳为两个方面：一是系统的任务资源数量已定，精细安排，用最少的资源去实现这个任务；二是资源数量已定，如何合理利用、调配，使任务完成的最多.前者是求极小，后者是求极大.线性规划的一般定义如下：对于求取一组变量Xj（j=1,2,n），使之既满足线性约束条件，又使具有线性特征的目标函数取得极值的一类最优化问题称为线性规划问题.线性规划模型建立需具备以下条件：一是最优目标.问题所要达到的目标能用线性函数来描述，且能够使用极值（最大或最小）来表示.二是约束条件.达到目标的条件是有一定限制的，这些限制可以用决策变量的线性等式或线性不等式来表示.三是选择条件，有多种方案可以供选择，
7、以便从中找出最优方案.线性规划问题的一般数学模型如下：max （或𝑚𝑖𝑛）𝑍 = 𝑐1𝑥1 + 𝑐2𝑥2 + 𝑐𝑥（1）a11x1 + a12x2 + + a1nxn （ = , ） 𝑏1a21x1 + a22x2 + + a2nxn （ = , ） 𝑏2s.t.（2）am1x1 + a𝑚2x2 + + a𝑚nxn （ = , ） 𝑏𝑚1x2
8、𝑥 0（ 0）j（j = 1,2,𝑛）𝑐称为决策变量称为目标函数系数𝑏j（𝑗 = 1,2,𝑛）称为约束右端系数𝑎j（𝑖, 𝑗称为约束系数其中式（1）为目标函数，式（2）称为约束条件 .由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：（1）标准形式max z = c1 x1 + c2 x2 + + cn xn a11 x1 +a12 x2 + +a1n xn =b1a 21 x1 +a2
9、2 x2 +a2n xn =b2a x +ax +ax =b m1 1m 2 2mn nm（2） 记号简写式 x j 0（ j = 1, n）nmax z = cj x jj =1 n j =1aij x j= bi（i = 1,2,., m）（3）矩阵形式x j 0（ j = 1,2,., n）max z = CXAX = bX 式中𝐶 = （𝑐1,𝑐）, 𝑋 = （𝑥1,𝑥） a11a12.a1n A = 21 .a2.（4）向量形式b1 b 0 0 22n , b = 2 ,0 = . . m
10、1m 2mn 3 p j x j = b式中 C,X,b,0 的含义与矩阵的表达式相同，而𝑝𝑗 = 𝑎,𝑎2𝑗,𝑎（𝑗 = 1,2,𝑛即 A=（𝑝1,𝑝2,𝑝将非标准形式化为标准形式的情况（3 种基本情况）（1）目标函数为求极小值minZ=CX, 则作 Z=-CX, 即 maxZ=-CX（2） 右端项小于 0只需要将两端同乘（-1），不等号改变方向，然后再将 不等式改为等式（3）约束条件为不等式若约束条件为“ ”则在不等
11、式左侧增加一个非负松驰变量，使其转化为“”；若约束条件为“ ”，则在不等式左侧减去一个非负剩余变量（也称松驰变量），使其转化为“”.2.2 线性规划模型的求解方法2.2.1 图解法线性规划可以在一定条件下合理安排人力、 物力等资源 ,使经济效果达到最好.一般来说 ,求线性目标函数在线性约束条件下的最大值或最小值的问题 ,统称为线性规划问题.满足线性约束条件的解叫做可行解 ,由所有可行解组成的集合叫做可行域.决策变量、 约束条件、 目标函数是线性规划的三要素.然而图解法不适合解大规模的线性规划的问题，局限性比较大.但对于只有两个或者三个变量的线性规划问题 ,可以用图解法求最优解 ,也就是作出约束
12、条件的可行域 ,利用图解的方法求出最优解 ,其特点是过程简洁、 图形清晰，简单易懂.下面仅做只有两个变量的线性规划问题.只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：（1） 以变量 x1 为横坐标轴，x2 为纵坐标轴，适当选取单位坐标长度建立平面坐标直角坐标系.由变量的非负性约束性可知，满足该约束条件的解均在第一象限内.（2） 图示约束条件，找出可行域（所有约束条件共同构成的图形）.（3） 画出目标函数等值线，并确定函数增大（或减小）的方向.（4） 可行域中使目标函数达到最优的点即为最优解.下面举出一个实例来说明：例 1某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一
13、种有 72 m3 ，第二种有 56 m3 ，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木料如下表所示.每生产一张圆桌可获利 60 元,生产一个衣柜可获利 100 元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?产 品木料（单位m3 ）第 一 种第 二 种圆 桌0.180.08衣 柜0.090.28解：设生产圆桌 x 张,生产衣柜 y 个,利润总额为 z 元,则由已知条件得到的线性规划模型为：max 𝑧 = 60𝑥 + 100𝑦,𝑠.𝑡. 0.18𝑥 + 0.
14、009𝑦 72,0.08x + 0.28 y 56,x 0, y 0.图 2-1这是二维线性规划，可用图解法解，先在 xy 坐标平面上作出满足约束条件的平面区域,即可行域 S，如上图所示.再作直线l : 60x + 100 y = 0 ,即l : 3x + 5 y = 0 ,把直线l 平移至l1 的位置时,直线经过可行域上点M ,且与原点距离最远,此时 z = 60x + 100 y 取最大值，为了得到 M 点坐标0.18x + 0.09 y = 72解方程组0.08x + 0.28 y = 56,得;于是知M 点坐标为（350,100），从而得到使利润总额最大的生产计划，即生
15、产圆桌350 张,生产衣柜 100 个,能使利润总额达到最大值 31000 元.这表明，当资源数量已知,经过合理制定生产计划,可使效益最好,这就是用图解法解线性规划来解决生产计划安排的问题之一.2.2.2 单纯形法单纯形是美国数学家 G.B.丹齐克于 1947 年首先提出来的.它的理论根据是：线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到.顶点所对应的可行解称为基本可行解.单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行.因基
16、本可行解的个数有限， 故经有限次转换必能得出问题的最优解.如果问题无最优解也可用此法判别.1953 年美国数学家 G.B.丹齐克为了改进单纯形法每次迭代中积累起来的进位误差，提出改进单纯形法.其基本步骤和单纯形法大致相同，主要区别是在逐次迭代中不再以高斯消去法为基础，而是由旧基阵的逆去直接计算新基阵的逆，再由此确定检验数.这样做可以减少迭代中的累积误差，提高计算精度，同时也减少了在计算机上的存储量.1954 年美国数学家 C.莱姆基提出对偶单纯形法.单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止.对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解.在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失.本节内容只对一般单形法的进行探讨.下面举出一个实际例子来做介绍例：求下列线性规划问题的最优解max z = 5x1 + 2x230x1 +20x2 160 5x +x 1512x1 4化为标准形式 x1 x2 max z = 5x1 + 2x2 + 0 x3 + 0 x4 +
