线性规划典型习题.ppt

1、第二章第二章 线性规划线性规划本章学习要求本章学习要求（1 1）线性规划问题及其数学模型）线性规划问题及其数学模型：线性规划问题建模方法、线性规划问题线性规划问题建模方法、线性规划问题 标准形式，非标准线性规划问题向标准线性规划问题的转化。标准形式，非标准线性规划问题向标准线性规划问题的转化。（2 2）线性规划问题的图解法及其几何意义）线性规划问题的图解法及其几何意义：图解法的适用条件与计算过程，图解法的适用条件与计算过程，通过图解法了解线性规划问题解的几何意义。通过图解法了解线性规划问题解的几何意义。（3 3）线性规划问题基本性质）线性规划问题基本性质：掌握描述线性规划问题基本性质的掌握描述

2、线性规划问题基本性质的4 4个定理。个定理。（4 4）单纯形法）单纯形法：掌握单纯形法的计算方法，包括寻找初始基本可行解、最：掌握单纯形法的计算方法，包括寻找初始基本可行解、最 优解的判别、基变换，熟练掌握单纯形表的计算过程。优解的判别、基变换，熟练掌握单纯形表的计算过程。（5 5）特殊的线性规划问题：）特殊的线性规划问题：掌握不能直接获得符合要去的初始基本可行解掌握不能直接获得符合要去的初始基本可行解 情况下的单纯形法，掌握大情况下的单纯形法，掌握大M M法的计算过程。法的计算过程。（6 6）线性规划在道路交通工程的应用：）线性规划在道路交通工程的应用：了解线性规划问题在道路交通工程了解线性

3、规划问题在道路交通工程 中的主要应用。中的主要应用。线性规划典型习题线性规划建模线性规划建模单纯性表求解单纯性表求解大大 M M 法法习题一习题一 桥梁工地要制作桥梁工地要制作100100套钢筋架子，每套需要长套钢筋架子，每套需要长2.92.9米、米、2.12.1米和米和1.51.5米的钢筋各米的钢筋各1 1根。现有原材根。现有原材料（钢筋）长料（钢筋）长7.47.4米，问如何下料最省（米，问如何下料最省（废料废料最少最少）？）？u在每根在每根7.47.4米长的原料钢筋上截取米长的原料钢筋上截取2.92.9米、米、2.12.1米和米和1.51.5米的料各米的料各1 1根，这样每根原料就都剩下了

4、根，这样每根原料就都剩下了0.90.9米长的废料无法利用。米长的废料无法利用。u所谓合理利用原材料，就是要使废料最少，因此考虑如何在原所谓合理利用原材料，就是要使废料最少，因此考虑如何在原材料上合理套裁，以下几种方法都是能节省材料的较好方案：材料上合理套裁，以下几种方法都是能节省材料的较好方案：方案方案123452.9米米1212.1米米2211.5米米3123合合计（米）（米）7.47.37.27.16.6废料（米）料（米）00.10.20.30.8n为得到为得到100100套钢筋架子，需要混合使用各种下料方案。套钢筋架子，需要混合使用各种下料方案。n设按第设按第j种方案下料的原材料根数为种

5、方案下料的原材料根数为xj（j=1,2,3,4,5）。）。根据表中的数据可以列出约束条件为：根据表中的数据可以列出约束条件为：X1+2X2+X4=1002X3+2X4+X5=1003X1+X2+2X3+3X5=100 Xj0,j=1,2,3,4,5123452.9米米1212.1米米2211.5米米3123合计合计7.47.37.27.16.6废料废料00.10.20.30.8目标函数为目标函数为MIN Z=0.1X2+0.2X3+0.3x4+0.8x5化标准型化标准型采用大采用大M M法，列单纯形表可解法，列单纯形表可解习题二习题二 在下面的线性规划问题中找出满足约束条在下面的线性规划问题中

6、找出满足约束条件的所有基解，指出哪些是基可行解，并件的所有基解，指出哪些是基可行解，并确定哪一个是最优解。确定哪一个是最优解。MAX Z=2X1+3X2+4X3+7X4 S.T.2X1+3X2-X3-4X4=8 -X1+2X2-6X3+7X4=3 X1,X2,X3,X4 0MAX Z=2X1+3X2+4X3+7X4 S.T.2X1+3X2-X3-4X4=8 -X1+2X2-6X3+7X4=3 X1,X2,X3,X4 0基解基解基基系数矩阵系数矩阵基本可行解基本可行解取子矩阵取子矩阵D1，D1为一个基为一个基对于对于D1，基变量为基变量为X1、X2，X3、X4为非基变量，令为非基变量，令 X3、

7、X4=0 X1=1、X2=2P1、P2可行解取子矩阵取子矩阵D2，D2为一个基为一个基对于对于D2，基变量为基变量为X1、X3，X2、X4为非基变量，令为非基变量，令 X2、X4=0 X1=45/13、X3=-14/13P1、P3非可行解取子矩阵取子矩阵D3，D3为一个基为一个基对于对于D3，基变量为基变量为X1、X4，X2、X3为非基变量，令为非基变量，令 X2、X3=0 X1=34/5、X4=7/5P1、P4可行解取子矩阵取子矩阵D4，D4为一个基为一个基对于对于D4，基变量为基变量为X2、X3，X1、X4为非基变量，令为非基变量，令 X1、X4=0 X2=45/16、X3=7/16P2、

8、P3可行解取子矩阵取子矩阵D5，D5为一个基为一个基对于对于D5，基变量为基变量为X2、X4，X1、X3为非基变量，令为非基变量，令 X3、X1=0 X2=68/29、X4=-7/29P2、P4非可行解取子矩阵取子矩阵D6，D6为一个基为一个基对于对于D6，基变量为基变量为X3、X4，X1、X2为非基变量，令为非基变量，令 X1、X2=0 X3=-68/31、X4=-45/31P3、P4非可行解习题三习题三求解如下的线性规划问题求解如下的线性规划问题化标准型化标准型101512000-MbiCBXBx1x2x3x4x5x6x70 x4531100099/50 x5-5615010015-Mx721100-1155/210+2M15+M12+M00-M010 x113/51/51/50009/590 x509161100243/2-Mx70-1/53/5-2/50-117/57/309-M/510+3M/5-2-2M/50-M010 x1139/8003/16-1/80003/20 x3009/161/161/16003/2-Mx700-43/80-7/16-3/80-111/2027/8-43M/800-21/8-7M/16-5/8-3M/80-M0所有的检验数所有的检验数j，且人工，且人工变量量x71/2，所以原，所以原线性性规划划问题无可行解。无可行解。