最 优 化 方 法

          最优化方法也称为运筹学方法。

一、运筹学的简史

运筹学的早期工作及其历史可追溯到1914年，当时兰彻斯特（Lanchester）提出了军事运筹学的战斗方程；1917年，丹麦工程师埃尔朗（Erlang）在哥本哈根电话公司研究电话通信系统时，提出了排对论的一些著名公式；20世纪20年代初提出了存储论的最优批量公式.1947年美国数学家丹西格（G..B.Danting）在解决美国空军军事规划问题时，提出了线性规划及单纯形法.早在1939年，前苏联学者康托洛维奇（JT.B.KaHTopobny）在解决工业生产组织和计划问题时，已提出了类似线性规划模型，并给出了“解乘数法”的求解法.可惜当时未被重视.

运筹学作为一门科学诞生于20世纪30年代末期，通常认为运筹学的活动是第二次世界大战早期从军事部门开始的.当时，英国为了研究“如何最好的运用空军及新发明的雷达保卫国家”，成立了一个由各方面的专家组成的交叉学科小组，即最早的运筹小组.进行“作战研究”（Operational,research），后来中文译名为“运筹学”.（我国在1956年曾用过运用学的名词，到1957年正式定名为运筹学）.

第二次世界大战期间，英、美军队中的运筹学小组研究诸如护航舰队保护商对的编队问题；当船队遭受德国潜艇的攻击时，如何使船队损失最小的问题，反潜深水炸弹的合理起爆深度问题；稀有资源在军队中的分配问题等.第二次世界大战后，特别是运筹学在军事上的显著成功，引起了人们的广泛的关注，运筹学很快深入到工业、商业、政府部门等，并得到了迅速发展.

在20世纪50年代中期，钱学森、许国志等教授全面介绍运筹学，并结合我国特点在国内推广应用.1957年，我国在建筑业和纺织业中首先应用运筹学；从1958年开始在交通运输、工业、农业、水利建设、邮电等方面陆续得到推广应用.在解决邮递员合理投递线路时，管梅谷教授提出了国外称之为“中国邮路问题”的解法；从20世纪60年代起，运筹学在钢铁和石油部门开始得到了比较全面、深入的应用.从1965年起，统筹法在建筑业、大型设备维修计划等方面的应用取得了可喜的进展；1970年在全国大部分省、市和部门推广优选法；70年代中期，最优化方法在工程设计界受到了广泛的重视，并在许多方面取得成果；排队论开始应用于矿山、港口、电信及计算机等方面；图论用于线路布置、计算机设计、化学物品的存放等；70年代后期,存储论在应用汽车工业等方面获得成功.在此期间，以华罗庚教授为首的一大批数学家加入到运筹学的研究队伍，使运筹学的很多分支很快跟上当时的国际水平.

运筹学是一门应用科学，至今还没有统一且确切的定义.

参见：

程理民《运筹学模型与方法教程》

钱颂迪主编《运筹学》，清华大学出版

二、引例

例1  某工厂生产甲、乙两种产品，生产每件产品需要原材料、能源消耗、劳动力及所获利如下表所示：

现有库存原材料1400千克；能源消耗总额不超过2400百元；全厂劳动满员为2000人，试安排生产任务（生产甲、乙产品各多少件），使获得利润最大，并求出最大利润.

[模型建立]设安排生产甲产品x件，乙产品y件，相应的利润为S ,则此问题的数学模型为：

maxS=5x+6y

s.t.   2x+3y≦1400

                                     x+6y≦2400              (1)

                                     4x+2y≦2000  

                               x0,y0,x,y∈Z

这是一个整数线性规划问题.

例2  某工厂有100台机器，拟分四期使用，在每一期中有生产任务，两种.设第k个周期初有完好的机器台，根据经验，若周期初把、-台机器分别投入任务、，则周期末分别有/3、台机器作废（k=1，2，3，4）.如果在一个生产周期中每一台机器执行任务可收益10千元，执行任务可收益7千元，问怎样分配机器使收益最大？试建立数学模型.

[数学模型的建立] 按题设，，（k=1、2、3、4）受约束于(subject to 简记为 s.t.）

=+(-),0≤≤ 且=100

第K个周期收益10+7（-），因此四个周期的总收益为

V=（10+7（-）），于是问题的数学模型为：

Max V=（10+7(-））

s.t. =+(-)    (2)

          0≤≤ ，且=100 ， k=1,2,3,4

这是一个分步决策，且为线性规划问题.

例3 某投资者有5亿元，想取其中的一部分对项目，进行投资，设投资亿元项目 ,从历史资料来分析，投资于项目和分别有预期的年收益20%和16%.同时，与项目和有关的总的风险损失为 (记为Q) .试设计使预期的总收益R最大而风险损失Q尽可能的小的投资方案.

[数学模型]

此问题的数学模型为：

Max R=0.2+0.16

Min Q=              (3)

s.t ≦5, ≧0

注意到：Min Q=Max(-Q),若投资者根据总收益与风险损失对自己的重要程度确定权系数，希望f=0.8R+0.2(-Q)最大，则数学模型为

Max f=0.8(0.2 +0.16)-0.2[]

s.t ≦5, ≧0                 (4)

三、数学规划的基本概念及解法

1、概念

① 在上面的数学模型（1）--（4）中，都是求函数的极值问题，象这样的在等式或不等式约束条件下求一元或多元函数的极值问题，称为数学规划问题.这个需要求极值的函数称为目标函数.数学规划问题中的自变量称为决策变量.

② 在数学规划中，目标函数和约束条件中的函数式都是线性的，就称它为线性规划问题.否则就称非线性规划问题（至少有一个非线性的）.

如（1）（2）是线性规划；（4）是非线性规划.

③ 早在1939年前苏联数学家康托洛维奇（JT.B.KaHTopobny）和美国的希奇柯克（F.L.Hitchcock）等人就在生产组织管理和制定交通运输方案方面首先研究和运用了线性规划方法.1947年，美国数学家丹西格（G.B.Dantzig）提出了单纯形法，给出了求解线性规划的实用方法.

④ 对于例3，数学规划（3）：在此数学规划问题中目标函数有多个，就称它为多目标规划问题.例如，全国大学生数学建模竞赛题96年A题、98年A题、98年B题、03年B题等都是多目标规划问题.

⑤ 另外，目标函数，约束条件中出现“最多约能”、“约不能超过”.这种模糊概念，若至少出现一个，则就称相应的规划为模糊（数学）规划问题.

⑥  又如在(4)中，数学规划问题中，目标函数为二次函数，且约束条件中的函数式子是线性的，则称它为二次规划.

⑦线性规划的一般形式为

s.t.                           (5)

            其中均为已知常数.

矩阵表示:

⑧标准形式(矩阵)为

          (松弛度量,剩余度量)

⑨线性规划问题中满足约束条件的解称为可行解,其全体称为可行域,使目标函数达到最小值(最大值)的可行解称为最优解,最优解对应的目标函数值称为最优值.

最优解为,最优值为.

2.重要结论

① 若线性规划问题⑸存在可行域,则可行域为凸集.

② 若线性规划问题可行域有界，则最优解在可行域的顶点达到.

3．数学规划的解法：

①． 解线性规划的单纯形法（解法一）.

②． 解法二  lindo 数学软件（1998年）.

Lindo

安装  A：>install

C:  > . ；(表示进入状态)

例如 求 

s.t.   

；

?  S T (或S.T 或Subject to)

? 

? 

?  END

: 运行 Go

③． 图解法（线性规划）

求例1的数学模型.

可行域为：由直线　　 直线

易知：当过的交点时，S取最大值.

由     解得

此时 (千元)

四.关于多目标规划

   　1．具有两个以上目标函数的数学规划,称为多目标规划,前面的例3就是一例,下面我们再举一例说明:

例4.某厂生产甲和乙两种产品,其中甲为紧俏商品.生产每斤甲的利润为4元，生产每斤乙的利润为3元.每斤甲的生产时间为每斤乙的两倍，如果全部时间用来生产乙，则每日可生产乙500斤，由于受原料的限制，该厂每日生产甲和乙的总数不超过400斤，问如何安排甲和乙的日产量，使该厂获得的利润最大且使甲的日产量最大？

[模型的建立]

设产品的日产量为，产品乙的日产量为，问题归结为如下数学模型

  或

   或

s.t.  

这是一个二目标规划问题.

许多实际问题都涉及到：①利润最大，能源消耗最少；②经济效益最大，又尽量满足市场需求；③长、宽、高尽可能性小；④总利润最大，而某个项目的日产量最大.

2．设个目标函数为 

s.t

称为约束集合，象集为F(R)=

3.记号

设

这些关系组成的序集是偏序集.

4.解

① 绝对最优解

② 有效解（非劣解）：中不存在使

③ 弱有效解（弱非劣解）：中不存在使

④ 结论：绝对最优解有效解弱有效解（但反之都不然）.

5.处理多目标规划的一些方法

 方法：将多目标规划（VP）转化为单目标规划问题来处理，以便求出（VP）的有效解或弱有效解.

（一）约束法

在p个目标函数中确定一个主要的，例如，则（VP）化为如下单目标规划：

定理1.若是（1）的最优解，则是(VP)的弱有效解.

（二）分层序列法

， 最后的最优解就是(VP)的弱有效解.

（三）功效系数法

定理2，若问题的最优值，则就是（VP）的有效解.

（四）评价函数法

构造评价函数，然后求相应的单目标问题的最优解，再证明它是多目标规划问题的有效解或弱有效解.

1） 乘除法

设在R中有,(j=1,2,…,p)，要求越小越好，越大越好.

此时考虑多目标规划问题.

求的最优解，则此最优解是上述问题的有效解.

2） 理想点法

3） 平均和加权法

若是的最优解，则的有效解.

4） 线性加权法

考虑(VP),按的重要程序确定一组权系数

作评价函数，

求出的最优解，

于是是（vP）的弱有效解，若,(j=1,2…,p),则是(vp)的有效解.

5） 极小——极大法

作评价函数，