资源描述：
《运筹学解析与答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第二章线性规划(LinearProgramming)线性规划是运筹学的一个基本分支，其应用极其广泛，其作用已为越来越多的人所重视。本章先通过例子归纳线性规划数学模型的一般形式，然后着重介绍有关线性规划的一些基本概念、基本理论及线性规划的求解方法---单纯形法。§1线性规划问题1.1线性规划问题举例例1（生产计划的制定问题）某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3，已知的条件如下表1所示，试制订出总利润最大的生产计划。产品单位产品所需原料数量（kg）原料Q1Q2Q3原料可用量（kg/日）
2、P12301500P2024800P33252000单位产品的利润（千元）354表1解：设xj-----产品Qj(j=1,2,3)的日产量，则该问题的目标是总利润最大，即maximizef(x)=3x1+5x2+4x3其约束条件是（1）2x1+3x2+0x3≤1500-----------（日消耗量P1不超过它们的日可用量）（2）0x1+2x2+4x3≤800------------（日消耗量P2不超过它们的日可用量）（3）3x1+2x2+5x3≤2000------------（日消耗量P3不超过它们的
3、日可用量）（4）xj≥0,j=1,2,3---------------(非负约束限制)于是求解该问题的数学模型为：maximizef(x)=3x1+5x2+4x3s．t2x1+3x2+0x3≤15000x1+2x2+4x3≤8003x1+2x2+5x3≤2000xj≥0,j=1,2,3例2（运输问题）设某种物质从m个发点：A1,A2,…,Am输送到n个收点：B1，B2，…,Bn.其中发出量分别为a1,a2,…,am,收入量分别为b1，b2，…,bn,并且（产销平衡）（注：也有产销不平衡问题）已知第i个发点
4、到第j个收点的距离（或单位运费）为cij(i=1,2,…,m;j=1,2,…,n)。问应如何分配供应，才能既能满足需要，又使总的运输吨公里达到最小？解：设xij------第i个发点运到第j个收点的物质数量，于是问题归结为：45求xij≥0,i=1,2,…,m;j=1,2,…,n,使满足：且使目标函数达到最小，即s.t例3(布点问题)某市有6个区，每个区都可建消防站，为了节省开支，市政府希望设置的消防站最少，但必须保证在该市任何地区发生火警时，消防车能在15分钟内赶到现场。假定各区的消防站要建的话,就建在
5、区的中心，根据实地测量,各区之间消防车行使的最长时间如下表:(单位:分钟)1区2区3区4区5区6区1区410162827202区105243217103区162441227214区283212515255区271727153146区20102125146请你为该市制定一个设置消防站的最节省的计划。建模并求解。解：本题实际上是要确定各个区是否要建立消防站，使其既满足要求，又最节省。这自然可引入0-1变量，故设目标是最少。以下考虑约束条件。若1区发生火警，按照“消防车要在15分钟内赶到现场”的要求，则l区和2
6、区至少应有一个消防站，即。同理得：45从而得模型为：再仔细观察知，若满足第一、三个约束条件，则必然满足第二、四个约束条件，故后者是多余的，可省略。从而化简得：实际上，在工业、农业、商业、军事和经济管理等许多领域中，许多问题都可以用线性规划模型来描述，或者可以用它来逼近。1.2线性规划LP模型所谓线性规划问题，即在一组线性等式或不等式的约束之下，求一个线性函数的最大值或最小值。线性规划问题的一般形式为s.t.:(LP)其中函数z=c1x1+c2x2+---+cnxn为目标函数限制条件（1）---（m）为约束
7、条件xj,j=1,2,---,n为决策变量符号“≥=≤”表示“≥”，“=”，“≤”三个符号中的任意一个。为了使数学形式更简洁一些，我们常采用矩阵记号来表示线性规划，从而得到线性规划LP的矩阵形式：45minz=CTxs.t.:Ax≥=≤bx≥=≤0这里称A=（aij）m×n为系数矩阵，c=(c1,c2,…,cn)T为价值向量，b=(b1,b2,…,bm)T为右端向量，x=(x1,x2,…,xn)T为决策变量。现给出LP的有关概念。定义1可行解或可行点：满足所有约束条件(1)~(m)的向量x=(x1,x2,
8、…,xn)T称为问题（LP）的可行解或可行点。定义2可行域D：所有可行点组成的集合称为问题（LP）的可行域，记为D={x
9、Ax≥=≤b,x≥=≤0}定义3最优解：使目标函数Z达到极小（或极大）的可行点称为问题（LP）的最优解。注由线性代数和微分学中求条件极值的知识知，对于给定的线性规划LP，下列三种情况必居其一：(见P13)（1）D=Æ，此时称LP问题无解；（2）D¹Æ，但目标函数在D上无界，此时称LP问题无界；（3）D¹Æ，
