孙一帆-二维线性规划的图解法及线性规划在实际中的应用

《孙一帆-二维线性规划的图解法及线性规划在实际中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、31孙一帆-二维线性规划的图解法及线性规划在实际中的应用院系：数学系专业：数学与应用数学姓名：孙一帆学号：指导教师：汪凤贞完成时间：2007年5月二维线性规划的图解法及线性规划在实际中的应用孙一帆（包头师范学院数学科学学院）摘要：线性规划是运筹学的一个最基本的分支，它是一门研究如何使用最少的人力、物力和财力去最优地完成科学研究、工业设计、经济管理中实际问题的专门学科.它已经成为帮助各级管理人员进行决策的一种十分重要的工具.关键词：线性规划，数学模型，图解法，实际问题现代化工业管理要求采用定性和定量分析相结合的方法

2、，一切管理工作要力求做到定量化、最优化，于是就产生了各种各样的管理优化技术.在诸多的管理优化技术中，线性规划是目前最常用、而又最为成功的一种.其原因有三：一是应用广泛，管理工作中的大量优化问题可以用线性规划的模型来表达；二是模型较为简单，容易建立、学习和掌握；三是求解方法成熟：1947年G.B.Dantzig已对一般的线性规划问题建立了解法，即单纯形法，且随着计算机技术的发展，用单纯形法解线性规划的计算程序已大量涌现.线性规划主要在以下两类问题中得到应用：一是在人力、物力、财力等资源一定的条件下，如何使用它们完成

3、最多的任务；二是做一项任务，如何合理安排和规划，能以最少的人力、物力、资金等资源来完成该项任务（即少投入，多产出）.在这里，重要的是建立线性规划的数学模型，一个实际问题的数学模型，是依据客观规律对该问题中我们所关心的那些量进行科学的分析后所得出反映这些量之间本质联系的数学关系式.线性规划问题的数学模型（简称线性规划模型）的一般形式为：min(或max)z?c1x1?c2x2?...?cnxns.t.a11x1?a12x2?...?a1nxn(*)b1,a21x1?a22x2?...?a2nxn(*)b2,（Ⅰ）.

4、...................................................am1x1?am2x2?...?amnxn(*b)m,xj（*）0(j=1,2,…,n).（Ⅱ）其中aij,bij,cij(i?1,2,...,m;j?1,2,...,n)均为已知常数，（*）表示“?”或“?”或“?”.x1,x2，...,xn称为决策变量（即由题所设的未知变量），z称为目标函数.-1-（Ⅰ）和（Ⅱ）称为约束条件，（Ⅰ）中的每一个式子均称为线性约束，（Ⅱ）中若要求变量≥0的条件称为非负条件.这说明

5、，线性规划模型由三部分构成：1．一组决策变量x1,x2,...,xn.通常要求它们非负，但在某些实际问题中也会出现变量为负数的情况;2．表示所给问题最优化指标的目标函数z;3．一组约束条件.正因为目标函数和约束条件都是关于决策变量的线性表示式，所以，这种数学模型称为线性规划模型，相应的问题叫做线性规划问题.若（Ⅰ）中的不等式都为等式且（Ⅱ）中的变量为非负，则叫做线性规划模型的标准型.解任一线性规划问题通用的方法是单纯形法，但对于某些特殊的线性规划问题也有特殊的解法，这样更加简便，下面是解二维线性规划问题的图解法：

6、一．解二维线性规划问题——图解法：对于只含有两个决策变量的LP问题，用图解法求解是最有效的，此方法简便、直观，所给问题也无需化成标准形，比单纯形法更有效，具体步骤见例题：例1．某木器厂生产圆桌和衣柜两种产品，现有两种木料，第一种有72m3，第二种有56m3，假设生产每种产品都需要用两种木料，生产一张圆桌和一个衣柜分别所需木料如下表所示.每生产一张圆桌可获利60元,生产一个衣柜可获利100元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?解：设生产圆桌x张,生产衣柜y个,利润总额为z元,则由已知条

7、件得到的线性规划模型为：maxz?60x?100y,s.t.0.18x?0.09y?72,0.08x?0.28y?56,x?0,y?0.-2-s这是二维线性规划，可用图解法解，先在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点坐标为(35

8、0,100)，从而得到使利润总额最大的生产计划，即生产圆桌350张,生产衣柜100个,能使利润总额达到最大值31000元.这表明，当资源数量已知,经过合理制定生产计划,可使效益最好,这就是用线性规划来解决生产计划安排的问题之一.例2．某养鸡场有1万只鸡,用动物饲料和谷物饲料混合喂养.每天每只鸡平均1吃混合饲料0.5kg,其中动物饲料不能少于谷物饲料的.动物饲料每千克0.9