《运筹学教程 第2版 教学课件 ppt 作者 邱菀华 冯允成 第2章（修改后）》由会员分享，可在线阅读，更多相关《运筹学教程 第2版 教学课件 ppt 作者 邱菀华 冯允成 第2章（修改后）（59页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性规划,2.1 线性规划的基本概念 2.2 线性规划的图解法 2.3 线性规划的标准形式 2.4 线性规划的解和基本定理 2.5 单纯形法,2.1 线性规划的基本概念,线性规划的数学模型为：求一组变量 的值，使之满足线性约束条件 (2-4) 并使线性目标函数 （2-5） 达到极值（最大或最小）。其中 为已知常数。,式中,矩阵形式,浓缩形式,（2-6）,在经济和生产活动中，线性规划是在有限资源（人力、物力、财力）限制条件下，寻求获得最大收益或支付最低成本的可行方案的一种数学方法。其中收益、成本和限制条件均为变量的线性表达式，故称为线性规划问题，简记为LP（Linear Programm
2、ing）问题。,2.2线性规划的图解法,当线性规划问题的决策变量个数少于时，可用图解法求解。 图解法是利用几何图形来求解线性规划问题的一种方法，它将几何图形和线性规划问题中的基本概念联系起来，直观明了，有助于人们理解线性规划问题的基本思想和解题思路。 本节主要介绍两个决策变量的线性规划问题的图解法。,1线性不等式的图像表示 （1）单个不等式的图像 对于一般情况，令f（x，y）axbyc式中， a、b、c为实常数。若 ）f（x，y），则其图像为一条直线，记为。 ）f（x，y），则其图像是以为边界的一个半平面。 ）f（x，y），则其图像是以为边界的另一个半平面。,当f（x，y）为非线性函数时，也有
3、类似情况，不同之处在于它们的边界是曲线f（x，y），而不是直线。 如何判定两个半平面中哪一个是f（x，y）的图像，哪一个是f（x，y）的图像呢？ 只要任取不在上的点（x，y）（为简化计算，x、y越简单越好，若原点（，）不在上，则取原点计算起来最简便）代入f（x，y）中，若有f（x，y），则点（x，y）所在的半平面为f（x，y）的图像，另一半平面为f（x，y）的图像。否则（x，y）所在的半平面为f（x，y）的图像，另一半平面为f（x，y）的图像。,（2）线性不等式组的图像 在线性规划中，称约束条件的图像为可行域。可行域中的点称为可行点或可行解。 线性不等式组的图像是一个“凸”的图形。这种图形的基
4、本特点是：在图形区域内任取两点，则连接这两点的线段上的所有点都在图形范围内。具有这种特征的图形称为凸集（或凸多边形、凸多面体）。,2目标函数等值线 目标函数P是一个依（x，y）而变化的变量。P值一旦确定，它的图像就是一条直线。P取一系列不同的值，则得到一组（或族）互相平行的直线，这些直线称为目标函数等值线。等值线就是位于该直线上的所有点都使目标函数取相等的值的直线。,3线性规划的图解法 所谓用图解法求解线性规划问题，就是寻求与其可行域有公共点的具有极值的目标函数等值线，这些公共点就是线性规划的最优解，此目标等值线的目标值即为线性规划的最优值。,把线性规划的图解法归结为以下三个步骤： ）画出约束
5、条件的图像可行域。 ）画出目标函数的图像等值线。 ）确定与可行域有公共点，且具有极值的目标 函数等值线，从而得到最优解、值。,例：用图解法求解线性规划问题,按照图解法步骤画出上图。 从中可以看出，该线性规划问题的最优解为 （x*,y*）（12,6） 它与可行域顶点B相对应，最优目标值P*=132。,从几何图直观上看到，线性规划问题如果存在最优解，则可能存在唯一最优解，也可能存在无穷多个最优解，并且最优解一定可以从可行域顶点中找到。此即为线性规划求解算法的核心思想。这一结论的正确性在n维空间也同样存在。,2.3 线性规划的标准形式,为了讨论和求解问题方便，人为的规定一种形式作为标准形式，不同形式
6、的线性规划问题的数学模型，总可以等价地转化成这种标准形式：,式中， 均为实常数； （j，n）为待求变量。且不失一般性，总可假定 （i，m）。 矩阵形式为：,线性规划问题的标准形式具有以下特点： 目标函数求最小值，约束条件都化为等式，决策变量都非负，右端项全非负。,将线性规划模型转化为标准形式： 1.化不等式约束为等式约束 2.化自由变量为非负变量 3.化求目标函数最大值问题为求最小值问题 任意形式的线性规划与标准形式的线性规划之间的差异不 外乎以上三种情况。因此，任何线性规划问题都可以化为标准形式的线性规划问题来求解。线性规划的求解问题便归结为标准形式的线性规划的求解问题。这就大大降低了探求线
7、性规划解法的复杂性。,2.4线性规划的解和基本定理,1.线性规划的解 （）凸集和基础可行解的定义 定义 连接 空间中两点 和 的线段是点集合 x|x （） ，式中，x、 、 均为向量 x 单个英文字母x，y，a，b，以及标号在右上方的字母符号，如 ， ， ， 等表示向量，标号在右下方的字母符号，如x1，x2，a12，a23等表示向量的分量或矩阵中的元素。,定义 设C ， C，C，若x （） C，则称C为凸集。 根据定义和定义可以看出，凸集中任意两个相异的点，连接该两点的线段仍属于该凸集。且其上每一点（不包括端点）均可由这两点和参数，唯一确定。但是，是不是凸集上所有的点均可由凸集中两个不相同于它
8、的相异点和参数（，）唯一确定？显然这是不一定的。 定义 凸集C中的一点x称为C的极点，若不存在C中另两个相异点 、 有下式成立 x （） ， （，）,定义 若x是 、，的线性组合x1 2 k 其中i（i，k）为已知实常数，k。当i，且kii时，我们称x是 ， ， 的凸组合。 显然，在有界闭凸集合中的任何一点，总可表示成它的极点的凸组合。,（）基础可行解 记n维向量x的非零分量对应下标组成的集合为J（x）i| ，i，n 定义 若xR，且 iJ（x）是线性无关向量组，则x称为（LP）问题的基础可行解。,（）旋转运算和基础解 ）旋转运算 旋转运算的步骤： 在线性方程组中选择旋转项asi（），此时xi
9、叫做旋转变量。 用/asi乘第s个方程的两端，以得到的新方程代替远方程组中的第s个方程。 对于j，m，js的每个j，用用（aji）乘以第s个方程的各项，然后加到第j个方程上，得到新的第j（j，m，js）个方程。,）基础解 在第一个方程中选择一个旋转变量并作旋转运算，再在第二个方程中选择与第一个旋转变量相异的变量作旋转变换，进行旋转运算，依次做下去，至多进行m次旋转运算，就可得到一个简化了的同解方程组，它与原方程组等价。在此过程中必须注意： 逐个方程选择旋转变量，不要遗漏。 一个方程只能选一个旋转变量，且不能与其他方程的旋转变量相同。若线性方程组的系数矩阵A的秩为r（rm）。不失一般性，可设mn
10、，且恰好前r个方程中的前r个变量被选中为旋转变量。,定义 对于方程组的一个正规等价方程组，取全部非基础变量 则每个基础变量的取值等于所在方程的右端常数项 如此得到的一个特解 称为线性方程组的一个基础解。,基础解具有如下性质： 对于同一组基础变量，方程组的基础解是唯一的。 一个线性方程组的基础解的个数是有限的，至多有 个基础解（ 即是从n个变量中取出r个变量的组合数）。 每一个基础解的非零分量的个数是有限的，不多于r（rm）。,）基础解的转换 对于同一个线性方程组，选择不同的旋转项，可得到不同的正规等价方程组。每个正规等价方程组，对应唯一确定的基础解。 如何从一个已知的基础解求得另一个基础解，即
11、如何实现基础解的转换？只要对现有的正规等价方程组继续进行旋转运算就可以 。 对于正规等价方程组，按照公式每进行一次旋转运算，就是一个非基础变量取代一个基础变量的过程。假如需要替换的基础变量有多个，继续利用此法逐一替换即可 。,）基础解和基础可行解的关系 由线性代数知识不难推出，基础变量对应的线性方程组的系数矩阵列是线性无关的。因此，线性方程组的满足非负条件的基础解，就是（LP）问题的基础可行解。 可见，（LP）问题基础可行解，可以通过旋转运算求其约束方程组的基础解的方法得到。当这些基础解的所有分量都大于或等于时，就是（LP）问题的基础可行解。,与线性方程组基础解的性质相类似，（LP）问题的基础
12、可行解具有如下性质： （LP）问题的基础可行解的个数是有限的，它至多有个。 每个基础可行解的非零分量个数至多等于r，因为基础变量只有r个。它对应的系数列向量组成一个线性无关极大组。,2线性规划的基本性质 定理2-1 （LP）问题可行域中的一点为极点的充分必要条件是，它是（LP）问题的基础可行解。 定理2-2 若（LP）问题存在最优解，则至少有一个最优解x*是（LP）问题的基础可行解。 定理2-3 假如（LP）问题存在可行解，则一定存在基础可行解。,2.5 单纯形法,用单纯形法求解（LP）问题通常分为两个主要阶段：第一阶段寻求（LP）的一个基础可行解，或断定（LP）无可行解； 第二阶段改善已求出
13、的基础可行解的目标值，逐步达到最优解，或断定（LP）无最优解。 这两个阶段都是用单纯形法处理的。,.单纯形算法 单纯形算法的计算步骤如下： 判断现有基础可行解是否是最优解。若是，则（LP）问题的所有可行解相应的目标值均满足zz，计算结束；若不是最优解，则继续下一步。 通过旋转运算，使现有基础变量中的某一个化为非基础变量，同时使现有某个非基础变量化为基础变量。由此得到一个新的改善了目标值的基础可行解。记它的目标值为z，且zz。再以新的基础可行解为起点，继续进行上一个步骤。,单纯形算法就是在以上两个步骤间反复迭代，直至求得最优解。 在迭代过程中必须解决以下几个问题： 判断一个基础可行解是否是最优解
14、的条件是什么？ 如何使求得的新的基础可行解的目标值比原基础可行解的目标值小？ 如何保证在旋转运算的过程中常数项非负？,（）单纯形法的最优解判别条件 把求解线性规划问题转换成寻求线性方程组的一个解 并使所有x满足非负条件和目标值z最小。 在单纯形算法中，上述最优解判别条件就是算法的停止条件之一。即只要单纯形表中存在 ，就继续进行旋转运算寻求新的、目标有所改善的基础可行解。,（）改善现有基础可行解的途径 如果最优解判别条件不能满足，即 中有负数，则应利用旋转变换运算求另一目标较小的基础可行解。 在迭代过程中，只要选负判别数列的非基础变量当进基变量，就可保证新基础可行解的目标值减小。,（）出基变量的
15、选择 解决这一问题的唯一准则是：选择的出基变量xp经 旋转运算后得到的所有常数项必须保证非负性。,单纯形法有以下主要结论： 假定 是（LP）问题的一个已知的基础可行解，相应的目标值为 ，可能出现如下几种情况： 若判别数 ，（jr+1，n），则 是（LP）问题的最优解， 为最优值，算法结束。 若 中，对某个 所有的 （i，r），则（LP）问题无最优解，目标函数值z，算法结束。 若 中，对某个 至少有一个 ， 则令,选定 作旋转项进行一次旋转运算，使xq变成基础变量，xp变成非基础变量。设旋转运算后得到的新基础可行解为x，目标值为zz。再对x、z重复进行上述三种情况的分析，直至算法结束。 实际运算时若判别数中不止一个为负，则一般选择其中最小者所对应的非基变量进基。 由线性规划的基本性质可知，线性规划的基础可行解的个
