运筹管理--MBA运筹学讲义（DOC 51页）(2)

-1-MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。例如，在线性规划中体现为两方面：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。-2-第一部分线性规划内容框架LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提出基本最优解基本方法图解法原始单纯形法单纯形法大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析──参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*第一部分线性规划（LinearProgramming）及其应用第一章LP问题的数学模型与求解§1LP问题及其数学模型（一）引例1（生产计划的问题）某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品-3-所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？ⅠⅡ资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：机器设备的限制条件：x1+2x2≤8原材料A的限制条件：4x1≤16（称为资源约束条件）原材料B的限制条件：4x2≤12同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有x1≥0，x2≥0（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数Z=2x1+3x2的值达到最大。综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x1+3x2-4-012416482..212121xxxxxxts引例2.（营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10x16x23x32x4)4,3,2,1(08005003002004005510206050300020090080010000.432143214321jxxxxxxxxxxxxxtxj（二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。-5-（1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：max(或min)z=c1x1+c2x2+…+cnxn(1.1)0),(),(),(.2122212222222111212211nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats(1.2)或紧缩形式max(或min)z=njjjxc10),,2,1(),(1jnjijjxmibxa(1.4)或矩阵形式max(或min)z=cx(1.3)-6-0),(XbAX(1.5)或向量形式：max(或min)z=cx),,2,1(0),(1njXbxpjnjjj(1.6)其中C=(c1,c2,…,cn)，称为价值系数向量；mnmmnnaaaaaaaaaA,,,,,,212222111211称为技术系数矩阵（并称消耗系数矩阵）=(p1,p2,…,pn)mbbbb21称资源限制向量X=(x1,x2,…,xn)T称为决策变量向量。（三）LP问题的标准型1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须把LP问题的一般形式化为统一的标准型：maxz=njjjxc1；maxz=cx-7-),,2,1(0),,2,1(1njxmibxajnjijj或0XbAXmaxz=cx或),,2,1(01njxbxpjnjjj标准型的特点：①目标函数是最大化类型②约束条件均由等式组成③决策变量均为非负④bi(i=1,2,…,n)2.化一般形式为标准型①minzmax(-z)=-cx②“”左边+松驰变量；“”左边－“松驰变量”③变量xj0-xj0变量xj无限制令xj=xj－xj④bi0等式两边同乘以(-1)。3.模型隐含的假设①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。③连续性假定：决策变量应取连续值。-8-④确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问题是确定型问题，不含随机因素。以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规划，整数规划或不确定型分析方法。对LP标准型，我们还假定r(A)=mn。（四）LP问题的解的概念设LP问题maxz=njjjxc1(1.7)njijjnibxa1),,2,1((1.8)),,2,1(0njxj(1.9)1.从代数的角度看：可行解和最优解满足约束条件(1.8)和(1.9)的解X=(x1,x2,…,xn)T称为可行解。所有可行解构成可行解集，即可行域}0,{xbAXSx。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。2.从LP角度看：-9-基：设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个基变量，n－m个非基变量。基本解与基可行解设B是LP问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一对应的，基本解的个数≤Cmn。在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。退化解如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。最优基如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。3.LP问题解之间的关系如图所示（五）两个变量LP问题的图解法1.LP问题解的几何表示。以引例为例说明可行解基本解基可行解-10-maxz=2x1+3x20,012416482212121xxxxxx按以下顺序进行：解：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。图1①②③④x2②③①Q2Q3Q4BQ1Ax1321001234-11-其中，将目标函数Z=2x1+3x2改写为zxx313212，因此，它可以表示为：以z为参数，以32为斜率的一族平行线。位于同一条直线上的点具有相同的值。解的几种情况：（1）此例有唯一解Q2，即x1=4,x2=2,z=14（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。（3）无界解求max无界但求min有唯一解（4）无可行解x2x10x2-12-可行域与最优解间的关系：可行域最优解空集无最优解（无可行解）有界集唯一最优解多重解无界集无有限最优解（无界解）结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）；（2）LP问题最优解若存在，则必可在可行域的顶点上得到；（3）LP问题的可行域的顶点个数是有限的；（4）若LP问题有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。2.基可行解的几何意义对例1LP问题标准化为maxZ=2x1+3x20,,12416482515241321xxxxxxxxx可求得所有的基本解：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)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点)0x1-13-但A、B、C三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。（6）LP问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn3.图解法只适用于两个变量（最多含三个变量）的LP问题。4.求解LP问题方法的思考：①完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能；②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。§2单纯形法与计算机求解1.解LP问题单纯形法的基本思路：求出一个初始基可行解y判别此基可行解是否最优解N求出使目标函数值得到改善的基可行解2.单纯形法的计算步骤（表格形式）（1）建立初始单纯形表，假定B=I，b≥0停-14-设maxZ=c1x1+c2x2+…+cnxn),,2,1(011221122111111njxbxaxaxbxaxaxbxaxaxjmnmnmmmmnnmmnnmm将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：-Zx1x2…xmxm+1…xnb0