浅谈线性规划在生活中的应用2.doc

浅谈线性规划在生活中的应用摘 要 线性规划的研究对象是计划管理工作中有关安排和估值的问题,解决的主要问题是在给定条件下,按某一衡量指标来寻找安排的最优方案.文章涉及的是在两个限定条件下的最大利润问题，它是一种最简单的线性规划，解决的方法就是用图象法和消去法.关键词 线性规划;松弛变量;最优解;目标函数中图分类号 0122.1线性规划作为数学规划中最简单的一种问题.它的研究对象是计划管理工作中有关安排和估值的问题，解决的主要问题是在给定条件下，按某一衡量指标来寻找安排的最优方案。它可以表示成求函数在满足约束条件下的极大或极小值问题.如果约束条件和目标函数都是呈线性关系的就叫线性规划.要解决线性规划问题，从理论上讲都要解线性方程组，而解线性方程组的常见方法是图象法和消去法.1 预备知识线性规划是数学规划中理论成熟,方法有效,应用最广泛的一个分支.它研究满足一组线性的等式或不等式约束条件,对一定的线性目标函数进行最优化处理的问题.它是由丹捷格(G.B.Dantzig)在1947年发表的成果.所解决的问题是美国制定空军军事规划时提出的,并提出了求解线性规划问题的方法.2 线性规划问题解的基本概念2.1 线性规划线性规划是在线性约束的有限集合上使一个仿射函数(仿射函数亦即线性函数)达到最大(或最小)的优化问题.2.2 松弛变量松弛变量表示一个决策过程中原料消耗的剩余量.2.3 可行解,可行域满足若干个约束条件的解称为线性规划问题的可行解,所有的可行解构成的集合叫它的可行域.2.4 最优解满足若干个约束条件和某个目标函数式的可性解称为线性规划问题的最优解.2.5 基本可行解 满足若干个非负条件的基本解称为基本可行解.3 简单线性规划问题的解法将实际生活中的线性规划问题,抽象为数学形式,目的在于找到解决问题的方法.为此,我们作以下一些讨论.3.1 最大利润问题例1 某工厂在计划期内要安排生产、两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗.如表1所示:表1 设备128台时原材料A4016原材料B0412该厂每生产一件产品可获利2元,每生产一件产品可获利3元.问应如何安排计划,使该工厂在限定条件下获利最多?显见,这个问题可以用以下的数学模型来描述:设分别表示在计划期内产品、的产量.因为设备的有效台时是8,这是一个限制产量的条件,所以确定产品、的产量时,要考虑不超过设备的有效台时数,即可用不等式表示为:.同理,因原材料的限量,可以得到两个不等式:,.该厂的目标是在不超过所有资源限量的条件下,如何确定产量以得到最大的利润.用z表示利润,这时.综合上述,此计划问题可用数学模型表示为: 目标函数: 约束条件: 3.2 两个变量的线性规划问题的图解法现在我们用图解法来解上述的例1:在以为坐标轴的直角坐标系中,非负条件是指第一象限.每一个约8束条件都代表一个半平面,如约束条件是代表以直线为边界的左下方的半平面.若同时满足:,和的约束条件的点,必然落在坐标轴和由这三个半平面交成的区域内(如右图).x1x2Ox1+2x2=84x1=164x2=12Q3Q2Q1Q4阴影区域中的每一个点(包括边界)都是这个线性规划问题的解,因而此区域是此线性规划问题的解集合,称它为可行域.再来分析目标函数.在这个坐标平面上,它可表示以z为参数,以为斜率的一族平行线:.位于同一直线上的点,具有相同的目标函数值,因而称它为“等值线”.当z值由小变大时,直线沿其法线方向向右上方移动当移动到点时， 使z值在可行域边界上实现最大化（如下图）:这就得到了例的最优解对应的点,点的坐标为.于是可计算出满足所有约束条件的最大值这说明该厂的最优生产计划方案是：生产件产品，生产件产品，可得最大利润为14元3.3 用消去法解两个变量的线性规划问题例某车间生产甲、乙两种产品，已知制造一件甲产品需要种元件个,种元件个；制造一件乙产品需要种元件个，种元件个.现因某种条件限制,只有A种元件180,B种元件135个；每件甲种产品可获利20元, 每件乙种产品可获利15元.试问在这种条件下,应该生产甲、乙两种产品各多少件才能得到最大利润?解: 设应该生产甲产品件,乙产品件,才能得到最大利润元.根据题意,此问题可用数学模型表示为: 目标函数 满足约束条件 即求解满足约束条件的,使目标函数的值最大.为此,引进松弛变量,把线性规划问题化为标准形式:求的最小值,并且满足： 也就是求方程组 的非负解,并且使目标函数的值最小 显然,有一个可行解是: . 相应的目标函数值为: 再从目标函数看出.如果不取,而增大的值,目标函数的值可以减少.为此,把换成. 由得 这样,原方程组可改写成 相应的目标函数可改为: 显然,又可得另一个可行解是: 相应的目标函数值为: 再从目标函数看出如果不取,而增大的值,目标函数的值还可以减少.为此,把换成,并且化简得 将式代入式得 因而方程组可改写成 相应的目标函数改为 显然,又可得另一个可行解是: 相应的目标函数值为 从目标函数可以看出,目标函数已经是最小值,所以这一可行解是最优解.即原问题的最优解为 相应的目标函数值 所以在这种条件下,生产甲、乙产品各件、件,使得最大利润为元.以上是用两种不同的方法解决了我们生产生活中常遇到的最大利润问题.消去法作为数学中常见的一个解方程组的方法,在解线性规划的问题中起到了很重要的作用.下面,我们再看一例,如何用消去法解线性规划中的问题.例3 求的值,使它们满足约束条件 并使目标函数 的最大值.解: 引进松弛变量,把题目对应的线性规划问题化为标准形式:求的最小值,并且满足： 也就是求方程组 的非负解,并且使目标函数的值最小 显然,有一个可行解是: . 相应的目标函数值为: 再从目标函数看出如果不取,而增大的值,目标函数的值可以减少.为此,把换成. 由得 这样,原方程组可改写成 相应的目标函数可改为: 显然,又可得另一个可行解是: 相应的目标函数值为: 从而 再从目标函数看出如果不取,而增大的值,目标函数的值还可以减少.为此,把换成,由得 即 由得 因而方程组可改写成 相应的目标函数改为 显然,又可得另一个可行解是: 对应的目标函数值为 从而 再从目标函数可以看出,如果不取,而增大的值,目标函数的值还可以减少.为此,把换成由并化简整理得 由并化简整理得 由并化简整理得 因而方程组可改写成 相应的目标函数改为 显然,此时的可行解为: 对应的目标函数值为 从而 从目标函数 看出,目标函数已经是最小值,所以这一可行解是原方程组的最优解.即当时满足给定的约束条件,并且使目标函数有最大值为.众所周知,在生产生活中人们经常遇到一些要求对现有资源、设备进行统一分配,全面安排,合理调度或最优设计等问题.从而提高经济效益,创造更多的价值.而提高经济效益的途径,一方面是靠技术的改革,另一方面要改进生产组织和计划,也就是作到合理安排人力、物力资源,合理组织生产过程,在条件不变的情况下统筹安排.在众多可能的方案中,选取出最经济、最合理的一个可行方案,从而进行最优决策.致谢 在此,衷心的感谢周老师在本文写作过程中给予了悉心的指导！ 参 考 文 献1/M.(数学规划协会)2运筹学(三版)M.运筹学教材编写组.清华大学出版社3线性规划导论M.谢金星,姜启源,张立平等译4不等式与线性规划初步M.吴德风.科学普及出版社5最优化模型与实验M.米德通6顾基发,唐锡晋.软系统工程方法论与软运筹学.系统研究M.浙江人民出版社Disscussion on the usage of linear programming in practiceHe Tonglei instructor: Zhou Jun(Student Number 3 Class 5 of 2007, Specialty of Mathematics and Applied Mathematics Departement of Mathematics,Hexi University,Zhangye,Gansu,734000,China)Abstract The targets of the linear programming research are some problems concerned about the arrangements and evaluations in the works of plan and management,and the problems the linear programming going to solve is to find the best scheme according to a certain evaluating criterion under a given situation.This article is about the biggest profits question i