合肥工业大学系统工程导论第章数学规划基础.doc

数学规划基础 系统工程的主要目标是改造或建立系统，使系统的整体功能达到最优。而作为系统科学的技术基础之一的运筹学，就是从系统总体的角度寻求系统最优解的数学工具，它包括数学规划（第3章）、图与网络（第4章）、决策分析（第6章）等。本章着重介绍数学规划的基本概念以及相关算法。 所谓数学规划，是指系统在一定约束条件下使某一评价目标达到最优（极值）的一种决策方法。数学规划的关键是从系统思想出发，在定性分析的基础上建立其数学模型。 数学规划模型的一般形式为：系统在满足条件 （1） 的情况下，使评价目标达到最优（最大或最小值），即 （2） 其中，式（1）是系统必须满足的限制条件的数学描述，通常由等式或不等式组成，称为约束条件，简记为s.t.（subject to，意为“受…的限制”）；式（2）是系统评价目标的数学描述，称为目标函数。 由于不同系统的目标函数和约束条件存在差异，则数学规划可以分为线性规划、非线性规划和动态规划等。下面我们主要介绍各数学规划模型的建立、求解及其结果分析方法。 线性规划 所谓线性规划，是指约束条件和目标函数均为线性的数学规划方法。根据系统评价目标是单个还是多个，可将线性规划分为单目标线性规划和多目标线性规划。 （一）单目标线性规划 问题的提出 在生产管理和经营活动中经常提出一类问题，即如何充分合理地利用有限的人力、物力、财力等资源，以便获得最佳的经济效益。 例1（生产管理问题） 某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问如何安排生产计划才能使工厂获利最多？ 产品Ⅰ 产品Ⅱ 限制 设备（台时/件） 1 2 8台时 原材料A（kg /件） 4 0 16kg 原材料B（kg /件） 0 4 12kg 利润（元/件） 2 3 解 上述所谓的“安排生产计划”问题，其实质就是要寻求一个满足设备和原材料资源约束的可行的生产方案，以确保工厂能获得最大的利润值。 假设产品Ⅰ、Ⅱ的产量分别为x1、x2，则该工厂的获利值f = 2 x1 + 3 x2。 由于可行的生产方案需要考虑不能超出设备的有效台时数限制，即x1+2 x2≤8；同时，还要考虑满足A、B原材料资源的约束条件，即4x1≤16，4x2≤12。因此，工厂的目标是在满足设备和原材料资源限制的条件下，如何确定两种产品的产量x1、x2，使工厂的获利最大。 综上所述，上述安排生产计划问题的数学模型为 目标 满足约束条件（s.t.） 由此可见，将这类实际问题转换为数学模型的基本步骤可归纳如下： 确定决策变量； 决策变量必须是可控制的且常用x1, x2, …, xn表示，如例1中产品Ⅰ、Ⅱ的产量。 确定所要追求的目标（目的）； 目标通常用决策变量的函数来表达，称为目标函数。目标可以是单一或多个的，这里着重讨论目标单一的情形，如例1中工厂的最大获利。 确定约束条件； 将现实中的各种限制用含有决策变量的数学关系式（等式或不等式）来表达，称为约束条件，如例1中设备和原材料资源的限制。 例2（环保问题） 靠近某河流有两个化工厂，流经工厂1的河水流量是5×106m3/天，在两个工厂之间有一条流量为2×106m3/天的支流，如图所示。工厂1每天排放工业污水2×104m3，工厂2每天排放工业污水1.4×104m3。从工厂1排出的污水流到工厂2之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应超过0.2%。若这两个工厂都各自处理一部分污水，工厂1处理污水的成本是1000元/104m3，工厂2处理污水的成本是800元/104m3，试问在满足环保要求的条件下，各工厂应分别处理多少污水，才能使两个工厂处理污水的总费用最小？ 解 假设工厂1和工厂2每天处理污水量分别为x1·104m3、x2·104m3，则两个工厂处理污水的总费用f = 1000x1 + 800 x2。 根据环保要求，从工厂1到工厂2之间的河流中污水含量不超过0.2%，则可得 由于从工厂1排出的污水流到工厂2之前有20%会自然净化，且流经工厂2后河流中污水含量仍要不超过0.2%，故有 此外，各工厂每天的污水处理量不应超过其污水排放量，则有x1≤2，x2≤1.4。因此，问题的目标是要求两个工厂处理污水的总费用最小。 综上所述，上述环保问题的数学模型为 目标 满足约束条件（s.t.） 数学模型的建立 通过上述例题可知，应用单目标线性规划来解决实