数学建模线性规划模型

数学建模西安交通大学理学院线性规划（LineProgramming)模型线性规划（LP）问题的模型建立1、运输问题：工厂123产量600400500某机电公司共有三个电机制造厂，并建立五个地区性仓库。公司先把产品运到这些仓库，以备向用户供货，三个厂每周生产电机台数如表：五个仓库每周需求量如表仓库12345需求量200250300550200运费仓库12345工厂121312242131321134由各厂到各仓库的运费（每台）如表电机公司希望建立一个满足制造厂的供应量和仓库的需求量并使总运费为最小的数学模型。运费仓库产量12345工厂141311600242134400321134500需求量200250300550200x11x23x35c11c23c35把m个发点的货物运到n个收点去，已知第i个发点的可供应量为ai(i=1,2,…,m),第j个收点的需求量为bj(j=1,2,…,n)，cij为从第i个发点到第j个收点的运输单价，应如何运输才能使总运费最省？一般的运输问题可叙述为：设xij为从第i个发点到第j个收点的运量不等式在某些条件下可能成为等式。1111min1.101,1mnijijijmijjinijijijZcXXbjnstXaimXimjn2、食谱问题：一公司饲养动物生长对饲料中三种营养成分：蛋白质、矿物质、维生素特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该公司买到五种不同的饲料，每种饲料1㎏所含营养成分如表饲料蛋白质(g)矿物质(g)维生素(mg)A10.300.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08饲料A1A2A3A4A5成本（元）27435每种饲料1㎏的成本如表要求确定既能满足动物生长所需，又使总成本为最低的饲料配方。建立数学模型：设xj(j=1,2,…,n)表示1㎏混合饲料中含第j种饲料的数量12345123451234512345min274350.320.61.8700.10.050.020.20.053.0.050.10.020.20.08100(1,,5)jZxxxxxxxxxxxxxxxstxxxxxxj饲料蛋白质(g)矿物质(g)维生素(mg)成本A10.300.100.052A22.000.050.107A31.000.020.024A40.600.200.203A51.800.050.085x1x2x3x4x5一般的食谱问题可叙述为：设有n种食物，每种食物中含有m中营养成分，用aij表示一个单位的第j种食物含第i种营养的数量，用bi表示每人每天对第i种营养的最低需求量，cj表示第j种食物的单价，xj表示所用第j种食物的数量，应如何搭配，能满足m种营养成分需求，又使食物总成本最低？11min1,,.01,,njjjnijjijjZcxaxbimstxjn3、河流污染与净化问题：某河流边上有两个化工厂，流经第一工厂的河水流量是每天500万m3，在两厂之间有一条流量为每天200万m3的支流。第一工厂每天排放工业污水2万m3，第二工厂每天排放工业污水1.4万m3，从第一工厂排放工业污水在流到第二工厂之前有20%可以自然净化，根据环保要求，河流中的工业污水含量应不大于2‰，若这两厂都各自处理一部分污水，第一工厂处理污水的成本为0.1元/m3，第二工厂处理污水的成本为0.08元/m3，问在满足环保的要求下，各化工厂应处理多少污水，使两厂总的处理污水费用最少？121121212min100080010.81.6.21.4,0Zxxxxxstxxxx设xj(j=1,2)为第j个化工厂每天处理污水量（河水流量中忽略了工厂的排入量。）模型为：工厂1工厂25002007004、合理下料问题：有长10m的钢管若干，现需裁出2m、3m、4m的钢管分别为20、15、15根。问如何裁，才能使浪费（根数）最少。方式1234567需求2m5332110203m0102102154m001012115余料0100100x1x2x3x4x5x6x7设xj用第j种方式下料所用钢管数，71123456712345671234567min533211020010210215.0010121150,1,,7jjjZXxxxxxxxxxxxxxxstxxxxxxxxj整数,请同学们考虑：如何裁，才能使浪费（料头）最少。模型为：一般的合理下料问题可叙述为：要利用某类钢材下A1,A2,…,Am一共m种零件毛料，根据省料原则，在一块钢材上设计出n种不同的下料方式，设在第j种下料方式中，可得Ai种零件aij个，设第i种零件的需求量为bi（如表）.问应采取什么方式，使既满足问题需要，又使所用钢材最少？方式1…n需求量A1a11…a1nb1……………AmAm1…Amnbm11min1,.01,njjnijjijjZXaXbimstxjn设xj为用第j种方式下料所用钢材数模型为：5、指派问题：某大学打算在暑期对三幢教学楼进行维修,该校让三个建筑公司对每幢楼的修理费用进行报价承包(见表,单位:万元),在暑期每个建筑公司只能修理一幢教学楼，因此该大学必须把各教学楼指派给不同建筑公司，为使报价总和最小，应指定建筑公司承包哪一幢教学楼？报价数目（万元)教学1楼教学2楼教学3楼建一公司132410建二公司171915建三公司202221x11x22x12x13x21x32x31x23x3310ijijxij第公司维修第栋楼第维修第栋楼不公司模型为：1112132122233132333131max(min)1324101719152022211(1,2,3).1(1,2,3)0,1(1,,,1,2,3)ijiijjijZxxxxxxxxxxjstxixinj一般的指派问题可叙述为：设有n项任务需派n个人去完成，但由于任务性质及个人专长不同，因此各人完成各任务的效率（或需时间、花费成本）不同，试问应如何安排，使总效率（或需时间、花费成本最少）最高？设tij表示第i个人完成第j件任务的效率10ijijxij第人去做第件任务第人不做第件任务1111max(min)1(1,,).1(1,,)0,1(1,,,1,,)nnijijijnijinijjijZtxxjnstxinxinjn模型为：6、投资决策问题：公司拟在某市东、南、西三区建立连锁店，拟议中有7个位置Ai(i=1,2,…,7)可供选择，规定东区在A1,A2,A3中至多选2个，西区在A4,A5中至少选1个，南区在A6,A7中至少选1个，并选用Ai点，投资bi元，估计每年获利ci元，但投资总额不得超过B元。问应如何选址，可使每年利润最大？10iiiAxA点被选用令点未被选用71711234567max2.110,1iiiiiiiZcxbxBxxxstxxxxx模型为：效率一二三A356B745C4687、生产配套问题：设第一、二、三个车间生产零件A、B、C的效率如下,假设三种零件各一个配成一套。应如何分配生产任务，可使生产的成套产品最多？设xij(i=1,2,3,j=1,2,3)表示第i个零件由第j个车间生产的生产时间。共生产配套产品Z套，x11x22x12x13x21x32x31x23x33模型如下:111213212223313233112131122232132333max3567454681.110ijZxxxZxxxZxxxZxxxstxxxxxxx一般的生产配套问题可叙述为：设有n个车间，要生产m种产品，假设这种产品每种一件配成一套。问如何安排任务，使生产的成套产品最多？设一天中第j个车间用于生产第i种产品的时间xij(i=1,…,m,j=1,…,n)，每天生产Z套，模型如下；11max1,,.11,,0nijijjmijiijZaxZimstxjnx8、森林管理问题：森林中树木每年要有一批被砍伐出售，为使森林不被耗尽而每年都有所收获，每砍伐一棵树，就应补种一棵幼苗，使的森林树木总数不变，希望有一个方案，在保持收获稳定的前提下，获得最大的经济价值。1）模型假设：我们把森林中的树木按高度分成n级，第k级高度在hk-1到hk之间（h0=0），其价值pk元，k=1，…，n，显然有p1＜p2＜…＜pn，第一级为幼苗，价值为零（p1=0），开始时，森林中树木高度分布为第k级数量为xk。设每年砍伐一次，要使每年维持收获，只能砍伐部分树木，留下的数目与补种的幼苗其高度状态与初始状态相同。设yk为每年第k级所砍伐的棵数。设森林树木总数为S（固定），有12nxxxS在一个生长期（即两次收获之间）假设树木至多只能生长一个高度级（即从k级进入k+1级，也可能因某些原因留在第k级）。并假设每一棵幼苗都生长到被收获（不考虑死亡的可能性）。假设在每一个生长期内，第k级的树木进入第k+1级的比例为gk，于是留在原级的比例为1-gk。2）模型建立：设X=(x1,x2,…,xn)T，1121110001000010001nngggGgg所以GX表示经过一个生长期后树木高度的分布。每次收获砍伐总数为1niiy而补种的棵数等于砍伐总数111niiygx要保持初始状态不变，有111(1,,1),0kkkkknygxgxkng因而有1122110nngxgxgx（否则，各级数目就会越来越少。）总收益:1111()nnkkkkkkkkPpyppgx1111((1,,1),0,0)kkkkknygxgxkngp11112112211max().......001,2,...,nkkkkknnnkPppgxxxxSstgxgxgxxkn数学模型归纳为以上各问题有以下特点：1）每一问题都用一组未知量来表示某一方案，其取值就表示特定方案，称之为决策变量。（通常为非负的）2）存在一定的限制条件，并用未知量的线性等式或不等式表示。3）有一个目标要求，并用未知量的线性函数表示，由实际要求，实现其最大化或最小化。LP的数学描述(数学模型)：（1）一般形式0,,,),(),(),(..)(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax或njxmibxatsxcZMinMaxjnjijijnjjj,2,10,2,1),(..)(11或（2）紧缩形式（3）矩阵形式0)(..)(XbAXtsCXZMinMax或其中:),,(21ncccC),,(21nxxxXmnmmnnaaaaaaaaaA212222111211Tmbbbb),,,(21（4）向量—矩阵形式：0)(..)(1XbxPtsCXZMinMaxnjjj或其中：njaaaPTmjjjj,,2,1,),,,(21),,,(21nPPPA线性规划问题主要解法是单纯形解法，一般用Lingo软件求解.线性规划（LP）问题的图解法若线性规划问题只有两个变量，则