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

1 1一般线性规划问题的数学模型一般线性规划问题的数学模型 2图解法图解法 3单纯形法原理单纯形法原理 4单纯形法的计算步骤单纯形法的计算步骤 5单纯形法的进一步讨论单纯形法的进一步讨论 6改进单纯形法改进单纯形法 7应用举例及应用举例及Matlab求解方法求解方法第一章第一章 线性规划及单纯形法线性规划及单纯形法1 1一般线性规划问题的数学模型一般线性规划问题的数学模型例如图所示，如何截取x使铁皮所围成的容积最大？x xa a一、问题的提出 某企业计划生产某企业计划生产、两种产品。这两种产两种产品。这两种产品都要分别在品都要分别在A、B、C、D四种不同设备上加工。四种不同设备上加工。生产每件产品生产每件产品需占用各设备分别为需占用各设备分别为2、1、4、0h，生产每件产品，生产每件产品，需占用各设备分别为，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品。已知各设备计划期内用于生产这两种产品的能力分别为的能力分别为12、8、16、12h，又知每生产一件，又知每生产一件产品产品企业能获得企业能获得2元利润，每生产一件产品元利润，每生产一件产品企企业能获得业能获得3元利润，问企业应安排生产两种产品各元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。多少件，使总的利润收入为最大。1 1一般线性规划问题的数学模型一般线性规划问题的数学模型产品产品 产品产品计划期内计划期内生产能力生产能力A2212B128C4016D0412利润利润23MAX需满足条件：需满足条件：实现目的：实现目的：二、线性规划问题的数学模型三个组成要素：三个组成要素：1.决策变量决策变量:是决策者为实现规划目标采取是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。的方案、措施，是问题中要确定的未知量。2.目标函数目标函数:指问题要达到的目的要求，表指问题要达到的目的要求，表示为决策变量的函数。示为决策变量的函数。3.约束条件约束条件:指决策变量取值时受到的各种指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式可用资源的限制，表示为含决策变量的等式或不等式。或不等式。一般线性规划问题的数学模型：一般线性规划问题的数学模型：目标函数：目标函数：约束条件：约束条件：简写形式：简写形式：矩阵形式表示为：矩阵形式表示为：其中：其中：三、线性规划问题的标准形式标准形式：标准形式：标准形式特点：标准形式特点：4.决策变量取值非负。决策变量取值非负。1.目标函数为求极大值；目标函数为求极大值；2.约束条件全为等式；约束条件全为等式；3.约束条件右端常数项全为非负值；约束条件右端常数项全为非负值；一般线性规划问题如何化为标准型：一般线性规划问题如何化为标准型：1.目标函数求极小值：目标函数求极小值：令：令：，即化为：，即化为：2.约束条件为不等式：约束条件为不等式：（1）当约束条件为）当约束条件为“”时时如：如：可令：可令：，显然显然（2）当约束条件为）当约束条件为“”时时如：如：可令：可令：，显然显然 称为称为松弛变量。松弛变量。称为称为剩余变量剩余变量。松弛变量和剩余变量统称为松弛变量松弛变量和剩余变量统称为松弛变量（3）目标函数中松弛变量的系数）目标函数中松弛变量的系数 由于松弛变量和剩余变量分别表示未被充分利由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源，都没有转化为价值和利用的资源以及超用的资源，都没有转化为价值和利润，因此润，因此在目标函数中系数为零在目标函数中系数为零。3.取值无约束的变量取值无约束的变量 如果变量如果变量 x 代表某产品当年计划数与上代表某产品当年计划数与上一年计划数之差，显然一年计划数之差，显然 x 的取值可能是正也的取值可能是正也可能是负，这时可令：可能是负，这时可令：其中：其中：令令4.变量变量 xj0，显然，显然例例.将下述线性规划模型化为标准型将下述线性规划模型化为标准型解：解：令令得标准形式为：得标准形式为：求解线性规划问题：求解线性规划问题：就是从满足约束方程组和约束不等式的决策变量取就是从满足约束方程组和约束不等式的决策变量取值中，找出使得目标函数达到最大的值。值中，找出使得目标函数达到最大的值。四、线性规划问题的解 可行解：可行解：满足约束条件的解称为满足约束条件的解称为可行解可行解，可行解的集，可行解的集合称为合称为可行域可行域。最优解：最优解：使目标函数达到最大值的可行解。使目标函数达到最大值的可行解。基基：约束方程组的一个满秩子矩阵称为规划问题的一：约束方程组的一个满秩子矩阵称为规划问题的一个个基基，基中的每一个列向量称为，基中的每一个列向量称为基向量基向量，与基向量对应，与基向量对应的变量称为的变量称为基变量基变量，其他变量称为，其他变量称为非基变量非基变量。基解：基解：在约束方程组中，令所有非基变量为在约束方程组中，令所有非基变量为0，可以，可以解出基变量的唯一解，这组解与非基变量的解出基变量的唯一解，这组解与非基变量的0共同构成共同构成基解基解。基可行解：基可行解：满足变量非负的基解称为满足变量非负的基解称为基可行解基可行解可行基：可行基：对应于基可行解的基称为对应于基可行解的基称为可行基可行基例例4 说明什么是基、基说明什么是基、基 变量、基解、基可变量、基解、基可行解和可行基行解和可行基实现目的：实现目的：为了便于建立为了便于建立 n 维空间中线性规划问题的维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯概念及便于理解求解一般线性规划问题的单纯形法的思路，先介绍图解法。形法的思路，先介绍图解法。求解下述线性规划问题：求解下述线性规划问题：2.2.线性规划问题的图解法线性规划问题的图解法画出线性规划问题的可行域：画出线性规划问题的可行域：目标函数的几何意义：目标函数的几何意义：最优解的确定：最优解的确定：图解法的步骤：图解法的步骤：1.建立坐标系，将约束条件在图上表示；建立坐标系，将约束条件在图上表示；2.确立满足约束条件的解的范围；确立满足约束条件的解的范围；3.绘制出目标函数的图形；绘制出目标函数的图形；4.确定最优解。确定最优解。无穷多最优解的情况：无穷多最优解的情况：目标函数与某个约束条件恰好平行目标函数与某个约束条件恰好平行无界解（或无最优解）的情况：无界解（或无最优解）的情况：可行域上方无界可行域上方无界无可行解的情况：无可行解的情况：约束条件不存在公共范围约束条件不存在公共范围图解法的启示：图解法的启示：1.求解线性规划问题时，解的情况有：唯一最求解线性规划问题时，解的情况有：唯一最优解，无穷多最优解，无界解，无可行解；优解，无穷多最优解，无界解，无可行解；2.若线性规划问题可行域存在，在可行域是一若线性规划问题可行域存在，在可行域是一个凸集；个凸集；3.若线性规划问题最优解存在，在最优解或最若线性规划问题最优解存在，在最优解或最优解之一一定能够在可行域的某个顶点取得；优解之一一定能够在可行域的某个顶点取得；4.解题思路是，先找凸集的任一顶点，计算其解题思路是，先找凸集的任一顶点，计算其目标函数值。比较其相邻顶点函数值，若更目标函数值。比较其相邻顶点函数值，若更优，则逐点转移，直到找到最优解。优，则逐点转移，直到找到最优解。3 3单纯形法原理单纯形法原理凸集：凸集：如果集合如果集合 C 中任意两个点中任意两个点 ，其连线上，其连线上的所有点也都是集合的所有点也都是集合C 中的点。中的点。上图中（上图中（1）（）（2）是凸集，（）是凸集，（3）（）（4）不是凸集）不是凸集顶点：顶点：如果对于凸集如果对于凸集 C 中的点中的点 X，不存在，不存在C 中的任中的任意其它两个不同的点意其它两个不同的点 ，使得，使得 X 在它们的连线上，在它们的连线上，这时称这时称 X 为凸集的顶点。为凸集的顶点。一、线性规划问题基本定理定理一定理一 若线性规划问题存在可行解，则问题的可行若线性规划问题存在可行解，则问题的可行 域是凸集。域是凸集。定理二定理二 线性规划问题的基本可行解线性规划问题的基本可行解 X 对应线性规划对应线性规划 问题可行域（凸集）的顶点。问题可行域（凸集）的顶点。定理三定理三 若线性规划问题有最优解，一定存在一个基若线性规划问题有最优解，一定存在一个基 可行解是最优解。可行解是最优解。从上述三个定理可以看出，要求线性规划问从上述三个定理可以看出，要求线性规划问题的最优解，只要比较可行域（凸集）各个题的最优解，只要比较可行域（凸集）各个顶点对应的目标函数值即可，最大的就是我顶点对应的目标函数值即可，最大的就是我们所要求的最优解。们所要求的最优解。定理定理1 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=1n即 pjxj=b(1)j=1m又 X是非基本可行解，P1,P2,Pm线性相关，即有1P1+2P2+mPm=0，其中1，2，m不全为0，两端同乘0，得1P1+2P2+mPm=0，（2）定理定理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 (00,1-0，当xj=0，必有yj=zj=0 pjyj=j=1n pjyj=b(1)j=1r pjzj=j=1n pjzj=b(2)j=1r (yj-zj)pj=0j=1r,(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 3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。证：证：设 X0=(x10,x20,xn0)T 是线性规划模型的一个最优解，z0=zmax=CX0若X0非基本可行解，即非顶点，只要取充分小，则必能找出X1=X0-0，X2=X0+0，即X1、X2为可行解，单纯形法的计算步骤：初始基本可行解新的基本可行解最优否？STOPYN二、确定初始基可行解线性规划问题的最优解一定会在基可行解中取得，我线性规划问题的最优解一定会在基可行解中取得，我们先找到一个初始基可行解。然后设法转换到另一个们先找到一个初始基可行解。然后设法转换到另一个基可行解，直到找到最优解为止。基可行解，直到找到最优解为止。设给定线性规划问题：设给定线性规划问题：因此约束方程组的系数矩阵为：因此约束方程组的系数矩阵为：由于该矩阵含有一个单位子矩阵，因此，用这个单位由于该矩阵含有一个单位子矩阵，因此，用这个单位阵做基，就可以求出一个基可行解：阵做基，就可以求出一个基可行解：其标准形为：其标准形为：三、从初始基可行解转换为 另一个基可行解 对初始可行解的系数矩阵进行初等行对初始可行解的系数矩阵进行初等行变换，构造出一个新的单位矩阵，其各列变换，构造出一个新的单位矩阵，其各列所对应的变量即为一组新的基变量，求出所对应的变量即为一组新的基变量，求出其数值，就是一个新的基可行解。其数值，就是一个新的基可行解。从一个基本可行解向另一个基本可行解转换从一个基本可行解向另一个基本可行解转换 不失一般性，设基本可行解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=1n pixi0=b(1)i=1m 又P1 P2 Pm为一个基，任意一个非基向量Pj可以以该组向量线性组合表示，即Pj=a1j P1 +a2j P2+amj Pm，即 Pj=aij pi，移项，两端同乘0，有 (Pj-aij pi)=0 (2)i=1mi=1m(1)+(2)：(xi 0-aij)Pi+Pj=b，取充分小，使所有xi 0-aij 0，从而i=1mX1=(x1 0-a1j,x2 0-a2j,xm 0-amj,0,0)T也是可行解。当取 =min aij 0 =，则X1前m个分量至少有一个xL1为0。xi 0aijaLjxL 0i P1,P2,PL-1,PL+1,Pm,Pj 线性无关。X1 也为基本可行解。四、最优性检验和解的判别令令，其中，其中 随基的改变而改变随基的改变而改变X1=(x1 0-a1j,x2 0-a2j,xm 0-amj,0,0)T基本可行解X0=(x10,x20,xm0,0,0)Tz0=cjxj0 =ci xi0 i=1mj=1nz1=cjxj1 =ci(xi 0-aij)+cj i=1mj=1n =cixi 0+(cj-ciaij)=z0+ji=1mmi=1四、最优性检验和解的判别1.当所有当所有 时，现有顶点对应的基可行解即为最时，现有顶点对应的基可行解即为最优解。优解。2.当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 且可以找到且可以找到 ，则该线性规划问题有无穷多最，则该线性规划问题有无穷多最优解。优解。3.如果存在某个如果存在某个 ，又，又 向量所有分量向量所有分量 ，对任意对任意 ，恒有，恒有 ，则存在无界解。，则存在无界解。因因 0，所以有如下结论：，所以有如下结论：z1=z0+j4 4单纯形法的计算步骤单纯形法的计算步骤第一步：求初始可行解，列初始单纯形表1.表中最上端一行是各变量在目标函数中的系数，表中最上端一行是各变量在目标函数中的系数，最左端一列是各基变量在目标函数中的系数值。最左端一列是各基变量在目标函数中的系数值。2.表中最后一行就是检验数表中最后一行就是检验数 。第二步：进行最优性检验 如果表中，所有检验数如果表中，所有检验数 ，则表中，则表中的基可行解就是问题的最优解，计算到此为的基可行解就是问题的最优解，计算到此为止，否则转入下一步。止，否则转入下一步。第三步：转换到新的基可行解，构造新单纯形表1.确定换入变量确定换入变量取使得取使得所对应的所对应的 作为换入基的变量。作为换入基的变量。2.确定换出变量确定换出变量取使得取使得所对应的所对应的 作为换出基的变量。作为换出基的变量。3.用换入变量替换换出变量，做新单纯形表用换入变量替换换出变量，做新单纯形表（1）（2）（3）检验数）检验数 的求法与初始单纯形表中求法相同的求法与初始单纯形表中求法相同第四步：重复第二、三步直到计算结束例例5 用单纯形法求解线性规划问题用单纯形法求解线性规划问题解：解：将原线性规划问题化为标准型将原线性规划问题化为标准型第一步：第一步：取系数矩阵中单位阵部分为基，得初始基可行解取系数矩阵中单位阵部分为基，得初始基可行解列出初始单纯形表列出初始单纯形表第二步：第二步：由于：由于：都大于零，因此，目前没有得都大于零，因此，目前没有得到最优解。到最优解。在大于零的检验数中，由于在大于零的检验数中，由于 ，且，且所以所以 为换入变量。为换入变量。第三步：第三步：由于由于所以确定所以确定 为换出变量为换出变量1.确定换入变量确定换入变量2.确定换出变量确定换出变量3.作新单纯形表作新单纯形表第四步：第四步：由于还存在检验数由于还存在检验数 ，因此重复上述步骤。，因此重复上述步骤。由于上表中所有检验数都小于等于零，因此已经由于上表中所有检验数都小于等于零，因此已经得到最优解，最优解为：得到最优解，最优解为：代入目标函数得最优值：代入目标函数得最优值：当计算检验数有相同值的时候，可从中任选一个变量当计算检验数有相同值的时候，可从中任选一个变量作为换入变量。作为换入变量。当计算当计算 值出现相同时，也可以从中任选一个作为换值出现相同时，也可以从中任选一个作为换出变量出变量注意：注意：5 5单纯形法的进一步讨论单纯形法的进一步讨论一、人工变量法考察上一节例考察上一节例5中的线性规划问题：中的线性规划问题：化标准形为：化标准形为：它的系数矩阵是：它的系数矩阵是：由于由于系数矩阵中存在单位阵系数矩阵中存在单位阵，很容易找到初始可行，很容易找到初始可行基。但存在着不同的情况，考察下面的线性规划问题：基。但存在着不同的情况，考察下面的线性规划问题：化为标准型：化为标准型：例例6该问题的系数矩阵为：该问题的系数矩阵为：这个矩阵中不含有单位矩阵，因此很难找到初始基。这个矩阵中不含有单位矩阵，因此很难找到初始基。对于这种线性规划问题的系数矩阵不含有单位对于这种线性规划问题的系数矩阵不含有单位矩阵的情况，我们往往采用添加矩阵的情况，我们往往采用添加人工变量人工变量 的方法，的方法，来人为构造一个单位矩阵。这样的方法就是来人为构造一个单位矩阵。这样的方法就是人工变人工变量法量法。为了构造出单位矩阵，在系数矩阵中添加两列单位为了构造出单位矩阵，在系数矩阵中添加两列单位列向量，系数矩阵变为：列向量，系数矩阵变为：线性规划问题的约束条件就变为：线性规划问题的约束条件就变为：因为因为 、是人为添加的，因此其对应的变量是人为添加的，因此其对应的变量 、称为称为人工变量人工变量。目标函数中人工变量的系数：目标函数中人工变量的系数：添加人工变量前，在线性规划问题的标准形中，添加人工变量前，在线性规划问题的标准形中，各约束条件已经是等式约束了，因此为了保证等式约各约束条件已经是等式约束了，因此为了保证等式约束满足不变，在最优解中，人工变量的取值必须为束满足不变，在最优解中，人工变量的取值必须为0。为此，令目标函数中人工变量的系数为为此，令目标函数中人工变量的系数为任意大的任意大的一个负值一个负值，用，用“”来表示，这样，只要人工变量来表示，这样，只要人工变量取值不为零，则目标函数就不能达到极大化。取值不为零，则目标函数就不能达到极大化。目标函数变为：目标函数变为：添加添加 M 来处理人工变量的方法，称为大来处理人工变量的方法，称为大M 法法求解过程：求解过程：因此最优解为：因此最优解为：二、两阶段法 用大用大 M 处理人工变量时，用计算机求解会出现处理人工变量时，用计算机求解会出现错误，由此产生了两阶段法。错误，由此产生了两阶段法。第一阶段：先求解一个目标函数中只含有人工第一阶段：先求解一个目标函数中只含有人工变量的线性规划问题。变量的线性规划问题。即令目标函数中其它变量的系数取零，人工变即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取量的系数取某个正的常数（一般取1），在保持原问），在保持原问题约束条件不变的情况下求这个目标函数极小化时题约束条件不变的情况下求这个目标函数极小化时的解。的解。第二阶段：从第一阶段的最终单纯形表出发，第二阶段：从第一阶段的最终单纯形表出发，去掉人工变量，按原问题的目标函数，继续寻找原去掉人工变量，按原问题的目标函数，继续寻找原问题的最优解。问题的最优解。三、关于解的判别1.当所有当所有 时，又对某个非基变量时，又对某个非基变量 有有 且可以找到且可以找到 ，则该线性规划问题有无穷，则该线性规划问题有无穷多最优解。多最优解。例例7.求解线性规划问题求解线性规划问题解：解：在图解法中，我们知道这个问题有无穷多解。在图解法中，我们知道这个问题有无穷多解。它的标准形为：它的标准形为：用单纯形法计算，得到最终单纯形表为：用单纯形法计算，得到最终单纯形表为：从表中可以得到最优解：从表中可以得到最优解：它对应的目标函数值为：它对应的目标函数值为：在上表中，非基变量在上表中，非基变量 的检验数为的检验数为0，如果将，如果将 换入基变量，得：换入基变量，得：从表中可以得到新的最优解：从表中可以得到新的最优解：它对应的目标函数值为：它对应的目标函数值为：因此因此 和和 连线上所有的点都是最优解，该问连线上所有的点都是最优解，该问题有无穷多最优解。题有无穷多最优解。例例8.求解线性规划问题求解线性规划问题解：用图解法求解时知道该问题有无界解，解：用图解法求解时知道该问题有无界解，它的标准形为：它的标准形为：用单纯形表求解过程如下：用单纯形表求解过程如下：表中表中 ，但，但 列数字为零，因此列数字为零，因此 的取值的取值可无限增大，所以目标函数值也可随之无限增大，可无限增大，所以目标函数值也可随之无限增大，说明问题的解无界。说明问题的解无界。例例9.求解线性规划问题求解线性规划问题解：利用图解法，我们已经知道该问题无可行解，解：利用图解法，我们已经知道该问题无可行解，将其化为标准形：将其化为标准形：该问题单纯形法求解如下：该问题单纯形法求解如下：当所有当所有 时，人工变量时，人工变量 仍然留在基变量中，仍然留在基变量中，而且不为零，故问题无可行解。而且不为零，故问题无可行解。四、单纯形法小结1.对给定的线性规划问题应首先化为标准形式；对给定的线性规划问题应首先化为标准形式；2.选取或构造一个单位矩阵作为基；选取或构造一个单位矩阵作为基；3.求出初始可行解并列出初始单纯形表；求出初始可行解并列出初始单纯形表；4.计算检验数，判断是否最优解；计算检验数，判断是否最优解；5.寻找换入及换出变量，构造新的单纯形表；寻找换入及换出变量，构造新的单纯形表；6.求出最优解。求出最优解。6 6改进单纯形法改进单纯形法用矩阵形式描述线性规划的标准形式为：用矩阵形式描述线性规划的标准形式为：由于在转化成标准形时，总可以构造一个单位矩由于在转化成标准形时，总可以构造一个单位矩阵作为初始单纯形表中的基。阵作为初始单纯形表中的基。因此将矩阵因此将矩阵 A 分成作为分成作为初始基的单位矩阵初始基的单位矩阵 I 和和非基变量系数矩阵非基变量系数矩阵 N 两块。两块。把把新单纯形表中的基（新表中的新单纯形表中的基（新表中的 I），对应的），对应的初始单纯形表中的那些向量初始单纯形表中的那些向量抽出来，单独列成一块，抽出来，单独列成一块，用用B 表示。表示。初始单纯形表可以改写为：初始单纯形表可以改写为：单单纯纯形形法法的的迭迭代代计计算算实实际际上上就就是是对对约约束束方方程程系系数数矩矩阵阵实实施施的的初初等等变变换换。对对矩矩阵阵（b|B|N|I）实实施施初初等等变变换换时时，当当 B 变变为为 I，I 将将变变换换为为 B-1。因因此此，上上述述矩矩阵阵变变为为（B-1 b|I|B-1 N|B-1）,新新单单纯纯形形表表可可写写为为：显然：显然：利用这些公式，我们来研究改进单纯形法利用这些公式，我们来研究改进单纯形法改进单纯形法的步骤：改进单纯形法的步骤：1.在下一步迭代的基变量确定后，新基可行解为：在下一步迭代的基变量确定后，新基可行解为：2.计算非基变量的检验数计算非基变量的检验数 和和3.产生产生 列的数字，有列的数字，有 ，如，如 ，线，线性规划问题有无界解，计算结束。否则寻找换出性规划问题有无界解，计算结束。否则寻找换出变量：变量：4.用非基变量用非基变量 替换基变量替换基变量 ，得出下一步中的，得出下一步中的基变量。基变量。5.重复上述步骤，直到计算结束。重复上述步骤，直到计算结束。B-1的求法：的求法：令令将将 D 左乘迭代前的基的逆矩阵左乘迭代前的基的逆矩阵 ，就得到迭，就得到迭代后基的逆矩阵代后基的逆矩阵 。例例10.用改进单纯形法求解用改进单纯形法求解解：其标准形为解：其标准形为因此因此（1）确定初始解）确定初始解找出约束条件中的单位矩阵找出约束条件中的单位矩阵 I 作为基，初始解：作为基，初始解：，非基变量检验数：非基变量检验数：因此因此 是换入变量，是换入变量，且且由于由于因此因此 是换出变量，是换出变量，。且且在基变量中，在基变量中，表示的是第三行。表示的是第三行。（2）第一次迭代）第一次迭代新的基变量：新的基变量：逆矩阵逆矩阵N 中只对应变元中只对应变元 ，因此，因此最大正检验数为最大正检验数为10/3，即，即 为换入变量，又为换入变量，又所以所以 为换出变量。为换出变量。（3）第二次迭代）第二次迭代新的基变量为：新的基变量为：因为所有检验数为零，所以最优解为：因为所有检验数为零，所以最优解为：7.7.应用举例及应用举例及MatlabMatlab求解法求解法例例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 语言中，以矩阵作为基本计算单位，向量语言中，以矩阵作为基本计算单位，向量可以看作是矩阵的特殊情况，用可以看作是矩阵的特殊情况，用“；”表示矩阵的分表示矩阵的分行，用行，用“，”表示两个元素的分隔，用表示两个元素的分隔，用“”表示矩表示矩阵整体。阵整体。利用利用 Matlab 进行线性规划问题求解的命令格式为：进行线性规划问题求解的命令格式为：X=linprog(f,A,b,Aeq,beq,LB,UB,X0)在上述式子中：在上述式子中：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