运筹学2014-2015-2第2章
- 格式:ppt
- 大小:2.89 MB
- 文档页数:137
第二章线性规划教学目的:了解线性规划的基本概念,理解线性规划最优化原理、单纯形法原理,掌握单纯形法及其矩阵描述、人工变量法、,能够对简单的问题建模。
教学重点:线性规划的含义、性质;线性规划问题的求解方法——图解法、单纯形法。
线性规划模型的建立非标准型线性规划问题转化为标准线性规划问题;线性规划问题的图解法;解的存在情况判断;大M法;两阶段法;单纯形法的矩阵表示;教学难点:单纯形法的求解思想、矩阵表示、对偶理论、对偶单纯形法以及灵敏度分析。
学时: 8学时2.1 线性规划(Linear Programming,LP)问题及其数学模型(1学时)我们应用数学规划模型求解实际问题中,将实际问题抽象成数学模型,然后再对其求解。
2.1.1线性规划问题提出我们用一个简单例子来说明如何建立数学规划问题的数学模型。
例2.1 某家具厂生产桌子和椅子两种家具,有关资料见表2-1。
解:用数学语言来描述生产计划安排问题,这个过程称为建立其数学模型,简称建模。
设:①桌子、椅子生产的数量分别为x1,x2,称为决策变量。
因为产量一般是一个非负数,所以有x1,x2≥0,称非负约束。
②限制条件为木工和油漆工的加工时间约束了产品的生产量x1,x2。
约束如下:4x1+3x2≤1202x1+x2≤50③生产桌子、椅子x 1,x 2所得总收入为Z ,显然Z =50x 1+30x 2。
我们希望总收入值能达到最大,这个关系用公式表达为max Z =50x 1+30x 2 把上述所有数学公式归纳如下12121212max .0z 50x 30x 4x 3x 120s t 2x x 50x x =++≤⎧⎪+≤⎨⎪≥⎩,这就是一个最大化的线性规划模型。
例 2.2(运输工具的配载问题)有一辆运输卡车,载重2.5t ,容积183m ,用来装载如下的两种货物:箱装件125kg/个、0.43m /个;包装件20kg/个、1.53m /个。
问:如何装配,卡车所装物件个数最多?解 根据题意,设箱装件1x 个,包装件2x 个,那么需要满足条件:体积约束 120.4 1.518x x +≤重量约束 12125202500x x +≤非负约束12,0x x ≥目标要求 max z=12x x +我们对上面的式子稍作整理,便得到下面的形式:max z=12x x +1212120.4 1.518125202500,0x x x x x x +≤⎧⎪+≤⎨⎪≥⎩ 上述两例中所提出的问题,最终都归结为在变量满足线性约束条件的前提下,求使线性目标函数最大或最小的问题,这种问题称为线性规划问题。