线性规划问题

线性规划LinearProgramming前言一线性规划的发展史参考书目：北京理工大学出版社，许万蓉，《线性规划》。山东科学技术出版社《线性规划》。29.183GMG管梅谷，郑汉鼎。研究线性规划最早的是苏联的П.В.канторович（康脱洛维奇），1939年，他发表了《生产组织与计划中的数学方法》一书。主要讨论了机床、负荷、下料运输等问题。但他提出的问题在当时并未引起人们的注意。他自己也未能提出一个统一的求解方法。在第二次世界大战期间，由于军事运输的需要，提出线形问题的解法，美国的经济学家柯普曼（Kounpman）也研究了运输问题。直到1947年，美国的G.B.Dautzip提出了求解线性规划的单纯形法，才使线性规划这门学科在理论上趋于成熟，并成功地运用到了工业、交通、农业、军事等各个领域内。使线性规划的理论与方法成为管理科学的重要内容。在当今电子技术高度发展的信息社会中，线性规划给人类在经济管理、生产管理、人才事务管理等方面发挥了巨大作用。现在对于成千上万个约束条件，成千上万个变量的线性规划问题在计算上已没有任何问题。据美国杂志对全美00家大公司的调查，线性规划的应用范围名列前茅，有85%的公司频繁使用线性规划。二线性规划问题的特点由于是管理科学的重要分支，也是它的最成熟，最完整的分支。而管理科学的特点是利用数学模型为管理人员提供方针，以便在现有信息的情况下作出有效的决策，或现有信息不足作出决策时，而去搜索更多的信息。这里我们要抓住以下几个要素：第一管理科学的核心是建立模型。即运用数学的抽象，住所要探讨对策问题最重要的特征。模型是现实的简化表示。笫二通过模型设计，给管理工作提供方便笫三进行有效决策所需信息的多少，决策所要探讨问题的复杂程度，而不决定于研究过程所用的工具。模型要求过多的信息就不是好模型。线性规划也是这样通过模型，求解，分析综合，为决策者提供科学决策依据。三线性规划的主要应用线性规划主要应用在以下几个方面：（1）在某一企业内部，如何配合产品的销售时间，在各部门的原料，产品的存储，分配的数量等最为合理。（2）在某一企业生产的产品数量（或产值），如何使现有的设备，人力，原料等条件限制下，合理组织生产，使经济效益最高。（3）在某地的交通网中，如何合理组织运输，使运费最小。（4）在市场上产品的（或原料）价格变动时，对于这些变动，企业如何做出最优决策。（5）合理下料问题，即利用某种原料下料时，如何达到既满足要求，又使原料最少。（6）配料问题，即生产由各种原料生产的的产品时（如混合饲料等）时，如何既满足规定的质量的标准，又使产品的成本最低。（7）库存问题，在仓库的容量及其他条件的限制下，确定库存物资的品种，数量，期限，使库存的效益最高。（8）在投入产出问题中，引进某一目标函数，制定最优的企业（或地区）经济计划。当前，我国正在进行以城市为重点的整个经济体制的改革，企业的自主权在扩大。一个企业要适应国内，国际的市场竞争，就必须改善经营管理，提高经济效益，制定最优的生产计划，并对瞬息万变的市场信息作出反映，应用现代数学方法，特别是线性规划方法，对于提高企业管理水平和企业活力，将会起着极大的作用。第一章线性规划问题概述§1.1线性规划问题举例及数学模型例1．（生产安排问题）某厂生产A,B两种产品。生产一吨A需用煤九吨，电力4千瓦，劳动力三个（以劳动日计算）；生产一吨B需用煤3吨，电力五千瓦，劳动力10个。已知一吨A可获利C1元，一吨可获利C2元。该厂现有煤360吨，电力200千瓦，劳动力300个，问：生产A,B各多少吨获利最大，试建立这一问题的数学模型。单位产品所需原料（单位）原料种类AB原料总数煤94360电力45200劳动力310300收益C1C2设生产A为X1吨，B为X2吨，而现在煤，电力，劳动力的消耗均有限制，所以应满足限制条件：煤耗：9X1+4X2≤360电耗：4X1+5X2≤200解：首先列出数据表：劳动力耗：3X1+10X2≤300生产数量：X1≥0X2≥0注意：约束条件两边单位一致从而此问题的数学模型为：求一组变量X1，X2值，使满足：0,0300103200543604921212121xxxxxxxx例2．设有钢材150根，长15米，需轧成配套钢料。每套由7根2米长与2根7米长的钢梁组成，问如何下料使钢材废料最少（设不计下料损耗）？解：依题意，每根钢材的下料有三种可能情形：1）截7米长0根，2米的7根，余1米废料。2）截7米长1根，2米长4根，无废料。3）截7米长2根，2米长0根。余1米废料。设用第j截法，用去钢材xj根（j=1，2，3）。则这批钢材截成7米长的钢梁为x2+2x3根，2米长的7x1+4x2根，废料总长x1+x3米.于是，得出问题的数学模型为：求一组变量x1,x2,x3,的值，使满足：（根数限制）根数钢材限制（配套限制）)(0,0,0)(150)47(72)2(3213212132xxxxxxxxxx例三（营养问题或配料问题）一个简化了的小鸡食物配方例。假定每天需要的混合司料质量是100斤，这分事物必须包含：1）至少0.8%但不超过1.2%的钙，2）至少22%的蛋白质，3）至少5%的纤维素。并且使废料总长f=x1+x3最少。主要配料是：石灰石，谷物，大豆粉，其营养成分如下：问应如何处理配料，使在营养和物质条件均满足的情况解：设生产100斤饲料，需用x1斤石灰石，x2斤谷物，x3斤大豆粉，于是可找出问题的模型：每斤配料中的含量配料钙蛋白质纤维每斤成本石灰石0.3800.000.000.164谷物0.0010.090.020.463大豆粉0.0020.500.081.250求f=0.064x1+0.463x2+1.250x3的值最小满足条件：0,0,010005.008.002.010022.050.009.0100008.0002.0001.0380.0)(100012.0002.0001.0380.01003213`232321321321xxxxxxxxxxxxxxxx钙由以上几个例子，我们看到，所建立的数学模型其目标函数和约束条件均是关于未知变量的线形函数。目的是要求目标函数在约束下的极大或极小。我们称这样一类模型为线性规划模型。建立数学规划模型主要由以下三个步骤（隐含着三个要素）1．确定决策变量，亦即选取适当的量为问题的待确定量，这是问题的基础。2．建立适当的约束条件。3．建立目标函数。下面我们再举一些例子说明如何建立线性规划模型：例四：（装配成套）某产品的一个单件包括四个A个零和三个B零件。这两种零件由两种不同原料制成，而这两种原料可利用的数额分别为100个单位和200个单位。由三个车间按不同的方法制造。下面表格给出每个生产班的原料耗用量和每种零件的产量。目标是确定每个生产班数使产品得配套数最大？175，，2解：设,x1,x2,x3是第1.23车间的生产班数，则三个车间生产零件A的总数是x+6x+8x生产零件B的总数是x+9x+4x1233每班进料（单位）每班产量（个数）车间原料1原料2零件1零件2186752596933884而原料1和原料2对应的约束条件分别是200896100358321321xxxxxx的最大值求标参数变成：中较小的一个。因此目和)3495,4867min(34954867321321321321xxxxxxyxxxxxx因为目标是要使产品总件数达到最大，而每件产品要4个零件A和3个零件B。所以产品的最大数额不能超过这是一个非线性的目标函数，可以通过变换转换成线性规划模型：求：.0,0,0,020089610035834954867321321321321321yxxxxxxxxxxxxyxxxyyf的最大值满足例6某厂准备在电视台做广告，根据电视台收费标准，播出时间有三种选择：时间（1）星期一至五18：30~22：30热门时间，每半分钟收费300元；时间（2）星期六、日18：30~22：30热门时间，每半分钟收费420元；时间（3）18：30~22：30以外的时间，即平时，每半分钟收费180元。工厂希望每天播出一次半分钟时间的广告。而电视台希望放在时间（2）的播出次数不0,0,0,02008961003580349504867321321321321321yxxxxxxxxxyxxxyxxxS.t.整理即得：求f=y的最大值要超过在时间（1）的播出次数，工厂则希望不要在星期一至五热门时间播出，以便平时也能看到广告播出。因此规定在时间（1）的播出每月不超过15次。所以规定在时间（2）的播出每月不少于4次。工厂估计，认为在时间（1）观众为平时的三倍。在时间（2）观众则为平时的五倍。试列出一个线性规划模型，确定一个月内播送广告的方案。使（1）观众最多，（2）费用最少。解：题中需要确定的是在不同的时间内各播出几次。以一个月30天来考虑，假定星期六、日共9天。设x为时间（1）播放次数。y为时间（2）播放次数。z为时间（3）播放次数。则x+y+z=30(每月中每天一次）电视台要求：y≤x厂方要求：x≤15及y≥4非负约束：x≥0，y≥0,z≥0.又一个月中:y≤9整理以上的约束条件得94150)0,30(300yxzzyxyxyx一标准形式:我们由上面的实际例子已经看到,线性规划问题的模型是由一组线性等式或不等式表示的约束条件及一个线性目标参数组成的.即下面的一般形式:求一组变量使满足),...2,1(njxj0,...,,),(.........),(...),(...21221122222221211111212111nmmmnmnmmnnnnxxxbbbxaxaxabbbxaxaxabbbxaxaxa或或或或或或§1.2线性规划的标准形式达到最大（或最小）为了便于求解线性规划，有必要找线性规划成一定形式，为下面的标准形式：0,...,0...............122112222212111212111mmnmnmmnnnnxxbxaxaxabxaxaxabxaxaxannxcxcxcf...2211并且使目标函数：的值，使满足nxxx,...,21求一组变量达到最大并且使目标函数其中nnmxcxcxcfbb...,0,...,022111因为一般形式的线性规划问题都能化成标准形式（后面介绍），因此只要会求解标准形式的线性规划问题，就会求解一般形式的线性规划问题了。下面介绍几种形式的标准线性规划[SLP]问题。1.缩写形式：)~1(0~1)0(..max)(11mjxmibxatsxcfSLPjnjijijnjjj矩阵形式：TmTnnbbbxxXcccoxbbAXtscxfSLP),...,(),...,(),,...,()0(..max)(111其中mnmmnnaaaaaaaaaA.....................2122221112110...00o注：向量非负，代表向量的各分量非负3.向量形式：nmnnnmnpppAaapaapaapnApppm...,............,...,,2112122111211则个列向量。即的是设家记住。学习中经常用到，请大这几种形式在我们以后则：)~1(,0)0(,max)(11njxbbxpxcfSLPjnjjjnjjj二化线性规划