2011第五章化工过程系统优化方法 -线性

1、5.4 线性规划及其应用,5.4.1 线性规划问题的数学模型 （一）引言 线性规划是运筹学的重要分支之一，也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自1947年线性规划被成功的运用于工业、交通、农业和军事等各个领域后。随着计算机的普及，它的适应领域越来越广泛。 研究内容 (1) 是一项任务确定后，如何统筹安排，尽量作到用最少的人力物力资源去完成这一任务。 (2) 是已有一定数量的人力物力资源，如何安排使用他们，使得完成任务最多,此外, 大量复杂的化工优化问题, 简化为线性规划问题 进行求解,目标函数及约束条件均为线性函数,整体指标最优的问题 1.运输问题 2.生产的组织与计划问题

2、 3.合理下料问题 4.配料问题 5.布局问题 6.分配问题,二）线性规划问题的数学模型,1.运输问题 设有两个化工厂a1、a2。其产量分别为23万桶与27万桶产品。它们生产的产品可供应b1、b2、 b 3三个工厂。其需要量分别为17万桶、18万桶和15万桶。自各产地到各工厂的运价格如下表：问应如何调运，才使总运费最省,解：设 xi j表示由工厂ai 运往工厂 bj 的产品数量(万桶) （i=1,2；j=1,2,3,目标函数,约束条件,2.生产的组织与计划问题 某化工厂生产a 、b两种产品，现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利

3、润最大,单位产品 产品,耗用资源,解：假设生产a产品x1吨， b产品x2吨. 得到利润7 x1 +12 x2万元，这一问题的数学模型为,约束条件,目标函数,从数学上共同特征： 每一个问题都是求一组变量（称为决策变量）的值。 代表一个具体方案, 通常要求变量的取值是非负的。 存在一定的限制条件(称为约束条件)。 这些约束条件都可以用一组线性等式或不等式来表示。 都有一个期望达到的目标，并且这个目标可以表示为 决策变量的线性函数（称为目标函数）。 我们将具有上述三个特点的最优化问题归结为线性规划问题，其数学模型简称线性规划数学模型,线性规划问题的数学模型的一般形式,1）式称为目标函数 （2）式中等

4、式或不等式称为约束条件 （3）式是非负约束条件 x1 , x2, ,xn称为决策变量，简称变量,满足约束条件的一组变量的值,称为线性规划问题的一个可行解; 使目标函数取得最大（或最小）的可行解称为最优解。 此时， 目标函数的值称为最优值,建立线性规划数学模型的步骤 首先，确定决策变量。 线性规划的数学模型建得是否容易，求解是否方便，取决于决策变量的选取是否得当。 其次，确定约束条件，并根据实际问题添加非负条件。 明确问题中所有的限制条件，并用决策变量的线性等式或不等式表示。 最后，确定目标函数，并确定是求极大还是求极小。 用决策变量的线性函数来表示实际问题所要达到的目标，得到目标函数,5.4.

5、2线性规划问题的图解法,例1 求x1、x2的值，使它们满足,并且使目标函数f =2 x1+5x2的值最大,图解法是利用直观的几何图形求解线性规划的一种几何解法,x1,2x1+5x2=19,2x1+5x2=15,2x1+5x2=8,2x1+5x2=4,x2=3,x1=4,x1+2x2=8,0,x2,最优解为 x1=2，x2=3 相应的目标函数的最大值为 s=2*2+5*3=19,x1,x1+2x2=8,x1+2x2=6,x1+2x2=2,x1+2x2=0,x2=3,x1=4,x1+2x2=8,0,x2,例 2 若把例1的目标函数改为 s= x1+2x2 ，则,最优解有 无穷多个, 它们对应的目标

6、函数值都是 8,例 3 求x1、x2的值，使它们满足,并且使目标函数s=2 x1+2x2的值最小,x1,x2,0,x1-x2=1,x1+2x2=0,2x1+2x2=2,2x1+2x2=6,2x1+2x2=10,2x1+2x2=16,最优解 x1=1，x2=0, 目标函数最小值 s=2,解,例 4 求x1、x2的值，使它们满足,并且使目标函数s=2 x1+2x2的值最小,x1,x2,x1 + x2 =1,没有可行解，当然没有最优解,解,x1 + x2 = -2,一）线性规划问题的标准形式,线性规划问题的标准型是,5.4.3 单纯形法,约束条件（2）式又称等式约束（3）式称非负约束,注：有的书上是

7、最小值max,min f,标准型的特点为 （1）目标函数为最大（小）值形式 （2）约束条件用等式表示且等 式右端的常数为非负值 （3）决策变量非负,线性规划问题的标准化的方法如下,1. 求目标函数的最小值,令 f= - f ，则可将求f的最大值问题转化求f的最小值成问题， 即,2. 约束条件为不等式 引入一个非负变量 xn+i，将不等式转化为线性等式，若需加上一个非负变量xn+i, 则称xn+i 为松弛变量,即若 ai1x1+ai2x2+ainxnbi,松弛变量,3. 若有bi0 可在该约束条件两边同乘 -1，化为,4.如果有某个变量xj 无非负约束 可引进非负变量xj, xj ， 令xj =

8、xj - xj 代入约束条件和目标函数中,剩余变量,若需减去上一个非负变量xn+k, 则称xn+k 为剩余变量. 即,例 1 将下面的线性规划问题化成标准型,解: 引进松弛/剩余变量 x40 , x5 0 ，将不等式约束条件变换成 等式约束条件,将 3x1-x2 -2x3 =-5 两边同乘 -1，变为 -3x1+x2 +2x3 =5,变量x3无非负约束，引进非负变量x6, x7， 令x3 = x7 - x6 ，代入约束条件和目标函数。得,最后，若要求目标函数为最大值, 则令f =- f ，则可将求f的最小值问题转化成求f的最大值问题。 (注: 目标函数可根据要求为最小或最大,本题要求最大,标准

9、型为,二）、基本概念,基变量: 在线性规划的标准型中，如果有变量只在某一个 约束方程中系数为1，在其余约束方程中系数全 为0，则称之为该约束 的一个基变量. 2. 典型方程组: 如果每个等式约束都有一个基变量，则称 等式约束条件是这些基变量的典型方程组,如果线性规划的约束条件是典型方程组，不失一般性，设n 个变量的线性规划问题的典型方程组为,其中 x1 , x2 , , xm 称为基变量， xm+1 , xm+2 , , xn称为非基变量。令非基变量xm+1 =0, xm+2 =0, xn =0 ，则可求得约束方程的一个解： x1 = b1, x2 = b2, , xm = bm , xm+1

10、 =0 , xm+2 =0, , xn =0 称为基本解。如果bi0( i=1,2,m )则称此基本解为基本可行解,三)、单纯形法 1单纯形法的基本思想 单纯形法的基本思路是：根据标准型，从可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函数值逐步变优，当目标函数值达到最大/最小值时，就得到问题的最优解,下面举例说明单纯形法的基本思想例 求解线性规划问题,解 先将问题化成标准型（引入松弛变量x4,x5,显然 x4 , x5为基变量， x1 , x2 , x3为非基变量， 约束条件是典型方程组。由（1）可得,将（2）代入目标函数可得 f = 2x1 +3 x2 + x3 +0 x4

11、+0 x5 , 令非基变量 x1 = x2 = x3 =0 则有 f = 2x1 +3 x2 +1x3 + 0 = 0 , 同时得到一个基本可行解 x1 = x2 = x3 =0 ,x4=1, x5=3 或 (0,0,0,1,3)t,分析: 由f = 2x1 +3 x2 + x3 +0可知， 非基变量的系数都是正数，若将其中任意一个非基变量变成基变量（取值从0变成正数）,都可以使目标函数值增加. 所以, 只要在目标函数的表达式中还存在有正系数的非基变量，就表示目标函数值还有增加的可能，就不是最优解，就需要将非基变量与基变量进行对换,x4 , x5为基变量， x1 , x2 , x3为非基变量,

12、本例f = 2x1 +3 x2 + x3 +0为 x2, 以求得目标函数值较快的增大 故 , 将x2换入到基变量中。 ） 同时，还要确定基变量中有一个要换出来成为非基变量,采用最小比值原则,进基: 把非基变量转换为基变量称为。 一般选择目标函数中正系数最大的那个非基变量为进基变量,出基:变量由基变量转化成非基变量称为,x2 为进基变量， x1, x3仍为非基变量， 故x1, x3的值为零。 代入（2）式可得,随着x2的值增加， x4, x5的值会逐渐变小,怎样确定出基变量 ,才能保证x40, x50 （即解的可行性）。 当x2 =9/4时， x5=0。即用 x2替换x5 （ x5出基）. 于是

13、得到新的基变量x4, x2 , 非基变量x1, x3 , x5 。 这种确定出基变量的方法称为最小比值原则,由（2）式写出用非基变量表示基变量的表达式,整理得,代入目标函数得 f= 7/4+5/4 x1 -17/4 x3 9/4 x5 令非基变量x1 = x3 = x5 =0 得一新的基本可行解 x1 =0, x2 =9/4, x3 =0, x4 =1/4, x5 =0 代入目标函数 得相应的目标函数值 f= 7/4,基变量x4, x2 基变量x1, x3 , x5,式中所有非基变量的系数均是负数，意味着目标函数值不可能再增加，故此时的基本可行解就是最优解，最优值 为8,非基变量x1的系数是正

14、数，说明目标函数值还可能增加，于是再用上述方法，确定进基、出基变量，又得到另一个基本可行解 x1 =1, x2 =2, x3 =x4 =x5 =0 f=2* 1+3*2=8 用非基变量表示目标函数 f= 8 - 3x3 5x4 - 1x5,单纯形法求解线性规划问题的基本计算步骤,1) 将线性规划问题转换为标准型,2) 确定基变量和非基变量, 并令非基变量为零, 计算基变量的值, 得到一组可行解,3) 选定新的基变量和非基变量,a,选择目标函数中正系数最大的那个非基变量 (进基变量)为新的基变量,b. 采用最小比值原则, 选定新的非基变量(出基变量,4) 重复2)-3) 直到 目标函数中变量系数

15、均为负数 (求最大值问题,2最优性检验 由标准形等式约束条件得,代入目标函数进行简单的运算后，用非基变量表示目标函数为,称为非基变量,的检验数,将,用检验数来判定线性规划问题是否有最优解有最优解定理,定理 (1)如果关于非基变量的所有检验数,则基本可行解就是最优解,2)如果关于非基变量的所有检验数,且其中有一个非基变量xm+k的检验数为零则该线性规划问题有无穷多个最优解,3)如果存在非基变量xm+k 的检验数0 且xm+k对应的系数列均小于等于零 则该线性规划问题无最优解,3. 单纯形表法,用表格的形式来表示求解线性规划问题的单纯形法的计算过程, 称为. 可以使计算和检验更加简便,具体方法如下

16、： （） 将目标函数式改写为-f+ c1 x1 + c2 x2 + cnxn =0 且作为等式约束方程组的第m+1个方程，得,对方程组的增广矩阵施行初等行变换，化为如下的 阶梯形矩阵,将矩阵表示成单纯形表,x1,x2,xm,xm+1,xn,x1,x2,xm,b1,b2,bm,a1m+1,a2m+1,amm+1,a1n,a2n,amn,下面通过具体的例子说明用单纯形法求解线性规划问题,例1 用单纯形法解线性规划问题,解 将该线性规划问题化为标准型,显然x3 , x4 , x5为基变量， x1 , x2为非基变量。可得单纯形表。这种直接从线性规划问题得到的单纯形表称为初始单纯形表,x1,x5,初始

17、基本可行解为 x1 = x2 =0 , x3 =12 ,x4 =8 ,x5 =16,注 用最小比值原则确定出基变量的一般方法是： 在单纯形表中，b列元素与进基变量列对应的正元素之比，取其比值最小的所对应的基变量出基。 x2 x4,12/2,8/2,目标函数中系数最大对应的变量x2为进基变量,注：比值相等时可任选其一,x1,x2,x3,x4,x5,x3,x2,x1,1/4,非基变量的检验数小于0,最优解为x1 =4 x2 =2 x3 =0,x4=x5=0 目标函数值为f=14,4,5,例2 用单纯形法求解线性规划问题,解 x3 , x4为基变量， x1 , x2为非基变量。可得初始单纯形表,x1,x3,x4,x2,x3