数学建模优化理论与方法.ppt

1、数学规划的理论与方法,1. 线性规划理论与方法 2. 目标规划的理论与方法 3. 整数规划的理论与方法 非线性规划的理论与方法 5. 动态规划 6. 最优控制理论,y,一.线性规划的理论与方法,线性规划是指目标函数是由线性函数给出，约束条件由线性等式或者不等式给出的优化问题。,最早提出线性规划问题并进行专门研究的学者康托洛维奇。 康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。,自从1947年美国学者丹青格提出求解线性规划问题的一般方法单纯形方法 后，才使线性规划的理论和方法日臻成熟。,（1）由决策变量构成，反映决策的目标是线性函数。 （2）一组由决策变量的线性等式或不等式

2、构成约束 条件。 （3）对决策变量取值范围加以限制的非负约束。,1.1 线性规划模型的特征,例1：某工厂生产甲、乙两种产品，每件产品的利润、 所消耗的材料、工时及每天的材料限额和工时限额， 如表1.1所示。试问如何安排生产，使每天所得的利润为最大？,表1.1,设每天生产甲、乙两种产品分别为 x1 , x2 则该问题可描述为由如下数学模型：,1.2 线性规划问题的标准型,如下形式的线性规划模型被称作标准型:,也可用矩阵形式描述:,A:资源消耗系数矩阵 b: 资源限量向量 C:价格向量 X:决策变量向量,同时我们对标准型作如下假定:,一般的线性规划问题通过变换可化成标准型 , 变 换方式可以归结为

3、:,1.3 线性规划问题解的概念,对于线性规划问题,1.4 线性规划问题的图解法,下面结合例1的求解来说明图解法步骤。,例1,第一步：在直角坐标系中分 别作出各种约束条件，求出 可行域（图中阴影部分）。,第二步：作出一条目标函数等值线，并确定 Z 值增大的方向。,第三步：沿 Z 值增大方向移动，当移至 Q2(6,4) 点时，Z 值为最大，Z*=36 .,1.5 基本定理,从理论上来讲,采用“枚举法”找出所有基可行解,并,1.6 求解线性规划问题的单纯形方法,一一比较,一定会找到最优解。但当 m, n 较大时,这种方法是不经济和不可取的。 下面介绍求解线性规划问题的有效方法单纯形方法。单纯形法的

4、实质是从一个基可行解向另一个基可行解（极点到极点）的迭代方法。,以下通过例1的求解过程说明单纯形方法的基本步骤。,例1：,第一步：引进松驰变量 x3 , x4 将原问题化为标准型。,标准型,第二步：找出初始可行基，建立初始单纯形表。 见下表1.2。,表 1.2,第三步：最优性检验。,第四步：换基迭代。,表1.3,同理，确定 x2 换入，x3 换出，继续迭代得表 1.3,表 1.3,表中最后一行的所有检验数都已是正数或零，从而得到基本最优解 X*=(6,4,0,0)T, Z*=36 。由于 x3 , x4 是引进的松弛变量，因此原问题的最优解为 x1=6, x2=4, 最优值 Z*=36 。,例

5、2 一奶制品加工厂用牛奶生产 A1 , A2 两种奶制品，1 桶牛 奶可以在设备甲上用 12 小时加工成 3 公斤 A1,或者在设备 乙上用 8 小时加工成 4 公斤 A2。根据市场需求，生产的 A1 , A2 全部能售出，且每公斤 A1 获利 24 元，每公斤 A2 获利 16 元。现在加工厂每天能得到 50 桶牛奶的供应，每天正式工人 总的劳动时间为 480 小时，并且设备甲每天至多能加工 100 公斤 A1 , 设备乙的加工能力没有限制。试为该厂制定一个,我们无意过深涉及线性规划的具体计算方法，而着重介绍的是如何建立若干实际的线性规划模型，如何使用现成的数学软件进行求解，以及如何对结果进

6、行深入的分析。 下面以奶制品加工生产计划为例，进行详细的讨论。,生产计划，使每天获利最大，并进一步讨论以下 3 个附加问题： 若用 35 元可买到 1 桶牛奶，买吗？若买，每天最多 买多少? 若可以聘用临时工人以增加劳动时间，付给临时工人 的工资最多是每小时几元? 由于市场需求的变化，A1 的获利增加到 30元/公斤， 应否改变生产计划？,分析,解法1：图解法。,约束条件,从图中可以看出，在 B(20,30) 点得到最优解。,解法2：软件实现。求解线性规划有不少现成的数学软件，比如用 LINDO 软件就可以很方便地实现。在 LINDO6.1版本下打开一个新文件，像书写模型一样。直接输入：,ma

7、x 72x1+64x2 st 2）x1+x250 3）12x1+8x2480 4）3x1100 end,注：LINDO中已规定所有决策变量均为非负，故变量非负的条件不必输入。输入文件中第1行为目标函数，2),3),4)是为了标示各约束条件，便于从输出结果中查找相应信息；程序最后以end 结束。,将文件存储并命名后，选择菜单 “Solve” 并对提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即可得到如下输出：,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000

8、000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,20桶牛奶生产A1, 30桶生产A2，利润3360元。,原料无剩余,时间无剩余,加工能力剩余40,三种资源,结果解释,OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2

9、30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,最优解下“资源”增加1单位时“效益”的增量,原料增加1单位, 利润增长48,时间增加1单位, 利润增长2,加工能力增长不影响利润,影子价格,35元可买到1桶牛奶，要买吗？,35 48, 应该买！,聘用临时工人付出的工资最多每小时几元？,2元！,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ

10、 COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INF

11、INITY 40.000000,最优解不变时目标函数系数允许变化范围,DO RANGE(SENSITIVITY) ANALYSIS?,Yes,x1系数范围(64,96),x2系数范围(48,72),A1获利增加到 30元/千克，应否改变生产计划,x1系数由24 3=72增加为303=90，在允许范围内,不变！,(约束条件不变),1.7 线性规划问题经典例题,典例1（运输问题）:设某种物资有 m 个产地 A1 , A2 , , Am ,产量分别为 a1 , a2 , , am , 有 n 个销地 B1 , B2 , , B n , 销量分别为 b1 , b2 , , bn 假设产销是平衡的， 即

12、有： 设 cij（ i=1,2, ,m ; j=1,2, ,n ) 为由产地 Ai 运往销地 Bj 的单位运费。这些数据汇总于表 1.4 中，试求总运费最少的运输方案。,表.4,假设 f 为总运费，xij 为从 Ai 运往 Bj 的物资的数量，则这个问题的数学模型是：,前面讨论的是产销平衡的问题，而实际问题中产销往往是不平衡的。对于这样的运输问题，解决的办法是把它转化为平衡的问题来处理。,当产大于销时，即：,此时，运输问题的数学模型可表示为：,由于总产量大于总销量，可虚拟 Bn+1 为存储地，并设 xi , n+1 是产地 Ai 的存储量，于是有：,同样，当总销量大于总产量时，只要增加一个虚拟

13、的产地Am+1 , 它的产量 am+1 为,可令，从假想产地 Am+1 到销地 Bj 的单位运费 cm+1,j=0 (j=1,2, ,n),同样可以将这类问题转化为产销平衡的问题。,典例2（下料问题）:某工厂有一批长度为 300cm 的钢管（数量充分多），要把它们截成长度为 45cm 、80cm 、95cm 的管料，并要求其根数比例为 5:3:2 ，来配套生产某种零件。问采用怎样的方案进行锯割，才能使得到的三种管料既能配套，又能使残料最少？,解：,首先，我们用表 1.5 列出各种可能的截法。,表1.5,解：设 xj (j=1,2, ,10) 表示按照第 j 种截法锯割的钢管 的根数，那么截出的

14、长 45cm 管料的根数为：,截出的长 95cm 管料的根数为：,截出的长 80cm 管料的根数为：,此时，残料的长度为：,因此，下料问题的数学模型为：,典例3（投资问题）:一投资公司将 1000 万元的资金对A 、B两个企业投资，对企业A每投资 1 万元，一年后公司可获利0.7 万元；对企业B每投资 1 万元，两年后公司可获利 2 万元。对企业 A 每次投资周期必须是一年，对企业 B 每次投资周期必须是两年，到期结算后，以本利的和再作为资金继续对A 、B两个企业投资。问公司要在第三年底收到最大效益，应该如何分配对 A 、B 两个企业的投资数量？,解：,设投资公司对A 、B两企业在第一年初的投

15、资额分别为 x11 、x21 万元；在第二年初的投资额分别为x12 、x22 万元；在第三年初的投资额分别为x13、x23 万元。,在第一年初，投资公司投出总金额为1000万元，所以有： x11+x21=1000 （1）,在第一年底，回收到对 A 企业投资的本金+利润合计为： x11+0.7x11=1.7x11 此资金作为第二年初对 A 、B 两企业 投资资金。,在第二年初，投资公司对 A 、B 两企业投资金额为 1.7x11 万元，所以有： x12+x22= 1.7x11 （2）,在第二年底，回收的金额是两部分的和一部分是第二年 初对 A 企业投资的本利和为： x12+0.7x12= 1.7

16、x12 万元,另外一部分是第一年初对 B 企业投资的本利 x21+2x21= 3x21万元。所以，第二年底投资公司共回收 1.7x12+3x21 万元，作为第三年初的投资资金。 在第三年初，只能对 A 企业进行投资，因此有： x13 =1.7x12+ 3x21 （3） x23 =0 （4）,在第三年底，投资公司从两个企业回收的本利分别为：从 A 企业回收的第三年初投入的本利 x13+0.7x13=1.7x13 万元； 与从B企业回收的第二年初投入的本利x22+2x22=3x22 万元。 因此，投资公司的总收入为： S= 1.7x13 + 3x22 综合上面讨论，我们得到此投资问题的数学模型为：

17、,以上我们建立了生产问题、运输问题、下料问题及投姿问题的数学模型。在实际问题中还有好多诸如布局问题、分派问题等，这些问题虽然各式各样但都可以归结为线性规划问题，线性规划模型可以解决实际优化中的大量问题。线性规划由于它的理论的完备性及方法的有效性越来越受到广泛的应用。,二.目标规划的理论与方法,前面介绍的线性规划问题，都是在约束条件下具有单个目标函数的基本特征。但现实世界中有很多问题却具有多个目标，这些目标的重要性各不相同，往往有不同的量纲，又相互冲突。决策者希望实现的这些目标，有的要求百分之百地予以实现，有的则要求基本实现就可以。诸如此类问题正是目标规划要研究解决的问题。目标规划通常包括线性目

18、标规划、非线性目标规划等。我们仅讨论线性目标规划（简称目标规划）的数学模型及方法。,以前面我们很熟悉的例1（生产计划问题）为例，它是一个单目标的线性规划问题,设每天生产甲、乙,两种产品分别为 x1 件和 x2 件，其数学模型如下：,其最优解为 x1*=6 ,x2*=4 ,z*=36 即最优方案为甲产品生产6件，乙产品生产4件，每天的总利润为36元。,现在工厂领导要求考虑市场等一系列其他因素，提出如下目标：,（1）根据市场信息，甲产品的销量有下降趋势，而乙产品的销量有上升趋势，故考虑乙产品的产量应大于甲产品的产量； （2）尽可能充分利用工时，不加班； （3）应尽可能达到并超过计划利润30元。 问

19、题： 在原材料不能超计划使用的前提下，并考虑上述（1）（2）（3）三个目标后，如何安排生产使这些目标依次实现？,设每天生产甲、乙两种产品分别为 x1 件和 x2 件，由于原材料的限制，显然有如下资源约束：2x1+3x224,2.1 目标规划数学模型的基本特征,正或负的偏差量，因此目标约束是软约束，具有一定的弹性。,建立目标规划的数学模型时，排定各个目标的优先等级，一般是通过专家来评定的。,2.2 目标规划的图解法,2.3 目标规划的单纯形解法,目标规划的数学模型结构和线性规划的模型结构类似，所以可用单纯形法求解。 用单纯形法求解目标规划问题的计算步骤如下(算法2.1)：,建立初始单纯形表，在表

20、中将检验数行按优先因子个数分 别列成 K 行（检验数矩阵），置 k=1 ; (2) 检查该行中是否存在正数，且对应的前 k-1 行的系数是零。 若有取其中最左边正系数对应的变量为换入变量 (3) 按最小比值规则确定换出变量，当存在两个以上相同的最 小比值时，选取具有较高优先级别的变量为换出变量。 (4) 按单纯形法进行基变换运算，建立新的计算表，返回(2)。 (5) 当 k=K 时，计算结束。表中的解即为满意解。否则置,k=k+1 , 返回到 (2) 。,下面用单纯形法求解以上例题，其求解过程如下： 首先将原问题化成标准形：,表2.1,表 2.1 中的检验数矩阵是这样得到的：,按算法2.1的步

21、骤对初始单纯形表2.1进行迭代，依次得下列各表。,表2.2,表2.3,表2.4,线性规划作为一种决策工具可以处理许多线性系统的最优化问题。但是，在解决实际问题时，线性规划存在着由其“刚性”本质所决定的某些固有的局限性。现代决策强调定量分析和定性分析相结合，强调硬技术和软技术相结合，强调矛盾和冲突的合理性，强调妥协和让步的必要性，线性规划无法胜任这些要求。目标规划在处理实际决策问题时，承认各项决策要求（即使是冲突的）的存在有其合理性；在作最终决策时，不强调其绝对意义上的最优性。由于目标规划一定程度上弥补了线性规划的局限性，因此被认为是一种较之线性规划更接近于实际决策过程的决策工具并得到广泛的重视

22、和应用。,三.整数规划的理论与方法,3.1 整数规划数学模型及其解的特点,要求一部分或全部决策变量必须取整数值的规划问题称为整数规划。不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。若松弛问题是一个线性规划，则称该整数规划为整数线性规划。整数线性规划模型的一般形式为：,整数线性规划问题可以分为下列几种类型： 1. 纯整数线性规划：指全部决策变量都必须取整数值的整 数线性规划（全整数规划）。 2. 混合整数线性规划：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。 3. 0-1型整数线性规划：指决策变量只能取值 0 或 1 的整数线

23、性规划。,整数规划的例子：,例1：某服务部门各时段（每2h为一时段）需要服务员人数见表3.1。按规定，服务员连续工作8h（即四个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。,解：设在第 j 时段开始上班的服务员人数为 xj 。由于第 j 时 段开始上班的服务员将在第（j+3）时段结束时下班，故 决策变量只需考虑 x1，x2，x3，x4，x5 。 问题的数学模型为:,表3.1,这是一个纯整数规划问题。,例2：现有资金总额为 B 。可供选择的投资项目有 n 个，项目j 所需投资额和预期收益分别为 aj 和 cj (j=1，2，n) 。此外，由于种种原因，有三个附加条件：第一

24、，若选择项目 1 ，就必须同时选择项目 2 。反之，则不一定；第二，项目 3 和项目 4 中至少选择一个；第三，项目 5，6 和 7 中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大？,解：每个投资项目都有被选择和不被选择两种可能，为此令,这样，问题可表示为:,这是一个01规划问题。其中，中间三个约束条件分别对应三个附加条件。,例3：工厂A1和A2生产某物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1，B2，B3，B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij（i,j=1,2,3,4）见表3.2。,表

25、3.2,工厂 A3 或 A4 开工后，每年的生产费用估计分别为1 200万元或1 500万元。现要决定应该建设工厂 A3 还是 A4 ，才能使今后每年的总费用（即全部物资运费和新工厂生产费用之和）最少。,解：这是一个物资运输问题，其特点是事先不能确定应该建 A3 和 A4 中的哪个，因而不知道新厂投产后的实际生产 费用。为此，引入01变量,再设 xij 为由 Ai 运往 Bj 的物资数量 (i,j=1,2,3,4)，单位是 千吨；z 表示总费用，单位是万元。,问题的数学模型为,显然，这是一个混合整数规划问题。,整数规划问题解的特点：,整数规划及其松弛问题，从解的特点上来说，二者之间既有密切的联

26、系，又有本质的区别。整数规划问题的可行解一定也是它的松弛问题的可行解（反之则不一定），所以，前者最优解的目标函数值不会优于后者最优解的目标函数值。 在一般情况下，松弛问题的最优解不会刚好满足变量的整数约束条件，因而不是整数规划的可行解，自然就不是整数规划的最优解。,图3.1中四边形OBPC及其内部为松弛问题的可行域，其中那些整数格点为整数规划问题的可行解。根据目标函数等值线的优化方向，从直观可知，P(x1=18/7,x2=19/7)点是松弛问题的最优解，其目标函数值z=94/7。在P点附近对x1和x2简单取整，可得四点:A1,A2 ,A3,和A4 。其中， A1和A2为非可行解； A3 和A4

27、虽为整数可行解，但不是最优解。,图3.1,本例整数规划的最优解为A*(x1=4,x2=2), 其目标函数值 z=12 。 由本例题可以看出，先求对应松弛问题的最优解，再用简单求 整的方法并不是求解整数规划的有效方法。,3.2 求解整数规划问题分支定界法,混合整数规划问题一般有无限多个可行解。即使是纯整数规划问题，随着问题规模的扩大，其可行解的数目也将急剧增加。因此，通过枚举全部可行解，并从中筛选出最优解的算法无实际应用价值。实际计算中往往是设法枚举（验算）其中一部分可行解，从而能够快速找到最优解。 分支定界法就是这种思路的一种，这一算法是20世纪60年代初由Land Doig等人提出的，由于它

28、既适用于纯整数线性规划，又适用于混合整数线性规划的求解，且方便于计算机上编程，所以一直作为求解整数线性规划的重要方法。,分支定界法的基本思想是：先不考虑原整数规划问题中的整数性约束，去解其相应的松弛问题。对于最大化问题，松弛问题的最优解就是原问题最优解的上界 。如果松弛问题的最优解满足整数性约束，则它就是原问题的最优解。否则，就在不满足整数性约束的变量中，任选一个xi（设它的值为 ），将新的约束条件 和 分别加入原问题中，把原问题分枝为两个子问题，并 分别求解子问题的松弛问题。若子问题的松弛问题的最优解满足整数性约束，则不再分枝，其相应的目标函数值就是原问题的目标函数值的一个下界 。对不满足整

29、数性约束的子问题，如果需要的话，继续按上述方法进行新的分枝，并分别求解其相应的松弛问题。过程中利用逐步减小 或增大 的技巧，直至所有的子问题不再分枝，从而求得原问题的最优解止。下面举例说明：,问题（2）,问题（3）,问题（4）,问题（6）,问题（5）,图示：,解原问题的松弛问题,可行解满足整数性约束？,将问题分为两个子问题,子问题的松弛问题有可行解？,各子问题都解决了？,解满足整数性约束？,停,选择尚未解决的子问题,3.3 01型整数规划,这是典型的 0-1 规划问题。,下面介绍一种求解背包问题的贪婪算法（greedy algorithm）,下面我们通过求解实例介绍另一种一种求解 0-1 型整

30、数规划的隐枚举法：,表3.3,所以，最优解 (x1,x2,x3)T= (1,0,1)T, maxz=8,3.4 指派问题（特殊的0-1整数规划）,指派问题的标准形式是：有 n 个人和 n 件事，已知第 i人做第 j 事的费用为 cij ( i, j=1,2,n ),要求确定人和事之间的一一对应的指派方案，使完成这 n 件事的总费用最少。,一般称矩阵 C=(cij)nn 为指派问题的系数矩阵，C 中第 i 行中各元素表示第 i 人做各事的费用，第 j 列各元素表示第 j 事由各人做的费用。 为了建立标准指派问题的数学模型，引入 n2 个 0-1 变量：,对于问题的每一个可行解，可用解矩阵 X=(

31、xij)nn 来表示，矩阵中每行和每列都有且只有一个 1 。指派问题共有 n!个可行解。,表3.4,例9 某商业公司计划开办五家新商店。为了尽早建成营业，商业公司决定由 5 家建筑公司分别承建。已知建筑公司Ai(i=1,2,5)对新商店Bj(j=1,2,5)的建造费用的报价（万元）为cij,见表5-9。商业公司应当对5家建筑公司怎样分配建造任务，才能使总的建造费用最少？,cij,Ai,Bj,标准的指派问题是一类特殊的整数规划问题，又是特殊的 0-1 规划问题，因此，它可以用多种相应的解法来求解。但是，这些解法都没有充分利用指派问题的特殊性质，有效地减少计算量。1955年，库恩（W.W.Kuhn

32、）利用匈牙利数学家康尼格(D.Konig)的关于距阵中独立零元素的定理，提出了解指派问题的一种方法，习惯上称之为匈牙利解法。,对于标准的指派问题，匈牙利解法的一般步骤可以表述如下： 步骤1：变换系数矩阵。先对各行元素分别减去本行中的最 小元素，再对各列元素分别减去本列中最小元素。 步骤2：在变换后的系数矩阵中确定独立零元素。若独立零 元素有 n 个，则已得出最优解；若独立零元素少于n,个，则作能覆盖所有零元素的最少直线数目的直线集合， 然后转步骤 2 。 为了确定独立零元素，可以在只有一个零元素的行（或 列）中加圈（标记为），因为这表示此人只能做该事（或 此事只能由该人来做）。每圈一个“0”，

33、同时把位于同列（或 同行）的其他零元素划去（标记为），这表示此事已不能 再由其他人来做（或此人已不能做其他事）。如此反复进行， 直至系数矩阵中所有零元素都被圈去或划去为止。在此过程 中，如遇到在所有的行和列中，零元素都不止一个，可任选 其中一个零元素加圈，同时划去同行和同列中其他零元素。 当过程结束时，被画圈的零元素即是独立零元素。,如独立零元素有 n 个，则表示已可确定最优指派方案。此时， 令解矩阵中和独立零元素对应位置上的元素为 1 ，其他元素为 0 ，即得最优解矩阵。但如独立零元素少于 n 个，则表示还不 能确定最优指派方案。此时，需要确定能覆盖所有零元素的最 少直线数目的直线集合。可按

34、下面的方法来进行： （1）没有 的行打 “” ； （2）在已打 “” 的行中，对 所在列打“”； （3）在已打“”的列中，对 所在行打“”； （4）重复（2）和（3），直到再也不能找到可以打“”的行或列为止； （5）对没有打“”的行画一横线，对打“”的列画一垂线,这,样就得到了覆盖所有零元素的最少直线数目的直线集合。 步骤3：继续变换系数矩阵。方法是在未被直线覆盖的元素中 找出一个最小元素。对未被直线覆盖的元素所在行（或列） 中各元素都减去这一最小元素。这样，在已被直线覆盖的元 素中势必会出现负元素，为了消除负元素，只要对它们所在 列（或行）中各元素都加上这一最小元素即可。返回步骤2。,下面根

35、据匈牙利解法的上述三个步骤来解例 8 。已知 例 8 指派问题的系数矩阵为：, 3 11 8 1 7 7 3 C= 2 3 2 1 5 4 2 3 4 ,由于只有 4 个独立零元素，少于系数矩阵阶数 n=5 ，故需要确定能覆盖所有零元素的最小直线数目的直线集合。采用步骤 2 中的方法，结果如下：,:, 3 11 8 1 7 7 3 C= 2 3 2 1 5 4 2 3 4 ,:,:,:,:,:,将第二行和第三行中各元素都减去未被直线覆盖的元素中的最小元素1。为了消除第一列中出现的负元素，再对第一列各元素分别加上1，即：,回到步骤2，对 C 加圈：,1 3 11 8 6 6 2 C= 1 2 1

36、 1 5 4 1 2 3 4 ,C “ 中已有 5 个独立零元素，故可确定指派问题的最优指派方案。其最优解为：,也就是说，让 A1 承建 B3 , A2 承建 B2 , A3 承建 B1 ，A4 承建 B4 , A5 承建 B5 。这样安排能使总的建造费用最少，为 7+9+6+6+6=34 (万元）,非标准形式的指派问题： 在实际应用中，常会遇到各种非标准形式的指派问题，通常的处理方法是先将它们转化为标准形式，然后再用匈牙利法解之。,1.最大化指派问题。 设最大化指派问题系数矩阵 C=(cij) nn , 其中最大元素为 m . 令矩阵 B=(bij) nn =(m-cij) nn , 则以

37、B 为系数矩阵的最小化指派问题和以 C 为系数矩阵的原最大化指派问题有相同最优解。 2.人数和事数不等的指派问题。 若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取 0 ，理解为这些费用实际上不会发生。,若人多事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费用系数同样也取 0 。 3.一个人可做几件事的指派问题。 若某人可做几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。 4.某事一定不能由某人做的指派问题。 若某事一定不能由某人做，则可将相应的费用系数取作足够大的数 M 即可。,四.非线性规划的理论与方法,由前几

38、节知道，线性规划的目标函数和约束条件都是其自变量的线性函数，如果目标函数或约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。许多实际问题需用非线性规划的模型来表达，并借助非线性规划的解法来求解。,4.1 非线性规划的数学模型,非线性规划数学模型的一般形势是：,有时也将非线性规划数学模型写成,即约束条件中不出现等式，如果有某一约束条件为等式 , 则可用如下两个不等式约束来替代它：,模型(4.2)的另一种形式是：,4.2 多元函数极值点存在的条件,回顾： 对二阶可微的一元函数 f (x) 极值点存在的条件如下： 必要条件： 充分条件：对于极小点： 对于极大点： 与一元函数类似，

39、对无约束多元函数，其极值点存在的 必要条件和充分条件如下： 定理4.1 （必要条件）设 R 是 n 维欧氏空间 En 上的某一开集， f(X) 在 R 上有连续一阶偏导数，且在点 取得局部极值， 则必有,定理4.2 （充分条件）设 R 是 n 维欧氏空间 En 上的某一开集， f(X) 在 R 上有连续二阶偏导数，若 ，且 正定， 则 为 f(X) 的严格局部极小点。此处,为 f(X) 在点 X* 处的海赛(Hesse)矩阵。 若将 正定改为负定，定理4.2就变成了X* 为 f(X) 的严格局部极大点的充分条件。,4.3 凸函数和凹函数,定义4.1 设 f(X) 为定义在 n 维欧氏空间 En

40、 中某个凸集 R c 上的 函数，若对任何实数 以及 R c中的任意两点 X(1) 和 X(2) ，恒有 则称 f(X) 为定义在 R c上的凸函数。 若对每一个 和任意两点 ，,恒有 则称 f(X) 为定义在 R c 上的严格凸函数。 若式 (4.7) 和 (4.8) 中的不等号反向，即可得到凹函数和严 格凹函数的定义。,凸函数的判定： （1）一阶条件：设 R c为 En 上的开凸集，f(X) 在 R c上可微，则 f(X) 为 R c上的凸函数的充要条件是：对任意两点 X(1) 和 X(2) ， 恒有 若式 (4.9) 为严格不等式，它就是严格凸函数的充要条件。,如将上式中的不等号反向，就

41、可得到凹函数（严格不等号时为 严格凹函数）的充要条件。,（2）二阶条件：设 R c为 En 上的开凸集，f(X) 在 R c上二阶可微， 则 f(X) 为 R c上的凸函数（凹函数）的充要条件是：对所有 ， 其海赛矩阵半正定（半负定）。,若 f(X) 的海赛阵对所有 ，都是正定（负定）的，则 f(X) 是 R c 上的严格凸函数（严格凹函数）。,函数的局部极小值只反映了函数的局部性质，并不一定等 于它的最小值。而最优化的目的，往往是要求函数在整个域中 的最小值。为此，必须求出所有的极小值并加以比较，从中选 出最小者。然而，对于定义在凸集上的凸函数来说，则用不着,进行这种麻烦的工作，它的任一极小

42、值就等于其最小值。如果 f(X) 是定义在凸集上的可微凸函数，则 不仅是极值 点存在的必要条件，同时也是充分条件。,4.4 下降迭代算法,对于可微函数来说，为了求最优解，可令其梯度等于零， 由此求得稳定点。然后再用充分条件进行判别，以求出最优解。 表面看来，问题似乎已经解决。但是，对一般 n 元函数 f(X) 来 说，由条件 得到的常常是一个非线性方程组，求解 它相当困难。此外，有时根本求不出目标函数对各自变量的偏 导数，从而使一阶必要条件难以应用。因此，除极个别的情形,之外，一般并非从一阶必要条件出发，而是采用所谓的迭代法 求解。 迭代法的基本思想是：先从最优点的某一个初始估计 X(0) 出

43、发，按照一定的规则（即所谓的算法），先找一个比 X(0) 更 好的点 X(1) ，再找比 X(1) 更好的点X(2) ， ，如此继续，就 产生了一个解点的序列 X(k) ,其对应的目标函数 f(X(k) 是逐步 减小的,即： 具有这种性质的算法称为下降迭代算法。,下降迭代算法的一般迭代格式是： （1）选取某一初始点 X(0) ，令 k : = 0 。 （2）确定搜索方向。若已得出某一迭代点 X(k) ,且 X(k) 不是极小 点。这时，就从 X(k) 出发确定一搜索方向 P(k) ，沿这个方向应能 找到使目标函数值下降的点。 （3）确定步长。沿 P(k) 方向前进一个步长，得新点 X(k+1)

44、 。即 在由 X(k) 出发的射线上，通过选定步长（因子） ，得下 一个迭代点 使得 （4）检验新得到的点是否为要求的极小点或近似极小点，如满,足要求，迭代停止。否则，令 k=k+1 , 返回第（2）步继续。 在许多算法中，步长的选定是由使目标函数值沿搜索方向 下降最多为依据的，即沿射线 求的极小，即选 取 ，使 由于这一工作是求以 为变量的一元函数的极小点，故称 这一过程为（最优）一维搜索，由此确定的步长称为最佳步长。 一维搜索有个重要的性质，就是在搜索方向上所得最优点 处的梯度和该搜索方向正交。 定理4 .3 设目标函数 f(X) 具有连续一阶偏导数， 按下述规,则产生 则有：,4.5 求

45、解无约束极值问题的最速下降法（梯度法）,无约束极值问题可表述为： 假定 f(X) 具有一阶连续偏导数，它存在极小点 X *。以 X(k) 表示极小点的第 k 次近似，为了求其第 k+1 次近似 X(k+1) , 在 X(k) 点沿方向 P(k) 作射线:,在此射线上确定 X(k+1) 。由于负梯度方向是函数值下降最快的 方向（通常指在 X(k) 的某一小范围内），沿这一方向搜索，有 可能较快地达到极小点，梯度法就采用这样的方向为搜索方向。 即取 选定了搜索方向之后，还要确定确定步长。 现介绍一种选取步长的方法： 设 f(X) 具有二阶连续偏导数，将 在 作泰勒展开：,上式对求导，并令其等于零，

46、即可得近似最佳步长的如下计算公式：,现将用梯度法求函数 f(X) 的极小点的步骤总结如下： 给定初始点 X(0) 和允许误差 ，令 k:0 。 (2) 计算 和 ，若 ，停止迭代， 得近似极小点 X(k) 和近似极小值 f(X(k) ) ；否则，转下一步。,（3） 使用公式（4.11)求 ，并计算 ， 然后令 k:k1 ,转回第（2）步。,由于沿负梯度方向目标函数的最速下降性，很容易使人 们误认为负梯度方向是最理想的搜索方向，最速下降法是一 种理想的极小化方法。实际上，某点的负梯度方向，通常只 是在该点附近才具有这种最速下降的性质。在一般情况下， 当用最速下降法寻找极小点时，其搜索路径呈直角锯

47、齿状(定 理4.3），在开头几步，目标函数下降较快，但在接近极小点 时，收敛速度就不理想了。特别是当目标函数的等值线为比 较扁平的椭圆时，收敛就更慢了。,4.6 求解约束极值问题的罚函数法和障碍函数法,绝大部分实际问题都受到某些条件的限制，这些限制条件 （约束）常给寻优工作带来很大困难。下面介绍两种求解带约 束极植问题的搜索算法。,4.6.1 罚函数法(外点法）,考虑带约束的非线性规划（4.3），即：,构造函数 如下：,于是当 时有： 当 时有：,这时，如果选取很大的实数 M0 ,并将各个约束条件加到 目标函数上，得一新函数如下：,可以看出，当 时，有 ；当 时，由于M 很大，将使 很大，从而

48、使,很大，这就相当于对非可行点的“惩罚”。而且，X 点离可行域 越远惩罚越严厉。可以想见，当 M 变得足够大时，相应于这样 的 M 值，(4.12) 的无约束极小点 X(M) , 就会和原来的约束问题 的极小点足够接近。而当 时，它就成为原约束问题的 极小点。 惩罚函数（4.12）也可改写成另外的形式：,或者：,是阶越函数：,假定对某一罚因子，例如说 M1 , , 就加大罚因 子的值。随着罚因子数值的增加，惩罚函数中的惩罚项所起 的作用随之增大，minP(X,M) 的解 X(M) 离可行域 R 的“距离” 就会越来越近，当,趋于无穷大时，点列 X(Mk) 就从可行域 R 的外部趋于原非 线性规

49、划问题的极小点。,和不等式约束问题类似，对于等式约束问题，即：,采用以下形式的罚函数：,对于既包含等式约束又包含不等式约束的一般非线性规 划问题(4.1),其罚函数为,或,罚函数法的迭代步骤如下： （1）取第一个罚因子 M1 0 (例如M1 =1），允许误差 ， 并令 k :=1 。 （2）求下述无约束极值问题的最优解： 其中P(X,Mk) 可取式（4.15)或(4.16)的形式。设其极小点为 X(k) 。 （3）若存在某一个 ，有 或存在某一个 ,有 则取 Mk+1Mk ( 例如 Mk+1=cMk , c=10 )，并令 k:=k+1 。然后，,转回第(2)步。 否则，停止迭代，得所要的点

50、X(k) 。,4.6.2 障碍函数法(内点法）,罚函数法的一个重要特点，就是函数 P(X,M) 可在整个 En 空间内进行优化，可以任意选择初始点，这给计算带来了很大 方便。但由于迭代过程常常是在可行域外进行，因而不能以中 间结果直接作为近似解使用。 如果要求每次的近似解都是可行解，以便观察目标函数值 的改善情况；或者，如果目标函数在可行域外的性质比较复杂， 甚至没有定义，这时就无法使用上面所述的罚函数法了。 障碍函数法与罚函数法不同，它要求迭代过程始终在可行,域内部进行。 考虑非线性规划（4.3），当 X 点从可行域 R 内部趋于其 边界时，至少有某一个约束函数 趋于零。 从而，下述倒数函数

51、 和对数函数 都将无限增大。如果把式 (4.17) 或 (4.18) 加到非线性规划 (4.3) 的目标函数上，就能构成新的目标函数障碍函数。,或,如果从某一点 出发，求下列无约束极小化问题,则随着障碍因子 的逐渐减小，即 障碍项所起的作用也越来越小，因而，求出的问题（4.21）的,解 就会逐步逼近原约束问题 (4.3) 的极小解。,障碍函数法的迭代步骤如下： （1）取第一个障碍因子 ，允许误差 ， 并令 k:=1 。 （2）构造障碍函数，可采取 (4.19) 或 (4.20) 。 （3）对障碍函数进行无约束极小化，设所得解为 。 （4）检查是否满足收敛准则：,或,如果满足此准则，则以 X(k

52、) 为原约束问题的近似极小解，停,止迭代；否则，取 rk+1 rk ，令 k:=k+1 , 转回第（3）步继续进 行迭代。,五. 动态规划,动态规划是解决多阶段决策过程最优化问题的一 种方法。该方法是由美国数学家贝尔曼等人在 20 世 纪 50 年代初提出的。他们针对多阶段决策问题的特 点，提出了解决这类问题的最优化原理，并成功地解 决了生产管理、工程技术等方面的许多实际问题。 多阶段决策问题的特点是整个决策过程可以分为 好几个彼此有联系的阶段，而每一个阶段都有多于一 个的小方案需要选择确定，决策者需要在可供选择的 小方案中选出其中的一个最优方案，使其效果在预定 的目标下达到最好。,一个简单的

53、多级决策：有某 旅行者从 A 地出发到 F 地， 可以选择两条路线，一是途 经 B 地，D 地到 F ;另一是途 经 C 地，E 地到 F (如图),每,段路程所需的费用在图中标 出。这个问题是以总旅费达到最小作为目标，显然应选择： A C E F。,整个规划的目标是使得最终结果达到最优，这就意味 着，某一段作出的决策，就这个阶段来说，并不一定是一个 最优的选择，甚至要作出某些牺牲（如上例第一段）。但是,由于各阶段的相互影响，到最后却会得到一个最优的结果。 相反，在这一阶段选择了一个最优的决策，并不等于最后得 到最优结果，这就是动态规划的特点。,使用动态规划方法解决多阶段决策问题，首先要将实际

54、 问题写成动态规划模型，此时要用到以下概念： （1）阶段；（2）状态；（3）决策和策略；（4）状态转 移；（5）指标函数。 下面我们结合以下例题说明这些概念。 例 5.1 最短路线问题。 如图所示，给定一个线路网络图，要从 A 地向 F 地铺 设一条输油管道，各点间连线上的数字表示距离，问应选择,什么线路，可使总距离最短？,A,4,6,8,3,3,5,4,2,5,B1,B2,E2,F,D1,E1,C1,C2,C3,C4,D3,D2,7,3,7,8,3,5,4,4,8,4,3,1,2,6,5,（1）阶段。 将所给问题的过 程，按时间或空间特 征分解成若干互相联 系的阶段，以便按次 序去求每阶段的

55、解。,（2）状态。 各阶段开始时的客观条件叫状态。描述各阶段状态的变量 称为状态变量，sk 表示第 k 阶段的状态变量 ，sk 的取值集合 称为状态集合，用 Sk 表示。,在例5.1中，各阶段的状态集合分别是： 当某段的初始状态已选定某个点时，从这个点以后的铺管 路线只与该点有关，不受以前铺管路线的影响，这叫状态变量 的“无后效性”，如果所选的状态变量不具备“无后效性”就不能 用来构造动态规划模型。,（3）决策和策略。 当各段的状态取定以后，就可以作出不同的决定，从而确 定下一阶段的状态，这种决定称为决策。表示决策的变量，称 为决策变量，常用 uk(sk) 表示第 k 阶段当状态为 sk 时的

56、决,策变量，Dk(sk) 表示第 k 阶段从状态 sk 出发的允许决策集合。 在例5.1中，有 D2(B1)=C1, C2, C3 如我们决定选择 C3，则可表为： u2(B1)=C3 各段决策确定后，整个问题的决策序列就构成一个策略， 用 p1,n u1(s1),u2(s2),un(sn)表示，P1,n 表示允许决策的 集合，使整个问题达到最优效果的策略就是最优策略。 (4)状态转移方程。 动态规划中，如果给定了第 k 阶段的状态 sk 和本阶段决 策 uk(sk) 则第 k+1 段的状态 sk+1 也就完全确定，它们的关,系可用下列状态转移方程表示： sk+1=Tk(sk,uk) 例5.1

57、中，状态转移方程为： sk+1=uk(sk) （5）指标函数。 用于衡量所选定策略优劣的数量指标称为指标函数。它分 为阶段指标函数和过程指标函数两种。阶段指标函数是指第 k 段，从状态 sk 出发，采取决策 uk 时的效益，用 d (sk,uk) 表示。一个 n 段的决策过程，从 1 到 n 叫做问题的原过 程，对任意给定的 ,从第 k 段到第 n 段的过程 称为原过程的一个后部子过程。V1,n(s1,p1,n) 表示初始状态为,s1 采用策略 p1,n 时，后部子过程的指标函数值，而Vk,n(sk,pk,n) 表示在第 k 段，状态为 sk 采用策略 pk,n时 ，后部子过程的指标 函数值。最优指标函数记为 fk(sk) ,它表示从第 k 段状态 sk 采用 最优策略 到过程终止时的最佳效益值。即： 当 k1 时， 就是从初始状态 到全过程结束的整体最 优函数。 下面用动态规划方法求解例5.1 。本方法是从过程的最后 一段开始，用逆序递推方法求解，逐