线性规划理论及其应用

I绪论1.1线性规划的研究意义线性规划是运筹学的一个分支，在科技飞速发展中，线性规划起到了巨大的作用。它被广泛运用于生活中[1]，如：城市公交、地铁，快递、物流，经济分析等。线性规划的发展过程充满了坎坷与磨难，1832年至1939年期间J.-B.-J.傅里叶、C.瓦莱－普森、Л.В.康托罗维奇先后提出了线性规划的想法，都未引起重视；直至1947年G.B.Dantzing提出求解线性规划的\t"/item/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/_blank"单纯形法[2]，才为这门学科奠定了基础。至此线性规划在J.von诺伊曼、T.C.库普曼斯、C.莱姆基等众多数学家的努力下逐渐发展了起来。然而发展过程坎坷的线性规划到了被广泛运用的今天，仍有许多人对线性规划缺乏了解。为了使更多人了解并掌握如何运用线性规划解决实际问题的方法，本文将对线性规划论的概述、公式及其运用进行系统性的描述。本文将通过引入线性规划在生活中的应用，列举生活中遇到的各类问题，并提出解题思路及过程，使读者对如何应用线性规划求解问题有一个更直观的理解。1.2线性规划简介线性规划是一种将实际问题转换成数学模型的方法，它使人们在不使用巨大资源的情况下对问题进行分析，得出问题的最优解，避免了时间及资源的浪费，为经济的发展起到了巨大的促进作用。线性规划改变的不仅是人们做事的方法，更是对人们的思维方式进行了方向性的指导，在加快人们思考速度的同时拓宽了人们思维的广度。1.3线性规划的发展史及其背景线性规划提出至今已有189年的历史，现将线性规划发展时间及过程制成列表（见表1）供大家参考。表1线性规划发展历程时间学者贡献1832年法国数学家J.-B.-J.傅里叶提出线性规划的想法1911年法国数学家C.瓦莱－普森再次提出线性规划的想法1939年苏联数学家Л.В.康托罗维奇《生产组织与计划中的数学方法》在创建和发展线性规划方法以及革新、推广和发展资源最优利用理论方面所做出杰出贡献1947年美国数学家乔治·伯纳德·丹兹格\t"/item/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92/_blank"单纯形法1947年美国数学家J.von诺伊曼对偶理论1951年美国经济学家J.C.库普曼斯应用到经济领域1954年C.莱姆基对偶单纯形法1954年S.加斯和T.萨迪解决线性规划的灵敏度分析和参数规划问题1956年A.塔克互补松弛定理1960年P.沃尔夫分解算法1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法1984年印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法——Karmarkar算法50年代后线性规划的应用范围不断扩大第二章线性规划的形式及其含义2.1线性规划中标准型及其含义标准型： （1） （2）可简写为 （3） （4）标准型公式符号及其含义：表2公式符号及其含义公式符号含义，，，参数价值系数约束条件右端项(第种资源的拥有量)工艺系数(表明生产单位产品时第种资源的消耗量)2.2线性规划中向量模型及其含义向量型： （5） （6）向量型公式符号及其含义： （7） （8）2.3线性规划中矩阵模型及其含义矩阵型： （9） （10）矩阵型公式符号及其含义： （11）第三章线性规划的概念3.1线性规划问题的概念当线性规划问题为 （12） （13） （14）时：表3名词及其定义名词解释(定义)可行解满足约束条件的解可行域全部可行解的集合最优解使目标函数达到最大值的可行解基基向量中的每一个列向量基变量与基向量对应的变量非基变量除基变量以外的其他变量基解基可行解满足变量非负约束条件的基解可行基对应基可行解的基3.2凸集的概念凸集：集合中任意两点，连线上的所有点也都是集合中的点，称为凸集.由于，,的连线可表示为 （15）对，，有，则称为凸集，在图1中(a)、(b)不是凸集，(c)、(d)是凸集[3]。(a)(b)(c)(d)图1集合图像3.3顶点的概念顶点：中不存在任何两个不同的点，，使成为这两个点连线上的一个点为顶点。线性的假设应符合以下几点:（1）比例性(proportionality):即目标函数的值同决策变量的取值成严格比例，约束条件中各产品的资源消耗量同产品生产量成严格比例。（2）可叠加性(additivity):指决策变量间相互独立，决策变量各自取值对目标函数总的取值互不影响，生产产品时对某种资源的消耗量是各产品对该资源消耗量的加总，并且互不影响。线性规划模型中决策变量和各参数取值须符合：（3）可分性(divisibility):指决策变量允许取小数、分数或任一实数。（4）确定性(certainty):指构建模型中的参数，，必须是确定的常数。线性规划问题中，解可能出现四种情况：①最优解唯一②无穷多最优解③无界解④无可行解线性规划问题中存在可行解的集合是凸集、基可行解对应可行域(凸集)的顶点、最优解是基可行解[4]。第四章线性规划的解题方法4.1图解法4.1.1线性规划问题可视化首先建立平面直角坐标系，其次将问题的约束条件归纳为约束方程组，根据约束方程组在平面直角坐标系上得出可行域。4.1.2图解法计算流程图3图解法计算步骤流程图4.2单纯形法4.2.1线性规划模型化为标准形式表4线性规划模型与标准形式的转换线性规划模型化为标准形式变量不变令，则取值无约束令，其中，约束条件右端项不变约束条件两端乘形式目标函数极大或极小不变令，化为求和前的系数加松弛变量时加人工变量时4.2.2单纯形法计算流程图2单纯形法计算步骤流程图

第五章线性规划在生活中的应用线性规划被广泛运用于生活中，如：城市公交、地铁，快递、物流，经济分析等。其主要作用在于解决问题前对方法进行优化，做到以下两点：（1）在资源相同的情况下，达到最大利益。（2）在完成任务的情况下，花费的代价最小。为了增强直观感受，本文列举了一些实际应用加强理解。例1：如何裁剪，使边长为a的正方形铁皮做成的正方体容器容积最大？当边长为10米时，容器容积为多大？解：设容器边长为，高为。由题意得：约束条件为：目标函数为：根据约束条件，在平面上绘制出可行域（图中阴影部分）。图4例1平面直角坐标系表11例6可行解（0,5）0（0,0）0（）要求容器容积最大时的值，即求最大时的值。当容器边长为，高为时容器容积最大，为。本题主要解决在资源相同的情况下，如何达到预定目标。例2：A公司需存放物资4个月。已知各月份所需仓库面积（见表5）。仓库租借费用随合同期定，期限越长折扣越大（见表6）。合同每月初都可办理，每份合同规定租用面积数和期限.A公司在任何一个月初办理租借合同，每次办理时可在签一份或若干份租用面积和租借期限不同的合同中进行选择，总目标是使所付租借费用最小。试建立上述问题的线性规划模型。表5所需仓库面积表月份1234所需仓库面积（100m2）15102012表6租赁费用表合同租借期限1个月2个月3个月4个月合同期内的租费（元/100m2）2800450060007300为第个月初签订的租借期为个月的合同的租借面积，满足1月份所需面积的合同为，满足2月份所需面积的合同为，满足3月份所需面积的合同有，满足4月份所需面积的合同有不，再据此建立数学模型[5]。本题主要解决在完成指定任务的情况下，如何使公司花费的代价降低到最小。例3：Z公司生产三种产品，分别需要经两道工序加工。设第一道工序可分别在设备A1，或A2上完成，有B1,B2,B3,三种设备可用于完成第二道工序[6]。已知产品1可在A,B任何一种设备上加工；产品可在任何规格的A设备上加工，但完成第二道工序时，只能在B1设备上加工；产品3只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据见表7，试安排最优生产计划，使该厂获利最大[7]。表7工序所需时间及相关参数设备产品设备有效台时（h）设备加工费（元/h）123A1510060000.0500A27912100000.0321B168040000.0625B2401170000.1119B370040000.0500原料费（元/件）0.250.350.50售价（元/件）1.252.002.80设分别为产品1,2，3的产量,产品1有6种生产方案:经A1，B1加工，记为(A1，B1)产量为,类似有(A1，B2),(A1，B3),(A2，B1),(A2，B2),(A2，B3)产量分别为,.产品2有2种生产方案(A1，B1)或（A2，B2）,产量分别为和,.产品3只有1种生产方案(A2,B2)，产量为,据此可建立数学模型.最优解为,最大获利为1147元。本题主要解决在资源相同且有诸多条件限制的情况下，如何使项目达到最大利益。例4：三化工厂招收男工名，女工名，员工人数满足，那么最多可招男工几名？最多可招女工几名？由题意得：约束条件为：首先，我们根据约束条件，在平面上绘制出可行域（图中阴影部分）。图5例4平面直角坐标系表8例4可行解表男女工人数（5,0）男工5人，女工0人（5,4）男工5人，女工4人（2,3）男工2人，女工3人其次根据题意可知为男工人数，为女工人数；即男工最多为5人，女工最多为4人。本题主要解决在约束条件下，如何将问题转换成可视化界面，便于人们在可行域中，找到最优解。例5：某人打算投资两个项目，项目盈利、亏损率见下表，投资人现可调动资金为10万元，要求资金亏损不超过1.8万元。如何使盈利最大？表9项目盈利、亏损率表A项目B项目盈利率100%50%亏损率30%10%解：设投资人将万元投资A项目，将万元投资B项目。由题意得：约束条件为：目标函数为：根据约束条件，在平面上绘制出可行域（图中阴影部分）图6例5平面直角坐标系表10例5可行解表（0,0）0（0,10）5（6,0）6（4,6）7根据阴影部分可知，投资人用4万元投资A项目，6万元投资B项目时，可确保亏损不超过1.8万元的同时达到盈利最大。本题主要解决如何将实际问题转化为线性问题后，在满足约束条件下，将问题转换成可视化界面，便于人们在可行域中，找到最优解。例6：一公司生产A、B两种瓶子，每种瓶子需要经过两道工艺，瓶子制作工艺、时间数据如下表：表11工艺所需时间及相关参数表工艺要求A瓶B瓶速度（个/天）工艺1612120工艺28464利润2024（1）如何安排A、B两种瓶子的生产可获得最大利润？最大利润为多少？解：设A瓶每日生产个，B瓶每日生产个时，可获得最大利润。由题意得：约束条件为：目标函数为：根据约束条件，在平面上绘制出可行域（图中阴影部分）。图7例6平面直角坐标系根据平面直角坐标系，绘制出可行解表格（见表6）。表12例6可行解表（0,10）240（0,0）0（8,0）160（4,8）272根据图表可知，A瓶每日生产4个，B瓶每日生产8个时，可获得最大利润，最大利润为272。本题主要解决如何将实际问题转化为线性问题后，在满足约束条件下，将问题转换成图表，便于人们在可行域中，找到最优解。

结论线性规划是运筹学的一个分支，在科技飞速发展中，线性规划起到了巨大的作用。它被广泛运用于生活中，如：城市公交、地铁，快递、物流，经济分析等。在工作和生活中，我们常常遇到两种情况，一是如何在资源相同的情况下，达到最大利益。二是在完成任务的情况下，如何使我们花费的代价最小。本文对利用线性规划求解此类问题进行了研究。在论文编写期间，我查阅了《线性规划的发展简史》这篇文章，文中为大家推荐了利奥尼德·康托洛维奇与利奥尼德·康托洛维奇两位为线性规划问题作出巨大贡献的人物，并对线性规划发展过程中的若干个重大历史事件进行整合[8]。通过综合本文及其它相关资料对线性规划的发展历程进行了整理，并制成表格（见表1）供大家参考。论文中对规划问题各分支的模型公式进行了整理，为了使读者便于理解，文中对公式中的符号及其含义进行了说明。单纯形法和图解法作为线性规划的解题方法，也在文中进行了举例说明。最后本文通过引入线性规划在生活中的应用，列举生活中遇到的各类问题，并提出解题思路及过程，使读者对如何应用线