线性规划与单纯形方法.ppt

《线性规划与单纯形方法.ppt》由会员分享，可在线阅读，更多相关《线性规划与单纯形方法.ppt（104页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性规划与单纯形方法 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第一节第一节 线性规划问题及数学模型线性规划问题及数学模型一、实例二、线性规划问题（LP问题）的共同特征三、两变量线性规划问题的图解法四、线性规划问题的标准型五、标准型LP问题解的概念六、可行解、基解和基可行解举例2一、实例一、实例例例1 1 生产计划问题生产计划问题Step 1:Step 1:明确问题，设定决策变量明确问题，设定决策变量 设设I I、IIII两种产品的产量分别为两种产品的产量分别

2、为x1,x2 。Step 2:Step 2:确定约束条件确定约束条件产品 I II 资源限量设备 1 2 8台时原料A 4 0 16公斤原料B 0 4 12公斤 利润 2 3问应如何安排生产问应如何安排生产使该厂获利最多使该厂获利最多？3说明：说明：OBJ 表示表示Objective;s.t.表示表示Subjectto Step 3:Step 3:给出目标函数给出目标函数Step 4:Step 4:整理数学模型整理数学模型4例例2现要做现要做100套钢架，每套需套钢架，每套需2.9米、米、2.1米和米和1.5米的元钢各一根。米的元钢各一根。已知原料长已知原料长7.4米，问如何下料，使余料最少？

3、米，问如何下料，使余料最少？设设I,II,III,IV,V分别代表五种不同的原料用量方案分别代表五种不同的原料用量方案,x1,x2,x3,x4,x5分别代表采用各方案下料的元钢的根数。分别代表采用各方案下料的元钢的根数。方案方案根数根数2.9米米2.1米米1.5米米合计合计余料余料I x11037.40IIx22017.30.1IIIx30227.20.2IVx41207.10.3Vx50136.60.8解：解：56LP(Linear Programming)LP(Linear Programming)是数学规划的一个重要分支，数是数学规划的一个重要分支，数学规划着重解决资源的优化配置，一般可

4、以表达成以下两个问学规划着重解决资源的优化配置，一般可以表达成以下两个问题中的一个：题中的一个：（1 1）当资源给定时，要求完成的任务最多；）当资源给定时，要求完成的任务最多；（2 2）当任务给定时，要求为完成任务所消耗的资源最少。）当任务给定时，要求为完成任务所消耗的资源最少。若上述问题的目标若上述问题的目标约束都能表达成变量的线性关系，约束都能表达成变量的线性关系，则这类优化问题称则这类优化问题称LPLP问题。问题。LP LP是一种解决在线性约束条件下追求最大或最小的线性是一种解决在线性约束条件下追求最大或最小的线性目标函数的方法。目标函数的方法。7 目标函数目标函数用决策变量的用决策变量

5、的线性函数线性函数来表示。按问题的不来表示。按问题的不同，要求目标函数实现同，要求目标函数实现最大化和最小化最大化和最小化。每一个问题变量都用一组每一个问题变量都用一组决策变量决策变量（x1,x2,xn）表表示某一方案，这组决策变量的值代表一个具体方案，这示某一方案，这组决策变量的值代表一个具体方案，这些变量是些变量是非负且连续非负且连续的。的。存在一定的存在一定的约束条件约束条件，这些约束条件可以用一组，这些约束条件可以用一组线性线性等式等式或或线性不等式线性不等式来表示。来表示。结论：结论：线性规划是研究在一组线性不等式或线性等式约束线性规划是研究在一组线性不等式或线性等式约束下，使得某一

6、线性目标函数取最大或最小的极值问题。下，使得某一线性目标函数取最大或最小的极值问题。二、线性规划问题（二、线性规划问题（LPLP问题）的共同特征问题）的共同特征8Max(Min)Z=c1x1+c2x2+cnxn (1)a11x1+a12x2+a1nxn(=,)b1 a21x1+a22x2+a2nxn(=,)b2s.t.(2)am1x1+am2x2+amnxn(=,)bm xj0,j=1,2,，n(3)(1)目标函数；目标函数；(2)约束条件；约束条件；(3)决策变量非负决策变量非负n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij

7、技术系数；技术系数；xj决策变量决策变量线性规划模型的一般形式为：线性规划模型的一般形式为：9线性规划模型的紧缩形式线性规划模型的紧缩形式n变量个数；变量个数；m约束行数；约束行数；cj价值系数；价值系数；bi右端项或限额系数；右端项或限额系数；aij技术系数；技术系数；xj决策变量决策变量10练习题：是否为线性规划模型？练习题：是否为线性规划模型？111.1.线性不等式的几何意义线性不等式的几何意义 半平面半平面1)1)作出作出LPLP问题的可行域问题的可行域2)2)作出目标函数的等值线作出目标函数的等值线3)3)移动等值线到可行域边界得到最优点移动等值线到可行域边界得到最优点2.2.图解法

8、步骤图解法步骤三、两变量线性规划问题的三、两变量线性规划问题的图解法图解法124x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例例1Q2(4,2)Z=2x1+3x2做目标函数做目标函数2x1+3x2的等值线，的等值线，与阴影部分的边界相交于与阴影部分的边界相交于Q2(4,2)点，表明最优生产计划点，表明最优生产计划为：生产为：生产I产品产品4件，生产件，生产II产产品品2件。件。Q313目标函数目标函数z=ax1+bx2的值的值递增递增的方向与系数的方向与系数a、b有关有关a0,b0a0X1X2a0,b0,b0z=ax1+bx2目标函数等值线：目标函数等值线：ax1+bx

9、2=k移项移项x2=-a/bx1+k/b目标函数等值线在纵目标函数等值线在纵轴上的截距为轴上的截距为k/b14例例4 4Z=3615例例 用图解法求解线性规划问题用图解法求解线性规划问题4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+4x2当当Z值由小变大时，将与值由小变大时，将与Q2Q3重合重合Q2Q3上任意一点都是最优解上任意一点都是最优解有有无穷多最优解无穷多最优解（多重解）（多重解）Q3(2,3)16例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界无界解无界解（“无无有限最优解有限最优解”或或“最优解无界最优解无界”

10、）约束条件过分宽松约束条件过分宽松注意：注意：可行域不闭合不一定就会出现可行域不闭合不一定就会出现无界解，这要看目标函数的性质。无界解，这要看目标函数的性质。若目标函数是若目标函数是minmin，则有最优解。无，则有最优解。无论有无最优解，一定有可行解。论有无最优解，一定有可行解。x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0017例例 用图解法求解线性规划问题用图解法求解线性规划问题可行域无界可行域无界唯一最优解唯一最优解X*=(1,0)1,0)，对应于点，对应于点Ax2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0018例例 用图解法求解线性规划问题用图解法

11、求解线性规划问题可行域无界可行域无界无穷多最优解无穷多最优解对应于点对应于点B沿着沿着OB向右上向右上方发出的射线上的所有点方发出的射线上的所有点x2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=0019例例 用图解法求解线性规划问题用图解法求解线性规划问题无可行解无可行解（可行域为空）（可行域为空）x14x1=164x2=12x1+2x2=8x248Q14Q430-2-2x1+x2=4无最优解无最优解203.3.图解法的作用图解法的作用 能解决少量问题能解决少量问题 揭示了线性规划问题的若干规律揭示了线性规划问题的若干规律解的类型解的类型可行域类型可行域类型唯一最优解唯一最优解无

12、穷多最优解无穷多最优解最优解无界最优解无界（无有限最优解）（无有限最优解）无解无解（不存在可行域）（不存在可行域）非空有界非空有界无界无界空集空集规律规律1 1：21规律规律2 2：线性规划问题的可行域为线性规划问题的可行域为凸集凸集线性规划问题凸集的顶点个数是有限的线性规划问题凸集的顶点个数是有限的最优解可在凸集的某顶点处达到最优解可在凸集的某顶点处达到 22 小结：图解法的基本步骤：小结：图解法的基本步骤：1在直角坐标系作出可行域在直角坐标系作出可行域S的区域的区域（一般是一个凸多边形）（一般是一个凸多边形）2令目标函数值取一个已知的常数令目标函数值取一个已知的常数k，作等值线：，作等值线

13、：c1x1+c2x2=k3对于对于max问题，让目标函数值问题，让目标函数值k由小变大，即让等值线进由小变大，即让等值线进行平移，若它与可行域行平移，若它与可行域S最后交于一个点（一般是最后交于一个点（一般是S的一个顶的一个顶点），则该点就是所求的最优点，若与点），则该点就是所求的最优点，若与S的一条边界重合，的一条边界重合，此时边界线上的点均是最优点此时边界线上的点均是最优点4将最优点所在的两条边界线所代表的方程联立求解，即将最优点所在的两条边界线所代表的方程联立求解，即得得最优解最优解X*，把最优解，把最优解X*带入目标函数，得带入目标函数，得最优值最优值Z*=CX*注意：若是求目标函数最

14、小值，等值线向反方向移动注意：若是求目标函数最小值，等值线向反方向移动23四、线性规划问题的标准型四、线性规划问题的标准型1.1.标准型标准型（1）目标函数）目标函数：max（2）约束条件：）约束条件：等式等式（3）变量约束：）变量约束：非负非负xj 0（4）资源限量：）资源限量：非负非负bi 0标准型的构成要素标准型的构成要素242.2.线性规划标准型的紧缩形式线性规划标准型的紧缩形式253.3.线性规划标准型的向量和矩阵表达式线性规划标准型的向量和矩阵表达式矩阵式矩阵式:MaxZ=CTXs.t.AX=bX0 n向量式向量式:MaxZ=cjxjj=1ns.t.Pjxj=bj=1xj 0,j=

15、1,2,.,n264.所有所有LP问题均可化为标准型问题均可化为标准型（1）最小转换成最大）最小转换成最大y1=f(x)y2=-f(x)xyx*y1*y2*27（2）不等式约束条件转换成等式约束条件）不等式约束条件转换成等式约束条件（3）变量约束转换）变量约束转换（4）把）把bi 0转换成转换成bi 028例例5 5 化标准型化标准型可化为可化为1.1.处理决策变量处理决策变量2.2.处理约束条件右端处理约束条件右端 常数项常数项3.3.约束条件不等式约束条件不等式4.4.处理目标函数处理目标函数29例例6 6 化标准型化标准型1.1.处理决策变量处理决策变量2.2.处理约束条件右端处理约束条

16、件右端 常数项常数项3.3.约束条件不等式约束条件不等式4.4.处理目标函数处理目标函数30MaxZ=x1+2x2+3x4-3x5+0 x6+0 x7s.t.x1-x2+x4-x5+x6=7x1+x2+x4-x5-x7=2-3x1-x2+3x4-3x5=5 x20,xj0,j=1,4,5,6,7MaxZ=x1+2x2+3(x4-x5)+0 x6+0 x7s.t.x1-x2+(x4-x5)+x6=7x1+x2+(x4-x5)-x7=2-3x1-x2+3(x4-x5)=5 x20,xj0,j=1,4,5,6,7最终结果最终结果中间结果中间结果31课堂练习课堂练习32五、标准型五、标准型LPLP问题

17、解的概念问题解的概念33（1）（2）（3）约束系数矩阵：约束系数矩阵：x1x2x3x4x5例：例：34约束系数矩阵：约束系数矩阵：可能可能的基矩阵是的基矩阵是A中任意三个列的组合，共中任意三个列的组合，共10个。个。35令令B=(P1,P2,Pm)且且|B|0，则称，则称Pj(j=1,2,m)为为基向量基向量。与基向量与基向量Pj对应的变量对应的变量xj称为称为基变量基变量，记为记为XB=(x1,x2,xm)T，其余的变量称为，其余的变量称为非基变量非基变量，记为，记为XN=(xm+1,xm+2,xn)T。363738B1=(P1,P2)：基基令：令：XB1=(x1,x2)x1=0，x2=2X

18、=(0,2,0,0)XB1=(0,2)对应于对应于B1的基解为的基解为39线性规划标准型问题解的关系线性规划标准型问题解的关系约束方程的约束方程的解空间解空间基解基解可行解可行解非可行解非可行解基可基可行解行解40例例7Max Z=2x1+3x2s.t.x1+2x284x1164x212x1,x2 0六、可行解、基解和基可行解举例六、可行解、基解和基可行解举例非基非基变量变量基变量基变量图中的点图中的点x4,x5x1=4x2=3x3=-2 A基解基解x3,x5x1=2x2=3x4=8B基可行解基可行解x3,x4x1=4x2=2x5=4C基可行解基可行解x2,x4x1=4x3=4x5=12D基可

19、行解基可行解x2,x3x1=8x4=-16x5=12E基解基解x1,x5x2=3x3=2x4=16F基可行解基可行解x1,x3x2=4x4=16x5=-4 G基解基解x1,x2x3=8x4=16x5=12H基可行解基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH标准型标准型41例例8 842第二节第二节 LPLP问题的基本理论问题的基本理论一、基本概念一、基本概念43判断以下图形哪些是凸集，哪些不是凸集？判断以下图形哪些是凸集，哪些不是凸集？返回返回44定理定理1 1 LPLP问题的可行域为一凸集问题的可行域为一凸集。二、基本定理二、基本定理45引理

20、引理线性规划问题的可行解线性规划问题的可行解X=(x1,x2,xn)T是基可行解是基可行解的的充要条件为充要条件为X的正分量所对应的系数列向量是线性独立的。的正分量所对应的系数列向量是线性独立的。46定理定理2 2 线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。（即：若（即：若X是是LP问题的可行解，则问题的可行解，则“X是是LP问题的基可行解问题的基可行解”等价于等价于“X是是LP问题可行域顶点问题可行域顶点”）设设X是基可行解，则其对应的向量组是基可行解，则其对应的向量组a1,a2,am线性无关线性无关(mm时，有时，有xj=xj(1)=xj(2)=0

21、.47484950定理定理3 3 若可行域有界，则若可行域有界，则LPLP问题的目标函数一定可以在其可问题的目标函数一定可以在其可行域的顶点上达到最优。行域的顶点上达到最优。引理引理若若S是有界凸集，则任何一点是有界凸集，则任何一点XS可表示为可表示为S的顶点的的顶点的凸组合。凸组合。51 线性规划问题的可行域是凸集线性规划问题的可行域是凸集(定理定理1)1)；凸集的顶点对应；凸集的顶点对应于基可行解于基可行解(定理定理2)2)，基可行解，基可行解(顶点顶点)的个数是有限的；若线的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到性规划有最优解，必在可行域某顶点上达到(定理定理3)3)。

22、因此。因此,我们我们可以在有限个基可行解中寻找最优解。可以在有限个基可行解中寻找最优解。由线性代数知，对标准形由线性代数知，对标准形LP问题，用枚举法可以求出所有问题，用枚举法可以求出所有基解，再通过观察找出其中的可行解（基可行解），进而找基解，再通过观察找出其中的可行解（基可行解），进而找出最优解。但如果变量和方程较多，比如出最优解。但如果变量和方程较多，比如m=50，n=100，所，所有基解有可能达有基解有可能达1029个，即使计算机每秒能求解个，即使计算机每秒能求解1亿个这样的亿个这样的方程组，也需要方程组，也需要30万亿年！因此，必须寻求有效的算法。万亿年！因此，必须寻求有效的算法。为

23、加快计算速度，算法必须具有两个功能，一是每得到一个为加快计算速度，算法必须具有两个功能，一是每得到一个解，就来检验是否已经最优，若是停止。二是若不是最优，要解，就来检验是否已经最优，若是停止。二是若不是最优，要保证下一步得到的解不劣于当前解。这就是线性规划的单纯形保证下一步得到的解不劣于当前解。这就是线性规划的单纯形法。法。52第三节第三节 单纯形法单纯形法基本思想基本思想检验解的检验解的最优性最优性结束结束Y旋转运算（消元运算）旋转运算（消元运算）确定另一个基本可行解确定另一个基本可行解N化化LP问题为标准型，问题为标准型，确定一个初始基本可行解确定一个初始基本可行解化化LP问题为标准型，从

24、可行域的某问题为标准型，从可行域的某个基可行解（一个顶点）开始，转换到个基可行解（一个顶点）开始，转换到另一个基可行解（另一个顶点），并使另一个基可行解（另一个顶点），并使目标函数值得到改善，如此反复，从而目标函数值得到改善，如此反复，从而求得问题的最优解。其实质是逐步迭代求得问题的最优解。其实质是逐步迭代（逼近）法。（逼近）法。53一、确定初始基可行解一、确定初始基可行解MaxZ=CXs.t.AX=bX0我们首先介绍求初始基可行解的方法。我们首先介绍求初始基可行解的方法。1.1.若给定问题标准化后（且若给定问题标准化后（且 ）系数矩阵）系数矩阵A A中存在中存在m m个线性无关个线性无关的单

25、位列向量，则以这的单位列向量，则以这m m个单位列向量构成的单位子矩阵作为初始个单位列向量构成的单位子矩阵作为初始基基B B，则，则 ，其余，其余x xj j=0=0是基可行解。是基可行解。2.2.大大M M法（人工变量法）法（人工变量法）54以以x2为主元素为主元素以以x1为主元素为主元素例例2x1+x2+2x3=10(1)3x1+3x2+x3=6(2)x1+1/2x2+x3=5(1)0 x1+3/2x2-2x3=-9(2)(1)/2,(2)-(1)3x1+0 x2+5/3x3=8(1)0 x1+x2-4/3x3=-6(2)(2)2/3,(1)-(2)/2二、旋转运算二、旋转运算55三、检验

26、数的意义三、检验数的意义结论：结论：如果如果LPLP问题通过单纯形法迭代到某步时，所有检验数问题通过单纯形法迭代到某步时，所有检验数0,0,则该则该LPLP问题已得到最优解。问题已得到最优解。MaxZ=CXs.t.AX=bX0若若cj-CBB-1Pj=j0,则则ZZ0,Z0即为最优解即为最优解.(基变量的检验数必为基变量的检验数必为0)令令A=(B,N),X=XB,C=(CB,CN)XN由由AX=b(B,N)XB=bBXB+NXN=bB-1BXB+B-1NXN=B-1bXNXB=B-1bB-1NXN(2)将将(2)式代入目标函数得式代入目标函数得Z=CX=(CB,CN)XB=CBXB+CNXN

27、=CB(B-1b-B-1NXN)+CNXN XN=CBB-1b+(CN-CBB-1N)XN=Z0+(cj-CBB-1Pj)xjxj为非基变量为非基变量56单纯形法举例单纯形法举例化为标准型化为标准型57约束方程的系数矩阵约束方程的系数矩阵对应于B的变量x3，x4，x5为基变量，（1）将（将（1）代入目标函数后得到）代入目标函数后得到z=0+2x1+3x2，令非基变量令非基变量x1=x2=0.得到得到z=0，及一个基可行解，及一个基可行解X(0)=(0,0,8,16,12)T58x2=3，x5为换出变量为换出变量（3）将（将（3）代入目标函数后得到）代入目标函数后得到z=9+2x13/4x5，令

28、非基变量令非基变量x1=x5=0.得到得到z=9，及一个基可行解，及一个基可行解X(1)=(0,3,2,16,0)T当将当将x2定为换入变量后定为换入变量后，必须从，必须从x3，x4，x5中中确定一个换出变量，并保证确定一个换出变量，并保证x3，x4，x50，当当x1=0时，由（时，由（1）式得到）式得到（2）用高斯消元法，将用高斯消元法，将x2的系数列向量变换为单位列向量，得到的系数列向量变换为单位列向量，得到59这时目标函数的表达式是这时目标函数的表达式是z=141.5x30.125x4，当将当将x1定为换入变量后定为换入变量后，继续利用上述方法，继续利用上述方法确定换出变量，继续迭代，再

29、得到一个基可确定换出变量，继续迭代，再得到一个基可行解行解X(2)=(2,3,0,8,0)T再经过一次迭代，再得到一个基可行解再经过一次迭代，再得到一个基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q14Q430Q2(4,2)Z=2x1+3x2Q360对于线性规划问题对于线性规划问题：MaxZ=CTXAX=b，X0，可用如下三，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无个判别定理来判别线性规划问题是否已经获得最优解或为无界解。界解。判别定理判别定理1 1设设X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一

30、切切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规为线性规划的最优解。划的最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一切切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，同时有某个，同时有某个非基变量的检验数非基变量的检验数k=0(kJ)，则该线性规划有无穷，则该线性规划有无穷多最优解。多最优解。判判别别定定理理3 3设设X为为线线性性规规划划的的一一个个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划问题具有无界解（无最优解）。划问题具有

31、无界解（无最优解）。61一、步骤一、步骤Step1.化化LP问题为问题为标准型标准型,建立建立初始单纯形表初始单纯形表;Step2.若所有检验数若所有检验数0,则最优解已达到。则最优解已达到。否则否则,计计算算 ,选取选取k 所对应的变量所对应的变量xk 为为换入变换入变量量（进基变量进基变量）;最大最大（检验数）规则（检验数）规则Step3.计算计算 ,选取选取l 所对应的变量所对应的变量xl 为为换出变量换出变量（出基变量出基变量）;最小比值规则最小比值规则Step4.以以alk为主元素进行为主元素进行旋转运算旋转运算,转转Step2;第四节第四节 单纯形法的步骤单纯形法的步骤62cj C

32、B XB b x1x2 xmxm+1xnj基可行解：基可行解：x1=b1,x2=b2,xm=bm,xm+1=xm+2=xn=01.1.初始单纯形表初始单纯形表c1c2cm cm+1cnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1n010a2,m+1a2n 001am,m+1amn000m+1n-CBTB-1b63对于上述单纯形表：对于上述单纯形表：（1）一个基对应一个单纯形表，且单纯形表中必须有一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。一个初始单位基。（2）从单纯形表中，可立即得到一个基可行解：从单纯形表中，可立即得到一个基可行解：x1=b1,x2=b2,

33、xm=bm,xm+1=xm+2=xn=0（3）用检验数的计算公式很容易计算检验数，并可根用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。性规划问题无最优解。642.2.换入变量（换入变量（进基变量）的选择进基变量）的选择cj c1c2cm cm+1ckcnCB XB b x1x2 xmxm+1xkxnc1x1 c2x2 cmxmb1 b2 bm100a1,m+1a1k a1n010a2,m+1a2k a2n 001am,m+1amkamnj-CBTB-1b000m+1k n选取选取 所对应

34、的变量所对应的变量xk 为换入变量。为换入变量。653.3.换出变量（换出变量（出基变量）的选择出基变量）的选择cj c1cl cm cm+1ckcnCB XB b x1xl xmxm+1xkxnc1x1 clxl cmxmb1 bl bm100a1,m+1a1k a1n 010al,m+1alk aln 001am,m+1amk amn1 l mj-CBTB-1b000m+1k n选取选取 所对应的变量所对应的变量xl 为换出变量。为换出变量。664.4.旋转运算旋转运算cj c1cl cm cm+1ckcn CB XB b x1xl xmxm+1xkxnc1x1 clxl cmxmb1 b

35、l bm100a1,m+1a1k a1n 010al,m+1alk aln 001am,m+1amk amnjckxkbl/alk01/alk 0al,m+1/alk1aln/alk b11-a1k/alk 0a1,m+10a1nbm0-amk/alk1am,m+10amn67二、实例二、实例化为标准型化为标准型68单纯形表算法单纯形表算法cjCB XB bx1x2x3x4x5j以以4为主元素进行旋为主元素进行旋转运算，转运算，x2为换入变为换入变量，量，x5为换出变量为换出变量cj23000CB XB bx1x2x3x4x50 x3 0 x4 3x221631010-1/2240010401

36、001/4-j-92000-3/4以以11为主元素进行为主元素进行运算，运算，x1为换入变量，为换入变量，x3为换出变量为换出变量0 x30 x40 x523000816121210040010040012300004-369cj23000CB XB bx1x2x3x4x52x1 0 x4 3x22831010-1/2-00-412401001/412j-1300-201/4以以22为主元素进行运为主元素进行运算，算，x5为换入变量，为换入变量，x4为换出变量为换出变量cj23000CB XB bx1x2x3x4x52x1 0 x5 3x24421001/4000-21/21011/2-1/8

37、0j-1400-3/2-1/80此时达到最优解：此时达到最优解：X*=(4,2)T,MaxZ=14。704x1=164x2=12x1+2x2=8x1x2484O三、单纯形表与图解法的对应关系三、单纯形表与图解法的对应关系X1=(0,0)T,Z1=0X2=(0,3)T,Z2=9X3=(2,3)T,Z3=13X4=(4,2)T,Z4=14Q1Q2QQ3基可行解基可行解 基基可行解可行解 迭代迭代 顶点顶点 相邻的顶点相邻的顶点迭代迭代 图解法：图解法：单纯形表算法：单纯形表算法：71对于极小化问题，其最优解的判定定理和进基变量的选取和对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚

38、好相反，如下所示：极大化问题刚好相反，如下所示：判别定理判别定理1 1 设设X为线性规划的一个基可行解，且对于为线性规划的一个基可行解，且对于一切一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性为线性规划的最优解。规划的最优解。判别定理判别定理2 2设设X为线性规划的一个基可行解，且对于一为线性规划的一个基可行解，且对于一切切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个，同时有某个非基变量的检验数非基变量的检验数k=0(kJ)，则该线性规划有无穷，则该线性规划有无穷多最优解。多最优解。判判别别定定理理3 3设设X为为线线性性规规划划的的一一个

39、个基基可可行行解解，若若有有k0(kJ)，且且pk0，即即aik 0（i=1,m），则则该该线线性性规规划问题具有无界解（无最优解）。划问题具有无界解（无最优解）。在进基可行解的转换过程中，进基变量的选取原则是：在进基可行解的转换过程中，进基变量的选取原则是：minj|j 0,而而k对应列向量对应列向量Pk0,则此则此LP问题有问题有无界解无界解.924.4.在最优表中出现某非基变量检验数为在最优表中出现某非基变量检验数为0 0（无穷多最优解）（无穷多最优解）93CBXBbx1x2x3x4x50 x340012/3-1/34x260101/203x14100-2/31/3cj-Zj-36000

40、0-10 x46003/21-1/24x2301-3/401/43x1810100cj-Zj-360000-1cj03400094例例1 1 某工厂要用三种原材料某工厂要用三种原材料D D、P P、H H混合调配出三种不同规格混合调配出三种不同规格的产品的产品A A、B B、C C。已知产品的规格要求、单价和原材料的供应。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？量、单价。该厂应如何安排生产使利润最大？产品产品名称名称规格要求规格要求单价单价(元元/kg）A原材料原材料D不少于不少于50%原材料原材料P不超过不超过25%50B原材料原材料D不少于不少于25%

41、原材料原材料P不超过不超过50%35C不限不限25原材料原材料名称名称每天最多供每天最多供应量应量(kg)单价单价(元元/kg)D10065P10025H6035第六节第六节 应用举例应用举例解：解：设设A中中D、P、H的含量为的含量为x11、x12、x13B中中D、P、H的含量为的含量为x21、x22、x23 C中中D、P、H的含量为的含量为x31、x32、x3395用单纯形法计算得结果：每天生产用单纯形法计算得结果：每天生产A A产品产品200kg,200kg,分别需要原分别需要原料料:D:D为为100kg;P100kg;P为为50kg;H50kg;H为为50kg.50kg.总利润收入总利

42、润收入Z Z=500=500元元/天天.96先考虑一月份的线性规划模型先考虑一月份的线性规划模型:例例2 297 以一月份内各种设备的生产能力总和为分母以一月份内各种设备的生产能力总和为分母,生产产品所生产产品所需要的各类设备的总台时数为分子需要的各类设备的总台时数为分子,可计算出一月份的平均可计算出一月份的平均设备利用系数设备利用系数Z,Z,将将Z Z作为目标函数作为目标函数,可得下面的模型可得下面的模型:98 考虑二月份线性规划模型时考虑二月份线性规划模型时:(1):(1)从全年计划中减去一月份从全年计划中减去一月份已生产的数量已生产的数量;(2);(2)对批量小的产品对批量小的产品,如一

43、月份已经安排较大如一月份已经安排较大产量的产量的,二月份将剩余部分安排生产二月份将剩余部分安排生产;(3);(3)保证第保证第4 4号产品在月号产品在月底前交货底前交货.这样这样,我们可以依我们可以依次对次对1212个月列出线性个月列出线性规划模型并求解规划模型并求解,再再根据具体情况对计算根据具体情况对计算结果进行必要调整。结果进行必要调整。99例例3 3 某部门在今后某部门在今后5 5年内连续给以下项目投资：年内连续给以下项目投资：项目项目A A，第一年至第四年每年年初投资，次年末回收本利，第一年至第四年每年年初投资，次年末回收本利115%115%；项目项目B B，第三年初投资，第五年末回

44、收本利，第三年初投资，第五年末回收本利125%125%，最大投资额，最大投资额 不超过不超过4 4万元；万元；项目项目C C，第二年初投资，第五年末回收本利，第二年初投资，第五年末回收本利140%140%，最大投资额，最大投资额 不超过不超过3 3万元；万元；项目项目D D，五年内每年初可购买公债，当年末归还，并加利息，五年内每年初可购买公债，当年末归还，并加利息6%6%。该部门现有资金该部门现有资金 1010万元，问该如何确定投资方案，使第五年末万元，问该如何确定投资方案，使第五年末拥有的资金本利和最大？拥有的资金本利和最大？12345Ax1Ax2Ax3Ax4ABx3BCx2CDx1Dx2D

45、x3Dx4Dx5D100第一年第一年第二年第二年第三年第三年第四年第四年第五年第五年101102班次班次时间时间所需人数所需人数16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030例例4 4 某公交线路每天各时段内所需司乘人员数如下：某公交线路每天各时段内所需司乘人员数如下：设所有的司乘人员分别在各时段的开始上班，并连续工设所有的司乘人员分别在各时段的开始上班，并连续工作作8 8小时，问该公交线路至少需配备多少司乘人员。列出该小时，问该公交线路至少需配备多少司乘人员。列出该问题的线性规划模型。问题的线性规划模型。103104