运筹学茹少峰课件1.ppt
《运筹学茹少峰课件1.ppt》由会员分享,可在线阅读,更多相关《运筹学茹少峰课件1.ppt(45页珍藏版)》请在三一文库上搜索。
1、第三章 线性规划的一般求解方法 单纯形法,它的一般形式为:,其中, , , 是已知数, 是待决策的变量。,一、线性规划问题的一般形式,一般情况下 m n , m , n 为正整数, 分别表示约束条件的个数和决策变量的个数,称为约束条件(Subject to)。 称为变量的非负约束条件。其余的变量可取正值、负值、或零值,称这样的变量为符号无限制变量或自由变量。 线性规划模型的特征是:一组决策变量 ,一组约束条件。一个目标函数。目标函数和约束条件都是线性的。,由前面一般形式可知,线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的;约束条件可以是“ ”形式、“”形式不等式,有的是
2、等式,决策变量有时有非负限制有时没有。这种多样性给讨论问题代来了不便。为了便于今后讨论,我们就要规定线性规划问题的标准型,二、线性规划问题的标准行式是什么? 如何将一个LP问题的一般形式转换为 标准形式? (1)、这里规定的标准形式为:,这里我们假设 bi 0 ( i = 1,2,m),否则两端同时乘以“-1”。,简记为:,用矩阵表示为:,用列向量表示为:,(2)为了把一般形式的LP变换为标准形式,必须消除其不等式约束和符号无限制变量。,目标函数的转换 约束条件的转换 变量的非负约束的转换 任何形式的线性规划数学模型都可以转换成标准型的线性规划,例4: 试将如下线性规划问题化成标准型,解:令
3、x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非负松弛变量 x6 , (2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型:,三、什么是可行解、可行域,可行域的几何结构?,满足所有约束条件的决策变量,称为可行解或可行点(feasible point)。 使目标函数值最大的可行解称为最优解 所有可行点组成的集合称为可行域(feasible region),记为D. 给定一个LP问题可行域D,下列三种情况必居其一,D = 称该问题无解或不可行。 D 且可行域有界。则线性规划问题一定存在最优解。这时最优解唯一,也可能有无穷多。 D , 且可行域为无界
4、,则线性规划问题或者有最优解(唯一或无穷多)也可能没有有限的最优解。 当可行域非空时,可行域的几何结构为(多面)凸集,四、基本解、基本可行解 (basic solution、basic feasible solution),秩(A)=m,则矩阵A中存在一个m阶满秩 子方阵B。称B矩阵为线性规划问题的一个基。,解之间的关系 可行解:满足约束条件 最优解:满足约束条件,同时使目标函数值最优。 基础解:满足 且非零分量的数目不大于方程的个数m。 基可行解:是基础解又是可行解。 基最优解:满足约束条件,且无非零分量,或非零分量对应的列向量现性无关,同时使目标函数值最优。,五、 LP问题的几何意义(单纯
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 茹少峰 课件
链接地址:https://www.31doc.com/p-2709603.html