MBA运筹学实用培训教案

MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。例如，在线性规划中体现为两方面：（1）关于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？运筹学解决问题的要紧方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。随着计算机及计算技术的迅猛进展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，如此能够节约大量的人力和时刻。第一部分线性规划内容框架LP问题差不多概念 数学模型 可行解、最优解实际问题 LP问题 解的概念 差不多解、基可行解提出 差不多最优解 差不多方法 图解法 原始单纯形法 单纯形法 大M法 人工变量法 对偶单纯形法 两时期法 对偶理论 进一步讨论 灵敏度分析──参数规划* 在经济治理领域内应用 运输问题（转运问题） 专门的LP问题 整数规划 多目标LP问题*第一部分线性规划（LinearProgramming）及其应用第一章LP问题的数学模型与求解§1LP问题及其数学模型（一）引例1（生产打算的问题）某工厂在打算期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，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引例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)(1.3)或紧缩形式 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=cx maxz=； maxz=cx或 maxz=cx 或标准型的特点：①目标函数是最大化类型②约束条件均由等式组成③决策变量均为非负④bi(i=1,2,…,n)2.化一般形式为标准型①minzmax(-z)=-cx②“”左边+松驰变量；“”左边－“松驰变量”③变量xj0-xj0变量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个基变量，n－m个非基变量。差不多解与基可行解设B是LP问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该LP问题的一个差不多解。显然，基B与差不多解是一一对应的，差不多解的个数≤Cmn。在差不多解中，称满足非负条件的差不多解为基可行解，对应的基称为可行基。退化解假如基解中非零重量的个数小于m，则称此差不多解为退化的，否则是非退化的。最优基假如对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称差不多最优解。3.LP问题解之间的关系如图所示 差不多解可行解 差不多解可行解基可行解基可行解（五）两个变量LP问题的图解法1.LP问题解的几何表示。以引例为例讲明①②③④maxz=2x①②③④按以下顺序进行：解：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的可行域；AQ1Q2x2③②AQ1Q2x2③②3B3BQ4Q4Q3220101x1①x1①0123401234图1其中，将目标函数Z=2x1+3x2改写为，因此，它能够表示为：以z为参数，以为斜率的一族平行线。位于同一条直线上的点具有相同的值。解的几种情况：（1）此例有唯一解Q2，即x1=4,x2=2,z=14（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。（3）无界解x2x20x10x1求max无界但求min有唯一解（4）无可行解x2x2xx100可行域与最优解间的关系： 可行域 最优解 空集 无最优解（无可行解） 有界集 唯一最优解 多重解 无界集 无有限最优解（无界解）结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）；（2）LP问题最优解若存在，则必可在可行域的顶点上得到；（3）LP问题的可行域的顶点个数是有限的；（4）若LP问题有两个最优解，则其连线上的点差不多上最优解。因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。2.基可行解的几何意义对例1LP问题标准化为 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）≤Cmn3.图解法只适用于两个变量（最多含三个变量）的LP问题。4.求解LP问题方法的考虑：①完全枚举法，对m、n较大时，Cmn是一个专门大的数，几乎不可能；②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。§2单纯形法与计算机求解1.解LP问题单纯形法的差不多思路：求出一个初始基可行解 y停判不此基可行解是否停最优解 N求出使目标函数值得到改善的基可行解2.单纯形法的计算步骤（表格形式）（1）建立初始单纯形表，假定B=I，b≥0设maxZ=c1x1+c2x2+…+cnxn将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：-Z x1 x2 … xm xm+1 … xn 0 1 0 … 0 1m+1 … 1n 10 0 1 … 0 2m+1 … 2n 20 0 0 … 1 mm+1 … mn m-1 c1 c2 … cm cm+1 … cn 0以非基变量表示基变量形式代入Z中的基变量,有 令因此因此，上述的增广矩阵就可写成：Z x1 x2 … xm xm+1 … xn 0 1 0 … 0 1m+1 … 1n 10 0 1 … 0 2m+1 … 2n 20 0 0 … 1 mm+1 … mn m1 0 0 … 0 …－cn 再令则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B）CjC1……Cmcm+1……cniCBxBx1……xmxm+1……xnC1x111……0a1m+1……a1nC2x220……0a2m+1……a2n：：：：：：………：Cmxmm0……1amm+1……amnZZ00……0m+1……nj检验数行上述初始单纯形表可确定初始可行基和初始基可行解：B=(P1,P2,…,Pm)=I,x=(b1,b2,…,bm,0……0)T从初始单纯形表建立的过程能够看到以下事实：（1）凡LP模型中约束条件为“≤”型，在化为标准型后必有B=I，假如b≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数非基变量的系数则以相反数填入检验数行各相应位置。（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。（3）更好表现一般规律的在矩阵形式的单纯形表中设MaxX=CX MaxZ=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-1b－B-1NXN－B-1XL代入目标函数中有 Z=CB(B-1b－B－1NXN－B-1XL)+CNXN+0XL =CBB-1b－CBB-1NXN－CBB-1XL)+CNXN =CBB-1b－(CBB-1N－CN)XN－CBB-1XL将写成对应于基B的矩阵形式的单纯形表T（B）：CCBCNCLXBXNXLXB1B-1NB-1ZCBB-1b0CBB-1N－CNCBB-1例如将例1化成标准型后如下表T（B）：Cj23000iCBXBx1x2x3x4x50x38121000x416400100x51204001-Z0-2-3000σj初始可行基B=(P3,P4,P5)=I,X=(0,0,8,16,12)T（2）判不最优解1在T(B)中，若所有的检验数σj≥0(j=1,2,…,n) 则B为最优基，相应的基可行解为最优解，停止计算。2在T(B)中，若有σk<0(1kn)，且xk的系数列向量Pk0，则该问题无界，停止计算。否则转入（3）（3）换基迭代（基变换）1先确定入基变量Xk:k=min{j|j<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判不最优性准则应是Cj－Zj≤0。④大M法适合于手算，不适用于计算机求解。（2）两时期法第一时期：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：MinW=xn+1+…+xn+m然后用单纯形法求解（1）。若W0，则原问题无可行解，停止计算。若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)（二）退化单纯形法计算中用规则决定换出变量时，有时出现两个以上相同的最小比值，如此在下一次迭代中就有一个或几个基变量等于0，出现退化解，如某个最大化问题的单纯形表为：Cj403000iCBXBx1x2x3x4x5x60x5620101030x43[1]-1010030x651110015Z0-40-3000j0x500[2]1-21004x131-10100/0x63021-1011Z120-4-3400j在出现退化解后的接着迭代中，有可能出现基循环：B1B2……B1如此迭代下去便永久得不到最优解。解决基循环的方法专门多，如“摄动法”、“字典序法”等等。在计算机上常采纳“Bland规则”：（1）取表中下标最小的非基变量xk为换入变量，即k=min{j|j>0}（2）按规则计算，若存在两个相同以上最小比值时，选取下标最小的基变量为换出变量xL，即值得庆幸的是出现基循环是罕见的。§3对偶理论与灵敏度分析一、LP的对偶问题1.引例前已述引例1是一个在有限资源的条件下，求使利润最大的生产打算安排问题，其数学模型为：（设备）（原材料A）（原材料（设备）（原材料A）（原材料B）现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台时和购买工厂的原材料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-1N－CN和CBB-1①②当①②表示LP问题已得到最优解令Y=CBB-1,且②有Y0由于基变量XB的检验数为0，可改写成CBB-1B－CB=0因此，包括基变量在内的所有检验数可写成(CBB-1B－CB,CBB-1N－CN)=(CBB-1A－C)=YA－C≥0即YAC又对② Y=CBB-1，两边右乘b，有Yb=CBB-1b=Z由于Y无上界，因此只有最小值，因此有MinW=Yb它是原问题 {maxZ=CX|AXb,X0}的对偶问题因此，对称形式下两个互为对偶LP问题的数学模型为：MaxZ=CX MinW=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=CX MinW=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.单纯形法的重新解释①（称为原始可行条件）②①（称为原始可行条件）②（称为对偶可行条件）因此，单纯形法是在保持原始可行下，通过迭代，逐步实现对偶可行，达到求出最优解的过程。依照对偶问题的对称性，也能够在保持对偶可行下，通过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法确实是这种思想所设计的。2.对偶单纯形法的计算步骤：举例讲明3.对偶单纯形法与单纯形法的不同之点：①不要求模型中b≥0②先确定换出变量xL，再确定换入变量xK③4.对偶单纯形法适用对象①maxZ=CX(C≤0) ②maxZ=CX（b无限制），③当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法或对偶单纯形法解之④进行灵敏度分析时，有时会用到此法四、对偶解的经济含义和影子价格1.对偶解Y*=CBB-1的经济含义设互为对偶的LP问题 maxZ=CX minW=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+3x2 minW=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限制)(资源1限制)(资源2限制)最终表3100XBx1x2x3x4x121110x400-1[-3]1Z60230x1212/301/3x3001/31-1/3Z60101∴资源1的影价=min{y1*(1),y1*(2)}=min{3,0}=0资源2的影价=min{y2*(1),y2*(2)}=min{0,1}=0影价>0，讲明该资源已耗尽，影价>0，讲明该资源已耗尽，成为短线资源。影价=0，讲明该资源有剩余，成为长线资源。（1）指出企业挖潜革新的途径（2）对市场资源的最优配置起着推进作用（3）可为企业决策者提供调整最优生产方案的信息CBB-1Pj－Cj<0讲明第j种产品应投产CBB-1Pj－Cj>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-1b≥0，则目前的基B仍为最优基，仅在B-1b和CBB-1b的数量上有些改变。若br的变化使B-1b中某些重量小于0，则目前的基成为非可行基，为此，可用对偶单纯形法迭代求得新的最优解。B-1b≥0给出了使最优基B保持不变时△br的同意的变化范围：由解不等式组B-1(b+△b)=B-1b+B-1可得：其中为最终表中列的第i个重量，为B-1中第r列的元素。例2.对价值系数Cj变化的分析（1）当CN中某个Cj发生变化时，只影到非基变量xj的检验数由于若，则△Cj≤σj。这确实是保持最优基不变下，△Cj的同意变化范围。否则，用单纯形法接着迭代，求得新的最优解。（2）当CB中某个Cr发生变化时，则会阻碍到所有非基变量的检验数σN=CBB-1N－CN。解不等式组 =(CB+△CB)B-1N－CN=(CBB-1N－CN)+△CBB-1N≥0即 (CBB-1N－CN)+(0,…,△Cr,…,0)B-1N≥0得到使最优解不变△Cr的同意变化范围；例（3）对增加新产品的分析设革企业在打算期内，拟议生产新产品Xn+1，并已知新产品的单位利润为Cn+1，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，现在应如何分析才能确定该新产品理澡投产？增加新产品应在不阻碍企业目前打算期内最优生产的前提下进行。因此可从现行的最估基B动身考虑：若σn+1=CBB-1Pn+1－Cn+1<0，则应投产若σn+1=CBB-1Pn+1－Cn+1>0，则不应投入。即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。（4）对增加新约束条件的分析在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产打算造成阻碍，如水、电和资源的供应不足等，对生产过程提出了新约束等。对增加新约束条件的分析方法步骤是：第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则讲明新增约束对目前的最优解（即最优生产方案）不构成阻碍（称此约束为不起作用约束），可临时不考虑新增约束条件。否则转下一步；第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。例：（5）技术系数aij变化的分析第一种情况（当jJN）：方法与增加一个新产品的分析相同。第二种情况（当jJB）：由于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销量3656解：这是一个产销平衡的运输问题，其数学模型是：设Xij表示从Ai调运产品到Bj的数量（吨），则minZ=3X11+11X12+3X13+10X14+X21+9X22+2X23+8X24+7X31+4X32+10X33+5X34x11+x12+x13+x14 =7x21+x22+x23+x24 =4x31+x32+x33+x34 =9s.tx11 +x21 +x31 =3s.tx12 +x22 +x32 =6x13 +x23 +x33 =5x14 +x24 +x34 =6xij≥0(i=1,2,3,j=1,2,3,4)一、产量平衡的运输问题及其解法1.产销平衡的运输问题的数学模型及其特点特点：（1）其系数矩阵的结构疏松，且每一列向量 Pij=(0,…1,…1,…0)T=ei+em+j能够证明，r(A)=m+n－1。即有m+n－1个独立方程。因此，该LP问题有且仅有m+n－1个基变量。（2）（产销平衡条件）（3）因为故必有可行解和最优解。由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用专门解法──表上作业法。2.表上作业法表上作业法实质上依旧单纯形法，但具体计算和术语上有所不同。其计算步骤方法，并通过对引例的求解过程讲明之一。（1）用最小元素法确定初始方案（即初始基可行解）切记在产销平衡表上必须且只能填写m+n－1个数字格（2）用位势法求出空格的检验数并进行最优解的判不设u1,u2,…um;v1,v2,…,vn是对应运输问题m+n个约束条件的对偶变量，B为含有人工变量的初始可行基，由LP问题的对偶理论知CBB-1=(u1,u2,…um;v1,v2,…,vn)而每个决策变量Xij相应的系数向量Pij=ei+em+j，因此CBB-1Pij=ui+vj因此，检验数σij=CBB-1Pij－Cij=(ui+vj)－Cij又各基变量的检验数为0，故对每个基变量所在的数格的检验数有(ui+vj)－Cij=0i,jJB即有方程组共m+n个未知数s=m+n－1个方程显然上述方程有解，且由于含有一个自由变量，因此，可令任一未知数为0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。如用位势法求引例初始基可行解的检验数：销地产地B1B2B3B4uiA1-13-211③⑩0A21-19②+1⑧-1A3-107④-12⑩⑤-5vj29310第一步：将运价表中的数字分不写在各格听右上角，并对基变量相应的运价加圈，同时在表中增加vj和ui列。第二步：利用圈数格分不算出ui和vj，即令u1=0，然后按ui+vj=Cij(i,jJB)，相继确定ui，vj的值。因此有v3=3,v4=10,u2=-1,v1=2,u3=-5,v2=9第三步：按σij=(ui+vj)－Cij(i,jJN)算出表中各空格（即非基变量）的检验数：σ11=(0+2)－3=-1，σ12=(0+9)－11=-2，σ22=-1，σ24=1，σ31=-10，σ33=-12由于运输问题的目标函数是求最小化，故判不最优解的准则是所有的σij=CBB-1Pij－Cij≤0因为24=+1>0，因此目前尚未得到最优解，尚须改进（3）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案）i)确定换入变量：自上而上，自左向右第一个正检验数相应的非基变量（空格）为入基变量。ii)作闭回路：以换入变量空格为动身点，用水平或垂直线向前划，当碰到某一恰当数格转90后，接着前进，直至回到起始空格止。iii)确定调整量=min{第奇数次拐角格的调运量}iv)在闭回路上进行调整：对闭回路上每个奇数次拐角格的调运量－对闭回路上每个第偶数次（含起始格）拐角格的调运量+。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。闭回路外的各调运量不变。如此便得到新的调运方案（新基可行解）销地产地B1B2B3B4产量A1(+1)43(-1)7A23(-1)1(+1)4A3639销量3656对调整后所得的新方案，再进行检验，已得到最优解（最优调运方案）；从A1调运到5吨到B3，调运2吨到B4从A2调运到3吨到B1，调运1吨到B4从A3调运到6吨到B2，调运3吨到B4总运费最小是85元（4）在进行表上作业法须注意的问题：i)在最终调运表中，若有某个空格（非基变量）的检验为0时，则表明该运输问题有多重调运方案；ii)在确定初始方案时，若在(i,j)格填上某数字后,出现Ai处的余量=Bj处的需量，现在必须在平衡表上被划去行和列相应位置的任一空格处填上一个“0”，以满足数格=m+n－1个的需要；iii)在用闭回路法调整时，当闭回路上第奇数次拐角数有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证数格=m+n－1个的需要。以上ii)，iii)均出现退化解。iv)用最小元素法所得到的初始方案能够不唯一。二、产销不平衡的运输的问题及其求解方法1.数学模型：产大于销产小于销 2.解法思路：将不平衡转化为平衡。即当时，考虑在平衡表中增加一虚拟列，表示增加一个销货点(j=n+1)如仓库，其销货量为，且各运价Cin+1=0；当时，考虑在平衡表中增加一虚拟行，表示增加一个新产地，且各运价Cm+1j=0。然后再用产销平衡的运输问题的解法进行解之。例三、转运问题及其解法：1.所谓转运问题是在以下背景产生的：(1)每个工厂生产的产品不直接运到销地，能够几个产地集中一起运。(2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。(3)除产、销地之外，还能够有几个中间转运站，在产地之间，销地之间或产销之间转运。凡类似上述情况下的调运物资并使总运费最小的问题统称为转运问题。2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。3.求解“转运问题”的方法步骤：(1)建立扩大的产销平衡运输问题单位运价表。其中1)对两地不能直接运输的单位运价定为M（专门大的正数）；2)对所有中转站Tj的产量和销量定为相等，设定为；3)对产量列的各数据可按下式计算并填入：Ai的产量=ai+,Tj产量=，Bj的产量=4)对销量行的各数据可按下式计算并填入：Aj的产量=,Tj销量=，Bj的销量=+bj(2)用表上作业法进行求解§2指派问题及其解法引例任务人员EJGR甲215134乙1041415丙9141613丁78119当指派第i人去完成第j项工作否则解：设Xij当指派第i人去完成第j项工作否则因此，该问题的数学模型为MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24+9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44表示第j项工作只指派人完成表示第i人被指派完成一项工作Xij=0或1(i,j=1,2,3,4)诸如此类，有n项任务，恰好有n个人可承担这些任务，但由于每人的专长技术不同，完成任务的效率(所费时刻_不同，为使完成n项任务的总效率最高（即所需总时最少），应如何指派（分派）人员的问题统称为指派（分派）问题。一、指派问题的数学模型及其特点1.数学模型：2.特点（1）给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(Cij)nxn,且Cij0，因此必有最优解()。（2）指派问题是一种专门的平衡的运输问题，由于模型结构的专门性（看作每产地的产量均为1，每销地的销量均为1），故可用更为简便的匈牙利法进行求解。（3）解矩阵是指派问题的可行解，但不一定是最优解。二、指派问题的解法──匈牙利法1.匈牙利法的差不多思想是：对同一项工作（任务）j来讲，同时提高或降低每人相同的效率（常数ti），不阻碍其最优指派；同样，对同一个人i来讲，完成各项工作的效率都提高或降低相同的效率（常数di），也不阻碍其最优指派，因此可得到新的效率矩阵(bij)nxn，其中bij=Cij+ti+dj（对所有的i,j）则新的目标函数为 其中为常数这讲明Z与Z同时达到最小值。因而最优解相同。故指派问题有以下性质：若从效率矩阵(Cij)nxn的一行（列）各元素中分不减去该行（列）的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解。2.匈牙利法三、对求最大化的指派问题，（即求）,可采纳构造新的效率矩阵(M－Cij)nxn，其中M=max{Cij}，（显然M－Cij0），将其转化为求所得到的最优解确实是原问题的最优解。事实上由于nM为常数，因此，使Z取得最小的最优解确实是使Z取得最大的最优解。4.以上讨论的指派问题是效率矩阵的行数等于列数，即m+n的情况。当mn时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再用匈牙利法求解。m-n列n-m行当m<n时 当m>n时m-n列n-m行5.指派问题必有最优解，但能够不唯一。§3整数线性规划问题及其解法一、整数线性规划在上一章讨论的LP问题中,对决策变量只限于不能取负值的连续型数值,即能够是正分数或正小数。然而在许多经济治理的实际问题中，决策变量