规划基本知识课件

1、第六章 数学规划模型 6.1 数学规划模型的基本知识6.1.1 数学规划模型的一般形式简单的优化模型往往是一元或者多元，无约束或者等式约束的最值问题。而在工程技术、经济金融管理、科学研究和日常生活等诸多领域中，人们常常遇到如下问题：结构设计要在满足强度要求的条件下选择材料的尺寸，使其总重量最轻；资源分配要在有限资源约束条件下制定各用户的分配数量，使资源产生的总效益最大；生产计划要按照产品的工艺流程和顾客需求，制定原料、零部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述一系列问题的实质是：在一系列客观或主观限制条件下，寻求使所关心的某个或多个指标达到最大（或最小）。用数学建模的方法对这

2、类问题进行研究，产生了在一系列等式与不等式约束条件下，使某个或多个目标函数达到最大（或最小）的数学模型，即数学规划模型。建立数学规划模型一般需要考虑以下三个要素：（1）决策变量：它通常是所研究问题要求解的那些未知量，一般用维向量表示，其中表示问题的第个决策变量。当对赋值后它通常称为该问题的一个解。（2）目标函数：它通常是所研究问题要求达到最大（或最小）的那个（那些）指标的数学表达式，它是决策变量的函数，记为。（3）约束条件：由所研究问题对决策变量的限制条件给出，允许取值的范围记为，即，称为可行域。常用一组关于决策变量的等式（）和不等式（）来界定，分别称为等式约束和不等式约束。数学规划模型可表达

3、成如下一般形式： 其中是对目标函数求最大值或最小值的意思，是“受约束于”的意思。由于等式约束总可以转化为不等式约束，大于等于约束总可以转化为小于等于约束，于是数学规划模型的一般形式又可简化为：6.1.2 数学规划模型的可行解与最优解由数学规划模型的一般形式，可行域可表达为： 满足约束条件的解即可行域中的点称为数学规划模型的可行解；使目标函数达到最大值或最小值的可行解，即可行域中使目标函数达到最大值或最小值的点称为数学规划模型的最优解。数学规划模型的求解本质就是在可行域中选择使得目标函数达到最优的点，在运筹学中对数学规划模型的求解进行了大量的研究和求解方法介绍，但总体来说数学规划模型的求解比较复

4、杂和繁琐，有些问题的求解非常困难。根据实际问题建立的数学规划模型，其结构往往非常复杂且数据量大，不能使用普通方法求解，目前数学软件已发展得比较成熟，可借助LINGO或MATLAB软件进行求解。6.1.3 数学规划模型的基本类型数学规划模型的分类方法较多，这里将数学规划模型按照下列方式划分：（1）线性规划模型：目标函数和约束条件都是线性函数的数学规划模型； （2）整数规划模型：决策变量要求取整数值的线性规划模型； （3）非线性规划模型：目标函数或者约束条件中有非线性函数的数学规划模型；（4）多目标规划模型：具有多个目标函数的数学规划模型。 本章主要介绍上述四类数学规划模型。此外还有如动态规划模型

5、等，可查阅清华大学编运筹学教材。6.2 线性规划模型6.2.1 线性规划模型的一般形式线性规划模型所解决的问题具有以下共同特征：（1）每个问题都可用一组决策变量 表示某一方案，决策变量的一组定值就代表一个具体方案。通常决策变量取值是非负的。（2）存在一定的限制条件（即约束条件），这些约束条件可用关于决策变量的一组线性等式或线性不等式来表示。（3）有一个目标要求（即目标函数），目标函数可表示为关于决策变量的线性函数。根据问题的需要，要求目标函数实现最大化或最小化。线性规划模型的一般形式如下： 目标函数： 约束条件： 用矩阵向量符号，可更简洁地表示线性规划模型的一般形式： 目标函数： 约束条件：

6、这里系数矩阵是矩阵，约束向量是列向量，价值向量是行向量。即：， ，关于线性规划模型的求解，目前已有相当完善的单纯形算法（详细参见清华大学编运筹学教材）。在实际建模中，由于数据庞大，借助于LINGO、MATLAB等数学软件进行求解是完全可以实现的。6.2.2 线性规划建模示例例6.1 货机装载问题 一架货机有三个货舱：前舱、中舱和后舱。三个货舱所能装载货物的最大重量和体积限制如表6-1所示。并且为了飞机的平衡，三个货舱共装载的货物重量必须与其最大的容许量成比例。 表6-1 重量、体积限制 前舱 中舱 后舱 重量限制（吨） 10 16 8 体积限制（立方米） 6800 8700 5300 现有四类

7、货物供该货机本次飞行装运，货物的规格以及装运后获得的利润如表6-2所示。表6-2 规格、利润 重量（吨） 空间（立方米/吨） 利润（元/吨） 货物1 18 480 3100 货物2 15 650 3800 货物3 23 580 3500 货物4 12 390 2850 问应如何安排装运，使得货机本次飞行获利最大？ 1. 模型假设（1）每种货物可以无限细分； （2）每种货物可以分布在一个或者多个货舱内； （3）不同的货物可以放在同一个货舱内，并且可以保证不留空隙。 2. 模型建立（1）决策变量本问题需要确定各种货物放在每个货舱内的重量，于是用表示第种货物放在第个货舱内的重量，：分别表示货物1，货

8、物2，货物3和货物4；：分别表示前舱、中舱和后舱。 以作为决策变量。（2）目标函数需要实现总利润的最大化，于是目标函数即为总利润函数： （3）约束条件供装载的四种货物的总重量约束： 三个货舱的空间限制约束： 三个货舱的重量限制约束： 三个货舱装入重量的平衡约束：综合上述分析，货机装载问题的数学模型为如下线性规划模型： 3. 模型求解使用数学软件MATLAB中的Linprog命令求解，求解结果为： 即使得货机本次飞行获利最大的装运安排为：货物1不装运；货物2在前舱装载10吨，在后舱装载5吨；货物3在中舱装载12.947吨，在后舱装载3吨；货物4在中舱装载3.053吨。货机本次飞行获利为：1215

9、16元。例6.2 连续投资问题某部门在今后五年内考虑给下列项目投资，已知：项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；项目D，五年内每年初可购买公债，于当年末归还，并加利息6% 。该部门现有资金10万元，问应如何确定这些项目每年的投资额，使到第五年末拥有的资金本利总额为最大？这个连续投资问题，与时间有关，属于多阶段决策问题，我们也可设法建立其线性规划模型。1. 模型假设（1）该部门现有资金10万元可

10、以完全用于投资；（2）每年产生的投资收益也可完全用于投资。2. 模型建立（1）决策变量设（）分别表示第年年初给项目A，B，C，D的投资额，以它们为模型的决策变量。根据给定的条件，将决策变量列于表 6-3中。表6-3 决策变量 项目第一年 第二年第三年 第四年第五年A 0B 00 00C 00 00D （2）约束条件由于项目D每年都可以投资，且当年末即能回收本息。所以该部门每年应把资金全部投出去，手中不应当有剩余的呆滞资金。因此第一年：该部门年初拥有10万元，可投资项目A与项目D，于是应有第二年：第二年初拥有的资金额仅为项目D在第一年回收的本息。而第二年年初可投资A、C、 D三个项目，于是第二年

11、的投资分配应为第三年：第三年初拥有的资金额是从项目A第一年投资及项目D第二年投资中回收的本利总和及。而第三年年初可投资A、B、 D三个项目，于是第三年的投资分配应为第四年与第五年：同以上分析，可得此外，对项目B、C的投资有限额规定，即：，（3）目标函数要求第五年末该部门手中拥有的资金额达到最大，于是目标函数可表示为：综合上述分析，这个连续投资问题的数学模型为如下线性规划模型： 3. 模型求解使用数学软件MATLAB中的Linprog命令求解，其结果可表示为表 6-4。 表6-4 求解结果项目第一年第二年第三年第四年第五年A3.47833.91304.50B00400C03000D6.52170

12、000到第五年末，该部门拥有的资金总额为14.375万元，即盈利43.75% 。6.3 整数规划模型6.3.1 整数规划模型的基本知识线性规划模型的决策变量取值可以是任意非负实数，但许多实际问题的建模中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划模型，称为整数规划模型。全部决策变量的取值都为整数的整数规划模型，称为纯整数规划模型；仅要求部分决策变量的取值为整数的整数规划模型，称为混合整数规划模型；要求决策变量只能取0或1值的整数规划模型，则称为0-1规划模型。 纯整数

13、规划模型的一般形式为： 0-1规划模型的一般形式为： 整数规划模型的求解比线性规划模型的求解要难得多，整数规划模型求解的困难在于模型的维数（决策变量与约束条件的个数）增加时，计算量将爆炸性（即按指数规律）增加。下面是一些有关整数规划模型常用的求解方法。（1）枚举法与隐枚举法：常用于0-1规划模型的求解，但模型的维数高时不可行。（2）分枝定界法：对纯整数规划模型和混合整数规划模型的求解均适用，比较可行。（3）割平面法：对纯整数规划模型和混合整数规划模型的求解均适用，比较可行。以上求解整数规划模型的详细算法，请参见清华大学编运筹学教材。在实际建模中，可借助于LINGO、MATLAB等数学软件对整数

14、规划模型进行求解。6.3.2 指派问题问题：设有项任务要派个人去完成，但由于任务的性质和个人专长不同，每个人去完成不同任务的效率（或所用时间）有所不同。试问应当派哪个人去完成哪项任务，使总的效率最高（或所用的总时间最少）？这类问题称为指派问题。设表示第人完成第项任务所需的时间，表示所用总时间。决策变量设置如下：由于问题的要求，每项任务均要有人去完成，即有又每人均要被分派任务，即有 以所用总时间作为目标函数，指派问题的解决归结为如下0-1规划模型： 对于指派问题的求解，已有较成熟的匈牙利算法（参见清华大学编运筹学教材）。在实际建模中，可用LINGO、MATLAB等数学软件进行求解。6.3.3 整

15、数规划建模示例例6.3 两辆平板车装载问题有七种规格的包装箱要装到两节铁路平板车上去。包装箱的宽和高是一样的，但厚度（t，以cm 计）及重量（w，以kg计）是不同的。表6-5给出了每种包装箱的厚度、重量以及数量。每节平板车有10.2m 长的地方可用来装包装箱（像面包片那样），载重为40吨。由于当地货运的限制，对于C5, C6, C7 类包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7cm。 试设计一种装车方案，使得浪费的空间最小。 表6-5 厚度、重量及数量包装箱类型C1C2C3C4C5C6C7厚度t/cm48.752.061.372.048.752.064.0重量w

16、/kg200030001000500400020001000数量/件87966481. 模型假设（1）各种规格的包装箱的宽和高是一样的，且满足装车的宽、高要求，平板车能装包装箱的数量只与包装箱的厚度与重量有关；（2）每件包装箱不能拆分装车；（3）每种包装箱可以分布在不同的平板车上； （4）不同的包装箱可以放在同一个平板车上，并且可以保证不留空隙。2. 模型建立（1）决策变量设（）表示在第节车上装载第种包装箱的数量，以为决策变量，只能取非负整数值。（2）约束条件以表示第种包装箱可用装车的件数，两节车的装箱数不能超过可用装车的件数，故有：以表示第节车可用装箱的长度，表示第种包装箱的厚度，每节车可装

17、的长度不能超过车能提供的长度，故有：以表示第种包装箱的重量，表示第节车的载重量，每节车可装的重量不能超过车能够承受的载重量，故有：对于C5, C6, C7类包装箱的总数的特别限制记为（），故有：（3）目标函数浪费的空间最小，即所装包装箱的总厚度最大。以所装包装箱的总厚度为目标函数，所装包装箱的总厚度表达式为：综合上述分析，两辆平板车装载问题的数学模型为如下整数规划模型： 3. 模型求解运用LINGO软件得到最优解：，最优目标值，即按此最优装车方案两辆平板车共剩余空间。另外，此模型完全适用于两辆平板车的载重量和可用装载空间不同的情形。例6.4 DVD在线租赁分配问题某网站有种DVD，每种DVD的

18、数量有限。需在该网站租赁DVD的顾客只要在线提交订单，网站就会通过快递的方式尽可能满足要求。网站规定顾客提交订单时，顾客应在订单上填写10种愿意观看的DVD，并且基于对这些DVD的偏爱程度，用1，2，10的数字对填写的10种DVD进行排序预定，其余种类的DVD填写数字0，表示不愿意观看。网站会根据手头现有的DVD数量和顾客的订单进行分发DVD，并且每位顾客每次只能获得3张DVD。表6-6中列出了网站手上20种DVD的现有张数和当前需要处理的100位顾客的在线订单，网站如何对这些DVD进行分配，才能使顾客获得最大的满意度？试建立其数学模型。表6-6 现有DVD张数和当前需要处理的会员的在线订单（

19、表格格式示例）DVD编号D001D002D003D004DVD现有数量812210顾客在线订单C00010020C00021090C000336100C000480541. 模型假设（1）网站对其顾客分配DVD时，只能向其提供已经预定的DVD，即订单中填写数字为0的DVD不分配给顾客；（2）每位顾客每次租赁只能获得3张或0张DVD；（3）顾客订单中对已预定DVD的排序数字1，2，10越小，表示顾客获得该种DVD的满意度越大，顾客获得没有预定DVD的满意度为0。2. 模型建立（1）决策变量定义如下0-1变量作为决策变量：（2）目标函数设有位顾客，网站共有种DVD，则顾客在线订单中的偏爱排序数字1

20、，2，10和0形成阶矩阵，记为，称为偏爱排序矩阵。表示第个顾客不愿意观看第种DVD；为1，2，10中数字之一时，数字越小表示第个顾客对第种DVD越偏爱，相应第个顾客获得第种DVD时，其满意度越高。为此按下列方式定义第个顾客获得第种DVD时的满意度指标：表示第个顾客不愿意观看第种DVD，其满意度为0；为1，2，10中数字之一时，数字越大表示第个顾客获得第种DVD时，其满意度越高。称为满意度矩阵。所有顾客获得各种DVD的总体满意度指标由下式表达：我们的目标即为实现总体满意度指标的最大化。（3）约束条件以表示第j种DVD的现有数量。显然，对每种DVD，要求分配的总量不超过相应的现有数量。即有：又根据

21、假设，网站只向会员提供其预定的DVD，即只有当满意度指标不为0时，才可以进行分配。故引入约束：进一步，对每个顾客每次租赁只能获得3张其预定的DVD或不能得到DVD，于是有：引人0-1变量，上述约束条件又可表达为：综合上述分析，DVD在线租赁分配问题的数学模型为如下0-1规划模型： 3. 模型求解引用2005年全国数模竞赛所给数据，利用LINGO软件对上述0-1规划模型进行求解是完全可以实现的，这里求解结果略。6.4 非线性规划模型6.4.1 非线性规划模型的基本知识在数学规划模型中，如果目标函数或约束条件、中包含非线性函数，就称这种规划模型为非线性规划模型。称为非线性规划模型的可行域。定义6.

22、1 若有，使得，均有（或）则称为非线性规划模型的全局最优解。定义6.2 称为点的邻域，其中，为向量的模；若有，使得均有（或）则称为非线性规划模型的局部最优解。一般说来，求解非线性规划模型要比求解线性规划模型困难得多。而且，也不像线性规划模型的求解有单纯形法这一通用算法，非线性规划模型目前还没有适于各种问题的一般算法，各种算法都有自己特定的适用范围。由于非线性规划模型的复杂性，在求解非线性规划模型的过程中，有时只能找到模型的局部最优解，局部最优解还不一定是全局最优解。特别，若某非线性规划模型的目标函数为决策变量的二次函数，约束条件与线性规划模型一样全是线性等式和线性不等式，称这种特殊形式的非线性

23、规划模型为二次规划模型。二次规划模型的一般形式为： 这里系数矩阵是矩阵，约束向量是列向量，是实对称矩阵，是列向量。 二次规划模型有成熟的求解算法，特别当是正定或半正定矩阵时，可得到全局最优解。用LINGO、MATLAB等数学软件进行求解也较为方便，二次规划模型有着非常广泛的应用。6.4.2 非线性规划模型的常用解法介绍非线性规划模型在工程计算和经济管理中经常遇到，近二十年来对非线性规划模型求解算法的研究有了很大发展，其求解方法大体可分为以下几类：（1）利用问题的最优性条件来求解的方法。（2）利用线性规划或二次规划来逐次逼近求解的方法，例如线性逼近法、二次逼近法等。（3）把约束非线性规划模型转化

24、为一个或一系列无约束非线性规划模型来求解的方法，例如惩罚函数法、精确惩罚函数法、乘子法等。（4）对约束非线性规划模型不预先进行转换，直接进行处理的分析方法，例如可行方向法、梯度投影法、广义既约梯度法等。（5）对约束非线性规划模型不预先进行转换的直接求解方法，例如复形法、随机试验法等。对于上述一系列关于非线性规划模型的求解方法，可详细参见清华大学编运筹学教材等参考文献。目前，如乘子法、精确惩罚函数法、广义既约梯度法、二次逼近法等方法都已开发成计算机软件，并在实际应用中获得成功。6.4.3 非线性规划建模示例例6.5 股票组合投资问题现有一笔资金决定进行股票投资，以一年为一个投资周期。市场上有种股

25、票（）可供选择，投资这种股票在过去年份的收益率情况可统计得到。对各种股票按适当的资金比例进行投资称为组合投资。一般组合投资能够满足达到一定的总体预期收益率，同时有效降低总体风险。（1）试设计一种组合投资方案，即确定投资各种股票的资金比例，使总体收益率至少达到，并且总体风险尽量小。（2）表6-7中给出了三种股票过去十二年的投资收益情况，试就只有表6-7中三种股票可供选择时进行计算。表6-7 三种股票过去十二年的投资收益情况股票第1年1.3001.2251.149第2年1.1031.2901.260第3年1.2161.2161.419第4年0.9540.7280.922第5年0.9291.1441

26、.169第6年1.0561.1070.965第7年1.0381.3211.133第8年1.0891.3051.732第9年1.0901.1951.021第10年1.0831.3901.131第11年1.0350.9281.006第12年1.1761.7151.908注：表6-7中的第一个数据1.300的含义是股票在第1年年末价值是其年初价值的1.300倍，即收益率为，其余数据的含义依次类推。1. 问题分析人们投资某股票时的收益率是不确定的，可将收益率视为一个随机变量，因此用收益率的平均值即数学期望值来表达投资某股票时的期望收益率。除了考虑期望收益率外，还要考虑风险，一般投资某股票的收益率越不稳

27、定即波动幅度越大，就认为其风险越大，因此可用收益率的方差来衡量投资某股票的风险：方差越大，则认为其风险越大；方差越小，则认为其风险越小。同时还应考虑股票间的相关性，由概率论的知识可知，两种股票收益率的协方差表示的则是它们之间的相关程度：（1）协方差为时，两者不相关；（2）协方差为正数时，表示两者正相关，协方差越大则正相关性越强，即越有可能一赚皆赚，一赔皆赔；（3）协方差为负数时，表示两者负相关，即越有可能一个赚，另一个赔。2. 模型假设（1）影响投资决策的主要因素为期望收益率和风险两项，不受意外因素影响；（2）用收益率的方差来衡量风险，用收益率的协方差来衡量股票间的相关程度；（3）遵守占优原则

28、：同一收益率水平下，选择风险低的投资方案；（4）不考虑交易费用；（5）手上现有资金全部用于股票投资。3. 模型建立（1）决策变量以，分别表示投资于，这种股票的资金比例，则向量表示一个投资组合，以其作为决策变量。（2）目标函数设，分别为投资，这种股票的收益率，则其期望收益率分别为，。按投资组合进行投资时，其组合收益率为，也是一个随机变量，期望组合收益率为：组合风险（即组合收益率的方差）为：注：符号表示数学期望，表示方差，表示与的协方差。我们的目标是希望组合风险尽量小，因此目标函数即为：（3）约束条件手上现有资金全部用于这种股票的投资，因此有：根据题设要求，期望组合收益率应大于等于给定的预期收益率

29、（），于是有：综合上述分析，股票组合投资问题的数学模型为如下二次规划模型： 4. 模型求解（1）数据准备根据概率论的知识和表6-7中给出的数据，计算出三种股票的期望收益率和三种股票收益率的协方差矩阵如下：，即： ，。（2）求解取和，将上述数据代入股票组合投资问题的二次规划模型，利用LINGO软件进行求解，其最优解为：，即投资三种股票的资金比例大致是：占，占，占，相应的风险值为。 此外，股票组合投资问题还有：（1）存在（例如可买国库券等）无风险资产；（2）考虑交易成本等情形。这些情形下的股票组合投资问题的数学模型请读者思考。例6.6 节水洗衣机问题我国淡水资源有限，节约用水人人有责。洗衣机在家庭

30、用水中占有相当大的份额，目前洗衣机已非常普及，节约洗衣机用水十分重要。假设在放入衣物和洗涤剂后洗衣机的运行过程为：加水漂洗脱水加水漂洗脱水加水漂洗脱水（称“加水漂洗脱水”为运行一轮）。请为洗衣机设计一种程序（包括运行多少轮、每轮加多少水等），使得在满足一定洗涤效果的条件下，总用水量最少。1. 问题分析（1）洗衣的基本原理与过程洗衣的基本原理就是将吸附在衣物上的污物溶于水中，通过脱去污水而带走污物。“溶污物脱污水”是由两个基本要素构成的“元操作”，无论是如何精心设计的洗衣方式和程序都是以此为基础的。洗衣的过程就是通过加水来实现上述“溶污物脱污水”操作的反复执行，使得残留在衣物上的污物越来越少，直

31、到满意的程度。通常洗衣要加入洗涤剂，它帮助衣物上原有的污物溶解。但应注意，洗涤剂本身也是不希望留在衣物上的东西。因此“污物”应是衣物上原有污物与洗涤剂的总和。有了这种认识后，就可以统一地处理“洗涤”过程（即通常加洗涤剂的首轮洗衣）和“漂洗”过程（即通常的以后各轮洗衣，不再加洗涤剂，但水中还有剩余洗涤剂），把二者都看作“溶污物”环节。“脱污水”在洗衣机中称为“脱水”，一般是由“排水”和“甩干”两个步骤组成。（2）节水洗衣机问题要点分析 立足于“溶污物脱污水”这种基本原理，我们可以找出节水洗衣机问题的基本要点如下：1）污物的溶解情况如何？我们将用“溶解特征”来刻画；2）每轮脱去污水后，污物减少情况

32、如何？这将由系统的动态方程表示；3）如何设计由一系列“溶污物脱污水”构成的节水洗衣机程序？这将通过用水程序来反映，也是我们最终需要的结果。 2. 模型假设（1）仅考虑离散的洗衣方案，即“加水溶污物脱污水”（以下称为“加水漂洗脱水”）三个环节是分离的，这三个环节构成一个洗衣周期，称为一轮；（2）每轮用水量不能低于高度，否则洗衣机无法转动；用水量高度不能高于，否则会溢出，设；（3）每次洗漂的时间是足够的，以便衣物上的污物充分溶入水中，从而使每轮所加的水被充分利用；（4）脱水时间也是足够的，以使污水充分脱出，即让衣物所含的污水量达到一个低限，设这个低限为一个大于0的常数，设。3. 模型建立（1）决策

33、变量设共进行轮“加水漂洗脱水”的过程，依次为第0轮，第1轮，第轮。第轮用水量（单位：高度）为（），以为模型的决策变量。（2）目标函数轮总用水量，根据要求我们以为目标函数，实现其最小化。（3）溶解特性、动态方程、约束条件设衣物上的初始污物量为，在第轮脱水之后仍吸附在衣物上的污物量为。在第轮洗漂之后和脱水之前，第轮脱水之后的污物量已变成了两部分：，（）其中表示已溶入水中的污物量，表示尚未溶入水中的污物量。与第轮的加水量有关，总的规律应是，越大越大，且当时，最小（，因为此时洗衣机处于转动临界点，有可能无法转动，该轮洗衣无效）；当时，最大（ 这里假设，其中称为“溶解率”），因此简单地选择线性关系表示这

34、种溶解特性则有： （6.1）在第轮脱水之后，衣物上尚有污物。有污水，其中污水中含有污物量为，于是第轮完成之后衣物上尚存的污物总量为： （6.2）将（6.1）代入（6.2）式，并整理后得系统动态方程：，（） （6.3）由于是洗衣全过程结束后衣物上最终残存的污物量，而是初始污物量，故反映了洗涤效果，越小，洗涤效果越好，我们设定适当小的正数（ ），用来表示达到设定的洗涤效果。由系统动态方程（6.3）可得： （6.4）于是达到设定的洗涤效果可用下列约束条件表示： （6.5）同时每轮的用水量还应满足不小于，不超过。于是应有约束条件：，（） （6.6）综合上述分析，节水洗衣机问题的数学模型为如下非线性规划

35、模型： 若令：，即。则上述节水洗衣机问题的非线性规划模型变成为如下更简洁的形式： 其中：，4. 模型求解（1）最少洗衣轮数定义函数：，（）。易知： ，（）可见是区间上的单调减函数，所以在区间上的最小值为：第轮的洗涤效果为： ，（）由此不难得出轮洗完后洗净效果最多可达到： 给定洗净效果的要求，则应有：于是， （6.7）设为满足（6.7）式的最小正整数，则最少洗衣轮数即为。（2）算法可选用一种求解非线性规划模型的算法，例如精确惩罚函数法，对于， ，（凭常识洗衣的轮数不应太多，比如可取已足够）进行枚举求解，然后选出最好的结果。其中是满足（6.7）式的最小正整数。注意不必使用求解混合整数非线性规划问题

36、的算法，那将使问题复杂化。 5. 注记（1）模型中的乘积约束可化为：；（2）在实际中，无论是参数，以及洗净效果要求，还是溶解特性，均应在各种不同条件下（比如针对衣物量的多少、衣物的各种质地以衣物的脏污程度）通过试验确定。6.5 多目标规划模型6.5.1 多目标规划模型的基本知识前面介绍的线性规划模型、整数规划模型、非线性规划模型中的目标函数都只有一个。而在许多实际问题中，衡量一个方案好坏的标准往往不止一个，例如设计导弹，既要射程最远，又要燃料最省，还要精度最高。这一类问题称为多目标规划问题。对多目标规划问题建立其具有多个目标函数的数学规划模型称为多目标规划模型。具有个目标的多目标规划模型的一般

37、形式为：目标函数 由于等式约束总可以转化为不等式约束，大于等于约束总可以转化为小于等于约束，同时目标函数的最大化总可以转化为目标函数的最小化，于是多目标规划模型的一般形式又可简化为：称为多目标规划模型的可行域。多目标规划模型的一般形式又可表达为：其中表示对个目标，以追求最小为目的。设有两向量，。规定以下几个有关向量比较的符号。（1）符号“”：若，则意味着的每个分量都要小于或等于的对应的分量；（2）符号“”：若，则意味着的每个分量都要严格小于的对应的分量；（3）符号“”：若，则意味着的每个分量都要小于或等于的对应的分量，并且存在的某一个分量严格的小于的对应的分量。定义6.3 设，若对于任意，均有

38、，即对于，均有，则称为多目标规划模型的绝对最优解。定义6.4 设，若不存在，使得，则称为多目标规划模型的有效解。定义6.5 设，若不存在，使得，则称为多目标规划模型的弱有效解。在多目标规划模型的个目标中，有的相互联系，有的相互制约，有的相互冲突。多目标规划模型除了目标函数不只一个这一明显的特点外，最显著的还有以下两点：目标间的不可公度性和目标间的矛盾性。目标间的不可公度性：是指各个目标没有统一的度量标准，因而难以直接进行比较。例如房屋设计问题中，造价目标的单位是元/平方米，建造时间目标的单位是年，而结构、造型等目标则为定性指标；目标间的矛盾性：是指如果选择一种方案以改进某一目标的值，可能会使另

39、一目标的值变坏，如房屋设计中造型、抗震性能目标的提高可能会使房屋建造成本目标提高。正是由于目标间的矛盾性，解决实际问题所建立的多目标规划模型常常没有绝对最优解，只能寻找其有效解或弱有效解。6.5.2 多目标规划模型的常用解法介绍多目标规划模型的解法大致可分为两类：直接解法和间接解法。到目前为止，常用的多为间接解法，即根据问题的实际背景和特征，设法将多目标规划模型转化为单目标规划模型，从而得到多目标规划模型的满意解。 1主要目标法在多目标规划模型中，若能从个目标中，确定一个目标为主要目标，例如，而把其余目标作为次要目标，并根据实际情况，确定适当的界限值，这样就可以把次要目标作为约束来处理，而将多

40、目标规划模型转化为求解如下的单目标线性或非线性规划模型：其中界限值取为，则此单目标规划模型的最优解必为原多目标规划模型的弱有效解。因此，用主要目标法求得的解必是多目标规划模型的弱有效解或有效解。2分层序列法把多目标规划模型中的个目标按其重要程度排一个次序，假设最重要，次之 ，再次之， ，最后一个目标为。先求出以第一个目标为目标函数，而原模型中的约束条件不变的问题：其最优解为，最优值为。再求解问题：其最优解为，最优值为。再求解问题：其最优解为，最优值为， ，如此继续下去，直到求解第个问题：其最优解为，最优值为。则就是原多目标规划模型在分层序列意义下得最优解，为其最优值。常将分层序列法修改如下：选

41、取一组适当小的正数成为宽容值，把上述的问题修改如下：再按上述方法依次求解各问题， ， 。3线性加权求和法对多目标规划模型中的个目标按其重要程度给以适当的非负权系数，且，然后用作为新的目标函数，成为评价（目标）函数，再求解单目标规划问题：其最优解为，取作为多目标规划模型的解。6.5.3 多目标规划建模示例例6.7 选课策略问题某学校规定，运筹学专业的学生毕业时必须至少学习两门数学课程、三门运筹学课程和两门计算机课程。这些课程的编号、名称 、学分、所属类别和先修课程要求如表6-8所示。一般学生选课时要考虑总的课程门数和所获得的学分。试设计选课策略，在满足毕业要求的同时，使得所修课程门数尽量少，所获

42、得的学分尽量多。表6-8 课程情况课程编号课程名称学分所属类别先修课程要求1微积分5数学2线性代数4数学3最优化方法4数学；运筹学微积分；线性代数4数据结构3数学；计算机计算机编程5应用统计4数学；运筹学微积分；线性代数6计算机模拟3计算机；运筹学计算机编程7计算机编程2计算机8预测理论2运筹学应用统计9数学实验3运筹学；计算机微积分；线性代数1. 模型假设（1）各个同学在选课时不受其他因素影响，只受学分和选课门数影响；（2）各门课程没有人数限制；（3）仅考虑表6-8所列9门课程。2. 模型建立（1）决策变量定义如下0-1变量作为决策变量：（2）约束条件至少选两门数学课程、三门运筹学课程和两门

43、计算机课程，根据表6-8中对各门课程所属类别的划分，这一约束可以表示为：某些课程有先修课程的要求。例如“数据结构”的先修课是“计算机编程”，这意味着如果，必须，这个条件可以表示为（注意：时对没有限制）。“最优化方法”的先修课是“微积分”和“线性代数”这一条件可以表示为，而这两个不等式可以合并为。这样，所有课程的先修课要求可以表达为：（3）目标函数根据本问题的假设，我们考虑课程门数和学分两个目标。所选课程门数可表达为：我们希望课程门数尽量少，即希望对目标函数实现最小化。所选课程的总学分可表达为：其中为课程编号为的课程的学分，这里，。我们希望学分尽量多，即希望对目标函数实现最大化。综合上述分析，选

44、课策略问题的数学模型为如下多目标规划模型：3. 模型求解记上述多目标规划模型的可行域为。（1）如果以课程门数作为主要目标，不考虑学分的多少，由主要目标法将上述多目标规划模型转化为如下的单目标规划模型：运用LINGO软件求解得到：，即选微积分、线性代数、最优化方法、计算机模拟、计算机编程、数学实验这门课，可满足毕业要求并使课程门数最少，此时总学分为。（2）如果以课程门数作为最重要目标，总学分作为次重要目标，即在课程门数达到最少的前提下使总学分达到最多。于是利用分层序列法在上述的基础上，再次求解如下的单目标规划模型：运用LINGO软件求解得到：，即将上述（1）中学分的“计算机模拟”换成学分的“应用

45、统计”，同样这门课，可使总学分由增至。（3）如果认为课程门数和总学分这两个目标的重要程度之间的差异不十分明显，这时可由线性加权求和法取权系数和，将原多目标规划模型转化为如下的单目标规划模型：运用LINGO软件求解得到：，即选微积分、线性代数、最优化方法、数据结构、应用统计、计算机模拟、计算机编程、数学实验这门课。此时虽然课程门数增加了两门课，但总学分也增加到了。例6.8 露天矿生产的车辆安排问题许多现代化铁矿是露天开采的，它的生产主要是由电动铲车（以下简称电铲）装车、电动轮自卸卡车（以下简称卡车）运输来完成。某露天矿里有10个爆破生成的石料堆，每堆称为一个铲位，每个铲位已预先根据铁含量将石料分

46、成矿石和岩石。一般来说，平均铁含量不低于25%的为矿石，否则为岩石。每个铲位的矿石、岩石数量，以及矿石的平均铁含量（称为品位）都是已知的，见表6-9。每个铲位至多能安置一台电铲，现有电铲7台，电铲的平均装车时间为5分钟。卸货地点（以下简称卸点）有卸矿石的矿石漏、2个铁路倒装场（以下简称倒装场）和卸岩石的岩石漏、岩场5个。各卸点一个班次的产量要求：矿石漏1.2万吨、倒装场1.3万吨、倒装场1.3万吨、岩石漏1.9万吨、岩场1.3万吨。从保护国家资源的角度及矿山的经济效益考虑，应该尽量把矿石按矿石卸点需要的铁含量（假设要求都为29.5%1%，称为品位限制）搭配起来送到卸点，搭配的量在一个班次（8小

47、时）内满足品位限制即可。从长远看，卸点可以移动，但一个班次内不变。卡车的平均卸车时间为3分钟。所用卡车载重量为154吨，平均时速28。卡车的耗油量很大，每个班次每台车消耗近1吨柴油。发动机点火时需要消耗相当多的电瓶能量，故一个班次中只在开始工作时点火一次。卡车在等待时所耗费的能量也是相当可观的，原则上在安排时不应发生卡车等待的情况。电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输。每个铲位到每个卸点的道路都是专用的宽60的双向车道，不会出现堵车现象，每段道路的里程都是已知的，见表6-10。一个班次的生产计划应该包含以下内容：出动几台电铲，分别在哪些铲位上；卡车分别在哪些路线上

48、各运输多少次（只求出各条路线上的车次数即可）。一个合格的计划要在卡车不等待条件下满足产量和质量（品位）要求，而一个好的计划还应该考虑：利用现有卡车20辆运输，获得最大的产量（岩石产量优先；在产量相同的情况下，取总运量最小的解）。试就上述问题建立数学模型，并给出算法。表6-9 各铲位矿石、岩石数量(万吨)和矿石的平均铁含量铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石量0.951.051.001.051.101.251.051.301.351.25岩石量1.251.101.351.051.151.351.051.151.351.25铁含量30%28%29%32%31%33%3

49、2%31%33%31%表6-10 各铲位和各卸点之间的距离（公里）铲位1铲位2铲位3铲位4铲位5铲位6铲位7铲位8铲位9铲位10矿石漏5.265.194.214.002.952.742.461.900.641.27倒装场1.900.991.901.131.272.251.482.043.093.51岩场5.895.615.614.563.513.652.462.461.060.57岩石漏0.641.761.271.832.742.604.213.725.056.10倒装场4.423.863.723.162.252.810.781.621.270.50图6-1 铲位和卸点位置的二维示意图1. 问

50、题分析 本题可以看成是经典运输问题的一种变形和扩展，它与经典运输问题明显有以下不同：（1）这是运输矿石与岩石两种物资的问题；（2）属于产量大于销量的不平衡运输问题；（3）为了完成品位约束，矿石要搭配运输；（4）产地、销地均有单位时间的流量限制；（5）运输车辆只有一种，每次都是满载运输，每车次154吨；（6）铲位数多于电铲数，意味着要选择不多于7个产地作为最后结果中的产地。 根据题目要求的原则：获得最大的总产量（岩石产量优先；在产量相同的情况下，取总运量最小的解），主要目标应有：（1）总产量最大；（2）岩石产量最大；（3）总运量（吨公里）最小。 三个目标之间的优先关系应该理解为字典序。2. 模型

51、假设（1）电铲在一个班次中，位置不能移动；（2）卡车在一个班次中，不发生等待或熄火后再启动的情况；（3）卡车空载与重载的速度都是28；（4）运输车辆只有一种，每次都是满载运输，每车次154吨；（5）电铲和卸点都不能同时为两辆及两辆以上卡车服务；（6）不会出现堵车现象。3. 模型建立（1）决策变量设为从号铲位到号卸点路线上所需的车次数，其中：分别代表个铲位；分别代表矿石漏、倒装场、岩场、岩石漏、倒装场。只能取非负整数值。设为0-1变量，其意义为：以上述定义的和作为决策变量。令，则决策变量又可表示为向量形式：。（2）约束条件 1）道路能力约束 由于一台电铲与一个卸点都不能同时为两辆及两辆以上卡车服务，所以一条路线上最多能同时运行的卡车数是有限的。设卡车在第号铲位到号卸点路线上运行一个周期平均所需的时间为，可以由下式计算：由于装车时间分钟大于卸车时间分钟，所以可以分析出这条路线上在卡车不等待条件下最多能同时运行的卡车数，由下式计算： 同样可分析出每辆卡车一个班次中在这条路线上最多可以运行的次数，由下式计算： 其中是开始装车时最后一辆车的延时时间。设一个班次中在这条路线上最多可以运行的总车次数为，由下式大约计算： 一个