MBA运筹学实用培训讲义

1、MBA运筹学讲义运筹学是是一门应应用科学学，它广广泛应用用现代科科学技术术知识、用定量量分析的的方法，解决实实际中提提出的问问题，为为决策者者选择最最优决策策提供定定量依据据。运筹筹学的核核心思想想是建立立在优化化的基础础上。例如，在在线性规规划中体体现为两两方面：（1）对对于给定定的一项项任务，如何统统筹安排排，使以以最少的的资源消消耗去完完成？（2）在在给定的的一定数数量的资资源条件件下，如如何合理理安排，使完成成的任务务最多？运筹学解解决问题题的主要要方法是是用数学学模型描描述现实实中提出出的决策策问题，用数学学方法对对模型进进行求解解，并对对解的结结果进行行分析，为决策策提供科科学依据

2、据。随着计算算机及计计算技术术的迅猛猛发展，目前对对运筹学学的数学学模型的的求解已已有相应应的软件件。因此此，在实实际求解解计算时时常可借借助于软软件在计计算机上上进行，这样可可以节省省大量的的人力和和时间。第一部分分线性规规划内容容框架LP问题题基本概念念数学模模型可行行解、最最优解实际问题题LP问题题解的概概念基本本解、基基可行解解提出基本本最优解解基本方法法图解法原始单纯纯形法单纯形法法大M法人工变量量法对偶单纯纯形法两两阶段法法对偶理论论进一步讨讨论灵敏度分分析参数规规划*在经济管管理领域域内应用用运输问题题（转运运问题）特殊的LLP问题题整数规规划多目标LLP问题题*第一部分分线性规

3、规划（LLineear Proograammiing）及其应应用第一章 LPP问题的的数学模模型与求求解1 LP问问题及其其数学模模型（一）引引例1（生产产计划的的问题） 某工厂厂在计划划期内要要安排生生产、的两种种产品，已知生生产单位位产品所所需的设设备台时时，A、B两种原原材料的的消耗以以及每件件产品可可获的利利润如下下表所示示。问应应如何安安排计划划使该工工厂获利利最多？资源限量量设备128(台时时)原材料AA4016(kkg)原材料BB0412(kkg)单位产品品利润（元）23该问题可可用一句句话来描描述，即即在有限限资源的的条件下下，求使使利润最最大的生生产计划划方案。解：设xx1,

4、x2分别表表示在计计划期内内生产产产品、的产量量。由于于资源的的限制，所以有有：机器设备备的限制制条件：x1+2xx28原材料AA的限制制条件： 44x116（称为为资源约约束条件件）原材料BB的限制制条件： 44x212同时，产产品、的产量量不能是是负数，所以有有x100，x20（称为为变量的的非负约约束）显然，在在满足上上述约束束条件下下的变量量取值，均能构构成可行行方案，且有许许许多多多。而工工厂的目目标是在在不超过过所有资资源限量量的条件件下，如如何确定定产量xx1，x2以得到到最大的的利润，即使目目标函数数Z=2xx1+3xx2的值达达到最大大。综上所述述，该生生产计划划安排问问题可

5、用用以下数数学模型型表示：maxzz=2xx1+3xx2引例2. （营营养配餐餐问题）假定一个个成年人人每天需需要从食食物中获获取30000卡卡路里热热量，555克蛋蛋白质和和8000毫克钙钙。如果果市场上上只有四四种食品品可供选选择，它它们每千千克所含含热量和和营养成成份以及及市场价价格如下下表所示示。问如如何选择择才能满满足营养养的前提提下使购购买食品品的费用用最小？序号食品名称称热量(卡卡路里)蛋白质(克)钙(mgg)价格(元元)1猪肉1000050400102鸡蛋8006020063大米9002030034白菜200105002解:设xxj(j=1,22,3,4)为为第j种食品品每天的

6、的购买量量，则配配餐问题题数学模模型为minzz=100 x16x23x32x4（二）LLP问题题的模型型上述两例例所提出出的问题题，可归归结为在在变量满满足线性性约束条条件下，求使线线性目标标函数值值最大或或最小的的问题。它们具具有共同同的特征征。（1）每每个问题题都可用用一组决决策变量量(x1,x2,xn)表示某某一方案案，其具具体的值值就代表表一个具具体方案案。通常常可根据据决策变变量所代代表的事事物特点点，可对对变量的的取值加加以约束束，如非非负约束束。（2）存存在一组组线性等等式或不不等式的的约束条条件。（3）都都有一个个用决策策变量的的线性函函数作为为决策目目标（即即目标函函数），

7、按问题题的不同同，要求求目标函函数实现现最大化化或最小小化。满足以上上三个条条件的数数学模型型称为LLP的数数学模型型，其一一般形式式为：max(或minn)z=c1x1+c2x2+cnxn(1.1)(1.3)(1.2)或紧缩形形式mmax(或minn)z=(1.4)或矩阵形形式mmax(或minn)z=cx(1.5)或向量形形式：mmax(或minn)z=cx(1.6)其中C=(c11,c2,cn)，称为为价值系系数向量量；称为技术术系数矩矩阵（并并称消耗耗系数矩矩阵） =(p1,p2,pn)称资源限限制向量量X=(x11,x2,xn)T称为决决策变量量向量。（三）LLP问题题的标准准型1.

8、为了了讨论LLP问题题解的概概念和解解的性质质以及对对LP问题题解法方方便，必必须把LLP问题题的一般般形式化化为统一一的标准准型：maxz=cxmmaxzz=； 或maxxz=ccx或标准型的的特点：目标函函数是最最大化类类型约束条条件均由由等式组组成决策变变量均为为非负bi(i=11,2,n)2.化一一般形式式为标准准型minnzmaax(-z)=-cxx“”左左边+松驰变变量；“”左边“松驰变变量”变量xxj0-xj0变量xj无限制制令xj=xjxjbi0等式式两边同同乘以(-1)。3.模型型隐含的的假设比例性性假定：决策变变量变化化的改变变量与引引起目标标函数的的改变量量成比例例；决策

9、策变量变变化的改改变量与与引起约约束方程程左端值值的改变变量成比比例。此此假定意意味着每每种经营营活动对对目标函函数的贡贡献是一一个常数数，对资资源的消消耗也是是一个常常数。可加性性假定：每个决决策变量量对目标标函数和和约束方方程的影影响是独独立于其其它变量量的。连续性性假定：决策变变量应取取连续值值。确定性性假定：所有的的参数(aijj,bi,cj)均为确确定，所所以LPP问题是是确定型型问题，不含随随机因素素。以上4个个假定均均由于线线性函数数所致。在现实实生活中中，完全全满足这这4个假定定的例子子并不多多见，因因此在使使用LPP时必须须注意问问题在什什么程度度上满足足这些假假定。若若不满

10、足足的程度度较大时时，应考考虑使用用其它模模型和方方法。如如非线性性规划，整数规规划或不不确定型型分析方方法。对LP标标准型，我们还还假定rr(A)=mn。（四）LLP问题题的解的的概念设LP问问题mmaxzz=(1.7)(1.8)(1.99) 1.从从代数的的角度看看：可行解和和最优解解满足约约束条件件(1.8)和(1.9)的解X=(x11,x2,xn)T称为可可行解。所有可可行解构构成可行行解集，即可行行域。而而使目标标函数达达到最大大值的可可行解称称为最优优解，对对应的目目标函数数值称为为最优值值。求解LPP问题就就是求其其最优解解和最优优值，但但从代数数的角度度去求是是困难的的。2.从

11、LLP角度度看：基：设AA为mxnn矩阵，r(AA)=mm，B是A中的mxxm阶非非奇异子子矩阵（即|BB|0），则则称B是LP问题题的一个个基。若B是LLP问题题的一个个基，则则B由m个线性性独立的的列向量量组成，即B=(Prr1,PPr2,Prmm)，其中中Prj=(a1rrj,aa2rjj,amrrj)T，(j=1,22,m)称为基基向理。与其向向量Prj相对对应的变变量xrj称为为基变量量，其它它变量称称为非基基变量。显然，对应于于每个基基总有mm个基变变量，nnm个非基基变量。基本解与与基可行行解设B是LP问题题的一个个基，令令其nm个非基基变量均均为零，所得方方程的解解称为该该LP

12、问题题的一个个基本解解。显然然，基BB与基本本解是一一一对应应的，基基本解的的个数Cmn。在基基本解中中，称满满足非负负条件的的基本解解为基可可行解，对应的的基称为为可行基基。退化解如如果基解解中非零零分量的的个数小小于m，则称称此基本本解为退退化的，否则是是非退化化的。最优基如如果对应应于基BB的基可可行解是是LP问题题的最优优解，则则称B为LP问题题的最优优基，相相应的解解又称基基本最优优解。3.LPP问题解解之间的的关系如如图所示示基本解可行解基可行解（五）两两个变量量LP问问题的图图解法 1.LLP问题题解的几几何表示示。以引引例为例例说明maxzz=2xx1+3xx2按以下顺顺序进行

13、行：解：（11）画出出直角坐坐标系；（2）依依次做每每条约束束线，标标出可行行域的方方向，并并找出它它们共同同的可行域；AQ1Q2x2（3）任任取一目目标函数数值作一一条目标标函数线线（称等等值线），根据据目标函函数（最最大或最最小）类类型，平平移该直直线即将将离开可可行域上上，则与与目标函函数线接接触的最最终点即即表示最最优解。3BQ4Q3201x10 1 2 3 4图1其中，将将目标函函数Z=2x11+3xx2改写为为，因此此，它可可以表示示为：以以z为参数数，以为为斜率的的一族平平行线。位于同同一条直直线上的的点具有有相同的的值。解的几种种情况：（1）此此例有唯唯一解QQ2，即x1=4,

14、x2=2,z=114（2）有有无穷多多最优解解（多重重解），若将目目标函数数改为zz=2xx1+4xx2则线段段Q2，Q3上的点点均为最最优解。（3）无无界解x20 x1求maxx无界但求miin有唯唯一解（4）无无可行解解x2x10可行域与与最优解解间的关关系：可行域最最优解空集无最最优解（无可行行解）有界集唯唯一最优优解多重解无界集无无有限最最优解（无界解解）结论：（1）LP问题题的可行行域是凸凸集（凸凸多边形形，凸多多面体，）；（2）LLP问题题最优解解若存在在，则必必可在可可行域的的顶点上上得到；（3）LLP问题题的可行行域的顶顶点个数数是有限限的；（4）若若LP问题题有两个个最优解解

15、，则其其连线上上的点都都是最优优解。因因此，求求解LPP问题可可转化为为如何在在可行域域的顶点点上求出出使目标标函数值值达到最最优的点点的问题题。 2.基基可行解解的几何何意义对例1 LPP问题标标准化为为maxxZ=22x1+3xx2可求得所所有的基基本解：x(1)=(00,0,8,116,112)TT(0点),xx(2)=(44,0,4,00,122)T(Q1点)x(3)=(44,2,0,00,4)T(Q2点),xx(4)=(22,3,0,88,0)T(Q3点)x(5)=(00,3,2,116,00)T(Q4点),xx(6)=(44,3,-2,0,00)T(C点)x(7)=(88,0,0,

16、-16,12)T(A点),xx(8)=(00,4,0,116,-4)TT(B点)但A、BB、C三点是是非可行行域上的的点，即即非可行行解。因因此，xx(1)，x(2)，x(3)，x(4)，x(5)才是基基可行解解，它们们与可行行域的顶顶点相对对应。于于是还有有结论：（5）对于于标准型型的LPP问题，X是基可可行解的的充要条条件是XX为可行行域的顶顶点。（6）LLP问题题可行域域顶点的的个数=基可行行解的个个数基的个个数Cmn 3.图图解法只只适用于于两个变变量（最最多含三三个变量量）的LLP问题题。 4.求求解LPP问题方方法的思思考：完全枚枚举法，对m、n较大时时，Cmn是一个个很大的的数，

17、几几乎不可可能；从可行行域的一一个顶点点（基可可行解）迭代到到另一个个顶点（基可行行解）。2 单纯形形法与计计算机求求解 1.解解LP问题题单纯形形法的基基本思路路：求出一个个初始基基可行解解y停判别此基基可行解解是否最优解N求出使目目标函数数值得到到改善的基基可行解解 2.单单纯形法法的计算算步骤（表格形形式）（1）建建立初始始单纯形形表，假假定B=I，bb0设maxxZ=cc1x1+c2x2+cnxn将目标函函数改写写为：-Z+cc1x1+c2x2+cnxn=0把上述方方程组和和目标函函数方程程构成nn+1个个变量，m+11个方程程的方程程组，并并写成增增广矩阵阵的形式式：-Zxx1x2x

18、mxm+11xn01001m+11n100102m+12n20001mm+1mnm-1cc1c2cmcm+11cn0以非基变变量表示示基变量量形式代代入Z中的基基变量,有令于是因此，上上述的增增广矩阵阵就可写写成：Zx11x2xmxm+11xn01001m+11n100102m+12n20001mm+1mnm1000cn再令则上述增增广矩阵阵可写成成下面表表格形式式：即初初始单纯纯形表TT（B）CjC1Cmcm+11cniCBxBx1xmxm+11xnC1x11100a1m+1a1nC2x22000a2m+1a2n：Cmxmm011amm+1amnZZ0000m+1nj检验数数行上述初始始单纯

19、形形表可确确定初始始可行基基和初始始基可行行解：B=(PP1,P2,Pm)=II, x=(b1,b2,bm, 000)T从初始单单纯形表表建立的的过程可可以看到到以下事事实：（1）凡凡LP模型型中约束束条件为为“”型，在在化为标标准型后后必有BB=I，如果bb0，则模模型中约约束方程程的各数数据不改改变符号号照抄在在表中相相应的位位置。目目标函数数非基变变量的系系数则以以相反数数填入检检验数行行各相应应位置。（2）在在单纯形形表中，凡基变变量所在在的列向向量必是是单位列列向量，其相应应的检验验数均为为零。（3）更好表现现一般规规律的在在矩阵形形式的单单纯形表表中设MaxxX=CCXMaxxZ=

20、CCX+00XL其标准型型为将系数矩矩阵(AA,I)分划为为(B,N,II)，其其中B为可行行基，对对应于基基变量向向量XB,N对应应于XN，I对应于于XL,(XXN,XL)为非基基变量向向量。于于是(XX,L)T=(XXB,XN,XL)T,(CC,0)=(CCB,CN,0)。因此此，矩阵阵形式的的LP模型型改写为为：用非基变变量向量量表示基基变量向向量，有有 XBB=B-11bB-1NXNB-1XL代入目标标函数中中有Z =CBB(B-11bB1NXNB-1XL)+CCNXN+0XXL =CBBB-1bCBB-1NXXNCBB-1XL)+CCNXN =CBBB-1b(CBB-1NCN)XNC

21、BB-1XL将写成对应应于基BB的矩阵阵形式的的单纯形形表T（B）：CCBCNCLXBXNXLXB1B-1NNB-1ZCBB-1b0CBB-1NCNCBB-1例如将例例1 化成标标准型后后如下表表T（B）：Cj23000iCBXBx1x2x3x4x50 x38121000 x416400100 x51204001-Z0-2-3000j初始可行行基B=(P33,P4,P5)=II, XX=(00,0,8,116,112)TT（2）判判别最优优解 1在T(BB)中，若所有有的检验验数j0 (j=11,2,n)则B为最最优基，相应的的基可行行解为最最优解，停止计计算。 2在T(BB)中，若有k0 (

22、1kkn)，且且xk的系数数列向量量Pk0，则该该问题无无界，停停止计算算。否则则转入（3）（3）换换基迭代代（基变变换） 1先确确定入基基变量XXk: k=mminj| j0（2）按按规则计计算，若若存在两两个相同同以上最最小比值值时，选选取下标标最小的的基变量量为换出出变量xxL，即值得庆幸幸的是出出现基循循环是罕罕见的。3 对偶理理论与灵灵敏度分分析一、LPP的对偶偶问题1.引例例前已述述引例11是一个个在有限限资源的的条件下下，求使使利润最最大的生生产计划划安排问问题，其其数学模模型为：（设备）（原材料A）（原材料B）maxZZ=2xx1+3xx2现从另一一角度考考虑此问问题。假假设有

23、客客户提出出要求，租赁工工厂的设设备台时时和购买买工厂的的原材料料A、B，为其其加工生生产别的的产品，由客户户支付台台时费和和材料费费，此时时工厂应应考虑如如何为每每种资源源的定价价问题？解：设yy1,y2,y3分别表表示出租租单位设设备台时时的租金金和出售售单位原原材料AA、B的价格格（含附附加值）工厂决策策者考虑虑：（1）出出租设备备和出售售原材料料应不少少于自己己生产产产品的获获利，否否则不如如自己生生产为好好。因此此有工厂的总总收入为为W=88y1+166y2+122y3（2）价价格应尽尽量低，否则没没有竞争争力（此此价格可可成为与与客户谈谈判的底底价）租赁者考考虑：希希望价格格越低越

24、越好，否否则另找找他人。于是，能能够使双双方共同同接受的的是MinWW=8yy1+166y2+122y3上述两个个LP问题题的数学学模型是是在同一一企业的的资源状状况和生生产条件件下产生生的，且且是同一一个问题题从不同同角度考考虑所产产生的，因此两两者密切切相关。称这两两个LPP问题是是互为对对偶的两两个LPP问题。其中一一个是另另一个问问题的对对偶问题题。2.从矩矩阵形式式讨论互互为对偶偶LP问题题由例1 有maxxZ=ccx由矩阵形形式的单单纯形表表中可知知：检验数的的表达式式为：CBB-1NCN和CBB-1当表示LPP问题已已得到最最优解令Y=CCBB-1,且有Y0由于基变变量XB的检验

25、验数为00，可改改写成CCBB-1BCB=0因此，包包括基变变量在内内的所有有检验数数可写成成(CBBB-1BCB, CCBB-1NCN)=(CBB-1AC)= YAAC0即YACC又对Y=CCBB-1，两两边右乘乘b，有Yb=CCBB-1b=Z由于Y无无上界，所以只只有最小小值，因因此有MinWW=Ybb它是原问问题maaxZ=CX| AXXb,XX0的对对偶问题题于是，对对称形式式下两个个互为对对偶LPP问题的的数学模模型为：MaxZZ=CXXMinnW=YYb与任何一个个LP问题题均有一一个对偶偶LP问题题与之匹匹配。对偶理论论就是研研究LPP问题及及其对偶偶问题的的理论，它是LLP理论

26、论中的重重要内容容之一。二、对偶偶理论 1.原原问题与与对偶问问题的关关系如下下表所示示原始对偶偶表原问题MMax（对偶问问题）对偶问题题Minn（原问问题）约束条件件数=mm变量个数数=m第i个约约束条件件为“”第i个约约束条件件为“”第i个约约束条件件为“=”第i个变变量0第i个变变量0第i个变变量无限限制变量个数数=m约束条件件个数=n第i个变变量0第i个变变量0第i个变变量无限限制第i个约约束条件件为“”第i个约约束条件件为“”第i个约约束条件件为“=”第i个约约束条件件的右端端项目标函第第i个变量量的系数数目标函数数第i个变量量的系数数第i个约约束条件件的右端端顶2.对偶偶问题的的基

27、本性性质MaxZZ=CXXMinnW=YYb设（1）（对称性性）对偶偶问题的的对偶是是原问题题；（2）（弱对偶偶性）若若是原问问题的可可行解，是对偶偶问题的的可行解解；则；（3）（无界性性）若原原问题（对偶问问题）为为无界解解，则其其对偶问问题（原原问题）无可行行解；（4）（最优性性准则），若、分别是是互为对对偶问题题的可行行解，且且C=b，则、分别是是它们的的最优解解；（5）（对偶定定理）若若互为对对偶问题题之一有有最优解解，则另另一问题题必有最最优解，且它们们的目标标函数值值相等。从上述性性质中，可看到到原问题题与对偶偶问题的的解必然然是下列列三种情情况之一一：原问题题与对偶偶问题都都有最

28、优优解，且且CX=Yb；一个问问题具有有无界解解，则它它的对偶偶问题无无可行解解；两个问问题均无无可行解解。（6）（互补松松驰性），若XX*、Y*分别是是原问题题的对偶偶问题的的可行解解，则XX*、Y*是最优优解的充充要条件件是：YY*XS=0,YSX*=0(其中XS,YS分别是是原问题题和对偶偶问题的的松驰变变量向量量)。或，X*、Y*分别是是原问题题和对偶偶问题最最优解的的充要条条件是：若y*i0，则则aijX*j=bi若aiijX*j0，则则aijy*i=cj若aiijy*icj，则X*j=0三、对偶偶单纯形形法 1.单单纯形法法的重新新解释 （称为原始可行条件） （称为对偶可行条件）X

29、*是最最大化原原LP问题题最优解解的充要要条件是是同时满满足因此，单单纯形法法是在保保持原始始可行下下，经过过迭代，逐步实实现对偶偶可行，达到求求出最优优解的过过程。根据对偶偶问题的的对称性性，也可可以在保保持对偶偶可行下下，经过过迭代，逐步实实现原始始可行，以求得得最优解解。对偶偶单纯形形法就是是这种思思想所设设计的。2.对偶偶单纯形形法的计计算步骤骤：举例说明明 3.对对偶单纯纯形法与与单纯形形法的不不同之点点：不要求求模型中中b0先确定定换出变变量xL，再确确定换入入变量xxK 4.对对偶单纯纯形法适适用对象象maxxZ=CCX(CC0)maxxZ=CCX（b无限限制），当变量量个数（约

30、束个个数时，可先转转化为其其对偶问问题，再再用单纯纯形法或或对偶单单纯形法法解之进行灵灵敏度分分析时，有时会会用到此此法四、对偶偶解的经经济含义义和影子子价格 1.对对偶解YY*=CCBB-1的经经济含义义设互为对对偶的LLP问题题maaxZ=CXminnW=YYb (原)(对)有 ZZ*=CCBB-1b=W* (其中中B为最优优基)因此或者说ZZ*=yy*1b1+y*2b2+y*mbm则其含义是是：若对对原问题题右端常常数项向向量b中的某某一常数数项bi增加一一个单位位，目标标函数的的最优值值Z*的变变化将是是Yi*。换句句话说，Yi*表示当当bi增加一一个单位位时，目目标函数数最优值值的相

31、应应增量。实质上上Yi*就是第第i种资源源边际价价值的一一种表现现，也是是对第ii种资源源的一种种估价。事实上，如引例例中互为为对偶LLP问题题分别描描述生产产计划问问题和资资源的定定价问题题，其数数学模型型分别是是：maxZZ=2xx1+3xx2minnW=88y1+166y2+122y3(原问题题)(对偶问问题)对原问题题用单纯纯形法求求解所得得最终表表为C23000CBXBbx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/880Z14001.50.12250由此，它它们的最最优解分分别是XX*=(4,22)T和Y=(1.55,0.1255,0)

32、 Z*=W*=14=8Y11*+116Y22*122Y3*其中Y11*=11.5表表示单独独对设备备台时增增加1个单位位，可使使Z值增加加1.55个单位位的利润润；Y2*=00.1225表示示单独对对原材料料A增加1个单位位，可使使Z值增加加0.1125个个单位的的利润；而Y3*=00表示单单独对原原材料BB增加一一个单位位，却不不使Z值增加加。这是是因为从从最终表表中可看看出，在在最优方方案中，松驰变变量x5=4，即即表示在在最优生生产方案案中，原原材料BB尚有4个单位位剩余被被闲置，不产生生任何经经济效益益。 2.影影子价格格的定义义把某一经经济结构构中的某某种资源源，在最最优决策策下的边

33、边际价值值称为该该资源在在此经济济结构中中的影子子价格。影子价格格是在最最优决策策下对资资源的一一种估价价，没有有最优决决策就没没有影子子价格，所以影影子价格格又称“最优计计划价格格”，“预测价价格”等等。资源的影影子价格格定量的的反映了了单位资资源在最最优生产产方案中中为总收收益应提提供的收收益，因因此，资资源的影影子价格格也可称称为在最最优方案案中投入入生产的的机会成成本。3.影子子价格的的求法 (1)在非退退化情况况下：设设B为LP问题题的最优优基，则则资源的影影价=YY*=CCBB-1 (2)在退化化情况下下：当对偶问问题有KK个最优优解，则则第i种资源源的影价价=即影价价的第ii个分

34、量量等于这这K个对偶偶解中第第i个分量量的最小小值。例如，设设某资源源利用问问题为(资源1限制)(资源2限制) maaxZ=3x11+x2最终表3100XBx1x2x3x4x121110 x400-1-31Z60230 x1212/301/3x3001/31-1/33Z60101资源11的影价价 =mminy1*(11),yy1*(22) =mmin3,00=00资源2的的影价=minny22*(11),yy2*(22)=minn0,1=0影价0，说明该资源已耗尽， 成为短线资源。影价=0，说明该资源有剩余， 成为长线资源。 4.影影子价格格的参谋谋作用（1）指指出企业业挖潜革革新的途途径（2

35、）对对市场资资源的最最优配置置起着推推进作用用（3）可可为企业业决策者者提供调调整最优优生产方方案的信信息 CCBB-1PjCj0说明明第j种产品品不应投投产尤其对新新产品是是否应投投产，可可按以上上两式考考虑。（4）可可以预测测产品的的价格（5）可可作为同同类企业业经济效效益评估估指标之之一。五、灵敏敏度分析析面对市场场变化，灵敏度度分析的的任务是是须解决决以下两两类问题题：（1）当当系数AA、b、c中的某某个发生生变化时时，目前前的最优优基是否否仍最优优（即目目前的最最优生产产方案是是否要变变化）？（2）为为保持目目前最优优基仍是是最优基基，参数数A、b、c允许变变化范围围是什么么？灵敏度

36、分分析的方方法是在在目前最最优基BB下进行行的。即即当参数数A、b、c中的某某一个或或几个发发生变化化时，考考察是否否影响以以下两式式的成立立？ 1.对对资源数数量br变化的的分析当b中某某个br发生改改变时，将影响响基变量量的取值值XB=B-11b。若br的变化化仍满足足B-1b0，则目目前的基基B仍为最最优基，仅在BB-1b和CBB-1b的数量量上有些些改变。若br的变化化使B-1b中某些些分量小小于0，则目目前的基基成为非非可行基基，为此此，可用用对偶单单纯形法法迭代求求得新的的最优解解。B-1bb0给出了了使最优优基B保持不不变时br的允许许的变化化范围：由解不等等式组 B-1(bb+

37、b)=B-11b+BB-1可得得：其中为最最终表中中列的第第i个分量量，为B-1中第第r列的元元素。例 2.对对价值系系数Cj变化的的分析（1）当当CN中某个个Cj发生变变化时，只影到到非基变变量xj的检验验数由于若，则Cjj。这就是保保持最优优基不变变下，Cj的允许许变化范范围。否否则，用用单纯形形法继续续迭代，求得新新的最优优解。（2）当当CB中某个个Cr发生变变化时，则会影响响到所有有非基变变量的检检验数N=CBB-1NCN。解不等式式组=(CB+CB)B-11NCN=(CCBB-1NCN)+CBB-1N0即(CCBB-1NCN)+(0,Cr,0)B-11N0得到使最最优解不不变Cr的允

38、许许变化范范围；例（3）对对增加新新产品的的分析设革企业业在计划划期内，拟议生生产新产产品Xn+11，并已已知新产产品的单单位利润润为Cn+11，消耗耗系数向向量为PPn+11=(aa1,nn+1,a2,n+11,am,nn+1)T，此时时应如何何分析才才能确定定该新产产品理澡澡投产？增加新产产品应在在不影响响企业目目前计划划期内最最优生产产的前提提下进行行。因此此可从现现行的最最估基BB出发考考虑：若n+1=CCBB-1Pn+11Cn+110，则则不应投投入。即新产品品的机会会成本小小于目前前的市场场价格时时，应投投产否则则不应投投产。（4）对对增加新新约束条条件的分分析在企业生生产过程程中

39、，经经常有新新情况发发生，造造成原本本不紧缺缺的某种种资源变变成为紧紧缺资源源，对生生产计划划造成影影响，如如水、电电和资源源的供应应不足等等，对生生产过程程提出了了新约束束等。对增加新新约束条条件的分分析方法法步骤是是：第一步：将目前前的最优优解代入入新增加加的约束束，若能能满足约约束条件件，则说说明新增增约束对对目前的的最优解解（即最最优生产产方案）不构成成影响（称此约约束为不不起作用用约束），可暂暂时不考考虑新增增约束条条件。否否则转下下一步；第二步：把新增增约束添添加到原原问题最最终表中中，并作作初等行行变换，构成对对偶可行行的单纯纯形表，并用对对偶单纯纯形法迭迭代，求求出新的的最优解

40、解。例：（5）技技术系数数aij变化化的分析析第一种情情况（当当jJN）：方方法与增增加一个个新产品品的分析析相同。第二种情情况（当当jJB）：由由于B中元素素的改变变影响到到B-1的变变化，因因此也影影响到TT(B)。目前前的基BB对应的的解有可可能既不不是原始始可行，也不是是对偶可可行。于于是不如如重新求求解。第二章特特殊LPP问题及及其解法法所谓特殊殊LP问题题是指LLP模型型的系数数矩阵具具有特殊殊的结构构，有可可能找到到比单纯纯形法更更为简便便的求解解方法，从而节节省人力力和物力力。1 运输问问题及其其解法引例：某公司经经销甲产产品，它它下设三三个加工工厂，每每日的产产量分别别为：A

41、A1-7吨，A2-4吨，A3-9吨。该公司司把这些些产品分分别运往往四个销销售点，各销售售每日销销量为：B1-3吨，B2-6吨，B3-5吨，B4-6吨。已知从从各工厂厂到各销销售点的的单位产产品的运运价为下下表所示示。问该该公司应应如何调调运产品品，在满满足各销销售点需需求量的的前提下下，使总总运费为为最少。平衡表（单位：吨）运运价表（单位：元/吨）销地产地B1B2B3B4产量B1B2B3B4A17311310A241928A3974105销量3656解：这是是一个产产销平衡衡的运输输问题，其数学学模型是是：设Xijj表示从从Ai调运产产品到BBj的数量量（吨），则minZZ=3XX11+11

42、1X112+33X133+100X144+X211+9XX22 +22X233+8XX24+77X311+4XX32+110X333+55X344x11+x122+x133+x144=7x21+x222+x233+x244=4x31+x322+x333+x344=9s.tx11+x211+x311=3x12+x222+x322=6x13+x233+x333=5x14+x244+x344=6xij0 (i=1,22,3, j=11,2,3,44)一、产量量平衡的的运输问问题及其其解法 1.产产销平衡衡的运输输问题的的数学模模型及其其特点特点：（1）其系系数矩阵阵的结构构疏松，且每一一列向量量Pi

43、ij=(0,1,1,0)T=ei+em+j可以证明明，r(A)=m+nn1。即有有m+nn1个独立立方程。于是，该该LP问题题有且仅仅有m+n1个基变变量。（2）（产销平平衡条件件）（3）因因为故必必有可行行解和最最优解。由于上述述特点，若按单单纯形法法求解必必须增加加人工变变量，致致使计算算量大大大增加，故用特特殊解法法表上上作业法法。2.表上上作业法法表上作业业法实质质上还是是单纯形形法，但但具体计计算和术术语上有有所不同同。其计计算步骤骤方法，并通过过对引例例的求解解过程说说明之一一。（1）用用最小元元素法确确定初始始方案（即初始始基可行行解）切记在产产销平衡衡表上必必须且只只能填写写m

44、+nn1个数字字格（2）用用位势法法求出空空格的检检验数并并进行最最优解的的判别设u1,u2,um; vv1,v2,vn是对应应运输问问题m+n个约约束条件件的对偶偶变量，B为含有有人工变变量的初初始可行行基，由由LP问题题的对偶偶理论知知CBB-1=(u1,u2,um; vv1,v2,vn)而每个决决策变量量Xij相应应的系数数向量PPij=eei+em+j，所所以CBB-1Pij=uui+vj于是，检检验数ij=CCBB-1PijCij =(uui+vj)Cij又各基变变量的检检验数为为0，故对对每个基基变量所所在的数数格的检检验数有有 (uii+vj)Cij =0 ii,jJJB即有方程

45、程组共m+nn个未知知数 s=m+nn1个方程程显然上述述方程有有解，且且由于含含有一个个自由变变量，因因此，可可令任一一未知数数为0，就可可求出上上述方程程组的解解(ui11,ui22,uim,vvj1,vvj2,vjn)称为为位势解解。如用位势势法求引引例初始始基可行行解的检检验数：销地产地B1B2B3B4uiA1-13-2110A21-19+1-1A3-107-12-5vj29310第一步：将运价价表中的的数字分分别写在在各格听听右上角角，并对对基变量量相应的的运价加加圈，同同时在表表中增加加vj和ui列。第二步：利用圈圈数格分分别算出出ui和vj，即令u1=0，然然后按uui+vj=C

46、ijj (i,jJB)，相继继确定uui，vj的值。于是有有v3=3,v4=100,u22=-11,v11=2,u3=-55,v22=9第三步：按ij= (uii+vj)Cij (ii,jJJN)算出表表中各空空格（即即非基变变量）的的检验数数：11=(0+2)3=-1，12=(0+99)11=-2，22=-1，24=11，31=-10，33=-12由于运输输问题的的目标函函数是求求最小化化，故判判别最优优解的准准则是所所有的ij=CCBB-1PijCij0因为244=+100，所以以目前尚尚未得到到最优解解，尚须须改进（3）在在调运平平衡表上上用闭回回路法进进行调整整，得到到新的基基可行解解

47、（新的的调运方方案） i) 确定换换入变量量：自上上而上，自左向向右第一一个正检检验数相相应的非非基变量量（空格格）为入入基变量量。 ii) 作闭闭回路：以换入入变量空空格为出出发点，用水平平或垂直直线向前前划，当当碰到某某一恰当当数格转转90后，继续前前进，直直至回到到起始空空格止。 iiii) 确确定调整整量=mmin第奇数数次拐角角格的调调运量 iv) 在闭闭回路上上进行调调整：对对闭回路路上每个个奇数次次拐角格格的调运运量对对闭回路路上每个个第偶数数次（含含起始格格）拐角角格的调调运量+。调整整后，将将闭回路路中为00的一个个数格作作为空格格（即出出基变量量）。闭回路外外的各调调运量不

48、不变。这这样便得得到新的的调运方方案（新新基可行行解）销地产地B1B2B3B4产量A1(+1)43(-11)7A23(-1)1(+1)4A3639销量3656对调整后后所得的的新方案案，再进进行检验验，已得得到最优优解（最最优调运运方案）；从A1调调运到55吨到B3，调运运2吨到B4从A2调调运到33吨到B1，调运运1吨到B4从A3调调运到66吨到B2，调运运3吨到B4总运费最最小是885元（4）在在进行表表上作业业法须注注意的问问题： i) 在最终终调运表表中，若若有某个个空格（非基变变量）的的检验为为0时，则则表明该该运输问问题有多多重调运运方案； ii) 在确确定初始始方案时时，若在在(

49、i,j)格格填上某某数字后后,出现Ai处的余余量=BBj处的需需量，此此时必须须在平衡衡表上被被划去行行和列相相应位置置的任一一空格处处填上一一个“0”，以满满足数格格=m+n1个的需需要； iiii) 在在用闭回回路法调调整时，当闭回回路上第第奇数次次拐角数数有几个个相同的的最小值值时，调调整后只只能有一一个空格格，其余余均要保保留数“0”，以保保证数格格=m+n1个的需需要。以上iii)，iiii)均出出现退化化解。iv) 用最小小元素法法所得到到的初始始方案可可以不唯唯一。二、产销销不平衡衡的运输输的问题题及其求求解方法法 1.数数学模型型：产大大于销产产小于销销 2.解解法思路路：将不

50、平衡衡转化为为平衡。即当时时，考虑虑在平衡衡表中增增加一虚虚拟列，表示增增加一个个销货点点(j=n+11)如仓仓库，其其销货量量为，且且各运价价Cinn+1=0；当当时，考考虑在平平衡表中中增加一一虚拟行行，表示示增加一一个新产产地，且且各运价价Cm+11j=00。然后后再用产产销平衡衡的运输输问题的的解法进进行解之之。例三、转运运问题及及其解法法： 1.所所谓转运运问题是是在以下下背景产产生的： (1)每个工工厂生产产的产品品不直接接运到销销地，可可以几个个产地集集中一起起运。 (2)运往各各销地的的物资可可先运给给其中的的几个销销地，再再转运给给其它销销地。 (3)除产、销地之之外，还还可

51、以有有几个中中间转运运站，在在产地之之间，销销地之间间或产销销之间转转运。凡类似上上述情况况下的调调运物资资并使总总运费最最小的问问题统称称为转运运问题。2.求解解“转运问问题”的思路路是把问问题中所所有的产产地、中中转站和和销地都都既看作作产地，又都看看作销地地，把“转运问问题”变成扩扩大后的的产销平平衡的运运输问题题处理。 3.求求解“转运问问题”的方法法步骤： (1)建立扩扩大的产产销平衡衡运输问问题单位位运价表表。其中中 1)对对两地不不能直接接运输的的单位运运价定为为M（很大大的正数数）； 2)对对所有中中转站TTj的产量量和销量量定为相相等，设设定为； 3)对对产量列列的各数数据可

52、按按下式计计算并填填入： Ai的产量量=ai+,Tj产量=，Bj的产量量= 4)对对销量行行的各数数据可按按下式计计算并填填入： Aj的产量量=,Tj销量=，Bj的销量量=+bj (2)用表上上作业法法进行求求解2 指派问问题及其其解法引例任务人员EJGR甲215134乙1041415丙9141613丁78119当指派第i人去完成第j项工作否则解：设XXij表示示第i人从事事第j项工作作，且因此，该该问题的的数学模模型为MinZZ=2XX11+115X112+113X113+44X144+100X211+4XX22+114X223+115X224 +9X331+114X332+116X333+

53、113X334+77X411+8XX42+111X443+99X444表示第jj项工作作只指派派人完成成表示第ii人被指指派完成成一项工工作Xij=0或1(ii,j=1,22,3,4)诸如此类类，有nn项任务务，恰好好有n个人可可承担这这些任务务，但由由于每人人的专长长技术不不同，完完成任务务的效率率(所费时时间_不同，为使完完成n项任务务的总效效率最高高（即所所需总时时最少），应如如何指派派（分派派）人员员的问题题统称为为指派（分派）问题。一、指派派问题的的数学模模型及其其特点 1.数数学模型型： 2.特特点（1）给给定一个个指派问问题时，必须给给出效率率矩阵（系数矩矩阵）CC=(CCij)

54、nxnn,且Cij0，因此此必有最最优解()。（2）指指派问题题是一种种特殊的的平衡的的运输问问题，由由于模型型结构的的特殊性性（看作作每产地地的产量量均为11，每销销地的销销量均为为1），故故可用更更为简便便的匈牙牙利法进进行求解解。（3）解解矩阵是指派问问题的可可行解，但不一一定是最最优解。二、指派派问题的的解法匈牙牙利法 1.匈匈牙利法法的基本本思想是是：对同同一项工工作（任任务）jj来说，同时提提高或降降低每人人相同的的效率（常数tti），不不影响其其最优指指派；同同样，对对同一个个人i来说，完成各各项工作作的效率率都提高高或降低低相同的的效率（常数ddi），也也不影响响其最优优指派，

55、因此可可得到新新的效率率矩阵(bijj)nxnn，其中中bij=Cijj+ti+dj （对所所有的ii,j）则新的目目标函数数为其中为常常数这说明ZZ与Z同时达达到最小小值。因因而最优优解相同同。故指指派问题题有以下下性质：若从效率率矩阵(Cijj)nxnn的一行行（列）各元素素中分别别减去该该行（列列）的最最小元素素，得到到的新效效率矩阵阵(bijj)nxnn不改变变原指派派问题的的最优解解。2.匈牙牙利法三、对求求最大化化的指派派问题，（即求求）,可采用用构造新新的效率率矩阵(MCij)nnxn，其中MM=maaxCCij，（显显然MCij0），将将其转化化为求所得到到的最优优解就是是原问

56、题题的最优优解。事事实上由于nMM为常数数，因此此，使ZZ取得最最小的最最优解就就是使ZZ取得最最大的最最优解。4.以上上讨论的的指派问问题是效效率矩阵阵的行数数等于列列数，即即m+nn的情况况。当mmn时，则则可用增增加虚设设的零元元数行（列）使使效率矩矩阵变成成方阵后后，再用用匈牙利利法求解解。m-n列n-m行当mnn时 5.指指派问题题必有最最优解，但可以以不唯一一。3 整数线线性规划划问题及及其解法法一、整数数线性规规划在上一章章讨论的的LP问题题中,对决策策变量只只限于不不能取负负值的连连续型数数值,即可以以是正分分数或正正小数。然而在在许多经经济管理理的实际际问题中中，决策策变量只

57、只有非负负整数才才有实际际意义。对求整整数最优优解的问问题，称称为整数数规划(Inttegeer PProggrammminng)(简记为为IP)。又称称约束条条件和函函数均为为线性的的IP为整整数线性性规划(Inttegeer LLineear Proograammiing)(简记记为ILLP)。ILP问问题数学学模型的的一般形形式为：求一组组变量XX1,X2,Xn，使人们对IIP感兴兴趣，还还因为有有些经济济管理中中的实际际问题的的解必须须满足如如逻辑条条件和顺顺序要求求等一些些特殊的的约束条条件。此此时需引引进逻辑辑变量（又称00-1变变量），以“0”表示“非”，以“1”表示“是”。凡决决策变量量均是00-1变变量的IIP为0-11规划。严格地说说，IPP是个非非线性问问题。