《第五章化工过程系统优化方法线性》由会员分享，可在线阅读，更多相关《第五章化工过程系统优化方法线性（48页珍藏版）》请在金锄头文库上搜索。
1、5.4 线性规划及其应用5.4.15.4.1线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型线性规划问题的数学模型（一）引言（一）引言（一）引言（一）引言 线性规划是运筹学的重要分支之一，也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自1947年线性规划被成功的运用于工业、交通、农业和军事等各个领域后。随着计算机的普及，它的适应领域越来越广泛。 研究内容有两类： (1) 是一项任务确定后，如何统筹安排，尽量作到用最少的人力物力资源去完成这一任务。 (2) 是已有一定数量的人力物力资源，如何安排使用他们，使得完成任务最多。 此外此外,大量复杂的化工优化问题大量复杂的化
2、工优化问题,简化为线性规划问题简化为线性规划问题进行求解进行求解.目标函数及约目标函数及约束条件均为线束条件均为线性函数性函数1编辑ppt整体指标最优的问题整体指标最优的问题1.运输问题运输问题2.生产的组织与计划问题生产的组织与计划问题3.合理下料问题合理下料问题4.配料问题配料问题5.布局问题布局问题6.分配问题分配问题2编辑ppt（二）线性规划问题的数学模型（二）线性规划问题的数学模型1.运输问题运输问题设有两个化工厂设有两个化工厂A A1 1、A A2 2。其产量分别为。其产量分别为2323万桶与万桶与2727万万桶产品。它们生产的产品可供应桶产品。它们生产的产品可供应B B1 1、B
3、 B2 2、 B B 3 3三个工厂。其三个工厂。其需要量分别为需要量分别为1717万桶、万桶、1818万桶和万桶和1515万桶。自各产地到各万桶。自各产地到各工厂的运价格如下表：问应如何调运，才使总运费最省。工厂的运价格如下表：问应如何调运，才使总运费最省。 运价 工厂 工厂B1B2B 3A1506070A2601101603编辑ppt解：解：设设设设 x xi ji j表示由工厂表示由工厂表示由工厂表示由工厂A Ai i 运往工厂运往工厂运往工厂运往工厂 B Bj j 的产品数量的产品数量的产品数量的产品数量( (万桶万桶万桶万桶) ) （i=1,2i=1,2；j=1,2,3)j=1,2,
4、3)运量 工厂工厂B1B2B 3发量A1x11x12x1323A2x21x22x2327收量171815504编辑ppt目标函数目标函数目标函数目标函数 约束条件约束条件约束条件约束条件5编辑ppt2.2.生产的组织与计划问题生产的组织与计划问题生产的组织与计划问题生产的组织与计划问题 某化工厂生产某化工厂生产某化工厂生产某化工厂生产A A 、B B两种产品，现有资源数、生产每单两种产品，现有资源数、生产每单两种产品，现有资源数、生产每单两种产品，现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表所示。位产品所需原材料数以及每单位产品可得利润如下表所示。位产品所需原材料数以及每
5、单位产品可得利润如下表所示。位产品所需原材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润最大？问如何制定生产计划使两种产品总利润最大？问如何制定生产计划使两种产品总利润最大？问如何制定生产计划使两种产品总利润最大？单位产品单位产品产品产品耗用资源耗用资源资源资源A（吨）（吨）B（吨）（吨）现有资源现有资源原料（吨）原料（吨）94360电力（千瓦）电力（千瓦）45200劳动日（个）劳动日（个）310300单位利润单位利润（万元（万元/吨）吨）7126编辑ppt解解解解：假设生产假设生产假设生产假设生产A A产品产品产品产品x x1 1吨，吨，吨，吨， B B产品产品产品
6、产品x x2 2吨吨吨吨. .得到利润得到利润得到利润得到利润7 7x x1 1 +12+12x x2 2万元，万元，万元，万元，这一问题的数学模型为：这一问题的数学模型为：这一问题的数学模型为：这一问题的数学模型为：约束条件约束条件 目标函数目标函数7编辑ppt从数学上从数学上共同特征共同特征：每一个问题都是求一组变量（称为决策变量）的值。代表一个具体方案,通常要求变量的取值是非负的。存在一定的限制条件(称为约束条件)。这些约束条件都可以用一组线性等式或不等式来表示。都有一个期望达到的目标，并且这个目标可以表示为决策变量的线性函数（称为目标函数）。我们将具有上述三个特点的最优化问题归结为我们
7、将具有上述三个特点的最优化问题归结为线性规划线性规划问问题，其数学模型简称线性规划数学模型。题，其数学模型简称线性规划数学模型。8编辑ppt线性规划问题的数学模型的线性规划问题的数学模型的线性规划问题的数学模型的线性规划问题的数学模型的一般形式一般形式一般形式一般形式（1）式称为目标函数目标函数（2）式中等式或不等式称为约束条件约束条件（3）式是非负约束条件非负约束条件x1 , x2, ,xn称为决策变量决策变量，简称变量变量。9编辑ppt满足约束条件的一组变量的值称为线性规划问题的一个可行解可行解;使目标函数取得最大（或最小）的可行解称为最优解最优解。此时，目标函数的值称为最优值最优值。10
8、编辑ppt建立线性规划数学模型的步骤建立线性规划数学模型的步骤 首先首先，确定决策变量。 线性规划的数学模型建得是否容易，求解是否方便，取决于决策变量的选取是否得当。 其次其次，确定约束条件，并根据实际问题添加非负条件。 明确问题中所有的限制条件，并用决策变量的线性等式或不等式表示。 最后最后，确定目标函数，并确定是求极大还是求极小。 用决策变量的线性函数来表示实际问题所要达到的目标，得到目标函数。11编辑ppt5.4.2线性规划问题的图解法线性规划问题的图解法例例例例1 1求x1、x2的值，使它们满足并且使目标函数f=2x1+5x2的值最大。图解法是利用直观的几何图形求解线性规划的一种几何解
9、法12编辑pptx12x1+5x2=192x1+5x2=152x1+5x2=82x1+5x2=4x2=3x1=4x1+2x2=80x2最优解为 x1=2，x2=3相应的目标函数的最大值为S=2*2+5*3=1913编辑pptx1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0x2=3x1=4x1+2x2=80x2例例例例2 2若把例1的目标函数改为改为 s=x1+2x2，则,最优解有 无穷多个无穷多个,它们对应的目标函数值都是8 814编辑ppt例例3求x1、x2的值，使它们满足并且使目标函数s=2x1+2x2的值最小。15编辑pptx1x20X X1 1-x-x2 2= =1
10、 1-X-X1 1+2x+2x2 2=0=02X1+2x2=22X1+2x2=62X1+2x2=102X1+2x2=16最优解最优解最优解最优解 X X X X1 1 1 1=1=1=1=1，x x x x2 2 2 2=0, =0, =0, =0, 目标函数最小值目标函数最小值目标函数最小值目标函数最小值 s=2s=2s=2s=2解解解解：16编辑ppt例例例例44求x1、x2的值，使它们满足并且使目标函数s=2 x1+2x2的值最小。17编辑pptx1x2-x1+x2=1没有可行解，当然没有最没有可行解，当然没有最优优解。解。解：解：解：解：x1+x20且且xm+k对应的对应的系数列系数列
11、均均小于等于零小于等于零则该线性规划问题则该线性规划问题无最优解无最优解 38编辑ppt3.3.单纯形表法单纯形表法单纯形表法单纯形表法用用表表格格的的形形式式来来表表示示求求解解线线性性规规划划问问题题的的单单纯纯形形法法的的计算过程计算过程,称为称为.可以使计算和检验更加简便可以使计算和检验更加简便,具体方法如下：具体方法如下：（）将目标函数式改写为将目标函数式改写为-f+c1x1+c2x2+cnxn=0且作为等式约束方程组的第且作为等式约束方程组的第m+1个方程，得个方程，得39编辑ppt对对方程组的增广矩阵施行初等行变换，化为如下的方程组的增广矩阵施行初等行变换，化为如下的 阶梯形矩阵
12、阶梯形矩阵40编辑ppt将矩阵表示成将矩阵表示成将矩阵表示成将矩阵表示成单纯形表单纯形表单纯形表单纯形表xBb100010001-f000-f0x1x2xmxm+1xnx1x2xmb1b2bma1m+1a2m+1amm+1a1na2namn下面通过具体的例子说明用下面通过具体的例子说明用单纯形法求解线性规划问题。单纯形法求解线性规划问题。41编辑ppt例例例例1 1 用单纯形法解线性规划问题用单纯形法解线性规划问题用单纯形法解线性规划问题用单纯形法解线性规划问题解解解解 将该线性规划问题化为标准型将该线性规划问题化为标准型42编辑ppt 显然显然显然显然x x3 3 , , x x4 4 ,
13、, x x5 5为基变量，为基变量，为基变量，为基变量， x x1 1 , , x x2 2为非基变量。可为非基变量。可为非基变量。可为非基变量。可得单纯形表。这种直接从线性规划问题得到的单纯形得单纯形表。这种直接从线性规划问题得到的单纯形得单纯形表。这种直接从线性规划问题得到的单纯形得单纯形表。这种直接从线性规划问题得到的单纯形表称为表称为表称为表称为初始单纯形表初始单纯形表初始单纯形表初始单纯形表 x1x5初始基本可行解为初始基本可行解为x1=x2=0,x3=12,x4=8,x5=16。注注注注用用用用最小比值原则最小比值原则最小比值原则最小比值原则确定确定确定确定出基变量出基变量出基变量
14、出基变量的一般的一般的一般的一般方法方法方法方法是：是：是：是： 在在在在单单单单纯纯纯纯形形形形表表表表中中中中，b b b b列列列列元元元元素素素素与与与与进进进进基基基基变变变变量量量量列列列列对对对对应应应应的的的的正正正正元元元元素素素素之之之之比，取其比值比，取其比值比，取其比值比，取其比值最小最小最小最小的所对应的基变量的所对应的基变量的所对应的基变量的所对应的基变量出基出基出基出基。 x x x x2 2 2 2 x x x x4 4 4 4x2x3x4xBb2210012120108400016-f2300001x3x x4 4x512/28/2目标函数中系数最大对应的变量
15、目标函数中系数最大对应的变量x2为进基变量为进基变量43编辑ppt注：比值相等时可任选其一xBb001-1-1/400101/2-1/8210004-f000-3/2-1/8-14x1x2x3x4x5x3x2x11/4非非基基变变量量的的检检验验数数小小于于0最优解为最优解为x x1 1 =4 =4 =4 =4 x x2 2 =2 =2 =2 =2 x x3 3 =0,=0,=0,=0,x x4 4= = = =x x5 5=0=0=0=0目标函数值为目标函数值为f=14f=14f=14f=14 4544编辑ppt例例例例2 2 用单纯形法求解线性规划问题用单纯形法求解线性规划问题用单纯形法求
16、解线性规划问题用单纯形法求解线性规划问题解解解解 x3 , , x4为基变量，为基变量， x1 , , x2为非基变量。可得初始单纯形表为非基变量。可得初始单纯形表 XBb1-1102-31014-f32000X X1 1X3X4X2X X3 3X4目标函数中系数最大对应的变量目标函数中系数最大对应的变量x1为进基变量为进基变量2/14/-3x1x345编辑pptXBb1-11020-23110-f05-30-6X1X2X3X4X1X4f中中x2检验数检验数0系数列系数列系数列系数列均均0无无无无最优解最优解最优解最优解例例例例3 3用单纯形法求解线性规划问题用单纯形法求解线性规划问题046编
17、辑ppt解解解解: : 将该线性规划问题化为标准型：将该线性规划问题化为标准型：将该线性规划问题化为标准型：将该线性规划问题化为标准型：F=-f进行换基迭代，计算过程如表47编辑pptxBb111100612010801003-f33000011100601-110201003-f00-300-18x x1 1x4x x3 3x5x2x3x4x5x1x4x511非基变量有非基变量有检验数检验数0，有有检验数检验数=0无穷多个最优解无穷多个最优解无穷多个最优解无穷多个最优解其中一个最优解是其中一个最优解是x1 = 6 , x2=x3=x4=0 ,x5=3 最优值为最优值为f=-F=-18,F=186/18/148编辑ppt
