《线性规划模型》PPT课件

《《线性规划模型》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划模型线性规划的学习要求知道线性规划模型的一般形式会用图解法求解二个变量的线性规划问题会利用软件Lindo求线性规划问题的最优解、最优值会建立简单的线性规划问题一、基本概念约束条件：线性规划模型的一般形式可以表示为：目标函数max(或min)=clx1+c2x2+…+cnxn。非负条件：x1≥0,x2≥0,…,xn≥0目标函数：max(或min)=≤(或=，≥)bi，i=1，2，…，m约束条件：可简写为：非负条件：xj≥0，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步：图示目标函数，并寻找最优解。例：maxz=l00x1+80x2约束条件4x1+2x2≤4002x1+4x2≤500非负条件：xl≥0,x2≥0唯一最优解（求最大值）示意图三、线性规划的软件lindo实现L

4、INDO是LinearINteractiveDiscreteOptimizer的缩写，是一个线性和整数规划的软件系统。最大规模的模型的非零系数可以达到1,000,000个，最大变量个数可以达到100,000个，最大目标函数和约束条件个数可以达到32000个，最大整数变量个数可以达到100,000个。它的特点是采用交互方式操作，而且命令简单明了，很容易掌握。用户在输入初步的数学模型后，可以一边运行，一边修改调试，直至获得满意的结果。LINDO既是一个实用的求解大规模线性和整数规划系统，也很适用于训练的目的，用来培养学生面对较复杂的实际问题，构造线性及整数规

5、划模型以及求解这些问题的能力。限于本教材的内容，本手册只介绍有关线性规划和整数规划的基本内容，省略了有关二次规划、参数规划以及有关线性规划算法的比较专门的内容。1.1LINDO命令一览表1、查询类(Information)HELP求助COM(Command)命令列表LOCAL当前版本信息CAT(Categories)命令分类TIME显示当前时间DATE显示当前日期8、整数规划、二次规划和参数规划(Integer,QuadraticandParametricPrograms)INT定义一个0-1变量QCP*(QuadraticProgramming)定义二

6、次规划PARA*(ParametricProgramming)求解参数规划POSD*(PositiveDefiniteness)检查二次规划矩阵的正定性TITAN*紧缩连续变量的上界以及0-1变量的系数BIP*整数规划中给出一个剪枝的界GIN（GeneralInteger）定义一个整数变量IPTOL*设定整数规划最优解的宽容度(1)模型中出现的关键词只能是MAX(或MIN)，ST(或SUBJECTTO)和END。关键词中不能含有空格。MAX(或MIN)，ST(或SUBJECTTO)的右面至少要有一个空格，关键词中字符大写和小写都合法的。(2)变量名不超过

7、8个字符，其中第一个字符必须定字母，其余的可以是字母或数字。这样就可以藉助变量表示变量的实际含义。例如有10种燃料，可以分别记为FUEL01，…，FUEL10等。(3)不等号用"＜"表示"≤"，用"＞"表示"≥"。要注意的是当模型(用LOOK命令)输出(到屏幕或打印机)时，不等号分别写成"＜＝"和"＞＝"。(4)目标函数中不能出现常数项，也不能出现等式，例如:MAX2X1＋3X2＋5和MAXZ=2X1＋3X2都是非法的。(5)无论连目标函数(第一行)或约束条件中，都不能出现括号、乘号。例如:MAX2(X1+X2)和MIN2*X1+3*X2都是非法的。(6

8、)在约束条件中，变量必须在关系符左面，常数必须在关系符右边，例如:3X1＋4X2