06第6章 数学规划模型.docx

PAGE PAGE 150 第 6 章 数学规划模型 现实世界中广泛存在着一类所谓的优化问题，在一系列既定条件的限制下，如何使所关注的预定目标达到最优，这就是数学规划模型。本章介绍数学规划中的线性规划、整数规划和非线性规划。另外介绍多目标规划的序贯解法。 线性规划 线性规划（Linear Programming 简记 LP）是运筹学的一个重要分支。自从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实际中的应用日益广泛。 线性规划的基本概念 线性规划的一般模型 线性规划模型的一般形式为  max(min) z ? ?n c x ； j j j ?1  (6.1) ??n ?s.t. ? ? ??j ?1 ? ?  a x ij j ? (?, ?)b , i ? 1,2, , m, , m, , n.  (6.2) 也可以表示为矩阵形式 x ? 0, j ? 1,2, j 向量形式 max(min) z ? cT x ； ?s.t. ? Ax ? (?, ?)b, ? ? x ? 0. max(min) z ? cT x ； ??n ?s.t. ? p j x j ? ? j ?1 ? (?, ?)b, c , c , , c , c , , c ]T ， 1 2 n , , b ]T ，称 2 m j ? 1,2, , n ）， 上面的表达式中，式(6.1)称为目标函数，式(6.2)称为约束条件；其中 c ? [ 称其为价值向量（或目标向量）； x ? [x , x , , x ]T ，称其为决策向量；b ? [b , b , a ] , a ]T（ mj 其为资源向量；A ? (a ij ) m?n ，称其为约束条件的系数矩阵；p j ? [a 1 j , a , 2 j 称其为约束条件的系数向量。 从上面的模型可以看出，线性规划的目标函数可以是最大化问题，也可以是最小化问题； 约束条件有的是“ ? ”，有的是“ ? ”，也可以是“ ? ”。 在一些实际问题中决策变量可以是非负的，也可以是非正的，甚至可以是无约束（即可以取任何值）。为了便于研究，在此规定线性规划模型的标准型为 max z ? cT x ； (6.3) 线性规划解的概念 s.t. ? Ax ? b, ?? x ? 0. ?  (6.4) 线性规划所研究的内容是线性代数的应用和发展，属于线性不等式组理论，或者说是高维空间中凸多面体理论。其基本点就是在满足一定的约束条件下，使预定目标达到最优。 定义 6.1 对于线性规划模型 满足全部约束条件的决策向量x ? Rn称为可行解； 全部可行解构成的集合（它是n 维欧氏空间 Rn中的点集，而且是一个“凸多面体”）称为可行域； 使目标函数达到最优值（最大值或最小值，并且有界）的可行解称为最优解。 定理 6.1 当线性规划问题有最优解时，一定可以在可行域的某个顶点上取到。当有唯一解时，最优解就是可行域的某个顶点。当有无穷多个最优解时，其中至少有一个解是可行 域的一个顶点。 根据定理 6.1，线性规划模型的最优解有以下几种情况： 有最优解时，可能有唯一最优解，也可能有无穷多个最优解。如果最优解不唯一， 则最优解一定有无穷多个，不可能为有限个。最优解对应的目标函数值（最优值）均相等。 没有最优解时，也有两种情形。一是可行域为空集，即无可行解；二是可行域非空，但目标函数值无界（求最大时无上界，求最小时无下界）。 美国数学家 G. B. Dantzig 于 1947 年提出了求解线性规划的单纯形法，给出了一个在凸多面体的顶点中有效地寻求最优解的迭代策略。 如果将凸多面体顶点所对应的可行解称为基本可行解，单纯形法的基本思想就是：先找 出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一 改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。即使问题无最优解也可用此法判别。 单纯形的详细计算步骤我们这里就不赘述了，有兴趣的读者可以参阅运筹学的有关书籍。 MATLAB 求解线性规划 MATLAB 优化工具箱中提供了一个求解线性规划的基本函数linprog。这个函数集中了求解线性规划的常用算法，如单纯形法和内点法等，会根据问题的规模或用户的指定选择算法进行求解。 MATLAB 中线性规划模型的标准型为 min z ? cTx ， ? A ? x ? b, ?s.t. ? Aeq ? x ? beq, ? ??LB ? x ? UB. ? 函数 linprog 的调用格式为 [x,z]=linprog(c,A,b,Aeq,beq,