第五节 线性规划建模举例

线性规划模型及其举例摘要：在日常生活中，我们常常对一个问题有诸多解决办法，如何寻找最优方案，成为关键，本文提出了线性规划数学模型及其举例，在一定约束条件下寻求最优解的过程，目的是想说明线性规划模型在生产中的巨大应用。

关键词：资源规划；约束条件；优化模型；最优解在工农业生产与经营过程中，人们总想用有限的资源投入，获得尽可能多的使用价值或经济利益。

如：当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多，利润最大）。

一.背景介绍如果产出量与投入量存在（或近似存在）比例关系，则可以写出投入产品的线性函数式：1()ni ij j j f x a x ==∑，1,2,,,1i m m =+ (1)若将（1）式中第（1m +）个线性方程作为待求的目标函数，其余m 个线性方程作为资源投入的限制条件（或约束条件），则（1）式变为：OPT. 1()nj j j f x c x ==∑ST. 1nij j j a x =∑> ( =, < )i b , 1,2,,i m = (2)0,j x ≥ 1,2,,j n =…（2）式特点是有n 个待求的变量j x （1,2,,j n =…）；有1个待求的线性目标函数()f x ，有m 个线性约束等式或不等式，其中i b （1,2,,i m =…）为有限的资源投入常量。

将客观实际问题经过系统分析后，构建线性规划模型，有决策变量，目标函数和约束条件等构成。

1．决策变量（Decision Variable,DV ）在约束条件范围内变化且能影响（或限定）目标函数大小的变量。

决策变量表示一种活动，变量的一组数据代表一个解决方案，通常这些变量取非负值。

2．约束条件（Subject To,ST ）在资源有限与竞争激烈的环境中进行有目的性的一切活动，都应考虑是否符合实际，有没有可行性，因而要构造基于科学预测的综合性约束（或限定）条件。

第一章 线性规划§1 线性规划在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。

此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。

自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。

特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

1.1 线性规划的实例与定义例1某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。

生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。

若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足（目标函数）2134m ax x x z += (1)s.t.（约束条件）⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0,781022122121x x x x x x x （2）这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。

由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。

而选适当的决策变量，是我们建立有效模型的关键之一。

1.2 线性规划的Matlab 标准形式线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。

第五节线性规划建模举例线性规划是一种操作研究的数学方法，广泛应用于商业、经济、工程领域中的优化问题。

线性规划建模是将实际问题描述为线性规划模型的过程。

本节将介绍几个线性规划建模的典型例子。

例1：混合饲料配方问题某饲料厂要生产一种混合饲料，需包括以下六种饲料成分：大豆粉、面粉、玉米、鱼粉、鸡粉、牛粉，并且要求这种混合饲料包含不少于25%的蛋白质和不多于15%的纤维素。

每吨饲料的生产成本和含量如下：| 饲料成分 | 成本（元/吨） | 蛋白质含量（%） | 纤维素含量（%） || -------- | ------------- | -------------- | -------------- || 大豆粉 | 200 | 45 | 10 || 面粉 | 100 | 10 | 2 || 玉米 | 150 | 8 | 5 || 鱼粉 | 300 | 60 | 0 || 鸡粉 | 280 | 50 | 2 || 牛粉 | 320 | 70 | 5 |问如何使得生产的混合饲料成本最小，同时满足蛋白质含量不少于25%和纤维素含量不超过15%的要求。

自变量：混合饲料中每种成分的含量。

目标函数：最小化混合饲料的成本。

约束条件：1. 蛋白质含量不少于25%：0.45×x1 + 0.1×x2 + 0.08×x3 + 0.6×x4 + 0.5×x5 + 0.7×x6 ≥ 0.25。

2. 纤维素含量不超过15%：0.1×x1 + 0.02×x2 + 0.05×x3 + 0×x4 + 0.02×x5 + 0.05×x6 ≤ 0.15。

3. 非负性：x1, x2, x3, x4, x5, x6 ≥ 0。

其中，x1，x2，x3，x4，x5，x6 分别表示大豆粉、面粉、玉米、鱼粉、鸡粉和牛粉的含量，单位为吨。

数学建模教案－线性规划模型一、问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。

例1 若需在长为4000mm的圆钢上，截出长为698mm和518mm两种毛坯，问怎样截取才能使残料最少？初步分析可以先考虑两种“极端”的情况：（1）全部截出长为698mm的甲件，一共可截出EQ F(4000,698) »5件，残料长为510mm。

（2）全部截出长为518mm的乙件，一共可截出 E Q F(4000,518) »7件，残料长为374mm。

由此可以想到，若将 x个甲件和y 个乙件搭配起来下料，是否可能使残料减少？把截取条件数学化地表示出来就是：698 x + 518y £ 4000x ，y都是非负整数目标是使：z = EQ F(698x + 518y,4000) （材料利用率）尽可能地接近或等于1。

（尽可能地大）该问题可用数学模型表示为：目标函数： max z = EQ F(698x + 518y,4000)满足约束条件：698 x + 518y £ 4000 ， (1)x ，y都是非负整数 . (2)例2 某工厂在计划期内要安排生产I 、II两种产品，已知生产单位产品所需的设备台数及A、B两种原料的消耗，如下表所示。

该工厂每生产一件产品I可获利 2 元，每生产一件产品II可获利 3 元，问应如何安排生产计划使工厂获利最多？这问题可以用以下的数学模型来描述：设 x 1, x 2分别表示在计划期内产品I、II的产量。

因为设备的有效台数为8 ，这是一个限制产量的条件，所以在确定I 、II的产量时，要考虑不超过设备的有效台数，即可用不等式表示为：x 1 + 2x 2£ 8 .同理，因原材料A 、B的限量，可以得到以下不等式：4 x 1£ 164 x 2£ 12.该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1、x2以得到最大的利润。

数学建模培训——线性规划在生产和经营管理中经常提出如何合理安排，使人力，物力等各种资源得到充分利用，获得最大效益，这类问题称为数学规划（优化）问题．1．如果统筹兼顾，合理安排，用最少的资源(如资金，设备，原材料，人工，时间)去完成确定的目标和任务；2．在一定的资源条件限制下，如何组织安排生产以获得最大的经济效益(如产量最多，利润最大)．一、线性规划的基本概念 1．实例 利润最大化问题某工厂用3种原料P 1，P 2，P 3生产3种产品Q 1，Q 2，Q 3．已知的生产条件如下表所示，试制订出总利润最大的生产计划．表 单位产品所需原材料的数量解：123x 354ma x x z x ++=1223123s.t. 231500,24800,3252000,0,1, 2,3.j x x x x x x x x j +≤+≤++≤≥=2．概念 （1）线性规划问题(linear programming ,简记为LP )：求多变量线性函数在线性约束条件下的最优值（2）线性规划问题的一般形式：11221111221121122222112212max(min) s.t. (,), (,),(,),,,,0.n nn n n n m m mn n m n z c x c x c x a x a x a x b a x a x a x b a x a x a x b x x x =++++++≤=≥+++≤=≥+++≤=≥≥其中12,,(,)n x x x x =称为决策变量(decision variable)，z 称为目标函数(objective function)．约束条件所确定的x 的范围称为可行域，满足约束条件的解x 称为可行解，同时满足目标函数和约束条件的解x *称为最优解(optimal solution)，整个可行域上的最优解称为全局最优解(global optimal solution)，可行域中某个邻域上的最优解称为局部最优解(local optimal solution)．最优解所对应的目标函数值称为最优值(optimum)．若令111212122212n n m m mn a a a a a a a a a A ⎛⎫ ⎪ ⎪= ⎪ ⎪⎝⎭，T 12,,(,)n x x x x = ，T 12,,(,)n c c c c =，T 12,,(,)m b b b b =，则（3）线性规划的规范形式为：T min ,0.c x Ax b x ≥≥ （4）线性规划的标准形式为：T min ,0.c x Ax b x =≥ （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; endLingo 的求解器运行状态窗口图 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根．请问应该如何下料（即截取原材料钢管），才能既满足生产的需求，又使得消耗原材料钢管的数量或浪费的材料最少？2345678123431456712456821000, 2232000,3mi 2341n 000 .z x x x x x x x x x xx x x x x x x x x x x x x ++++++++++≥++++≥+++++≥=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; end2．运输问题某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售点的销售量（假定单位均为吨）以及各工厂到各销售点的单位运价（元/吨）示于下表中．问产品如何调运才能使总运费最小．解：设第i 产地运往第j 销地的产品数量为ij x ，单位运费为ij c ，第i 产地的产量为i a ，第j 销地销售量为j b ，其中1,2,3;1,2,3,4.i j ==34114131min ,1,2,3,,1,2,3,4,0.ij iji j iji j ijj i ij z c x xa i xb j x =========≥∑∑∑∑model : sets :chandi/1..3/:a; xiaodi/1..4/:b;feiyong(chandi,xiaodi):c,x; endsetsmin =@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 结束．即：sets:集合名称1/成员列表1/：属性1_1，属性1_2，…，属性1_n1；集合名称2/成员列表2/：属性2_1，属性2_2，…，属性2_n2；派生集合名称（集合名称1，集合名称2）：属性3_1，…，属性3_n3；endsets2.数据数据部分的语法为data:属性1=数据列表；属性2=数据列表；enddata注：在数据段中，=右侧不能出现运算，故不能出现分数，如3/8，这里的/表示除法运算．（1）通过复制粘贴传递数据（2）从文本文件传递数据◆从文本文件导入数据命令：@file(’fname.txt’)，其中文本文件fname.txt应与LINGO程序文件在同一目录中.◆将程序执行结果导出到文本文件中命令：@text(’fname.txt’)=决策变量名如无特别指定，文本文件fname.txt将被默认保存在LINGO程序文件的当前工作目录中.如运输问题中实例Lingo程序为：model:sets:chandi/1..3/:a;xiaodi/1..4/:b;feiyong(chandi,xiaodi):c,x;endsetsmin=@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=@file(yunshuwt.txt);b=@file(yunshuwt.txt);c=@file(yunshuwt.txt);@text(yunshuwtx.txt)=@table(x);!把计算结果以表格形式输出到外部纯文本文件;enddataendyunshuwt.txt文件内容：9 5 7~ !~是记录分割符，该第一个记录是产量;3 84 6~2 9 10 21 3 4 28 4 2 5注：1.@text(yunshuwtx.txt)= x也可以；2.程序与文本文件必须在同一个目录下；3.运行Lingo程序时，文本文件打开或关闭均可．（3）从Excel文件传递数据◆从Excel文件中导入数据命令：数据名=@ole(’fname.xls’,’数据块名’)，其中Excel文件fname.xls应与LINGO程序文件在同一目录中．数据块的定义：在Excel文件中选定数据区域后，选择菜单“插入-名称-定义…”即可进行定义.如数据块名称与数据名相同时，可以省略数据块名称．◆将程序执行结果导出到Excel文件中命令：@ole(’fname.xls’,’数据块名’)=决策变量名，其中保存决策变量的数据块应预先在Excel文件fname.xls中加以定义.model:sets:chandi/1..3/:a;xiaodi/1..4/:b;feiyong(chandi,xiaodi):c,x;endsetsmin=@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=@ole(yunshu.xlsx);b=@ole(yunshu.xlsx);c=@ole(yunshu.xlsx,cc);!Excel中不允许使用域名"c"，对应的数据块定义成"cc";@ole(yunshu.xlsx)=x;enddataend注：程序运行时，excel文件必须打开．3.函数基本运算符：算术运算符、逻辑运算符和关系运算符；数学函数：三角函数和常规的数学函数；金融函数：两种金融函数；概率函数：大量与概率相关的函数；变量限制函数：用来定义变量的取值范围；集合操作函数：对集合的操作提供帮助；集合循环函数：遍历集合的元素，执行一定的操作；数据输入输出函数：允许模型和外部数据源相联系，进行数据的输入输出；辅助函数：各种杂类函数.算术运算符：+ 加- 减* 乘/ 除^ 乘方关系运算符：= 相等<(<=) 小于（小于或等于）>(>=) 大于（大于或等于）逻辑运算符：#not# 一元运算符，否定该操作数的逻辑值；#eq# 若两个运算数相等，则为true，否则为false；#ne# 若两个运算符不相等，则为true，否则为false；#gt# 若左边的运算符严格大于右边的运算符，则为true，否则为false；#ge# 若左边的运算符大于或等于右边的运算符，则为true ，否则为false ； #lt# 若左边的运算符严格小于右边的运算符，则为true ，否则为false ； #le# 若左边的运算符小于或等于右边的运算符，则为true ，否则为false ； #and# 若两个参数都为true ，则为true ，否则为false ； #or# 若两个参数都为false ，则为false ，否则为true.变量限制函数：@bnd(l,x ,u) 有界变量u x l ≤≤ @free(x ) 自由变量 @bin(x ) 0-1变量 @gin(x ) 一般整数变量注：LINGO 默认所有变量都是非负的，如需改变，要另外定义.数学函数：@abs(x) x 的绝对值@sin(x) x 的正弦值（x 采用弧度制）； @cos(x) x 的余弦值 @tan(x) x 的正切值 @exp(x) 常数e 的x 次方 @log(x) x 的自然对数@lgm(x) x 的gamma 函数的自然对数 @sqrt(x) x 的算术平方根@sign(x) x<0时，返回-1；否则，返回1. @floor(x) x 的整数部分 @smax(x1,x2) x1，x2中的最大值 @smin(x1,x2) x1，x2中的最小值 @mod(x1,x2) x1/x2的余数集合操作函数：@for(s:e) 对集合s中的每一元素都生成一个由表达式e描述的约束条件;@sum(s:e) 对集合s中的每一元素都生成表达式e的值，再返回所有这些值的和;@prod(s:e) 对集合s中的每一元素都生成表达式e的值，再返回所有这些值的积;@max(s:e) 对集合s中的每一元素都生成表达式e的值，再返回所有这些值的最大值; @min(s:e) 对集合s中的每一元素都生成表达式e的值，再返回所有这些值的最小值; @size(s) 返回集合s中的元素的个数.五、案例——人力资源分配问题某个中型百货商场对售货人员（周工资200元）的需求量经统计如下表．为了保证员工充分休息，要求每位员工每周工作5天，休息2天．问应如何安排员工的工作时间，使得所配员工的总费用最小．。