MBA运筹学实用培训讲义

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

2、件在计算机上进 行，这样可以节省大量的人力和时间。第一部分线性规划内容框架r LP问题数学模型实际问题 行解提 出LP问题解的概念可行解、最优基本解、基可基本最优解法段法基本方法I f图解法原始单纯形法|单纯形法一I人工变量法I对偶单纯形法大M两阶p对偶理论进一步讨论敏度分析F经济管理领域内应用参数规划特殊的LP问题:运输问题（转运问题） 整数规划多目标LP问题*第一部分线性规划（Linear Programming ）及其应用第一章LP问题的数学模型与求解§ 1 LP问题及其数学模型（一）引例1 （生产计划的问题）某工厂在计划期内要安排生产I、U的两种产品，已知生产单位产品所需的设

3、备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？In资源限量设备128（台时）原材料A4016(kg)原材料B0412(kg)单位产品利润（元）23该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的 生产计划方案。解：设Xi,X2分别表示在计划期内生产产品I、U的产量。由于资源的 限制，所以有：机器设备的限制条件：Xi+2X2<8 原材料A的限制条件：4x i< 16（称为资源约束条件）原材料B的限制条件：4x 2< 12 -同时，产品I、U的产量不能是负数，所以有Xl> 0，X2> 0（称为变量的非负约

4、束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有 许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产 量XI, X2以得到最大的利润，即使目标函数Z=2xi+3x2的值达到最大。综上所述，该生产计划安排问题可用以下数学模型表示：maxz=2x+3x2x1 2x28st.4xi 164x212x1 x20引例2.（营养配餐问题）假定一个成年人每天需要从食物中获取 3000卡路里热量，55克蛋白质 和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和 营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使 购买食品的费用最小？序号食品名称热量

5、（卡路里）蛋白质（克）钙(mg)价格（元）1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002解:设Xj（j=1,2,3,4）为第j种食品每天的购买量，则配餐问题数学模型为min z=10xi6x23x32x410000x1 800x2900x3 200x4300050x1 60x220x3 10x455x t400x1200x2 300x3 500x4800Xj 0( j 1,2,3,4)（二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征(1)每个问题都可用一组决策

6、变量(X1,X2,Xn)表示某一方案，其具 体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可 对变量的取值加以约束，如非负约束。( 2)存在一组线性等式或不等式的约束条件。( 3)都有一个用决策变量的线性函数作为决策目标(即目标函数) 按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：max(或 min )z=c 1X1+C2X2+cxn (1.1)a11 X2 a12 X2a21 X2a22 X2s.tam1 X2 am2 X2X1(1.2)或紧缩形式nmax或min)z=cj Xjj1naj Xj( , )bi (i

7、1,2, ,m)j1Xj0a1n Xna2n Xnamn XnX2Xn(,(,)b1)b2)bm(1.3)(1.4)或矩阵形式max或 min )z=cxAX ( , )bX0(1.5) 或向量形式：max或 min )z=cxnpj xj ( , )bj1Xj 0 (j 1,2, ,n)（1.6）其中C =（C1,C 2,Cn），称为价值系数向量;a11 ,a12 ,a1na21 ,a22 ,A 21 22a2n2n 称为技术系数矩阵（并称消耗系数矩阵）am1,am2 ,amn=（P 1小，小）b1b2b 2 称资源限制向量bmX = (xi,x 2,x n)TW为决策变量向量。（三）LP问

8、题的标准型1. 为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须 把LP问题的一般形式化为统一的标准型：nmaxz= Cj xj ;maxz=Cxj1jfjXjbi(i 42，m)或 AX bxj 0(j1,2,n)X 0maXz=cXn或 j 1 pjXjbXj 0(j 1,2, ,n)标准型的特点： 目标函数是最大化类型 约束条件均由等式组成 决策变量均为非负 b(i=1,2,n)2. 化一般形式为标准型 minz max(-z)=-cx左边“松驰变量” “ ” 左边 +松驰变量 变量Xj 0 -Xj 0变量Xj无限制令Xj =Xj xj bi<0等式两边同乘以(-1)

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

10、模型和方法。如非线性规 划，整数规划或不确定型分析方法。对LP标准型，我们还假定r（A）=m<n。（四）LP问题的解的概念设LP问题nmaxz= CjXjj i(1.7)najXjbi (i1,2,n)j i(1.8)Xj0( j 1,2,n)(1.9)1. 从代数的角度看:可行解和最优解满足约束条件(1.8)和(1.9)的解 X=(x1,x 2,x n)称为可行解。所有可行解构成可行解集，即可行域S X Axb,x 0。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的2. 从LP角度看：基：设A为mxr

11、矩阵，r(A)=m , 6是人中的mxr阶非奇异子矩阵(即|B| 0),则称B是 LP问题的一个基若B是LP问题的一个基，则B由m个线性独立的列向量组成，即 B = (Pr1,Pr2,Prm)，其中 Rj =1rj 月 2rj ,*) (j=1,2,耐称为基向理。 与其向量Prj相对应的变量Xrj称为基变量，其它变量称为非基变量。显然， 对应于每个基总有m个基变量，n-m个非基变量。基本解与基可行解设B是 LP问题的一个基，令其n-m个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一 对应的，基本解的个数W Cn。在基本解中，称满足非负条件的基本解为基 可行解，

12、对应的基称为可行基。退化解如果基解中非零分量的个数小于m则称此基本解为退化的，否则是非退化的。最优基如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。3. LP问题解之间的关系如图所示(五) 两个变量LP问题的图解法1丄P问题解的几何表示。以引例为例说明maxz=2x+3x2x1 2x284xi164x212x10, x20 按以下顺序进行：解：（1）画出直角坐标系；（2）依次做每条约束线，标出可行域的方向，并找出它们共同的 可行域；（3）任取一目标函数值作一条目标函数线 （称等值线），根据目标 函数（最大或最小）类型，平移该直线即将离开可行域上，则

13、与目标函数 线接触的最终点即表示最优解。图121其中，将目标函数Z=2xi+3X2改写为X2X1Z,因此，它可以33表示为：以z为参数，以 -为斜率的一族平行线。位于同一条直线上的点3具有相同的值。解的几种情况：（1）此例有唯一解 Q2，即xi=4,X2=2,z=14（2）有无穷多最优解（多重解），若将目标函数改为z=2xi+4x2则线段Q, Q上的点均为最优解。可行域与最优解间的关系:最优解可行域空 集'无最优解（无可行解）有界集.唯一最优解七三二三多重解无界集*无有限最优解（无界解）结论：（1） LP问题的可行域是凸集（凸多边形，凸多面体，）;（2）LP问题最优解若存在，则必可在可

14、行域的顶点上得到；（3）LP问题的可行域的顶点个数是有限的；（4）若LP问题有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最 优的点的问题2. 基可行解的几何意义对例1 LP问题标准化为maxZ=2x+3x2x1 2x2 x384x1 x4164x2 x512，X50可求得所有的基本解：x=(0,0,8,16,12)T(0 点),x =(4,0,4,0,12) T©点)x(3)=(4,2,0,0,4)t(Q2点),x =(2,3,0,8,0)丁©点)x(5)=(0,3,2,16,0)t(Q4点),x (6)=(4,

15、3,-2,0,0)T(C点)x=(8,0,0,-16,12)t(A点),x (8) =(0,4,0,16,-4)T(B 点)但A、B C三点是非可行域上的点，即非可行解。因此，x,x,x（3）, x，x（5）才是基可行解，它们与可行域的顶点相对应。于是还有结论：（5）对于标准型的LP问题， X是基 可行解的充要条件是X为可行 域的顶点。（6） LP问题可行域顶点的个数二基可行解的个数w基的个数w Cn3. 图解法只适用于两个变量（最多含三个变量）的 LP问题。4. 求解LP问题方法的思考： 完全枚举法，对m n较大时，U是一个很大的数，几乎不可能； 从可行域的一个顶点（基可行解）迭代到另一个顶

16、点（基可行解）。§ 2单纯形法与计算机求解1. 解LP问题单纯形法的基本思路:2. 单纯形法的计算步骤（表格形式）（1）建立初始单纯形表，假定B=I，b>0设 maxZ=cxi+C2X2+cxnX1a1m 1Xm 1a1n Xnb1X2a2m 1 Xm 1a2nXnb2Xmamm 1Xm 1amn XnbmXj0 (j 1,2,n)将目标函数改写为：-Z+C1X1+C2X2+CnXn = 0把上述方程组和目标函数方程构成n+1个变量，m+个方程的方程组,并写成增广矩阵的形式：-ZXiX2-1C2 XXAm7入m+1Xnb 0a 1m+1° a1n和 0a 2m+1a2

17、nb 21a mm+1amn bm CmCm+1 Cn0丿基变量形彳式XibinaijXjj 1代入z中的基变量，有令Z。G(biCbCi bim _Ci bi,ZjWijXj)CjXj(GaiJXjCjXjC3ijCWijCj)Xj于是ZZoj(Zj Cj)Xjm 1因此，上述的增广矩阵就可写成:ZX1X2Xm Xm+1Xnb-0 100a 1m+1a 1nb 10 010a 2m+1a 2nb 20 0013 mm+13 mnb mT 000mmCi3im 1Cm 1Ci3i n Cni 1i 1mGbii 1再令jCj乙mCji 1ciaij则上述增广矩阵可写成下面表格形式：即初始单纯形

18、表 T (B)CCCmCm+1CniCbXbbX1XmXm+1 XnC1X1b 110a1m+1a1nC2X2b 200a2m+1a2n:CmXmb m01amm+1amnZZd00m+1nj检验数行上述初始单纯形表可确定初始可行基和初始基可行解:0)B = (Pi,P2,Pm) = I, X=(b1,b2,bm, 0从初始单纯形表建立的过程可以看到以下事实:(1) 凡LP模型中约束条件为“W”型，在化为标准型后必有 B=I，如 果b> 0,则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数非基变量的系数则以相反数填入检验数行各相应位置。(2) 在单纯形表中，凡基变量所在的

19、列向量必是单位列向量，其相应 的检验数均为零。mm(3) Z°Cibi, j Zj Cj 询 Cj(j m 1, n)i 1i 1更好表现一般规律的在矩阵形式的单纯形表中设 MaxX=CXMaxZ=CX+QXAxbx Q其标准型为Ax IxL bx, Xl0将系数矩阵(A,I)分划为(B,N,I)，其中B为可行基,对应于基变量向量Xb,N对应于Xn， I对应于Xl,(X叫Xl)为非基变量向量。于是 (X,L) t=(Xb,X叫Xl)：(C,O)=(C b,C叫0)。因此，矩阵形式的LP模型改写为:XbMaxZ (CbCn，0)XnMaxZ CBXBCN X N 0X LXlXb(B,

20、N,I) XnbBXbNXn IX l bXlXB, XN , XL0Xb,Xn,Xl0用非基变量向量表示基变量向量，有-1 -1 -1Xb=B b B NX B X.代入目标函数中有-1 1-1Z =Cb(B b B NX BX)+CnXn+0X-1-1-1=C bB b GB NX CBB X_)+CX-1-1-1=C bB b (CbB N- CN)Xn CBB X_Z (CbB N Cn)Xn CbB Xl CbB b1 1 1XB B NX n B Xl B b写成对应于基B的矩阵形式的单纯形表T (B):ccbGclbXbXnXlXb1B b1b 1nb-1ZCBB-1b0CbB&

21、#39;1 N- GCbB1例如将例1化成标准型后如下表T ( B):c23000icbXbbX1X2X3X4X50X38121000X416400100X51204001-Z0-2-3000C j初始可行基 B=(P3,P4,P5)=I, X=(0,0,8,16,12)(2) 判别最优解1 在T(B)中，若所有的检验数C j>0 (j=1,2,n)则B为最优基，相应的基可行解为最优解，停止计算。2 在T(B)中，若有c k<0 (1 k n)，且Xk的系数列向量Pk 0,则该问 题无界，停止计算。否则转入(3)(3) 换基迭代(基变换)1 先确定入基变量X<: k=minj

22、|j<02 按最小比值原则确定出基变量xl：min1 aikaikbLaLk3 以8lk为主元，进行初等行变换（又称旋转变换）即将列向量Pk变换为单位列向量：返回（2）。换基迭代的关键在于将换入变量对应的列向量PK用初等行变换方法 变换成单位列向量。其中主元aLK变成1。即aika2kPkaik1第个分量amk0如果在最终表中有非基变量的检验数为0,则该问题有多重最优解。3.单纯形法的进一步讨论一一用人工变量法求初始基可行解（一）人工变量法若对LP莫型标准化后，不具有B=I时，如何办？此时可采用人工变量法 得到初始基可行解。所谓人工变量法是在原问题不含有初始可行基 B=I的情况下，人为的

23、对 约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP 问题后求解。当增加的人工变量全部取值为 0时，才与原问题等价。这样， 新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行 迭代。经迭代后，若人工变量全部被换成非基变量，则原问题的约束条件 被恢复，同时也得到一个基可行解。在最终表中若不能全部被换出，则说明原问题无可行解。 因此，该法的关键在于将人工变量全部换出。 人工变量法常见的有大狀和两阶段法。(1) 大M法(通过下例简略介绍其方法与步骤) 例，用大M法求解MinZ=x1+1.5x 2x1 3 x2 3x1 x2 2x1, x2 0解： MinZ=x1

24、+1.5x 2+0.x 3+0.x 4+Mx5+Mx6x13x2x3x1 x2x4x5 3x6 2x1,x2 0,x3, x40,x5, x6 0其中X3,x 4为松驰变量，X5,X 6为人工变量，M为任意大的正数。注意到：分别在约束条件增加人工变量X5,X6是为了构成“人工基” 对于Min的目标函数采用(+M)，而对于MaX的目标函数则采 用(-M)作为人工变量的系数，是强加于人工变量的一种惩罚，其目的是为了 强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。 对于minZ判别最优性准则应是C Zj < 0。 大M法适合于手算，不适用于计算机求解。( 2)两阶段法第一阶段

25、：不考虑原问题是否存在基可行解；给原 LP问题的约束条件 加入人工变量，构造仅含人工变量的目标函数并要求实现最小化(即使原 LP问题目标函数是求最大化)的辅助问题：Min W=x+i+Xn+ma11a1n xnxn 1b1a21 x1a2n xnxn 2b2amnxnxnbmxn m0然后用单纯形法求解（1）。若W0,则原问题无可行解，停止计算。若 W=0且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的 基可行解；如果人工变量中含有为 0的基变量时（即退化解） ，则可再进行 初等行变换将其换出，从而获得原问题的基可行解。第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工

26、变量列删去，同时将人工目标函数行换入原问题的目标函数作为第二阶段 计算的初始表。仍以上例为例用两阶段法求解。MinZ=x1+1.5x 2+0x3+0x4x1 3x2 x3 3原问题：x1 x2x4 2x1,x2 0,x3,x4 0MinW=x5+x6x13x2x3x5 3辅助问题：x1 x2x4x6 2x1,x2 0,x3,x4 0, x5 , x6 0书中第19页表2.9和表2.10的说明：（1）第一阶段的初始表中非基变量的检验数 =人工变量所在行的非基变量相应系数之和，目标函值值 =人工变量所在行相应常数之和（2）第二阶段单纯形表中目标函数系数应将非基变量表示基变量后所 得结果填入，或先直

27、接填入原系数，再通过初等行变换使基变量的检验数 为0。（3）若maxZ则可转化为minZZ1二Z）（二）退化单纯形法计算中用 规则决定换出变量时，有时出现两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于 0,出现退化解,如某个最大化问题的单纯形表为：C403000CbbXiX2X3X4X5X6i0X5620101030X431-1010030X651110015Z0-40-3000j0X50021-21004Xi31-10100/0X63021-1011Z120-4-3400j在出现退化解后的继续迭代中，有可能出现基循环:B E2 Bi这样迭代下去便永远得不到最优解。解决基循

28、环的方法很多，如“摄动法”、“字典序法”等等 在计算机上常采用“ Bia nd规则”：（1）取表中下标最小的非基变量Xk为换入变量，即k=mi nj | j >0（2）按 规则计算，若存在两个相同以上最小比值时，选取下标最小 的基变量为换出变量XL，即L min r | r mi门旦 | aik 0aik值得庆幸的是出现基循环是罕见的。§ 3对偶理论与灵敏度分析一、LP的对偶问题1. 引例 前已述引例1是一个在有限资源的条件下，求使利润最大的生 产计划安排问题，其数学模型为：maxZ=2x+3x2X! 2x28（设备）4x216（原材料A）4X212（原材料B）x1 ,x20现

29、从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台 时和购买工厂的原材料A、B,为其加工生产别的产品，由客户支付台时费 和材料费，此时工厂应考虑如何为每种资源的定价问题？解：设y1,y2,y3分别表示出租单位设备台时的租金和出售单位原材料 A、 B的价格（含附加值）工厂决策者考虑：（1）出租设备和出售原材料应不少于自己生产产品的获利，否则不如自己生产为好。因此有y1 4y2 22y1 4y3 3工厂的总收入为W=8y1+16y2+12y3（2）价格应尽量低，否则没有竞争力 （此价格可成为与客户谈判的底 价）租赁者考虑：希望价格越低越好，否则另找他人。 于是，能够使双方共同接受的是Min

30、W=8y1+16y2+12y3y1 4y2 2s.t 2y1 4y3 3y1 y2 y3 0上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产 生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称 这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问 题。2. 从矩阵形式讨论互为对偶LP问题由例1有maxZ=cxYX bX0由矩阵形式的单纯形表中可知：检验数的表达式为：1当 CBB N CN 0当 CB B 1 0表示LP问题已得到最优解令Y=CB-1,且有Y 0由于基变量Xb的检验数为0,可改写成GBt CB=0 因此，包括基变量在内的所有检验数可写成

31、(CbB-1 B Cb, C bB1 N CN)=(C bB-1A C)= YA C> 0 即YA C又对YmCB1，两边右乘b,有-1Yb=CB b=Z由于丫无上界，所以只有最小值，因此有Mi nW=YbYA CY 0它是原问题maxZ=CX| AX b,X 0的对偶问题于是，对称形式下两个互为对偶LP问题的数学模型为：MaxZ=CXMin W=YbYXbYA C与X0Y 0任何一个LP问题均有一个对偶LP问题与之匹配。对偶理论就是研究LP问题及其对偶问题的理论，它是 LP理论中的重要 内容之一。二、对偶理论1. 原问题与对偶问题的关系如下表所示原始对偶表原问题Max (对偶问题)对偶

32、问题Min (原问题)约束条件数=m变量个数=m第i个约束条件为“”第i个变量0第i个约束条件为“”第i个变量w 0第i个约束条件为“=”第i个变量无限制变量个数=m约束条件个数=n第i个变量0第i个约束条件为“”第i个变量w 0第i个约束条件为“”第i个变量无限制第i个约束条件为“=”第i个约束条件的右端项目标函数第i个变量的系数目标函第i个变量的系数第i个约束条件的右端顶2. 对偶问题的基本性质MaxZ=CXMin W=YbYX bYA C设X 0Y 0（1）（对称性）对偶问题的对偶是原问题；（2） （弱对偶性）若X是原问题的可行解，Y是对偶问题的可行解;则 CX Yb ；（3）（无界性）

33、若原问题（对偶问题）为无界解，则其对偶问题（原 问题）无可行解；（4）（最优性准则），若X、Y分别是互为对偶问题的可行解，且 cX=Yb，则X、Y分别是它们的最优解；（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最 优解，且它们的目标函数值相等。从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一: 原问题与对偶问题都有最优解，且 CX=Yb 一个问题具有无界解，则它的对偶问题无可行解； 两个问题均无可行解。、 * *（6）（互补松驰性），若X、丫分别是原问题的对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*Xs=O,YsX*=O（其中Xs,Ys分别是原问题和对

34、偶问题的松驰变量向量）。或，x*、Y分别是原问题和对偶问题最优解的充要条件是： 若y：>0,则 ajXj=b 若 ajX*j<b，则 y*i=0若X*j>0，则 aj y*i=Cj若 aj y*i>Cj，则 X*j=0三、对偶单纯形法1. 单纯形法的重新解释X*是最大化原LP问题最优解的充要条件是同时满足 （称为原始可行条件）CBB 1N CN 0（称为对偶可行条件）因此，单纯形法是在保持原始可行下，经过迭代， 逐步实现对偶可行, 达到求出最优解的过程。根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步 实现原始可行，以求得最优解。对偶单纯形法就是这种思想所设

35、计的。2. 对偶单纯形法的计算步骤：举例说明3. 对偶单纯形法与单纯形法的不同之点： 不要求模型中b> 0 先确定换出变量Xl，再确定换入变量Xk min - | arj 0-j arjark4. 对偶单纯形法适用对象AXXb（b无限制），|（t）0AXb（t）(t 1,2,r) 当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法或对偶单纯形法解之 进行灵敏度分析时，有时会用到此法四、对偶解的经济含义和影子价格1. 对偶解Y*=GB1的经济含义设互为对偶的LP问题maxZ=CXmin W=Yb原)AX(对)YA CY 0有Z*=C bB-1 b=W* (其中B为最优基)Z *1因

36、此CBBy *b或者说 Z*=y* 1b计 y*2b2+y*m)mZ*bi其含义是：若对原问题右端常数项向量b中的某一常数项b增加一个单 位，目标函数的最优值Z*的变化将是Y*。换句话说，Y*表示当bi增加一个 单位时，目标函数最优值的相应增量。实质上 Y*就是第i种资源边际价值 的一种表现，也是对第i种资源的一种估价。事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是:maxZ=2x+3x2min W=8y+16y2+12y3yi 4y222yi 4y33yi, y 0, y30X! 2x28(原问题)4x,16（对偶问题）4X212X1 , x20对原问

37、题用单纯形法求解所得最终表为C23000CbXbbX1X2X3X4X52X141001/400X5400-21/213X22011/2-1/80Z14001.50.1250由此，它们的最优解分别是X*=(4,2) 丁和丫=(1.5,0.125,0)Z*=W*=14=8Y 1*+16Y2*12Y3*y1Z*1.5, y2*Z*b20.125, yZ*bi其中Y1*=1.5表示单独对设备台时增加1个单位，可使Z值增加1.5个单位的利润；Y2*=0.125表示单独对原材料A增加1个单位，可使Z值增加0.125 个单位的利润；而Y3*=0表示单独对原材料B增加一个单位，却不使Z值增加这是因为从最终表中

38、可看出，在最优方案中，松驰变量X5=4,即表示在最优生产方案中，原材料B尚有4个单位剩余被闲置，不产生任何经济效益。2. 影子价格的定义把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影 子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。资源的影子价格定量的反映了单位资源在最优生产方案中为总收益应 提供的收益，因此，资源的影子价格也可称为在最优方案中投入生产的机 会成本。3. 影子价格的求法（1）在非退化情况下：设B为LP问题的最优基，则资源的影价=Y*=CB-1（2）在退化情况下：当对偶问

39、题有K个最优解，则第i种资源的影价=叫门yi*（k）即影价的 第i个分量等于这K个对偶解中第i个分量的最小值。例如，设某资源利用问题为maxZ=3xi+X2c（资源1限制）x1 x22（资源2限制）3x1 2x26x1, x20最终表3100bX1X2X3X4X121110X400-1-31Z60230X1212/301/3X3001/31-1/3Z I 6 I 0101资源1的影价=mi ny1 ,y=mi n3,0=0资源2的影价=miny；,y 2*(2) =min0,1=04. 影子价格的参谋作用 影价>0,说明该资源已耗尽，(1) 指出企业挖潜革新的途径成为短线资源。影价=0,

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

41、是在目前最优基B下进行的。即当参数A、b、c中的 某一个或几个发生变化时，考察是否影响以下两式的成立?B b 01CbB N CN 01.对资源数量br变化的分析当b中某个br发生改变时，将影响基变量的取值 XB=B_1b。若br的变化仍 满足1b>0,则目前的基B仍为最优基，仅在1b和CBB-1b的数量上有些改变。 若br的变化使B'1b中某些分量小于0,则目前的基成为非可行基，为此，可 用对偶单纯形法迭代求得新的最优解。1b>0给出了使最优基B呆持不变时 br的允许的变化范围：由解不等式组0B -1(b+ bBb+B1 br0可得：bi air br 0 (i 1,2,

42、 m)0miax 6/比|瓦 0brmin 6/百|乳 0i其中bi为最终表中b列的第i个分量，air为B-1中第r列的元素。例2.对价值系数C变化的分析(1)当Cn中某个C发生变化时，只影到非基变量Xj的检验数由于j (CbB 1Pj) (Cj Cj) j Cj若 j 0，则Cj。这就是保持最优基不变下， C的允许变化范围。否则，用单纯形法继续迭代，求得新的最优解。(2)当CB中某个C发生变化时,则会影响到所有非基变量的检验数c n=CBB-1 N g。解不等式组一 =(Cb+ACb)B-1 N- CN=(CbB-1 N- G)+ CbB-1 N> 01 1即(CbB- N- 5+(0

43、, C,0)B - N>0jCr arj 0( j JN )得到使最优解不变G的允许变化范围；mpj /arj | arj0C min0例(3) 对增加新产品的分析设革企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润 为G+1,消耗系数向量为只+1=1+1月2+1,am*)此时应如何分析才能确定 该新产品理澡投产？增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因 此可从现行的最估基B出发考虑：若 C n+GB1 Pn+1 G+1<0,则应投产若 C n+GB1 Pn+1 G+1>0,则不应投入。即新产品的机会成本小于目前的市场价格时，应投产否则不应投

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

45、产品的分析相同。第二种情况（当j Jb）：由于B中元素的改变影响到B1的变化，因此也 影响到T（B）。目前的基B对应的解有可能既不是原始可行，也不是对偶可行。 于是不如重新求解。第二章特殊LP问题及其解法所谓特殊LP问题是指LP模型的系数矩阵具有特殊的结构，有可能找到 比单纯形法更为简便的求解方法，从而节省人力和物力。§ 1运输问题及其解法引例：某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A-7吨,£4吨，A-9吨。该公司把这些产品分别运往四个销售点，各销售每日销量 为：B-3吨，B2-6吨，B3-5吨，B-6吨。已知从各工厂到各销售点的单位产 品的运价为下表所示

46、。问该公司应如何调运产品，在满足各销售点需求量 的前提下，使总运费为最少。A974105销量3656解：这是一个产销平衡的运输问题，其数学模型是:设X表示从A调运产品到B的数量（吨），则min Z=3Xi+11X2+3X3+10X4+X：i+9X：2+2X 23+8*4+7X2*1+4X32+10X3+5X34X11+X12+X13+X14=7s.tX11X31+X32+X33+X34=9+X21+X31=3X12+X22+X32=6X13+X23+X33=5X21+X22+X23+X24=4X14+X24+X34 =6<Xij > 0(i=1,2,3, j=1,2,3,4)、产量

47、平衡的运输问题及其解法1. 产销平衡的运输问题的数学模型及其特点m nmi nZCXi 1 j 1mXijbj (j 1,2,m)i 1nXijai (i 1,2,n)j 1Xj 0 (i 1 m,j 1 n)特点：（1）其系数矩阵的结构疏松，且每一列向量R =（0,1,1,0） T=e +em+j可以证明，r（A）=m+n 1。即有m+n- 1个独立方程。于是，该LP问题有且仅有m+n-1个基变量。mn（2） aibj （产销平衡条件）i 1j 1mn（3） 因为 MinZCij Xij 0故必有可行解和最优解。i1j1由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大 大增加，故

48、用特殊解法表上作业法。2. 表上作业法 表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其 计算步骤方法，并通过对引例的求解过程说明之一。（1）用最小元素法确定初始方案（即初始基可行解） 切记在产销平衡表上必须且只能填写 m+n- 1个数字格（2）用位势法求出空格的检验数并进行最优解的判别设U1,U2,um v 1,v 2,v n是对应运输问题m+r个约束条件的对偶变量, B为含有人工变量的初始可行基，由LP问题的对偶理论知-1CBB =（U1,U 2,Um； v 1,v 2,v n）而每个决策变量Xj相应的系数向量Pj =e+em+j，所以CbB-1R =u+Vj 于是，检验数 c

49、 ij =CBB Pj Cj =（u i +Vj） Cj 又各基变量的检验数为 0，故对每个基变量所在的数格的检验数有 （u i+vj ） Cij =0 i,jJB即有方程组UiiV j1C i1 j1Ui2V j2C i2 j2、共m+个未知数 s=m+n 1个方程UisV jsCisjs显然上述方程有解，且由于含有一个自由变量，因此，可令任一未知数为0,就可求出上述方程组的解(Ui1,Ui2,Uim,Vj1,Vj2,Vjn)称为位势解。如用位势法求引例初始基可行解的检验数：第一步：将运价表中的数字分别写在各格听右上角，并对基变量相应 的运价加圈，同时在表中增加Vj和Ui列。第二步：利用圈数

50、格分别算出Ui和Vj，即卩令Ui=0,然后按Ui+Vj=G (i,jJb)，相继确定Ui，Vj的值。于是有V3=3,V4=10,U2=-1,v i=2,u 3=-5,v 2=9第三步：按(T ij = (u i+Vj) c (i,jJn)算出表中各空格(即非基变量)的检验数：(T ii=(0+2) 3=-1，(T12=(0+9) 11=-2 ，(T 22=- 1，(T24=1，(T 31=-10 ，(T 33=- 12由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的（T ij =CBB1 R - Cij w 0因为24=+1>0,所以目前尚未得到最优解，尚须改进（3）在调运平衡表上用闭回路法进行