运筹学-1复习.doc

第1章 线性规划 当数学规划问题的目标函数（对要达到的目标的数学描述）和约束条件（资源的限制等）中出现的所有函数都是线性函数的时候称为线性规划。 1.1 一般线性规划问题的数学模型 线性规划问题的一般形式为： (或求最小) 向量形式 引进向量 ，，， 线性规划问题可以改写为向量形式 （或） 向量-矩阵形式 再引进矩阵 线性规划问题可以表示为向量-矩阵形式： s.t.（或） 应用单纯形法的标准形式： 在标准形式中约束条件都是等式。 向量-矩阵形式的标准形式是： s.t. 3.非标准线性规划问题的标准化 （1）如果某个约束为： 可以在不等式的左边增加一个变量，则约束可改写为： （2）如果某个约束为： 在不等式的左边减去一个变量，则约束可改写为： 这里引进的变量和称为松弛变量。 （3）如果问题是求最小值，则引进，化为求最大问题。 （4）如果对某变量没有非负约束，则引进两个非负变量， ，令代入约束条件中。 4.线性规划问题的解 可行解：线性规划的满足所有约束条件的解称为可行解，全部可行解的集合称为可行域。 最优解：使得目标函数达到最大的可行解称为最优解。 1.2 线性规划问题的图解法 图解法是一种简单直观的解线性规划问题的方法。它适用于含有两个变量的模型。虽然实际的线性规划问题很少只有两个变量的情况，但它有助于理解线性规划问题的解的基本性质，这种解法的思想有助于学习其它解法。因此，学好图解法是学习线性规划的基础。 下面以例1-1中的生产计划问题为例介绍图解法。 【例1-4】用图解法解例1-1中的生产计划问题： 图解法的步骤： 第一步：确定可行域，即确定满足所有约束条件的点的图形范围。为此需分析约束条件的几何意义。将看做平面上的点，那么变量的非负约束，表示第一象限的所有点。下面分析约束条件，直线将平面分为两个 部分直线下面的点，直线上面的点，因此约束条件， 表示图1-2中阴影三角形中的所有点。以此类推，4项约束可以与轴，轴构成4个这样的三角形，它们在平面上的交集称为可行解区域，简称可行域。由图1-3的阴影部分给出。 图1-2 例1-1的可行域 图1-3 例1-1的可行解 第二步：绘制目标函数的等值线，在可行域上寻找最优解，即 在可行域上求一个使目标函数最大的可行解。 做法是先找出的点,即满足 的点，这些点构成一条直线。我们还可以画一系列的与它平行的直线： 这是一系列的平行于的直线，称为等值线。等值线离原点越远，值越大。 可以先画出任意一条等值线，例如 然后将它沿着它的法线方向向上移动，直到直线与可行域只有一个交点或一个相交的线段，再向上移动就离开了可行域，就得到了线性规划问题的一个最优解或无限多个可行解。 对这个例子，这条直线就是。它是通过顶点(4，2)的的平行线。 点，,，即例1-1的线性规划问题的唯一解。 这个问题的最优解是唯一的，除此以外还可能有以下几种情况： 由图解法可以看出线性规划问题解的几种情况：除这个例子有唯一最优解的情况外还有以下几种情况： 有无穷多个解 如果每件产品乙可获利4元，则目标函数改为 这时等值线，行解区域的一条边平行，因此线段 上的点都是这个线性规划问题的解，即这个线性规划问题有无穷多解。 无最优解 线性规划问题 无最优解，见图。1-7 无可行解 线性规划问题 没有可行解，见图1-8。 通过图解法可以直观地看到以下结论： 线性规划的可行域是个凸集。 如果线性规划问题有最优解，最优解一定可以在可行域的某个顶点上找到。 由此想到的一种解线性规划问题的思路：先找出可行域的任一个点，计算这个顶点的目标函数值，比较相邻顶点的目标函数值看是否更大，直到找到线性规划问题的最优解。 可以证明顶点可行解与最优解的关系如下： 任意具有可行解与有界可行域的线性规划问题，一定具有顶点可行解和至少一个最优解，而且最优的顶点可行解一定是最优解。所以，如果一个问题有唯一最优解它一定是顶点可行解；如果一个问题有多个最优解，那么其中至少有两个是顶点可行解。 (Hillier,Lieberman:线性规划导论（第9版），P.32。) 1.3 线性规划的基本定理 基、基解和基可行解 基 设线性规划问题中的系数矩阵中（一般线性规划问题中，变量的个数都大于方程的个数），，矩阵是矩阵的一个满秩阶子矩阵，则称矩阵是线性规划问题的一个基。 假设 满秩，则矩阵中的每一个列向量称为基向量，与它对应的变量称为基变量，。线性规划中除个基变量以外的其他变量称为非基变量。 基解 在线性方程组中令所有非基变量为0，即令 这时线性方程组的行列式不为0，依据克莱姆规则，线性方程组有唯一解 这个解加上取0的非基变量，扩充为线性规划问题的一个解 称为线性