运筹学基础及应用第五版胡运权第一章.ppt

1一般线性规划问题的数学模型,2图解法,3单纯形法原理,4单纯形法的计算步骤,5单纯形法的进一步讨论,6改进单纯形法,7应用举例及Matlab求解方法,第一章 线性规划及单纯形法,1一般线性规划问题的数学模型,例如图所示，如何截取x使铁皮所围成的容积最大？,一、问题的提出,某企业计划生产、两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品需占用各设备分别为2、1、4、0h，生产每件产品，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品企业能获得2元利润，每生产一件产品企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。,1一般线性规划问题的数学模型,需满足条件：,实现目的：,二、线性规划问题的数学模型,三个组成要素：,1.决策变量:是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。,2.目标函数:指问题要达到的目的要求，表示为决策变量的函数。,3.约束条件:指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。,一般线性规划问题的数学模型：,目标函数：,约束条件：,简写形式：,矩阵形式表示为：,其中：,三、线性规划问题的标准形式,标准形式：,标准形式特点：,4.决策变量取值非负。,1.目标函数为求极大值；,2.约束条件全为等式；,约束条件右端常数项全为非负值；,一般线性规划问题如何化为标准型：,1.目标函数求极小值：,令：，即化为：,2.约束条件为不等式：,（1）当约束条件为“”时,如：,可令：，显然,（2）当约束条件为“”时,如：,可令：，显然,称为松弛变量。,称为剩余变量。,松弛变量和剩余变量统称为松弛变量,（3）目标函数中松弛变量的系数,由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利润，因此在目标函数中系数为零。,3.取值无约束的变量,如果变量 x 代表某产品当年计划数与上一年计划数之差，显然 x 的取值可能是正也可能是负，这时可令：,其中：,例.将下述线性规划模型化为标准型,解：令,得标准形式为：,求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。,四、线性规划问题的解,可行解：满足约束条件的解称为可行解，可行解的集合称为可行域。,最优解：使目标函数达到最大值的可行解。,基：约束方程组的一个满秩子矩阵称为规划问题的一个基，基中的每一个列向量称为基向量，与基向量对应的变量称为基变量，其他变量称为非基变量。,基解：在约束方程组中，令所有非基变量为0，可以解出基变量的唯一解，这组解与非基变量的0共同构成基解。,基可行解：满足变量非负的基解称为基可行解,可行基：对应于基可行解的基称为可行基,例4 说明什么是基、基 变量、基解、基可行解和可行基,实现目的：,为了便于建立 n 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。,求解下述线性规划问题：,2.线性规划问题的图解法,画出线性规划问题的可行域：,目标函数的几何意义：,最优解的确定：,图解法的步骤：,建立坐标系，将约束条件在图上表示；确立满足约束条件的解的范围；绘制出目标函数的图形；确定最优解。,无穷多最优解的情况：,目标函数与某个约束条件恰好平行,无界解（或无最优解）的情况：,可行域上方无界,无可行解的情况：,约束条件不存在公共范围,图解法的启示：,求解线性规划问题时，解的情况有：唯一最优解，无穷多最优解，无界解，无可行解；若线性规划问题可行域存在，在可行域是一个凸集；若线性规划问题最优解存在，在最优解或最优解之一一定能够在可行域的某个顶点取得；解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。,3单纯形法原理,凸集：如果集合 C 中任意两个点，其连线上的所有点也都是集合C 中的点。,上图中（1）（2）是凸集，（3）（4）不是凸集,顶点：如果对于凸集 C 中的点 X，不存在C 中的任意其它两个不同的点，使得 X 在它们的连线上，这时称 X 为凸集的顶点。,一、线性规划问题基本定理,定理一 若线性规划问题存在可行解，则问题的可行 域是凸集。,定理二 线性规划问题的基本可行解 X 对应线性规划 问题可行域（凸集）的顶点。,定理三 若线性规划问题有最优解，一定存在一个基 可行解是最优解。,从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我们所要求的最优解。,定理1：若LP模型存在可行解，则可行域为凸集。,证明：设 max z=CX st.AX=b X0,并设其可行域为C，若X1、X2为其可行解，且X1X2，则 X1C，X2 C，即AX1=b，AX2=b，X10，X20，,又 X为X1、X2连线上一点，即 X=X1+(1-)X2，(01)，AX=AX1+(1-)AX2=b+(1-)b=b,(01)，且 X 0，X C，C为凸集。,三个基本定理：,引理：线性规划问题的可行解X=(x1,x2,xn)T 为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。,证：（1）必要性：X基本可行解X的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T，若X为基本可行解，显然，由基本可行解定义可知x1,x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。,（2）充分性：X的正分量所对应的系数列向量线性独立 X为基本可行解若A的秩为m，则X的正分量的个数km；当k=m时，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基，X为基本可行解。当km时，则必定可再找出m-k个列向量与P1,P2,Pk一起构成基，X为基本可行解。,证：等价于 X非基本可行解X非凸集顶点（1）必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,xm,0,0,0)T，为非基本可行解，X为可行解，,pjxj=b，,j=1,n,即 pjxj=b(1),j=1,m,又 X是非基本可行解，P1,P2,Pm线性相关，即有1P1+2P2+mPm=0，其中1，2，m不全为0，两端同乘0，得1P1+2P2+mPm=0，（2）,定理2：线性规划模型的基本可行解对应其可行域的顶点。,由(1)+(2)得(x1+1)P1+(x2+2)P2+(xm+m)Pm=b由(1)-(2)得(x1-1)P1+(x2-2)P2+(xm-m)Pm=b,令X1=(x1+1，x2+2，xm+m，0，0)T X2=(x1-1，x2-2，xm-m，0，0)T取充分小,使得 xj j0，则 X1、X2均为可行解，但 X=0.5X1+(1-0.5)X2，X是X1、X2连线上的点，X非凸集顶点。,（2）充分性：X非凸集顶点 X非基本可行解,设X=(x1,x2,xr,0,0,0)T为非凸集顶点，则必存在Y、Z两点，使得,X=Y+(1-)Z，(01)，且Y、Z为可行解或者 xj=yj+(1-)zj(01)，（j=1,2,n)，yj0，zj0,0,1-0，当xj=0，必有yj=zj=0,pjyj=,j=1,n,pjyj=b(1),j=1,r,pjzj=,j=1,n,pjzj=b(2),j=1,r,(yj-zj)pj=0,j=1,r,(1)-(2),得,即,(y1-z1)P1+(y2-z2)P2+(yr-zr)Pr=0,Y、Z为不同两点，yj-zj不全为0，P1,P2,Pr线性相关，X非基本可行解。,z1=CX1=CX0-C=zmax-C，z2=CX2=CX0+C=zmax+C z0=zmax z1，z0=zmax z2，z1=z2=z0，即 X1、X2也为最优解，若X1、X2仍不是顶点，可如此递推，直至找出一个顶点为最优解。从而，必然会找到一个基本可行解为最优解。,定理3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。,证：设 X0=(x10,x20,xn0)T 是线性规划模型的一个最优解，z0=zmax=CX0若X0非基本可行解，即非顶点，只要取充分小，则必能找出X1=X0-0，X2=X0+0，即X1、X2为可行解，,单纯形法的计算步骤：,初始基本可行解,新的基本可行解,最优否？,STOP,Y,N,二、确定初始基可行解,线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个基可行解，直到找到最优解为止。,设给定线性规划问题：,因此约束方程组的系数矩阵为：,由于该矩阵含有一个单位子矩阵，因此，用这个单位阵做基，就可以求出一个基可行解：,其标准形为：,三、从初始基可行解转换为 另一个基可行解,对初始可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。,从一个基本可行解向另一个基本可行解转换,不失一般性，设基本可行解X0=(x10,x20,xm0,0,0)T，前m个分量为正值，秩为m，其系数矩阵为,P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm,pjxj0=,j=1,n,pixi0=b(1),i=1,m,又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即Pj=a1j P1+a2j P2+amj Pm，即 Pj=aij pi，移项，两端同乘0，有(Pj-aij pi)=0(2),i=1,m,i=1,m,(1)+(2)：(xi 0-aij)Pi+Pj=b，取充分小，使所有xi 0-aij 0，从而,i=1,m,X1=(x1 0-a1j,x2 0-a2j,xm 0-amj,0,0)T,也是可行解。,当取=min aij 0=，则X1前m个分量至少有一个xL1为0。,xi 0,aij,aLj,xL 0,i,P1,P2,PL-1,PL+1,Pm,Pj 线性无关。,X1 也为基本可行解。,四、最优性检验和解的判别,四、最优性检验和解的判别,当所有 时，现有顶点对应的基可行解即为最优解。当所有 时，又对某个非基变量 有 且可以找到，则该线性规划问题有无穷多最优解。3.如果存在某个，又 向量所有分量，对任意，恒有，则存在无界解。,因0，所以有如下结论：,z1=z0+j,4单纯形法的计算步骤,第一步：求初始可行解，列初始单纯形表,表中最上端一行是各变量在目标函数中的系数，最左端一列是各基变量在目标函数中的系数值。2.表中最后一行就是检验数。,第二步：进行最优性检验,如果表中，所有检验数，则表中的基可行解就是问题的最优解，计算到此为止，否则转入下一步。,第三步：转换到新的基可行解，构造新单纯形表,1.确定换入变量,2.确定换出变量,3.用换入变量替换换出变量，做新单纯形表,（1）,（2）,（3）检验数 的求法与初始单纯形表中求法相同,第四步：重复第二、三步直到计算结束,例5 用单纯形法求解线性规划问题,解：将原线性规划问题化为标准型,第一步：取系数矩阵中单位阵部分为基，得初始基可行解,列出初始单纯形表,第三步：,1.确定换入变量,2.确定换出变量,3.作新单纯形表,第四步：由于还存在检验数，因此重复上述步骤。,由于上表中所有检验数都小于等于零，因此已经得到最优解，最优解为：,代入目标函数得最优值：,当计算检验数有相同值的时候，可从中任选一个变量作为换入变量。,当计算 值出现相同时，也可以从中任选一个作为换出变量,注意：,5单纯形法的进一步讨论,一、人工变量法,考察上一节例5中的线性规划问题：,化标准形为：,它的系数矩阵是：,由于系数矩阵中存在单位阵，很容易找到初始可行基。但存在着不同的情况，考察下面的线性规划问题：,化为标准型：,例6,该问题的系数矩阵为：,这个矩阵中不含有单位矩阵，因此很难找到初始基。,对于这种线性规划问题的系数矩阵不含有单位矩阵的情况，我们往往采用添加人工变量 的方法，来人为构造一个单位矩阵。这样的方法就是人工变量法。,为了构造出单位矩阵，在系数矩阵中添加两列单位列向量，系数矩阵变为：,线性规划问题的约束条件就变为：,因为、是人为添加的，因此其对应的变量、称为人工变量。,目标函数中人工变量的系数：,添加人工变量前，在线性规划问题的标准形中，各约束条件已经是等式约束了，因此为了保证等式约束满足不变，在最优解中，人工变量的取值必须为0。为此，令目标函数中人工变量的系数为任意大的一个负值，用“”来表示，这样，只要人工变量取值不为零，则目标函数就不能达到极大化。,目标函数变为：,添加 M 来处理人工变量的方法，称为大M 法,求解过程：,因此最优解为：,二、两阶段法,用大 M 处理人工变量时，用计算机求解会出现错误，由此产生了两阶段法。,第一阶段：先求解一个目标函数中只含有人工变量的线性规划问题。,即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。,第二阶段：从第一阶段的最终单纯形表出发，去掉人工变量，按原问题的目标函数，继续寻找原问题的最优解。,三、关于解的判别,当所有 时，又对某个非基变量 有 且可以找到，则该线性规划问题有无穷多最优解。,例7.求解线性规划问题,解：在图解法中，我们知道这个问题有无穷多解。,它的标准形为：,用单纯形法计算，得到最终单纯形表为：,从表中可以得到最优解：,它对应的目标函数值为：,在上表中，非基变量 的检验数为0，如果将 换入基变量，得：,因此 和 连线上所有的点都是最优解，该问题有无穷多最优解。,例8.求解线性规划问题,解：用图解法求解时知道该问题有无界解，,它的标准形为：,用单纯形表求解过程如下：,表中，但 列数字为零，因此 的取值可无限增大，所以目标函数值也可随之无限增大，说明问题的解无界。,例9.求解线性规划问题,解：利用图解法，我们已经知道该问题无可行解，,将其化为标准形：,该问题单纯形法求解如下：,当所有 时，人工变量 仍然留在基变量中，而且不为零，故问题无可行解。,四、单纯形法小结,对给定的线性规划问题应首先化为标准形式；选取或构造一个单位矩阵作为基；求出初始可行解并列出初始单纯形表；计算检验数，判断是否最优解；寻找换入及换出变量，构造新的单纯形表；求出最优解。,6改进单纯形法,用矩阵形式描述线性规划的标准形式为：,由于在转化成标准形时，总可以构造一个单位矩阵作为初始单纯形表中的基。,因此将矩阵 A 分成作为初始基的单位矩阵 I 和非基变量系数矩阵 N 两块。,把新单纯形表中的基（新表中的 I），对应的初始单纯形表中的那些向量抽出来，单独列成一块，用B 表示。,初始单纯形表可以改写为：,单纯形法的迭代计算实际上就是对约束方程系数矩阵实施的初等变换。对矩阵（b|B|N|I）实施初等变换时，当 B 变为 I，I 将变换为 B-1。因此，上述矩阵变为（B-1 b|I|B-1 N|B-1）,新单纯形表可写为：,显然：,利用这些公式，我们来研究改进单纯形法,改进单纯形法的步骤：,在下一步迭代的基变量确定后，新基可行解为：计算非基变量的检验数 和产生 列的数字，有，如，线性规划问题有无界解，计算结束。否则寻找换出变量：用非基变量 替换基变量，得出下一步中的基变量。重复上述步骤，直到计算结束。,B-1的求法：,令,将 D 左乘迭代前的基的逆矩阵，就得到迭代后基的逆矩阵。,例10.用改进单纯形法求解,解：其标准形为,因此,（1）确定初始解,非基变量检验数：,因此 是换入变量，且,（2）第一次迭代,新的基变量：,逆矩阵,N 中只对应变元，因此,最大正检验数为10/3，即 为换入变量，又,所以 为换出变量。,（3）第二次迭代,新的基变量为：,因为所有检验数为零，所以最优解为：,7.应用举例及Matlab求解法,例11.工业原料的合理利用,要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原料长7.4m，应如何切割，使用原料最节省（扔掉的料头最小）。,考察如下方案的综合使用：,解：该问题的线性规划数学模型如下,该问题要用单纯形法求解，需要添加人工变量：,利用大 M 法求解，得到：,例12.混合配料问题,某糖果厂用原料A、B、C 加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C 含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划数学模型。,解：用 i=1,2,3 分别代表原料A、B、C，用 j=1,2,3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种糖果使用的第 i 种原料的质量，则问题的数学模型可归结为：,目标函数,约束条件为,例13.投资项目的组合问题,兴安公司有一笔 30 万元的资金，考虑今后三年内用于下列项目的投资：1.三年内的每年年初均可投入，每年获利为投资额的 20%，其本利可一起用于下一年的投资；2.只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内；3.允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内；4.允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内；试为该公司确定一个使第三年末本利总和为最大的投资组合方案。,解：用 xij 表示第 i 年初投放到 j 项目的资金数，则可投资的变量表如下,由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为：,第一年初投资总额为30万，因此有：,第二年初的投资额与第一年末收回的本利总额相同：,第三年初投资额与第二年末收回的本利总额相同：,再考虑各项目的投资限额，得到该问题的线性规划模型如下：,下面我们考虑如何用 Matlab 语言来求解线性规划问题,在 Matlab 语言中，标准输入形式要求目标函数为极小，约束条件为等于或小于等于，并使用矩阵或列向量的形式给出，其标准形为：,上述线性规划问题改写：,在 Matlab 语言中，以矩阵作为基本计算单位，向量可以看作是矩阵的特殊情况，用“；”表示矩阵的分行，用“，”表示两个元素的分隔，用“”表示矩阵整体。,在上述式子中：f 是目标函数中的系数向量；Aeq(A)为约束方程组（不等式组）的系数矩阵；beq(b)为约束方程组（不等式组）的右端列向量；LB 为决策向量 X 的下限；UB 为决策向量 X 的上限；X0 为决策向量 X 的初值；,各参量在 Matlab 命令中使用的名称可以根据需要而不同，但是出现的顺序不能发生改变。,1 1 0 0 0 0;-1.2 0 1 1 0 0;0-1.5-1.2 0 1 1;,决策向量的上限、下限和初值我们可以根据实际情况自己进行估计，在该问题中，我们可以设上限为每种方案最多使用50W，最少使用0，初值可以设为全都取0。,f=0;0;0;-1.6;-1.2;-1.4;Aeq=1 1 0 0 0 0;-1.2 0 1 1 0 0;0-1.5-1.2 0 1 1;beq=300000;0;0;A=0 1 0 0 0 0;0 0 0 1 0 0;0 0 0 0 0 1;b=150000;200000;100000;LB=zeros(6,1);UB=500000*ones(6,1);X0=zeros(6,1);x,fval=linprog(f,A,b,Aeq,beq,LB,UB,X0),x=1.0e+05*1.6667 1.3333 0.0000 2.0000 1.0000 1.0000fval=-5.8000e+05,