运筹学线性规划与目标函数.ppt

1,线性规划与目标规划,第1章 线性规划与单纯形法第2章 对偶理论与灵敏度分析第3章 运输问题第4章 目标规划,2,第1章 线性规划与单纯形法,第1节 线性规划问题及其数学模型第2节 线性规划问题的几何意义第3节 单纯形法第4节 单纯形法的计算步骤第5节 单纯形法的进一步讨论第6节 应用举例,3,第1节 线性规划问题及其数学模型,1.1 问题的提出1.2 图解法1.3 线性规划问题的标准形式1.4 线性规划问题的解的概念,4,第1节 线性规划问题及其数学模型,线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。,5,1.1 问题的提出,1.1 问题的提出 例 1 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。,每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?,6,1.1 问题的提出,用数学关系式描述这个问题,7,1.1 问题的提出,得到本问题的数学模型为:,这就是一个最简单的线性规划模型。,8,1.1 问题的提出,例 2 靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。,图1-1,化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。,9,1.1 问题的提出,设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米,建模型之前的分析和计算,x11,0.8x1+x21.6,10,1.1 问题的提出,得到本问题的数学模型为：,11,1.1 问题的提出,每一个线性规划问题都用一组决策变量 表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。,上述两个问题具有的共同特征：,12,1.1 问题的提出,决策变量及各类系数之间的对应关系,13,1.1 问题的提出,线性规划模型的一般形式,14,1.2 图解法,1.2 图解法例1是一个二维线性规划问题，可用作图法直观地进行求解。,15,1.2 图解法,目标值在（4，2）点，达到最大值14,16,1.2 图解法,（1）无穷多最优解(多重最优解)，见图1-4。（2）无界解，见图1-5-1。（3）无可行解，见图1-5-2。,通过图解法，可观察到线性规划的解可能出现的几种情况：,17,1.2 图解法,目标函数 max z=2x1+4x2,图1-4 无穷多最优解（多重最优解）,18,1.2 图解法,图1-5-1 无界解,19,当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例1的数学模型中增加一个约束条件:则该问题的可行域即为空集，即无可行解，,无可行解的情形,1.2 图解法,20,图1-5-2 不存在可行域,1.2 图解法,21,1.3 线性规划问题的标准型式,1.3 线性规划问题的标准型式,22,1.3 线性规划问题的标准型式,用向量形式表示的标准形式线性规划,线性规划问题的几种表示形式,23,1.3 线性规划问题的标准型式,用矩阵形式表示的标准形式线性规划,24,1.3 线性规划问题的标准型式,(1)若要求目标函数实现最小化，即min z=CX，则只需将目标函数最小化变换求目标函数最大化，即令z=z，于是得到max z=CX。(2)约束条件为不等式。分两种情况讨论：若约束条件为“”型不等式，则可在不等式左端加入非负松弛变量，把原“”型不等式变为等式约束；若约束条件为“”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。(3)若存在取值无约束的变量xk,可令,如何将一般线性规划转化为标准形式的线性规划,25,1.3 线性规划问题的标准型式,例3 将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为,26,1.3 线性规划问题的标准型式,例4 将下述线性规划问题化为标准形式线性规划,(1)用x4x5替换x3，其中x4，x50；(2)在第一个约束不等式左端加入松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z=z，将求min z 改为求max z=max(-z)=-(-x1+2x2-3x3)即可得到该问题的标准型。,27,1.3 线性规划问题的标准型式,例4 例4的标准型,28,1.4 线性规划问题的解概念,1.可行解2.基3.基可行解4.可行基,29,1.4 线性规划问题的解的概念,定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。,1.可行解,30,1.4 线性规划问题的解的概念,2.基，基向量，基变量,31,1.4 线性规划问题的解的概念,满足非负条件（1-6）的基解，称为基可行解.基可行解的非零分量的数目不大于m，并且都是非负的。,3 基可行解,32,1.4 线性规划问题的解的概念,对应于基可行解的基，称为可行基。约束方程组(1-5)具有的基解的数目最多是 个，一般基可行解的数目要小于基解的数目。以上提到了几种解的概念，它们之间的关系可用图1-6表明。说明：当基解中的非零分量的个数小于m时，该基解是退化解。在以下讨论时，假设不出现退化的情况。,4 可行基,33,1.4 线性规划问题的解的概念,不同解之间的关系,34,第2节 线性规划问题的几何意义,2.1 基本概念2.2 几个定理,35,2.1 基本概念,凸集凸组合顶点,36,2.1 基本概念,定义设K是n维欧氏空间的一点集，若任意两点X(1)K，X(2)K的连线上的所有点X(1)+(1)X(2)K，(01)，则称K为凸集。,图1-7,1.凸集,37,2.1 基本概念,实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。图1-2中的阴影部分是凸集。任何两个凸集的交集是凸集，见图1-7(d),38,2.1 基本概念,设X(1)，X(2)，X(k)是n维欧氏空间En中的k个点。若存在1，2，k，且0i1,i=1,2,，k 使 X=1X(1)+2X(2)+kX(k)则称X为X(1)，X(2)，X(k)的一个凸组合（当0i1时，称为严格凸组合）。,2.凸组合,39,2.1 基本概念,设K是凸集，XK；若X不能用不同的两点X(1)K和X(2)K的线性组合表示为 X=X(1)+(1)X(2)，(01)则称X为K的一个顶点(或极点)。图中的0，Q1,2,3,4都是顶点。,3.顶点,40,2.2 几个定理,定理1 若线性规划问题存在可行域，则其可行域 是凸集。,41,2.2 几个定理,定理1的证明：只需证明D中任意两点连线上的点必然在D内即可。设 是D内的任意两点；且X(1)X(2)。,42,2.2 几个定理,43,2.2 几个定理,引理 1 线性规划问题的可行解X=(x1,x2,，xn)T为基可行解的充要条件是：X的正分量所对应的系数列向量是线性独立的。,44,2.2 几个定理,定理2 线性规划问题的基可行解X对应于可行域D的顶点。证：不失一般性，假设基可行解X的前m个分量为正。故 现分两步来讨论，分别用反证法。,45,2.2 几个定理,(1)若X不是基可行解，则它一定不是可行域D的顶点。根据引理1，若X不是基可行解，则其正分量所对应的系数列向量P1，P2，Pm线性相关，即存在一组不全为零的数i,i=1,2,m，使得 1P1+2P2+mPm=0(1-9)用一个数0乘(1-9)式再分别与(1-8)式相加和相减，得(x11)P1+(x22)P2+(xm m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b,46,2.2 几个定理,因X 不是可行域D的顶点，故在可行域D中可找到不同的两点 X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使得 X=X(1)+(1)X(2)，01 设X是基可行解，对应的向量组P1Pm线性独立，故当jm时，有xj=xj(1)=xj(2)=0。由于X(1)，X(2)是可行域的两点，因而满足,（2）若X不是可行域D的顶点，则它一定不是基可行解。,将两式相减，得,因X(1)X(2)，所以上式中的系数不全为零，故向量组P1,P2,，Pm线性相关，与假设矛盾，即X不是基可行解。,47,2.2 几个定理,引理2 若K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。本引理的证明从略，用以下例子说明本引理的结论。例5 设X是三角形中任意一点，X(1)，X(2)和X(3)是三角形的三个顶点，试用三个顶点的坐标表示X(见图1-8),图1-8,48,2.2 几个定理,解：任选一顶点X(2)，做一条连线XX(2)，并延长交于X(1)、X(3)连接线上一点X。因为X是X(1)、X(3)连线上一点，故可用X(1)、X(3)线性组合表示为X=X(1)+(1)X(3)01 又因X是X与X(2)连线上的一个点，故X=X+(1)X(2)01 将X的表达式代入上式得到X=X(1)+(1)X(3)+(1)X(2)=X(1)+(1)X(3)+(1)X(2)令 1=,2=(1),3=(1)，得到X=1X(1)+2X(2)+3X(3)ii=1,0i1,49,2.2 几个定理,定理 3 若可行域有界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证：设X(1),X(2)，X(k)是可行域的顶点，若X(0)不是顶点，且目标函数在X(0)处达到最优z*=CX(0)(标准型是z=max z)。因X(0)不是顶点，所以它可以用D的顶点线性表示为 代入目标函数得,50,2.2 几个定理,在所有的顶点中必然能找到某一个顶点X(m)，使CX(m)是所有CX(i)中最大者。并且将X(m)代替(1-10)式中的所有X(i)，得到,由此得到 X(0)CX(m)根据假设CX(0)是最大值，所以只能有 CX(0)=CX(m)即目标函数在顶点X(m)处也达到最大值。,51,2.2 几个定理,有时，目标函数可能在多个顶点处达到最大，这时在这些顶点的凸组合上也达到最大值，这时线性规划问题有无限多个最优解。假设是目标函数达到最大值的顶点，则对这些顶点的凸组合，有,52,2.2 几个定理,设：于是：另外，若可行域为无界，则可能无最优解，也可能有最优解，若有最优解，也必定在某顶点上得到。,53,基本结论,线性规划问题的所有可行解构成的集合是凸集，也可能为无界域，它们有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点。若线性规划问题有最优解，必在某顶点上得到。虽然顶点数目是有限的，若采用“枚举法”找所有基可行解，然后一一比较，最终必然能找到最优解。但当n,m较大时，这种办法是行不通的，所以要继续讨论如何有效寻找最优解的方法。本课程将主要介绍单纯形法。,54,第3节 单纯形法,3.1 举例3.2 初始基可行解的确定3.3 最优性检验与解的判断3.4 基变换3.5 迭代（旋转运算）,55,单纯形法求解线性规划的思路：,一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样，问题就得到了最优解，先举一例来说明。,56,3.1 举例,例6 试以例1来讨论如何用单纯形法求解。解：已知本例的标准型为：,57,3.1 举例,约束条件(1-12)式的系数矩阵为从(1-12)式可看到x3,x4,x5的系数构成的列向量,58,3.1 举例,P3,P4,P5是线性独立的，这些向量构成一个基B。对应于B的变量x3,x4,x5为基变量.,从(1-12)式中可以得到（1-13）,59,3.1 举例,将(1-13)式代入目标函数(1-11)：得到当令非基变量x1=x2=0，便得到z=0。这时得到一个基可行解X(0)X(0)=(0,0,8,16,12)T 本基可行解的经济含义是：工厂没有安排生产产品、，资源都没有被利用，所以工厂的利润为z=0。,60,3.1 举例,从分析目标函数的表达式(1-14)可以看到：非基变量x1,x2(即没有安排生产产品，)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。,61,3.1 举例,如何确定换入、换出变量?一般选择正系数最大的那个非基变量x2为换入变量，将它换到基变量中，同时还要确定基变量中哪一个换出来成为非基变量。可按以下方法来确定换出变量：分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的变量仍然非负，即x3,x4,x50。,62,3.1 举例,如何确定换入、换出变量当x1=0时，由(1-13)式得到,63,3.1 举例,如何确定换入、换出变量当x2取何值时，才能满足非负要求呢？从(1-15)式可看出，只有选择 x2=min(8/2,-,12/4)=3时，才能使(1-15)式成立。因当x2=3时，基变量x5=0，这就决定用x2去替换x5。以上数学描述说明，每生产一件产品，需要用掉的各种资源数为(2，0，4)。由这些资源中的薄弱环节，就确定了产品的产量。这里就是由原材料B的数量确定了产品的产量x2=12/4=3件。,64,3.1 举例,如何确定换入、换出变量为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换，得到,65,3.1 举例,将(1-16)式中x2的系数列向量变换为单位列向量。其运算步骤是：=/4；=-2;=,并将结果仍按原顺序排列有：,高斯消去法,66,3.1 举例,再将(1-17)式代入目标函数(1-11)式得到,67,3.1 举例,从目标函数的表达式(1-18)可看到，非基变量x1的系数是正的，说明目标函数值还可以增大，即X(1)还不是最优解。于是，再用上述方法确定换入、换出变量，继续迭代，得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T 再经过一次迭代，又得到一个基可行解X(3)X(3)=(4,2,0,0,4)T 而这时得到目标函数的表达式是：z=141.5x3 0.125x4(1-19)再检查(1-19)式，可见所有非基变量x3,x4的系数都是负数，这说明若要用剩余资源x3,x4，就必须支付附加费用。所以当x3=x4=0时，即不再利用这些资源时，目标函数达到最大值。所以X(3)是最优解。即当产品生产4件，产品生产2件时，工厂可以得到最大利润。,68,小结,通过上例，可将每步迭代得到的结果与图解法做一对比。例1的线性规划问题是二维的，即有两个变量x1,x2。当加入松弛变量x3,x4,x5后，变换为高维的。这时可以想象，满足所有约束条件的可行域是高维空间中的凸多面体(凸集)。该凸多面体上的顶点，就是基可行解。初始基可行解为 X(0)=(0,0,8,16,12)T，对应于图1-2中的原点(0，0)；X(1)=(0,3,2,16,0)T对应于图中的Q4点(0，3)；X(2)=(2，3，0，8，0)T对应于Q3点(2，3)；最优解X(3)=(4，2，0，0，4)T相当于图中的 Q2点(4，2)。,从初始基可行解X(0)开始迭代，依次得到X(1)，X(2)，X(3)，相当于图中的目标函数平移时，从0点开始，首先碰到Q4，然后碰到Q3，最后达到Q2。,69,3.2 初始基可行解的确定,为了确定初始基可行解，要首先找出初始可行基，其方法如下。(1)直接观察(2)加松弛变量(3)加非负的人工变量,70,3.2 初始基可行解的确定,从线性规划问题的系数构成的列向量Pj(j=1,2,n)中，通过直接观察，找出一个初始可行基,(1)直接观察,71,3.2 初始基可行解的确定,对所有约束条件为“”形式的不等式，利用化标准型的方法，在每个约束条件的左端加上一个松弛变量。经过整理，重新对xj及aij(i=1,2,m;j=1,2,n)进行编号，则可得下列方程组（x1,x2,xm 为松弛变量）：,(2)加松弛变量,72,3.2 初始基可行解的确定,于是，(1-22)中含有一个mm阶单位矩阵，初始可行基B即可取该单位矩阵。将(1-22)式每个等式移项得,73,3.2 初始基可行解的确定,令xm+1=xm+2=xn=0，由(1-23)式可得xi=bi(i=1,2,m)得到一个初始基可行解。又因bi0(在1-3节中已做过规定)，所以得到一个初始基可行解 X=(x1,x2,xm,0，0)T nm个=(b1,b2,bm,0，0)T nm个,74,3.2 初始基可行解的确定,对所有约束条件为“”形式的不等式及等式约束情况，若不存在单位矩阵时，可采用人造基方法。即对不等式约束，减去一个非负的剩余变量，再加上一个非负的人工变量；对于等式约束，再加上一个非负的人工变量这样，总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。,(3)加非负的人工变量,75,3.3 最优性检验与解的判别,由于线性规划问题的求解可能出现唯一最优解、无穷多最优解、无界解和无可行解等四种情况，因此，需要建立解的判别准则。一般情况下，经过迭代后(1-23)式变成,76,3.3 最优性检验与解的判别,将 代入目标函数(1-20)式，整理后得,77,3.3 最优性检验与解的判别,令,78,3.3 最优性检验与解的判别,若 为对应于基B的一个基可行解，且对于一切j=m+1,n，有j0，则X(0)为最优解。称j为检验数。,1.最优解的判别定理,79,3.3 最优性检验与解的判别,若 为一个基可行解，对于一切j=m+1，,n，有j0，又存在某个非基变量的检验数m+k=0，则线性规划问题有无穷多最优解。证:只需将非基变量xm+k换入基变量中，找到一个新基可行解X(1)。因m+k=0，由(1-27)知z=z0，故X(1)也是最优解。由2.2节的定理3可知，X(0)和X(1)连线上所有点都是最优解。,2.无穷多最优解判别定理,80,3.3 最优性检验与解的判别,若 为一基可行解，有一个m+k0，并且对i=1,2,，m，有ai,m+k0，那么该线性规划问题具有无界解(或称无最优解)。证:构造一个新的解 X(1)，它的分量为,3无界解判别定理,81,3.3 最优性检验与解的判别,因，所以对任意的0都是可行解，把x(1)代入目标函数内，得到z=z0+m+k 因m+k0，故当+，则z+，故该问题目标函数无界。,82,3.3 最优性检验与解的判别,其它情形以上讨论都是针对标准型的，即求目标函数极大化时的情况。当要求目标函数极小化时，一种情况是将其化为标准型。如果不化为标准型，只需在上述1，2点中把j0改为j0，第3点中将m+k0改写为m+k0即可。,83,3.4 基变换,若初始基可行解X(0)不是最优解及不能判别无界时，需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)，得到一个新的可行基，称为基变换。为了换基，先要确定换入变量，再确定换出变量，让它们相应的系数列向量进行对换，就得到一个新的基可行解。,84,1.换入变量的确定,由(1-27)式可知，当某些j0时，若xj增大，则目标函数值还可以增大。这时需要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的j0，那么选哪个非基变量作为换入变量呢?为了使目标函数值增加得快，从直观上看应选j0中的较大者，即由 应选择xk为换入变量。,85,2.换出变量的确定,设P1，P2，Pm是一组线性独立的向量组，它们对应的基可行解是X(0)，将它代入约束方程组(1-21)得到,其他的向量Pm+1,Pm+2,Pm+t,Pn都可以用P1，P2，Pm线性表示。若确定非基变量Pm+t为换入变量，必然可以找到一组不全为0的数(i=1,2,m)使得,86,2.换出变量的确定,在(1-29)式两边同乘一个正数，然后将它加到(1-28)式上，得到,87,2.换出变量的确定,88,2.换出变量的确定,89,2.换出变量的确定,新的基可行解为,90,2.换出变量的确定,由此得到由X(0)转换到X(1)的各分量的转换公式,91,2.换出变量的确定,这里 是原基可行解X(0)的分量；是新基可行解X(1)的各分量；,i,m+t是换入向量Pm+t对应原来一组基向量的坐标。现在的问题是，这个新解X(1)的m个非零分量对应的列向量是否独立?事实上，因为X(0)的第一个分量对应于X(1)的相应分量是零，即,92,2.换出变量的确定,成立。又因将(1-32)式减(1-31)式得到,93,2.换出变量的确定,由于上式中至少有l,m+t0，所以上式表明P1，P2，Pm是线性相关，这与假设相矛盾。,由此可见，X(1)的m个非零分量对应的列向量Pj(j=1,2,m,jl)与Pm+t是线性独立的，即经过基变换得到的解是基可行解。实际上，从一个基可行解到另一个基可行解的变换，就是进行一次基变换。从几何意义上讲，就是从可行域的一个顶点转向另一个顶点。,94,3.5 迭代(旋转运算),上述讨论的基可行解的转换方法是用向量方程描述的，在实际计算时不太方便，因此下面介绍系数矩阵法。考虑以下形式的约束方程组,一般线性规划问题的约束方程组中加入松弛变量或人工变量后，很容易得到上述形式,95,3.5 迭代(旋转运算),设x1,x2,xm为基变量，对应的系数矩阵是mm单位阵I，它是可行基。令非基变量xm+1,xm+2,xn为零，即可得到一个基可行解。若它不是最优解，则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时为在迭代过程中可表示为,其中 是经过迭代后对应于 的元素值。,96,3.5 迭代(旋转运算),按规则确定xl为换出变量，xk,xl的系数列向量分别为,97,3.5 迭代(旋转运算),为了使xk与xl进行对换，须把Pk变为单位向量，这可以通过(1-33)式系数矩阵的增广矩阵进行初等变换来实现。,98,3.5 迭代(旋转运算),变换的步骤是：(1)将增广矩阵(1-34)式中的第l行除以al k，得到,(2)将(1-34)式中xk列的各元素，除al k变换为1以外，其他都应变换为零。其他行的变换是将(1-35)式乘以aik(il)后，从(1-34)式的第i行减去，得到新的第i行。,99,3.5 迭代(旋转运算),由此可得到变换后系数矩阵各元素的变换关系式,是变换后的新元素。,100,3.5 迭代(旋转运算),(3)经过初等变换后的新增广矩阵是,101,3.5 迭代(旋转运算),(4)由(1-36)式中可以看到x1,x2,xk,，xm的系数列向量构成mm单位矩阵;它是可行基。当非基变量xm+1,，xl,xn为零时，就得到一个基可行解X(1),在上述系数矩阵的变换中，元素al k称为主元素，它所在列称为主元列，它所在行称为主元行，元素al k位置变换后为1。,102,3.5 迭代(旋转运算),例7 试用上述方法计算例6的两个基变换。解：例6的约束方程组的系数矩阵写成增广矩阵,当以x3,x4,x5为基变量，x1,x2为非基变量，令x1,x2=0，可得到一个基可行解X(0)=(0,0,8,16,12)T,103,3.5 迭代(旋转运算),现用x2去替换x5，于是将x3,x4,x2的系数矩阵变换为单位矩阵，经变换后为,令非基变量x1,x5=0，得到新的基可行解X(1)=(0,3,2,16,0)T,104,第4节 单纯型法的计算步骤,4.1 单纯型表4.2 计算步骤,105,4.1 单纯型表,为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似。将(1-22)式与目标函数组成n+1个变量，m+1个方程的方程组。,106,线性规划的方程组,107,线性规划的方程组,为了便于迭代运算，可将上述方程组写成增广矩阵形式,108,线性规划的方程组,若将z看作不参与基变换的基变量，它与x1,x2,xm的系数构成一个基，这时可采用行初等变换将c1,c2,cm变换为零，使其对应的系数矩阵为单位矩阵。得到,表1-2,109,线性规划的方程组,表1-2的说明XB列中填入基变量，这里是x1，x2,，xm；CB列中填入基变量的价值系数，这里是c1,c2,cm；它们是与基变量相对应的；b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1,c2,cn；i列的数字是在确定换入变量后，按规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是,110,4.2 计算步骤,表1-2称为初始单纯形表，每迭代一步构造一个新单纯形表。计算步骤：(1)按数学模型确定初始可行基和初始基可行解，建立初始单纯形表。(2)计算各非基变量xj的检验数，检查检验数，若所有检验数 则已得到最优解，可停止计算。否则转入下一步。,111,4.2 计算步骤,(3)在j0,j=m+1,n中，若有某个k对应xk的系数列向量Pk0，则此问题是无界，停止计算。否则，转入下一步。(4)根据max(j0)=k，确定xk为换入变量，按规则计算,112,4.2 计算步骤,(5)以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)，把xk所对应的列向量 将XB列中的xl换为xk，得到新的单纯形表。重复(2)(5)，直到终止。,113,4.2 计算步骤,现用例1的标准型来说明上述计算步骤(1)取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为基。这就得到初始基可行解X(0)=(0,0,8,16,12)T将有关数字填入表中，得到初始单纯形表，见表1-3。表中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零。,114,4.2 计算步骤,表 1-3,115,4.2 计算步骤,计算非基变量的检验数 各非基变量的检验数为1=c1z1=2(01+04+00)=22=c2z2=3(02+00+04)=3 填入表1-3的底行对应非基变量处。,116,4.2 计算步骤,它所在行对应的x5为换出变量，x2所在列和x5所在行的交叉处 4称为主元素或枢元素(pivot element),117,4.2 计算步骤,(4)以4为主元素进行旋转运算或迭代运算，即初等行变换，使P2变换为(0,0,1)T,在XB 列中将x2 替换x5,于是得到新表1-4.,换人变量,换出变量,主元素,118,4.2 计算步骤,(5)检查表1-4的所有cjzj,这时有c1z1=2；说明x1应为换入变量。重复(2)(4)的计算步骤，得表1-5。,换人变量,换出变量,主元素,因为还存在检验数0，继续进行迭代。,119,4.2 计算步骤,(6)表1-6最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大，于是得到最优解,X*=X(3)=(4,2,0,0,4)T 目标函数的最大值 z*=14,120,第5节 单纯形法的进一步讨论,5.1 人工变量法5.2 退化5.3 检验数的几种表示形式,121,5.1 人工变量法,设线性规划问题的约束条件其中没有可作为初始基的单位矩阵，则分别给每一个约束方程加入人工变量xn+1,xn+m，得到,122,5.1 人工变量法,以xn+1,，xn+m为基变量，并可得到一个mm单位矩阵。令非基变量x1,xn为零，便可得到一个初始基可行解X(0)=(0,0,0,b1,b2,bm)T因为人工变量是后加入到原约束条件中的虚拟变量，要求经过基的变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量，这表示原问题有解。若在最终表中当所有cjzj0，而在其中还有某个非零人工变量，这表示原问题无可行解。以下讨论如何解含有人工变量的线性规划问题。,123,5.1 人工变量法,例8 现有线性规划问题，试用大M法求解。,1.大M法,124,5.1 人工变量法,解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到,这里M是一个任意大的正数。,125,5.1 人工变量法,因本例的目标函数是要求min，所以用所有cjzj0来判别目标函数是否实现了最小化.用单纯形法进行计算时，见表1-6。,126,5.1 人工变量法,在表1-6的最终计算结果可看出，已得到最优解：x1=4,x2=1,x3=9，x4=x5=x6=x7=0；目标函数z=2,127,5.1 人工变量法,以下介绍求解含有人工变量线性规划问题的两阶段法。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。,2.两阶段法,128,5.1 人工变量法,第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和要求实现最小化。如,129,5.1 人工变量法,第一阶段求解用单纯形法求解上述模型。若得到的最有值w=0，说明原问题存在基可行解，可以进行第二段计算。否则原，问题无可行解，应停止计算。第二阶段求解从第一阶段计算得到的最终表中除去人工变量，将目标函数行的系数，换为原问题的目标函数系数，作为第二阶段计算的初始表。各阶段的计算方法及步骤与第3节介绍的单纯形法相同。,130,5.1 人工变量法,例9 试用两阶段法求解如下线性规划问题：,131,5.1 人工变量法,解:先在上述线性规划问题的约束方程中加入人工变量，给出第一阶段的数学模型为：,132,5.1 人工变量法,第一阶段用单纯形法求解，见表1-7。求得的结果是w=0，最优解是x1=0,x2=1,x3=1,x4=12,x5=x6=x7=0因为人工变量x6=x7=0，所以(0，1，1，12，0)T是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消，填入原问题的目标函数系数，进行第二阶段计算，见表1-8。,133,5.1 人工变量法,表 1-7,134,5.1 人工变量法,表 1-8,从表1-8得到最优解：x1=4,x2=1,x3=9,目标函数值 z=2,135,5.2 退化,在单纯形法计算中用规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现了退化解。这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，又返回到B1，即出现计算过程的循环，便永远达不到最优解。,136,5.2 退化,尽管实际计算过程中循环现象极少出现，但还是有可能发生的。如何解决这问题?先后有人提出了“摄动法”，“字典序法”。1974年由勃兰特(Bland)提出一种简便的规则，简称勃兰特规则：(1)选取cjzj0中下标最小的非基变量xk为换入变量，即k=min(j cjzj0)(2)当按规则计算存在两个和两个以上最小比值时，选取下标最小的基变量为换出变量。按勃兰特规则计算时，一定能避免出现循环。,137,5.3 检验数的几种表示形式,本书以max z=CX；AX=b，X0为标准型，以cjzj0，（j=1,2,n）作为最优解的判别准则。由于还有其他形式的问题，为了避免混淆，将有关情况归纳如下：设x1,x2,xm为约束方程的基变量，于是可得,138,5.3 检验数的几种表示形式,将它们代入目标函数后，可有两种表达形式,139,判别准则的选择,当要求目标函数实现最大化时，若用(1-37)式来分析，就需要用cjzj0,（j=1,2，,n）作为判别准则；若用(1-38)式来分析，就需要用zjcj0,（j=1,2,n）作为判别准则。当要求目标函数实现最小化时，可用(1-37)式或(1-38)式来分析，这时可分别用cjzj0或zjcj0，（j=1,2,n）来判别目标函数是否已达到最小。,140,几种判别准则的汇总,141,5.4 单纯形法小结,(1)根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表1-10。分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表。,表1-10,142,第6节应用举例,一般讲，一个经济、管理问题凡满足以下条件时，才能建立线性规划模型。(1)要求解问题的目标函数能用数值指标来表示，且为线性函数；(2)存在着多种方案及有关数据；(3)要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。,143,第6节应用举例,例10 合理利用线材问题。现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。解：最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。见表1-11。,表1-11,144,第6节应用举例,为了得到100套钢架，需要混合使用各种下料方案。设按方案下料的原材料根数为x1,方案为x2，方案为x3，方案为x4,方案为x5。根据表1-11的方案，可列出以下数学模型：,145,第6节应用举例,在以上约束条件中加入人工变量x6,x7,x8；然后用表1-12进行计算。,表1-12,146,第6节应用举例,第1次计算,147,第6节应用举例,第2次计算,148,第6节应用举例,最终计算表（第3次计算）,由计算得到最优下料方案是：按方案下料30根；方案下料10根；方案下料50根。即需90根原材料可以制造100套钢架。有非基变量的检验数为零，所以存在多重最优解。,149,第6节应用举例,例11（配料问题）某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1-13和表1-14。该厂应如何安排生产，使利润收入为最大?解：如以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推。,表1-13,150,第6节应用举例,根据表1-13有：,这里 AC+AP+AH=A；BC+BP+BH=B(1-40)将(1-40)逐个代入(1-39)并整理得到,151,第6节应用举例,表1-14表明这些原材料供应数量的限额。加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg。,表1-14,152,第6节应用举例,由此得约束条件,AC+BC+DC100AP+BP+DP100AH+BH+DH60在约束条件中共有9个变量，为计算和叙述方便，分别用x1,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.,