《简介与线性规划(第一至四章)打印》由会员分享，可在线阅读，更多相关《简介与线性规划(第一至四章)打印（160页珍藏版）》请在金锄头文库上搜索。
1、1,运筹学研究的基本思想与方法,（1）基本思想 运筹学研究的是如何用科学的方法来解决某一比较复杂的系统的最优管理或运行问题。 模型就是某一物体或系统的替代物。模型有实物模型和数学模型。如果所用的替代物具有一种数学的形式或与其相似的符号形式（如逻辑形式），则为数学模型。数学模型又可分为确定型模型和随机型模型。 运筹学模型是数学模型的一种，其典型形式为： 如何确定可控变量应取的值，使效能指标达到最优化。这就是运筹学的基本思想。,2,（2）基本方法或工作步骤,提出和形成问题 实际问题 决策目标 问题中的变量 可能的方案以及行动步骤 问题的来龙去脉 建立模型 辩认并确定相关的变量 确定变量之间的关系,
2、3.测试模型 把以前的数据代入模型，看它所预言的结果与实际结果是否接近 修改模型时，分析模型中是否有不相关的变量、是否忽视了相关的变量、变量间的函数关系是否正确 4.得到问题的解决方案 用相应算法求解 软件求解 5.方案实施与控制 外在因素变化时，调整模型或方案以适应变化,3,1.3 运筹学在工商管理中的应用,生产计划 库存管理 运输问题 人事管理 市场营销 财务与会计,4,运筹学方法的使用情况,各个工商企业使用运筹学方法的频率不同，有的经常使用，有的只是偶尔使用。 大公司大企业使用运筹学方法的百分比高。据统计，88%的美国大公司使用预测方法，超过50%的大公司用运筹学方法制定生产计划、存储控
3、制、资金预算、运输方案等。 各种运筹学方法的使用程度也是不同的，统计、线性规划、网络计划、计算机模拟、决策论、排队论使用的频率高。如制造业中最经常使用的是网络计划，其次是统计、模拟、线性规划。,5,中国使用运筹学方法的情况,6,90年以前的一些经典应用,7,90年代以来的一些应用举例,8,1.4 学习管理运筹学必须使用相应的计算机软件，必须注重学以致用的原则,例如，有人要从北京去乌鲁木齐。在一百多年以前，我们应该告诉他如何配备粮草、银两、衣物，如何选购马匹、马车，挑选马夫和保镖，如何根据天气、地理条件和社会诸因素来确定行车路线和行程，更重要的是如何在几个月的行程中处理吃穿住行，应付突发事件等问
4、题；但是现在我们只需告诉他如何去北京飞机场，如何在乌鲁木齐下飞机后提取行李和坐车就可以了，其余的问题交给航空公司和机组人员就行了。完全没有必要为了一次旅行攻读空气动力学、喷气发动机设计和制造、飞行器驾驶手册等厚厚的教科书。 “他山之石，可以攻玉”。 计算机为运筹学提供解题工具。,9,Chapter Two Linear Programming,线性规划问题 线性规划模型 线性规划的求解 图解法 单纯形法 线性规划的应用,10,线性规划问题(P11) （生产计划）某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，以及资源的限制，如下表所示。该工厂每生
5、产一单位产品I可获利50元，每生产一单位产品可获利100元，工厂应分别生产多少产品I、 才能使工厂获得最多？,11,建立模型,第一步：确定决策变量(要决定的未知量) 第二步：确定追求目标、目标与决定变量 之间的函数关系(目标函数) 第三步：确定约束条件(决策变量受到的约束),12,生产计划问题的模型 1.确定决策变量：x1, x2 (x1 为产品I的生产数量, x2为产品II的生产数量) 2.确定目标函数：Z=50x1+100x2 3.寻找约束条件 s.t. (subject to) 设备限制：x1+x2300 原料A的限制：2x1+x2400 原料B的限制：x2250 非负条件： x1 0
6、，x20,13,靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3,在两个工厂之间有一条流量为每天200万支流，第一化工厂每天排放含有某种有害物质的工业污水2万m3，第二化工厂每天排放含有这种有害物质的工业污水1.4万m3。从第一化工厂排出的工业污水流到第二化工厂之前，有20可自然净化，根据环保要求，河流中工业污水的含量应不大于0.2%，这两个工厂都需要各自处理一部分工业污水，第一化工厂处理工业污水的成本是1000元/万m3，第二化工厂处理工业污水的成本是800元/万m3，现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小？,14,1
7、.确定决策变量：x1, x2 (x1第一化工厂每天处理污水 , x2为第二化工厂每天处理污水 ) 2.确定目标函数：Z=1000x1+800x2 3.寻找约束条件 处理污水量限制 ： 环保限制： 非负条件： x1 0 ，x20,15,16,市场调查公司（MSI）专门评定消费者对新产品、服务和广告活动的反应。一个客户要求MSI帮助确定消费者对一种近期推出的家居产品的反应。客户要求采取个人入户调查（分为日间调查和晚间调查），以从有孩家庭和无孩家庭获得回答。客户的合同要求依据以下条款进行1000个访问：1）至少访问400个有孩家庭；2）至少访问400个无孩家庭；3）晚间访问的总数量至少等于日间访问的
8、数量；4）至少40%有孩家庭必须在晚间访问；5）至少60%无孩家庭必须在晚间访问。 访谈成本见表所示。怎样安排，才能既满足合同要求，又成本最低？,练习,17,决策变量：对有孩家庭日间访问的数量x1、对有孩家庭晚间访问的数量x2、对无孩家庭日间访问的数量x3、对无孩家庭晚间访问的数量x4 目标函数：min z=20x1+25x2+18x3+20x4 约束条件：x1+x2+x3+x41000 x1+x2400 x3+x4400 x2+x4x1+x3 即- x1+x2- x3+x40 x20.4（x1+x2）即-0.4x1+0.6x20 x40.6（x3+x4）即-0.6x3+0.4x40 x1 、
9、x2 、x3 、x4 0,18,线性规划的数学模型,1. 每一个问题都用一组决策变量表示某一方案，这组变量的值就代表一个具体方案，一般这些变量的取值非负 决策变量 2. 存在一定的限制条件(如供求关系，生产任务、资源限制等) ，它们可以用变量的线性等式或线性不等式来表示，这些条件称为约束条件。 线性约束 3. 都有一个要求达到的目标，它可以用变量的线性函数（称为目标函数）来表示。根据需要要求目标函数最大化或最小化。 目标函数 -具有上面三个特征的问题是线性规划问题,19,建模过程 （P12）,1.理解要解决的问题，了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ， ，xn ），每一组
10、值表示一个方案； 3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标； 4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件,20,练习题：人员安排问题(P39),某昼夜服务公共交通系统每天各时间段（每4小时为一个时间段）所需的值班人员如下表所示。这些值班人员在某时段上班后要连续工作8个小时（包括轮流用膳时间在内）。问该公交系统至少需多少名工作人员才能满足值班的需要。,21,22,某地区在今后三年内有四种投资机会,第种：三年内每年年初投资，年底可获利润20%，并将本金收回； 第种：第一年年初投资，第二年年底可获利润50%，并将本金收回，但该项目投资不得超过二万元；
11、 第种：第二年年初投资，第三年年底收回本金，并获利润60%，但该项投资不得超过一万五千元； 第种：第三年年初投资，于该年年底收回本金，且获利40%，但该项投资不得超过一万元。 现在该地区准备拿出三万元资金，问如何制定投资计划，使到第三年年末本利最大。,23,24,25,截料问题(P46),某工程施工中需要制作10000套钢筋，每套钢筋有2.9米、2.1米和1.5米三种不同长度但直径和材质相同的钢筋各一根组成。目前可采购到的同类钢筋的长度均为7.4米，问应购进多少根7.4米的钢筋才能满足工程的需要？,26,27,运 输 问 题,28,问 题 分 析,29,模 型,30,某厂在今后四个月内需租用仓
12、库堆存货物。已知各个月所需的仓库面积数如表1所示。又知，当租借合同期限越长时，场地租借费用享受的折扣优待越大，有关数据如表2所示。租借仓库的合同每月初都可办理，每份合同应具体说明租借的场地面积数和租借期限。工厂在任何一个月初办理签约时，可签一份，也可同时签若干份租借场地面积数和租借期限不同的合同。为使所付的场地总租借费用最少，试建立一个线性规划模型。,31,32,33,34,35,36,37,38,39,引用（“”）记号，LP模型的一般形式可写为：,式中，常数Cj称为价值系数，aij是直接消耗系数，即变量xj取值为1时，第i种资源的直接消耗数量，bi是第i种资源的限制用量。,40,LP的向量表
13、示,C =（c1，c2，cn）, 是目标函数系数组成的行向量； X = ( x1 , x2 , xn)T , 是模型中所有变量组成的列向量； pj = ( a1j , a2j ,amj )T , 是约束条件中xj的系数组成列向量； b = ( b1 , b2 , ,bm )T , 是约束条件右边常数组成的列向量； O = ( 0, 0, , 0 )T ，是n维零向量。,41,LP模型的矩阵表示为,42,标准模型有四点要求：,1目标函数求极大值； 2除非负约束条件外，其他所有约束条件全为等式； 3约束等式右端常数项bi非负； 4决策变量取值非负。,43,如何化标准形？,当碰到最小化问题，即min
14、 z =CX 化标准形的方法：令z =-z(z =-CX)，min z=-CX 与max z=CX最优解相同，最优值反号 当约束条件是不等式 不等式左边加减一个非负变量(称松驰变量)化为标准形 当某个bi=0 ，替代 xk,44,45,46,标准化练习,47,答案,48,标准化练习,P24 课后习题3,49,LP问题的解的概念,可行解：满足约束条件的解X=(x1，x2，xn) 最优解：使目标函数达到最优值的可行解 基：已知A是约束条件的mn系数矩阵，其秩为m。若B是A中mm阶非奇异子矩阵(即|B|0),则称B是LP问题的一个基 基向量：基B中的一个列向量pi 基变量：与基向量Pi对应的变量xi
15、称为基变量(个数为m)，其它变量称为非基变量(n-m个) 基解：由一个基所求出的解称为基解，基解有可行的基解(称基可行解)，也有非可行的基解(称基不可行解),50,LP问题的求解：图解法,例：maxz=50x1+100x2 s.t. x1+x2300 x1+x2400 x2250 x10 x20,51,分别取决策变量X1, X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。,52,（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。,53,（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。,54,200,300,400,100,200,300,400,100,x1+x2300,2x1+x2400,x2250,X20,x10,B(50,250),Z=0 50x1+100x2,Z=27500 50x1+100x2,可行域,最优解,线性规划问题的最优解 一定是在可行域的顶点上,55,56,57,x1,x2,5,10,0,2x1+ x210,x1+x28,7,8,8,x27,max z=6x1+4x2,0=6x1+4x2,最优解,(X1=2， x2=6) z=36,s.t.,58,线性规划的图解法2,x1,x2,目标函数等值线,最优解,6,6,-8,4,max
