数学建模培训——线性规划
在生产和经营管理中经常提出如何合理安排，使人力，物力等各种资源得到充分利用，获得最大效益，这类问题称为数学规划（优化）问题．
1．如果统筹兼顾，合理安排，用最少的资源(如资金，设备，原材料，人工，时间)去完成确定的目标和任务；
2．在一定的资源条件限制下，如何组织安排生产以获得最大的经济效益(如产量最多，利润最大)．
一、线性规划的基本概念 1．实例 利润最大化问题
某工厂用3种原料P1，P2，P3生产3种产品Q1，Q2，Q3．已知的生产条件如下表所示，试制订出总利润最大的生产计划．
表 单位产品所需原材料的数量
原料 P1 P2 P3 单位产品的利润/万元 解：maxz?3x1?5x2?4x3
产品 Q1 2 0 3 3 Q2 3 2 2 5 Q3 0 4 5 4 原材料可用量/（千克·日-1） 1500 800 2000 s.t. 2x1?3x2?1500, 2x2?4x3?800, 3x1?2x2?5x3?2000, xj?0,j?1,2,3.2．概念 （1）线性规划问题(linear programming ,简记为LP)：求多变量线性函数在线性约束条件下的最优值
（2）线性规划问题的一般形式：
max(min) z?c1x1?c2x2?s.t. a11x1?a12x2? a21x1?a22x2? am1x1?am2x2? x1,x2,其中x?(x1,x2,?cnxn?a1nxn?(?,?)b1,?a2nxn?(?,?)b2,?amnxn?(?,?)bm,
,xn?0.,xn)称为决策变量(decision variable)，z称为目标函数
(objective function)．约束条件所确定的x的范围称为可行域，满足约束条件的解x称为可行解，同时满足目标函数和约束条件的解x称为最优解(optimal solution)，整个可行域上的最优解称为全局最优解(global optimal solution)，可行域中某个邻域上的最优解称为局部最优解
?(local optimal solution)．最优解所对应的目标函数值称为最优值(optimum)．
若令
?a11?aA??21???am1a12a22am2a1n??a2n? ，x?(x1,x2,??amn?,xn)T ，c?(c1,c2,,cn)T，
b?(b1,b2,,bm)T，则
min cTxAx?b, x?0.（3）线性规划的规范形式为：
（4）线性规划的标准形式为：
min cTxAx?b, x?0.（5）决策变量为整数时，称为整数线性规划；决策变量取0或1时，称为0-1线性规划． （6）规划问题的三要素：决策变量，目标函数，约束条件 （7）线性规划模型的求解步骤 二、线性规划问题的求解 1．单纯形法
（1）线性规划问题的解的性质
线性规划问题的可行域是一个凸多边形．
线性规划问题如果存在最优解，则最优解必在可行域的顶点处达到．
（2）单纯形法: 从可行域的一个顶点（基本可行解）出发，转换到另一个顶点，并且使目标函数值逐步减小，有限步后可得到最优解．
2．软件求解——借助于Lingo和Matlab可以求解规划问题． 3．Lingo求解线性规划模型 LINGO的基本语法：
（1）以model：开始，以end结束（可省略）； （2）目标函数直接记作“max=”、“min=”； （3）约束条件符号“s．t．”不出现；
（4）每一语句必须以英文状态下的分号“；”结尾；
（5）变量名称不区分大小写，以字母开头，可含数字和下划线； （6）所有变量都假定是非负的，不必再另外输入非负变量约束条件； （7）“>”代替“>=”，“<”代替“<=”； （8）注释语句以感叹号“！”开始，以分号“；”结束； （9）每行可有多个语句，语句可以断行． 实例的求解程序： model:
max=3*x1+5*x2+4*x3;
2*x1+3*x2<1500; 2*x2+4*x3<800;
3*x1+2*x2+5*x3<2000; end
Lingo的求解器运行状态窗口
求解器状态
变量数量
变量总数 非线性变量数 整数变量数 约束总数
非线性约束个数 总数
非线性系数个数 内存的使用量 求解花费的时间
当前模型类型
当前解的状态 当前目标函数值
当前约束不满足的总量
目前为止迭代次数 使用的特殊求解程序 目前可行解的最佳目标函数值
目标函数值的界
特殊求解程序当前运行步数
有效步数
约束数量 非零系数数量
扩展求解器状态
图 Lingo的求解器状态窗口
注：1．Model Class（当前模型类型）包括：LP 线性规划；QP 二次规划；ILP 整数线性规
划，IQP 整数二次规划；PILP 纯整数线性规划；NLP 非线性规划；MIP 混合整数规划，INLP整数非线性规划，PINLP纯整数非线性规划．
2．State（解的状态）包括：Global Optimum全局最优解；Local Optimum局部最优解；Feasible 可行解；Infeasible不可行解；Unbounded无界解；Interrupted中断；Undetermined 未确定． 三、经典的线性规划模型 1．下料问题
现有一批长度为7.4m的钢管，由于生产的需要，要求截出规格为2.9m，2.1m和1.5m的钢管．数量分别为1000根，2000根和1000根．请问应该如何下料（即截取原材料钢管），才能既满足生产的需求，又使得消耗原材料钢管的数量或浪费的材料最少？
表 钢管下料数据计算表 钢管规格/m 2.9 2.1 1.5 残料长度/m 下料方式 B1 2 0 1 0.1 B2 1 0 3 0 B3 1 2 0 0.3 B4 1 1 1 0.9 B5 0 2 2 0.2 B6 0 1 3 0.8 B7 0 3 0 1.1 B8 0 0 4 1.4 需求量/根 1000 2000 1000 min z?x1?x2?x3?x4?x5?x6?x7?x8 2x1?x2?x3?x4?1000, 2x3?x4?2x5?x6?3x7?2000, x1?3x2?x4?2x5?3x6?4x8?1000.model:
min=x1+x2+x3+x4+x5+x6+x7+x8; 2*x1+x2+x3+x4>1000;
2*x3+x4+2*x5+x6+3*x7>2000; x1+3*x2+x4+2*x5+3*x6+4*x8>1000; end
2．运输问题
某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）以及各工厂到各销售点的单位运价（元/吨）示于下表中．问产品如何调运才能使总运费最小．
表 单位运价表 销地 产地 A1 A2 A3 销量 B1 2 1 8 3 B2 9 3 4 8 B3 10 4 2 4 B4 2 2 5 6 产量 9 5 7 解：设第i产地运往第j销地的产品数量为xij，单位运费为cij，第i产地的产量为ai，第j销地销售量为bj，其中i?1,2,3;j?1,2,3,4.
min z???cijxiji?1j?134?xj?134ij?ai,i?1,2,3,?bj,j?1,2,3,4,
?xi?1ijxij?0.model: sets:
chandi/1..3/:a; xiaodi/1..4/:b;
feiyong(chandi,xiaodi):c,x; endsets
min=@sum(feiyong(i,j):c(i,j)*x(i,j));
@for(chandi(i):@sum(xiaodi(j):x(i,j))=a(i)); @for(xiaodi(j):@sum(chandi(i):x(i,j))=b(j)); data: a=9,5,7; b=3,8,4,6; c=2,9,10,2 1,3,4,2 8,4,2,5; enddata end
四、Lingo 1.集合
定义集合需要明确三方面内容：集合的名称、集合内的成员（组成集合的个体，即元素）、集合的属性（可以看成是与该集合有关的变量和常量）．
集合定义语法：集合名称/成员列表/：属性1，属性2，…，属性n；
其中成员列表可采用显式罗列（成员之间用逗号或空格隔开）或隐式罗列（首末两个成员之间用“．．”省略号连接） 派生集合的定义语句有以下要素组成：集合的名称、对应的初始集合、集合的成员（可以省略不写）、集合的属性（可以省略）．
派生集合定义语法：派生集合名称（集合名称1，集合名称2）：属性1，…，属性n； 集合的定义部分以语句sets:开始，endsets结束．即：
线性规划
