运筹学_暑期培训

优化与网络模型•优化方法•图论三个工厂：A、B、C。各工厂分别有140吨、120吨、50吨产品待运；三个仓库：甲、乙、丙。甲库可存货60吨，乙库可存货100吨，丙库可存货150吨；任一工厂到仓库的路程如表：工厂仓库ABC甲9126乙613.54.5丙1.539问：如何调运货物才能使总的吨公里最小？什么是最优化？西北大学数学系直观思路：1、距离最短A－丙。（140吨）；2、B－丙。（10吨）；依此类推。可得调运方案：工厂仓库ABC存货量甲6060乙5050100丙14010150供应量14012050总和＝310总吨公里数＝140＊1.5＋60＊12＋50＊13.5＋10＊3＋50＊4.5＝1860。最佳方案：工厂仓库ABC存货量甲105060乙100100丙30120150供应量14012050总和＝310总吨公里数＝1395。西北大学数学系对该问题如果利用数学符号（即建立数学模型）来表示,可如下讨论：设工厂A向仓库甲、乙、丙的调运吨数分别为11x、12x、13x，工厂B向仓库甲、乙、丙的调运吨数分别为21x、22x、23x，工厂C向仓库甲、乙、丙的调运吨数分别为31x、32x、33x，则调运货物的总吨公里数（相当于运输费用）为33323133222113121195.4635.13125.169xxxxxxxxxz现在需要求该函数的最小值，而限制条件为：0,,,,,,,,1501006050120140333231232221131211332313322212312111333231232221131211xxxxxxxxxxxxxxxxxxxxxxxxxxx决策变量目标函数约束条件西北大学数学系优化问题是工程技术、经济管理、科学研究等领域最常遇到的一类问题。它研究在有限或无限种可行方案中挑选最优方案，构造寻求最优解的计算方法。达到最优目标的方案，称为最优方案，搜索最优方案的方法，称为最优化方法。建立的寻求最优的数学表达式，称为最优化模型。西北大学数学系一、优化问题的基本形式及分类形式：min()..()0fxstgxxD³Î分类：（1）约束优化和无约束优化；（2）线性规划、非线性规划、二次规划等。解法：枚举法，搜索法，启发式算法。西北大学数学系二、线性规划及求解标准型：11221111221121122222112212min..,,,0nnnnnnmmmnnmncxcxcxstaxaxaxbaxaxaxbaxaxaxbxxx++++++=+++=+++=³其它形式化为标准型的方法：解法：单纯形法，对偶单纯形法，两阶段法等。西北大学数学系Matlab中的标准型：112211112211211222221122min..nnnnnnmmmnnmcxcxcxstaxaxaxbaxaxaxbaxaxaxb++++++?+++?+++?或min..TzcxstAxb=£求解命令：x=linprog(c,A,b)%返回的值x就是优化问题的最优解。西北大学数学系化标准型的方法：目标函数：max--------min只需令：则目标变为：约束条件：zz¢=-maxminzz¢®：不等式两端同乘-1“=”:利用两个不同方向的不等式约束代替变量范围约束：每一个变量的范围约束看作独立的约束条件西北大学数学系例：321532maxxxxz0,,10527321321321xxxxxxxxxs.t.标准型：123123123123123min235..772510000xxxstxxxxxxxxxxxx--+++?---?-+-?-?-?-?从而[2,3,5]c=--[7,7,10,0,0,0]b=--111111251100010001A轾犏犏---犏犏--犏=犏-犏犏-犏犏-犏臌x=linprog(c,A,b)执行命令：西北大学数学系其它命令：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB)说明：该命令可将不等式约束与等式约束以及变量的范围限制分别输入。A,b:不等式约束的系数矩阵和右端项；Aeq,beq：等式约束的系数矩阵和右端项；LB,UB：变量的范围限制；x,fval：分别返回最优解和最优值。注意：linprog()还有其它形式的用法，具体可在Matlab指令窗运行helplinprog，就能看到所有的函数调用形式。西北大学数学系例：123123123123123max23..2932442360,23,zxxxstxxxxxxxxxxxx无限制利用上述方法处理后，可令[1,2,3]c=---211312A轾-犏=犏--臌[9,4]b=-[4,2,3]Aeq=--6beq=-[10000,2,10000]LB=---[0,3,10000]UB=，，执行命令：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB)西北大学数学系三、整数规划及求解规划中的变量（部分或全部）限制为整数时，称为整数规划。分类：整数规划混合整数规划0-1整数规划西北大学数学系理论解法：整数规划和混合整数规划：分枝定界法割平面法0-1整数规划：完全枚举法，隐枚举法指派问题：匈牙利算法所有整数规划问题：蒙特卡洛算法软件求解：①针对理论解法编程求解；②某些特殊问题可用Matlab命令求解；③主要采用Lingo编程求解西北大学数学系西北大学数学系Lingo程序：设n=8，c，a，B应给出具体值。Max=c1*x1+c2*x2+c3*x3+c4*x4+c5*x5+c6*x6+c7*x7+c8*x8;-1*x1+x2=0;x3+x4=1;x5+x6+x7=2;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);bin(x8);西北大学数学系四、非线性规划及求解西北大学数学系定义：目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）。分类：约束优化和无约束优化西北大学数学系理论解法：无约束优化：梯度法，牛顿法，共轭方向法等；约束优化：障碍函数法，惩罚函数法等。软件求解：①针对理论解法编程求解；②Matlab命令求解；③Lingo编程求解。西北大学数学系x=fmincon(fun,x0,A,B,Aeq,Beq,lb,ub,nonlcon,options)西北大学数学系西北大学数学系无约束优化问题的Matlab求解标准形式：min()fxmin()[,]fxxabÎ命令：[X,FVAL]=fminbnd(fun,x1,x2,options)标准形式：命令：[X,FVAL]=fminunc(fun,x0,options)西北大学数学系西北大学数学系二次规划bAxxfHxxTTs.t.,21min标准型：Matlab命令：[X,FVAL]=quadprog(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)西北大学数学系五、多目标规划及求解西北大学数学系多目标的处理：决策值和目标值：决策变量的值给定后，上面每一个不等式左端的值称为决策值，右端的数称为标值。正负偏差量：决策值和目标值之间的差异。注意：引入偏差量的目的是可将目标函数借助于偏差量表示为等式。西北大学数学系11222331212111222123312min()..211021081056,0,0zpdpddpdstxxxxddxxddxxddxxdd数学模型：解法：（1）利用针对多目标规划的单纯形法求解，这种情况下甚至不需要给出p的值；（2）将p的值给定，直接利用线性规划方法求解。赛题选讲西北大学数学系钢管订购和运输要铺设一条1521AAA的输送天然气的主管道。经筛选后可以生产这种主管道钢管的钢厂有721,,SSS。图中粗线表示铁路，单细线表示公路，双细线表示要铺设的管道(假设沿管道或者原来有公路，或者建有施工公路)，圆圈表示火车站，每段铁路、公路和管道旁的阿拉伯数字表示里程(单位km)。为方便计，1km主管道钢管称为1单位钢管。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7图一西北大学数学系一个钢厂如果承担制造这种钢管，至少需要生产500个单位。钢厂iS在指定期限内能生产该钢管的最大数量为is个单位，钢管出厂销价1单位钢管为ip万元，如下表：i1234567is80080010002000200020003000ip1601551551601551501601单位钢管的铁路运价如下表：里程(km)≤300301～350351～400401～450451～500运价(万元)2023262932里程(km)501～600601～700701～800801～900901～1000运价(万元)37445055601000km以上每增加1至100km运价增加5公路运输费用为1单位钢管每公里0.1万元（不足整公里部分按整公里计算）。钢管可由铁路、公路运往铺设地点（不只是运到点1521,,,AAA，而是管道全线）。问题：请制定一个主管道钢管的订购和运输计划，使总费用最小（给出总费用)。西北大学数学系模型的假设1．公路运输费用为1单位钢管每公里0.1万元，不足整公里按整公里计算。2．购买和运输钢管都是整单位（即为整公里）。3．沿管道或者原来有公路或者建有施工公路。4．一个钢厂如果承担制造钢管，至少要生产500个单位。5．钢管可由铁路、公路运往铺设地点。6．把“钢厂钢管的销价和产量上限变化对总费用和运购计划的影响”理解为在最优解附近的微小变化对总费用和运购计划的影响。销价最小变化是1万元，产量上限的最小变化是1个单位。问题分析铺设一个天然气运输管道（线形或树形），总费用包括购买钢管的费用，运费和铺设时的运费。购买钢管的费用由钢厂的钢管销价和向这个厂订购的钢管数量决定。运费由钢厂向铺设起始点运输的钢管数量和它到此起始点的运输道路决定（由于通过铁路和公路运输，所以并不仅仅由路程决定）。一般情况下铁路运输比公路运输要节省费用（只有在200公里以内，公路运输比铁路运输要节省）。对于铺设费用，在假设一的前提下，由一头出发，铺设x公里的费用的计算是：0.1*[x+(x-1)+(x-2)+…+2+1]=0.05*x*(x+1)，通过比较可以发现：铺设一段管道，从两头往中间铺比从一端向另一端铺要节省费用。再由假设三，铺设时沿管道走的是公路，所以当管道段较长时，两头铺所节省的费用是比较可观的。比如问题一中，所有管道段都从一头铺的铺设总费用为：)]1D([D05.0yx,yx,=12.29亿元。而在最优的铺设方法下（即两头向中间铺的路程相同），铺设总费用为：)]12D(2D[205.0yx,yx,=6.16亿元，最优解中的铺设费用应在这两者之间。因为铺设费用的表达式是二次式，所以求解总费用是一个非线性规划问题。西北大学数学系模型的建立与求解1．模型建立：由定义得：从Si运出的钢管总量：151ji,ji,)RL(Tij购买钢管的费用：C1=71ii)p*T(i把钢管运送到所有Aj的总运费：C2=71ji,ji,ji,151]F*)RL[(ij从Aj向左铺设的钢管量Lj=71iji,L；向右铺设的钢管量Rj=71iji,R铺设钢管过程中的公路运费：C3=0.1*151jjjj1)/2](R*R1)/2(L*[Lj目标函数(总费用)为：