华南理工大学工商管理学院运筹学试用教材.pdf

目录目录第一章线性规划.1第一节 线性规划模型.1第二节线性规划的求解.5一、两变量线性规划问题的图解法.5二、单纯形法.6三、改进单纯形法.21复习思考题.24第二章对偶理论与对偶单纯形法.27第一节对偶理论.28第二节 非对称对偶问题.31第三节 对偶单纯形法.33复习思考题.35第三章灵敏度分析.37一、目标函数系数0的变化.38二、右端常数为的变化.39三、约束矩阵A的变化.40复习思考题.42第四章特殊类型的线性规划.44第一节 整数规划模型.44第二节0-1整数规划模型.47第三节运输问题.47一、产销平衡的运输问题.49二、运输问题的扩展.53第四节指派问题.56复习思考题.57第五章图论.59第一节图与网络的概念.59一、图的概念.59二、图与子图.60第二节最小树问题.61一、树、支撑树与最小树.61二、最小树问题的解法.61第三节 最短路问题.62一、Dijk s t ra标号法.63二、Dijk s t ra简化标号法.68I运筹学华南理工大学工商管理学院 试用教材第四节最大流问题.69一、基本概念与定理.69二、Fo rd-Ful k e rs o n标号法.73复习思考题.80第六章目标规划.82第一节 目标规划的模型.82一、目标规划的引出.82二、目标规划的基本概念.83三、目标规划的数学模型及建模步骤.86第二节目标规划的图解法.89第三节 求解目标规划的单纯形法.91复习思考题.93第七章存贮论.95第一节存贮论的基本概念.95一、存贮问题的提出.95二、存贮论的基本概念.96第二节确定性存贮模型.97一、模型一：不允许缺货，生产时间很短的存贮模型.97二、模型二：不允许缺货，生产需一定时间的存贮模型.99三、模型三：允许缺货（需补足），生产时间很短的存贮模型.101四、模型四：允许缺货（需补足），生产需一定时间的存贮模型.103五、模型五：价格有折扣的存贮模型.106复习思考题.108第一章线性规划第一章线性规划口学习目标掌握基本的线性规划问题的建模、两变量线性规划问题的图解法、单纯形表上作业法；了解改进单纯形 法的基本原理，掌握求解方法.第一节线性规划模型在运筹学里使用的“模型”一词的含义与其在语言文字中的含义不同。运筹学里所说的模型是某些真实事 物的简化表述。通过建立模型，有助于解次被抽象的实际问题，并且指导我们解决其他具有这些共性的实际 问题。当用线性规划来求解一个实际问题的时候，需要把这个实际问题用适当的数学形式表达出来，这个表达 的过程，就是建立数学模型的过程。建立线性规划问题数学模型有三个基本步骤：第一步，找出选定的未知变量（决策变量），并用代数符号表示它们；第二步，找出问题中所有的约束条件，写出未知变量的线性方程或线性不等式；第三步，找出模型的目标或标准，表示成决策变量的线性函数，求其最大值或最小值。下面通过儿个线 性规划问题来说明这些建模的基本过程。例1.1生产计划问题某公司准备制订生产计划，利用两种资源生产三种不同的产品A、B、C,生产部门提供的单位产品资源 消耗的数据如下：资源单位产品资源消耗日最大供应量产品A产品B产品C劳动力（小时）11150原材料（磅）945400每件产品利润（美元）431试建立规划模型，求各种产品的日产量，使总收益最大。解：第一步，确定决策变量。根据题目的要求，未知变量是A、B、C三个产品的日产量，分别设为：叫一产品A的日产量 数一产品B的日产量 g产品C的日产量第二步，确定约束条件。在这个问题中，约束条件是可用劳动力和原材料的限制。对于劳动力而言，有71+12+23（50同理，对于原材料而言，约束条件为：9*1+4x2+5a;3 W 400第三步，确定目标函数。本问题的目标是使整个销售利润最大。假设全部产品可以售出，则全部利润 为：ma x Z 4叫+3*2+*31运筹学华南理工大学工商管理学院 试用教材因此这个生产组合问题的线性规划问题变成：ma x Z=4x i+3x 2+73S.t.X+X2+X3 4 509*i+422+5x3 W 400Xi20,22*320例1.2下料问题某公司需要一批某种规格的线材，要求长度为50c m的300根，40c m的400根，30c m的500根，现市场上这 种规格的线材只有长度为110c m的，试建模求该厂至少需要在市场上购进多少根这样的材料进行切割，才能满 足其需求。解：最简单的办法就是，按照一定的顺序，先满足所有的50c m的需求，然后切割40c m的，最后再切 割30c m的。这种做法虽然很方便，但是却不一定是最省的方法。这里通过建立线性规划模型来找出一种 最省材料的方法。首先，先找出把110c m的线材切割成30c m,40c m,50c m的所有可能的切割方法。如图1-1所示，一共 有6种切割法。图1-1 6种不同的下料切法为了用最少的原材料，需要混合使用上述6种下料方法。设按第井中切割法下料的l l()c m的线材的根数 为g,可列出以下的数学模型。min Z=xi+X2+X3+X4+x5+x6s.t.2xi+X2+X32300X2+2x4+252400 2X3+X4+2X5+3262500Xi 0,i=1,2,3,4,5,6例1.3投资问题某公司投资部现有资金200万元，今后5年内考虑给以下的项目投资，已知项目1：每年年初都可以投资，当年末收回本利110%；项目2：每年年初都可以投资，次年末回收120%；项目3：每年年初都可以投资，回收周期为3年，回收本利135%；项目4：第三年初需要投资，到第五年末回收本利160%,但是规定最大投资额不能超出100万元。问：应 如何确定这些项目的投资时间和投资额，使得第五年末拥有资金的本利金额为最大？解：(1)确定变量：这是一个连续投资问题，设g,=第，年初投资于*页目的金额，根据上述条件，可以列出每年年初和年末的资金总额，见下表2第一章线性规划年份年初投资总额年末收回本利总额1Xj +X12+犬31.1孙2121+工22+工23l.lx2 1+1.2x123工31+132+X33+134LI%+L2%2 2+135项34工41+*42+*431.lx41+1.2x32+1.35x235%51+X52+153l.lx51+1.2x42+1.35九33+L6X3 4(2)约束条件：第1年：因为年初可用于投资的资金总额为200万，所以当年的投资总额不能超过这个数量，故有111+X12+X13 4 200第2年：因第二年初投资的资金来自于第一年年末，故有X21+222+*2 3 W 1-111下一年初用于投资的资金总额不能超出上一年年末所拥有的资金总额，同理，可以写出第3、4、5年的约 束条件。第3年：*3 1+132+X33+734 =1,2,3,4Xl l+X12+X13200X21+X22+X23X31+X32+X33+*34w1.1*21+1.2X12X41+X42+*43wI.I 231+1.2X22+1.35213*51+?52+*53w1.1*41+1.2X32+1.35X23力341003运筹学华南理工大学工商管理学院 试用教材有读者可能会问，如果全部约束都为不等式，是否意味着每年年末的可用资金不会在次年年初全部投资 完，那么在次年年末的资金中是否也应该考虑这些未使用的资金？从严格意义上来说，在模型中是可以这样 处理的，读者可以尝试写出这样的模型。但从实际意义上来说，既然每年年初投资的投资都可以在年末回收 本利，那么不投资也就意味着浪费。因此，上述模型中，除了最后一个约束不等式（即项目4在第3年的投资额 不得超过1（）0万元）之外，其它约束都可以写为严格等式。不过，上述模型，以及这里所说的两种情况所建出 的模型，最后的最优解必然是一致的，因为第5年年末本利和最大的目标会必然导致这样的结果。例1.4设址问题考虑A1、人2、人3三地，每地都出产一定数量的原料、也消耗一定数量的产品（见下表）。已知制成每吨产 品需4吨原料 各地之间的距离为：Ai人2，150k mAi一43，100k mA2A3,200k m假定每万吨原料运输1k m的费用是5000元，每万吨产品运输1k m的费用是6000元。由于地区条件差异，在 不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才能使总费用最小？出产原料及产品需求情况地点年产原料（万吨）年产品需求（万吨）生产费用（万元/万吨）小307200“2251015023458160解：（1）确定变量：令*为4运往4的原料数量，g叮为4运往4的产品数量，i,j-1,2,3o（2）约束条件：根据题意，有11+X12+213(30力 21+7 22+223(25*3 1+*3 2+X33445yn+y2i+yn二7yi2+y22+32二10、yi3+。23+。33=8若设Q为4处的设厂规模（产品年产量），则有Qi ya+yi2+gi3,Qi +52 2+V2 3，Qs ysi+ys2+沙33原料与产品的平衡为1+*2 1+。31X12+*2 2+。32213+力 23+233=4(y11+yi2+yi3)4(21+y22+沙23)=4(,31+V32+。33)将上述条件合并，则有:4第一章线性规划4gl i+4g12+4g13+x12+x i3-x2i 一 x3i 4 304g21+4g22+4g23+力21+223 7 12 X32 4 254g31+4g32+4g33+X31+X32 i3 223 4 45yn+y2i+y3i=7yi2+V22+沙32=10J13+J23+y338 xij20,J，=1,2,3,、V ij20,KI=1,2,3(3)目标函数：本题的目的是使总费用最小，则目标函数为(包括原料运输费用、产品运输费用和生产费 用)，(单位：万元)。min Z-75*12+75x 21+50 x i3+50*31+I OOC23+I OO232+901/12+90V21+60gl3+60g31+12023+120g32+200(j/n+ni2+gi3)+150(7/2i+y22+V23)+160(姬1+y32+933)第二节线性规划的求解上一节简单介绍了把一些实际问题描述成线性规划数学模型的过程，那么模型如何求解呢？本节先介绍 两个变量的线性规划问题的在坐标系中的图解法，然后再学习具有普遍意义的多变量线性规划问题的解法一 一单纯形法。一、两变量线性规划问题的图解法线性规划问题求解的方法比较多，首先介绍模型中仅有两个变量的线性规划问题的求解，用图解法来求 解具有直观、易理解的优点。虽然对于模型中有多于两个变量的问题，图解法不具有适用性，但是通过介绍 这种方法有助于理解几个基本概念。例1.5ma x Z=xi+3x 2s.t.Xi+2X2 4 10力1+2221徵4 4*1,220这是一个两变量线性规划问题。这个问题中要求解出力1、的值，使它们满足全部的约束，并取得目标 函数的最大值。首先，找出所有满足乃、力2非负且符合全部约束的值。例如，3=1，力2=3,它们的值为 非负，且满足所有的约束条件，这种解称为可行解。全部可行解的集合称为可行域。线性规划问题的最优解 就是在可行域内使问题取得最优值的可行解。用图解法来求解两变量线性规划问题时，首先要在坐标平面上画出可行域。在本例中，可行域是由三个 约束条件在第一象限所围成的多边形组成。其中，21+2 W 10,要求可行解都在直线的+2/2=10的左 侧；*1+/221要求可行解都在直线*1+*2=1的右侧；/2 W 4要求所有的可行解在直线*2=4的卜侧。由 此得到的可行域在图1-2中由阴影部分的多边形ABCDE构成。观察目标函数Z,若固定Z值，则目标方程Z=叫+3/2代表一条直线。当Z取不同值的时候，就形成了 一系列斜率相同的直线簇。通过变换几个Z值可发现，要使Z取得最大值，必须使直线Z=2i+3/2向远离原 点的方向移动(见图1-2中的箭头指向)。当这条直线移动到点C(2,4)时，直线Z=/i+3/2即将离开可行域 的临界点处，再向外移动就会导致目标函数与可行域没有重合的部分。此时，21=2,22=4,Z取得最大 值14。从图解法中，可以导出线性规划问题的两个重要的性质：5运筹学华南理工大学工商管理学院 试用教材图1-2性质1线性规划问题的可行域如果存在的话，是一个凸集。性质2线性规划问题的最优解如果存在的话，则一定在可行域凸集的顶点上达到。这两条性质不仅对于两变量线性规划问题成立，对于多变量线性规划问题也是成立的。图解法虽然直观、简明，但是它能解决的问题非常有限。一旦变量的数量超过两个时，这种解法就无能 为力了。为了求解一般的线性规划问题，有必要介绍一种具有普遍意义的方法。本书主要介绍Da n t zig的单纯 形法(Simp l e x me t ho d)o二、单纯形法(一)线性规划问题的标准化1.线性规划问题的标准形式有小个约束，几个变量的线性规划问题的一般表示形式为：max Z c xi+。2*2+cnxns.t.anxi+ai2X2 H-F ainxn bi211+。2272 H-F a2nXna62QmlCl+Qm2*2+,+CLmnXn(*120,2220,附o,历0,匕20,，brn0,或者min Z cii+。2*2+cnxnS.t.anXi+ai2X2+-F QlnnbiQ2 12 1+。22*2+(12nXn22Or n.l Xi+Qm.2 2 2+,+*120,2 220,*n?o,bl20,20,，b/n0,使用单纯形法求解线性规划问题，首先要求数学模型采取标准化的形式。下面是有加个约束，几个变量的6第一章线性规划线性规划问题的标准形式：ma x(min)Z +C2X2+cnxns.t.anxi+ai2X2+ainxn biQ2 12 1+0,22X2+Q2 n=62Cl ml l+Qm2*2+，+d mnXn tm 乃0,*220,*n20,bl0,6220,，bm)0,这种标准形式的特点是：(1)、目标函数取最大值或最小值；(2)、全部约束条件都用方程表示；(3)、全部变量非负；(4)、约束方程的右侧常数全部非负。用矩阵向量符号，可将上述问题更简洁地表述为：ma x(min)Z exs.t.Ax=bx0b0其中，4是(mx Ti)矩阵，称为系数矩阵，b是(mx l)列向量,c是(1 x九)行向量。即:4m x n-anfl2 1Q12*Q2 2 4,.ain一。2九,Xn x1-XlX2)b?7 2 X 1=bi匕2,Cixn=(C1,C2,.,cn)_ d ml*mn _ xn._ bm _2.写出线性规划问题的标准形式在碰到线性规划问题的数学模型时，都应把它们变换为标准形式后求解。当写出的数学模型不满足上述 标准形式的特点中的任何一条时，都需要做适当的变换。(1)不等式约束条件的变换这里有两种情况：一是约束方程为不等式时，可在“W”不等号的左端加入非负松弛变量(Sl a c k va ria bl e),然后将变为二；另一种是约束方程为“牙不等式，则可在不等号左边减去一个非负的剩余 变量(Surp l us va ria bl e),然后将变为“=”。例1.63xi+5x2 4 15 加入松弛变量叼 3叫+5x2+X3=152X1+*2+/3210 加入剩余变量*2xi+*3-*4=10(2)变量的符号为非正。这里又有两种情况：一是变量费的符号为负，即g(0,此时取另一变量必=-g,用-必替换g,则 可以保证所有的变量均为非负；另一种情况是，变量叼没有符号限制，此时的处理办法是，取两个非负变 量必、Xj,.Xj=xj Xj,用叫-吗替换叼，即可保证变量均为非负。7运筹学华南理工大学工商管理学院 试用教材例1.73x i X2+623 1X1+22 33=3X120,*2 0,23无符号限制引入变量工：20,工；0,x；20,使变量a：$=一盯，x3=x3 x3xi+/+6x 3 6*4 1X1 22 323+SiEg 3XI20,助0,送0,X320(3)约束条件右边的常数为负数。出现这种情况时，方程两边同乘-1即可。例1.8X1+徵+*3=1 方程两端同乘以Xi X2 Xs 1(-)关键概念求解线性规划问题的实质，就是求出线性方程组的解集，并在解集里找出使目标函数取得最大值或最小 值的那一个或一组解。线性方程组可以用消元法，或者称为高斯-约旦(Ga us s-Jo rda n)解法求解(详见线性代数 课程中的相关内容)。这种解法的核心内容，就是通过“高斯-约当”消元法(在线性代数中称为初等行变换)来 进行消元。通过“高斯-约当“消元得到的新的方程组，与原方程组为等价方程组。这种消元法的两种类型为：1、方程组中的任一方程乘上一个不为零的数；2、方程组中的任一方程两边同乘一个常数，分别加到另一方程的两边。下面通过一个例子来回顾一下这种解法。例1.9下面的方程组含有两个方程，它们各有5个变量：(S1)2+23 4/4+25=2(1-1)X1 2223 364 25=4(1-2)由于未知量的个数多于方程数，所以这个方程组有一个以上的解，这些解的集合称为解集。将S1中的(1-1)式乘以-1,力口到(1-2)上去，可得方程组S1的一个等价方程组S2($2)X1 2X2+的 一 4X4+2X5=2(1-3)X2 2X3+*4 3*5=2(1-4)再用S2中的(1-4)乘以2,加I到(1-3)中去，可以得到另一个等价方程组S3(S3)xi 3*3 2*4 4*5=6(1-5)X2 2*3+*4 3*5=2(1-6)由于Si，S2,S3是等价方程组，因此任一方程组的解，也是其它两个方程组的解。而观察S3,可以很容 易可以得出一组解。令力3=工4=*5=0，有*1=6,*2=2。任选/3,X4,X5的值，通过(1-5)和(1-6)可以求 得相应的力1,如的值，可得到方程组S3的其它的解，所有这些解都是原问题的解。用此例来学习有关的几个 定义：基变量若一个变量在一个方程中的系数为1,在其他方程中系数为零，则称这个变量为给定方程的基变量(基本 变量，Ba s ic va ria bl e)0基变量以外的其他变量叫做非基变量。在丛中,叫,*2为基变量，砌x4,g为非基变 旦 里。正规方程组(Ca n o n ic a l s ys t e m)在方程组中的每个方程中都有一个基变量的时候，方程组就是正规方程组。在例1.9中，从(1-1)和(1-2)式 中分别消去数，叫的系数，得到的等价方程组S3就是正规方程组。实际上，本例中任意两个变量通过初等变 8第一章线性规划换消去系数之后，都可以成为基变量，相应的方程组就是正规方程组。在其他时候，通过引入松弛变量作为 基变量，也可以得到正规方程组，这种方程在解题中经常会使用到。注意，由于正规方程组中每个方程都必须含有一个基变量，因此，基变量的个数由方程个数决定，非基 变量的个数就等于所有变量的个数减去基变量的个数。“高斯-约当“消元法(Ga us s-Jo rda n El imin a t io n)即把给定方程组简化为等价方程组的初等变换方法。通过消元，使得指定变量在一个方程中系数为1,在 其他方程中系数为零。要使一般的方程组变为正规方程组，就需要进行高斯-约旦消元。基本解(Ba s ic s o l ut io n)令非基变量取值为零，求解基变量所得到的正规方程组的解叫做基本解。基本可行解(Ba s ic f e a s ibl e s o l ut io n)基变量非负的基本解，叫做基本可行解。在本例中，XI=6,*2=2,*3=*4=*5=0就是基本解，同 时也是基本可行解。上述的概念对于理解后面单纯形法的求解原理是非常重要的，需要准确地掌握。(三)单纯形法的求解过程1.单纯形法的原理下面通过一个例子，来介绍单纯形法的原理。例 1.10ma x Z 4%+3+*3S.t.Xi+X2+*3 4 50(1-7)9g+4x2+5x 3 4 400(1-8)X10,22。，力30这个线性规划问题不是标准形式，通过在(1-7)和(1-8)中各引入一个松弛变量为4,为5，使问题标准化如 下：ma x Z=4x i+3/2+6s.t.*1+2 2+2 3+2 4=50(1-9)9*i+42+53+25=400(1-10)Xi 0,i=1,2,3,4,5此时，约束条件中的方程组是正规方程组，变量24是方程(1-9)的基变量，力5是方程(1-10)的基变量。可以 得到一个基本解/1=2 2=23=0,*4=50,*5=400,因为全部变量都为非负，所以这个解也是基本可行 解。此时的目标函数值为：Z=4(0)+3(0)+1(0)=0需要指出，不是所有问题都像本例一样轻易地得出基本可行解，当出现这种情况的时候，需要求出正规 方程组的基本可行解之后，再应用单纯形法。在(四)中将会讨论这种情况。基本可行解的改进已知初始基本可行解为：X-j.X2 X3 0,X4 50,X5 400,此时 Z 0为了使目标函数取得最大值，首先要检验当前的目标函数值Z是否为最优，如果不是，则选择新的基变 量和非基变量，从而改进Z的值。改进的方法是更换基变量，即：根据一定规则，把某个非基变量变成基变 9运筹学华南理工大学工商管理学院 试用教材量，把相应地把某个基变量变为非基变量。改进的关键，就是适当地配对交换基变量与非基变量，使这种交 换能最大限度地改进目标函数值Z。在任一基本可行解中，基变量始终取正值，而非基变量始终取零。因此，将某非基变量变为基变量首先 要把它的值增至正值。判断是否选择某个非基变量是否应换为基变量的原则是，改变它是否能改进z值，最 直接的办法是通过给非基变量增加1个单位，来判断它是否能改进z值。以非基变量也为例，把*1从。增至1,研究其对目标函数Z的影响。在这里暂不改变22,23的值，仍令它们 为零。这样，(1-9)和(1-10)可以写成xi+X4=50(1-11)9叫+g=400(1-12)当叫增加到1时，为满足(1-11)式，基变量/4的值减少到49,同理，*5的值减少到391。新的可行解为：xi X2 0,13=0)14=49,g 391,新的目标函数值为：Z=4(1)+3(0)+1(0)=4因此，的每增加一个单位，Z值的纯变化为z=Z新值一 Z旧值=4-0=4这个值叫做非基变量血的检验数(也称为相对利润)。其意义在于，每增加1个单位的g将会使Z改进4个单 位。因此，应该尽可能多地增加为1。然而，由于受到两个约束条件的限制，如不可能无限地增加。随着叫的增加，基变量24,力5的值将会减 小，为了得到可行解(所有变量为非负)，必须使这两个变量保持非负。由式(1-11)可见，如果21大于50,24就 变成负值了；同理，由式(1-12)有，当*1大于400/9时，g就成为负值了。因此，由力4,力5的限制，乃不能超 过加加(苧，警)=警。为增加1个单位，Z增加4个单位。叫最大可增至警，目标函数增加4x =曾。也就是说，当为增 加至警时.，基变量窃变为零，成为非基变量。在第二个约束条件中，非基变量血变为基变量。于是，新的基 本可行解为：400 c c 50 cXl=X2=0,73=0,X4=,15=0对变量21做如下消元处理，可等到改进后的新正规方程组：(1)用9除(1-10)式，使的的系数变为1；(2)用-吉乘(1-10)式后加到(1-9)式上，消去力1：5 4 1 50产+产+*4一产=4 5 1 400的十铲2+铲3+铲5=歹上面的过程通过迭代完成了一次基变量与非基变量的互换，约束条件的限制对这种互换产生了重要的作 用一一非基变量值的增大，导致某个基变量的值减小至。变成非基变量。需要注意，在某些约束方程中，某个 非基变量的系数可能为零或负值，当增大此非基变量时，该约束所对应的基变量的值并不会减小(非基变量系 数为0时)，甚至可能增大(非基变量系数为负值时)。此时，该约束条件对非基变量的增大没有限制，该约束条 件对应的基变量也不会成为出基变量。下一步的工作是计算全部非基变量的检验数，以检验上述基本可行解是否最优。如果存在某个非基变量 的检验数为正，那么上面求得的这个基本可行解就是一个可以继续改进的基本可行解，目标函数值Z可以继 续优化。重复以上的过程，直至所有的非基变量的检验数都为非正时，说明当前基本可行解不能进一步改进 To此时得到的基本可行解就是该线性规划问题的最优解。10第一章线性规划最优化的条件在求最大值问题中，如果全部非基变量的检验数为负或为零时，则与之相应的基本可行解为最优解。读 者可以思考一下，在最小值问题中最优化条件是什么？以上就是单纯形法的基本原理，小结一下整个过程：第1步从正规方程组求得初始基本可行解；第2步检验当前基本可行解是否最优。这需要计算所有非基变量的检验数（或相对利 润），即非基变量增加一单位，引起的目标函数的纯变化。如果所有的检验数 都为负数或零，则当前的基本可行解为最优解。第3步 选择一个非基变量作为进基变量，一般选择具有最大（在最大值问题中）检验数 的非基变量，因为它能更显著地改进目标函数Z的值.第4步确定由上一步选择的进基变量替代的基变量（即出基变量）。这一步需要确定非 基变量增加的最大幅度。对非基变量系数为正的约束条件，可由约束条件右 端的常数来比非基变量的正系数。如果有负系数，则视该比值为无穷大。由 于确定的是非基变量增加的最大幅度，因此取比值最小的那个方程中的基变 量作为出基变量。这个法则通常称为最小比值准贝（Min imum ra t io rul e）,第5步 通过高斯-约旦消元，得出新的正规方程组和新的基本可行解，回到第2步。2.表上作业法前面介绍了单纯形法的基本原理，即通过不断的改进基本可行解直至取得最优解。单纯形法的各个步 骤，线性规划问题的约束条件、目标函数都可以用图表形式表示，因此单纯形表便于进行线性规划的运算。此外，通过使用单纯形表运算导出的一些公式，使问题在计算机上运算变得更加方便和有效。下面通过使用单纯形表，把前面描述的运算过程更直观、简洁地描述在表格中。首先介绍一下单纯形表的结构，表1-1是单纯形表的一般形式。表1-1单纯形表的一般形式CJ芍Ab弓其中，c j：变量叼的目标函数系数；Xj：所有决策变量叼；CB：基变量在目标函数中的系数；2由所有基变量；A：约束条件系数矩阵；6：约束条件右端常数；Cj：变量叼的检验数。下面继续使用前面的例1.10来介绍表上作业法，写出标准形式。ma x Z=4x i+312+23s.t.*1+22+23+24=5011运筹学华南理工大学工商管理学院 试用教材9/1+4数+5/3+25=400Xi 0,i=1)2,3,4,5将各项系数填入表中，得表1-2：表1-2CBCi 基变量、43100常数X1肛工3工50%41111050094501400由表1-2可以迅速写出初始基本可行解力4=50,X5=400,Xi=X2=X3=0,向量Cb和当前表常数列的 内积为目标函数值：（50、Z=（0,0）=0+0=0400/这里有必要讨论一下：当前表的常数列就是基变量的取值，而非基变量的值都为0。为什么？在图解法的分析中，已经知道：性质1线性规划问题的可行域如果存在的话，是一个凸集。性质2线性规划问题的最优解如果存在的话，则一定在可行域凸集的顶点上达到。最优化的结果，一定是在可行域的凸集顶点达到。在可行域的凸集顶点上，必然有一部分变量（m-n,巾个变量几个约束条件，也就是几个基变量）的取值为0,这部分变量就是非基变量。因此单纯形法的求解 过程，就是从可行域的一个顶点向更优的顶点移动的过程，最终找到基变量的最优组合和取值。继续求解，为检验上述的基本可行解是否为最优解，需要计算出所有非基变量的检验数。这里介绍一种 比较便捷的计算方法一一内积法。如果用心表示非基变量叼的检验数，巧代表约束条件中叼的系数向量，则有Cj-g-e g与正规方程中叼列系数的内积(1-13)容易证明，这种方法是计算检验数的一种简洁的方法。例如:求无。由于有约束条件的限制，非基变量值的增加会导致基变量值的减少，进而影响到Z值：g每增大1个 单位，24就减少1个单位（对应于基变量24所在行的21的系数），Z值的变化为*4在目标函数中的系数。乘 以24值的变化量，即0X1;同时，为每增大1个单位，费就减少9个单位（对应于基变量方所在行的*1的系 数），Z值的变化为磔在目标函数中的系数。乘以*5值的变化量，即0X1。这样，为每增大1个单位为Z值带来的纯变化就是4-（Ox 1+0 x 9）=4,或者写成：=4一(0,0)(；)=4-(0+0)=4同理，有C2=3-(0,。)(：)=3-(0+0)=3=1-(0+0)=1由于力4,力5为基变量，其检验数必定为0。在原来的表上加下检验数行，就得到初始表（见表1-3）。由于济亍中仍存在某些正值，所以当前基本可行解不为最优。非基变量21使得Z有最大的单位增值，因此 选它作为新的基变量（进基变量），在表1-4中用向上的箭头表示非基变量叫进基。12第一章线性规划表1-3初始单纯形表CbCj 基病、43100常数X1X4工50X411110500工594501400工行检验数43100Z=0为了确定被换出的变量(出基变量)，应用前面提出的最小比值准则。计算每个约束条件的限 制。min毕，弩,第二行有最小比值，对应的基变量为费，因此g应为出基变量，在表1-4中用向右的 箭头表示3出基。表1-4找出进基变量和出基变量Cb43100常数基变量、0%411110500悼45014Q工行检验数43100Z=0的增大警个单位，出减少为零成为非基变量，血，血成为新的基变量。这里要做如下的高斯-约旦消元,可得新的正规方程组。(1)用9除(1-10)式，使乃的系数变为1；(2)用一/乘(1-10)式后加至女1-9)式上，消去*1。下面给出第二张表：表1-5cb勺43100常数X1X40X405/914/91-1/950/9.4修1/,4/95/901/9400/9工行检验数011/9-11/90-4/9Z=1600/9表1-5中新的基本可行解为*1=警，徼=0,*3=0,*4=罟，*5=o,Z=等。为检验此解是否为最 优解，需要计算所有非基变量(数，*3,*5)的检验数，用内积法计算的结果如表1-5中所示。此时只有6的检验 50 400、数为正，因此力2应进基。又由最小比值准则，有min，于,第一行有最小比值，对应的基变量为力4,因 9 9此应由*4出基。经过高斯-约旦消元(过程略)，又得到第三张表：表1-6cbc，基礴、43100常数为%2工3X43014/59/5-1/5104修101/5-4/51/540工行检验数00-11/5-11/5-1/5Z=190经过内积法求检验数，非基变量(*3,*4,*5)的检验数均为负数，说明非基变量值的增大，不可能改进 目标函数值，此时的基本可行解*1=40,X2=10,X3-X4-X5=。为该线性规划问题的最优解，最优值 为 Z=190o13运筹学华南理工大学工商管理学院 试用教材计算步骤小结概括起来，用单纯形法求解最大值问题的计算步骤如图1-3所示:图1-3用单纯形法求解最大值问题的步骤读者对单纯形法的运算过程已经比较熟悉以后，可以把问题直接在表中解出，不需要在纸上列出其它的 步骤。上面的过程就可以在一个表格中完成，如表1-7所示。表1-7CB5 基蛭、43100常数X工2工3X4X50%4111105()0工549 _4501400 工行检验数43100Z=00%40W94/91-1/950/9 a4X1t 4/95/901/9400/9展行检验数01 11/9-11/90-4/9Z=1600/93X2014/59/5-1/5104X101/5-4/51/540工行检验数00-11/5-11/5-1/5Z=190（四）大M法和两阶段法应用单纯形法来解线性规划问题，有一个特别的要求，即必须要有一个初始基本可行解，否则得不到初 始表。在前面所举的问题中，恰好都很容易地取得了初始基本可行解，但是在解决现实问题时，常常没有办 法直接得到初始基本可行解，例如下面这个问题。ma x Z=621+3x 2+4x 3s.t.XX+22+23+74 4 303x i+622+X3 2X4 4 0X2 2414第一章线性规划Xi,X2,X3,2420引入两个松弛变量，一个剩余变量之后，这个问题正规化之后变为ma x Z=6x1+312+4犯s.t.*1+22+23+24+15 W 303%+6+*3 2*4+*6 40X2 *724X1,12,13,X4,X5,16,170直接观察，很难确定应该取哪三个变量作为取得初始基本可行解的基变量。比如，三个约束方程分别 取磔，*6,*7作为基变量，这时要把第三个约束条件两边同乘以-1，这时可以得到的初始基本解为Xl=X2=X3=X4=0,X5=30,XQ=0,=一4但由于如=-412A1X20100-11-21113-20100011工行检验数-10001M-M+Z=2-3X1001/3-2/32/3-5/341120100-11-211130012/3-4/34/3-7/39工行检验数0001/31/3跖1/3A1-2/3Z=-2全部检验数为非负，求解结束，从最终表中，可以读出问题的最优解:xi=4)72=1,X3=9)力4=立5=0,min Z=2注意：如果大河法单纯形最终表中仍有一个或多个人工变量，则原方程没有基本可行解，原问题也没有 可行解。这可以理解为约束条件无法满足，需要重新考虑一下建模是否合理。2.两阶段法这种解法分为两个阶段。第一阶段是构造一个原问题的辅助问题，通过求解这个辅助问题，得出原问题 的一个基本可行解，同时使原问题的约束条件变为正规方程组。第二阶段利用第一阶段得出的基本可行解和 正规方程组进一步计算，得出原问题的最优解。第一阶段：构造辅助问题。构造的方法是将原问题的目标函数变为人工变量之和印，然后求W的最小 值。求解这个问题，如果得出min W=0,则最优解中人工变量的取值都为零（因为人工变量非负），只要 从最优解中去掉人工变量部分，余下部分就是原问题的一个初始基本可行解；若得出min W0,则最优解 中的人工变量至少有一个大于零，说明原问题无解。第二阶段：在第一阶段求得一个基本可行解之后，将第一阶段最终表中的人工变量部分去掉，并将H标 函数的系数换成原问题的目标函数的系数。然后用单纯形法继续求解。例1.12用两阶段法求解例1.11min Z 3c i+12+13S.t.X1 2X2+N3 W 114xi+X2+2/3232xi X3=-1g20,E=1,2,316第一章线性规划同样，首先化为标准形式min Z 3*1+*2+s.t.X1 2X2+*3+*4=11 4X1+22+2*3*5=3-2x-+X3=1Xi O,i=1,2,3,4,5第一阶段：引入人工变量，构造辅助问题。min W=xq+X7S.t.X1 2X2+23+*4=11-421+X2+2*3 *5+*6 3-2xi+X3+*7=1g-0,i 1,2,3,4,5,6,7用单纯形法求解辅助问题，见表1-9,表1-9第一阶段单纯形表Cb0000011常数基通、X2工3X4九5九6对0%41-211000111X6-4120-11031沏-20Hi0001L_c行检验数6-1-30100W=40%43-20100-1101*60川00-11-20-201000112行检验数0-100103W=10X43001-22-51200100-11-210%3-201000112行检验数0000011W=0现在有min印=0,第一阶段辅助问题的最优解为：xi=0,=1,的=1,=12,xs=0,力6=0,X7=0o由于人工变量/6和*7均为零，可得出原问题的一个基本可行解，X!-Q,X2-1,*3=1,X4-12,X5=0,可以进入第二阶段。第二阶段：删去第一阶段最终表中的人工变量26和W所在的列，并将原来的目标函数系数填写入相应的位 置，建立第二阶段的初始单纯形表，见表1-10。在最终表中，己行检验数各数均为非负，即满足