线性规划典型习题.ppt

第二章 线性规划,本章学习要求,（1）线性规划问题及其数学模型：线性规划问题建模方法、线性规划问题 标准形式，非标准线性规划问题向标准线性规划问题的转化。 （2）线性规划问题的图解法及其几何意义：图解法的适用条件与计算过程， 通过图解法了解线性规划问题解的几何意义。 （3）线性规划问题基本性质：掌握描述线性规划问题基本性质的4个定理。 （4）单纯形法：掌握单纯形法的计算方法，包括寻找初始基本可行解、最 优解的判别、基变换，熟练掌握单纯形表的计算过程。 （5）特殊的线性规划问题：掌握不能直接获得符合要去的初始基本可行解 情况下的单纯形法，掌握大M法的计算过程。 （6）线性规划在道路交通工程的应用：了解线性规划问题在道路交通工程 中的主要应用。,线性规划典型习题,线性规划建模 单纯性表求解 大 M 法,习题一,桥梁工地要制作100套钢筋架子，每套需要长2.9米、2.1米和1.5米的钢筋各1根。现有原材料（钢筋）长7.4米，问如何下料最省（废料最少）？,在每根7.4米长的原料钢筋上截取2.9米、2.1米和1.5米的料各1根，这样每根原料就都剩下了0.9米长的废料无法利用。 所谓合理利用原材料，就是要使废料最少，因此考虑如何在原材料上合理套裁，以下几种方法都是能节省材料的较好方案：,为得到100套钢筋架子，需要混合使用各种下料方案。 设按第j种方案下料的原材料根数为xj（j=1,2,3,4,5）。根据表中的数据可以列出约束条件为：,X1+2X2+X4=100 2X3+2X4+X5=100 3X1+X2+2X3+3X5=100 Xj0, j=1,2,3,4,5,目标函数为,MIN Z=0.1X2+0.2X3+0.3x4+0.8x5,化标准型,采用大M法，列单纯形表可解,习题二,在下面的线性规划问题中找出满足约束条件的所有基解，指出哪些是基可行解，并确定哪一个是最优解。,MAX Z=2X1+3X2+4X3+7X4 S.T. 2X1+3X2-X3-4X4=8 -X1+2X2-6X3+7X4=3 X1,X2,X3,X40,MAX Z=2X1+3X2+4X3+7X4 S.T. 2X1+3X2-X3-4X4=8 -X1+2X2-6X3+7X4=3 X1,X2,X3,X40,基解,基,系数矩阵,基本可行解,取子矩阵D1，,D1为一个基,对于D1 ，基变量为X1、X2，X3、X4为非基变量，令 X3、X4=0 X1 =1、X2 =2,P1、P2,可行解,取子矩阵D2，,D2为一个基,对于D2 ，基变量为X1、X3，X2、X4为非基变量，令 X2、X4=0 X1 =45/13、X3 =-14/13,P1、P3,非可行解,取子矩阵D3，,D3为一个基,对于D3 ，基变量为X1、X4，X2、X3为非基变量，令 X2、X3=0 X1 =34/5、X4=7/5,P1、P4,可行解,取子矩阵D4，,D4为一个基,对于D4 ，基变量为X2、X3，X1、X4为非基变量，令 X1、X4=0 X2 =45/16、X3 =7/16,P2、P3,可行解,取子矩阵D5，,D5为一个基,对于D5 ，基变量为X2、X4，X1、X3为非基变量，令 X3、X1=0 X2 =68/29、X4 =-7/29,P2、P4,非可行解,取子矩阵D6，,D6为一个基,对于D6 ，基变量为X3、X4，X1、X2为非基变量，令 X1、X2=0 X3 =-68/31、X4