浙大城院数学建模5

21:21:47MCM1第五章、优化模型§5.1线性规划模型§5.2运输问题§5.3库存问题§5.4最佳捕鱼方案§5.5森林救火费用最小问题21:21:47MCM2§5.5森林救火费用最小问题§5.6光学中的折射原理§5.7身体结构得优化21:21:47MCM3经济管理和科学研究等领域中经常会遇到的问题类型之一。在很多情况下，我们会凭经验解决面临的优化问题，这样做看似有效，风险也较小，但决策时常常会融入太多决策者的主观臆断，因而无法保证结果的最优性。那么，是否一定要做大量的试验来探索最优方案呢？前言：最优化方法是数学学科中的一个应用性很强的分支，它包含的内容十分广泛，有数学规划（如线性规划、非线性规划、二次规划、目标规划、多目标规划等）、库存论、排队论、博弈论、组合优化（离散优化）、随机规划等等。21:21:47MCM4§5.1线性规划模型线性规划（LinearProgramming,简记LP）是数学规划的一个重要组成部分。自从1947年G·B·Dantzig提出求解线性规划的单纯形法以来，线性规划在理论上日趋成熟，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。21:21:47MCM5某厂生产甲、乙两种产品，每单位产品销售后的利润分别为4千元与3千元。生产甲产品需用A、B两种机器加工，每单位产品的加工时间分别为2小时和1小时；生产乙产品需用A、B、C三种机器加工，每单位产品的加工时间为每台机器各一小时。若每天可用于加工这两种产品的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应当生产甲、乙两种产品各多少，才能使总利润最大？例5.1（线性规划的实例）21:21:47MCM6例5.1的数学模型设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1、x2应满足：12max43xx12122122108.7,0xxxxstxxx(5.1)4x1+3x2表示生产x1单位甲产品和x2单位乙产品的总利润，被称为问题的目标函数。中的几个不等式是问题的约束条件，记为S.t。由于式中的目标函数与约束条件均为线性函数，故被称为线性规划问题。21:21:47MCM7线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有（称没有非负约束的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为线性规划的标准形式1minnjjjcx1,1,...,.0,1,...,nijjijjaxbimstxjn(5.2)21:21:47MCM8或更简洁地，利用矩阵与向量记为minTzCx.0Axbstx(5.3)其中C和x为n维列向量，b为m维列向量，b≥0，A为m×n矩阵，mn且rank(A)=m。21:21:47MCM9如果根据实际问题建立起来的线性规划问题并非标准形式，可以将它如下化为标准形式：（1）若目标函数为maxz=CTx，可将它化为min－z=－CTx（2）若第i个约束为ai1x1+…+ainxn≤bi，可增加一个松驰变量yi，将不等式化为ai1x1+…+ainxn+yi=bi，且yi≥0。若第i个约束为ai1x1+…+ainxn≥bi，可引入剩余量yi，将不等式化为ai1x1+…+ainxn－yi=bi，且yi≥0。（3）若xi为自变量，则可令，其中、≥021:21:47MCM10例如，例5.1并非标准形式，其标准形式为12min43xx12312425123452108.7,,,,0xxxxxxstxxxxxxx(5.4)21:21:47MCM11为了了解线性规划问题的特征并导出求解它的算法，我们先应用图解法来求解例5.1。满足线性规划所有约束条件的点被称为问题的可行点（或可行解），所有可行点构成的集合被称为问题的可行域，记为R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们就得到了一族平行直线（见图5-1）。线性规划的图解法21:21:47MCM12图5-1（注：）对于例5.1，等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，例5.1的最优解为x*=(2,6)T，最优目标值z*=26。21:21:47MCM13（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”，（注：我们称这种“顶点”为极点）。从上面的图解过程可以看出并不难证明以下断言：（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时必定是若干个半平面的交集（除非遇到空间维数的退化）。R既可能是有界区域，也可能是无界区域。（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。21:21:47MCM14上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足某一线性等式aix=bi的点集被称为一个超平面，而满足某一线性不等式aix≤bi（或aix≥bi）的点集被称为一个半空间（其中ai为一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域R必定为多胞形（为统一起见，空集Φ也被视为多胞形）。在一般n维空间中，要直接得出多胞形的极点概念还有一些困难。在图5.1中顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径（代数方法）来定义它。21:21:47MCM15给定一个标准形式的线性规划问题（5.3），其中A=(aij)mxn，mn且秩r(A)=m。取出A的m个线性无关的列，这些列构成A的一个m阶非奇异子矩阵B，称B为A的一个基矩阵。A的其余n－m列构成一个m×(n－m)矩阵N。称对应于B的列的变量为基变量（共有m个），记它们为xB。其余变量称为非基变量，记为xN。基本解与基本可行解21:21:47MCM16对线性规划（5.3），取定一个基矩阵B，令非基变量xN=0，可以唯一地解出xB，xB=B-1b。这样得到的点x=（B-1b，0）称为（5.3）的一个基本解。为了叙述方便起见，这里我们将xB放在了前面，其实，它们的位置可以任意，但这并不影响到问题实质。显然，基本解不一定是可行解，因为还要求它们满足非负约束，当一个基本解同时还是可行解时（即B-1b≥0），称之为（5.3）的一个基本可行解。进而，若B-1b0，则称x=（B-1b，0）为（5.3）的一个非退化的基本可行解，并称B为一组非退化的可行基。由于基矩阵最多只有种不同的取法，即使A的任意m列均线性无关，且对应的基本解均可行，（5.3）最多也只能有个不同的基本可行解。21:21:47MCM17定理5.1基本可行解与极点的等价定理设A为一个秩为m的m×n矩阵（nm）b为m维列向量，，记R为（5.3）的可行域。则x为R的极点的充分必要条件为x是在线性规划的求解中，下列定理起了关键性的作用。基本可行解与极点的等价定理定理5.1既提供了求可行域R的极点的代数方法，又指明了线性规划可行域R的极点至多只有有限个。的基本可行解。0Axbx21:21:47MCM18定理5.2线性规划基本定理线性规划（5.3）具有以下性质：（2）若问题（5.3）存在一个最优解，则必定存在一个最优的基本可行解。（1）若可行域R≠Φ，则R必有基本可行解。定理5.2并非说最优解只能在基本可行解（极点）上达到，而是说只要（5.3）有有限最优解，就必定可在基本可行解（极点）中找到。21:21:47MCM19从模型本身来讲，线性规划显然应属于连续模型。但定理5.2表明，如果线性规划具有有限最优解，我们只需比较各个基本可行解上的目标函数值，即可找到一个最优解，而问题的基本可行解至多只有有限个，从而问题化为一个从有限多个极点中去选取一个最优点的问题。正是基于这样一种想法，Dantzig提出了求解线性规划问题的单纯形法。21:21:47MCM20Dantzig单纯形法的基本步骤如下：求解线性规划的单纯形法步1:取一个初始可行基B（一般取法见后面的两段单纯形法），再用高斯—约当消去法求出初始基本可行解x0，编制成所谓的初始单纯形表；步2:判断x0是否最优解，如果x0是最优解，输出x0，停，否则到步3；步3:按某一改进准则，将一个非基变量转变为基变量，而将一个基变量转变为非基变量，求一个更好的基本可行解。这相当于交换B与N的一个列，同样可用高斯—约当消去法，运算可以通过单纯形表上的所谓“转轴运算”实现。21:21:47MCM21设B为一组非退化的可行基，x0=（B-1b，0）为其对应的基本可行解。现在，我们来讨论如何判别x0是否为最优解。为此，考察任一可行解BNxxx由Ax=b可得11BNxBbBNx代入目标函数，得到11()TTTTTBBNNBNBNZCxCxCBbCCBNx01()TTTNBNCxCCBNx(5.6)21:21:47MCM22定理5.3最优性判别定理令1TTNNBrCCBN（1）若rN≥0，则x0必为（5.3）的一个最优解。（2）记。若，rj0，则当B为非退化可行基时，x0必非最优解。21:21:47MCM23证明（1）若rN≥0，由于变量满足非负约束，必有xN≥0。于是，由（5.6）式知xR故x0为（5.3）的一个最优解。0TTzCxCx（2）（5.6）式给出了x处的目标值与x0处的目标值之间的联系。现设,且j≠j0仍令xj=0。由非退化假设，B－1b0，根据（5.5）式可知，当且充分小时，仍有xB0。此时对应的x仍为可行解，但由（5.6），其目标函数值：00,jrjN00jx00110TTTTBjjBzCxCBbrxCBbCx故x0必非最优解。21:21:47MCM24定理5.3不仅给出了判别一个基本可行解是否为最优解的准则，而且在x0非最优解时还指出了一条改进它的途径。由于rN在判别现行基本可行解是否为最优解时起了重要作用，所以rN被称为x0处的检验向量，而rj(j∈N)则被称为非基变量xj的检验数。有趣的是上述过程完全可以在以下的单纯形表上进行。先将CT、A、b及数0写在一个矩阵中，将此矩阵看成一张数表，在此表上用高斯—约当消去法解方程组Ax=b0TCAb高斯-约当消去法（第一行不变）110TTBNCCIBNBb21:21:47MCM25利用单位矩阵I消第一行的为零向量，则被消成，而0则被消成。将消去后的行向量写到最后一行，删去原来的第一行，得到一张被称为单纯型表的表格：TBCTNC1TTNBNCCBNr10TBCBbZ表5.1xBxNIB－1NB－1b0rN－Z021:21:47MCM26表格（5.1）以极为简洁明了的方式表达了我们需要的全部信息。从其中I所在的m行可以看出哪些变量是基变量并可直接读出对应的基本可行解x0=（B-1b，0）。其最后一行又给出了非基变量的检验数及x0处目标函数值的相反数。现在，我们以例5.1为例，来看一下单纯形法是如何工作的。例5.1的标准形式为（5.4），容易看出它的一个初始基B=I（以x3、x4、x5为基变量），且CB已经为零，故我们已有了一张初始的单纯形表(表5.2)21:21:47MCM27表5.2x1X2x3x4x5基变量x3②110010x4110108x5010017rj－4－30000x0=(0,0,10,8,7)Tz0=CTx0=0rN=(r1,r2)=(－4，－3)21:21:47MCM28由于存在着负的检验数，且x0非退化，故x0非最优解。r1，r2均为负，x1，x2增大（进基）均能改进目标函数值。例如，取x1进基，仍令x2=0（x2仍为非基变量），此时由（5.5）式及（5.6）式有3141510287xxxxx