运筹管理MBA运筹学讲义2

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)a11x2a12x2a1nxn(,)b1a21x2a22x2a2nxn(,)b2s.t(1.2)am1x2am2x2amnxn(,)bm(1.3)x1x2xn0或收缩形式nmax(或min)z=cjxjj1najxj(,)bi(i1,2,,m)j1(1.4)xj0或矩阵形式max(或min)z=cxAX(,)b(1.5)X0或向量形式：max(或min)z=cxnpjxj(,)bj1(1.6)Xj0(j1,2,,n)此中C=(c,c,,cn)，称为价值系数向量；12a11,a12,a1na21,a22,a2n称为技术系数矩阵（并称耗费系数矩阵）Aam1,am2,amn=(p1,p2,,pn)b1b2b称资源限制向量bmX=(x1,x2,,xn)T称为决议变量向量。（三）LP问题的标准型为了议论LP问题解的观点和解的性质以及对LP问题解法方便，一定把LP问题的一般形式化为一致的标准型：nmaxz=cjxj；j1maxz=cxnAXbajxjbi(i1,2,,m)j1或xj0(j1,2,,n)X0maxz=cxn或pjxjbj1xj0(j1,2,,n)标准型的特色：①目标函数是最大化种类②拘束条件均由等式构成③决议变量均为非负④bi(i=1,2,,n)化一般形式为标准型①minzmax(-z)=-cx②“”左侧+松驰变量；“”左侧－“松驰变量”③变量xj0-xj0变量xj无穷制令xj=xj－xj④bi<0等式两边同乘以(-1)。模型隐含的假定①比率性假定：决议变量变化的改变量与惹起目标函数的改变量成比率；决议变量变化的改变量与惹起拘束方程左端值的改变量成比率。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的耗费也是一个常数。②可加性假定：每个决议变量对目标函数和拘束方程的影响是独立于其他变量的。③连续性假定：决议变量应取连续值。④确立性假定：所有的参数(aij,bi,cj)均为确立，所以LP问题是确立型问题，不含随机要素。以上4个假定均因为线性函数所致。在现实生活中，完整知足这4个假定的例子其实不常见，所以在使用LP时一定注意问题在什么程度上知足这些假定。若不知足的程度较大时，应试虑使用其他模型和方法。如非线性规划，整数规划或不确立型剖析方法。对LP标准型，我们还假定r(A)=m<n。（四）LP问题的解的观点设LP问题nmaxz=cjxj(1.7)j1najxjbi(i1,2,,n)(1.8)j1xj0(j1,2,,n)(1.9)从代数的角度看：可行解和最优解知足拘束条件(1.8)和(1.9)12nT的解X=(x,x,,x)称为可行解。所有可行解构成可行解集，即可行域S{XAxb,x0}。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。从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与基本解是一一对应的，基本解的个数≤mCn。在基本解中，称知足非负条件的基本解为基可行解，对应的基称为可行基。退化解假如基解中非零重量的个数小于m，则称此基本解为退化的，不然是非退化的。最优基假如对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。3.LP问题解之间的关系以下图基本可行解解基可行解（五）两个变量LP问题的图解法1.LP问题解的几何表示。以引例为例说明maxz=2x1+3x2按以下次序进行：①②解：（1）画出直角坐标系；③④（2）挨次做每合拘束线，标出可行域的方向，并找出它们共同的可行域；（3）任取一目标函数值作一条目标函数线（称等值线），依据目标函数（最大或最小）种类，平移该直线马上走开可行域上，则与目标函数线接触的最后点即表示最优解。0Bx2②Q4Q3213①③x1012342图1此中，将目标函数Z=2x+3x改写为2x11z，所以，它能够表示为：以z为3312参数，以2为斜率的一族平行线。位于同一条直线上的点拥有相同的值。3Q1A解的几种状况：（1）此例有独一解Q2，即x1=4,x2=2,z=14（2）有无量多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。（3）无界解x20x1求max无界但求min有独一解（4）无可行解x20

x1可行域与最优解间的关系：可行域最优解空集无最优解（无可行解）有界集独一最优解多重解无界集无有限最优解（无界解）结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，）；（2）LP问题最优解若存在，则必可在可行域的极点上获取；（3）LP问题的可行域的极点个数是有限的；（4）若LP问题有两个最优解，则其连线上的点都是最优解。所以，求解LP问题可转变为怎样在可行域的极点上求出使目标函数值达到最优的点的问题。基可行解的几何意义对例1LP问题标准化为maxZ=2x+3x12可求得所有的基本解：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问题可行域极点的个数=基可行解的个数≤基的个数≤Cmn3.图解法只合用于两个变量（最多含三个变量）的LP问题。求解LP问题方法的思虑：①完整列举法，对m、n较大时，Cmn是一个很大的数，几乎不行能；②从可行域的一个极点（基可行解）迭代到另一个极点（基可行解）。§2纯真形法与计算机求解解LP问题纯真形法的基本思路：求出一个初始基可行解y鉴别此基可行解能否停最优解N求出使目标函数值获取改良的基可行解纯真形法的计算步骤（表格形式）（1）成立初始纯真形表，假定B=I，b≥0设maxZ=c1x1+c2x2++cnxn将目标函数改写为：-Z+c1x1+c2x2++cnxn=0把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：-Zx1x2xmxm+1xnb0100a1m+1a1nb0010a2m+1a2nb0001amm+1amnbm

12-1c1c2cmcm+1cn0xibinaijxj代入Z中的基变量,有以非基变量表示基变量形式j1mm令Z0cibi,Zjciaiji1i1n于是ZZo(Zjcj)xjjm1所以，上述的增广矩阵便可写成：Zx1x2xmxm+1xnb0100a1m+1a1nb10010a2m+1a2nb20001amm+1amnbm1000mmin－cnmcaccibiii1i1i1m再令jcjZjcjciaiji1则上述增广矩阵可写成下边表格形式：即初始纯真形表T（B）CjC1Cmcm+1cnCBxBx1xmxm+1xniCx1b110aa11m+11nCx2b200aa22m+12n：：：：：：：Cxmbm01aammm+1mnZZ00nj查验数行0m+1上述初始纯真形表可确立初始可行基和初始基可行解：B=(P1,P2,,Pm)=I,x=(b1,b2,,bm,00)T从初始纯真形表成立的过程能够看到以下事实：（1）凡LP模型中拘束条件为“≤”型，在化为标准型后必有B=I，假如b≥0，则模型中拘束方程的各数据不改变符号照抄在表中相应的地点。目标函数非基变量的系数则以相反数填入查验数行各相应地点。（2）在纯真形表中，凡基变量所在的列向量必是单位列向量，其相应的查验数均为零。mm（3）Z0cibi,jZjcjciaijcj(jm1,n)i1i1更好表现一般规律的在矩阵形式的纯真形表中设MaxX=CXMaxZ=CX+0XLAxb其标准型为AxIxLbx0x,xL0将系数矩阵(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,N,I)XNbBXBNXNIXLbXLXB,XN,XL0XB,XN,XL0用非基变量向量表示基变量向量，有XB=B-1b－B-1NX－B-1XL代入目标函数中有-1－1-1Z=CB(Bb－BNX－BXL)+CNXN+0XL-1-1-1=CBBb－CBBNX－CBBXL)+CNXN-1-1-1=CBBb－(CBBN－CN)XN－CBBXL将写成对应于基B的矩阵形式的纯真形表T（B）：CCBCNCLXXXBNLXB1B-1NB-1ZCBB-1b0CBB-1N－CNCBB-1比如将例1化成标准型后以下表T（B）：Cj23000CBXBx1x2x3x4x5i0x38121000x416400100x51204001-Z0-2-3000σjT初始可行基B=(P3,P4,P5)=I,X=(0,0,8,16,12)（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}按最小比值原则确立出基变量xL：3以aLK为主元，进行初等行变换（又称旋转变换）马上列向量PK变换为单位列向量：返回（2）。换基迭代的重点在于将换入变量对应的列向量PK用初等行变换方法变换成单位列向量。此中主元aLK变为1。即a1k0a2k0Pk::a1k第L个重量1::amk0假如在最后表中有非基变量的查验数为0，则该问题有多重最优解。纯真形法的进一步议论──用人工变量法求初始基可行解（一）人工变量法若对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+0x4x13x2x33原问题：x1x2x42x1,x20,x3,x40MinW=x5+x6x13x2x3x53协助问题：x1x2x4x62x1,x20,x3,x40,x5,x60书中第19页表2.9和表2.10的说明：（1）第一阶段的初始表中非基变量的查验数

=人工变量所内行的非基变量相应系数之和，目标函值值=人工变量所内行相应常数之和。（2）第二阶段纯真形表中目标函数系数应将非基变量表示基变量后所得结果填入，

或先直接填入原系数，再经过初等行变换使基变量的查验数为0。（3）若maxZ，则可转变为

minZ1(Z1=-Z)（二）退化纯真形法计算顶用规则决定换出变量时，有时出现两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于0，出现退化解，如某个最大化问题的纯真形表为：Cj403000CBXBx1x2x3x4x5x6i0x5620101030x43[1]-1010030x651110015Z0-40-3000j0x500[2]1-21004x131-10100/0x63021-1011Z120-4-3400j在出现退化解后的持续迭代中，有可能出现基循环：B1B2B1这样迭代下去便永久得不到最优解。解决基循环的方法好多，如“摄动法”、“词典序法”等等。在计算机上常采纳“Bland规则”：（1）取表中下标最小的非基变量xk为换入变量，即k=min{j|j>0}（2）按规则计算，若存在两个相同以上最小比值时，选用下标最小的基变量为换出变量xL，即值得有幸的是出现基循环是稀有的。3对偶理论与敏捷度剖析一、LP的对偶问题引例前已述引例1是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：maxZ=2x1+3x2（设施）现从另一角度考虑此问题。假定有客户提出要求，租借工厂的设施台时和购置工厂的（原资料A）原资料A、B，为其加工生产其他产品，由客户支付台时费和资料费，此时工厂应试虑怎样（原资料B）为每种资源的订价问题？解：设y1,y2,y3分别表示出租单位设施台时的租金和销售单位原资料A、B的价钱（含附带值）工厂决议者考虑：（1）出租设施和销售原资料应许多于自己生产产品的赢利，不然不如自己生产为好。所以有工厂的总收入为W=8y1+16y2+12y3（2）价钱应尽量低，不然没有竞争力（此价钱可成为与客户谈判的底价）租借者考虑：希望价钱越低越好，不然另找别人。于是，能够使双方共同接受的是MinW=8y1+16y2+12y3上述两个LP问题的数学模型是在同一公司的资源状况和生产条件下产生的，且是同一个问题从不一样角度考虑所产生的，所以二者亲密有关。称这两个LP问题是互为对偶的两个LP问题。此中一个是另一个问题的对偶问题。从矩阵形式议论互为对偶LP问题由例1有maxZ=cx由矩阵形式的纯真形表中可知：查验数的表达式为：CBB-1N－CN和CBB-1CBB1NCN0①当1CBB0②表示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=CXMinW=YbYXbYACX与Y00任何一个LP问题均有一个对偶LP问题与之般配。对偶理论就是研究LP问题及其对偶问题的理论，它是LP理论中的重要内容之一。二、对偶理论原问题与对偶问题的关系以下表所示原始对偶表原问题Max（对偶问题）对偶问题Min（原问题）拘束条件数=m变量个数=m第i个拘束条件为“”第i个变量≥0第i个拘束条件为“≥”第i个变量≤0第i个拘束条件为“=”第i个变量无穷制变量个数=m拘束条件个数=n第i个变量≥0第i个拘束条件为“”第i个变量≤0第i个拘束条件为“≥”第i个变量无穷制第i个拘束条件为“=”第i个拘束条件的右端项目标函数第i个变量的系数目标函第i个变量的系数第i个拘束条件的右端顶)。或，X*、对偶问题的基天性质MaxZ=CXMinW=YbYXbYAC设0Y0X（1）（对称性）对偶问题的对偶是原问题；（2）（弱对偶性）若X是原问题的可行解，Y是对偶问题的可行解；则CXYb；（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解；（4）（最优性准则），若X、Y分别是互为对偶问题的可行解，且CX=Yb，则X、分别是它们的最优解；（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。从上述性质中，可看到原问题与对偶问题的解必定是以下三种状况之一：①原问题与对偶问题都有最优解，且CX=Yb；②一个问题拥有无界解，则它的对偶问题无可行解；③两个问题均无可行解。（6）（互补松驰性），若X*、Y*分别是原问题的对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(此中XS,YS分别是原问题和对偶问题的松驰变量向量Y*分别是原问题和对偶问题最优解的充要条件是：①若y*i>0，则aijX*j=bi②若aijX*j<b，则y*i=0③若X*j>0，则

aij

y*

i=cj④若aijy*i>cj，则X*j=0三、对偶纯真形法纯真形法的从头解说X*是最大化原LP问题最优解的充要条件是同时知足①（称为原始可行条件）所以，纯真形法是在保持原始可行下，经过迭代，逐渐实现对偶可行，达到求出最优②（称为对偶可行条件）解的过程。依据对偶问题的对称性，也能够在保持对偶可行下，经过迭代，逐渐实现原始可行，以求得最优解。对偶纯真形法就是这类思想所设计的。2.对偶纯真形法的计算步骤：举例说明对偶纯真形法与纯真形法的不一样之点：①不要求模型中b≥0②先确立换出变量xL，再确立换入变量xK③minj|arj0karjarkj对偶纯真形法合用对象①maxZ=CX(C≤0)②maxZ=CXAXbAXb(t)(t1,2,,r)X（b无穷制），l(t)00X③当变量个数（拘束个数时，可先转变为其对偶问题，再用纯真形法或对偶纯真形法解之④进行敏捷度剖析时，有时会用到此法四、对偶解的经济含义和影子价钱对偶解Y*=CBB-1的经济含义设互为对偶的LP问题maxZ=CXminW=YbAXbYAC(原)0(对)0XY有Z*=CBB-1b=W*(此中B为最优基)所以Z*CBBY*1b或许说Z*=y*1b1+y*2b2+y*mbmZ**则yibi其含义是：若对原问题右端常数项向量b中的某一常数项bi增添一个单位，目标函数的最优值Z*的变化将是Yi*。换句话说，Yi*表示当bi增添一个单位时，目标函数最优值的相应增量。实质上Yi*就是第i种资源边沿价值的一种表现，也是对第i种资源的一种估价。事实上，如引例中互为对偶LP问题分别描绘生产计划问题和资源的订价问题，其数学模型分别是：maxZ=2x1+3x2minW=8y1+16y2+12y3x12x28y14y224x116(原问题)(对偶问题)2y14y334x212y1,y20,y30x1,x20对原问题用纯真形法求解所得最后表为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个单位节余被闲置，不产生任何经济效益。影子价钱的定义把某一经济结构中的某种资源，在最优决议下的边沿价值称为该资源在此经济结构中的影子价钱。影子价钱是在最优决议下对资源的一种估价，没有最优决议就没有影子价钱，所以影子价钱又称“最优计划价钱”，“展望价钱”等等。资源的影子价钱定量的反应了单位资源在最优生产方案中为总利润应供给的利润，因此，资源的影子价钱也可称为在最优方案中投入生产的时机成本。影子价钱的求法在非退化状况下：设B为LP问题的最优基，则资源的影价=Y*=CBB-1在退化状况下：当对偶问题有K个最优解，则第i种资源的影价=min{yi*(k)}即影价的第i个重量等于这kK个对偶解中第i个重量的最小值。比如，设某资源利用问题为maxZ=3x1+x2(资源1限制)最终表(资源2限制)1003XBx1x2x3x4x121110x400-1[-3]1Z60230x1212/301/3x3001/31-1/3Z60101∴资源1的影价=min{y1*(1),y1*(2)}=min{3,0}=0*(1)*(2)}=min{0,1}=0资源2的影价=min{y2,y2影子价钱的顾问作用影价>0，说明该资源已耗尽，（1）指出公司挖潜改革的门路成为短线资源。影价=0，说明该资源有节余，成为长线资源。（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中的某一个或几个发生变化时，观察能否影响以下两式的成立？对资源数目br变化的剖析当b中某个br发生改变时，将影响基变量的取值XB=B-1b。若br的变化仍知足B-1b≥0，则当前的基B仍为最优基，仅在B-1b和CBB-1b的数目上有些改变。若br的变化使B-1b中某些重量小于0，则当前的基成为非可行基，为此，可用对偶纯真形法迭代求得新的最优解。B-1b≥0给出了使最优基B保持不变时△br的同意的变化范围：由解不等式组0:B-1(b+△b)=B-1b+B-1br0可得：biairbr0(i1,2,m):0此中bi为最后表中b列的第i个重量，air为B-1中第r列的元素。例对价值系数Cj变化的剖析（1）当CN中某个Cj发生变化时，只影到非基变量xj的查验数因为j(CBB1Pj)(CjCj)jCj若j0j≤σj。，则△C这就是保持最优基不变下，△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吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应怎样调运产品，在知足各销售点需求量的前提下，使总运费为最少。均衡表（单位：吨）运价表（单位：元/吨）销地B1

B2

B3

B4

产量

B1

B2

B3

B4产地A17311310A241928A9741053销量3656解：这是一个产销均衡的运输问题，其数学模型是：设Xij表示从Ai调运产品到Bj的数目（吨），则minZ=3X+11X+3X+10X+X+9X111213142122+2X+8X+7X+4X+10X+5X232431323334x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9s.tx11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0(i=1,2,3,j=1,2,3,4)一、产量均衡的运输问题及其解法产销均衡的运输问题的数学模型及其特色特色：（1）其系数矩阵的结构松散，且每一列向量Pij=(0,1,1,0)T=ei+em+j能够证明，r(A)=m+n－1。即有m+n－1个独立方程。于是，该LP问题有且仅有m+n－1个基变量。mn（2）aibj（产销均衡条件）i1j1mn（3）因为MinZCijXij0故必有可行解和最优解。i1j1因为上述特色，若按纯真形法求解一定增添人工变量，以致计算量大大增添，故用特殊解法──表上作业法。表上作业法表上作业法实质上还是纯真形法，但详细计算和术语上有所不一样。其计算步骤方法，并经过对引例的求解过程说明之一。（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于是，查验数σ=CBP－C=(u+v)－CijB-1ijijijij又各基变量的查验数为0，故对每个基变量所在的数格的查验数有(ui+vj)－Cij=0i,jJB即有方程组ui1vj1Ci1j1ui2vj2Ci2j2共m+n个未知数s=m+n－1个方程:uisvjsCisjs明显上述方程有解，且因为含有一个自由变量，所以，可令任一未知数为0，便可求出上述方程组的解(ui1,ui2,uim,vj1,vj2,vjn)──称为位势解。如用位势法求引例初始基可行解的查验数：销地B2B3B4ui产地B1A1311③⑩-1-20A219②+1⑧-1-1A7④⑩⑤-10-12-53vj29310第一步：将运价表中的数字分别写在各格听右上角，并对基变量相应的运价加圈，同时在表中增添vj和ui列。第二步：利用圈数格分别算出ui和vj，即令

u1=0

，而后按

ui+vj=Cij

(i,j

JB)

，接踵确立

ui

，

vj

的值。于是有v3=3,v4=10,u2=-1,v

1=2,u3=-5,v

2=9第三步：按σ

ij=(u

i+vj)－Cij

(i,j

JN)算出表中各空格（即非基变量）的查验数：11=(0+2)－3=-1，σ12=(0+9)－11=-2，σ22=-1，σ24=1，σ31=-10，σ33=-12因为运输问题的目标函数是求最小化，故鉴别最优解的准则是所有的σij=CBB-1Pij－Cij0因为24=+1>0，所以当前还没有获取最优解，尚须改良（3）在调运均衡表上用闭回路法进行调整，获取新的基可行解（新的调运方案）确立换入变量：自上而上，自左向右第一个正查验数相应的非基变量（空格）为入基变量。作闭回路：以换入变量空格为出发点，用水平或垂直线向前划，当遇到某一合适数格转90后，持续行进，直至回到开端空格止。确立调整量=min{第奇数次拐角格的调运量}在闭回路长进行调整：对闭回路上每个奇数次拐角格的调运量－对闭回路上每个第偶数次（含开端格）拐角格的调运量+。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。闭回路外的各调运量不变。这样便获取新的调运方案（新基可行解）销地B1B2B3B4产量产地A1(+1)43(-1)723(-1)1(+1)4AA3639销量3656对换整后所得的新方案，再进行查验，已获取最优解（最优调运方案）；从A1调运到5吨到B3，调运2吨到B4从A2调运到3吨到B1，调运1吨到B4从A3调运到6吨到B2，调运3吨到B4总运费最小是85元（4）在进行表上作业法须注意的问题：i)在最后调运表中，如有某个空格（非基变量）的查验为0时，则表示该运输问题有多重调运方案；在确立初始方案时，若在(i,j)格填上某数字后,出现Ai处的余量=Bj处的需量，此时一定在均衡表上被划去行和列相应地点的任一空格处填上一个“0”，以知够数格=m+n－1个的需要；在用闭回路法调整时，当闭回路上第奇数次拐角数有几个相同的最小值时，调整后只好有一个空格，其他均要保存数“0”，以保证数格=m+n－1个的需要。以上ii)，iii)均出现退化解。用最小元素法所获取的初始方案能够不独一。二、产销不均衡的运输的问题及其求解方法mnmn1.数学模型：产大于销aibj产小于销aibji1j1i1j12.解法思路：mn将不均衡转变为均衡。即当aibj时，考虑在均衡表中增添一虚构列，表示i1j1mn增添一个销货点(j=n+1)如库房，其销货量为aibj，且各运价Cin+1=0；当i1j1mn时，考虑在均衡表中增添一虚构行，表示增添一个新产地，且各运价C=0。aibjm+1ji1j1而后再用产销均衡的运输问题的解法进行解之。例三、转运问题及其解法：所谓转运问题是在以下背景产生的：每个工厂生产的产品不直接运到销地，能够几个产地集中一同运。运往各销地的物质可先运给此中的几个销地，再转运给其他销地。除产、销地以外，还能够有几此中间转运站，在产地之间，销地之间或产销之间转运。凡近似上述状况下的调运物质并使总运费最小的问题统称为转运问题。求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变为扩大后的产销均衡的运输问题办理。求解“转运问题”的方法步骤：成立扩大的产销均衡运输问题单位运价表。此中1)对两地不可以直接运输的单位运价定为M（很大的正数）；mn2)对所有中转站Tj的产量和销量定为相等，设定为aibj；i1j13)对产量列的各数据可按下式计算并填入：Ai的产量=ai+,Tj产量=，Bj的产量=对销量行的各数据可按下式计算并填入：用表上作业法进行求解§2指派问题及其解法引例任务EJGR人员甲215134乙1041415丙9141613丁78119解：设Xij表示第i人从事第j项工作，且当指派第i人去达成第j项工作所以，该问题的数学模型为不然MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24+9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44X11X21X31X411X12X22X32X421项工作只指派人达成X13X23X33X43表示第j1X14X24X34X441X11X12X13X141X21X22X23X241人被指派达成一项工作表示第iX31X32X33X341X41X42X43X441Xij=0或1(i,j=1,2,3,4)诸这样类，有n项任务，恰巧有n个人可担当这些任务，但因为每人的专长技术不一样，达成任务的效率(所费时间_不一样，为使达成n项任务的总效率最高（即所需总时最少），应怎样指派（分配）人员的问题统称为指派（分配）问题。一、指派问题的数学模型及其特色数学模型：特色（1）给定一个指派问题时，一定给出效率矩阵（系数矩阵）C=(Cij)nxn,且Cij0，所以必n

n有最优解

(

MinZ

CijXij

0)。i1j1（2）指派问题是一种特别的均衡的运输问题，因为模型结构的特别性（看作每产地的产量均为1，每销地的销量均为1），故可用更加简易的匈牙利法进行求解。（3）解矩阵是指派问题的可行解，但不必定是最优解。二、指派问题的解法──匈牙利法匈牙利法的基本思想是：对同一项工作（任务）j来说，同时提升或降低每人相同的效率（常数ti），不影响其最优指派；相同，对同一个人i来说，达成各项工作的效率都提高或降低相同的效率（常数di），也不影响其最优指派，所以可获取新的效率矩阵(bij)nxn，此中bij=Cij+ti+dj（对所有的i,j）则新的目标函数为nn此中tidj为常数i1j1这说明Z与Z同时达到最小值。因此最优解相同。故指派问题有以下性质：若从效率矩阵(Cij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，获取的新效率矩阵(bij)nxn不改变原指派问题的最优解。2.匈牙利法nn三、对求最大化的指派问题，（即求MaxZCijXij）,可采纳结构新的效率矩i1j1阵(M－Cij)nxn，此中M=max{Cij}，（明显M－Cij0），将其转变为求所获取的最优解就是原问题的最优解。事实上因为nM为常数，所以，使Z获得最小的最优解就是使Z获得最大的最优解。4.以上议论的指派问题是效率矩阵的行数等于列数，即m+n的状况。当mn时，则可用增添虚设的零元数行（列）使效率矩阵变为方阵后，再用匈牙利法求解。C11,C12C1nC11C1n00当m<n时Cm1,Cm2Cmn当m>n时C21C2n00::::::000n-m行Cm1Cmn00000m-n列指派问题必有最优解，但能够不独一。§3整数线性规划问题及其解法一、整数线性规划在上一章议论的LP问题中,对决议变量只限于不可以取负值的连续型数值,即能够是正分数或正小数。但是在很多经济管理的实质问题中，决议变量只有非负整数才有实质意义。对求整数最优解的问题，称为整数规划(IntegerP