第三章数学规划模型

1 第三章 数学规划模型

§3.1 引言

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

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

一项工程由m个市供电，已知每个施工点对某种材料的需求为r I（单位：吨），施工点的位置坐标为（ai,bi）（以公里计），i=1,2,„„，m。现在要设立n个料场，已知每个料场这种材料的最大容量为qj（单位：吨），j=1,2,„„，n。时确定这n个料场的位置坐标，及各料场向各施工点的材料运量，在保证施工需求的条件下，使材料运输的总吨公里最小。

用（xj,yj）表示n个料场的位置坐标，wij表示第j料场向第I施工点的材料运量，则材料运输的总吨公里为

ijminjijdwZ11 （1）

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

ijd22)()(ijijbyax （2）

（1），（2）给出了这个模型的目标函数，模型的约束条件有三：

一是保证各施工点的需求ri,即

mirwnjiij,2,1,1 (3)

二是不超出各料场的最大容量qj,即

njqwjmiij,,2,1,1 (4)

三是对wij的自然要求

wijnjmi,,2,1,,,2,1,0 (5)

总商，这个模型概括为（3）—（5）下求（xj,yj）和wij,使由（1），（2）给出的目标函数Z最小。

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

Min Z=f(x) (6)

s.t. x21,(),(xxxRAn,„„，xn) (7)

这里x时n为向量，A时n为空间Rn的一个集合，f时n元函数。

§2.2生产计划

企业内部生产计划的制定是一项非常复杂的工作，让我们简要地分这样几个层次加以讨论。的以， 2 在工厂以及，根据市场需求和人力、设备条件，以最大利润为目标制定产品生产计划；第二，在车间一级，根据产品生产计划、生产流程、资源约束以及费用参数等，以最小成本为目标，制定生产批量计划；第三，在车间内部，根据产品的加工时间和顺序，以完工时间最早或设备均衡生产为目标，给出各产品的作业排序。此外，不论哪个层次，当目标不止一个是，将使问题更加复杂。

例1 某厂有n种产品J1，J2，„„，Jn,单位数量产品的利润为c1,c2,„„，cn,根据市场调查，起需求量不超过q1,q2,„„，qn,按照工厂的生产能力，单位数量Ji（I=1,2,„„,n）所需人力资源为a1i,所需设备资源为a2i,所需原料为a3i,而工厂的人力、设备、原料资源限制分别为b1,b2,b3,问工厂在制定生产计划时应如何确定这n种产品的产量。

这类优化问题建模的关键时确定决策变量、目标函数和约束条件，并用数学形式（符号、式子等）将它们表达出来。

决策变量应是问题要求确定的量——各产品的产量，记以xi（I=1，2，„„，n）；目标函数显然应是总利润

C=iniixc1 （1）人力、设备、原料及需求量的限制构成了约束条件

313212111bxanbxabxaiiiiniiinii （2），（3），（4）

nixqxiii,,2,1,0, （5）

问题归结为在条件（2）~（5）下求x1,x2,„„,xn,使（1）式给出的C最大。

例2 工厂已经拟定了对某种产品的需求量，

必如10个时段（可以一周或一天为一个时段）的

需求分别为d1,d2,„„,d10,该产品的生产流程如图

2—1其中1时（最终）产品，2~6是它的零部件，

箭头旁的数字是装配系数，如4个5装配1个3。

1~6统称项目。现再考虑两种费用：生产准备费

和储存费。如果某时段生产项目i，则需准备费si

（与生产数量无关）；如果将以后时段对i的需求也提前生产出来（目的在于节省准备费），则单位时段需存储费hi(可看作资金的积压)。假定各项目的生产能力都是无限的，即在一个时段内可以完成任意数量的生产，且各项目都不需要提前期。是制定各项目的生产批量计划，及每个项目每时段生产多少，使总费用最少。

解：决策变量是各项目在各时段的产量，记xij为项目i在时段j的产量(i=1,2,„„,6,j=1,2,„„，10)。目标函数是生产准备费与存储费之和，记Iij为项目i在时段j的存储量，则总费用可表示为

ijijIJiijijixyIhysZ()(61101 (1),(2) 3 其中0100)(xxx Iij与xij的关系可表为以下的约束条件

65410,,2,1432210,,2,1,332111,11,1ixixjixixixIxIjdIxIjjjjjijijjijjijj （3），（4）

其它约束条件有

xij,Iij0,Ii0=0 (5),(6)

于是问题归结为在条件（2）~（6）下求xij,是（1）给出的Z最小，这是无资源约束下多项目的生产批量模型。

在模型中没有考虑项目的生产费用，这是因为需求必须满足，各时段生产量之和是个常数，只要各项目单位数量的生产费用不随时段改变，那么总的生产费用仍为常数，所以最优决策与这部分费用无关。

例3 如果例1给出的问题还要考虑下列因素，试重新求解。

1）要力争发到并超过去年的总利润M；2）充分利用现有人力资源，但不希望增加劳动力；3）J1和J2属同类产品，但J1已经老化，将退出市场，故J1的产量不要超过J2。

解： 与例1只有一个目标不同，这里有3个目标，属于多目标决策问题，目标规划模型是解决这类问题的方法之一，其思路是首先引入一些新的决策变量，即对每个目标设一个正偏差变量和一个负偏差变量（指决策值与目标之间的偏差），然后利用权重系数，将多目标问题化为单目标问题，使这些偏差尽可能小。

对于本题，我们设利润超过M的部分为正偏差1d，不足M的部分为负偏差1d；人力资源超过b1的部分为正偏差d2+，不足b1的部分为负偏差d2-；J1产量x1超过J2产量的部分x2为正偏差d3+，不足部分为负偏差d3-。需要指出的是，由于决策值不可能既超过目标值，又未达到目标值，dk+,dk-(k=1,2,3)二者必有一个为零，即dk+dk-=0，且按定义，它们均为非负值。

按照问题的要求，在将这三个目标综合为单目标时，应使d1-,d2+,d2-,d3+尽量小（请注意，这里不包括d1+,d3-），设这三个目标的权重分别为p1,p2,p3,并不妨令p1+p2+p3=1,,那么这个模型的目标函数为

3322211)(dpddpdpZ （1）

而原来由利润给出的目标函数（例1（1）式）变为约束条件

Mddxcii11 （2）

原来的人力资源约束（例1（2）式）化为

12211bddxainii （3）

根据d3-,d+3的定义还应有约束 4 x1-x2+d3--d+3=0 (4)

例1中的其它约束条件仍然成立：

niqxbxabxaiiniiiniii,,2,1,313122 （5），（6），（7）

最后，再加上dk+,dk-的非负约束

dk+,d-k0 (8)

目标规划模型归结为，在条件（2）~（8）下求xi(I=1,2,„„，n)和dk-,dk+(k=1,2,3),使（1）式确定的Z最小。

§2.3分派与装载

生活和工作中经常碰到任务分派问题，如由5个人承担5项任务，由于个人的专长不同，他们完成各项任务的时间（或代价）不同，那么派谁去完成哪项任务使总的效率最高呢？类似的问题很多。

例4 车间有n项加工任务，分派给n个工人完成。已知每个人完成各项任务的时间（其中有若干人不能完成某几项任务），问如何进行任务分派，使所需总时间最少？

解：将工人编号为i=1,2,„„,n,任务编号为j=1，2，„„，n,第i人完成第j项任务的时间记为cij(若第i人不能完成任务j，则记cij=M，M是充分大的正数)，任务分派用如下的0—1变量表述：

否则人完成任务若分派第01jixij