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