运筹学课件（第一讲）-线性规划及单纯形法

运筹学课程第二章线性规划及单纯形法线性规划的发展提出阶段前苏联数学家康托洛维奇在1939年著的《生产组织与计划中的数学方法》一书中，首次提出了线性规划问题．美国学者希奇柯克(F.LHitchock,1941)和柯普曼(T.CKoopman，1947)独立提出了运输问题这类特殊的线性规划问题．发展阶段在1947年，美国学者丹捷倍(G.BDantzig)提出了线性规划问题的一般解法——单纯形法，为线性规划的发展奠定了基础。成熟应用阶段40多年来，随着电子计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域．成为现代化管理的有力工具之一。

线性规划研究的几类问题两类问题已有一定数量的人力、物质资源，研究怎样充分和合理地使用这些资源，才能使完成酌任务量最大；(maxZ)已确定了一项任务，研究怎样合理安排，才能使完成任务所耗费的资源量最小。(minZ)这两类问题是相互联系的，或者说是一个问题的两种不同提法，总的是要求耗费最小量的资源，完成尽可能多的任务，获得最好的经济效果。实际应用中的分类生产组织与计划问题、资源合理利用问题、运输问题、合理下料问题、配料问题、布局问题生产组织与计划问题（1）问题描述一个工厂或车间有各种不同类型的设备各若干台，各种不同设备生产各种零件的效率不同，在一个生产周期，应如何安排各设备的生产使得成全的产品总量最大。实例某车间用三种不同型号的机床A1，A2，A3加工B1，B2两种零件。机床台数、生产效率(每台机床每个工作日完成零件的个数)如表所示．问如何合理安排机床的加工任务，才能使生产的零件总数最多?建立模型生产组织与计划问题（2）生产组织与规划问题的一般形式某工厂用机床A1,A2,…,Am加工B1,B2,…,Bn种零件，在一个生产周期内各机床可能的加工机时、工程必须完成各种零件的最小数量、各机床加工每个零件的时间（机时/个）和加工每个零件的成本（元/个）见下表。问如何安排各机床的生产任务，才能完成加工任务，又使成本最低？生产组织与计划问题（3）表1表2建立模型生产组织与计划问题（4）资源的合理利用问题（1）资源合理利用的一般形式某厂计划在下一个生产周期内生产B1,B2,…,Bn。种产品，要消耗Al,A2,…,Am种资源。已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如下表所示。问如何安排生产计划，才能充分利用现有资源，使获得的总利润最大？建立模型资源的合理利用问题（2）合理下料问题（1）问题描述在生产中经常会遇到这样的问题，把长度一定的线材或板材截成尺寸不同曲零件毛坯，或在面积一定的板材上切割形状、尺寸不同的零件毛坯．在一般情况下．很难使材料完全利用，总会多出一些料头，如果恰当的搭配下料，则可以减少料头、使原材料得到充分利用，这就是合理下料问题．问题所要解决的就是怎样组成和选择下料方案，在满足各种零件毛坯数量要求的前提下．使总的原材料消耗最少．实例现有一批某种型号的圆钢长8m。需要裁取长2.5m的毛坯100根、长1.3m的毛坯200根，问应该怎样选择下料方式，才能既满足需要，又使总的用料最少?建立模型下料方案分析数学模型合理下料问题（2）合理下料问题的一般形式设用某种原材料截取零件A1,A2,…,Am的毛坯，根据以往的经验，在一件原材料上可以有B1,B2,…,Bn种不同的下料方式，每种下料方式可截得各种毛坯的个数以及每种毛坯的需要量如下表所示．问应如何下料，才能既满足需要又使原材料消耗最少?

合理下料问题（3）建立模型合理下料问题（4）合理配料问题（1）合理配料问题的一般形式某饲养场用n种饲料B1,B2,…,Bn，配制成含有m种营养成分A1,A2,…,Am的混合饲料，各种饲料所合营养成分的数量、混合饲料对各种成分的最低需要量以及各种饲料的单价如下表所示。问应如何配料，才能既满足需求，又使混合饲料总成本最低?

建立模型合理配料问题（2）运输问题（1）问题描述在某一地区内，有某种产品的产地与销地各若干，把这种产品从各产地调运到各销地，调运方案可以很多，应如何组织调运，才能使总的运费或运力(即总的运输吨公里数)最少。实例某公司下属两个工厂，生产同一种产品。产品均可运往三个中心仓库去销售。已知每个工厂的产量，各仓库的销量及各工厂到每个仓库的运输单价如下表所示。问如何组织调运可使生产与运输的总费用最少?建立模型运输问题（2）运输问题的一般形式设某种物资共有m个产地A1,A2,…,Am，其产量分别为a1,a2,…,am，另有n个销地B1,B2,…,Bn，其销量分别为b1,b2,…,bn，已知由产地Ai(i=1,2,…,m)运往销地Bj的(j=1,2,…,n)的单位运价为cij，其数据如下表所示，问应如何调运，才能使总运费最省?运输问题（3）建立模型运输问题（4）运输问题（5）布局问题（1）布局问题的一般形式某农场要在n块土地B1,B2,…,Bn上种植m种作物A1,A2,…,Am

，各块土地的面积、各种作物计划播种的面积以及各种作物在各块土地上的单产如下表所示。问应如何合理安排种植计划，才能使总产量最大？(假设计划播种总面积等于土地总面积，即)建立模型布局问题（2）线性规划模型的建立（1）线性规划模型的特点都有一组决策变量(x1,x2,…,xn)，决策变量的一组取值表示一个决策方案，且决策变量的取值一般都是非负的。都有一组约束条件，约束决策变量的取值。都有一个要达到的目标，用目标函数来表示。目标函数和约束条件都是线性等式或线性不等式。线性规划问题求解的一般步骤研究和明确问题的要求和条件；设定决策变量；选定衡量目标函数的数量指标(利润、费用、成本、产量等）收集和确定数学模型的所有参数数据列出目标函数的数学表达式列出所有约束条件的线性数学表达式。实例有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如表1所示。现有三种货物待运，已知有关数据列于表2。又为了航运安全．要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过15％，前、后舱之间不超过10％．问该货轮应装载A、B、C各多少件，运费收入为最大?线性规划模型的建立（2）表1表2问题分析（1）确定决策变量。因为A、B、C三种商品在货轮的前、中、后舱均可装载，令i=1,2,3分别代表商品A、B、C，用j＝1,2,3分别代表前、中、后舱，设决策变量xij为装于j舱位的第i种商品的数量(件).(2)确定目标函数商品A的件数为x11+x12+x13，即装于货轮前、中、后舱商品A的件数之和，类似可得：商品B的件数为x21+x22+x23商品C的件数为x31+x32+x33为使运费总收人最大，目标函数为：

maxZ=1000(x11+x12+x13)+700(x21+x22+x23)+600(x31+x32+x33)线性规划模型的建立（3）(3)确定约束条件前、中、后舱位载重限制为线性规划模型的建立（4）前、中、后舱位体积限制为A、B、C三种商品的数量限制为根据各舱实际载重大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过15％，前、后舱之间不超过10％．可得舱体平衡条件为：线性规划模型的建立（5）各决策变量要求非负，即建立模型线性规划模型的建立（5）相关概念可行解满足线性规划问题约束条件的解，都称为该线性规划问题的可行解，所有可行解集合称为可行解集（或可行域）。最优解是目标函数达到最优值（最大值或最小值）的可行解，称为最优解。凸多边形区域设x1,x2为多边形区域中的两点，若两点连线上的任意一点，即ax1+（1-a)x2,(0≤a≤1)仍属于该多边形区域，则该多边形区域为凸多边形区域。任何两个凸多边形区域的集合仍为凸多边形区域。顶点设x为凸多边形区域中的一点，若x不能用凸多边形区域种不同两点的线性组合来表示，则称x为凸多边形区域的一个顶点。线性规划问题的图解法（1）线性规划问题的图解法（2）问题实例求解步骤求满足约束条件的可行域建立直角坐标系，以x1为横轴，x2为纵轴；确定非负约束x1≥0，x2≥0的各点集合，即第一象限；确定满足约束条件2x1+3x2≤100的各点集合。在坐标系中画出直线2x1+3x2=100，该直线为边界的左下方的半平面即为满足约束条件2x1+3x2≤100的各点集合；同理，确定其他各约束条件的点集合；点集合的交叉区域即为该问题的可行域。从可行域中找出目标函数的最优解画目标函数的等值线；平移等值线，在可行解区域内找到目标函数的最优解。线性规划问题图解法的几种特殊情况有多重最优解将上例中目标函数由Z=6x1+4x2变为Z=4x1+6x2后，再用图解法进行求解可行解区域无界用图解法求解线性规划问题的图解法（3）无可行解区域用图解法求解图解法的几点讨论(1)若线性规划问题有可行解．则可行解区域是一个凸多边形，它可能是有界的；也可能是无界的。