《最优化方法应用知识》由会员分享，可在线阅读，更多相关《最优化方法应用知识（27页珍藏版）》请在金锄头文库上搜索。
1、3 最优化方法许多生产计划与管理问题都可以归纳为最优化问题, 最优化模型是数学建模中应用最广泛的模型之一, 其内容包括线性规划、整数线性规划、非线性规划、动态规划、变分法、最优控制等.min f (x),s.t. xW.最优化问题简单来说就是我们在微积分中学过的求极值(包括条件极值)问题, 此类问题的一般形式为：(P) 这里s.t.是英文subject to (满足于)的缩写, x = (x1 , x2 , , xn )T, 称为决策变量, f (x) 是n元实值函数, 称为目标函数, xW 称为约束条件, W 为可行解域. 如果 W = E n (n维欧氏空间), 则称(P)为无约束优化问题
2、；如果f (x )是线性函数, W 由若干个线性等式或不等式确定, 则称(P)为线性规划问题(LP). 这类优化问题(P)统称为静态规划问题, 它包括线性规划和非线性规划.本章将对线性规划、动态规划和非线性规划问题一一作简要地介绍.3.1 线性规划线性规划是最优化方法中理论完整、方法成熟、应用广泛的一个重要分支, 可以应用于生产计划, 物资调运, 资源优化配置, 地区经济规划等问题.3.1.1 线性规划问题的数学模型例1 (生产计划问题) 某工厂生产甲、乙两种产品, 甲产品每生产一件需消耗黄铜2kg, 3个工日, 两个外协件, 每件可获利润60元；乙产品每生产一件需消耗黄铜4kg, 1个工作日
3、, 不需外协件, 每件可获利润30元. 该厂每月可供生产用的黄铜320kg, 总工日180个, 外协件100个. 问应怎样安排生产才能使工厂的利润最高？下面我们来分析问题, 建立数学模型.问题是：怎样安排生产, 即甲、乙两种产品各生产多少才能使工厂的利润最高？用x1, x2分别表示甲、乙两种产品生产的件数, 该厂追求的目标是获取最高利润, 用数学表达式表示为：max f = 60x1 + 30x2.由于生产甲、乙产品的件数要受到生产能力的约束, 即黄铜约束 2x1 + 4x2 320,工日约束 3x1 + x2 180,外协件约束 2x1100,非负约束 x1, x2 0.这样, 该厂生产计划
4、问题就归结为如下数学模型max f =60x1 + 30x2,2x1 + 4x2 320,3x1 + x2 180,2x1100,x1, x2 0.例2 (运输问题) 计划由三个粮站A1, A2, A3运输某种粮食至三个加工厂B1, B2, B3, 三个粮站的供应量和三个加工厂的需求量以及各供应地至需求地的单位运输价(元/吨)如表3-1所示, 试作出运费最省的调运计划方案.表3-1加工厂粮站B1 B2 B3供应量(吨)A1A2A3 120 80 9070 40 3060 50 20203050需求量(吨)25 50 25100现在的问题：如何调运, 才能使运费最省？设xij表示第i个粮站运到第
5、j个加工厂的粮食数量(单位：吨, i, j =1, 2, 3 ), 则总运费f = 120x11 + 80x12 + 90x13 + 70x21 + 40x22 + 30x23 + 60x31 + 50x32 + 20x33 .从各粮站运出的粮食数量不能超过供应量x11 + x12 + x13 = 20, x21 + x22 + x23 = 30, x31 + x32 + x33 = 50,同时还要保证各加工厂的需要x11 + x21 + x31 = 25, x12 + x22 + x32 = 50, x13 + x23 + x33 = 25,而运输量应满足 xij 0.于是上述运输问题的数学
6、模型为min f = 120x11 + 80x12 + 90x13 + 70x21 + 40x22 + 30x23 + 60x31 + 50x32 + 20x33 ,x11 + x12 + x13 = 20,x21 + x22 + x23 = 30,x31 + x32 + x33 = 50,x11 + x21 + x31 = 25,x12 + x22 + x32 = 50,x13 + x23 + x33 = 25,xij 0.从上述两个例子可以看出, 虽然两个问题的具体内容和性质不同, 但它们都属于优化问题, 它们的数学模型都有相同的数学形式, 即在一定的线性等式或不等式的条件下, 使某一线性
7、函数达到最大(或最小).所谓线性规划问题的数学模型是将实际问题转化为一组线性不等式或等式约束下求线性目标函数的最小(大)值问题, 它都可以化为如下标准形式：(LP) min f = c1x1 + c2x2 + + cnxn ,a11x1 + a12x2 + + a1nxn = b1 ,a21x1 + a22x2 + + a2nxn = b2 , am1x1 + am2x2 + + amnxn = bm ,x1 , x2 , , xn 0.记c = (c1 , c2 , , cn ), A = (aij )mn, x = (x1 , x2 , , xn )T, b = (b1 , b2 , ,
8、bm )T, 可将(LP)写成矩阵形式：min f = cx,s.t.Ax = b,x0.(LP) 其中x0意指x中的每一个分量xj 0.再记A = (a1 , a2 , , an ), 并且假设A的秩为m. 我们把A中任意m个线性无关列向量组成矩阵B称为线性规划问题(LP)基矩阵, 简称基；对应变量称为基变量, 其它变量称为非基变量.由于线性无关, 因此B = ()可逆, 用B-1左乘Ax = b的两边得B-1Ax = B-1b 3-1记 B-1A = (pij )mn = ( p1 , p2 , , pn ), B-1b = ( b 1 , b 2 , , b m )T, 不难看出都是基本
9、单位向量, 即 () = I.用D表示非基变量下标的集合, 即D =1, 2, , n - j1 , j2 , , jm, 由3-1式得到用非基变量表示基变量如下： 3-2记cB = (), 用cB左乘3-1式的两边得cBB-1Ax = cBB-1b 3-3由f = cx和3-3式得f = cBB-1b - (cBB-1A- c )x 3-4再记 g = cBB-1b, cBB-1A- c = (a1 , a2 , , an ), 由3-4式得到用非基变量表示的目标函数：f = g - 3-53-5式和3-2式合称为 (LP) 对应于基B的典式.由3-2式知, 当所有的非基变量xj = 0 (
10、 jD) 时, 基变量 = b i ( i = 1, 2, , m ) 是Ax = b的解, 此解称为 (LP) 的基解. b 1 , b 2 , , b m通常称为基变量值.当某个基解为可行解, 即所有的基变量值非负时, 此基解称为基可行解, 相应的基B称为可行基.假设B为可行基, 由3-5式和3-2式可得如下两个最优判别准则：最优判别准则 当所有的检验数 a1 , a2 , , an0时, f = g 为(LP)的最优值.此时的基B称为最优基, 相应的基可行解称为基最优解.最优判别准则 若有某个检验数 as0, 且ps0, 则(LP)无最优解.读者可以自行证明最优判别准则和.3.1.2 单
11、纯形解法设B是(LP)的一个基, 其典式的矩阵表现形式是, 上述矩阵称为对应于基B的单纯形表, 记作T (B), 它通常写成如下形式(表3-2)：表3-2x1 x2 xnfga1 a2 anb 1b 2b mp11 p12 p1np21 p22 p2n pm1 pm2 pmn如果prs0 (sD), 那么利用初等行变换可将T (B)的第r行( prs所在的行)除以prs, 然后将第0行(目标函数行)减去第r行的as倍, 再将第i行减去第r行的pis倍, 即使prs所在的列中其它各项都变为0. 这种变换相当于将其典式的第r式中的非基变量xs解出, 再代入其它各式得到一个新基对应的典式, 称这种变
12、换为换基迭代, 称prs为轴心项, xs为进基变量, 为离基变量.下面给出(LP)已有一个可行基B的单纯性解法迭代步骤 计算T (B), 转向. 根据最优判别准则, 若B是最优基或(LP)无最优解, 停；否则转向. 寻找轴心项, 假设正检验数中下标最小的是as, 则取满足b r /prs = minb i /pis | pis 0, 1im的prs为轴心项, 转向. 以prs为轴心项换基迭代, 得新基B1, 用B1代替B, 转向.1976年, Bland证明了在已有一个可行基的单纯性解法中, 按照选取轴心项换基迭代, 迭代次数是有限的.读者也可以自行证明每次迭代后得到的新基是可行基, 且目标函
13、数值是递减的.例3 用单纯形法解本节例1中的线性规划问题.解 原模型为：max f = 60x1 + 30x2,2x1 + 4x2 320,3x1 + x2 180,2x1100,x1, x2 0.引入松弛变量x3, x4, x5, 化原问题为标准形式min g = - max f = - 60x1 - 30x2,2x1 + 4x2 + x3 =320,3x1 + x2 + x4 =180,2x1 + x5 =100,x1, x2 , x3, x4, x50.在约束条件中, 变量x1, x2 , x3, x4, x5对应的列向量为a1 = (2, 3, 2)T, a2 = (4, 1, 0)T, a3 = (1, 0, 0)T, a4 = (0, 1, 0)T, a5 = (0, 0, 1)T.令B0 = (a3 , a4 , a5 ), 则B0为单位矩阵, 是一个现成可行基, 对应的单纯形表为表3-3.表3-3x1 x2 x3 x4 x5g060 30 0 0 0x3x4x53201801002 4 1
