《运筹管理--MBA运筹学讲义》由会员分享，可在线阅读，更多相关《运筹管理--MBA运筹学讲义（48页珍藏版）》请在金锄头文库上搜索。
1、MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。 例如，在线性规划中体现为两方面： （1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？ （2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？ 运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算
2、机上进行，这样可以节省大量的人力和时间。第一部分 线性规划内容框架LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提 出基本最优解基本方法图解法原始单纯形法单纯形法 大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*第一部分 线性规划（Linear Programming）及其应用第一章 LP问题的数学模型与求解 1 LP问题及其数学模型 （一）引例1（生产计划的问题） 某工厂在计划期内要安排生产、的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗
3、以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。解：设x1,x2分别表示在计划期内生产产品、的产量。由于资源的限制，所以有：机器设备的限制条件：x1+2x28原材料A的限制条件： 4x116（称为资源约束条件）原材料B的限制条件： 4x212同时，产品、的产量不能是负数，所以有x10，x20（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有
4、资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数Z=2x1+3x2的值达到最大。综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x1+3x2引例2. （营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2
5、,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10x16x23x32x4 （二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。（1）每个问题都可用一组决策变量(x1,x2,xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为LP的数学模型，其一般形式
6、为：max(或min)z=c1x1+c2x2+cnxn(1.1)(1.3)(1.2)或紧缩形式max(或min)z=(1.4)或矩阵形式max(或min)z=cx(1.5)或向量形式：max(或min)z=cx(1.6)其中C=(c1,c2,cn)，称为价值系数向量；称为技术系数矩阵（并称消耗系数矩阵） =(p1,p2,pn)称资源限制向量X=(x1,x2,xn)T称为决策变量向量。（三）LP问题的标准型1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须把LP问题的一般形式化为统一的标准型：maxz=cxmaxz=； 或maxz=cx或标准型的特点：目标函数是最大化类型约束条件
7、均由等式组成决策变量均为非负bi(i=1,2,n)2.化一般形式为标准型minzmax(-z)=-cx“”左边+松驰变量；“”左边“松驰变量”变量xj0-xj0变量xj无限制令xj=xjxjbi0等式两边同乘以(-1)。3.模型隐含的假设比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。连续性假定：决策变量应取连续值。确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问
8、题是确定型问题，不含随机因素。以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规划，整数规划或不确定型分析方法。对LP标准型，我们还假定r(A)=mn。（四）LP问题的解的概念设LP问题maxz=(1.7)(1.8)(1.9) 1.从代数的角度看：可行解和最优解 满足约束条件(1.8)和(1.9)的解X=(x1,x2,xn)T称为可行解。所有可行解构成可行解集，即可行域。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。求解LP问题就
9、是求其最优解和最优值，但从代数的角度去求是困难的。2.从LP角度看：基：设A为mxn矩阵，r(A)=m，B是A中的mxm阶非奇异子矩阵（即|B|0），则称B是LP问题的一个基。若B是LP问题的一个基，则B由m个线性独立的列向量组成，即B=(Pr1,Pr2,Prm)，其中Prj=(a1rj,a2rj,amrj)T，(j=1,2,m)称为基向理。与其向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，nm个非基变量。基本解与基可行解 设B是LP问题的一个基，令其nm个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一对应的，
10、基本解的个数Cmn。在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。退化解 如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。3.LP问题解之间的关系如图所示W基本解可行解基可行解（五）两个变量LP问题的图解法 1.LP问题解的几何表示。以引例为例说明maxz=2x1+3x2按以下顺序进行：解：（1）画出直角坐标系； （2）依次做每条约束线，标出可行域的方向，并找出它们共同的 可行域；AQ1Q2x2 （3）任取一目标函数值作一条目标函数线（称等值线），根据
11、目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。3BQ4Q3201x10 1 2 3 4图1 其中，将目标函数Z=2x1+3x2改写为，因此，它可以表示为：以z为参数，以为斜率的一族平行线。位于同一条直线上的点具有相同的值。解的几种情况：（1）此例有唯一解Q2，即x1=4,x2=2,z=14 （2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。 （3）无界解x20x1求max无界但求min有唯一解 （4）无可行解x2x10可行域与最优解间的关系：可行域最优解空 集无最优解（无可行解）有界集唯一最优解
12、多重解无界集无有限最优解（无界解）结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，）； （2）LP问题最优解若存在，则必可在可行域的顶点上得到； （3）LP问题的可行域的顶点个数是有限的； （4）若LP问题有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。 2.基可行解的几何意义 对例1 LP问题标准化为maxZ=2x1+3x2可求得所有的基本解：x(1)=(0,0,8,16,12)T(0点),x(2)=(4,0,4,0,12)T(Q1点)x(3)=(4,2,0,0,4)T(Q2点),x(4)=(2,3,0,8,0
13、)T(Q3点)x(5)=(0,3,2,16,0)T(Q4点),x(6)=(4,3,-2,0,0)T(C点)x(7)=(8,0,0,-16,12)T(A点),x(8)=(0,4,0,16,-4)T(B点)但A、B、C三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。 （6）LP问题可行域顶点的个数=基可行解的个数基的个数Cmn 3.图解法只适用于两个变量（最多含三个变量）的LP问题。 4.求解LP问题方法的思考：完全枚举法，对m、n较大时，Cmn是一个很大
