1.1线性规划问题.ppt

运筹与优化理论,讲授教师：向宇,信息与计算科学专业,第二章线性规划与单纯形法,第二章线性规划与单纯形法线性规划是运筹学最重要的分支。自1947年美国人丹捷格提出求解线性规划的单纯形法以来，它在理论上已趋向成熟，实际上的应用日益广泛与深入，现在几乎各行各业都可以建立线性规划模型。比如制定企业最佳经营计划、确定产品最优配料比、寻找材料的最优下料方案、研究各种资源的最优分配方案等等。由于线性规划模型具有应用的广泛性，更主要由于它的算法易于在计算机上实现，实际上，EXCEL的“规划求解”可以用来求解一般的线性规划问题。所以，线性规划已成为现代管理科学的重要基础和手段之一。,1线性规划问题,1线性规划问题1.1线性规划问题的数学模型线性规划是研究在一组线性不等式或等式约束下使得某一线性目标函数取最大（或最小）的极值问题。下面我们通过几个例子来介绍线性规划问题的数学模型。例1.某工厂生产，两种型号计算机，为了生产一台型和型计算机，所需要原料分别为2和3个单位，需要的工时分别为4和2个单位。在计划期内可以使用的原料为100个单位，工时为120个单位。已知生产每台，型计算机可获得利润分别为6和4个单位，试确定获利最大的生产方案。,线性规划数学模型,建立该问题的数学模型设x1,x2分别表示计划期内产品，的产量。因为计划期内生产用的原料和工时都是有限的，所以在确定产品，的产量时要满足下面约束条件：2x1+3x21004x1+2x2120 x1,x20一般满足上述约束方程组的解不是唯一的，根据题意我们需要的是既满足约束条件，又使得所获利润最大的方案。,线性规划数学模型,若以Z表示总利润，我们的目标是maxZ=6x1+4x2综合上述，该问题可用数学模型表示为：目标函数：maxZ=6x1+4x2约束条件：2x1+3x21004x1+2x2120 x1,x20,线性规划数学模型,例2某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：班次时间所需人数16：0010：0060210：0014：0070314：0018：0060418：0022：0020522：002：002062：006：0030,线性规划数学模型,设司乘人员在各时间段一开始时上班，并连续工作8小时，问该公司线路至少应配备多少司乘人员。列出该问题数学模型。设x1,x2,x6为各班新上班人数，考虑到在每个时间段工作的人数既包括该时间段新上班的人又包括上一个时间段上班的人员，按所需人员最少的要求可列出本例的数学模型：,线性规划数学模型,目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：x1+x660 x1+x270 x2+x360 x3+x420 x4+x520 x5+x630 x1,x2,x60,线性规划数学模型,上面两例优化模型，都具有下述特征：(1)每个问题都用一组未知变量x1,xn表示所求方案，通常这些变量都是非负的，称为决策变量。(2)存在一组约束条件，这些约束条件都可以用一组线性等式或不等式表示。(3)都有一个要求的目标，并且这个目标可表示为一组决策变量的线性函数，称为目标函数。目标函数可以是求最大，也可以是求最小。具有上述特征的数学模型就称为线性规划模型。,线性规划数学模型,线性规划数学模型的一般形式如下：目标函数：max(min)Z=c1x1+c2x2+cnxn约束条件:a11x1+a12x2+a1nxn（，）b1a21x1+a22x2+a2nxn（，）b2am1x1+am2x2+amnxn（，）bmx1,x2,xn0,2图解法,1.2图解法如何求解线性规划模型是本章讨论的中心问题。首先介绍只有两个决策变量的线性规划的图解法，该方法能够对线性规划的解法从几何直观上给我们以启迪。对于两个决策变量的每一组取值，都可以看作平面直角坐标系中一个点的坐标，因此，我们可以把满足约束条件的点在平面直角坐标系中表示出来。以例1的模型为例，约束条件2x1+3x2100，4x1+2x2120都代表由一条直线划定的半个平面，考虑到x1,x20，所以，满足所有约束条件的点应为坐落在第一象限的区域OQ1Q2Q3（如图），该区域称为可行域。,图1-1,图1-1,O,X2605040302010,1020304050 x1,4x1+2x2=120,2x1+3x2=100,Q3,Q2,Q1,2图解法,决策变量的一组取值称为线性规划问题的一个解。满足约束条件的解称为可行解。所有可行解的集合即称为可行域。使目标函数达到最优的解称为最优解。例1的可行域包含无穷多个可行解，为了在无穷多个可行解中找到最优解，我们在坐标系中画出目标函数表示的一族平行线。观察这族平行线移动时对应的Z值变化,可以看出，这族平行线愈向右上方移动，对应Z值愈大。由于平行线族在Q2点脱离可行域，所以，例1在Q2点取得最优解。Q2是直线2x1+3x2=100和4x1+2x2=120的交点，解此方程组可得:x1=20,x2=20.因为例1的解是：生产型型计算机分别为20台，能得到最大利润为200单位。,结论,从图解法可以看出一般情况下（1）具有两个变量的线性规划问题的可行域是凸多边形。（2）若线性规划存在最优解，它一定在可行域的某个顶点得到。虽然图解法只能求解包