《第三节 交通运输优化》由会员分享，可在线阅读，更多相关《第三节 交通运输优化（6页珍藏版）》请在金锄头文库上搜索。
1、第三节 交通运输优化在研究交通和交通运输问题的过程中，经常遇到大量的最优化问题。比如， 货物的最优运输线路；城市信号交叉口最优信号配时；城市交通组织最优方案等。例1某运输公司，运输甲、已两种产品。运输过程必须经过A1、A2、A3三个地 方，每个地方产品运输数量、每种产品单位运输成本及运输成本限额如表 所示。试问该公司如何安排运输，使公司获得利润最大？表1单位产品运费甲乙运费限额A3416B2320C2115单位利润79例 2 （生产计划问题）某企业计划生产甲、乙两种产品，这两种产品均需在 A、B、 C 三种不同设备上加工。每单位产品所耗用的设备工时、单位产品利润 及各设备在某计划期内的工时限额
2、如表 1。试问应如何安排生产计划，才 能使企业获得最大利润。表2设备单位产品耗工时甲乙工时限额A116B128C026单位利润341 基本概念（1）设计变量（决策变量）：在设计过程中进行选择并最终必须确定的各项独 立参数。（2）最优化设计的维数：决策变量的数目称为最优化设计的维数，比如：1 维、 2 维、 3 维设计问题。（3）设计空间：在最优化设计中由各决策变量的坐标轴所描述的空间称为设计 空间。当决策变量数目大于3时，n维空间又称为超越空间。注意：设计空间中的一个点（一组决策变量的值）就是一种设计方案。（4）目标函数：用决策变量表示的、反应所设计问题性能的函数表达式。 注意：最优化设计的过
3、程就是选择合理的决策变量，使目标函数达到最优或找出目标函数的最小值（或最大值）的过程。（5）单目标函数最优化问题 ：目标函数只有一个。（6）多目标函数最优化问题 ：目标函数（性能指标）有多个。（7）无约束优化、约束优化（8）线性规划（Linear Programming，简记为LP）：目标函数和约束条件都是 自变量（包括决策变量和非决策变量）的线性函数。非线性规划（Nonlinear Programming，简记为NP）：如果目标函数和约 束函数中至少有一个是自变量的非线性函数，这种规划问题就称为非线性规划问 题。2 实例分析上述例2 ，属于单目标函数最优化问题。（1） 数学模型（优化模型）的
4、建立决策变量：计划期内甲、乙两种产品的产量，分别用x、x表示，其取值均为非12负；目标函数：计划期内两种产品的总利润，用z表示，即z = 3 x + 4 x12问题：总利润最大，即max z = 3 x + 4 x12约束条件：xX2受到工时限额的约束即x + x 6 12x + 2 x 8122x 0， x 012综上，该问题的数学模型（优化模型）为max z = 3 x + 4 xs.t.12x + x 6(1)12x + 2 x 8122x 012其中，“ s.t. ”为“subject to”（受约束于）的缩写。2）模型求解方法：线性规划的图解法；MATLAB软件。图解法适用条件：二维
5、优化问题（几何含义： XOY 二维坐标系），即只有两个 决策变量。解 可行域图形的确定LP 模型所有约束条件构成的公共部分。称为可行域图形。因为x ,x 0，可行域在第一象限。第一个约束条件x + x 6表示半平面, 1 2 1 2此半平面是以直线x +x 6为边界的在其左下方第一象限部分。类似地，12可求出其余约束条件表示的半平面部分（见图 1）。图中的凸多边形 OABCD 即为该例的可行域图形。图1 凸多边形（包括其边界）上的每一点，都是本例 LP 模型的一个可行解。因 此凸多边形区域 OABCD 是该 LP 模型的可行解的集合，称为可行域，可行域 中使目标函数达到最大（或最小）的点为最优
6、点，最优点对应的坐标即为 LP 的最优解，相应的函数值称为最优值。目标函数的等值线与最优点的确定考虑本例的目标函数z = 3 x + 4 x12 它代表以 z 为参数，-3/4 为斜率的一簇平行线。由小到大给z赋值，如令z = 0,4,12等可得到一组平行线（见图1），而位于同一直线上的点，具有相同的目标函数值，因而称其为等值线。垂直于这组平行线画一直线，取z值沿此直线递增的方向，即为直线簇z = 3x + 4x的法线 12方向（如图1）,其为z值增加最快的方向。沿法线方向平行移动直线z = 3x + 4x，当移动到B点时，z值在可行域上达 12到最大，从而B为最优点。求出B点坐标，解x +
7、2 x = 8 1 2x + x = 6121得 x * = 4， x * = 2，最优值为 z = 20。1 2 max故本例的最优生产方案为：日产甲产品 4 件，乙产品 2 件，每天可得最大利润20 千元。(3) 图解法求解工具：AutoCADAutoCAD 步骤：1) 设置极限(limits) : (-10, -10), (10, 10)2) 设置栅格间距：0.53) 打开栅格；4) 绘制可行域图形(由各个约束条件对应直线构成的闭合凸多边形)；5) 绘制目标函数对应直线(等值线)；6) 沿目标函数法线方向平移目标函数等值线(offse t)；7) 确定最优解，利用目标捕捉工具获取最优解对应点坐标(id)。(4) 使用MATLAB软件求解函数：linprog函数(具体参见该函数语法手册)求解问题：最小化问题minf(x),约束条件为A*x=b格式：x=linprog(f,A,b,lb),lb 为向量 X (x1,x2)的下限 实例中目标函数(1)需转换为等效的最小化形式：min z = 一 3 x - 4 x 12首先输入下列系数：f=-3;-4;A=1 1;1 2;0 2;b=6;8;6lb=0;0然后调用 linprog 函数：x=linprog(f,A,b,lb)
