线性规划模型.ppt

《线性规划模型.ppt》由会员分享，可在线阅读，更多相关《线性规划模型.ppt（143页珍藏版）》请在麦多课文档分享上搜索。

1、第三章 线性规划模型 y2、找出问题中所有的限制或约束，写出未知变量的线性方程组或线性不等式组；一、线性规划模型1、找出 待定的未知变量 （又称为 决策变量 决策者自己可以控制的变量），并且用符号表示；3、找出模型的目标函数：是以函数形式表示的决策者追求的目标写出未知变量的线性方程或线性不等式（一）建立线性规划模型有三个基本步骤：例 （ 配料问题 ）某铸造厂生产铸件，每件需要 20千克铅， 24千克铜和 30千克铁。现有四种矿石可供选购，它们每 10千克含有成分 的质量（千克）和价格（元）如图。问：对每个铸件来说，每种矿石各应该选购多少，可以使 总费用最少 ？试建立数学模型。分析和建立模型（

2、1）确定决策变量： 设 为第 i种矿石的选取的数量（单位 10kg） ； （ 2）确定目标函数 ：目标应该是使得总费用最小，即达到最小；（ 3） 确定约束条件 ：选定的四种矿石的数量应该满足铸件对三种成分的需求量，并且矿石数量应该是非负的，即每件需要 20千克铅， 24千克铜和 30千克铁综合以上分析，得到配料问题的数学模型为：受 约束于（二）线性规划模型的结构具有如下特性（ 1）目标函数是决策变量 的线性函数；（ 2）约束条件是决策变量 的线性等式或不等式；具有以上结构特点的模型就是线性规划模型，记为 LP（ Linear Programming）， 具有以下一般形式：（三）线性规划的标准模

3、型由于目标函数既可以是实现最大化，也可以是实现最小化，约束条件可以是等式，也可以是不等式，决策变量为非负或不受限制，这么复杂的情况，一定会给模型的求解带来不便，为此引入标准形式标准形式（四）线性规划数学模型标准形式的特点2、约束条件均为线性；3、决策变量及 方程右端非负 。线性规划数学模型标准形式可以有向量形式表示：1、目标函数为最大化类型（有的书上为最小化）；1、如果目标函数为最小化问题，则将目标函数两边乘以 “ -1” ；2、如果约束方程右端为负，在该方程两端同乘以 “ -1” ；如果所建的模型不符合标准形式，则可以用适当方法化为标准形式，主要有：3、如果约束为 “ ” ，则可以增加一个变

4、量 ，在左端加上 ，这种变量称为 剩余变量 ；4、如果约束为 “ ” ，则可以增加一个变量 ，在右 端加上 ，这种变量要求非负，在线性规划中均称为 松驰变量 ；5、如果某决策变量 无符号限制，则将每个 换成例： 将下列线性规划模型化为标准形式化成标准形式为：（一）基本概念：1、 可行解 ：所有满足约束条件 的解。2、 可行域 ：所有可行解组成的集合。4、 最优值 ：对应于最优解的目标函数值。3、 最优解 ：使得目标函数达到最优值的可行解。二、线性规划问题的解及单纯形法（解法）5、 基 ：约束方程组 的系数矩阵为 阶的矩阵 则称 A的 任意一个 阶的非奇异 子矩阵 B为线性规划的一个 基 。6、

5、 基向量 ：组成 基 B的 列向量 称为 基向量 。7、 基变量 ：基向量 对应的变量 称为 基变量 ，基变量以外的变量称为 非基变量 。9、 基可行解 ：满足非负条件 的基本解。10、 可行基 ：基可行解对应的基。11、 基本最优解 ：使目标函数达到最大值的基可行解。12、 最优基 ：基本最优解对应的基。8、 基本解： 在 中，令 非基变量全部为 0，求出 的一个解 X， 称为 基本解 。1、 基本思想 ： 首先 找出一个 基可行解 ， 然后 根据 某种最优性准则 判断该解是否为最优，如果最优，则结束；否则利用某种迭代规则 寻找下一个基可行解，并且使下一个基可行解的 目标函数值有所改变，反复

6、多次， 直到找出最优解，或判断出原问题无最优解 。（二）单纯形法为了确定 初始 基可行解 ，需要先找出初始可行基。其方法是：观察约束方程组系数矩阵 ，若其中有 子块为 m阶单位矩阵 ，则可将其选为初始可行基；否则，可采用所谓 人工变量法寻找初始可行基 。（ 1）、确定 初始 基可行解并且计算相应的目标函数值2、计算步骤 （ 3步）若 的前 m列为单位阵（ 作为基 ），则约束方程 可化为 为 基变量 ，为 非基变量令 非基变量 即得 初始 基可行解 。 将方程组（ 1）代入目标函数故对应于基可行解 的目标函数值 ，于是 原线性规划模型等价于此等价模型称为原线性规划的 典式 ，其中 称为 基本可行

7、解 的 检验数（ 2）、根据检验数 进行最优性检验与解的判断。定理 ：若线性规划的基可行解 对应的典式为（ 1）并且检验数为 、 当存在某个检验数 时，并且典式（ 1）中所有 时， 线性规划无有限最优解 。 则 、 当 时， 是线性规划的有限最优解； 、 当存在检验数 且典式（ 1）中有些 ，这时采用迭代法 实现基可行解的转移。当初始基可行解 不是最优解，并且不能判别无有限最优解时，需要另找一个 基可行解 ， 并使相应目标函数值增大 ，（即要对原可行基换一个列向量）。为此需要确定 进基变量 和 出基变量的规则。（ 3） 通过换基迭代，实现基可行解的转移 进基变量的规则 ：当某个 时，增加 可以使得目标函数值增加，故将 作为进基变量。当有两个以上的 时，一般选择最大 对应的变量 为进基变量 出基变量的规则：为了使得目标函数值增加得较快，进基变量 的取值使得目标函数值尽可能的大，出基变量取哪一个，通过 准则来确定。准则