机械优化设计6线性规划课件

1、第六章 线性规划一.线性规划的基本概念二.求解线性规划的单纯形法三.初始基本可行解10/13/20221第六章 线性规划一.线性规划的基本概念二.求解线性规划的单纯 某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？一）应用实例6-1 线性规划的基本概念10/13/20222 某厂生产甲、乙两种产品，已知：两种产品分别由两条生产日利润最大生产能力限制劳动力限制变量非负解: 设甲、乙两种

2、产品的日产件数分别为s.t.10/13/20223日利润最大生产能力限制劳动力限制变量非负解: 设甲、乙两种产二)线性规划的一般形式s.t.特点: 1)为极小化问题; 2)约束取等号; 3)限定系数非负; 4)变量非负.式中， 价值系数； 结构系数 限定系数10/13/20224二)线性规划的一般形式s.t.特点: 1)为极小化问题; 将数学模型化为标准型的方法1）将极大化问题化为极小化问题 松弛变量（开关变量）（两边乘-1）4）将负的限定系数化为正值3）将任意变量化为非负变量2）将不等式约束变为等式约束：目标函数变号；10/13/20225将数学模型化为标准型的方法 松弛变量（开关变量）（两

3、边乘s.t.化为标准型:10/13/20226s.t.化为标准型:10/11/20226三）线性规划的基本概念s.t. 1.线性规划的图解x2x10F=0F*=620(1.5,7)10/13/20227三）线性规划的基本概念s.t. 1.线性规划的图解x2x102. 线性规划的基本概念1）可行解满足约束条件及非负条件的解。（D内及其边界上的解）2）基本解使n-m个变量等于0，解约束方程组(共有m个约束方程)所得的解。基本解对应于约束边界的交点.3）基本可行解可行域中的基本解（即D的顶点）。4）基本变量与非基本变量 预先取为零值的n-m个变量为非基本变量，其余m个为基本变量。x2x10F=0F*

4、=-620(1.5,7)s.t.10/13/202282. 线性规划的基本概念1）可行解满足约束条件及非负条件的四）线性规划的基本性质 1）可行域D为凸集，每个基本可行解对应于D上的一个顶点； 2）只要可行域存在且封闭，则起码有一个基本可行解为最优点； *）若最优点所在的边界线与等值线平行，则该边界线上的点均为最优点； ）若可行域不封闭，则可能有无界解。 3)最优点可在D的顶点中寻找。10/13/20229四）线性规划的基本性质10/11/202296-2 求解线性规划的单纯形法一.基本思路 先取D的一个顶点作为初始点,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解,直至达到最

5、优解.*1)需获得一个初始基本可行解; 2)每次只更换一个非基本变量;3)保证下降性和可行性.10/13/2022106-2 求解线性规划的单纯形法一.基本思路 先取D的一二.计算实例s.t.1.初始基本可行解取x5,x6 为基本变量, 则有:0 0 0 0 4 5T10/13/202211二.计算实例s.t.1.初始基本可行解取x5,x6 为基本变2.第一次变换顶点(1)选取进基变量原则: 考虑下降性,且下降得最快判别数:假定x2进基, 则有取相应的目标函数变化量:即10/13/2022122.第一次变换顶点(1)选取进基变量原则: 考虑下降性,且写成一般形式:最小,x3 应为进基变量推论:

6、 若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解.10/13/202213写成一般形式:最小,x3 应为进基变量推论: 10/11/2(2)确定离基变量原则:考虑可行性(该变量离基后,能使余下的基本变量为非负)判别数:由于)若取 (离基),则有 应取 为正且其值为最小者对应的基本变量离基.(可行)(不可行)若取 (离基),则有 10/13/202214(2)确定离基变量原则:考虑可行性(该变量离基后,能使余下)推论:若线性规划的的所有离基判别数均为负数时,则问题有无界解.最小,x6 应为离基变量0 0 5/3 0 2/3 0T* )因为 ,故 也必须大于0, 否则不满足可行

7、性要求;10/13/202215)推论:若线性规划的的所有离基判别数均为负数时,则问题有无进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(3)(4)10/13/202216进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(32)确定离基变量 离基(1)(2)0 0 8/5 1/5 0 0T(3)(4)10/13/2022172)确定离基变量 离基(1)(2)0 0 4. 第三次变换顶点1) 确定进基变量 故 为最优点, 为最优值:0 0 8/5 1/5 0 0T10/13/2022184. 第三次变换顶点1) 确定进基变量 故 为最优点三.用单纯形表求解线性规划例.用初等变换

8、法求解解:增广矩阵:10/13/202219三.用单纯形表求解线性规划例.用初等变换法求解解:增广矩阵:s.t.离基判别数进基判别数 单纯形法实际上是解一系列的线性方程组,也可用初等变换方法列表求解.但需加入判别数的计算.421235基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-15例110/13/202220s.t.离基判别数进基判别数 单纯形法实际上是解一系列的42123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38

9、/37/3-25/3421235基变量x1x2x3x4x5x63x5112410425x612310155/3X0000045F037-4-11-20-1510/13/20222142123基变量x1x2x3x4x5x63x51/3-1/342123基变量x1x2x3x4x5x63x51/3-1/3010/312/30.21x31/32/311/305/35X1005/302/30F111/38/37/3-25/34212基变量x1x2x3x4x5x62x41/10-1/10010.21x33/107/10101.6X2001.60.200F223.51.5已获得最优解10/13/202222

10、42123基变量x1x2x3x4x5x63x51/3-1/3-2-300基变量x1x2x3x40 x3-1110330 x41-4014-1X00034F00-2-3-2-30基变量x1x2x3x4-3x2-1103-30 x4-30116-16/3X103016F1-9-5s.t.例2问题有无界解10/13/202223-2-300基变量x1x2x3x40 x3-1110330 x46-3 初始基本可行解大M法 引入一组人工变量,它们在目标函数中的系数均是非常大的正数M;(2) 两相法 引入一组人工变量,在人工变量未完全离基前目标函数为各人工变量之和,当人工变量完全离基后恢复原目标函数。 当

11、A内不包含单位矩阵时,需引入由人工变量组成的单位矩阵,以方便获得初始可行解.10/13/2022246-3 初始基本可行解大M法 当A内不包含单位矩阵时,一.采用大M法获得初始基本可行解s.t.采用大M法：s.t.原问题： 因M是比其他价值系数大得多的正数,且人工变量非负,迭代的结果会使人工变量趋于零,而获得原问题的基本可行解.10/13/202225一.采用大M法获得初始基本可行解s.t.采用大M法：s.t.s.t.411MM基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M表一10/13/202226s.t.411MM基变量x1

12、x2x3x4x5Mx421210411MM基变量x1x2x3x4x5Mx42121042Mx53310131X000043F07M4-5M1-4M1-3M411M基变量x1x2x3x4x5Mx40-14/3121.54x1111/3013X110020F14+2M-3+M-4/3-4M/3表一表二10/13/202227411MM基变量x1x2x3x4x5Mx42121042Mx411基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40表三初始基本可行解411M基变量x1x2x3x4x5Mx40-14/3121.54x11

13、11/3013X110020F14+2M-3+M-4/3-4M/3表二10/13/202228411基变量x1x2x3x4x51x30-3/411.5-2411基变量x1x2x3x4x51x30-3/411.5-24x115/400.50.4X20.501.5F23.50-13/40411基变量x1x2x3x4x51x3011.81x2100.4X300.41.8F32.2表三表四初始基本可行解最优解10/13/202229411基变量x1x2x3x4x51x30-3/411.5-2二.采用两相法获得初始基本可行解大M法的M是一个充分大的正数, 有时在计算机上不便处理.s.t.原问题：s.t.相1问题：10/13/202230二.采用两相法获得初始基本可行解大M法的M是一个充分大的正数00011基变量x1x2x3x4x51x421210421x53310131X0 00043F07-5-4-30001基变量x1x2x3x4x51x40-14/3121.50 x1111/3013X1 10020F121-4/3表一表二10/13/20223100011基变量x1x2x3x4x51x421210421x000基变量x1x2x3x4x50 x30-3/411.5-20 x115/400.50.4X2 0.501.5F2 00表三初始基