《数学建模线性规划模型课件.ppt》由会员分享，可在线阅读，更多相关《数学建模线性规划模型课件.ppt（106页珍藏版）》请在三一办公上搜索。
1、数学建模,西安交通大学理学院,线性规划（Line Programming)模型,线性规划（L P）问题的模型建立,1、运输问题：,某机电公司共有三个电机制造厂，并建立五个地区性仓库。公司先把产品运到这些仓库，以备向用户供货，三个厂每周生产电机台数如表：,五个仓库每周需求量如表,由各厂到各仓库的运费（每台）如表,电机公司希望建立一个满足制造厂的供应量和仓库的需求量并使总运费为最小的数学模型。,把m个发点的货物运到n个收点去，已知第i个发点的可供应量为ai(i=1,2,m),第j个收点的需求量为bj(j=1,2,n)，cij为从第i个发点到第j个收点的运输单价，应如何运输才能使总运费最省？,一般的
2、运输问题可叙述为：,设xij为从第i个发点到第j个收点的运量,不等式在某些条件下可能成为等式。,2、食谱问题：,一公司饲养动物生长对饲料中三种营养成分：蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该公司买到五种不同的饲料，每种饲料1所含营养成分如表,每种饲料1的成本如表,要求确定既能满足动物生长所需，又使总成本为最低的饲料配方。,建立数学模型：,设xj(j=1,2,n)表示1混合饲料中含第j种饲料的数量,一般的食谱问题可叙述为：,设有n种食物，每种食物中含有m中营养成分，用aij表示一个单位的第j种食物含第i种营养的数量，用bi表示每人每天对第
3、i种营养的最低需求量，cj表示第j种食物的单价，xj表示所用第j种食物的数量，应如何搭配，能满足m种营养成分需求，又使食物总成本最低？,3、河流污染与净化问题：,某河流边上有两个化工厂，流经第一工厂的河水流量是每天500万m3，在两厂之间有一条流量为每天200万m3的支流。第一工厂每天排放工业污水2万m3，第二工厂每天排放工业污水1.4万m3，从第一工厂排放工业污水在流到第二工厂之前有20%可以自然净化，根据环保要求，河流中的工业污水含量应不大于2，若这两厂都各自处理一部分污水，第一工厂处理污水的成本为0.1元/m3，第二工厂处理污水的成本为0.08元/m3，问在满足环保的要求下，各化工厂应处
4、理多少污水，使两厂总的处理污水费用最少？,设xj(j=1,2)为第j个化工厂每天处理污水量（河水流量中忽略了工厂的排入量。）,模型为：,4、合理下料问题：,有长10m的钢管若干，现需裁出2m、3m、4m的钢管分别为20、15、15根。问如何裁，才能使浪费（根数）最少。,设xj用第j种方式下料所用钢管数，,请同学们考虑：如何裁，才能使浪费（料头）最少。,模型为：,一般的合理下料问题可叙述为：,要利用某类钢材下A1,A2,Am一共m种零件毛料，根据省料原则，在一块钢材上设计出n种不同的下料方式，设在第j种下料方式中，可得Ai种零件aij个，设第i种零件的需求量为bi（如表）.问应采取什么方式，使既
5、满足问题需要，又使所用钢材最少？,设xj为用第j种方式下料所用钢材数,模型为：,5、指派问题：,某大学打算在暑期对三幢教学楼进行维修,该校让三个建筑公司对每幢楼的修理费用进行报价承包(见表,单位:万元),在暑期每个建筑公司只能修理一幢教学楼，因此该大学必须把各教学楼指派给不同建筑公司，为使报价总和最小，应指定建筑公司承包哪一幢教学楼？,模型为：,一般的指派问题可叙述为：,设有n项任务需派n个人去完成，但由于任务性质及个人专长不同，因此各人完成各任务的效率（或需时间、花费成本）不同，试问应如何安排，使总效率（或需时间、花费成本最少）最高？,设tij表示第i个人完成第j件任务的效率,模型为：,6、
6、投资决策问题：,公司拟在某市东、南、西三区建立连锁店，拟议中有7个位置Ai(i=1,2,7)可供选择，规定东区在A1,A2,A3中至多选2个，西区在A4,A5中至少选1个，南区在A6,A7中至少选1个，并选用Ai点，投资bi元，估计每年获利ci元，但投资总额不得超过B元。问应如何选址，可使每年利润最大？,模型为：,7、生产配套问题：,设第一、二、三个车间生产零件A、B、C的效率如下,假设三种零件各一个配成一套。应如何分配生产任务，可使生产的成套产品最多？,设xij(i=1,2,3,j=1,2,3)表示第i个零件由第j个车间生产的生产时间。共生产配套产品Z套，,模型如下:,一般的生产配套问题可叙
7、述为：,设有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）
8、，开始时，森林中树木高度分布为第k级数量为xk。,设每年砍伐一次，要使每年维持收获，只能砍伐部分树木，留下的数目与补种的幼苗其高度状态与初始状态相同。设yk为每年第k级所砍伐的棵数。设森林树木总数为S（固定），有,在一个生长期（即两次收获之间）假设树木至多只能生长一个高度级（即从k级进入k+1级，也可能因某些原因留在第k级）。并假设每一棵幼苗都生长到被收获（不考虑死亡的可能性）。假设在每一个生长期内，第k级的树木进入第k+1级的比例为gk，于是留在原级的比例为1-gk。,2）模型建立：,设X=(x1,x2,xn)T，,所以GX表示经过一个生长期后树木高度的分布。,每次收获砍伐总数为,而补种的棵
9、数等于砍伐总数,要保持初始状态不变，有,因而有,（否则，各级数目就会越来越少。）,总收益:,数学模型归纳为,以上各问题有以下特点：,1）每一问题都用一组未知量来表示某一方案，其取值就表示特定方案，称之为决策变量。（通常为非负的）,2）存在一定的限制条件，并用未知量的线性等式或不等式表示。,3）有一个目标要求，并用未知量的线性函数表示，由实际要求，实现其最大化或最小化。,LP的数学描述(数学模型)：,（1）一般形式,（2）紧缩形式,（3）矩阵形式,其中 :,（4）向量矩阵形式：,其中：,线性规划问题主要解法是单纯形解法，一般用Lingo软件求解.,线性规划（LP）问题的图解法,若线性规划问题只有
10、两个变量，则可用图解法求解。图解法简单直观，不但能很快求得LP问题的最优解和最优值，而且它的结论对多个变量线性规划问题也提供了求解思路。,图解法讲解,图解法求解时，先做出问题的可行解域，它是每个线性约束所确定的半平面的交，再将目标函数Z作为参数，做出目标函数线，它是一簇平行线，根据目标函数的要求，寻找Z在可行解域中的最大或最小值，即可求得问题的最优解。,x+y=0,x+y0,x+y0,二元一次方程 a1x1+a2x2 =b 代表x1 x2平面上的一条直线，而二元一次不等式a1x1+a2x2 b则代表了以此直线为界的半平面,1,-1,x-y+10,x-y+10,x-y+1=0,3,6,2x+y-
11、60,2x+y-6=0,3,5,-5,x-y+5=0,x+y=0,x=3,4,6,8,4,6,3,A,B,C,D,图解法求LP问题的示意图,图解法 的启示,可行域是一个凸多边形.,LP的解可能有多种形式,如多解,无界解(发散,无穷)或无可行域.,最优解一定在可行域的边界上,一般是在顶点上,1.唯一最优解,例. 用图解法求解：,可行解域OABC最优解B(4,1), 即X1 =4 X2 =1最优值Z=9,图解法求LP问题会出现的几种情况,2.无可行解,例. 用图解法求解：,此问题无可行解，无最优解,3.无界,例. 用图解法求解：,此例可行解域无界，目标直线可向右上方无限延伸，故目标函数值无界，,称
12、此情况为无界情况,线性规划（LP）问题的单纯形法,1.LP标准型的概念,目标函数约定是极大化Max;,约束条件均用等式表示;,决策变量限于取非负值;,右端常数均为非负值 ;,2.LP问题的标准化,（1）目标函数的标准化,MinZ=CX,MaxZ=-CX,（2） 约束条件的标准化 约束条件是类型 左边 加 非负松弛变量 约束条件是类型 左边 减 非负剩余变量 变量符号不限 引入新变量,将下面的线性规划问题化为标准型：,LP解的基本概念及基本性质,1.基本概念,满足约束条件的解称为线性规划问题的可行解,所有可行解的集合称为可行域。,基、基向量、基变量、非基变量,在mn阶约束方程组中,若有一个mm阶
13、的非奇异子矩阵B, 则B为该LP的一个基。B所在列对应的向量为基向量，对应的变量为基变量，其余向量为非基向量。其余变量为非基变量。,可行解:,基解(也叫“基本解”）,基解的特点：,1.基解的非零分量个数小于等于约束方程数 m,2.基解是约束方程的交点。,3.基解只满足条件约束，不一定满足非 负约束，因此基解中的分量有可能为负数。,4.基解的个数有限，不超过 。,取一个基，令其中非基变量为0，可得相应基解。求基解的前提是取m个线性无关向量构成基。,2.基本定理,定理1 LP的可行域为凸集,定理2 基本可行解 可行解的非零分量对应的系数列向量线性无关,定理3 基可行解 可行域的顶点,定理4 若可行
14、域有界，最优解一定在其顶点上,基本思路：从可行域中某个基可行解开始，根据一定标准，转换到另一个基可行解，当目标函数最大时，就得到了最优解。,单纯型核心：关键在于判别，使每次转换后结果更优，从而不必穷举所有顶点即可得到最优解。,判别方法：观察非基变量取值对目标函数的影响。,单纯型法：,定理1 当所有非基变量的检验数 ,相应的基可行解为最优解。,定理2 当还有非基变量的检验数 ,则该解不是最优解。,1.化标准型,单纯型求解步骤,2. 建立初始单纯型表, 确定初始基，求出初始基可行解。,3. 计算检验数 ，确定换入基变量和换出基变量。,0,2,3,0 0 0 0,6,4,3,2 3 0 0 0 0,
15、12 81612,0000,换入变量的确定 计算， cC Bi a ij 可只计算非基变量的，换入基变量 kmax ， 0 ，k对应的 列为主元列。,换出变量的确定 计算 i， i b/ a ik （当a ik 0时） 只计算非负的a ik 对应的行，换出基变量 L min i ，L对应的行为主元行。,k列L行的元素称为主元素，用alk表示,Z,2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1,b,6,4,3,2 3 0 0 0 0,12 81612,0000,0003,3 0 1 0 0 0 1/4,16 4 0 0 0 1 0,2 1 0 0
16、1 0 -1/2,6 2 0 1 0 0 -1/2,2 0 0 0 0 -4/3,324-,4. 迭代计算（求新的基本可行解）5. 重复3、4步，直至最优。,X(3)=(2 , 3, 2, 0, 8, 0 ) Z=13X(4)=(4 , 2, 0, 0, 0, 4 ) Z=14,线性规划（LP）问题的特殊解法,1、运输问题：,步骤：,1）最小元素法确定初始方案：按运费最小优先供应原则（多个最小元素选最上一行最左边一个），划去行或列时一次只能划去一行或一列，最后一个同时划去行和列，保证表上又m+n-1个格有数字（包括0）。,2）求出检验数，判别是否最优。（对最小化问题，若每个空格的检验数 ，则方
17、案达到最优。）（为了求出检验数，需画出闭回路(闭回路唯一)。） 第偶数次拐角点运价-第奇数次拐角点运价,3）求出调整量，在闭回路上调整。调整量： 奇数次拐角点运量调整：奇数次拐角点运量-；偶数次拐角点运量+。（若表中有几个零出现，将最上一行最左边一个的零改为空格，其余保留，保证表上又m+n-1个格有数字。）,另一种求检验数的方法：1）运价表上有调运量的数字加，2）同行或同列同时减去或加上同一个数，使其带数字全部变为零，则未加的数字即为对应空格的检验数。,3）最大化问题用最大元素法建立初始方案。判别最优时,检验数 达到最优，其余与最小元素法相同。,注：,1）运输问题最优解不唯一。,2）对于产销不
18、平衡问题，可以虚加发点或收点来进行求解（发量大于收量，虚加一列，运价增加一列，并全部为零，在用最小元素法时，须先将库存一列去掉，再逐一选取最小元素）。,2、指派问题：,Theorem1: 如果从效率矩阵的任一行（列）各元素减去该行（列）的最小元素（或加上某一正数），不改变问题的最优解。,Theorem2:如果从效率矩阵的每一行分别减去该行的最小元素ai，每一列分别减去该列的最小元素bj，得到最优解。则目标函数（最小化）的最优值等于各行、各列减去数之和，即minZ=ai-bj,例：4人工作分派，效率矩阵如下,如何分派使得问题最小化。(minZ=29),步骤：,1）每行每列减去各行、各列最小元素，
19、使每行每列至少有一个零元素。,2）从零元素最少的行开始，对一个零元素标，表示一种分派，同时把该行、列的其余零元素划去，防止下次分派落在此行、列上，当某行零元素多于一个，则标注零元素最少的列。至所有零元素标注或划去为止。若得到n个0*，则0*改为1，其余改为0，即为最优分派。,3）若0*少于n个，则作0*的最少覆盖集。,例：求该指派问题的minZ,对没有0*的行打。,对打行所有零元素列打。,再对打列上0*行打。,重复、，到不能打为止。,对没有打行划线，对打列划线，其线条数=0*数。,在没有划线的元素中找最小元素，对没有划线行各元素减去最小元素，对划线列各元素加上最小元素，得到新的效率矩阵，返回第
20、2）步。,再例：求该指派问题的minZ,注1：对最大化问题，采用构造一个新的效率矩阵 ，并取 ，则,注2：若效率矩阵mn（行数不等于列数），可虚设零行（列），使效率矩阵变成方阵，然后再用匈牙利法求解。,3、生产配套问题：,设每个车间都生产效率最高的零件,按开始的原则重新分配得：,（若某列有相同的最大效率，选取时应位于不同行列上。,把第一行的效率再扩大，该行乘以,为使零件A和C的产量相等（配套），得：,这时有,得：,为使三个车间产量相等（配套），需把第一车间生产零件B的时间的一部分用来生产零件A和C，,零件A的产量为,零件B的产量为,零件C的产量为,最优解为:,(不唯一,可生产392/61(套)
21、,若要求每个车间生产的零件必须为整数，则易得出：,零件A：,零件B：,零件C：,即一天可完成6套产品。,（一车间6个B零件，二车间5个A零件，三车间1个A零件、6个B零件。）,4、森林管理问题：,森林中树木每年要有一批被砍伐出售，为使森林不被耗尽而每年都有所收获，每砍伐一棵树，就应补种一棵幼苗，使的森林树木总数不变，希望有一个方案，在保持收获稳定的前提下，获得最大的经济价值。,1）模型假设：,树木按高度分成n级，第k级高度在hk-1到hk之间（h0=0），其价值pk元，k=1，n，显然: 0=p1p2pn， 第一级为幼苗，价值为零（p1=0），开始时，森林中树木高度分布为第k级数量为xk。,设
22、每年砍伐一次，要使留下的数目与补种的幼苗其高度状态与初始状态相同。设yk为每年第k级所砍伐的棵数。设森林树木总数为S（固定），有,在一个生长期（即两次收获之间）假设树木至多只能生长一个高度级（即从k级进入k+1级，也可能因某些原因留在第k级）。并假设每一棵幼苗都生长到被收获（不考虑死亡的可能性）。假设在每一个生长期内，第k级的树木进入第k+1级的比例为gk，于是留在原级的比例为1-gk。,2）模型的分析与建立,记xik+1为k+1年的第i级数目,现在来考虑收获情形:,维持每年收获,期初=期末-收获+新种幼苗数,有收获模型：,保证对森林有持续收获，就相当于要求Y是常量。数学上相当于要求每年森林树
23、木分布状况相同，即存在X，使得X(k)=X，X即为模型的平衡解。,它相当于以下关系式：,可以看出，第一个方程为其余n-1个方程之和，且因Y为收获向量，则yi0。考虑到幼苗的经济价值为零，故不砍伐幼苗，y1=0，且仍用xk表示x，由方程组（1）可得：,所以收获总价值,再利用方程组（1）可得,（其中p1=0）,数学模型归纳为,3）模型的求解,对于线性规划问题，有两个定理：,定理1：线性规划问题的可行域为凸集。,定理2：线性规划问题的最优解在可行域的顶点上达到。,由定理2知道:只要从某个高度级中收获全部树木，而不用收获其它高度级的树木，就可以得到最大持续收获。,假定只收获第k级的全部树木，所以有,由
24、于第k级树木被全部收获，所以，当ik时，第i级就不存在树木，即xi=0。,所以收获第k级树木的收入：,只要生长参数gi已知，就可以求出P的值，再比较k取不同值时的P值，从中确定持续收获的最大经济收入。,4）数值举例：,现已知某处森林具有6年的生长期，经过实地测量，得其生长矩阵,各年龄树木价格分别为：,这里设森林中树木总数为S，,若只收获第二年（k=2）,此时,若只收获第三年（k=3）,若只收获第四年（k=4）,若只收获第五年（k=5）,若只收获第六年（k=6）,比较可知14.7S最大，应砍伐第三年中全部树木，使收益最大。,即第一年树木占森林树木总数的52.5%，第二年树木占森林树木总数的47.
25、5%。,作业：,1.对下表所表示的运输问题建模并求解,2.现要用10050厘米的板料裁剪出规格分别为4040 厘米与5020厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？,电视台为某个广告公司特约播放两套片集。其中片集甲播映时间为20分钟，广告时间为1分钟，收视观众为60万，片集乙播映时间为10分钟，广告时间为1分钟，收视观众为20万。广告公司规定每周至少有6分钟广告，而电视台每周只能为该公司提供不多于80分钟的节目时间。电视台每周应播映两套片集各多少次，才能获得最高的收视率？,某厂生产甲、乙两种产品，生产甲种产品每件要消耗煤9吨，电力4千瓦，使用劳动力3个，获利70元；
26、生产乙种产品每件要消耗煤4吨，电力5千瓦，使用劳动力10个，获利120元。有一个生产日，这个厂可动用的煤是360吨，电力是200千瓦，劳动力是300个，问应该如何安排甲、乙两种产品的生产，才能使工厂在当日的获利最大，并问该厂当日的最大获利是多少？答案：（甲20件，乙24件，获利4280元）,药房有两种复合维生素制剂，甲种每粒含维生素A、B各1克， D、E各4克和C 5克，乙种每粒含维生素A 3克，B 2克、D 1克、E 3克和C 2克，一顾客每天需摄入维生素A不超过18克、B不超过13克、D不超过24克和E至少12克，问： (1)每天应服两种维生素各多少才能满足需要而且尽可能摄入较多的维生素C
27、？ (2)甲种复合维生素每粒1.5元，乙种复合维生素每粒1元，选择怎样的服法才能花最少的钱而又满足每天的需要，此时顾客摄入的维生素C是多少？,某牧场所饲养一批动物，平均每头动物每天至少需要700g蛋白质、30g矿物质和100g维生素.现在有甲、乙、丙、丁和戊五种饲料可选用，每千克饲料的营养成分(单位：g)与价格(单位：元/kg)如表所示,蛋白质矿物质维生素价格,甲31.0 0.5 0.4,乙20.5 1.0 1.4,丙10.2 0.2 0.8,丁62.0 2.0 0.6,戊 120.5 0.8 1.6,试求能满足动物生长营养需求又最经济的选用饲料方案.,农场有A、B和C三块地，分别是200 k
28、m2、400 km2和600 km2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为375 t、120 t和750 t.估计各块地种植三种作物的单产(单位:t /km2)如表,A B C,水稻 11.250 9.750 9.000,大豆 6.000 6.750 5.250,玉米 15.000 13.500 12.750,应如何制订种植计划能使总产量最高？又若作物的售价为水稻元/t ,大豆元/t ,玉米950元/t ,那么应如何制订种植计划能使总收益最高.,铸铁厂要生产一种规格的铸件共10 t.其成分要求为：锰含量至少达到0.45,硅含量允许在3.255.5，市场有充分的锰和三种不同型
29、号的生铁可供作铸件的炉料使用，它们价格是锰每千克75元，A种生铁每吨1700元，B种生铁每吨1900元， C种生铁每吨1400元.三种生铁含锰和硅的成分百分比()如表所示,A B C,锰 0.40.5 0.35,硅 41 0.5,若不计冶炼铸造过程中的损耗，问工厂怎样选择炉料能使成本最低？,某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？,某厂每日8小时的产量不低于1800件。为了进行质量控制，计划聘请两种不同水平的检验员。一级检验员的标准为：速度25件/小时，正确率98%，计时工资4元/小时；二级检验员的标准为：速度15小时/件，正确率95%，计时工资3元/小时。检验员每错检一次，工厂要损失2元。为使总检验费用最省，该厂应聘一级、二级检验员各几名？,
