您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 市场营销 > 1 线性规划与单纯形法
Page:1QSC华东理工大学工商经济学院生产与运作管理1线性规划与单纯形法Page:2QSC华东理工大学工商经济学院生产与运作管理线性规划的发展•20世纪30年代前苏联数学家康特洛维奇提出解乘数法(1975年诺贝尔经济学奖)•1947美国空军数学顾问丹捷格线性规划单纯形法•冯.诺依曼对偶理论库恩塔克盖尔严格证明Page:3QSC华东理工大学工商经济学院生产与运作管理概要•1问题描述•2建模•2.1变量•2.2目标函数•2.3约束条件•3模型求解•3.1图解法•3.2单纯形法•3.2.1标准化•3.2.2解的基本概念•3.2.3单纯形法的一般思路+例子•3.2.4单纯形表结构+例子•3.2.5单纯形法的计算步骤•3.3大M法Page:4QSC华东理工大学工商经济学院生产与运作管理•4解的几种特殊形式•4.1无可行解•4.2无界解•4.3多重最优解Page:5QSC华东理工大学工商经济学院生产与运作管理1问题描述--线性规划经典问题生产计划问题某工厂拥有A、B、C三种类型的设备,生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示:每件产品占用的机时数(小时/件)产品甲产品乙产品丙产品丁设备能力(小时)设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润(元/件)5.247.308.344.18Page:6QSC华东理工大学工商经济学院生产与运作管理12341234123412341234max5.247.38.344.181.51.02.41.020001.05.01.03.58000..1.03.03.51.05000,,,0zxxxxxxxxxxxxstxxxxxxxx2建模Page:7QSC华东理工大学工商经济学院生产与运作管理线性规划问题的表示一般形式nnxcxcxcz2211max(min)0...,,).(......).().(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxatsPage:8QSC华东理工大学工商经济学院生产与运作管理线性规划问题的表示-矩阵形式12TnccCcnxxxX21nbbbb21mnmmnnaaaaaaaaaA212222111211max(min)z=CXs.t.AX≤(=,≥)bX≥0Page:9QSC华东理工大学工商经济学院生产与运作管理线性规划问题的表示-标准形式maxz=CXs.t.AX=bX≥0例子Page:10QSC华东理工大学工商经济学院生产与运作管理3模型求解3.1图解法(线性规划问题的几何特征)maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1,x2≥0123456xz=0z=3z=6z=9z=12z=15.3013456约束条件(1)约束条件(2)C-1-8-2-3-4-5-6-7x21Page:11QSC华东理工大学工商经济学院生产与运作管理(d)可行域无界(e)可行域无界(f)可行域为空集多个最优解目标函数无界无可行解(a)可行域有界(b)可行域有界(c)可行域无界唯一最优解多个最优解唯一最优解Page:12QSC华东理工大学工商经济学院生产与运作管理3.2单纯形法3.2.1标准化•松弛变量的引入Page:13QSC华东理工大学工商经济学院生产与运作管理3.2.2线性规划解的基本概念maxz=x1+2x2s.t.x1+x2≤3x2≤1x1,x2≥0maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x2,x3,x4≥0Page:14QSC华东理工大学工商经济学院生产与运作管理O123123xx21ABCDx3=0x4=0x2=0x1=0可行域(可行解全体)基本可行解(可行域顶点、极点)基本解Page:15QSC华东理工大学工商经济学院生产与运作管理•基向量:基B中的一列为B的基向量.•基变量:与基B的基向量相应的变量.•基本解:对于基B,令所有非基变量为零,求得满足条件约束的解.•基本可行解:满足非负约束的基本解.•基本最优解:满足最优化目标的基本可行解.•退化的基本解:基本解中存在基变量为零.Page:16QSC华东理工大学工商经济学院生产与运作管理基矩阵基向量基变量非基变量基本解基本可行解对应点11101B12,PP12,XX34,XX(1)(2,1,0,0)TX是B21100B非基矩阵31001B14,PP14,XX23,XX(3)(3,0,0,1)TX是A41110B23,PP23,XX14,XX(4)(0,1,2,0)TX是C51011B24,PP24,XX13,XX(5)(0,3,0,2)TX否D61001B34,PP34,XX12,XX(6)(0,0,3,1)TX是OPage:17QSC华东理工大学工商经济学院生产与运作管理基的定义定义线性规划的基(Basis)对于线性规划的约束条件AX=bAmnX≥0设B是A矩阵中的一个非奇异的m×m子矩阵,则称B为线性规划的一个基。Page:18QSC华东理工大学工商经济学院生产与运作管理设B是线性规划的一个基,则A可以表示为A=[B,N]XXXBNX也可相应地分成其中XB为m×1向量,称为基变量XN为(n-m)×1向量,称为非基变量约束方程AX=b的分块矩阵表示BNXXb,.BNAX=b可表示为或BXB+NXN=bPage:19QSC华东理工大学工商经济学院生产与运作管理若XN取确定的值,则XB有唯一的值与之对应XB=B-1b-B-1NXN特别,取XN=0,这时有XB=B-1bPage:20QSC华东理工大学工商经济学院生产与运作管理定义线性规划的解称为线性规划与基B对应的基本解(非基变量都取值为0)。若其中B-1b0,则称以上的基本解为一基本可行解,相应的基B称为可行基。XXXBb0BN1基本解与基本可行解的定义Page:21QSC华东理工大学工商经济学院生产与运作管理定理线性规划问题的可行域是凸集.线性规划问题的每个基本可行解对应着可行域的一个顶点.若线性规划问题有最优解,必在可行域的某一个顶点上达到.Page:22QSC华东理工大学工商经济学院生产与运作管理3.2.3单纯形法的一般思路寻找初始基本可行解给出基本可行解为最优解的判别准则给出从目前基本可行解转移到新基本可行解的方法Page:23QSC华东理工大学工商经济学院生产与运作管理求解流程确定初始基本可行解最优解?否转移到新的基本可行解给出最优解是Page:24QSC华东理工大学工商经济学院生产与运作管理例子maxz=x1+2x2s.t.x1+x2≤3x2≤1x1,x2≥0maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x2,x3,x4≥0Page:25QSC华东理工大学工商经济学院生产与运作管理单纯形原理的矩阵描述设标准的线性规划问题为maxz=CXs.t.AX=bX0矩阵A可以分块记为A=[B,N]相应地,向量X和C可以记为,BBNNXXCCCXPage:26QSC华东理工大学工商经济学院生产与运作管理AX=b可以写成BXB+NXN=b即XB=B-1b-B-1NXN对于一个确定的基B,目标函数z可以写成,.BBNBBNNNzXCXCCCXCXX目标函数z用非基变量表出的形式1111()()BNNNBNBNzCBbBNXCXCBbCCBNXPage:27QSC华东理工大学工商经济学院生产与运作管理3.2.4单纯形表的结构CBCNXBXNCBXBIB-1NB-1b检验数0CN-CBB-1NPage:28QSC华东理工大学工商经济学院生产与运作管理11,111,122,112,2,11,1122110mmnnmmnnmmmmmnnmmmmmnnxaxaxbxaxaxbxaxaxbzcxcxcxcxcxPage:29QSC华东理工大学工商经济学院生产与运作管理1211,11,12,12,2,1,12101000010000110mmnmnmnmmmnmmmnzxxxxxbaabaabaabcccccPage:30QSC华东理工大学工商经济学院生产与运作管理11,11,12,12,2,1,1,1,1110001BmnmnmnmmmnmmmmmiimniiniiiiizxxxbaabaabaabccaccacbPage:31QSC华东理工大学工商经济学院生产与运作管理单纯形方法例子maxz=50x1+40x2s.t.3x1+5x2≤150x2≤208x1+5x2≤300x1,x2≥0Page:32QSC华东理工大学工商经济学院生产与运作管理103020605040X21020304050ABCDE(1)(2)(3)X1X4=0X5=0X2=0X3=0X1=0Page:33QSC华东理工大学工商经济学院生产与运作管理标准化maxz=50x1+40x2s.t.3x1+5x2+x3=150(1)x2+x4=20(2)8x1+5x2+x5=300(3)x1,x2,x3,x4,x5≥0Page:34QSC华东理工大学工商经济学院生产与运作管理信息表(单纯形表)当前基本可行解:(0,0,150,20,300),Z=05040000x1x2x3x4x5RHS比值035100150150/300101020-085001300300/85040000x5检验数x3x4Page:35QSC华东理工大学工商经济学院生产与运作管理当前基本可行解:(75/2,0,75/2,20,0),Z=18755040000x1x2x3x4x5RHS比值0025/810-3/875/21200101020205015/8001/875/260035/400-25/4x3x4x1检验数Page:36QSC华东理工大学工商经济学院生产与运作管理5040000x1x2x3x4x5RHS比值40018/250-3/2512000-8/2513/2585010-5/2505/253000-14/50-26/5x1检验数x2x4当前基本可行解:(30,12,0,8,0),Z=1980Page:37QSC华东理工大学工商经济学院生产与运作管理3.2.5单纯形法的计算步骤(max)•(1)找出初始可行基,给出初始基本可行解,建立初始单纯形表。•(2)检验各非基变量的检验数,如果所有检验数都小于等于0,则已得到最优解;否则,转下一步。•(3)正检验数最大对应的变量作为换入变量;极小比值准则决定换出变量;迭代运算。•(4)再检验直到得到最优解。Page:38QSC华东理工大学工商经济学院生产与运作管理单纯形法的计算步骤(min)•(1)找出初始可行基,给出初始基本可行解,建立初始单纯形表。•(2)检验各非基变量的检验数,如果所有检验数都大于等于0,则已得到最优解;否则,转下一步。•(3)负检验数最小对应的变量作为换入变量;极小比值准则决定换出变量;迭代运算。•(4)再检验直到得到最优解。Page:39QSC华东理工大学工商经济学院生产与运作管理3.3大M法一般问题的初始基本可行解maxz=4x1+2x2-3x3+5x4s.t.2x1-x2+x3+2x4≥50(1)3x1-x3+2x480(2)x
本文标题:1 线性规划与单纯形法
链接地址:https://www.777doc.com/doc-4121699 .html