《第三章线性规划的应用及计算机求解》由会员分享，可在线阅读，更多相关《第三章线性规划的应用及计算机求解（27页珍藏版）》请在金锄头文库上搜索。
1、3. 线性规划的应用及计算机求解迄今为止,线性规划可以说是最成功的定量分析工具之一。特别是随着信息技术的发展, 线性规划在国民经济的各行各业中,特别是在金融,企业管理,市场销售,人力资源,和生产管理等领域获得广泛应用。实践证明,利用线性规划分配资源可为企业和社会节约大量财富。在本章中,我们将要研究常见的资源配置问题并说明如何利用线性规划工具求解最优配置问题。对于那些愿意将工作完成更好的个人或机构,为满足某一特定目标而对有限资源进行分配是一件非常重要的工作。3.1线性规划在制造业中的应用:制定生产计划在制造行业中,利用线性规划制订企业的生产计划是非常普遍现象。详细的生产计划包括决定生产那些规格的
2、产品以及对应于每种产品的数量,同时生产计划一方面应当考虑市场需求和有效地满足企业现有的原材料,人力,材料供应,和设备加工能力等约束条件,另一方面应当考虑产品之间的关系。线性规划能够根据管理者的目标在各种可行的生产方案中挑选出一个最优的方案,比如说,寻求利润最大的生产方案。3.1.1汽车生产计划首都汽车制造厂生产五种不同档次轿车,而生产轿车的关键原材料或部件,以及熟练技术工人的工时都是有限的,工厂经营者需要决定每款轿车的产量,使得总利润最大。为了建立线性规划模型,我们首先定义决策变量如下: 豪华型轿车的产量 高档轿车的产量 中档轿车的产量 经济型轿车的产量 微型豪华轿车的产量每辆轿车的车身都必须
3、使用用同一种混合材料制造,其库存总量是。装配任何一款轿车都用到两种基础配件:配件和配件,而工厂现有库存量分别是件和件。装配线上的工人必须接受过专业训练,工厂技术工人的总工时为小时。我们假设其他在轿车生产过程中的其他辅助材料,零配件,像轮胎,皮革,塑料成品等可以随叫随到,不受限制,还假设其他工种工人的工时数不受限制。每款轿车的单车利润是单车销售收入减单车生产成本,假设各款轿车的单车利润分别为人民币,和万元,所以下述目标函数反应了生产计划的总利润:在资源使用方面,每辆豪华型轿车的车身需用去混合材料,高档轿车,中档轿车,经济型轿车,和微型豪华轿车的单车用料分别为,和。所以,混合材料构成的约束条件为:
4、 混合材料库存上限在每款轿车组装过程中,都必须用到配件和配件,其具体使用数量参见表:表: 配件和的消耗量汽车型号配件配件豪华型轿车 高档轿车 中档轿车 经济型轿车 微型豪华轿车 所以,配件和的总量约束构成了以下两个约束条件: 配件库存上限 配件库存上限用于豪华型轿车,高档轿车,中档轿车,经济型轿车,和微型豪华轿车上的装配工时分别为,和小时,下述约束条件成立: 装配工时上限从上面四个约束,即线性规划的约束条件仅适用于导致生产瓶颈的那些有限资源,也就是说,并不是所有生产要素都必须反应在线性规划的约束条件中。再考虑工厂的销售情况,由于工厂已经获得辆中档轿车和辆经济型轿车的订单,所以这两款车的产量必须
5、满足: 中档轿车需求量 经济轿车需求量历史订单数据表明,高档轿车与豪华轿车通常一起接到订单,平均来说,在收到辆高档轿车定单的同时至少会收到辆豪华型轿车的订单,所以,这两款车的产量存在下述关系: 高档轿车与豪华轿车定单数量关系历史订单数据还表明,微型豪华轿车的订单数量不会超过其他四款轿车订单总量的一半,即: 微型豪华轿车与其他轿车定单数量关系最后,所有轿车的产量必须是大于等于零,所以:我们给出汽车生产计划完整的线性规划模型: 3.1.2标准格式为了利用计算机求解汽车生产问题,有必要将线性规划的约束条件整理成标准格式。其基本要求如下:约束条件中的所有决策变量都必须出现在不等式的左端。所以约束条件:
6、 应表示为:约束条件中的决策变量顺序应与其定义顺序相一致。比如说,在所有约束条件中,变量都必须先于变量,就是根据它们的定义顺序。每个决策变量都有属于自己的系数。比如,约束条件:应当改写为:如果决策变量在约束条件中不出现,则给它们补系数。例如,约束:可被表示为:而约束:可被表示为:那么,线性规划问题的标准格式如下: 3.1.3松弛和剩余变量若对标准最大化线性规划问题的约束条件引入辅助变量,则可将不等式约束条件转化成等式约束条件。为了便于区分,通常称线性规划问题的决策变量为主变量。对于小于等于形式的约束条件,可以通过引进松弛变量将其转换为等式约束,比如对下述约束:引进松弛变量,其经济含义为混合材料
7、现存的库存数量。将增加到上式左端后,则获得等式约束条件:它的经济含意是已消耗混合材料数量, ,加尚未使用数量,等于总库存量。而对于大于等于类型的约束条件,则可引进剩余变量将其转换为等式约束条件,考虑问题中约束:引进剩余变量,其经济含义为中档轿车现存的产量。将增加到上式左端后,则获得等式约束条件:它的经济含意是中档轿车的产量减去剩余产量等于订单量辆。因为松弛变量和剩余变量都具有经济含意,它们必须大于等于零,即和。3.2利用计算机求解线性规划问题当一个线性规划问题只有二个决策变量时,我们可以通过几何方法求解,当线性规划问题的变量多于二个以上时,我们一般是利用单纯形法进行迭代求解。在第二章中,我们介
8、绍了如何设计单纯表格,利用手工进行求解的过程(从初始基可行解开始,确定主元素,以及利用高斯消元法完成迭代),但是随着决策变量和约束条件的增多,手工计算就难以完成大型线性规划问题的求解工作。如果将单纯形法编制成计算机软件,通过计算机求解就可以解决大型线性规划问题。随着信息技术的不断进步,求解线性规划问题的计算机软件也日趋丰富和多样化。为了方便大家对于求解线性规划问题工具的使用,在本书中我们主要介绍如何将电子表格作为求解工具。利用电子表格求解线性规划问题,如汽车生产问题,我们可以按照以下三个步骤进行:步骤 把线性规划问题的目标函数和约束条件的各项系数转换到标准表格中,参见表;步骤 把标准表格转换为
9、电子表格;步骤 利用的规划求解(在工具菜单下)求解线性规划。标准表格根据制订汽车生产计划的线性规划问题,我们首先将目标函数和约束条件的系数填充到标准表格中,参见表。表3.2: 汽车生产问题的标准表格决策变量 符号右端项目标函数 混合材料库存量 配件库存量 配件库存量 总装配工时 中档轿车需求量 经济轿车需求量 高档车与豪华车定单数量 微型豪华车与其他轿车定单数量 可以看出,标准表格包含了汽车生产问题的基本特征。标准表格的第一行是标题和决策变量,第二行是决策变量在目标函数中的系数,第三到十行分别是决策变量在约束条件的系数。电子表格格式然后我们设计表示汽车生产计划的电子表格。由于表格的行是以数字标
10、识,列是以字母标识,所以只要选中了表格中的一行和一列,就唯一确定了一个单元格。电子表格中的相关数据是根据标准表格转换而来,比如说,单元格H5中存放的是混合材料库存量数据。表3.3: 汽车生产计划的电子表格为了求解汽车生产问题,需要对电子表格进行扩展。表是对汽车生产问题在表基础上的扩充。表3.4: 汽车生产计划的扩充电子表格我们看到在扩充后的电子表格中,分别增加了行和行,以及列和列,其中第行与第行完全相同,代表的是决策变量,第行是决策变量的值,而列与列相同,列单元格分别计算目标函数和约束条件的左端项。对于资源约束行来说,列的单元格计算了各种资源被消耗的量。单元格(目标函数)的计算公式如下:单元格
11、(约束条件)的计算公式: 表还给出了汽车生产问题的生产方案为:,和时,列单元格的计算结果。资源消耗量分别为:混合材料(单元格),件配件(单元格),件配件(单元格),以及小时装配时间(单元格)。此外,由于单元格是,单元格是,满足市场对中档轿车和经济轿车的最低需求。同样道理,单元格为,单元格为,它们也没有破坏混合定单约束和。相对这个可行解的利润是(单元格)。从表我们还可以看出,通过分别将单元格到的计算值与汽车生产问题的右端约束项到进行比较,能够判断当前解到是否可行。表中到的值都小于等于到的值,所以这个生产方案是汽车生产问题的可行方案。而对于汽车生产问题的另外一个生产方案:, , ,和来说,它是不可
12、行方案,参见表。表3.5:汽车生产计划的不可行解我们注意到,虽然表中的利润是万元,但是该计划需要消耗件配件(单元格)和件配件(单元格),而配件和配件的库存量分别只有件(单元格)和件(单元格),所以这个生产计划是不可行的。 利用的规划求解求解线性规划问题最优解电子表格在其工具栏菜单下有一个规划求解模块,利用它可以求线性规划问题的最优解。我们将使用规划求解求解汽车生产问题的最优解。如果我们选中工具栏中的规划求解菜单条,就会弹出如下的规划求解参数对话框:表3.6: 汽车生产计划的规划求解参数对话框我们不难看出,规划求解参数对话框提供了三个最基本参数设置窗口:目标单元格,可变单元格,和约束。目标单元格
13、是存放目标函数的计算值,位于单元格,由于目标函数是求最大值,在等于选项中选择最大值。在可变单元格的对话框中输入,它们直接对应汽车生产问题的决策变量。为了对规划求解添加约束条件,我们首先点击规划求解参数对话框中约束选项右边的添加按钮,系统就会弹出如表所示的添加约束对话框:表3.7: 添加约束对话框我们可以根据约束条件的不等式方向进行批量输入,如表所示,头四个约束(电子表格的5到8行,即:)都是资源约束且都是符号,它们就可被一次性输入。同样道理,我们可以批量输入和,最后,在点击添加约束对话框的确定按钮之后,就回到规划求解参数对话框(表)。为了对决策变量加上非负限制,我们点击规划求解参数对话框右边的选项按钮,就会弹出规划求解选项对话框,在对采用线性模型和假定非负二个选项画勾后,就完成了变量的非负约束,参见表表3.8: 规划求解选项对话框到目前为止,我们已经完成对汽车生产问题利用进行计算所需要的参数设置,点击规划求解参数对话框(表)右上角的求解按钮,开始运算。在完成求解之后,规划求解结果对话框就会出现:表3.9: 规划求解结果对话框我们看到规划求解结果对话框的提示内容为:”规划求解找到一解,可满足所有的约束及最优状况” 。在选择保存规划求解结果之后,点击规划求解结果对话框中的确定按钮,就返回到扩充后的电子表格,参见表。表3.10:汽
