资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,第六章 线性规划,一.线性规划的基本概念,二.求解线性规划的单纯形法,三.初始基本可行解,11/17/2024,1,第六章 线性规划一.线性规划的基本概念二.求解线性规划的单纯,某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？,一）应用实例,6-1 线性规划的基本概念,11/17/2024,2,某厂生产甲、乙两种产品，已知：两种产品分别由两条生产,日利润最大,生产能力限制,劳动力限制,变量非负,解,:,设甲、乙两种产品的日产件数分别为,s.t.,11/17/2024,3,日利润最大生产能力限制劳动力限制变量非负解:设甲、乙两种产,二)线性规划的一般形式,s.t.,特点:,1)为极小化问题;2)约束取等号;,3)限定系数非负;4)变量非负.,式中，价值系数；结构系数,限定系数,11/17/2024,4,二)线性规划的一般形式s.t.特点:1)为极小化问题;,将数学模型化为标准型的方法,1）将极大化问题化为极小化问题,松弛变量,（开关变量）,（两边乘-1）,4）将负的限定系数化为正值,3）将任意变量化为非负变量,2）将不等式约束变为等式约束：,目标函数变号；,11/17/2024,5,将数学模型化为标准型的方法 松弛变量（开关变量）（两边乘,s.t.,化为标准型,:,11/17/2024,6,s.t.化为标准型:10/7/20236,三）线性规划的基本概念,s.t.,1.线性规划的图解,x,2,x,1,0,F=0,F*=620,(1.5,7),11/17/2024,7,三）线性规划的基本概念s.t.1.线性规划的图解x2x10,2.线性规划的基本概念,1）可行解,满足约束条件及非负条件的解。,（D内及其边界上的解）,2）基本解,使n-m个变量等于0，解约束方程组(共有m个约束方程)所得的解。,基本解对应于约束边界的交点.,3）基本可行解,可行域中的基本解（即D的顶点）。,4）基本变量与非基本变量,预先取为零值的n-m个变量为非基本变量，其余m个为基本变量。,x,2,x,1,0,F=0,F*=-620,(1.5,7),s.t.,11/17/2024,8,2.线性规划的基本概念1）可行解满足约束条件及非负条件的,四）线性规划的基本性质,1）可行域D为凸集，每个基本可行解对应于D上的一个顶点；,2）只要可行域存在且封闭，则起码有一个基本可行解为最优点；,*）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点；,）若可行域不封闭，则可能有无界解。,3)最优点可在D的顶点中寻找。,11/17/2024,9,四）线性规划的基本性质10/7/20239,6-2 求解线性规划的单纯形法,一.基本思路,先取D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最优解.,*1)需获得一个初始基本可行解;,2)每次只更换一个非基本变量;,3)保证下降性和可行性.,11/17/2024,10,6-2 求解线性规划的单纯形法一.基本思路 先取D的一,二.计算实例,s.t.,1.初始基本可行解,取x,5,x,6,为基本变量,则有:,0 0 0 0 4 5,T,11/17/2024,11,二.计算实例s.t.1.初始基本可行解取x5,x6 为基本变,2.第一次变换顶点,(1)选取进基变量,原则:考虑下降性,且下降得最快,判别数:,假定x,2,进基,则有,取,相应的目标函数变化量:,即,11/17/2024,12,2.第一次变换顶点(1)选取进基变量原则:考虑下降性,且,写成一般形式:,最小,x,3,应为进基变量,推论:,若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解.,11/17/2024,13,写成一般形式:最小,x3 应为进基变量推论:10/7/20,(2)确定离基变量,原则:考虑可行性(该变量离基后,能使余下的基本变量为非负),判别数,:,由于,)若取 (离基),则有,应取 为正且其值为最小者对应的基本变量离基.,(可行),(不可行),)若取 (离基),则有,11/17/2024,14,(2)确定离基变量原则:考虑可行性(该变量离基后,能使余下,),推论:,若线性规划的的所有离基判别数均为负数时,则问题有无界解.,最小,x,6,应为离基变量,0 0 5/3 0 2/3 0,T,*)因为 ,故 也必须大于0,否则不满足可行性要求;,11/17/2024,15,)推论:若线性规划的的所有离基判别数均为负数时,则问题有无,进基,3.第二次变换顶点,去掉了,(1),(2),1)确定进基变量,(3),(4),11/17/2024,16,进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(3,2)确定离基变量,离基,(1),(2),0 0 8/5 1/5 0 0,T,(3),(4),11/17/2024,17,2)确定离基变量 离基(1)(2)0 0,4.第三次变换顶点,1)确定进基变量,故 为最优点,为最优值:,0 0 8/5 1/5 0 0,T,11/17/2024,18,4.第三次变换顶点1)确定进基变量 故 为最优点,三.用单纯形表求解线性规划,例.用初等变换法求解,解:增广矩阵:,11/17/2024,19,三.用单纯形表求解线性规划例.用初等变换法求解解:增广矩阵:,s.t.,离基判别数,进基判别数,单纯形法实际上是解一系列的线性方程组,也可用初等变换方法列表求解.但需加入判别数的计算.,4,2,1,2,3,5,基变量,x,1,x,2,x,3,x,4,x,5,x,6,3,x,5,1,1,2,4,1,0,4,2,5,x,6,1,2,3,1,0,1,5,5/3,X,0,0,0,0,0,4,5,F,0,37,-4,-11,-20,-15,例1,11/17/2024,20,s.t.离基判别数进基判别数 单纯形法实际上是解一系列的,4,2,1,2,3,基变量,x,1,x,2,x,3,x,4,x,5,x,6,3,x,5,1/3,-1/3,0,10/3,1,2/3,0.2,1,x,3,1/3,2/3,1,1/3,0,5/3,5,X,1,0,0,5/3,0,2/3,0,F,1,11/3,8/3,7/3,-25/3,4,2,1,2,3,5,基变量,x,1,x,2,x,3,x,4,x,5,x,6,3,x,5,1,1,2,4,1,0,4,2,5,x,6,1,2,3,1,0,1,5,5/3,X,0,0,0,0,0,4,5,F,0,37,-4,-11,-20,-15,11/17/2024,21,42123基变量x1x2x3x4x5x63x51/3-1/3,4,2,1,2,3,基变量,x,1,x,2,x,3,x,4,x,5,x,6,3,x,5,1/3,-1/3,0,10/3,1,2/3,0.2,1,x,3,1/3,2/3,1,1/3,0,5/3,5,X,1,0,0,5/3,0,2/3,0,F,1,11/3,8/3,7/3,-25/3,4,2,1,2,基变量,x,1,x,2,x,3,x,4,x,5,x,6,2,x,4,1/10,-1/10,0,1,0.2,1,x,3,3/10,7/10,1,0,1.6,X,2,0,0,1.6,0.2,0,0,F,2,2,3.5,1.5,已获得最优解,11/17/2024,22,42123基变量x1x2x3x4x5x63x51/3-1/3,-2,-3,0,0,基变量,x,1,x,2,x,3,x,4,0,x,3,-1,1,1,0,3,3,0,x,4,1,-4,0,1,4,-1,X,0,0,0,3,4,F,0,0,-2,-3,-2,-3,0,基变量,x,1,x,2,x,3,x,4,-3,x,2,-1,1,0,3,-3,0,x,4,-3,0,1,16,-16/3,X,1,0,3,0,16,F,1,-9,-5,s.t.,例2,问题有无界解,11/17/2024,23,-2-300基变量x1x2x3x40 x3-1110330 x4,6-3 初始基本可行解,大M法,引入一组人工变量,它们在目标函数中的系数均是非常大的正数M;,(2)两相法,引入一组人工变量,在人工变量未完全离基前目标函数为各人工变量之和,当人工变量完全离基后恢复原目标函数。,当A内不包含单位矩阵时,需引入由人工变量组成的单位矩阵,以方便获得初始可行解.,11/17/2024,24,6-3 初始基本可行解大M法 当A内不包含单位矩阵时,一.采用大M法获得初始基本可行解,s.t.,采用大M法,：,s.t.,原问题,：,因M是比其他价值系数大得多的正数,且人工变量非负,迭代的结果会使人工变量趋于零,而获得原问题的基本可行解.,11/17/2024,25,一.采用大M法获得初始基本可行解s.t.采用大M法：s.t.,s.t.,4,1,1,M,M,基变量,x,1,x,2,x,3,x,4,x,5,M,x,4,2,1,2,1,0,4,2,M,x,5,3,3,1,0,1,3,1,X,0,0,0,0,4,3,F,0,7M,4-5M,1-4M,1-3M,表一,11/17/2024,26,s.t.411MM基变量x1x2x3x4x5Mx421210,4,1,1,M,M,基变量,x,1,x,2,x,3,x,4,x,5,M,x,4,2,1,2,1,0,4,2,M,x,5,3,3,1,0,1,3,1,X,0,0,0,0,4,3,F,0,7M,4-5M,1-4M,1-3M,4,1,1,M,基变量,x,1,x,2,x,3,x,4,x,5,M,x,4,0,-1,4/3,1,2,1.5,4,x,1,1,1,1/3,0,1,3,X,1,1,0,0,2,0,F,1,4+2M,-3+M,-4/3-4M/3,表一,表二,11/17/2024,27,411MM基变量x1x2x3x4x5Mx42121042Mx,4,1,1,基变量,x,1,x,2,x,3,x,4,x,5,1,x,3,0,-3/4,1,1.5,-2,4,x,1,1,5/4,0,0.5,0.4,X,2,0.5,0,1.5,F,2,3.5,0,-13/4,0,表三,初始基本可行解,4,1,1,M,基变量,x,1,x,2,x,3,x,4,x,5,M,x,4,0,-1,4/3,1,2,1.5,4,x,1,1,1,1/3,0,1,3,X,1,1,0,0,2,0,F,1,4+2M,-3+M,-4/3-4M/3,表二,11/17/2024,28,411基变量x1x2x3x4x51x30-3/411.5-2,4,1,1,基变量,x,1,x,2,x,3,x,4,x,5,1,x,3,0,-3/4,1,1.5,-2,4,x,1,1,5/4,0,0.5,0.4,X,2,0.5,0,1.5,F,2,3.5,0,-13/4,0,4,1,1,基变量,x,1,x,2,x,3,x,4,x,5,1,x,3,0,1,1.8,1,x,2,1,0,0.4,X,3,0,0.4,1.8,F,3,2.2,表三,表四,初始基本可行解,最优解,11/17/2024,29,411基变量x1x2x3x4x51x30-3/411.5-2,二.采用两相法获得初始基本可行解,大M法的M是一个充分大的正数,有时在计算机上不便处理.,s.t.,原问题：,s.t.,相1问题：,11/17/2024,30,二.采用两相法获得初始基本可行解大M法的M是一个充分大的正数,0,0,0,1,1,基变量,x,1,x,2,x,3,x,4,x,5,1,x,4,2,1,2,1,0,4,2,1,x,5,3,3,1,0,1,3,1,X,0,0,0,0,4,3,F,0,7,-5,-4,-3,0,0,0,1,基变量,x,1,x,2,x,3,x,4,x,5,1,x,4,0,
展开阅读全文