线性规划模型的 标准形式.doc

1、1第三部分 运筹学第四章 运筹学建模4.1 运筹学概述运筹学是用数学方法研究各种系统最优化问题的学科。其研究方法是应用数学语言来描述实际系统，建立相应的数学模型，并对模型进行研究和分析，据此求得模型的最优解；其目的是制定合理运用人力、物力和财力的最优方案；为决策者提供科学决策的依据；其研究对象是各种社会系统，可以是对新的系统进行优化设计，也可以是研究已有系统的最佳运营问题。因此，运筹学既是应用数学，也是管理科学，同时也是系统工程的基础之一。运筹学一词最早出现于第二次世界大战期间，当时为了急待解决作战中所遇到的许多错综复杂的战略战术问题，英美一些具有不同学科和背景的科学家，组成了许多研究小组，专

2、门从事军事行动的优化研究。研究的典型课题有：高射炮阵地火力的最佳配置、护航舰队规模的大小以及开展反潜艇作战的侦察等方面。由于受到战时压力的推动，加上不同学科互相渗透而产生的协同作用，在上述几个方面的研究都卓有成效，为第二次世界大战盟军的胜利起到积极作用，也为运筹学各个分支的进一步研究打下了基础。战后，这些科学家们转向研究在民用部门应用类似方法的可能性。因而，促进了在民用部门中应用运筹学有关方法的研究和实践。1947 年，美国数学家 GBDantzig 提出了求解线性规划的有效方法单纯形法。50 年代初，应用电子计算机求解线性规划问题获得了成功。50 年代末，工业先进国家的一些大型企业也陆续应用

3、了运筹学的方法以解决企业在生产经营活动中所出现的许多问题，取得了良好效果。60 年代中期，一些银行、医院、图书馆等都已陆续认识到运筹学对帮助改进服务功能、提高服务效率所起的作用，由此带来了运筹学在服务性行业和公用事业中的广泛应用。电子计算机技术的迅速发展，为广泛应用运筹学方法提供了有力工具，运筹学的应用又开创了新的局面。当前，运筹学在经济管理、生产管理、工程建设、军事作战、科学试验以及社会系统等各个领域中都得到了极为广泛的应用。一些发达国家的企业、政府、军事等部门都拥有相当规模的运筹学研究组织，专门从事运筹学的应用研究，并为上层决策部门提供科学决策所需的信息和依据。随着运筹学技术的推广应用，各

4、国都先后成立了运筹学研究的专业学术机构。早在1948 年，英国成立了运筹学俱乐部，并出版运筹学的专门学术刊物。1957 年，在英国牛津大学召开了第一届国际运筹学会议。1959 年，成立了国际运筹学联合会。我国于 1956 年成立了第一个运筹学小组，1980 年成立了全国运筹学会，这对促进我国运筹学的应用和发展起了积极作用，特别是著名数学家华罗庚教授早在 50 年代中期就在一些企业和事业单位积极推广和普及优选法、统筹法等运筹学方法，取得了显著成效。今天，我国有关高等院校不仅设置了运筹学专业，而且在管理类、财经类等的有关专业普遍开设了运筹学的必修课程。许多专业的硕土生，也设置了运筹学作为学位课程。

5、运筹学的实质在于模型的建立和使用。应用运筹学处理问题时，首先要求从系统观点来分析问题，即不仅要求提出需要解决的问题和希望达到的目标，而且还要弄清问题所处的环境和约束条件，包括：时间、地点、资金、原材料、设备、人力、能源、动力、信息、技术等的环境和约束条件，以及要处理问题中的主要因素、各种环境和约束条件之间的逻辑关系。运筹学是一门多分支的应用学科，随着新的系统问题的不断出现，运筹学的有关分支2也在不断的发展，内容在不断充实和扩大。其主要分支有：近年来，有关运筹学的应用和理论研究都得到迅速发展。在理论研究方面，涌现出许多新的模型方法和算法。随着运筹学在各种专业学科中的广泛应用，结合专业特点，产生和

6、发展了许多新的专业分支。研究的内容有：“军事运筹学” 、 “运筹学在卫生医疗系统中的应用” 、 “运筹学在交通运输中的应用” 、 “运筹学在旅游观光事业中的应用” 、 “运筹学在体育运动中的应用”以及“能源运筹学模型” 、 “教育运筹学模型” 、 “刑事司法运筹学模型”等。而且，运筹学与相关学科的交叉渗透还将进一步得到发展。另一方面，随着运筹学应用逐渐向复杂的社会大系统渗透运筹学的研究内容已出现了定量分析和定性分析相结合的发展趋势。同时，运筹学的发展与计算机技术的发展密切相关。计算机的飞速发展将深刻地影响着运筹学将来的发展。随着计算机技术的提高，许多目前还不能求解的运筹学问题在将来会被解决。运

7、筹学的应用也会被推向越来越广的领域。运筹学涉及到的理论和方法非常广泛，有些分支已发展完善为一门独立学科，限于篇幅，本书中只就线性规划、非线性规划的部分内容进行讨论，其他内容请读者参阅有关资料书籍。4.2 线性规划模型的标准形线性规划是求一个 函数 （称为目标函数）在规定条件nxf,21（称为约束条件）下的极大值或极小值问题。Axn,214.2.1 线性规划模型的可行解和最优解3定义 5.1 设线性规划模型的一般式为：nxcxcZ21ma(in)（5.1）约束条件（s.t.） njxbxaaxj mmmn ,21,0,21 222 1121（5.2）满足约束条件（5.2）的一组数 ，称为该线性规

8、划模型的可行解。nx,21满足目标函数，即使得目标函数达到最大值或最小值的可行解，称为该线性规划模型的最优解。把最优解代入目标函数所得到的目标函数的最大值或最小值称为最优值。定义 5.2 某个线性规划模型的全体可行解组成的集合，称为该线性规划模型的可行解域。4.2.2 线性规划模型的标准型为讨论方便，我们规定线性规划模型的标准型，而其它非标准型总可以通过一些方法化为标准型。线性规划模型的标准型为：目标函数 （5.3）nxcxcZ21ma约束条件（s.t.） （5.4）njxbxaaj mmn ,21,021 222 1注意，在线性规划模型的标准型中，约束条件是一组线性等式，也称为约束方程组，利

9、用向量或矩阵符号，线性规划模型的标准型还可以记为：目标函数 CXZa约束条件（s.t.） 0BA其中 ， ，ncC,21mnmnaa 2121124， ， 是指 的各分量 。mbB21nxX210X0,21nx标准型具有以下特点：（1） 目标函数是求最大值；（2） 约束条件为线性方程组；（3） 未知变量 都有非负限制。nx,21线性规划模型的非标准型，可以通过以下三种方法化为标准型：（一） 目标函数是求最小值 Zmi设 ，可设 ，则求最小值问题转化为求最大nxcxcZ21in Z值问题，即将求 转化为求 ，且 。ia nxcxc21a（二） 约束条件为不等式如果约束条件为不等式，则可增加一个或

10、减去一个非负变量，使约束条件变为等式，增加或减去的 这个非负变量称为松弛变量。例如： iniii bxaxa21加一个非负变量 ，使不等式变为等式：1nx iniii xx121如果约束为： iniii baa21则减去一个非负变量 ，使不等式变为等式：1nx iniii xx12（三） 模型中的某些变量没有非负限制若某个变量 取值可正可负，这时可设两个非负变量 和 ，令 ，这样jx jj jjjx就可以满足标准型的要求。4.3 线性规划模型的建立模型是线性规划解决问题的工具，线性规划方法通过对实际问题进行分析，建立其相应的线性规划模型，然后进行求解和分析，为决策提供依据。所建立的模型是否能够

11、恰当的反映实际问题中的主要矛盾，直接影响到所求得的解是否有意义，从而影响着决策的质量。因此，建模是应用线性规划方法的第一步，也是最为重要的一步。5建立线性规划模型有三个基本步骤：第一步，找出问题中的所有相关的未知变量（决策变量） ，并用代数符号表示它们，根据变量的物理性质研究变量是否有非负性；第二步，找出问题中的目标，写成变量的线性函数，作为线性规划模型的目标函数；第三步，找出问题中所有的限制或约束，写成变量的线性方程或线性不等式，作为线性规划模型的约束条件。4.3.1 生产计划问题生产计划问题是企业生产过程中时时遇到的问题，其最简单的一般形式可以描述如下：用若干种原材料(设备)生产某几种产品

12、，原材料(或设备) 供应有一定的限制，要求制定一个产品生产计划，使其在给定资源限制条件下能得到最大收益。例题 5.1 根据以下现实情况建立线性规划模型 某厂计划内将安排生产 I,II 两种产品，已知生产单位重量的产品所需的设备为 A 及B、C 两种原料的消耗如表 1 所示：I II 总用量设备 A 1 2 8材料 B 6 0 24材料 C 0 5 15表 5.1 生产设备和原料消耗表生产单位重量的产品 I 可获利 2 万，生产单位重量的产品 II 可获利 5 万。问：如何安排生产可使工厂获得的利润最多？解：模型建立：第一步，确定决策变量：要求的未知变量是 I,II 两种产品的产量，用 ， 分别

13、表示1x2它们；第二步，确定目标函数：本问题的目标是使工厂获得的利润 最大；125Z第三步，确定约束条件：在这个问题中，约束条件是设备及材料的限制，设备 A： 128x材料 A： 64材料 B： 25x则这一问题的线性规划模型为： 12maZs.t. 0,546821x64.3.2 合理下料问题下料问题是加工业中常见的一种问题，其一般的提法是把一种尺寸规格已知的原料，切割成给定尺寸的几种零件毛坯，问题是在零件毛坯数量要求给定的条件下，如何割才能使废料最少? 下料问题由所考虑的尺寸的维数可以分成三维( 积材) 下料，二维(面料)下料和一维(棒料 )下料问题，其中最简单的是棒料下料问题，现举一例来

14、讨论如何用线性规划方法解决下料问题。例题 5.2 某厂生产过程中需要用长度分别为 31 米、25 米和 17 米的同种棒料毛坯分别为 200、100 和 300 根，而现在只有一种长度为 9 米的原料，问应如何下料才能使废料最少?解 解决下料问题的关键在于找出所有可能的下料方法(如果不能穷尽所有的方法，也应尽量多收集各种可能的下料方法)，然后对这些方案进行最佳结合。对给定的 9 米长的棒料进行分割，可以有 9 种切割方法，见表 5.2 所示。表 5.2 毛坯切割方案表设用第 i 种方法下料的总根数为 ，则用掉的总根数为ix129xx废料总长度为： 123567890.3.0.9.8.0.40.

15、5x约束条件为所需的零件毛坯数量： 123452xx34678102593xx由此可得该问题的线性规划模型如下： 12356789min0.3.0.9.81.0.1.40.5Zxx4136782459923,0xxx7由于用掉的总料长度为 ，则有废料长度203.12.5301.78用料根数1380。94.3.3 合理配料问题这类问题的一般提法是：由多种原料制成含有 M 种成份的产品，已知产品中所含各种成份的比例要求及各种原料的单价，并且知道各种原料所含成份的数量，问应如何配料，才能使产品的成本最低。例题 5.3 根据对 77 种食物所含的九种营养物：热量( 糖与脂肪)、蛋白质、钙、铁、维生素

16、A、维生素 BI、维生素 B2、草酸与维生素 C 的成份及食物的市场价格调查，按照医生所提出的对每个人每天所需的营养要求，可得表 5.3表 5.3 食物营养成分表问怎样采购食物才能在保证营养要求的前提下花费最省？这就是营养问题或饮食问题，配料问题就是由此而推广来的。设每天购买甲，乙，丙，丁四种食物的数量分别为 ，即可列出如下的线性1234,x规划模型：（总花费最省）1234min0.8.50.91.5Zxx123423470.6.68.7,0xstx4.4 线性规划模型的图解法图解法是求解两个变量线性规划问题的一种简单直观的方法。两个变量线性规划模型的一般形式为：（5.5）21max(in)x

17、cZ8s.t. （5.6）0,21221xba该线性规划模型的可行解域是所有满足约束条件的数组 。21,x约束条件是一组线性等式或不等式。在几何上，两个变量的线性等式是平面上的直线。线性不等式 是半平面。可行解域就是由直线或半平面相交而成的平面bxa21区域，而每个可行解即为该平面区域上的一个点。例题 5.4 求以下线性规划问题的最优解：（1） 2134maxxZs.t. 0,521x（2) 4inZs.t. 0,183221x解：（1）第一步，求可行解域：可行解域是所有满足约束条件的数组 ，四个不等式是四个半平面，而可行解域21,x就是这四个半平面的公共部分。其形状为一个凸多边形区域，可行解

18、 是凸多边形内21,x的一个点，如图 5.1。0 551015OCABx2 x19图 5.1 例题 5.4（1）的可行解域第二步，求最优解：在几何上，目标函数 代表平面上的一个平行直线族，族中一条直线对应2134xZ一个 Z 值。凡落在同一条直线上的点 ，如果又落在可行解域上，那么这样的点就,是具有相同的目标函数值的可行解，所以平行直线族中的每一条直线又称为等值线。我们画出几条等值线，使每条等值线都和可行解域（凸多边形）有焦点，并且使等值线所对应的 Z 值递增。0 5510154x1+32=71254x1+32=12x2 X1图 5.2 例题 5.4（1）的最优解由观察可知，等值线离原点越远，

19、Z 值越大，而通过 B 点的等值线就是使目标函数值达到最大的等值线，这条等值线和凸多边形只相交于 B 点，因此 B 点为最优解。由解出 B 点坐标为 ，则该问题的最优解就是 ，最优值为 。51021x415, 415,465（2）线性规划的可行解域一般为凸多边形，而有时则是无界的凸多边形，如本题图5.3 所示。10-5 0 5 10 15 20 25 301020ABCD4x1+3x2=1x1+x2=12x1+3x2=18 Y X 图 5.3 例题 5.4（2）的可行解域若线性规划存在唯一最优解，则一定是可行解域的某个顶点。若两个顶点都是最优解，则这两个顶点连线上的任一点都是最优解，若可行解区域无界，则可能不存在最优解。4.5 线性规划模型的单纯形法单纯形方法是 1947 年由 G.B.Dantzig 提出的一种最有效的求解线性规划问题的方法。4.5.1 用换元迭代法解线性规划问题例题 5.5 求解线性规划模型 12max5Zxs.t. 12864,0x解：对上述线性规划模型进行标准化，得： 12ma5Zxs.t. 1234512386,0xx约束方程的系数矩阵