运筹管理--MBA运筹学讲义.docx

MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。 例如，在线性规划中体现为两方面： （1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？ （2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？ 运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。第一部分 线性规划内容框架LP问题基本概念数学模型可行解、最优解实际问题LP问题解的概念基本解、基可行解提 出基本最优解基本方法图解法原始单纯形法单纯形法 大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*第一部分 线性规划（Linear Programming）及其应用第一章 LP问题的数学模型与求解 §1 LP问题及其数学模型 （一）引例1（生产计划的问题） 某工厂在计划期内要安排生产、的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？资源限量设备128(台时)原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。解：设x1,x2分别表示在计划期内生产产品、的产量。由于资源的限制，所以有：机器设备的限制条件：x1+2x28原材料A的限制条件： 4x116（称为资源约束条件）原材料B的限制条件： 4x212同时，产品、的产量不能是负数，所以有x10，x20（称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数Z=2x1+3x2的值达到最大。综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x1+3x2引例2. （营养配餐问题）假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量(卡路里)蛋白质(克)钙(mg)价格(元)1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为minz=10x16x23x32x4 （二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。（1）每个问题都可用一组决策变量(x1,x2,xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。（2）存在一组线性等式或不等式的约束条件。（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：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或标准型的特点：目标函数是最大化类型约束条件均由等式组成决策变量均为非负bi(i=1,2,n)2.化一般形式为标准型minz®max(-z)=-cx“£”®左边+松驰变量；“³”®左边“松驰变量”变量xj£0®-xj³0变量xj无限制®令xj=xj¢xj²bi<0®等式两边同乘以(-1)。3.模型隐含的假设比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。连续性假定：决策变量应取连续值。确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问题是确定型问题，不含随机因素。以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规划，整数规划或不确定型分析方法。对LP标准型，我们还假定r(A)=m<n。（四）LP问题的解的概念设LP问题maxz=(1.7)(1.8)(1.9) 1.从代数的角度看：可行解和最优解 满足约束条件(1.8)和(1.9)的解X=(x1,x2,xn)T称为可行解。所有可行解构成可行解集，即可行域。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。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与基本解是一一对应的，基本解的个数Cmn。在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。退化解 如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。3.LP问题解之间的关系如图所示W基本解可行解基可行解（五）两个变量LP问题的图解法 1.LP问题解的几何表示。以引例为例说明maxz=2x1+3x2按以下顺序进行：解：（1）画出直角坐标系； （2）依次做每条约束线，标出可行域的方向，并找出它们共同的 可行域；AQ1Q2x2 （3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。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可行域与最优解间的关系：可行域最优解空 集无最优解（无可行解）有界集唯一最优解多重解无界集无有限最优解（无界解）结论：（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)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是一个很大的数，几乎不可能；从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。 §2 单纯形法与计算机求解 1.解LP问题单纯形法的基本思路：求出一个初始基可行解y停判别此基可行解是否最 优 解N求出使目标函数值得到改善的基可行解 2.单纯形法的计算步骤（表格形式） （1）建立初始单纯形表，假定B=I，b0 设maxZ=c1x1+c2x2+cnxn将目标函数改写为：-Z+c1x1+c2x2+cnxn=0把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：-Zx1x2xmxm+1xn01001m+11n100102m+12n20001mm+1mnm-1c1c2cmcm+1cn0以非基变量表示基变量形式代入Z中的基变量,有 令 于是因此，上述的增广矩阵就可写成：Zx1x2xmxm+1xn01001m+11n100102m+12n20001mm+1mnm1000cn 再令则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B）CjC1Cmcm+1cnqiCBxBx1xmxm+1xnC1x1110a1m+1a1nC2x2200a2m+1a2n： ：Cmxmm01amm+1amnZZ000sm+1sn¬sj检验数行上述初始单纯形表可确定初始可行基和初始基可行解：B=(P1,P2,Pm)=I, x=(b1,b2,bm, 00)T从初始单纯形表建立的过程可以看到以下事实： （1）凡LP模型中约束条件为“”型，在化为标准型后必有B=I，如果b0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数非基变量的系数则以相反数填入检验数行各相应位置。 （2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。 （3）更好表现一般规律的在矩阵形式的单纯形表中设MaxX=CXMaxZ=CX+0XL 其标准型为 将系数矩阵(A,I)分划为(B,N,I)，其中B为可行基，对应于基变量向量XB,N对应于XN，I对应于XL,(XN,XL)为非基变量向量。于是(X,L)T=(XB,XN,XL)T,(C,0)=(CB,CN,0)。因此，矩阵形式的LP模型改写为： ® 用非基变量向量表示基变量向量，有 XB=B-1bB-1NXNB-1XL 代入目标函数中有Z =CB(B-1bB1NXNB-1XL)+CNXN+0XL =CBB-1bCBB-1NXNCBB-1XL)+CNXN =CBB-1b(CBB-1NCN)XNCBB-1XL将 写成对应于基B的矩阵形式的单纯形表T（B）：C®CBCNCLXBXNXLXB1B-1NB-1ZCBB-1b0CBB-1NCNCBB-1例如将例1 化成标准型后如下表T（B）：Cj23000qiCBXBx1x2x3x4x50x38121000x416400100x51204001-Z0-2-3000¬j初始可行基B=(P3,P4,P5)=I, X=(0,0,8,16,12)T （2）判别最优解 1° 在T(B)中，若所有的检验数j0 (j=1,2,n)则B为最优基，相应的基可行解为最优解，停止计算。 2° 在T(B)中，若有k<0 (1£k£n)，且xk的系数列向量Pk£0，则该问题无界，停止计算。否则转入（3） （3）换基迭代（基变换） 1° 先确定入基变量Xk: k=minj| sj<0 2° 按最小比值原则确定出基变量xL： 3° 以为主元，进行初等行变换（又称旋转变换）即将列向量变换为单位列向量：返回（2）。换基迭代的关键在于将换入变量对应的列向量用初等行变换方法变换成单位列向量。其中主元变成1。即第L个分量如果在最终表中有非基变量的检验数为0，则该问题有多重最优解。 3.单纯形法的进一步讨论用人工变量法求初始基可行解 （一）人工变量法若对LP模型标准化后，不具有B=I时，如何办？此时可采用人工变量法得到初始基可行解。所谓人工变量法是在原问题不含有初始可行基B=I的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP问题后求解。当增加的人工变量全部取值为0时，才与原问题等价。这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，则原问题的约束条件被恢复，同时也得到一个基可行解。在最终表中若不能全部被换出，则说明原问题无可行解。因此，该法的关键在于将人工变量全部换出。人工变量法常见的有大M法和两阶段法。 （1）大M法（通过下例简略介绍其方法与步骤） 例，用大M法求解MinZ=x1+1.5x2解：MinZ=x1+1.5x2+0.x3+0.x4+Mx5+Mx6其中x3,x4为松驰变量，x5,x6为人工变量，M为任意大的正数。注意到：分别在约束条件增加人工变量x5,x6是为了构成“人工基” 对于Min的目标函数采用(+M)，而对于Max的目标函数则采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。 对于minZ判别最优性准则应是CjZj0。 大M法适合于手算，不适用于计算机求解。（2）两阶段法第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：MinW=xn+1+xn+m然后用单纯形法求解（1）。若W¹0，则原问题无可行解，停止计算。若W=0，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换入原问题的目标函数作为第二阶段计算的初始表。仍以上例为例用两阶段法求解。MinZ=x1+1.5x2+0x3+0x4原问题：MinW=x5+x6辅助问题：书中第19页表2.9和表2.10的说明：（1）第一阶段的初始表中非基变量的检验数=人工变量所在行的非基变量相应系数之和，目标函值值=人工变量所在行相应常数之和。（2）第二阶段单纯形表中目标函数系数应将非基变量表示基变量后所得结果填入，或先直接填入原系数，再通过初等行变换使基变量的检验数为0。 （3）若maxZ，则可转化为minZ1(Z1=-Z) （二）退化单纯形法计算中用q规则决定换出变量时，有时出现两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于0，出现退化解，如某个最大化问题的单纯形表为：Cj403000qiCBXBx1x2x3x4x5x60x5620101030x431-1010030x651110015Z0-40-3000¬sj0x50021-21004x131-10100/0x63021-1011Z120-4-3400¬sj在出现退化解后的继续迭代中，有可能出现基循环：B1®B2®®B1这样迭代下去便永远得不到最优解。解决基循环的方法很多，如“摄动法”、“字典序法”等等。在计算机上常采用“Bland规则”：（1）取表中下标最小的非基变量xk为换入变量，即k=minj | sj>0 （2）按q规则计算，若存在两个相同以上最小比值时，选取下标最小的基变量为换出变量xL，即值得庆幸的是出现基循环是罕见的。 §3 对偶理论与灵敏度分析 一、LP的对偶问题 1.引例 前已述引例1是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：（设备）（原材料A）（原材料B）maxZ=2x1+3x2现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台时和购买工厂的原材料A、B，为其加工生产别的产品，由客户支付台时费和材料费，此时工厂应考虑如何为每种资源的定价问题？解：设y1,y2,y3分别表示出租单位设备台时的租金和出售单位原材料A、B的价格（含附加值）工厂决策者考虑： （1）出租设备和出售原材料应不少于自己生产产品的获利，否则不如自己生产为好。因此有工厂的总收入为W=8y1+16y2+12y3（2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价）租赁者考虑：希望价格越低越好，否则另找他人。于是，能够使双方共同接受的是MinW=8y1+16y2+12y3上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。2.从矩阵形式讨论互为对偶LP问题由例1 有maxZ=cx由矩阵形式的单纯形表中可知：检验数的表达式为：CBB-1NCN和CBB-1 当表示LP问题已得到最优解令Y=CBB-1,且有Y³0由于基变量XB的检验数为0，可改写成CBB-1BCB=0因此，包括基变量在内的所有检验数可写成(CBB-1BCB, CBB-1NCN)=(CBB-1AC)= YAC0即YA³C又对Y=CBB-1，两边右乘b，有Yb=CBB-1b=Z由于Y无上界，所以只有最小值，因此有MinW=Yb它是原问题maxZ=CX| AX£b,X³0的对偶问题于是，对称形式下两个互为对偶LP问题的数学模型为：MaxZ=CXMinW=Yb与任何一个LP问题均有一个对偶LP问题与之匹配。对偶理论就是研究LP问题及其对偶问题的理论，它是LP理论中的重要内容之一。二、对偶理论 1.原问题与对偶问题的关系如下表所示原 始 对 偶 表原问题Max（对偶问题）对偶问题Min（原问题）约束条件数=m 变量个数=m第i个约束条件为“”第i个约束条件为“”第i个约束条件为“=” 第i个变量0 第i个变量0 第i个变量无限制变量个数=m 约束条件个数=n第i个变量0第i个变量0第i个变量无限制 第i个约束条件为“” 第i个约束条件为“” 第i个约束条件为“=”第i个约束条件的右端项目标函第i个变量的系数 目标函数第i个变量的系数 第i个约束条件的右端顶2.对偶问题的基本性质MaxZ=CXMinW=Yb设 （1）（对称性）对偶问题的对偶是原问题；（2）（弱对偶性）若是原问题的可行解，是对偶问题的可行解； 则；（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解；（4）（最优性准则），若、分别是互为对偶问题的可行解，且C=b，则、分别是它们的最优解；（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：原问题与对偶问题都有最优解，且CX=Yb；一个问题具有无界解，则它的对偶问题无可行解；两个问题均无可行解。（6）（互补松驰性），若X*、Y*分别是原问题的对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS,YS分别是原问题和对偶问题的松驰变量向量)。或，X*、Y*分别是原问题和对偶问题最优解的充要条件是：若y*i>0，则åaijX*j=bi若åaijX*j<b，则y*i=0若X*j>0，则åaijy*i=cj若åaijy*i>cj，则X*j=0 三、对偶单纯形法 1.单纯形法的重新解释 （称为原始可行条件） （称为对偶可行条件）X*是最大化原LP问题最优解的充要条件是同时满足因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是这种思想所设计的。2.对偶单纯形法的计算步骤：举例说明 3.对偶单纯形法与单纯形法的不同之点：不要求模型中b0先确定换出变量xL，再确定换入变量xK 4.对偶单纯形法适用对象maxZ=CX(C0)maxZ=CX（b无限制），当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法或对偶单纯形法解之进行灵敏度分析时，有时会用到此法 四、对偶解的经济含义和影子价格 1.对偶解Y*=CBB-1的经济含义 设互为对偶的LP问题maxZ=CXminW=Yb (原)(对) 有 Z*=CBB-1b=W* (其中B为最优基) 因此 或者说Z*=y*1b1+y*2b2+y*mbm 则其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是Yi*。换句话说，Yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上Yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是：maxZ=2x1+3x2minW=8y1+16y2+12y3(原问题)(对偶问题)对原问题用单纯形法求解所得最终表为C23000CBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80Z14001.50.1250由此，它们的最优解分别是X*=(4,2)T和Y=(1.5,0.125,0) Z*=W*=14=8Y1*+16Y2*12Y3* 其中Y1*=1.5表示单独对设备台时增加1个单位，可使Z值增加1.5个单位的利润；Y2*=0.125表示单独对原材料A增加1个单位，可使Z值增加0.125个单位的利润；而Y3*=0表示单独对原材料B增加一个单位，却不使Z值增加。这是因为从最终表中可看出，在最优方案中，松驰变量x5=4，即表示在最优生产方案中，原材料B尚有4个单位剩余被闲置，不产生任何经济效益。 2.影子价格的定义把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格。影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。资源的影子价格定量的反映了单位资源在最优生产方案中为总收益应提供的收益，因此，资源的影子价格也可称为在最优方案中投入生产的机会成本。3.影子价格的求法 (1)在非退化情况下：设B为LP问题的最优基，则 资源的影价=Y*=CBB-1 (2)在退化情况下： 当对偶问题有K个最优解，则第i种资源的影价=即影价的第i个分量等于这K个对偶解中第i个分量的最小值。例如，设某资源利用问题为(资源1限制)(资源2限制) maxZ=3x1+x2最 终 表3100XBx1x2x3x4x121110x400-1-31Z60230x1212/301/3x3001/31-1/3Z60101 资源1的影价 =miny1*(1),y1*(2) =min3,0=0 资源2的影价=miny2*(1),y2*(2)=min0,1=0影价>0，说明该资源已耗尽， 成为短线资源。影价=0，说明该资源有剩余， 成为长线资源。 4.影子价格的参谋作用 （1）指出企业挖潜革新的途径 （2）对市场资源的最优配置起着推进作用 （3）可为企业决策者提供调整最优生产方案的信息 CBB-1PjCj<0说明第j种产品应投产 CBB-1PjCj>0说明第j种产品不应投产尤其对新产品是否应投产，可按以上两式考虑。（4）可以预测产品的价格 （5）可作为同类企业经济效益评估指标之一。 五、灵敏度分析面对市场变化，灵敏度分析的任务是须解决以下两类问题：（1）当系数A、b、c中的某个发生变化时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）？ （2）为保持目前最优基仍是最优基，参数A、b、c允许变化范围是什么？ 灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的成立？ 1.对资源数量br变化的分析当b中某个br发生改变时，将影响基变量的取值XB=B-1b。若br的变化仍满足B-1b0，则目前的基B仍为最优基，仅在B-1b和CBB-1b的数量上有些改变。若br的变化使B-1b中某些分量小于0，则目前的基成为非可行基，为此，可用对偶单纯形法迭代求得新的最优解。B-1b0给出了使最优基B保持不变时br的允许的变化范围：由解不等式组 B-1(b+b)=B-1b+B-1可得： 其中为最终表中列的第i个分量，为B-1中第r列的元素。 例 2.对价值系数Cj变化的分析 （1）当CN中某个Cj发生变化时，只影到非基变量xj的检验数 由于 若，则Cjj。 这就是保持最优基不变下，Cj的允许变化范围。否则，用单纯形法继续迭代，求得新的最优解。 （2）当CB中某个Cr发生变化时，则会影响到所有非基变量的检验数N=CBB-1NCN。解不等式组=(CB+CB)B-1NCN=(CBB-1NCN)+CBB-1N0 即(CBB-1NCN)+(0,Cr,0)B-1N0得到使最优解不变Cr的允许变化范围； 例 （3）对增加新产品的分析设革企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润为Cn+1，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,am,n+1)T，此时应如何分析才能确定该新产品理澡投产？增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最估基B出发考虑：若n+1=CBB-1Pn+1Cn+1<0，则应投产若n+1=CBB-1Pn+1Cn+1>0，则不应投入。 即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。 （4）对增加新约束条件的分析在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新约束等。对增加新约束条件的分析方法步骤是：第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。例：（5）技术系数aij变化的分析第一种情况（当jÎJN）：方法与增加一个新产品的分析相同。第二种情况（当jÎJB）：由于B中元素的改变影响到B-1的变化，因此也影响到T(B)。目前的基B对应的解有可能既不是原始可行，也不是对偶可行。于是不如重新求解。第二章 特殊LP问题及其解法所谓特殊LP问题是指LP模型的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的求解方法，从而节省人力和物力。§1 运输问题及其解法引例：某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-7吨，A2-4吨，A3-9吨。该公司把这些产品分别运往四个销售点，各销售每日销量为：B1-3吨，B2-6吨，B3-5吨，B4-6吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少。平衡表（单位：吨）运价表（单位：元/吨）销地产地B1B2B3B4产量B1B2B3B4A17311310A241928A3974105销