数学建模西安交通大学理学院 戴 雪 峰 E-mail: daixuefengmail.xjtu.edu.cn线性规划（Line Programming)模型线性规划（L P）问题的模型建立1、运输问题：工厂123产量600400500某机电公司共有三个电机制造厂，并建立 五个地区性仓库。公司先把产品运到这些 仓库，以备向用户供货，三个厂每周生产 电机台数如表：五个仓库每周需求量如表仓库12345 需求量 200250300550200运费仓 库12345工 厂121312242131321134由各厂到各仓库的运费（每台）如表电机公司希望建立一个满足制造厂的供应 量和仓库的需求量并使总运费为最小的数 学模型。运费仓 库产量11345工厂141311600242134400321134500需求量200250300550200x11x23x35c11c23c35把m个发点的货物运到n个收点去，已知第i 个发点的可供应量为ai(i=1,2,m),第j个收 点的需求量为bj(j=1,2,n)，cij为从第i个发 点到第j个收点的运输单价，应如何运输才能 使总运费最省？一般的运输问题可叙述为：设xij为从第i个发点 到第j个收点的运 量不等式在某些条件下 可能成为等式。2、食谱问题： 一公司饲养动物生长对饲料中三种营养成 分：蛋白质、矿物质、维生素特别敏感， 每个动物每天至少需要蛋白质70g、矿物质 3g、维生素10mg，该公司买到五种不同的 饲料，每种饲料1所含营养成分如表饲料蛋白质(g)矿物质 (g)维生素(mg)A10.300.100.05 A22.000.050.10 A31.000.020.02 A40.600.200.20 A51.800.050.08饲料A1A2A3A4A5成本（元）27435每种饲料1的成本如表要求确定既能满足动物生长所需，又使总成 本为最低的饲料配方。 建立数学模型：设xj(j=1,2,n)表示1混合饲料中含第j种 饲料的数量饲料蛋白质(g) 矿物质(g)维生素(mg)成本 A10.300.100.052 A22.000.050.107 A31.000.020.024 A40.600.200.203 A51.800.050.085x1x2x3 x4x5一般的食谱问题可叙述为： 设有n种食物，每种食物中含有m中营养成 分，用aij表示一个单位的第j种食物含第i种 营养的数量，用bi表示每人每天对第i种营 养的最低需求量，cj表示第j种食物的单价 ，xj表示所用第j种食物的数量，应如何搭 配，能满足m种营养成分需求，又使食物 总成本最低？3、河流污染与净化问题： 某河流边上有两个化工厂，流经第一工厂的 河水流量是每天500万m3，在两厂之间有一条 流量为每天200万m3的支流。第一工厂每天排 放工业污水2万m3，第二工厂每天排放工业污 水1.4万m3，从第一工厂排放工业污水在流到 第二工厂之前有20%可以自然净化，根据环 保要求，河流中的工业污水含量应不大于2 ，若这两厂都各自处理一部分污水，第一工 厂处理污水的成本为0.1元/m3，第二工厂处理 污水的成本为0.08元/m3，问在满足环保的要 求下，各化工厂应处理多少污水，使两厂总 的处理污水费用最少？设xj(j=1,2)为第j个化工厂每天处理污水量 （河水流量中忽略了工厂的排入量。） 模型为：工厂1工厂2 5002007004、合理下料问题： 有长10m的钢管若干，现需裁出2m、3m、 4m的钢管分别为20、15、15根。问如何裁 ，才能使浪费（根数）最少。 方式1234567需求2m5332110203m0102102154m001012115余料0100100x1x2x3x4x5x6x7设xj用第j种方式下料所用钢管数，请同学们考虑：如何裁，才能使浪费（料头 ）最少。模型为：一般的合理下料问题可叙述为： 要利用某类钢材下A1,A2,Am一共m种零件 毛料，根据省料原则，在一块钢材上设计出 n种不同的下料方式，设在第j种下料方式中 ，可得Ai种零件aij个，设第i种零件的需求量 为bi（如表）.问应采取什么方式，使既满足 问题需要，又使所用钢材最少？ 方式1n需求量A1a11a1nb1AmAm1Amnbm设xj为用第j种方式下料所用钢材数模型为：5、指派问题：某大学打算在暑期对三幢教学楼进行维修, 该校让三个建筑公司对每幢楼的修理费用 进行报价承包(见表,单位:万元),在暑期每 个建筑公司只能修理一幢教学楼，因此该 大学必须把各教学楼指派给不同建筑公司 ，为使报价总和最小，应指定建筑公司承 包哪一幢教学楼？ 报 价 数 目（万元 ) 教学1楼教学2楼教学3楼建一公司132410 建二公司171915建三公司202221x11x22x12x13x21x32x31x23x33模型为：一般的指派问题可叙述为：设有n项任务需派n个人去完成，但由于任务 性质及个人专长不同，因此各人完成各任务 的效率（或需时间、花费成本）不同，试问 应如何安排，使总效率（或需时间、花费成 本最少）最高？设tij表示第i个人完成第j件任务的效率模型为：6、投资决策问题：公司拟在某市东、南、西三区建立连锁店 ，拟议中有7个位置Ai(i=1,2,7)可供选择 ，规定东区在A1,A2,A3中至多选2个，西区 在A4,A5中至少选1个，南区在A6,A7中至少 选1个，并选用Ai点，投资bi元，估计每年 获利ci元，但投资总额不得超过B元。问应 如何选址，可使每年利润最大？模型为：效率一二三 A356 B745C4687、生产配套问题： 设第一、二、三个车间生产零件A、B、C 的效率如下,假设三种零件各一个配成一套 。应如何分配生产任务，可使生产的成套 产品最多？设xij(i=1,2,3,j=1,2,3)表示第i个零件由第j个 车间生产的生产时间。共生产配套产品Z套 ，x11x22x12x13x21x32x31x23x33模型如下:一般的生产配套问题可叙述为： 设有n个车间，要生产m种产品，假设这种 产品每种一件配成一套。问如何安排任务 ，使生产的成套产品最多？ 设一天中第j个车间用于生产第i种产品的时 间 xij (i=1,m,j=1,n) ，每天生产Z套，模型如下；8、森林管理问题：森林中树木每年要有一批被砍伐出售，为 使森林不被耗尽而每年都有所收获，每砍 伐一棵树，就应补种一棵幼苗，使的森林 树木总数不变，希望有一个方案，在保持 收获稳定的前提下，获得最大的经济价值 。1）模型假设： 我们把森林中的树木按高度分成n级，第k 级高度在hk-1到hk之间（h0=0），其价值pk 元，k=1，n，显然有 p1p2pn ， 第一级为幼苗，价值为零（p1=0），开 始时，森林中树木高度分布为第k级数量为 xk。设每年砍伐一次，要使每年维持收获，只 能砍伐部分树木，留下的数目与补种的幼 苗其高度状态与初始状态相同。设yk为每 年第k级所砍伐的棵数。设森林树木总数 为S（固定），有 在一个生长期（即两次收获之间）假设树 木至多只能生长一个高度级（即从k级进 入k+1级，也可能因某些原因留在第k级） 。并假设每一棵幼苗都生长到被收获（不 考虑死亡的可能性）。假设在每一个生长 期内，第k级的树木进入第k+1级的比例为 gk，于是留在原级的比例为1-gk。2）模型建立： 设X=(x1,x2,xn)T，所以GX表示经过一个生长期后树木高度 的分布。 每次收获砍伐总数为 而补种的棵数等于砍伐总数 要保持初始状态不变，有因而有（否则，各级数目就会越来越少。） 总收益:数学模型归纳为以上各问题有以下特点：1）每一问题都用一组未知量来表示某一方 案，其取值就表示特定方案，称之为决策 变量。（通常为非负的）2）存在一定的限制条件，并用未知量的线 性等式或不等式表示。3）有一个目标要求，并用未知量的线性函 数表示，由实际要求，实现其最大化或最 小化。LP的数学描述(数学模型)： （1）一般形式 （2）紧缩形式（3）矩阵形式其中 :（4）向量矩阵形式：其中：线性规划问题主要解法是单纯单纯 形解法，一般用 Lingo软件求解.线性规划（LP）问题的图解法若线性规划问题只有两个变量，则可用图解 法求解。图解法简单直观，不但能很快求得 LP问题的最优解和最优值，而且它的结论对 多个变量线性规划问题也提供了求解思路。图解法讲解图解法求解时，先做出问题的可行解域，它 是每个线性约束所确定的半平面的交，再将 目标函数Z作为参数，做出目标函数线，它 是一簇平行线，根据目标函数的要求，寻找 Z在可行解域中的最大或最小值，即可求得 问题的最优解。xyox+y=0x+y0x+y0x-y+10x-y+1=0xyo362x+y-602x+y-6=0xyo35-5x-y+5=0x+y=0x=34 46 68 84 46 63 3A AB BC CD D图解法求LP问题的示意图图解法 的启示 可行域是一个凸多边形.LP的解可能有多种形式,如多解,无界解( 发散,无穷)或无可行域.最优解一定在可行域的边界上,一般是在 顶点上1.唯一最优解 例. 用图解法求解：可行解域OABC 最优解B(4,1), 即 X1 =4 X2 =1 最优值Z=9图解法求LP问题会出现的几种情况2.无可行解例. 用图解法求解：此问题无可行解，无最优解3.无界例. 用图解法求解：此例可行解域无界，目标直线可向右上方无 限延伸，故目标函数值无界， 称此情况为无界情况线性规划（LP）问题的单纯形法1.LP标准型的概念 目标函数约定是极大化Max; 约束条件均用等式表示; 决策变量限于取非负值; 右端常数均为非负值 ;2.LP问题的标准化 （1）目标函数的标准化MinZ=CXZ=-ZZ=-ZMaxZ=-CX目标函数标准化示意图目标函数标准化示意图（2） 约束条件的标准化约束条件是类型左边 加 非负松弛变量 约束条件是类型左边 减 非负剩余变量 变量符号不限引入新变量 将下面的线性规划问题化为标准型： LP解的基本概念及基本性质1.基本概念满足约束条件的解称为线性规划问题的可 行解,所有可行解的集合称为可行域。 基、基向量、基变量、非基变量 在mn阶约束方程组中,若有一个mm阶的 非奇异子矩阵B, 则B为该LP的一个基。B 所在列对应的向量为基向量，对应的变量 为基变量，其余向量为非基向量。其余变 量为非基变量。可行解:基解(也叫“基本解”）基解的特点： 1.基解的非零分量个数小于等于约束方程数 m 2.基解是约束方程的交点。 3.基解只满足条件约束，不一定满足非 负约 束，因此基解中的分量有可能为负数。4.基解的个数有限，不超过 。取一个基，令其中非基变量为0，可得相应 基解。求基解的前提是取m个线性无关向量 构成基。2.基本定理定理1 LP的可行域为凸集 定理2 基本可行解 可行解的非 零分量对应的系数列向量线性无关 定理3 基可行解 可行域的顶点定理4 若可行域有界，最优解一定在其顶点上基本思路：从可行域中某个基可行解开始，根据 一定标准，转换到另一个基可行解，当目标函数 最大时，就得到了最优解。 单纯型核心：关键在于判别，使每次转换后结果 更优，从而不必穷举所有顶点即可得到最优解。 判别方法：观察非基变量取值对目标函数的影响 。单纯型法：定理1 当所有非基变变量的检验检验 数 ,相 应应的基可行解为为最优优解。 定理2 当还还有非基变变量的检验检验 数 ,则则 该该解不是最优优解。 1.化标标准型单纯型求解步骤2. 建立初始单纯单纯 型表, 确定初始基，求出初 始基可行解。b2 2 1 0 0 01