您所在位置：网站首页 > 高等教育 > 大学课件线性规划的基本定理ppt课件

线性规划的基本定理ppt课件

32页

卖家[上传人]：资****亨

文档编号：133550778

上传时间：2020-05-28

文档格式：PPT

文档大小：225.50KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

35 金贝

/ 32 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、 3 线性规划的基本定理 1标准形式及图解法1 1标准形式矩阵表示 3 线性规划的基本性质其中A是m n矩阵 c是n维行向量 b是m维列向量评注为计算需要一般假设b 0 否则可在方程两端乘以 1 即可化为非负 3 线性规划的基本性质任意非标准形式均可划为标准形式如引入松弛变量xn 1 xn 2 xn m 则有 3 线性规划的基本性质若某变量xj无非负限制则引入xj xj xj xj xj 0若有上下界限制比如xj lj 令xj xj lj 有xj 0 3 线性规划的基本性质 1 2 图解法当自变量个数少于3时我们可以用较简便的方法求解 3 线性规划的基本性质 Min3x 2 5ys t 2x 4y 403x 2y 50 x y 0 例如考虑食谱问题 3 线性规划的基本性质可行区域的极点 0 25 15 2 5 最优解 20 0 2基本性质2 1线性规划的可行域 3 线性规划的基本性质定理3 1线性规划的可行域是凸集 2 2最优极点观察上例最优解在极点 15 2 5 达到我们现在来证明这一事实线性规划若存在最优解则最优解一定可在某极点上达到考察

2、线性规划的标准形式 3 2 3 线性规划的基本性质根据表示定理任意可行点x可表示为把x的表达式代入 3 2 得等价的线性规划 3 线性规划的基本性质于是问题简化成 3 线性规划的基本性质在 3 6 中令 3 线性规划的基本性质显然当时目标函数取极小值 3 线性规划的基本性质即 3 5 和 3 8 是 3 4 的最优解此时 2 若 3 2 存在有限最优解则目标数的最优值可在某极点达到 3 线性规划的基本性质定理3 2设线性规划 3 2 的可行域非空则 3最优基本可行解 3 线性规划的基本性质前面讨论知道们最优解可在极点达到而极点是一几何概念下面从代数的角度来考虑不失一般性设rank A m A B N B是m阶可逆的 3 线性规划的基本性质于是 Ax b可写为于是称为方程组Ax b的一个基本解 3 线性规划的基本性质定义3 1 为约束条件Ax b x 0的一个基本可行解 B称为可行基矩阵 3 线性规划的基本性质称为一组可行基且至少有一个分量为0 称基本可行解是退化的 3 线性规划的基本性质 3 线性规划的基本性质 3 线性规划的基本性质

3、容易知道基矩阵的个数是有限的因此基本解从而基本可行解的个数也是有限的不超过 3 线性规划的基本性质定理3 3令K x Ax b x 0 A是m n矩阵 r A m则K的极点集与Ax b x 0的基本可行解集合等价 3 线性规划的基本性质证明提纲 1 设x是K的极点则x是Ax b x 0的基本可行解 2 设x是Ax b x 0的基本可行解则x是K的极点 3 线性规划的基本性质 1 先证极点x的正分量所对应的A的列线性无关 3 线性规划的基本性质 3 线性规划的基本性质 3 线性规划的基本性质 2 设x是Ax b x 0的基本可行解记即 3 线性规划的基本性质总结线性规划存在最优解目标函数的最优值一定能在某极点上达到可行域K x Ax b x 0 的极点就是其基本可行解从而求线性规划的最优解只需要求出最优基本可行解即可 3 线性规划的基本性质 3 4基本可行解的存在问题 3 线性规划的基本性质定理3 4若Ax b x 0有可行解则一定存在基本可行解其中A是秩为m的m n矩阵否则我们通过如下步骤构造出一基本可行解 3 线性规划的基本性质 3 线性规划的基本性质

《线性规划的基本定理ppt课件》由会员资****亨分享，可在线阅读，更多相关《线性规划的基本定理ppt课件》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源