数学规划模型的建立与求解

1、数学规划模型的建立与求解数学规划模型的建立与求解张兴元2009 年 3 月数学规划模型的建立与求解1优化问题及其一般模型优化问题及其一般模型 优化问题是人们在工程技术、经济管理和科学研究等领域中最常遇到的问题之一。例如：n 设计师要在满足强度要求等条件下选择材料的尺寸， 使结构总重量最轻；n 公司经理要根据生产成本和市场需求确定产品价格， 使所获利润最高；n 调度人员要在满足物质需求和装载条件下安排从各 供应点到需求点的运量和路线，使运输总费用最低；n 投资者要选择一些股票、债券下注，使收益最大，而风险最小n 数学规划模型的建立与求解一般地，优化模型可以表述如下： min( ). .( )0i

2、zf xs tg x ， i i = =1 1, , 2 2, , , m m 这是一个多元函数的条件极值问题，其中 x = x 1 , x 2 , , x n 。 许多实际问题归结出的这种优化模型，但是其决策变量个数 n 和约束条件个数 m 一般较大，并且最优解往往在可行域的边界上取得，这样就不能简单地用微分法求解，数学规划数学规划就是解决这类问题的有效方法。 数学规划模型的建立与求解2数学规划模型分类数学规划模型分类“数学规划是运筹学和管理科学中应用及其广泛的分支。在许多情况下，应用数学规划取得的如此成功，以致它的用途已超出了运筹学的范畴，成为人们日常的规划工具。”H.P.Williams

3、.数学规划模型的建立。 数学规划包括线性规划线性规划、非线性规划、整数规划整数规划、几何规划、多目标规划等，用数学规划方法解决实际问题，就要将实际问题经过抽象、简化、假设，确定变量与参数，建立适当层次上的数学模型，并求解。 数学规划模型的建立与求解3建立数学规划模型的步骤建立数学规划模型的步骤当你打算用数学建模的方法来处理一个优化问题的时候，首先要确定寻求的决策是什么，优化的目标是什么，决策受到那些条件的限制（如果有限制的话），然后用数学工具（变量、常数、函数等）表示它们，最后用合适的方法求解它们并对结果作出一些定性、定量的分析和必要的检验。 数学规划模型的建立与求解Step 1. 寻求决策，

4、即回答什么？必须清楚，无歧义寻求决策，即回答什么？必须清楚，无歧义。 阅读完题目的第一步不是寻找答案或者解法，而是Step 2. 确定决策变量确定决策变量 第一来源：Step 1的结果，用变量固定需要回答的决策 第二来源：由决策导出的变量（具有派生结构） 其它来源：辅助变量（联合完成更清楚的回答）Step 3. 确定优化目标确定优化目标 用决策变量表示的利润、成本等。Step 4. 寻找约束条件寻找约束条件 决策变量之间、决策变量与常量之间的联系。 第一来源：需求； 第二来源：供给； 其它来源：辅助以及常识。Step 5. 构成数学模型构成数学模型 将目标以及约束放在一起，写成数学表达式。 数

5、学规划模型的建立与求解【实例【实例 1 】：某储蓄所每天的营业时间是上午9:00到下午5:00。 根据经验，每天不同时间段所需要的服务员数量如下：时间段（时）9-1010-1111-1212-11-22-33-44-5服务员数量43465688储蓄所可以雇佣全时和半时两类服务员。全时服务员每天报酬100元，从上午9:00到下午5:00工作，但中午12:00到下午2:00之间必须安排1小时的午餐时间。储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬40元。问该储蓄所应如何雇佣全时和半时两类服务员？ 数学规划模型的建立与求解Step 1：需要回答什么？：需要回答什么

6、？ 1. 雇佣的全时雇员数量和半时雇员数量； 2. 半时雇员开始上班时间？（最早9:00，最晚1:00） 3费用是多少？ Step2：决策变量？：决策变量？ 1全时雇员数量：x； 2每个时间开始时雇佣的半时雇员数量：yi，i=1,2,5 3清楚吗？漏掉了什么？ 全时雇员需要午餐。 4全时雇员数量分解：12点就餐：x1；1点就餐：x2注意：x1，x2为由决策导出的变量。 Step3Step3：目标函数：目标函数 目标：支付报酬最少 支付报酬=全时员工报酬+半时员工报酬 Z=100(x1+x2)+40(y1+y2+y3+y4+y5)数学规划模型的建立与求解Step4：约束条件：约束条件 需求：服务

7、员数量约束(8个)； 供方约束：半时雇员约束：y1+y2+y3+y4+y53； 常规约束：非负整数。 Step5：数学模型：数学模型 12123451211212121232123412345123451245125123451212345100()40(). .434656883,0Minxxyyyyys txxyxxyyxxyyyxyyyyxyyyyxxyyyxxyyxxyyyyyyxxyyyyyZ 数学规划模型的建立与求解发电站 A水库 B水库 A发电站 B水源 A水源B【实例【实例2】：某电力公司经营两座发电站，发电站分别位于两个水库上，位置如右图所示： 已知发电站可以将水库A的1万立

8、方米的水转换为400千度电能，发电站B只能将水库B的1万立方米的水转换为200千度电能。发电站A、B每个月的最大发电能力分别是60000千度、35000千度。每个月最多有50000千度电能够以200元/千度的价格售出，多余的电能只能够以140元/千度的价格售出。水库A、B的其它有关数据如下表（单位：万立方米）。请你为该电力公司制定本月和下月的生产经营计划。 水库 A水库 B水库最大蓄水量20001500水源流入水量本本月20040下月13015水库最小蓄水量1200800水库目前蓄水量1900850数学规划模型的建立与求解Step 1. Step 1. 寻求决策，即回答什么？寻求决策，即回答什

9、么？ 1. 水库A、B本月和下月发电量（可以用水量表示）； 2. 电力公司的收益。 Step 3. Step 3. 确定优化目标确定优化目标 目标：利润最大化。 利润=高价电利润+低价电利润 P=200(u1+u2)+140(v1+v2) Step 2. Step 2. 确定决策变量确定决策变量 1.1. 水库A、B本月和下月用于发电的水量：xA1，xA2，xB1，xB2 2. 收益导出决策变量： 本月和下月高价售电量：u1，u2；本月和下月低价售电量：v1，v2； 3. 辅助决策变量（水库安全运行）： 本月和下月水库直接放走的水量：yA1，yA2，yB1，yB2； 本月和下月结束时水库的水量

10、：zA1，zA2，zB1，zB2 数学规划模型的建立与求解Step 4. 寻找约束条件寻找约束条件 1. 电量守恒：每月发电量=每月卖出量（2个） 2. 水量守恒： 发电用水量+直接放走量+库存量=原有库存量+来水量（4个） 3. 发电能力限制：4个 4. 水库蓄水量限制：4个 5. 高价电量限制：2个 Step 5. 构成数学模型构成数学模型 121211112222111111112221222122112212max 200()140(). . 400200, 4002001900200850401301595000 ,950040060000 , 400ABABAAABBBAAAAAA

11、BBBBAAAAuuvvs txxuvxxuvxyzxyzxyxyzzxyzzxyuvuvxx 1212121212121212121212126000020035000 , 2003500012002000 ,120020008001500 , 800150050000 ,50000,0BBAABBAABBAABBAABBxxzzzzuuxxxxyyyyzzzzu uvv 数学规划模型的建立与求解【实例【实例3】：】：有4名同学到一家公司参加三个阶段的面试：公司要求每个同学必须首先到秘书处初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的

12、）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）： 秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早上8:00，问他们最早何时离开公司？ 数学规划模型的建立与求解Step 1. 寻求决策，即回答什么？寻求决策，即回答什么？ 1. 同学甲、乙、丙、丁的面试次序 1）同学甲、乙、丙、丁每个阶段面试的开始时间 2）先后次序 2. 离开时间 Step 2. 确定决策变量确定决策变量 1. 同学甲、乙、丙、丁参加第j阶段面试的开始时间ti,j； 2. 同

13、学甲、乙、丙、丁面试结束时间：T1，T2，T3，T4 3. 离开时间：T=max T1，T2，T3，T4 4. 先后次序：ri,j，01变量 5. 面试时间（已知）：ci,jStep 3. 确定优化目标确定优化目标 Min T 数学规划模型的建立与求解Step 4. 寻找约束条件寻找约束条件 1. 单人面试先后次序约束：ti,j+ci,jti,j+1，i=1,2,3,4；j=1,2 2. 每个阶段j在同一时间只能由一个同学参加面试： ti,j + ci,j - tk,j T ri,k （i,k=1,2,3,4；j=1,2,3；ik） tk,j + ck,j ti,j T(1 - ri,k)（i

14、,k=1,2,3,4；j=1,2,3；ik） Step 5. 构成数学模型构成数学模型 123411,31,322,32,333,33,344,34,3,1,.max,. .,1,2,3,4;1,2, ,1,2,3,4;1,2,3;(1) , ,1,2,3,4;1,2,3;i ji ji ji ji jk ji kk jk ji ji kiMin TT T T Ts tTtcTtcTtcTtctctijtctT ri kjiktctTri kjikt ,0,0 ,1,2,3,4;1,2,301jii kTijror 数学规划模型的建立与求解4模型的理论求解方法模型的理论求解方法线性规划问题和整

15、数规划问题是两类非常重要的数学规划问题，它们的求解方法是很多数学规划问题的求解方法的基础。 4.1 线性规划问题的单纯形法线性规划问题的单纯形法4.1.1 一般的线性规划问题模型一般的线性规划问题模型 1122(1)(1)(2)(2)(3)(3)min (max ). .nnzc xc xc xs tAxbAxbAxb 或或其中 12,TnnxxxxR(1)(2)(3),AAA为矩阵， (1)(2)(3),bbb，为列向量。 数学规划模型的建立与求解4.1.2 标准的线性规划问题标准的线性规划问题min. .0Tzc xs tAxbx 其中： ,0,nmm nx cRbRbARmn （1）数学

16、规划模型的建立与求解4.1.3 单纯形法单纯形法G.B.Dantzig的单纯形法（Simplex method）是一个顶点迭代算法，即从一个顶点出发，沿着凸多面体的棱迭代到另一个顶点，使目标函数值下降（至少不升），由顶点个数的有限性，可以证明经过有限次迭代一定可以求得最优解或者判定该问题无最优解，这就是单纯形法的基本思想。而几何上一个的顶点对应在代数上的一个基可行解，因此，单纯形法求解线性规划问题只需要关心基可行解。 数学规划模型的建立与求解若线性规划问题 （1）中： ,AIN ，其中I是一个 m 阶单位矩阵，且 12,0mbbb ，即为 1122,11111,111,122,112,2,11

17、,min(). .(2)0 ,1,2,nnmnmiijii jjij mimmnnmmnnmm mmm nnmjzc xc xc xc bcc axs txaxaxbxaxaxbxaxaxbxjn 则 I 称为线性规划问题的一个基 ， 而对应着基的变量 ,1,2,jxjm 称为基变量，其余变量 ,1,2 ,jxjmmn 为非基变量。 非基变量均取值零的可行解 12,0,0Tmxbbb 称为基可行解。 数学规划模型的建立与求解单纯形法的计算步骤如下： 数学规划模型的建立与求解【示例】【示例】利用单纯形法求解线性规划问题 1212121212max10001500. .95350452002515

18、0,0wxxs txxxxxxxx 第一步，将原问题化成标准形式，并构造初始单纯形表第一步，将原问题化成标准形式，并构造初始单纯形表 【解】：【解】：345,xxx，引入松弛变量将原问题化成标准形式：3453412121212125min(10001500). .953504520025150,0,zxxsxxxxxxtxxxxxxx x 数学规划模型的建立与求解该问题已经满足（2），基变量为 345,xxx，非基变量为 12,xx基本可行解为 0,0,350,200,150Tx ，目标函数值为，检验系数为 1000,1500,0,0,0T ，构造初始单纯形表如下： 基变量基变量p p1 1p

19、 p2 2p p3 3p p4 4p p5 5b b9 95 51 10 00 03503504 45 50 01 10 02002002 25 50 00 01 1150150检验数检验数10001000150015000 00 00 00 05x4x3xj 3453412121212125min(10001500). .953504520025150,0,zxxsxxxxxxtxxxxxxx x 1210000 ,15000 因为 所以当前解不是最优解不是最优解。 数学规划模型的建立与求解第二步，选择进基变量与离基变量第二步，选择进基变量与离基变量基变量基变量p1p2 p3p4p5bx39

20、5100350 x445010200 x52001150检验数检验数100015000000j 第三步，以第三步，以3,2a为主元进行迭代，得新的单纯形表如下为主元进行迭代，得新的单纯形表如下 基变量基变量p1p2p3p4p5bx37010-1200 x42001-150 x20.41000.230检验数400000-300-45000j 新的基本可行解为 0,30,200,50,0Tx 新的最优值为 -45000；14000 ，当前解不是最优解不是最优解。 检验数数学规划模型的建立与求解 第四步，重复前面的第二步，选择进基变量和离基变量第四步，重复前面的第二步，选择进基变量和离基变量基变量基

21、变量p1p2p3p4p5bx37010-1200 x4001-150 x20.41000.230检验数检验数400000-300-45000j 第五步，以第五步，以 为主元进行迭代，得新的单纯形表如下：为主元进行迭代，得新的单纯形表如下： 2,1a基变量基变量p p1 1p p2 2p p3 3p p4 4p p5 5b bx x3 30 00 01 1-3.5-3.52.52.52525x x1 11 10 00 00.50.5-0.5-0.52525x x2 20 010 0-0.2-0.20.40.42020检验数检验数0 00 00 0-200-200-100-100-55000-55

22、000j 最优解： 25,20,25,0,0Tx 最优值： 55000 数学规划模型的建立与求解4.2 整数规划问题的分支定界法整数规划问题的分支定界法求解整数规划问题的算法有分支定界法、割平面法、分解算法、松弛算法、群论算法等。 分支定界算法分支定界算法（Branch and Bound Algorithm）是最常用的一种，它是1965年由 R.J.Dakin 发现的一种隐式枚举法。它的基本思想是反复划分可行域，定出最优值 z*的界限 z1z*z2对于极大化问题来讲，下界 z1 即为由计算已求得的所有可行整数点中的最大目标值，上界 z2 可由松弛问题的最优值或尚未查清的子问题的最大目标值得到

23、，分支定界法就是将一个问题（P)不断的分支为几个问题的集合，并确定新的各子问题的界限，直到求得所要求的解为止。 数学规划模型的建立与求解分支定界法解纯整数规划和混合整数规划问题分支定界法解纯整数规划和混合整数规划问题n 首先忽略整数约束求解，求得原问题的最优解 xn 如果决策变量 xi 本是整数要求，但是得到的结果 xi=u（不是整数），则将原问题归结为2个区域的线性规划求解，这个两个区域为分别增加约束条件 xi ceil(u) 和 xi floor(u)n 然后分别都这两个规划模型重复上面的步骤，直到满足整数要求为止。n 再选出最优解。 数学规划模型的建立与求解【示例】利用分支定界算法求解ILP问题： 1212012max58. .6()59450,1,2.iizxxs txxPxxxxI i P0 x1=2.25x2=3.75z=41.25x1=1.8x2=4z=41x1=3x2=3z=390z*4141P1x24P2x233121211212max58. .6()59450,4zxx