数学建模案例分析--最优化方法建模1引言

本章从生产计划、物资运输、产品试验、资源分配、任务均衡、投资决策等工程技术、经济管理和日常生活中的优化问题出发，建立它们的数学规划模型，着重阐述如何选择决策变量、构造目标函数、确定约束条件，内容涉及线性规划、非线性规划、整数规划、动态规划、多目标规划。对这些数学规划模型的解法不多做介绍。

§1 优化问题简介

优化是我们在工程技术、经济管理等诸多领域中最常遇到的问题之一。结构设计要在满足强度要求的条件下使所用材料的总重量最轻；编制生产计划要在人力、设备等条件下使产品的总利润最高；安排运输方案要在满足物资需求和不超过供应能力条件下使运输总费用最少；确定某种产品如橡胶的原料配方要使它的强度、硬度、变形等多种指标都达到最优。

人们解决这些优化问题的手段大致有以下几种：一是依靠过去的经验，这看来似乎切实可行，且不担风险，但会融入决策者过多的主观因素，从而难以确认所给决策的优越性；二是做大量的试验，这固然真实可靠，却常要耗费太多的资金和人力；三是建立数学模型，求解最优决策。虽然因建模时要作适当的简化，可能使结果不一定完全可行或达到实际上的最优，但是它基于客观的数据，又不需要太大的费用，具有前两种手段无可比拟的优点。如果在数学建模的基础上再辅以适当的经验和试验，就可以得到实际问题的一个比较的解答。在决策科学化、定量化的呼声日渐高涨的今天，这一方法的推广无疑是符合时代潮流和形势发展需要的。

我们经常遇到的优化问题的数学模型是什么样子呢？看一个实例：

一项工程有m个施工点，已知每个施工点对某种材料的需求为ri(i1,2,,m)（单位：吨），施工点的位置坐标为(ai,bi)(i1,2,,m)。现在要设立n个料场，已知每个料场这种材料的最大容量为（单位：吨）qj(j1,2,,n)。试确定这n个料场的位置坐标，及各料场向各施工点的材料运量，在保证施工需求的条件下，使材料运输的总吨公里最小。

用(xj,yj)(j1,2,,n)表示n个料场的位置坐标，wij表示第j料场向第i个施工点的材料运量，则材料运输的总吨公里为

mnijZwi1j1dij （1）

其中dij是第i个施工点与第j料场之间的距离。

dij22 (xjai)(yjbi) （2）

（1）,（2）给出了这个模型的目标函数，模型的约束条件有三个： 一是保证各施工点的需求量ri(i1,2,,m)，即

nj1 wijri,i1,2,3,m （3）

二是不超出各料场的最大容量qj(j1,2,,n)，即

nwi1ij qj,j1,2,3,n （4）

三是对wij的自然要求

wij0,i1,2,,m,j1,2,,n

（5）

综上，这个模型概括为在条件（3）~（5）下求(xj,yj)(j1,2,,n)和wij，使由（1），（2）给出的目标函数Z最小。

一般地说，这一类优化模型可以表达成如下的形式：

Min Zf(x) （6）xA(R),ns.t.x(x1,x2,xn) （7）

这里x是n维向量，A是n维空间Rn的一个集合，f(x)是n元函数，s.t.（subject to）是（受约束于）的意思。当然，Min（求极小）也可改为Max（求极大）。具体地说，x相当于上例中的(xj,yj)(j1,2,,n)和wij，f(x)由（1）、（2）式给出，A由（3）~（5）确定。

学过多元微积分的人一眼就可看出，这是多元函数的条件极值问题，它早已在微积分学中研究过，不妨称那里给出的解法是古典方法。不幸的是，大多数实际问题归结出的优化模型很难用古典方法求解，这是因为：

1、古典方法通常只能处理f(x)和A比较简单的情形，通常是求出解析解，而实际问题中的f(x)和

A比较繁杂，一般难以得到解析解。

2、古典方法通常只能处理n很小的情形，而实际问题中n往往很大，如几十到几万。比较有效的求解这类优化模型的方法属于20世纪中叶出现的运筹学的一个重要分支——数学规划。它主要包括：线性规划（LP）、非线性规划（NLP）、整数规划（IP）、动态规划（DP）、多目标规划等。许多介绍运筹学或优化算法的教材或专著，都以这些规划划分章节，分别讲述它们的解法，而这里我们则以实际问题分类，着重讨论怎样建立它们的数学模型，在附录中给出用软件的解法。