运筹学-1复习.doc

MATLAB基础及在运筹学中的应用第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的线性规划问题的唯一解这个问题的最优解是唯一的，除此以外还可能有以下几种情况：由图解法可以看出线性规划问题解的几种情况：除这个例子有唯一最优解的情况外还有以下几种情况：（1） 有无穷多个解 如果每件产品乙可获利4元，则目标函数改为这时等值线，行解区域的一条边平行，因此线段上的点都是这个线性规划问题的解，即这个线性规划问题有无穷多解2） 无最优解 线性规划问题无最优解，见图1-7（3） 无可行解 线性规划问题没有可行解，见图1-8通过图解法可以直观地看到以下结论：（1） 线性规划的可行域是个凸集2） 如果线性规划问题有最优解，最优解一定可以在可行域的某个顶点上找到3） 由此想到的一种解线性规划问题的思路：先找出可行域的任一个点，计算这个顶点的目标函数值，比较相邻顶点的目标函数值看是否更大，直到找到线性规划问题的最优解。

可以证明顶点可行解与最优解的关系如下：任意具有可行解与有界可行域的线性规划问题，一定具有顶点可行解和至少一个最优解，而且最优的顶点可行解一定是最优解所以，如果一个问题有唯一最优解它一定是顶点可行解；如果一个问题有多个最优解，那么其中至少有两个是顶点可行解Hillier,&Lieberman:线性规划导论（第9版），P.32)1.3 线性规划的基本定理基、基解和基可行解基 设线性规划问题中的系数矩阵中（一般线性规划问题中，变量的个数都大于方程的个数），，矩阵是矩阵的一个满秩阶子矩阵，则称矩阵是线性规划问题的一个基假设满秩，则矩阵中的每一个列向量称为基向量，与它对应的变量称为基变量，线性规划中除个基变量以外的其他变量称为非基变量基解 性方程组中令所有非基变量为0，即令这时线性方程组的行列式不为0，依据克莱姆规则，线性方程组有唯一解这个解加上取0的非基变量，扩充为线性规划问题的一个解称为线性规划问题的基解基可行解 满足非负约束的基解称为基可行解对应于基可行解的基称为可行基线性规划的基本定理定理1-1.如果线性规划问题存在可行解，则可行域是凸集定理1-2线性规划问题的任一个基可行解必对应于可行域的一个顶点。

定理1-3 如果线性规划的可行域有界，则目标函数至少在可行域的一个顶点上达到最大值(或最小值)定理1-4 如果线性规划的可行域无界，则问题可能无最优解，如果有最优解，目标函数最大值也一定在可行域的一个顶点上达到 单纯形法的基本思路是：先找出一个初始基本可行解，它对应可行域的一个顶点，据一定规则判断其是否最优解，如果是最优解，问题就解决了；如果不是最优解，则转换到另一顶点，并使目标函数值增大；如此下去，直到找到某一最优解为止单纯形法的求解步骤 单纯形法是解线性规划问题的系统化的方法单纯形法的第一步是求出可行域的一个顶点，作为求解的开始单纯形法的第二步是沿着可行域的棱边由一个顶点过渡到另一个顶点，一般在一个顶点上有多个棱边可供选择，Dantzig的单纯形法提供了在多个棱边中选出一个保证使目标函数增大的棱边，沿这个棱边到一个新的顶点使目标函数增大如果从一个顶点出发，沿它的多个棱边的任何一个得到新的顶点都不会使目标函数增大，我们就得到了最优解这是顶点可行解的一个重要性质：如果一个顶点可行解没有相邻的顶点可行解比它更优（目标函数更大），那么这个顶点可行解就是最优解（如果问题有最优解的话，例如由可行域有界保证）。

以上对于例1-1的线性规划问题它的标准形式为结合这个例子说明单纯形法的解题步骤：第1步：求一个初始基可行解，并制作初始单纯形表对应于初始基可行解,基变量是，变量，为非基变量,将目标函数改写为可以得到表1：初始表 基 12 8 16 12 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 1 Z 0 -2 -3 0 0 0 0第2步：检验此基本可行解是否为最优解，即检验各非基变量在Z行的对应的系数是否有取负值的，如果非基变量在Z行的对应的系数全都大于等于0，则已经得到最优解，计算停止。

否则进行下一步第3步：确定入基变量和出基变量 取非基变量在Z行的绝对值最大的负数对应的非基变量为入基变量；计算入基变量所在列的正系数与列相应的系数的比，列相应的系数做分子，比值记为，记在表的最右列，的最小值对应的基变量为出基变量表1：初始表 基 12 8 16 12 2 2 1 0 0 0 12/2=6 1 2 0 1 0 0 8/2=4 4 0 0 0 1 0 - 0 [4] 0 0 0 1 12/4=3 Z 0 -2 -3 0 0 0 0如果入基变量所在列的系数全部小于等于0，则为无界解，计算停止。

第3步：用消元法，得到新的基可行解 将入基变量所在列的系数化为单位列向量（[ ]中的数常称为主元，将它化为1，其它都化为0） 基 6 2 16 3 2 0 1 0 0 -0.5 6/2=31 0 0 1 0 -0.5 2/1=2 4 0 0 0 1 0 16/4=4 0 1 0 0 0 0.25 - Z 9 -2 0 0 0 0 +0.75返回第2步，进行迭代表2 基 6 2 16 3 2 0 1 0 0 -0.5 6/2=3[1] 0 0 1 0 -0.5 2/1=2 4 0 0 0 1 0 16/4=4 0 1 0 0 0 0.25 - Z 9 -2 0 0。