数学建模线性规划模型ppt课件.ppt

《数学建模线性规划模型ppt课件.ppt》由会员分享，可在线阅读，更多相关《数学建模线性规划模型ppt课件.ppt（106页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能数学建模西安交通大学理学院西安交通大学理学院为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性规划（Line Programming)模型为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性规划（线性规划（L P）问题的）问题的模型建立模型建立为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1、运输问

2、题：工厂123产量600400500某机电公司共有三个电机制造厂，并建立五个地区性仓库。公司先把产品运到这些仓库，以备向用户供货，三个厂每周生产电机台数如表：五个仓库每周需求量如表仓库12345需求量 200 250300550200为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能运费仓 库12345工厂121312242131321134由各厂到各仓库的运费（每台）如表电机公司希望建立一个满足制造厂的供应量和仓库的需求量并使总运费为最小的数学模型。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充

3、分发挥中小学图书室育人功能运费仓库产量12345工厂141311600242134400321134500需求量200250300550200 x11x23x35c11c23c35为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能把m个发点的货物运到n个收点去，已知第i个发点的可供应量为ai(i=1,2,m),第j个收点的需求量为bj(j=1,2,n)，cij为从第i个发点到第j个收点的运输单价，应如何运输才能使总运费最省？一般的运输问题可叙述为：一般的运输问题可叙述为：设xij为从第i个发点到第j个收点的运量不等式在某些条件下可能成

4、为等式。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2、食谱问题：一公司饲养动物生长对饲料中三种营养成分：蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该公司买到五种不同的饲料，每种饲料1所含营养成分如表饲料蛋白质(g)矿物质(g)维生素(mg)A10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书

5、室育人功能饲料A1A2A3A4A5成本（元）27435每种饲料1的成本如表要求确定既能满足动物生长所需，又使总成本为最低的饲料配方。建立数学模型：设xj(j=1,2,n)表示1混合饲料中含第j种饲料的数量为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能饲料蛋白质(g)矿物质(g)维生素(mg)成本A10.300.100.052A22.000.050.107A31.000.020.024A40.600.200.203A51.800.050.085x1x2x3x4x5为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教

6、育大会精神,充分发挥中小学图书室育人功能一般的食谱问题可叙述为：设有n种食物，每种食物中含有m中营养成分，用aij表示一个单位的第j种食物含第i种营养的数量，用bi表示每人每天对第i种营养的最低需求量，cj表示第j种食物的单价，xj表示所用第j种食物的数量，应如何搭配，能满足m种营养成分需求，又使食物总成本最低？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3、河流污染与净化问题：某河流边上有两个化工厂，流经第一工厂的河水流量是每天500万m3，在两厂之间有一条流量为每天200万m3的支流。第一工厂每天排放工业污水2万m3，第二工

7、厂每天排放工业污水1.4万m3，从第一工厂排放工业污水在流到第二工厂之前有20%可以自然净化，根据环保要求，河流中的工业污水含量应不大于2，若这两厂都各自处理一部分污水，第一工厂处理污水的成本为0.1元/m3，第二工厂处理污水的成本为0.08元/m3，问在满足环保的要求下，各化工厂应处理多少污水，使两厂总的处理污水费用最少？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能设xj(j=1,2)为第j个化工厂每天处理污水量（河水流量中忽略了工厂的排入量。）模型为：工厂1工厂2500200700为深入学习习近平新时代中国特色社会主义思想和

8、党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4、合理下料问题：有长10m的钢管若干，现需裁出2m、3m、4m的钢管分别为20、15、15根。问如何裁，才能使浪费（根数）最少。方式1234567需求2m5332110203m0102102154m001012115余料0100100 x1x2x3x4x5x6x7为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能设xj用第j种方式下料所用钢管数，请同学们考虑：如何裁，才能使浪费（料头）最少。模型为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教

9、育大会精神,充分发挥中小学图书室育人功能一般的合理下料问题可叙述为：要利用某类钢材下A1,A2,Am一共m种零件毛料，根据省料原则，在一块钢材上设计出n种不同的下料方式，设在第j种下料方式中，可得Ai种零件aij个，设第i种零件的需求量为bi（如表）.问应采取什么方式，使既满足问题需要，又使所用钢材最少？方式1n需求量A1a11a1nb1AmAm1Amnbm为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能设xj为用第j种方式下料所用钢材数模型为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发

10、挥中小学图书室育人功能5、指派问题：某大学打算在暑期对三幢教学楼进行维修,该校让三个建筑公司对每幢楼的修理费用进行报价承包(见表,单位:万元),在暑期每个建筑公司只能修理一幢教学楼，因此该大学必须把各教学楼指派给不同建筑公司，为使报价总和最小，应指定建筑公司承包哪一幢教学楼？报 价 数 目（万元)教学1楼教学2楼教学3楼建一公司132410建二公司171915建三公司202221x11x22x12x13x21x32x31x23x33为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能模型为：为深入学习习近平新时代中国特色社会主义思想和党

11、的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能一般的指派问题可叙述为：设有n项任务需派n个人去完成，但由于任务性质及个人专长不同，因此各人完成各任务的效率（或需时间、花费成本）不同，试问应如何安排，使总效率（或需时间、花费成本最少）最高？设tij表示第i个人完成第j件任务的效率为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能模型为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能6、投资决策问题：公司拟在某市东、南、西三区建立连锁店，拟议中有7个位置Ai

12、(i=1,2,7)可供选择，规定东区在A1,A2,A3中至多选2个，西区在A4,A5中至少选1个，南区在A6,A7中至少选1个，并选用Ai点，投资bi元，估计每年获利ci元，但投资总额不得超过B元。问应如何选址，可使每年利润最大？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能模型为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能效率一二三A356B745C4687、生产配套问题：设第一、二、三个车间生产零件A、B、C的效率如下,假设三种零件各一个配成一套。应如何分配生

13、产任务，可使生产的成套产品最多？设xij(i=1,2,3,j=1,2,3)表示第i个零件由第j个车间生产的生产时间。共生产配套产品Z套，x11x22x12x13x21x32x31x23x33为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能模型如下:为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能一般的生产配套问题可叙述为：设有n个车间，要生产m种产品，假设这种产品每种一件配成一套。问如何安排任务，使生产的成套产品最多？设一天中第j个车间用于生产第i种产品的时间 xij (

14、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。为深入学习习近平新

15、时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能设每年砍伐一次，要使每年维持收获，只能砍伐部分树木，留下的数目与补种的幼苗其高度状态与初始状态相同。设yk为每年第k级所砍伐的棵数。设森林树木总数为S（固定），有在一个生长期（即两次收获之间）假设树木至多只能生长一个高度级（即从k级进入k+1级，也可能因某些原因留在第k级）。并假设每一棵幼苗都生长到被收获（不考虑死亡的可能性）。假设在每一个生长期内，第k级的树木进入第k+1级的比例为gk，于是留在原级的比例为1-gk。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分

16、发挥中小学图书室育人功能2）模型建立：设X=(x1,x2,xn)T，所以GX表示经过一个生长期后树木高度的分布。每次收获砍伐总数为 而补种的棵数等于砍伐总数 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能要保持初始状态不变，有因而有（否则，各级数目就会越来越少。）总收益:为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能数学模型归纳为为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能以上各问题有以下特点：1）每一

17、问题都用一组未知量来表示某一方案，其取值就表示特定方案，称之为决策变量。（通常为非负的）2）存在一定的限制条件，并用未知量的线性等式或不等式表示。3）有一个目标要求，并用未知量的线性函数表示，由实际要求，实现其最大化或最小化。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能LP的数学描述(数学模型)：（1）一般形式为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）紧缩形式为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图

18、书室育人功能（3）矩阵形式其中:为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（4）向量矩阵形式：其中：线性规划问题主要解法是线性规划问题主要解法是单纯形解法单纯形解法，一般用，一般用Lingo软件求解软件求解.为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性规划（线性规划（LP）问题的图解法）问题的图解法为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能若线性规划问题只有两个变量，则可用图解法求解。图解法

19、简单直观，不但能很快求得LP问题的最优解和最优值，而且它的结论对多个变量线性规划问题也提供了求解思路。图解法图解法讲解讲解图解法求解时，先做出问题的可行解域，它是每个线性约束所确定的半平面的交，再将目标函数Z作为参数，做出目标函数线，它是一簇平行线，根据目标函数的要求，寻找Z在可行解域中的最大或最小值，即可求得问题的最优解。xyox+y=0 x+y0 x+y0 x-y+10 x-y+1=0 xyo362x+y-602x+y-6=0 xyo35-5x-y+5=0 x+y=0 x=3为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4 4

20、6 68 84 46 63 3A AB BC CD D为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图解法求LP问题的示意图为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能图解法的启示可行域是一个凸多边形可行域是一个凸多边形.LP的解可能有多种形式的解可能有多种形式,如多解如多解,无界解无界解(发散发散,无穷无穷)或无可行域或无可行域.最优解一定在可行域的边界上最优解一定在可行域的边界上,一般是在一般是在顶点上顶点上为深入学习习近平新时代中国特色社会主义思想和党的十九大

21、精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1.1.唯一最优解唯一最优解例.用图解法求解：可行解域OABC最优解B(4,1),即X1=4X2=1最优值Z=9图解法求LP问题会出现的几种情况为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.2.无可行解无可行解例.用图解法求解：此问题无可行解，无最优解为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3.3.无界无界例.用图解法求解：此例可行解域无界，目标直线可向右上方无限延伸，故目标函数值无界，称此情况为无界情

22、况为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线性规划（线性规划（LP）问题的单纯形法）问题的单纯形法为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1.LP标准型的概念目标函数约定是极大化Max;约束条件均用等式表示;决策变量限于取非负值;右端常数均为非负值;2.LP问题的标准化（1）目标函数的标准化 MinZ=CXZ=-ZMaxZ=-CX为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能目目标标函函数数标

23、标准准化化示示意意图图为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能（2）约束条件的标准化 约束条件是类型 左边加非负松弛变量 约束条件是类型 左边减非负剩余变量 变量符号不限 引入新变量 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能将下面的线性规划问题化为标准型：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能LP解的基本概念及基本性质解的基本概念及基本性质1.基本概念满足约束条件的解称为线性规划问题的

24、可行解,所有可行解的集合称为可行域。基、基向量、基变量、非基变量基、基向量、基变量、非基变量在mn阶约束方程组中,若有一个mm阶的非奇异子矩阵B,则B为该LP的一个基。B所在列对应的向量为基向量，对应的变量为基变量，其余向量为非基向量。其余变量为非基变量。可行解可行解:为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基解基解(也叫也叫“基本解基本解”）基解的特点：基解的特点：1.基解的非零分量个数小于等于约束方程数 m2.基解是约束方程的交点。3.基解只满足条件约束，不一定满足非 负约束，因此基解中的分量有可能为负数。4.基解的个数

25、有限，不超过 。取一个基，令其中非基变量为0，可得相应基解。求基解的前提是取m个线性无关向量构成基。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2.基本定理定理1 LP的可行域为凸集定理2 基本可行解 可行解的非零分量对应的系数列向量线性无关定理3 基可行解 可行域的顶点定理4 若可行域有界，最优解一定在其顶点上为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能基本思路：基本思路：从可行域中某个基可行解开始，根据一定标准，转换到另一个基可行解，当目标函数最大时，就得到了

26、最优解。单纯型核心：单纯型核心：关键在于判别，使每次转换后结果更优，从而不必穷举所有顶点即可得到最优解。判别方法：判别方法：观察非基变量取值对目标函数的影响。单纯型法：单纯型法：定理定理1 1 当所有非基变量的检验数当所有非基变量的检验数 ,相应相应的基可行解为最优解。的基可行解为最优解。定理定理2 2 当还有非基变量的检验数当还有非基变量的检验数 ,则该则该解不是最优解。解不是最优解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1.1.化标准型化标准型单纯型求解步骤单纯型求解步骤2.2.建立初始单纯型表建立初始单纯型表,确定初

27、始基，求出初确定初始基，求出初始基可行解。始基可行解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能 b 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1Z3.3.计算检验数计算检验数 ，确定换入基变量和换出，确定换入基变量和换出基变量。基变量。0 02 23300000000 6 64 43 323000023000012816120000为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n换换入变量的确定入变量的确定 计算

28、计算，c C Bi a ij 可只计算非基变量的可只计算非基变量的，换入基变量，换入基变量 kmax，0 ，k对应的对应的 列为主元列。列为主元列。n n换换出变量的确定出变量的确定 计算计算 i，i b/a ik （当（当a ik 0时）时）只计算非负的只计算非负的a ik 对应的行，换出基变量对应的行，换出基变量 L min i ，L对应的行为主元行。对应的行为主元行。n n k列列L行的元素称为主元素，用行的元素称为主元素，用alk表示表示为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能Z 2 2 1 0 0 0 1 2 0

29、1 0 0 4 0 0 0 1 0 0 4 0 0 0 1 b 0 02 233000000006 64 43 3230000230000128161200000003 3 0 1 0 0 0 1/4 3 0 1 0 0 0 1/4 16 4 0 0 0 1 0 16 4 0 0 0 1 02 1 0 0 1 0 -1/22 1 0 0 1 0 -1/26 2 0 1 0 0 -1/26 2 0 1 0 0 -1/2Z Z9 92 0 0 0 0 -4/32 0 0 0 0 -4/3324-为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育

30、人功能4.迭代计算（求新的基本可行解）迭代计算（求新的基本可行解）5.重复重复3、4步，直至最优。步，直至最优。02030442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0324-Z14 0 0 0 -1/2 -1/8 0 X(3)=(2,3,2,0,8,0)Z=13X(4)=(4,2,0,0,0,4)Z=14 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能线线性性规规划划内内容容框框架架为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻

31、全国教育大会精神,充分发挥中小学图书室育人功能线性规划（线性规划（LP）问题的特殊解法）问题的特殊解法为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能单位运价B1B2B3B4发量A165344A244756A376583收量24341、运输问题：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能步骤：步骤：1）最小元素法确定初始方案：按运费最小优先供应原则（多个最小元素选最上一行最左边一个），划去行或列时一次只能划去一行或一列，最后一个同时划去行和列，保证表上又m+n-1个

32、格有数字（包括0）。2）求出检验数，判别是否最优。（对最小化问题，若每个空格的检验数 ，则方案达到最优。）（为了求出检验数，需画出闭回路(闭回路唯一)。）第偶数次拐角点运价-第奇数次拐角点运价为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3）求出调整量，在闭回路上调整。调整量：奇数次拐角点运量调整：奇数次拐角点运量-；偶数次拐角点运量+。（若表中有几个零出现，将最上一行最左边一个的零改为空格，其余保留，保证表上又m+n-1个格有数字。）另一种求检验数的方法：1）运价表上有调运量的数字加，2）同行或同列同时减去或加上同一个数，使其带

33、数字全部变为零，则未加的数字即为对应空格的检验数。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3）最大化问题用最大元素法建立初始方案。判别最优时,检验数 达到最优，其余与最小元素法相同。注：1）运输问题最优解不唯一。2）对于产销不平衡问题，可以虚加发点或收点来进行求解（发量大于收量，虚加一列，运价增加一列，并全部为零，在用最小元素法时，须先将库存一列去掉，再逐一选取最小元素）。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2、指派问题：Theorem1:如果从效率矩

34、阵的任一行（列）各元素减去该行（列）的最小元素（或加上某一正数），不改变问题的最优解。Theorem2:如果从效率矩阵的每一行分别减去该行的最小元素ai，每一列分别减去该列的最小元素bj，得到最优解。则目标函数（最小化）的最优值等于各行、各列减去数之和，即minZ=ai-bj为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能B1 B2B3B4A1314105A21041210A39141513A478119例：4人工作分派，效率矩阵如下如何分派使得问题最小化。(minZ=29)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神

35、,贯彻全国教育大会精神,充分发挥中小学图书室育人功能步骤：步骤：1）每行每列减去各行、各列最小元素，使每行每列至少有一个零元素。2）从零元素最少的行开始，对一个零元素标，表示一种分派，同时把该行、列的其余零元素划去，防止下次分派落在此行、列上，当某行零元素多于一个，则标注零元素最少的列。至所有零元素标注或划去为止。若得到n个0*，则0*改为1，其余改为0，即为最优分派。3）若0*少于n个，则作0*的最少覆盖集。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能B1B2B3B4B5A1127979A289666A3717121412A4

36、15146610A54107106例：求该指派问题的minZ为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能对没有0*的行打。对打行所有零元素列打。再对打列上0*行打。重复、，到不能打为止。对没有打行划线，对打列划线，其线条数=0*数。在没有划线的元素中找最小元素，对没有划线行各元素减去最小元素，对划线列各元素加上最小元素，得到新的效率矩阵，返回第2）步。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能B1B2B3B4B5A11518212420A21923221821A

37、32617161927A41821231725A51725202619再例：求该指派问题的minZ为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能注1：对最大化问题，采用构造一个新的效率矩阵 ，并取 ，则 注2：若效率矩阵mn（行数不等于列数），可虚设零行（列），使效率矩阵变成方阵，然后再用匈牙利法求解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能一二三零件数量A3560B7(1)457C46(1)8(1)143、生产配套问题：设每个车间都生产效率最高的零件3.667

38、.2745468为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能零件数量3.66（1）7.257（1）457468（1）8按开始的原则重新分配得：（若某列有相同的最大效率，选取时应位于不同行列上。把第一行的效率再扩大，该行乘以为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能420/3（1）8（x13）7（1）45468（x33）为使零件A和C的产量相等（配套），得：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功

39、能零件数量420/3（1）8（3/14）44/7 7（1）457468(11/14）44/7这时有得：4（x11）20/38（3/14）4（x21）16/720/74（x31）68（11/14）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能为使三个车间产量相等（配套），需把第一车间生产零件B的时间的一部分用来生产零件A和C，为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能零件A的产量为零件B的产量为零件C的产量为最优解为:(不唯一,可生产392/61(套)为深入学习习近

40、平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能若要求每个车间生产的零件必须为整数，则易得出：零件A：零件B：零件C：即一天可完成6套产品。（一车间6个B零件，二车间5个A零件，三车间1个A零件、6个B零件。）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4、森林管理问题：森林中树木每年要有一批被砍伐出售，为使森林不被耗尽而每年都有所收获，每砍伐一棵树，就应补种一棵幼苗，使的森林树木总数不变，希望有一个方案，在保持收获稳定的前提下，获得最大的经济价值。1）模型假设：树木按高度分成n级

41、，第k级高度在hk-1到hk之间（h0=0），其价值pk元，k=1，n，显然:0=p1p2pn，第一级为幼苗，价值为零（p1=0），开始时，森林中树木高度分布为第k级数量为xk。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能设每年砍伐一次，要使留下的数目与补种的幼苗其高度状态与初始状态相同。设yk为每年第k级所砍伐的棵数。设森林树木总数为S（固定），有在一个生长期（即两次收获之间）假设树木至多只能生长一个高度级（即从k级进入k+1级，也可能因某些原因留在第k级）。并假设每一棵幼苗都生长到被收获（不考虑死亡的可能性）。假设在每一个生

42、长期内，第k级的树木进入第k+1级的比例为gk，于是留在原级的比例为1-gk。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能2）模型的分析与建立记xik+1为k+1年的第i级数目为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能现在来考虑收获情形:维持每年收获期初=期末-收获+新种幼苗数有收获模型：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能保证对森林有持续收获，就相当于要求Y是常量。数学上相当于要求每年森

43、林树木分布状况相同，即存在X，使得X(k)=X，X即为模型的平衡解。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能它相当于以下关系式：可以看出，第一个方程为其余n-1个方程之和，且因Y为收获向量，则yi0。考虑到幼苗的经济价值为零，故不砍伐幼苗，y1=0，且仍用xk表示x，由方程组（1）可得：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能所以收获总价值再利用方程组（1）可得（其中p1=0）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神

44、,充分发挥中小学图书室育人功能数学模型归纳为数学模型归纳为为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能3）模型的求解对于线性规划问题，有两个定理：定理1：线性规划问题的可行域为凸集。定理2：线性规划问题的最优解在可行域的顶点上达到。由定理2知道:只要从某个高度级中收获全部树木，而不用收获其它高度级的树木，就可以得到最大持续收获。假定只收获第k级的全部树木，所以有由于第k级树木被全部收获，所以，当ik时，第i级就不存在树木，即xi=0。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学

45、图书室育人功能为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能所以收获第k级树木的收入：只要生长参数gi已知，就可以求出P的值，再比较k取不同值时的P值，从中确定持续收获的最大经济收入。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能4）数值举例：现已知某处森林具有6年的生长期，经过实地测量，得其生长矩阵各年龄树木价格分别为：为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能这里设森林中树木总数为S，若只收获第二

46、年（k=2）,此时若只收获第三年（k=3）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能若只收获第四年（k=4）若只收获第五年（k=5）为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能若只收获第六年（k=6）比较可知14.7S最大，应砍伐第三年中全部树木，使收益最大。即第一年树木占森林树木总数的52.5%，第二年树木占森林树木总数的47.5%。为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能运价B1B2B3B

47、4B5发量A1214325A2105217A3143216收量22545作业：作业：1.对下表所表示的运输问题建模并求解2.现要用10050厘米的板料裁剪出规格分别为4040 厘米与5020厘米的零件，前者需要25件，后者需要30件。问如何裁剪，才能最省料？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能电视台为某个广告公司特约播放两套片集。其中片集甲播映时间为20分钟，广告时间为1分钟，收视观众为60万，片集乙播映时间为10分钟，广告时间为1分钟，收视观众为20万。广告公司规定每周至少有6分钟广告，而电视台每周只能为该公司提供不多

48、于80分钟的节目时间。电视台每周应播映两套片集各多少次，才能获得最高的收视率？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能某厂生产甲、乙两种产品，生产甲种产品每件要消耗煤9吨，电力4千瓦，使用劳动力3个，获利70元；生产乙种产品每件要消耗煤4吨，电力5千瓦，使用劳动力10个，获利120元。有一个生产日，这个厂可动用的煤是360吨，电力是200千瓦，劳动力是300个，问应该如何安排甲、乙两种产品的生产，才能使工厂在当日的获利最大，并问该厂当日的最大获利是多少？答案：（甲20件，乙24件，获利4280元）为深入学习习近平新时代中国特

49、色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能药房有两种复合维生素制剂，甲种每粒含维生素A、B各1克，D、E各4克和C5克，乙种每粒含维生素A3克，B2克、D1克、E3克和C2克，一顾客每天需摄入维生素A不超过18克、B不超过13克、D不超过24克和E至少12克，问：(1)每天应服两种维生素各多少才能满足需要而且尽可能摄入较多的维生素C？(2)甲种复合维生素每粒1.5元，乙种复合维生素每粒1元，选择怎样的服法才能花最少的钱而又满足每天的需要，此时顾客摄入的维生素C是多少？为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发

50、挥中小学图书室育人功能某牧场所饲养一批动物，平均每头动物每天至少需要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 km2、400km