运筹学(简化)

《运筹学(简化)》由会员分享，可在线阅读，更多相关《运筹学(简化)（46页珍藏版）》请在金锄头文库上搜索。

1、第一部分第一部分 运筹学运筹学一、什么是运筹学？一、什么是运筹学？ 实例：一公司有： 三个工厂：A、B、C。 各工厂分别有 140 吨、120 吨、50 吨产品待运； 三个仓库：甲、乙、丙。甲库可存货 60 吨，乙库可存货 100 吨，丙库可存货 150 吨； 任一工厂到仓库的路程如表： 工厂仓库ABC甲9126乙613.54.5丙1.539问：如何调运货物才能使总的吨公里最小？直观思路：1、距离最短 A丙。 （140 吨） ； 2、B丙。 （10 吨） ；依此类推。 可得调运方案： 工厂仓库ABC存货量甲6060乙5050100丙14010150供应量14012050总和310总吨公里数14

2、01.560125013.5103504.51860。最佳方案：工厂仓库ABC存货量甲105060乙100100丙30120150供应量14012050总和310总吨公里数1395。对该问题如果利用数学符号（即建立数学模型）来表示,可如下讨论：设工厂 A 向仓库甲、乙、丙的调运吨数分别为、，工厂 B 向仓库甲、乙、11x12x13x丙的调运吨数分别为、，工厂 C 向仓库甲、乙、丙的调运吨数分别为、21x22x23x31x、，则调运货物的总吨公里数（相当于运输费用）为32x33x33323133222113121195 . 4635 .13125 . 169xxxxxxxxxz现在需要求该函数的

3、最小值，而限制条件为：0,1501006050120140333231232221131211332313322212312111333231232221131211xxxxxxxxxxxxxxxxxxxxxxxxxxx运筹学运筹学：以系统为研究对象，把系统的功能和特点用模型表示，通过对模型的定量分 析，从总体上寻求最优策略，为决策和揭露新问题提供数量根据，并以研究结果的应用为 目的，保证系统高效运行。 运筹学建立模型的最终目的是实现系统的最优化，帮助管理者作出正确的决策，使系 统正常有效地运行。这里的最优化是指在一定条件下求最优解（可以是求最大值，也可以 是求最小值） 。 运筹学研究系统的基

4、本方法由以下运筹学研究系统的基本方法由以下 5 个阶段构成个阶段构成： 第一阶段：观察所要研究的系统，确定存在的问题、影响问题的因素、约束、假设以 及准备优化的目标。 第二阶段：对系统进行描述建立模型。 模型的复杂程度视具体问题而定，过份简单则不能准确反映系统的实质，过份复杂则 造成求解的困难。模型是所研究系统的一个理想（简化的）表达形式。一个现实系统的性 质可能受到许多因素的影响，但是一般只有一小部分因素真正支配着系统的特性。建模时 应该抓住这些支配系统的因素，从现实系统中抽象出一个“假想的现实系统” ，然后把这些 因素之间的关系确定下来，并简化成一个适合于分析的形式，这种形式就是模型。 第

5、三阶段：根据实际条件对模型进行检验。 模型一旦确定，就应该根据实际条件对模型的正确性、可靠性进行分析检验。一般可 按照下述三种情况之一处理：（1）给出有关方程的统一的精确解法；（2）如果没有统一 解法，则可以代入具体数据进行测算，分析测算结果是否和实际情况相符；（3）如果该模 型不能用任何正规的数学方法处理，则可以用类比方法进行模拟处理。 第四阶段：分析模型。按优化目标的要求选取最优解，即在模型规定的约束条件下求 出符合目标函数要求的最优条件组合。 这一阶段还需要检验在这些约束条件下最优解的敏感程度，即弄清楚当约束条件之一 稍有变化时最优解会不会改变。经过检验，就可以知道最优解对各个约束条件的

6、依赖程度。第五阶段：贯彻执行。二、规划问题的几个基本概念：二、规划问题的几个基本概念： 决策变量：决策变量：规划问题需要求解的一组变量，这组变量的每一组定值就对应规划问题的一个具体实施方案。如上例中的；ijx目标函数：目标函数：规划问题一定有一个要求目标，并且这个要求目标可以表示为决策变量的 函数，问题的解决归结为寻求一组决策变量的值，使目标函数实现最大或最小；如上例中 的函数 z；约束条件：约束条件：每一个规划问题中，决策变量都要满足一定的约束条件，这些条件可用包 含决策变量的等式或不等式表示； 可行域：可行域：由约束条件所确定的决策变量的集合，可行域中的每一组决策变量的取值称 为可行解，如

7、上例中的第一个调运方案； 最优解：最优解：使目标函数达到最值的可行解，如上例中的最佳方案。 分分 类类：线性规划和非线性规划单目标规划和多目标规划注意：注意： 1、规划问题类似于高等数学中的多元函数的最值问题，如：例：求函数的最值，其中yxyxz6320, 0, 13,10yxyxyx决策变量：x, y目标函数：yxyxz632约束条件：0, 0, 13,10yxyxyx可行域：由不等式所确定的平面区域0, 0, 82,10yxyxyx10 yx82 yx可行域显然，可行域中的任何一个点，都满足约束条件，都是可行解，而要求的最值),(yx点应该是可行域中的最优解。 2、优化问题中目标函数和决策

8、变量必不可少，约束条件对于实际问题一般情况下也一 定存在，但是在利用软件求解时，没有目标函数也可以给出结果，但是这时的结果一般只 是一个可行解，并不是最优解。三、线性规划：三、线性规划： 1、线性规划的特征：目标函数和约束条件都是决策变量的线性函数。 2、一般形式： njjjxcz1max(min)mibxainjjij, 2 , 1),(1L njxj, 2 , 10L注意：1规划问题的理论求解方法很多，但是这里我们将不考虑具体理论方法，只需 要掌握软件求解即可。 2实际解决问题时，对于规划问题一定要对目标函数，以及每一个约束条件给于详细 的解释，不要不加解释只是纯粹的罗列公式。例 1 资源

9、最优利用问题 某厂生产甲、乙两种产品，需要煤、电力、水泥三种资源。生产每种产品 1kt 需要各 种资源的数量、各种资源的限量以及生产每种产品（kt）的利润（千元）如表所示。问在 这种条件下，应该安排生产甲、乙产品各多少，才能使该厂获得最大利润？产品 单位消耗资源甲 乙资源限量煤电力水泥2 11 20 3879产品利润4 5解：（1）问题中待确定的变量决策变量：甲、乙两种产品的生产量，1x2x（2）决策变量所受的约束。问题中受到限制的是煤、电力、水泥的数量。于是有：煤的总需求量不能超过供应量： 8221 xx电力的总需求量不能超过供应量： 7221 xx水泥的总需求量不能超过供应量： 932x此

10、外，甲、乙两种产品的生产量应该取非负值：，01x02x（3）建立目标函数。在三种资源供应量的限制下，合理安排两种产品的产量，使得总 利润2154xxz达到最大。（4）资源最优利用问题的数学模型：求，的值，使1x2x2154xxz达到最大，并满足： 0,9372822122121xxxxxxx例 2 物资调运问题设有两个仓库，分别储存水泥 23t 和 27t。有三个工地各需水泥21A A ，321B B B，17t，18t 和 15t (总存货量等于总需求量)。已知各仓库到各工地的单位运费如表所示，问应 如何调运，使运费最省？工地 运费仓库1B2B3B1A2A3 11 31 9 2数学模型：求变

11、量（从仓库运往工地的水泥数量）的值，使目标函数：ijxiAjB2322211312116116965xxxxxxz达到最小，并满足：3 , 2 , 1; 2 , 1,0 1518172723231322122111232221131211jixxxxxxxxxxxxxij例 3 生产安排问题 某车间的车工分、两级，各级车工每人每天的加工能力、成品合格率及日工资数 如表所示级别加工能力（个人天）成品合格率（）工资（元天）2401609795.55.63.6工厂要求每天至少加工配件 2400 个，车工每出一个废品，工厂要损失 2 元，现有级 车工 8 人，级车工 12 人，且工厂要求至少安排 6

12、个级车工。试安排车工工作，使工厂 每天支出费用最小。解：（1）决策变量：安排、两级车工的人数为，1x2x（2）分析约束条件：车工人数限制：，81x1262 x每天加工的配件总数限制： 即 240016024021xx302321 xx特殊约束：，且为整数01x02x（3）目标函数：这个问题的目标是使工厂每天的总费用最小。包括车工的工资和因为 出废品而造成的损失。每个级车工每天的费用： 工资：5.6 废品损失： 共计：20%)3240(2同理每个级车工每天的总费用为：18工厂每天的总费用为： 。211820xxz（4）数学模型：求求，的值，使1x2x211820xxz达到最大，并满足：整数且 且

13、0x,x302x3x12x6x8x2121221四、整数规划：四、整数规划： 1、整数规划：决策变量只能取整数值。 整数规划对应的线性规划：去掉整数规划中的整数限制，得到的一般线性规划。 2、常见基本模型： （1）最优生产计划问题 一家玩具公司制造三种玩具，每一种要求不同的制造技术，高级的一种每台需要 17 小 时加工装配劳动力，8 小时检验，利润 30 元。中级的每台需要 2 小时加工装配劳动力，半 小时检验，利润 5 元。低级的每台需要半小时加工装配劳动力，10 分钟检验，利润 0.6 元。 可供利用的加工劳动力为 500 小时，检验 100 小时，同时，据市场预测，对高级玩具需求 量不超

14、过 10 台，中级不超过 30 台，低级不超过 100 台。该公司应如何安排生产计划才能 使利润最大？ （2）工厂选址问题有个城市，每日需要某种物资的数量分别是，先在计划要在其中选取nnaaa,21L个城市，建造座生产这种物资的工厂。假设已知若在城市建厂，日产量最多为，mmjjb而建设费用为。设城市 到城市的单位运价为，问这个工厂应该设在何处，才能jfijijcm使得既满足需要又能使总费用最省？解：设变量 ，从城市 到城市运送的物资数量为，则可以 否则建厂在城市 0j1jyijijx建立如下数学模型：Min njjjninjijijyfxcz 111使得： , 2 , 1,010111njix

15、ymyaxybxijjnjjjniijiinjijL，或（3）背包问题一个背包的容积为。现有中物品可装，而每种物品都只能整件装入；物品的重Vnj量为，体积为。问如何配装，使得既不超过背包的容积，又使装的总重量最大？jjv解：设 ，则可以建立如下数学模型： 否则被装入物品 0j1jxMax njjjxz 1使得： n,1,2,j101 L，或jnjjjxvxv（4）指派问题 设有项任务，恰好有个人可以分别完成其中一项，但由于各人能力不同，由不同nn 的人去完成不同的工作所耗用的时间不同，具体所耗用的时间可用如下效率矩阵表示，C 问指派那个人完成那项任务，总耗时最少？效率矩阵：第 个人完成第项任务所耗时ijijcnnnnnncccccccccCLLLLLLL212222111211解：设 ，则可以建立如下数学模型： 否则项工作时完成第个人当分配第 0j i1ijxMin