《线性规划模型ppt课件》由会员分享，可在线阅读，更多相关《线性规划模型ppt课件（18页珍藏版）》请在金锄头文库上搜索。
1、线性规划模型线性规划模型.线性规划的学习要求线性规划的学习要求知道线性规划模型的一般形式知道线性规划模型的一般形式会用图解法求解二个变量的线性规划问题会用图解法求解二个变量的线性规划问题会利用软件会利用软件LindoLindo求线性规划问题的最优解、最优求线性规划问题的最优解、最优值值会建立简单的线性规划问题会建立简单的线性规划问题.一、基本概念一、基本概念约束条件：约束条件： 1.线性规划模型的一般形式可以表示为：线性规划模型的一般形式可以表示为：目标函数目标函数 max(或或min)=clx1+c2x2+ + cnxn。非负条件：非负条件： x10, x20, , xn0.目目标函数函数
2、： max(或或min)= (或=，) bi，i=1，2，m约束条件：约束条件： 可简写为可简写为 ： 非负条件：非负条件： xj0，j=1，2，n.线性规划的特点：线性规划的特点：具有唯一的目标函数。具有唯一的目标函数。决策变量无论在目标函数还是在约束条件中出现都具决策变量无论在目标函数还是在约束条件中出现都具有幂为有幂为1的指数形式，并往往和一常数相乘。的指数形式，并往往和一常数相乘。目标函数或约束条件中都不包括决策变量的乘积项。目标函数或约束条件中都不包括决策变量的乘积项。目标函数和每个约束条件中决策变量的系数均为常数。目标函数和每个约束条件中决策变量的系数均为常数。决策变量之值可以是任
3、一实数。决策变量之值可以是任一实数。.说明：说明： 目标函数中的系数ci , i=1,2, ，n , 常称为价值系数，它反映某种价值如利润、收益或效益）；约束条件中的右端项bj，j=1,2, ，m等长称为右端系数，它反映某种资源的限制如劳动力、原材料等）；约束条件中的aij常称为技术系数。一般，它们都是已知的常数。.一个线性规划问题有解，是指能找出一组一个线性规划问题有解，是指能找出一组xjxjj=1j=1，2 2，n n），使其满足所有的约束条件和非负条件。），使其满足所有的约束条件和非负条件。称任何一组这样的称任何一组这样的xjxjj=1j=1，2 2，n n是线性规划是线性规划问题的一个
4、可行解。通常，线性规划问题含有多个问题的一个可行解。通常，线性规划问题含有多个可行解。称全部可行解的集合为该线性规划问题的可行解。称全部可行解的集合为该线性规划问题的可行域。使目标函数值达到最优的可行解称为该线可行域。使目标函数值达到最优的可行解称为该线性规划问题的最优解，最优目标函数值称为该线性性规划问题的最优解，最优目标函数值称为该线性规划问题的最优值。对不存在可行解的线性规划问规划问题的最优值。对不存在可行解的线性规划问题，称该线性规划问题无解。题，称该线性规划问题无解。.二、二、 两个变量的线性规划问题的图解法两个变量的线性规划问题的图解法第第1 1步：在平面上建立直角坐标系；步：在平
5、面上建立直角坐标系；第第2 2步：图示约束条件和非负条件，找出可行域；步：图示约束条件和非负条件，找出可行域；第第3 3步：图示目标函数，并寻找最优解。步：图示目标函数，并寻找最优解。.例：例： max z=l00x1+80x2约束条件约束条件 4x1+2x2400 2x1+4x2500 非负条件：非负条件： xl0, x20 .唯一最优解求最大值示意图唯一最优解求最大值示意图.三、线性规划的软件三、线性规划的软件lindo实现实现LINDO 是是 Linear INteractive Discrete Optimizer的缩写，是一个线性和整数规划的软件系的缩写，是一个线性和整数规划的软件系
6、统。最大规模的模型的非零系数可以达到统。最大规模的模型的非零系数可以达到1,000,000个，最大变量个数可以达到个，最大变量个数可以达到100,000个，最大目标函个，最大目标函数和约束条件个数可以达到数和约束条件个数可以达到32000个，最大整数变量个，最大整数变量个数可以达到个数可以达到100,000个。它的特点是采用交互方式个。它的特点是采用交互方式操作，而且命令简单明了，很容易掌握。用户在输入操作，而且命令简单明了，很容易掌握。用户在输入初步的数学模型后，可以一边运行，一边修改调试，初步的数学模型后，可以一边运行，一边修改调试，直至获得满意的结果。直至获得满意的结果。.LINDO既是
7、一个实用的求解大规模线性和整数规划系既是一个实用的求解大规模线性和整数规划系统，也很适用于训练的目的，用来培养学生面对较复统，也很适用于训练的目的，用来培养学生面对较复杂的实际问题，构造线性及整数规划模型以及求解这杂的实际问题，构造线性及整数规划模型以及求解这些问题的能力。限于本教材的内容，本手册只介绍有些问题的能力。限于本教材的内容，本手册只介绍有关线性规划和整数规划的基本内容，省略了有关二次关线性规划和整数规划的基本内容，省略了有关二次规划、参数规划以及有关线性规划算法的比较专门的规划、参数规划以及有关线性规划算法的比较专门的内容。内容。.1.1 LINDO 命令一览表命令一览表1、查询类
8、(Information)HELP 求助COM ( Command )命令列表LOCAL 当前版本信息CAT ( Categories )命令分类TIME 显示当前时间DATE显示当前日期.8、整数规划、二次规划和参数规划 ( Integer, Quadratic and Parametric Programs )INT定义一个0-1变量QCP*(Quadratic Programming)定义二次规划PARA*(Parametric Programming)求解参数规划POSD*(Positive Definiteness)检查二次规划矩阵的正定性TITAN*紧缩连续变量的上界以及0-1变量
9、的系数BIP*整数规划中给出一个剪枝的界GIN （General Integer）定义一个整数变量IPTOL*设定整数规划最优解的宽容度 .(1)(1)模型中出现的关键词只能是模型中出现的关键词只能是 MAX ( MAX (或或 MIN ) MIN )， ST ( ST (或或 SUBJECT TO )SUBJECT TO )和和 END END。关键词中不能含有空格。关键词中不能含有空格。MAX ( MAX ( 或或 MIN ) MIN )， ST ( ST (或或 SUBJECT TO ) SUBJECT TO )的右面至少要有一个空的右面至少要有一个空格，关键词中字符大写和小写都合法的。
10、格，关键词中字符大写和小写都合法的。(2)(2)变量名不超过变量名不超过8 8个字符，其中第一个字符必须定字母，个字符，其中第一个字符必须定字母，其余的可以是字母或数字。这样就可以藉助变量表示变量其余的可以是字母或数字。这样就可以藉助变量表示变量的实际含义。例如有的实际含义。例如有1010种燃料，可以分别记为种燃料，可以分别记为FUEL01FUEL01，FUEL10FUEL10等。等。(3)(3)不等号用不等号用 表示表示，用，用 表示表示。要注意的。要注意的是当模型是当模型( (用用 LOOK LOOK 命令命令) )输出输出( (到屏幕或打印机到屏幕或打印机) )时，不等时，不等号分别写成
11、号分别写成 和和 。(4)(4)目标函数中不能出现常数项，也不能出现等式，例如目标函数中不能出现常数项，也不能出现等式，例如: :MAX 2X1MAX 2X13X23X25 5 和和 MAX Z=2X1 MAX Z=2X13X23X2都是非法的。都是非法的。.(5)无论连目标函数(第一行)或约束条件中，都不能出现括号、乘号。例如:MAX2(X1+X2)和 MIN 2*X1+3*X2都是非法的。(6)在约束条件中，变量必须在关系符左面，常数必须在关系符右边，例如:3X14X230 和 3X134X2 都是非法的。(7)模型中系数必须写成整数或小数形式而不能写成指数形式，例如：下列系数的记法是非法
12、的： .258E+5。如系数是小数形式，输入的位数限制定整数最大6位，小数最大5位。(8) 变量的非负约束是隐含的，不需要在模型中加以意义。.LINDO/PC 5.3 2019 LINDO SYSTEMS INC.1MAX 4 X1 + X2 - X3 + 2 X42ST3X1 X2 + X3 - X4 = 3043 X1 + X2 - X3 + 2 X4 = 365X1 + 2 X2 + X3 2 X4 = 206END.23 - Exit with compile - Exit without compile.OBJECTIVE FUNCTION VALUE1)12737.0600(此即为我们要求的目标函数的最大值VARIABLEVALUEREDUCED COSTX1 294.117600.000000X21500.000000.000000 X3 0.0000001.414647X4 58.823530.000000ROWSLACKDUAL PRICES2).0000001.9535293).000000 .2423534).0000001.378236.
