Chapter 1 线性规划及其单纯形法课件

第一章线性规划及单纯形法§1-1线性规划问题及其数学模型§1-2图解法§1-3单纯形法原理§1-4单纯形法计算步骤§1-5单纯形法的进一步讨论1/14/20231引言线性规划是运筹学的重要分支，也是运筹学中最基本的内容。早在1939年，前苏联著名数学家康特洛维奇研究了运输和下料等问题，编著了《生产组织和计划中的数学方法》一书，为线性规划的研究奠定了基础。1947年Dantgig提出了一般线性规划的算法——单纯形法。尔后Kuhn提出了线性规划的对偶理论，使线性规划的理论和方法日趋完善成熟。随着电子计算机的产生与发展，线性规划在工业、农业、商业、交通运输业、建筑业、军事等行业的计划和管理及决策分析中得到了广泛与深入的应用，取得了良好的效果。目前，线性规划正以它具有理论成熟，计算简单精确，适应性强，应用面广的特点引起了工程技术人员、管理人员和经济学者的重视。它已成为重要的优化技术和手段。1/14/20232一、线性规划问题的数学模型在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优，这就是规划方法。例1美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间、调试工序每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电产品各多少件，使获取的利润为最大？§1-1线性规划问题及其数学模型返回第一章目录1/14/20233§1-1线性规划问题及其数学模型用数学语言来描述这个问题。假设美佳公司每天制造Ⅰ、Ⅱ两种家电产品的数量分别是x1和x2件。max约束条件目标函数Z＝2x1＋x25x2≤156x1＋2x2≤24x1＋x2≤5x1，x2≥0这就是例1的数学模型1/14/20234《运筹学基础及应用》第一章例2【例2】某企业计划生产I、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。按工艺资料规定，生产每件产品I需占用各设备分别为2、1、4、0小时，生产每件产品B，需占用各设备分别为2、2、0、4小时。已知设备计划期内用于生产这两种产品的能力分别为12、8、16、12小时，又知每生产一件产品I企业能获得2元利润、每生产一件产品Ⅱ企业能获得3元利润，问该企业应安排生产两种产品各多少件，使总的利润收入为最大？1/14/20235产品资源产品Ⅰ产品Ⅱ生产能力（h）设备A（h）2212设备B（h）128设备B（h）4016设备B（h）0412利润（元/件）23假设：计划期内生产产品Ⅰx1件，产品Ⅱx2件。1/14/20236例2捷运公司拟在下一年度的1～4月份的4个月内租用仓库堆放物资。已知各月份所需仓库面积数。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字如表1-2所示。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此，该厂可根据需要，在任何一个月初办理租借合同。每次办理可签一份，也可签若干份租用面积和租借期限不同的合同，试确定该公司签定租借合同的最优决策，目的是使所付租借费用最小。1/14/20237假设用xij表示捷运公司第i（i＝1，2，…，4）个月月初签订租借期为j（j＝1，2，…，4）个月的仓库面积数(单位为100m2）。则minz＝2800(x11+x21+x31+x41)+4500(x12+x22+x32)+6000(x13+x23)+7300x14 x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 xij≥0(i＝1，2，…，4；j＝1，2，…，4）租借期为一个月的仓库面积租借期为二个月的仓库面积租借期为三个月的仓库面积租借期为四个月的仓库面积一月份拥有的租借面积二月份拥有的租借面积三月份拥有的租借面积四月份拥有的租借面积一月份仓库需求面积约束二月份仓库需求面积约束三月份仓库需求面积约束四月份仓库需求面积约束非负约束1/14/20238组成线性规划模型的三个要素maxZ＝2x1＋x2 5x2≤15 6x1＋2x2≤24 x1＋x2≤5 x1，x2≥0目标函数：约束条件（1）变量（决策变量）:它是规划中要确定的未知量，是用数量方式来表示的方案或措施，可由决策者决定和控制。（2）目标函数：它是决策变量的函数，是决策者在一定的限制条件下希望得到的结果。（3）约束条件：指决策变量取值时受到的各种资源条件的限制，通常用等式或不等式来表达。其中，xij≥0叫做非负约束。由于目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式，所以此类模型称为线性规划的数学模型。实际问题中，线性的含义有二：一是严格的比例性，即某种产品对资源的消耗量和可获得的利润与其生产数量严格成比例。二是可迭加性。即生产多种产品对某种资源的消耗量等于各产品对该项资源的消耗量之和。1/14/20239模型中，cj称为价值系数。bi是资源限制量。aij称为技术系数或工艺系数。二、线性规划模型的一般形式假设线性规划问题中含有n个变量，m个约束方程。则线性规划模型的一般形式为：max(或min)z＝c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤（或＝，≥）b1a21x1+a22x2+…+a2nxn≤（或＝，≥）b2…………am1x1+am2x2+…+amnxn≤（或＝，≥）bmx1,x2,…,xn≥0简写为：向量形式：矩阵形式：1/14/202310三、线性规划问题的标准形式若得出的线性规划模型不是标准形式，应通过下列方法将其化为标准形式：1.目标函数为求极小值的情况，即本教材规定，线性规划模型的标准形式为：其特点是：(1)目标函数求极大；(2)约束条件取等式；(3)变量非负；(4)约束条件右边常数为正值。化为标准形式的方法是，令zˊ＝－z，则1/14/202311三、线性规划问题的标准形式3.约束条件为不等式的情况。当约束条件为“≤”时，在约束符号的左边加上一个松弛变量，将“≤”变为“＝”；如6x1+2x2≤24,化为标准形式为6x1+2x2＋x3＝24，x3≥0。当约束条件为“≥”时，在约束符号的左边减去一个剩余变量，将“≥”变为“＝”；如10x1+12x2≥18,化为标准形式为10x1+12x2－x3＝18，x3≥0。4.对变量无约束的情况。如x在（－∞，＋∞）之间变化，即x的取值可正可负时，令x＝xˊ－x〞代入线性规划模型即可，其中xˊ≥0，x〞≥0。5.对于x≤0的情况，令xˊ＝－x，显然xˊ≥0。2.若约束条件右边常数项bi<0，化为标准形式的方法是：将等式或不等式两边同时乘以（－1）。1/14/202312例3将下述线性规划模型化为标准形式minz＝x1+2x2+3x3－2x1+x2+x3≤9－3x1+x2+2x3≥44x1－2x2－3x3＝－6x1≤0，x2≥0，x3取值无约束（左边减去x8）（令z1＝－z）（左边加上x7）（两边同时乘以－1）解：令x4＝－x1，x3＝x5－x6代入上式，其中x4，x5，x6≥0minz＝－x4+2x2+3（x5－x6)2x4+x2+(x5－x6)≤93x4+x2+2(x5－x6)≥4－4x4－2x2－3(x5－x6)＝－6x2,x4,x5,x6≥0maxz1＝－2x2＋x4－3x5＋3x6x2+2x4+x5－x6＋x7＝9x2+3x4+2x5－2x6－x8＝42x2＋4x4＋3x5－3x6＝6x2,x4,x5,x6,x7,x8≥0该线性规划问题的标准形式为1/14/202313§1-2图解法含有两个决策变量的线性规划问题可用图解法求解。图解法的目的：一是判别线性规划问题的求解结局；二是在存在最优解的条件下，把问题的最优解求出来。一、图解法的步骤1.在坐标平面上建立直角坐标系；2.图示约束条件，找出可行域；3.图示目标函数，寻找最优解。例：maxz＝2x1＋x2 5x2≤15 6x1＋2x2≤24 x1＋x2≤5 x1，x2≥0Q1Q3Q2Q4Ox1x25x2＝156x1＋2x2＝24x1＋x2＝5z＝2z＝8.5(3.5，1.5)6x1＋2x2＝24x1＋x2＝5联立单纯形法返回第一章目录1/14/202314二、线性规划问题求解的几种可能结局上例用图解法解得线性规划问题的最优解为x1＝3.5，x2＝1.5，与最优解相应的目标函数值z＝8.5。这是该线性规划的唯一最优解。除此之外，线性规划问题的求解还有以下几种情况：1.线性规划问题有无穷多最优解。2.线性规划问题的最优解无界。3.线性规划问题无解，或无可行解。Q1Q4Q3Q2Ox1x2x1x2Ox1x2有无穷多最优解目标函数求极大时，最优解无界无可行域，所以无解。遗漏必要的约束条件约束条件之间存在矛盾1/14/202315三、由图解法得到的起示1.求解线性规划问题时，解的情况有：有唯一最优解；无穷多最优解；最优解无界（无界解）；无可行解。2.若线性规划问题的可行域存在，则可行域是凸集。3.若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多解的话）一定是可行域的某个顶点。4.解题思路是，先找出凸集的任一顶点，计算该处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果不是，则该顶点就是最优解点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，直到找出使目标函数值达到最大的顶点为止。1/14/202316§1-3单纯形法原理可行解：满足（2）、（3）式的解称为可行解。全部可行解的集合称为可行域。最优解：使目标函数（1）达到最大值的可行解称为最优解。一、线性规划问题的解的概念有线性规划问题：基：设A为约束方程（2）的m×n阶系数矩阵（设n>m），其秩为m，B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。系数矩阵基：图解法返回第一章目录1/14/202317一、线性规划问题的解的概念基B中的每一个列向量Pj(j=1，2，…，m）称为基向量，与基向量Pj对应的变量xj称为基变量；除基变量以外的变量称为非基变量。基解：在约束方程中，将非基变量移到等式右边：P1P2Pm令非基变量xm+1＝xm+2＝…＝xn＝0，得可解得m个基变量的唯一解为：XB＝（x1，x2，…，xm）T。加上非基变量取0的值，得X＝（x1,x2,…，xm,0,…,0）T。这就是线性规划问题的基解。1/14/202318基可行解：满足非负约束的解称为基可行解。可行基：对应于基可行解的基称为可行基。例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解。maxz＝2x1+3x2+x3x1+x3＝5x1+2x2+x4＝10x2+x5＝4x1~5≥0一、线性规划问题的解的概念解：用穷举法找出该线性规划问题的全部基解。打√者为基可行解。最优解为：x1＝2，x2＝4，x3＝3，x4＝0，x5＝0与最优解对应的目标函数值为z＝191/14/202319凸集设C为n维欧氏空间的一个点集。若对于C中任意两点X1，X2满足αX1+(1-α)X2∈C(0＜α＜1)则称C为凸集。也就是说，如果X1∈C，X2∈C，则线段X1X2上的所有点X也属于C。即：X＝αX1+(1-α)X2∈C(0＜α＜1)称C为凸集。从直观上看，凸集没有凹入部分，其内部没有孔洞。二、凸集和顶点凸集凸集凸集凸集凸集凸集1/14/202320不是凸集不是凸集不是凸集不是凸集二、凸集和顶点顶点设K为凸集，X∈C，若X不能用C中不同的两点X1，X2的线性组合表示为X＝αX1+(1-α)X2∈C(0＜α＜1)则称X为C的一个顶点（或极点）。即X不能成为C中任何线段的内点。1/14/202321三、线性规划的基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集。引理线性规划的可行解X=(x1,x2,…,xn)为基可行解的充要条件是X

的正分量所对应的系数列向量线性独立。定理2：线性规划的基本可行解对应于其可行域的顶点。定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。单纯形法迭代原理1/14/202322定理1：若线性规划问题存在可行解，则问题的可行域是凸集。证明若满足线性规划约束条件线性规划的基本定理的证明∑Pjxj＝bj=1n的所有点组成的集合C是凸集,则C内任意两点X1，X2连线上的点也必然在C内。设X1=(x11,x12,…，x1n)T,X2=(x21,x22,…，x2n)T为C内任意两点，即X1∈C，X2∈C，将X1，X2代入约束条件，有∑Pjx1j＝bj=1n∑Pjx2j＝bj=1n；（1-9）X1，X2连线上任意一点可表示为：

X＝aX1＋（1－a）X2

（0<a<1) (1-10)将（1-9）代入（1-10）得：所以X1∈C，X2∈C。由于集合中任意两点连线上的点均在集合内，所以C为凸集。1/14/202323引理线性规划的可行解X

=(x1,x2,…,xn)为基可行解的充要条件是X的正分量所对应的系数列向量线性独立。证：（1）必要性。由基可行解的定义得证。（2）充分性。若向量P1,P2,…,Pk线性独立，则必有k≤m时；当k=m时，它们恰好构成一个基，从而X=(x1,x2,…,xm,0,…,0)T为相应的基可行解。当k<m时，则一定可以从其余列向量中找出(m-k)个与P1,P2,…,Pk构成一个基，其对应的解恰为X，所以根据定义它是基可行解。返回1/14/202324定理2：线性规划的基本可行解对应于其可行域的顶点。证:本定理需要证明:X是可行域顶点X是基可行解。用反证法证明：X不是可行域的顶点X不是基可行解。（1）X不是基可行解X不是可行域的顶点。假设X的前m个分量为正，有1/14/202325由引理知P1,P2,…,Pm线性相关，即存在一组不全为零的数δi(i=1,2,…，m),使得 d1P1+d2P2+…+dmPm=0 (1.12)将（1.12）乘以一个不全为零的数μ得 md1P1+md2P2+…+mdmPm=0 (1.13)(1.13)+(1.11)得：(x1＋md1)P1+(x2＋md2)P2+…+(xm＋mdm)Pm=b(1.11)-(1.13)得：(x1－md1)P1+(x2－md2)P2+…+(xm－mdm)Pm=b令 X(1)=[(x1＋md1),(x2＋md2),…,(xm＋mdm),0,…,0] X(2)=[(x1－md1),(x2－md2),…,(xm－mdm),0,…,0]又m可以这样来选择，使得对所有i=1,2,…,m有xi±mdi≥0即X不是可行域的顶点。引理1/14/202326（2）X不是可行域的顶点X不是基本可行解。设X＝(x1,x2,…,0,…,0)T不是可行域的顶点，因而可以找到可行域内另外两个不同点Y和Z，有X=aY+(1-a)Z(0<a<1),或可写为：xj=ay+(1-a)zj;(0<a<1;j=1,2,…,n)因a>0,1-a>0,故当xj=0时，必有yi=zi=0(1.14)-(1.15)得：因(yj－zj)不全为零，故P1,P2,…,Pr线性相关，即X不是基可行解。1/14/202327定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。证：设X(0)=(x10,x20,…,xn0)是线性规划的一个最优解，若X(0)不是基可行解，由定理2知X(0)不是顶点，一定能在可行域内找到通过X(0)的直线上的另外两个点（X(0)+md)≥0和（X(0)－md）≥0。将这两个点代入目标函数有C(X(0)＋md)＝CX(0)＋Cmd ; C(X(0)－md)＝CX(0)－Cmd因CX(0)为目标函数的最大值，故有CX(0)≥CX(0)＋Cmd ； CX(0)≥CX(0)－Cmd由此知Cmd＝0，即有C(X(0)＋md)＝CX(0)＝C(X(0)－md)。如果（X(0)＋md）或(X(0)－md)仍不是基可行解，按上面的方法继续做下去，最后一定可以找到一个基可行解，使目标函数值等于CX(0)，问题得得证。1/14/202328四、单纯形法迭代原理基本思路：先找出一个基可行解，判断它是否为最优解，如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直到求得最优解或判断问题无解为止。在约束条件（1.16）的系数矩阵中，总可以找到一个单位矩阵：确定初始基可行解1/14/202329基阵P1,P2,…,Pm称为基向量，与其对应的变量x1,x2,…xm称为基变量，模型中的其它变量称为非基变量。在约束条件中令所有的非基变量等于零，即可得到一个解：X＝(x1,x2,…xm,xm+1,…,xn)T＝（b1,b2,…,bm,0,…,0)T因b≥0，所以X满足非负约束，是一个基可行解。从一个基可行解转换为相邻的基可行解定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。1/14/202330设初始基可行解中的前m个为基变量为：X(0)＝(x10,x20,…,xm0,0,…，0)T将其代入约束条件（1.16）有系数矩阵的增广矩阵为：因P1,P2,…,Pm是一个基，其它向量Pj可用这个基的线性组合来表示：1/14/202331或将（1.20）式乘上一个正数θ＞0得（1.19）+（1.21）并整理得：由（1.22）式找到满足约束方程组的另一个点X(1),有X(1)＝(x10-qa1j,x20-qa2j,…,xm0-qamj,0,…,q,…,0)T其中q是X(1)的第j个坐标的值。要使X(1)是一个基本可行解，必须使xi0－qaij≥01.23）令这m个不等式中至少有一个等号成立。故可令1/14/202332由式（1.24）知因alj＞0，故由矩阵元素组成的行列式不为零，P1,P2,…,Pl-1,Pl,Pl+1…,Pm是一个基。在上述增广矩阵中作初等变换，将第l行乘上（1/alj),再分别乘以（-aij)(i=1,2,…,l-1,l+1,…,m)加到各行去，则增广矩阵左半部分变成单位矩阵。所以，X(1)是一个可行解。与变量xl1,…,x1l-1,,x1l+1,…,xm,xj对应的向量经重新排列后得又因bl/alj＝q，所以

b=(b1-qa1j,…,bl-1-qal-1,j,bl+1-qal+1,j,…,bm-qamj)T

由此X(1)是同X(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。1/14/2023333.最优性检验和解的判别将基本可行解X(0)和X(1)分别代入目标函数得式中，因为q＞0,所以只要就有z(1)＞z(0)。1/14/202334最优性检验和解的判别准则（1）当所有sj≤0时，当前基可行解是线性规划问题的最优解；（2）当所有sj≤0，若对某个非基变量xj有cj－zj＝0,则该线性规划问题有无穷多个最优解；若对所有非基变量有sj＜0，线性规划问题有唯一最优解。（3）若存在sj＞0，又Pj≤0，则表明线性规划问题有无界解。1/14/202335§1-4单纯形法计算步骤第一步：求初始基可行解，列出初始单纯形表。cj→c1…cm…cj…cnCB基bx1…xm…xj…xnc1x1b11…0…a1j…a1nc2x2b20…0…a2j…a2n┆┆┆┆┆┆…┆┆┆cmxmbm0…1…amj…amncj－zj0…0……基变量及其值问题中所有变量单位矩阵非基变量系数向量Pj表示为基向量线性组合时的系数，因基向量是单位向量，故有Pj=a1jP1+a2jP2+…+amj。各变量在目标函数中的系数值各基变量在目标函数中对应的系数检验数sj=cj-zj=cj-(c1a1j+c2a2j+…+cmamj)返回第一章目录1/14/202336第二步：最优性检验若单纯形表中所有检验数cj－zj≤0，且基变量中不含有人工变量，则得到线性规划问题的最优解，计算结束；若存在cj－zj＞0，而Pj≤0，则问题为无界解，计算结束；否则转下一步。第三步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。1.确定换入基的变量。只要有检验数sj＞0，其对应的xj就可以作为换入基的变量，当有一个以上检验数大于零时，从中找出最大的一个sk，其对应的变量xk为换入基的变量（简称换入变量）。2.确定换出基的变量。用Pk列的系数分别去除常数项，找出最小比值确定xl为换出基的变量，元素alk

决定了从一个基可行解到相邻基可行解的转移去向，所以，称alk为主元。1/14/2023373.用换入变量xk替换换出变量xl，作初等变换，得到一个新的单纯形表。初等变换的方法是：将主元化为1，主元所在列的其它元素化为0。第四步：重复第二、三两步，直到得出计算结果。例5

用单纯形法求解线性规划问题解：在约束方程中加松弛变量，将该线性规划问题化为标准形式其约束条件系数矩阵的增广矩阵为：P1P2P3P4bP5基变量为x3、x4、x5；非基变量为x1、x2。单位矩阵构成一个基1/14/202338令非基变量x1、x2等于零，的初始基本可行解为：

X(0)＝(0,0,15,24,5)T初始单纯形表cj→21000CB基bx1x2x3x4x50x315051000x424620100x5511001cj－zj21000因为存在s1＝2＞0，s2＝1＞0。所以初始基可行解不是最优解。选择最大检验数对应的非基变量作为换入变量。求最小比值，确定换入变量。主元列主元行将主元化为1，主元所在列的其它元素化为0。1/14/202339迭代运算初始单纯形表cj→21000CB基bx1x2x3x4x50x315051000x424[6]20100x5511001cj－zj21000第一次迭代的单纯形表cj→21000CB基bx1x2x3x4x5cj－zjx3x1x5020141/301/600155100012/30-1/6101/30-1/301/14/202340迭代运算第一次迭代的单纯形表cj→21000CB基bx1x2x3x4x50x315051002x1411/301/600x510[2/3]0-1/61cj－zj01/30-1/30第二次迭代的单纯形表cj→21000CB基bx1x2x3x4x5cj－zjx3x1x2021103/20-1/43/2017/201/4-1/20015/215/4-15/2000-1/4-1/21/14/202341迭代运算结果最终单纯性表（第二次的结果）cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj－zj000-1/4-1/2因为所有检验数sj≤0，且基变量中不含人工变量，所以得到线性规划问题的最优解为：代入目标函数得：1/14/202342§1-5单纯形法的进一步讨论一、人工变量法线性规划模型化为标准形式后，若其约束条件的系数矩阵中不含有单位矩阵，需加人工变量，以便求解。例6

用单纯形法求解线性规划问题P4P6P7罚因子，任意大负值人工变量返回第一章目录1/14/202343单纯形法求解过程cj→-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj－zj-2M-34M10-M000x40x2-Mx7cj－zj1-21-10-110033211-10066403-31s1＝－3－[0×3＋0×(－2)+(－M)×6]＝6M－36M－3s2＝0－[0×0＋0×1+(－M)×0]＝00s3＝1－[0×2＋0×(－1)+(－M)×4] ＝4M＋14M＋1s4＝0－[0×1＋0×0+(－M)×0] ＝00s5＝0－[0×1＋0×(－1)+(－M)×3] ＝3M3Ms6＝－M－[0×(－1)＋0×1+(－M)×(－3)]＝－4M－4Ms7＝－M－[0×0＋0×0+(－M)×1]＝001/14/202344单纯形法求解过程cj→-30100-M-MCB基bx1x2x3x4x5x6x70x4330211-100x21-21-10-110-Mx76[6]0403-31cj－zj6M-304M+103M-4M00x40x2-3x1cj－zj1102/301/2-1/21/60311/30001/300001-1/21/2-1/200303/2-M-3/2-M+1/21/14/202345单纯形法求解过程cj→-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x23011/30001/3-3x1110[2/3]01/2-1/21/6cj－zj00303/2-M-3/2-M+1/20x40x21x3cj－zj103/23/203/4-3/41/401-1/25/20-1/41/41/400001-1/21/2-1/200-9/20-3/4-M+3/4-M-1/4∵所有检验数均≤0，且人工变量为零，∴得到问题的最优解。X＝(0,5/2,3/2,0,0)T;z＝－3x1＋x3＝3/2两阶段法1/14/202346检验数计算cj→-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj－zj-2M-34M10-M00单纯形法求解过程1/14/202347二、两阶段法对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。第一阶段：构造只包括人工变量的目标函数，保持原问题约束条件不变，求第一阶段目标函数极小化的解。判断：当所有sj≤0时，若人工变量为0，第一阶段的目标函数值也为0，则得到第一阶段最优解，转入第二阶段计算。否则，原问题无解。第二阶段：去掉人工变量，将目标函数该为原问题的目标函数，继续迭代，寻找线性规划问题的最优解。1/14/202348用两阶段法求解线性规划问题x6、x7是人工变量。解：1)构造第一阶段的目标函数。2）将第一阶段的目标函数化为标准形式：3）列单纯形表计算求解。1/14/202349cj→00000-1-1CB基bx1x2x3x4x5x6x70x441111000-1x61-21-10-110-1x790310001cj-zj-2400-1000x4330211-100x21-21-10-110-1x7660403-31cj-zj60403-400x400001-1/21/2-1/20x23011/30001/30x11102/301/2-1/21/6cj-zj00000-1-1表1-11表1-121/14/202350表1-12cjCB基bx1x2x3x4x50x400001-1/20x23011/300-3x11102/301/2cj-zjcj-zj-3010000303/2x4x2x3001103/403/23/201-1/25/200001-1/20-1/4-9/2000-3/4因为所有sj≤0,所以得到问题的最优解为： X=(0,5/2,3/2,0,5)T;z＝（-3）×0＋3/2＝3/2表1-111/14/202351三、单纯形法计算中的几个问题1.

目标函数极小化时解的判别。以所有检验数sj≥0作为判别表中解是否最优的标志，或将其化为极大化问题求解。2.退化。按最小比值确定换出变量时，有时同时出现两个相同的最小值，从而使下一个表的基可行解出现一个或多个基变量等于0的退化解。原因：是模型中存在多余的约束，使多个基可行解对应同一顶点。存在退化解，就可能出现迭代运算循环。解决办法：在同等条件下，始终选择下标值最小的变量作为换入变量，下标值最大的变量作为换出变量。3.无可行解的判别。求解过程中，若出现所有检验数sj≤0，而基变量中仍含有非零的人工变量，表明问题无解。1/14/202352例7

用单纯形法求解线性规划问题标准化加人工变量cj→2100-MCB基bx1x2x3x4x50x3211100-Mx56220-11cj-zj2+2M1+2M0-M02x1-Mx5cj-zj121100020-2-1100-2-2M-M01/14/202353四、单纯形法小结1.一般线性规划模型化为标准形式的方法线性规划模型化为标准形式变量xj≥0不变xj≤0令xjˊ＝－xj

，则xj≥0xj无约束令xj＝xjˊ－xj〞；xjˊ≥0，xj〞≥0约束条件右端项bi≥0不变bi＜0约束条件两端乘“-1”形式≤bi＋xsi＝bi＝bi＋xai＝bi≥bi－xsi＋xai＝bi目标函数极大或极小maxz＝不变minz＝令z′＝z，化为求maxz′变量前的系数加松弛变量xs时maxz＝＋0xsi加人工变量xa时maxz＝－Mxai1/14/202354Y单纯形法计算步骤框图找出初始基可行解列出初始单纯形表计算检验数sj所有sj≤0对某一sj＜0有Pj≤0迭代运算用xk替换xl列出新的单纯形表 将主元化为1，主元所在列的其他元素化为0。无界解基变量中含非零的人工变量存在非基变量检验数为零无可行解无穷多最优解唯一最优解NNYYNYN1/14/202355应用举例用长8m的角钢切割钢窗用料。每付钢窗含1.5m的料2根，1.45m的2根，1.3m的6根，0.35m的12根。若需钢窗用料100付，问最少需切割8m长的角钢多少根？试建立其线性规划数学模型。解：为了节省材料，可以考虑各种套裁下料方案（见下表）。料头为零的套裁方案表x2x1x3x4x5x6x7x8x9假设变量1/1