数学建模线性规划省公共课一等奖全国赛课获奖课件.pptx

1-1 下料问题下料问题1-1 资源配置问题资源配置问题1-3 配料问题配料问题1-4 运输问题运输问题1-5 指派问题指派问题第1页2/638/5/20248/5/2024 某工厂生产一个型号机床，每台机床上需要某工厂生产一个型号机床，每台机床上需要2.9米、米、2.1米、米、1.5米长三种轴各一根，这些轴需要用同一个圆钢米长三种轴各一根，这些轴需要用同一个圆钢制作制作,圆钢长度为圆钢长度为7.4米。假如要生产米。假如要生产100台机床，应怎样台机床，应怎样下料，才能使得用料最省？下料，才能使得用料最省？分析分析 下料方式下料方式下料方式下料方式长度长度B1B2B3B4B5B6B7B8需要需要量量2.9米米211100001002.1米米021032101001.5米米10130234100余料余料0.10.30.901.10.20.81.4例例1 1 下料问题下料问题第2页3/638/5/20248/5/2024（1 1）若采取木工师傅下料方法：先下最长、若采取木工师傅下料方法：先下最长、再下次长、最终下短再下次长、最终下短(见下表见下表)下料方式下料方式 下料根数下料根数 2.9米根数米根数 2.1米根数米根数 1.5米根数米根数 B150100050B5330990B8120048B61022累计96100101100用此方式下料共用用此方式下料共用96根，节约用料根，节约用料4根，根，但这依然不是最好下料方法。但这依然不是最好下料方法。第3页4/638/5/20248/5/2024若要我们安排下料若要我们安排下料,暂不排除暂不排除8种下料方式中任何一个，种下料方式中任何一个，经过建立数学模型进行求解，寻找最好下料方案。经过建立数学模型进行求解，寻找最好下料方案。决议变量决议变量 目标函数目标函数.87654321xxxxxxxxS+=第4页5/638/5/20248/5/20242.9米、米、2.1米和米和1.5米圆钢数量均不低于米圆钢数量均不低于100根根 约束条件约束条件 下料方式下料方式长度长度B1B2B3B4B5B6B7B8需要需要量量2.9米米211100001002.1米米021032101001.5米米10130234100余料余料0.10.30.901.10.20.81.4非负非负 第5页6/638/5/20248/5/2024线性规划模型线性规划模型第6页7/638/5/20248/5/2024用用LINDO软件求解软件求解Min S=x1+x2+x3+x4+x5+x6+x7+x8;s.t.2*x1+x2+x3+x4=100;2*x2+x3+3*x5+2*x6+x7=100;x1+x3+3*x4+2*x6+3*x7+4*x8=100;end Global optimal solution found at iteration:3 Objective value:90.00000 Variable Value Reduced Cost X1 40.00000 0.000000 X2 20.00000 0.000000 X3 0.000000 0.1000000 X4 0.000000 0.000000 X5 0.000000 0.1000000 X6 30.00000 0.000000 X7 0.000000 0.1000000 X8 0.000000 0.000 Row Slack or Surplus Dual Price 1 90.00000 -1.000000 2 0.000000 -0.4000000 3 0.000000 -0.3000000 4 0.000000 -0.000最优下料方案最优下料方案第7页8/638/5/20248/5/2024 请考虑一下，本问题能不能将目标函数确定为请考虑一下，本问题能不能将目标函数确定为余料最少，为何？余料最少，为何？说明说明 下料问题是在经济和管理中经常碰到问题。本下料问题是在经济和管理中经常碰到问题。本例是条材下料问题、另外还有板材下料问题（如保例是条材下料问题、另外还有板材下料问题（如保险柜下料、服装厂下料等）或者更复杂下料问题。险柜下料、服装厂下料等）或者更复杂下料问题。第8页9/638/5/20248/5/2024例例2 资源最优配置问题资源最优配置问题 某工厂要安排一个产品生产某工厂要安排一个产品生产,该产品有该产品有、三种型号，三种型号，生产这种产品均需要两种主要资源：生产这种产品均需要两种主要资源：原材料原材料和和劳动力劳动力。每件产。每件产品所需资源数、现有资源数量以及每件产品出售价格以下表。品所需资源数、现有资源数量以及每件产品出售价格以下表。试确定这三种产品日产量使总产值最大。试确定这三种产品日产量使总产值最大。产品产品资源资源可利用资源可利用资源原材料(千克)436120千克劳动力劳动力(小时小时)245100小时小时价格（元）价格（元）453第9页10/638/5/20248/5/2024设生产产品设生产产品,数量分别为数量分别为x1,，x2,x3件件 产品产品资源资源可利用资源可利用资源原材料(千克)436120千克劳动力劳动力(小时小时)245100小时小时价格（元）价格（元）453用用LINDO软件求解软件求解.152max,0,16,18321=Sxxx第10页11/638/5/20248/5/2024 某企业喂养动物以供出售，每个动物每七天最少需要营养成某企业喂养动物以供出售，每个动物每七天最少需要营养成份蛋白质份蛋白质70g，矿物质，矿物质3g，维生素，维生素10mg，该企业能买到，该企业能买到5种不一样种不一样饲料，每种饲料饲料，每种饲料1kg所含各种营养成份和成本以下表所表示，求既所含各种营养成份和成本以下表所表示，求既能满足动物生长需要，又使总成本最低饲料配方。能满足动物生长需要，又使总成本最低饲料配方。营养营养 饲料饲料A1 A2 A3 A4 A5 营养最低要求营养最低要求 蛋白质蛋白质(g)0.3210.61.870矿物质矿物质(g)0.10.050.020.20.053维生素维生素(mg)0.050.10.020.20.0810成本（元成本（元/kg）0.20.70.40.30.5例例3 配料问题配料问题 第11页12/638/5/20248/5/2024设设需要需要5种饲料种饲料A1,A2,A3,A4,A5数量分别为数量分别为x1,x2,x3,x4,x5kg,营养营养 饲料饲料A1 A2 A3 A4 A5 营养最低要求营养最低要求 蛋白质蛋白质(g)0.3210.61.870矿物质矿物质(g)0.10.050.020.20.053维生素维生素(mg)0.050.10.020.20.0810成本（元成本（元/kg）0.20.70.40.30.5第12页13/638/5/20248/5/2024用用LINDO软件软件求解求解说明说明:该模型应该还要增加约束该模型应该还要增加约束（进行总量控制）（进行总量控制）第13页14/638/5/20248/5/2024 设有两个砖厂设有两个砖厂A1、A2，其产量分别为，其产量分别为23万块、万块、27万块，它们万块，它们生产砖供给生产砖供给B1、B2、B3三个工地，其需要量分别为三个工地，其需要量分别为18万块、万块、17万万块、块、15万块。而自各产地万块。而自各产地Ai到各工地到各工地Bj(i=1,2;j=1,2,3)运价以下运价以下表。问应怎样调运，才使总运费最省？表。问应怎样调运，才使总运费最省？平衡表平衡表(万块万块)运价表(元元/万块万块)产地 销地B1B2B3供给量B1B2B3A123506070A2276011060需求量需求量18171550例例4 运输问题运输问题 第14页15/638/5/20248/5/2024设设砖厂砖厂Ai供给工地供给工地Bj砖块数量为砖块数量为xij(i=1,2;j=1,2,3)最优解最优解平衡表平衡表(万块万块)运价表(元元/万块万块)产地销地B1B2B3供给量B1B2B3A123506070A2276011060需求量需求量18171550第15页16/638/5/20248/5/2024运输问题推广运输问题推广农作物布局问题农作物布局问题 某农场要在某农场要在B1,B2,Bn这这n块土地上种植块土地上种植m种农作物种农作物A1,A2,Am,各种土地面积各种土地面积bj、各种作物计划播种面积、各种作物计划播种面积ai、各种作物、各种作物在各块土地上单产在各块土地上单产cij(i=1,2,m;j=1,2,n)以下表。问以下表。问:应怎应怎样安排种植计划样安排种植计划,才使总产量最大？才使总产量最大？平衡表产量表农作物 土地 B1B2Bn播种面积B1B2BnA1a1 c11c12c1nA2a2c21c22c2nAmam cm1cm2cmn土地面积b1b2bn第16页17/638/5/20248/5/2024设设xij表示土地表示土地Bj种植农作物种植农作物Ai面积面积(i=1,2,m;j=1,2,n)平衡表产量表农作物 土地B1B2Bn播种面积B1B2BnA1a1 c11c12c1nA2a2c21c22c2nAmam cm1cm2cmn土地面积b1b2bn第17页18/638/5/20248/5/2024 这个问题数学模型与运输问题数学模型相同，统称这个问题数学模型与运输问题数学模型相同，统称为（经典）运输问题，还有其它问题也能够建立类似为（经典）运输问题，还有其它问题也能够建立类似结构数学模型。这类数学模型称为结构数学模型。这类数学模型称为康康希希问题。问题。关于运输问题有专门求解方法关于运输问题有专门求解方法表上作业法。表上作业法。康托洛维奇康托洛维奇希罕柯克希罕柯克第18页19/638/5/20248/5/2024解：解：设在设在2点、点、6点、点、10点、点、14点、点、18点、点、22点钟开始点钟开始上班服务员分别为上班服务员分别为例5 某饭店二十四小时中需要服务员数量以下表，假如每个服务员连续工作8小时，试问在2点、6点、10点、14点、18点、22点钟开始上班服务员为多少时，一天所需服务员人数最少？时间时间26610101414181822222最少服务员最少服务员48107124第19页20/638/5/20248/5/2024利用利用LINDO求解求解 min x1+x2+x3+x4+x5+x6stx1+x6=4x1+x2=8x2+x3=10 x3+x4=7x4+x5=12x5+x6=4endgin 6（6个变量个变量全为整数）全为整数）得到结果以下：得到结果以下：OBJECTIVE FUNCTION VALUE 1)26.00000 VARIABLE VALUE REDUCED COST x1 4.000000 0.000000 x2 4.000000 0.000000 x3 6.000000 0.000000 x4 8.000000 0.000000 x5 4.000000 0.000000 x6 0.000000 0.000000第20页21/638/5/20248/5/2024例例6 某学院男子篮球队要从某学院男子篮球队要从8名队员中选择平均身高最高出场名队员中选择平均身高最高出场阵容，队员号码、身高及擅长位置以下表所表示：阵容，队员号码、身高及擅长位置以下表所表示：同时要求出场阵容满足以下条件：同时要求出场阵容满足以下条件：中锋只能有一个上场；中锋只能有一个上场；最少有一名后卫；最少有一名后卫；假如假如1号队员和号队员和4号队员都上场号队员都上场,则则6号队员不能上场；号队员不能上场；2号队员和号队员和6号队员必须保留一个不出场。号队员必须保留一个不出场。写出该问题数学模型。写出该问题数学模型。队员号码队员号码12345678身高（身高（cm）1.921.901.881.861.851.831.801.78位置位置中锋中锋 中锋中锋 前锋前锋 前锋前锋 前锋前锋 后卫后卫 后卫后卫 后卫后卫第21页22/638/5/20248/5/2024解：解：设设 则可建立则可建立0-1规划模型：规划模型：第22页23/638/5/20248/5/2024利用利用LINDO求解求解01规划问题，得规划问题，得 max 1.92x1+1.9x2+1.88x3+1.86x4+1.85x5+1.83x6+1.8x7+1.78x8stx1+x2+x3+x4+x5+x6+x7+x8=5x1+x2=1x6+x7+x8=1x1+x4+x6=2x2+x6=1endint 8（8个变量全为个变量全为0,1变量）变量）得到结果以下：得到结果以下：第23页24/638/5/20248/5/2024例例7 某工厂生产某工厂生产A1,A2两种产品，产品分别由两种产品，产品分别由B1,B2两种部件组两种部件组装，每件产品所用部件数、部件产量限额以及产品利润以下表。装，每件产品所用部件数、部件产量限额以及产品利润以下表。问问:怎样安排怎样安排 A1,A2生产数量，该厂才能有最大利润？生产数量，该厂才能有最大利润？解：解：设生产设生产A1,A2分别为分别为x1,x2件，件，用用LINDO求出最优解：求出最优解：第24页