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

《合肥工业大学系统工程导论第3章-数学规划基础.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章数学规划基础系统工程的主要目标是改造或建立系统，使系统的整体功能达到最优。而作为系统科学的技术基础之一的运筹学，就是从系统总体的角度寻求系统最优解的数学工具，它包括数学规划（第3章）、图与网络（第4章）、决策分析（第6章）等。本章着重介绍数学规划的基本概念以及相关算法。所谓数学规划，是指系统在一定约束条件下使某一评价目标达到最优（极值）的一种决策方法。数学规划的关键是从系统思想出发，在定性分析的基础上建立其数学模型。数学规划模型的一般形式为：系统在满足条件（1）的情况下，使评价目标达到最优（最大或最小值），即（2）

2、其中，式（1）是系统必须满足的限制条件的数学描述，通常由等式或不等式组成，称为约束条件，简记为s.t.（subjectto，意为“受…的限制”）；式（2）是系统评价目标的数学描述，称为目标函数。由于不同系统的目标函数和约束条件存在差异，则数学规划可以分为线性规划、非线性规划和动态规划等。下面我们主要介绍各数学规划模型的建立、求解及其结果分析方法。一、线性规划所谓线性规划，是指约束条件和目标函数均为线性的数学规划方法。根据系统评价目标是单个还是多个，可将线性规划分为单目标线性规划和多目标线性规划。（一）单目标线性规划1.问

3、题的提出在生产管理和经营活动中经常提出一类问题，即如何充分合理地利用有限的人力、物力、财力等资源，以便获得最佳的经济效益。例1（生产管理问题）某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问如何安排生产计划才能使工厂获利最多？产品Ⅰ产品Ⅱ限制设备（台时/件）128台时原材料A（kg/件）4016kg原材料B（kg/件）0412kg利润（元/件）23解上述所谓的“安排生产计划”问题，其实质就是要寻求一个

4、满足设备和原材料资源约束的可行的生产方案，以确保工厂能获得最大的利润值。假设产品Ⅰ、Ⅱ的产量分别为x1、x2，则该工厂的获利值f=2x1+3x2。由于可行的生产方案需要考虑不能超出设备的有效台时数限制，即x1+2x2≤8；同时，还要考虑满足A、B原材料资源的约束条件，即4x1≤16，4x2≤12。因此，工厂的目标是在满足设备和原材料资源限制的条件下，如何确定两种产品的产量x1、x2，使工厂的获利最大。综上所述，上述安排生产计划问题的数学模型为目标满足约束条件（s.t.）由此可见，将这类实际问题转换为数学模型的基本步骤可归

5、纳如下：（1）确定决策变量；决策变量必须是可控制的且常用x1,x2,…,xn表示，如例1中产品Ⅰ、Ⅱ的产量。（2）确定所要追求的目标（目的）；目标通常用决策变量的函数来表达，称为目标函数。目标可以是单一或多个的，这里着重讨论目标单一的情形，如例1中工厂的最大获利。（3）确定约束条件；将现实中的各种限制用含有决策变量的数学关系式（等式或不等式）来表达，称为约束条件，如例1中设备和原材料资源的限制。例2（环保问题）靠近某河流有两个化工厂，流经工厂1的河水流量是5×106m3/天，在两个工厂之间有一条流量为2×106m3/天的

6、支流，如图所示。工厂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=10

7、00x1+800x2。根据环保要求，从工厂1到工厂2之间的河流中污水含量不超过0.2%，则可得由于从工厂1排出的污水流到工厂2之前有20%会自然净化，且流经工厂2后河流中污水含量仍要不超过0.2%，故有此外，各工厂每天的污水处理量不应超过其污水排放量，则有x1≤2，x2≤1.4。因此，问题的目标是要求两个工厂处理污水的总费用最小。综上所述，上述环保问题的数学模型为目标满足约束条件（s.t.）1.数学模型的建立通过上述例题可知，应用单目标线性规划来解决实际的最优化问题时，必须符合以下特征（参见P34）：（1）所求问题都有一

8、个目标要求，且相应的目标函数可以用最大或最小值的形式来表达；（2）要达到最优目标，必须有多种方案可供选择；注意：每一组决策变量（x1,x2,…,xn）的取值就是一个具体方案。（3）所寻求的目标必然有条件约束；（4）目标函数和约束条件都是线性方程式，且决策变量具有非负性。因此，单目标线性规划问题的数学模型可归纳如下：目