LinearProgramming第一章线性规划问题概述幻灯片.pptVIP

为了便于求解线性规划，有必要化线性规划成一定形式，即为下面的标准形式： 求一组变量 因为一般形式的线性规划问题都能化成标准形式（后面介绍），因此只要会求解标准形式的线性规划问题，就会求解一般形式的线性规划问题了。 下面介绍几种形式的标准线性规划[SLP]问题。 1.缩写形式： 矩阵形式： 注：向量非负，代表向量的各分量非负 3.向量形式： 二 化线性规划问题为标准形式： 第二 若约束条件中出现线性不等式 则可能转化为求目标参数 转换方法： 第一 若是求目标函数 第四 下面根据这些方法来做几个实例： 例8 将下面的线性规划问题标准化： §1.3线性规划的基本性质 一 两个变量线性规划问题的图解法： 我们先对二维的简单线性规划问题利用图解法进行求解。从图解法的几何直观可以启发我们的思维，探寻线性规划的一些基本性质。 例9：利用图解法求解下面线性规划问题： 解：在平面上取一个直角坐标系，他的两个坐标是 首先找出平面上满足约束条件的点。 当目标函数取某一 值h时。 令h=0，得直线 目标函数的值为0 再令h=2,6,7.得另外三条直线，其上点分别对应目标值2，6，7，因此把 叫做目标函数的等值线。当参数h变化时，就得到一族平行直线，他们形象的描绘了目标函数的变化状态。 平面上满足约束条件的点为上图中的一个凸多边形。表明原线性规划问题的目标函数只能在这个凸多边形（含边界）上取值，那么求解线性规划问题就是如何从这个凸多边形上求出使目标函数达最大值的关系。 为此，我们先看看目标函数在凸多边形上取值的变化性能。 当h由小（大）变大（小）时，我们来观察等值线在凸多边形上的变化情形。取等值线的正（负）法向量，其方向指向目标参数值增大（减小）的方向。当h由小（大）变大（小）时，直线 沿（负）法方向平行移动，目标参数值不断增大。这样就可以看到，对于凸多边形 目标参数在0~7之间取值，且： 相交时，目标参数值达到最大值7，如果等值线继续沿法方向移动，将离开这个凸多边形。不满足约束条件。于是知这个线性规划的最优解为 二 线性规划的基本性质： 若将上面例9改求目标参数 约束条件不变，那这整个问题就是：一个是在凸多边形 的极大，另一个则是在同一凸多边形上求同一目标参数的极小，由点面的分析知，目标参数在凸多边形顶点 这个事实就是线性规划的一个基本性质，如果线性规划有最优解，必然在凸多边形（或凸多面体）的顶点上达到最优，下一章我们将证明这一性质。 当求解线性规划问题时，图解法给人们提供了直观的思想，求解线性规划的单体形法是以解空间的凸多面体某一顶点开始进行替代，直到求出达到极值的顶点（如果问题有最优解）。 这个目标参数也在凸多边形顶点 解：画出由约束条件决定的4个 半平面的交集K，这是一个无界 的凸多边形。作目标函数的等值 线 方向 等值线可以无限制的减小，也就是问题最优值是负无 下面在举几个例子说明怎样用图解法求线性规划问题的解。 例10.求 使目标函数 穷大，或者说函数 最大化：目标函数等值线沿法向移动，最小化，沿负法向移动。 例11 使 约束条件决定的图形是 图中凸多边形OBAC 做等值直线束 沿正法方向 再移动就离开K了，所以线段AB上的点都使 解：如图所示：四个约束条件 决定的半平面没有相交部分即问题没有可行解。 综上可见：两个变量的线性规划问题可能有以下四种情形 1.有唯一最优解 2.有最优解，但不唯一 3.有可行解，但是没有最优解。 4. 没有可行解。 对于一般问题也有上述论述。 最 优 化 方 法 各位同学：欢迎大家选修“最优化方法”课程！ 本课程为工科硕士研究生学位基础课程，课程采用平时考核和期末考试综合评定成绩的方法结业。 本课程课件为非出版物、非公共用品，敬请不要商量拷贝课件事宜！ 建议购买相关教材或者借阅参考书，适当做听课笔记！ 线性规划 教学大纲 一、本课程教学目的是使同学们从理论上，应用上掌握运筹学的一个 基本分枝---线性规划。 二 、基本要求： （1）通过学习，熟悉线性规划的基本概念；能熟练的运用线性规划解决实际问题，包括建立模型。求解和解后的经济分析基本方法。 （2）从数学理论上完善的了解线性规划基本原理，以及该课题新近的发展动态。