《运筹学的主要内容》由会员分享,可在线阅读,更多相关《运筹学的主要内容(9页珍藏版)》请在金锄头文库上搜索。
1、运筹学的主要内容运筹学一般应包括线性规划、非线性规划、整数规划、动态规划、多目标规划、网络 分析、排队论、对策论、决策论、存储论、可靠性理论、模型论、投入产出分析等等。线性规划、非线性规划、整数规划、动态规划、多目标规划这五个部分统称为规划论, 它们主要是解决两个方面的问题。一个方面的问题是对于给定的人力、物力和财力,怎样才 能发挥它们的最大效益;另一个方面的问题是对于给定的任务,怎样才能用最少的人力、物 力和财力去完成它。网络分析主要是研究解决生产组织、计划管理中诸如最短路径问题、最小连接问题、 最小费用流问题、以及最优分派问题等。特别在设计和安排大型复杂工程时,网络技术时重 要的工具。排队
2、现象在日常生活中屡见不鲜,如机器等待修理,船舶等待装卸,顾客等待服务等。 它们有一个共同的问题,就是等待时间长了,会影响生产任务的完成,或者顾客会自动离去 而影响经济效益;如果增加修理工、装卸码头和服务台,固然能解决等待时间过长的问题, 但又会蒙受修理工、码头和服务台空闲的损失。这类问题的妥善解决是排对论的任务。对策论是研究具有厉害冲突的各方,如何制定出对自己有利从而战胜对手的斗争策略。 例如,战国时代田忌赛马的故事便是对策论的一个绝妙的例子。决策问题是普遍存在的,凡属“举棋不定”的事情都必须做出决策。人们之所以举棋 不定,是因为人们在着手实现某个预期目标时,面前出现了多种情况,又有多种行动方
3、案可 供选择。决策者如何从中选择一个最优方案,才能达到他的预期目标,这是决策论的研究任 务。人们在生产和消费过程中,都必须储备一定数量的原材料、半成品或商品。存储少了 会因停工待料或失去销售机会而遭受损失,存储多了又会造成资金积压、原材料及商品的损 耗。因此,如何确定合理的存储量、购货批量和购货周期至关重要,这便是存储论要解决的 问题。对于一个复杂的系统和设备,往往是由成千上万个工作单元或零件组成的,这些单元 或零件的质量如何,将直接影响到系统或设备的工作性能是否稳定可靠。研究如何保证系统 或设备的工作可靠性,这便是可靠性理论的任务。人们在生产实践和社会实践中遇到的事物往往是很复杂的,要想了解
4、这些事物的变化 规律,首先必须对这些事情的变化过程进行适当的描述,即所谓建立模型,然后就可通过对 模型的研究来了解事物的变化规律。模型论就是从理论上和方法上来研究建立模型的基本技 能。投入产出分析是通过研究多个部门的投入产出所必须遵守的综合平衡原则来制定各个 部门的发展计划,借以从宏观上控制、调整国民经济,以求得国民经济协调合理的发展。运筹学的方法论包括以下几个部分:(1) 提出需要解决的问题:提出需要解决的问题,确定目标,并分析问题所处的环境和 约束条件。抓住主要矛盾,舍弃次要因素。(2) 建立模型:选用合适的数学模型来描述问题,确定决策变量,建立目标函数、约束 条件等,并据此建立相应的运筹
5、学模型。(3) 求解模型:确定与数学模型有关的各种参数,选择求解方法,求出解。解可以是最 优解、次优解、满意解。(4) 解的检验:首先检查求解步骤和程序有无错误,然后检查解是否反映现实问题。(5) 解的控制:通过灵敏度分析等方法,对所求的解进行分析和评价,并据此对问题的 提出和建模阶段进行修正。(6) 解的实施:提供决策所需的依据、信息和方案,帮助决策者决定处理问题的方针和 行动。另外,这六部分之间存在下图所示关系:解的实施11 线性规划问题举例例1.1.1某工厂用3种原料P, P , P生产3种产品Q , Q , Q。已知单位产品所需原1 23123料数量如表 1.1.1 所示,试制订出利润
6、最大的生产计划。单位产品所需原料数量(kg) 原料产品QiQ2Q3原料可用量P12301500P2024800P33252000单位产品的利润(千兀)354第一节 运输问题的模型1.1 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地,在每个产地 的供应量与每个销地的需求量已知,并知道各地之间的运输单价的前提下,如何确定一个使 得总的运输费用最小的方案。例山某公司从两个产地A1、A2将物品运往三个销地B 1、B2、B3,各产地的产量、 各销地的销量和各产地运往各销地每件物品的运费如下表所示,问:应如何调运可使总运输 费最小?表 2.1.1、销 产、地 地B1B2B3产
7、量Ai646200A2655300销量150150200例3.4.4 (一维背包问题)有一个人带一个背包上山,其可携带物品重量的限度为b。 设有n种不同的物品可供他选择装入背包中,已知第j种物品的重量为a 0,单位价值为 jc 0( j二1,2,n )。问此人应如何选择携带物品的方案,使总价值最大?第三节 目标规划问题的一些例子例 4.3.12 波德桑小姐是一个小学教师,她刚刚继承了一笔遗产,交纳税金后净得 50,000 美元。波德桑小姐感到她的工资已足够她每年的日常开支,但是还不能满足她暑假旅 游的计划。因此,她打算把这笔遗产全部用去投资,利用投资的年息资助她的旅游。她的目 标当然是在满足某
8、些限制的条件下进行投资,使这些投资的年息最大。波德桑小姐的目标优先等级是:第一,她希望至少投资20,000美元去购买年息为 6的 政府公债;第二,她打算最少用5,000美元,至多用15,000美元购买利息为 5的信用卡; 第三,她打算最多用10,000美元购买随时可兑换现款的股票,这些股票的平均利息为8; 第四,她希望给她的侄子的新企业至少投资30,000 美元,她侄子允诺给她7的利息。设:x =购买公债的投资额(美元)1x =购买信用卡的投资额(美元)2x 3=购买可兑换股票的投资额(美元)x =对她侄子企业的投资额(美元)4这个问题的线性规划模型如下:max z = 0.06x + 0.0
9、5x + 0.08x + 0.07x1234x + x + x + x 200001x 50002s.t.x 150002x 300004x , x , x , x 01234如果用线性规划的单纯形法求解这个问题,就会发现这个问题无可行解,或者说这个问 题“不可行”。只要检查一下第1、第 2、第 3 和第 6个约束,问题的不可行性是一目了然的。 简而言之,波德桑小姐没有足够的钱来实现她的愿望。然而,对于波德桑小姐来说,用线性规划得出的这样一个答案是不能使她满意的。而能 够使她满意的是,她希望知道即使不可能绝对地满足她的全部愿望,那么怎样才能尽可 能地接近于满足她的愿望?在这样一个更为实际的许可
10、条件下,我们假定她的目标优先等级 是:P1 :她的全部投资额不允许超过50,000 美元,这是一个绝对约束;P :尽可能的满足:用20,000美元购买公债,用5,00015,000美元购买信用卡。她2 认为购买信用卡比购买公债重要2倍;P :尽可能资助她的侄子30,000美元;3P: (1) 尽可能用10,000美元购买兑换股票, (2) 每年利息的总收入尽可能达到4,0004美元。那么,可以建立这个问题的目标规划模型:11maxz = Pd + + P (d- + 2d- + 2d+) + Pd- + P (d + + d +)x22343 64574x + x + x + x + dd +
11、 = 500001 2 3 411x + d d + = 20000122x + d d + = 50002 3 3s.t. 0jk k求解这个目标规划问题,得到的满意解是:x 1 =20,000 美元x =5,000 美元2x =03x =25,000 美元4 因此,我们得到了一个有意义的解,这个解能够最好地满足(即使不能绝对地满足)波德桑小姐的全部目标。事实上,在实际的决策中,决策者的某些目标不可能完全地达到,这本来也是很自然的事情。例 5.3.3 某车间需要在每月初供应一定数量的某种部件给总装车间。由于生产条件的变化,该车间在各个月份中生产每单位这种部件所需消耗的工时不同。各个月份的生产
12、,除供应下个月的需求外,其余部分可存入仓库供以后月份的需求。但因仓库容量的限制,库存部件的数量不能超过某一给定值H = 9,而开始库存量为2,期末库存量要求为0。已知半年期间的各个月份的需求量以及在这些月份中生产该部件每单位数量所需工时数如表 5.3.4所示。现在要求制定一个半年逐月产量的生产计划,使得既满足供应需求和库容的限制,又使得在这半年中生产这种部件的总耗费工时数最少。表 5.3.4月份( k )0123456需求量( d )k0853274单位工时( a )k111813172010例 7.4.3 某时装商店计划冬季到来之前订购一批款式新颖的皮制服装。每套皮装进价 是 1000 元,
13、估计可以获得 80 的利润,冬季一过则只能按进价的 50处理。根据市场需求 预测,该皮装的销售量服从参数为160 的指数分布,求最佳订货量。具有竞争或对抗性质的行为称为对策行为在这类行为中,参加斗争或竞争的各方各自 具有不同的目标和利益为了达到各自的目标和利益,各方必须考虑对手的各种可能的行动 方案,并力图选取对自己最为有利或最为合理的方案对策论就是研究对策行为中各方是否 存在着最合理的行动方案,以及如何找到这个合理的行动方案的数学理论和方法合作对策厂 完全理性非合作对策:1有限理性r多人对策,一二人零和对策-二人非零和对策按对策人数Y-二人对策广静态对策完全信息静态对策不完全信息静态对策完全信息静态对策动态对策不完全信息静态对策图 8.1.1