3.2线性规划问题的基本解.ppt_第1页
3.2线性规划问题的基本解.ppt_第2页
3.2线性规划问题的基本解.ppt_第3页
3.2线性规划问题的基本解.ppt_第4页
3.2线性规划问题的基本解.ppt_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、3.2 线性规划问题的基本解,基本概念： 可行解、可行域、最优解、基、基变量、基阵、基本可行解,给定一个线性规划问题LP,一、基本概念：,1、可行解 (a feasible solution),满足约束条件的X称为线性规划问题的可行解;,所有可行解的集合称为可行域 (feasible region),使目标函数(1.1)达到最大值的可行解称为最优解(an optimal solution)。,2、基(base),即,是A的m个列向量,设,是线性无关的，,如果,则称,为基向量。,记约束方程系数矩阵A的列向量是,3、基变量(basic variables),构成线性规划问题的一组基向量,设,则对应

2、的变量,称为基变量，,其余的向量称为非基向量，其余的变量称为非基变量 (non-basic-variable)，,称为基或基阵(basic matrix)。,矩阵,约束方程A的系数矩阵为：,分别是变量,的系数向量。,例1,向量组 是线性无关组,是此问题的一个基,其中 为基变量，而 是非基变量。,向量组 是线性无关组,是基变量，,是此问题的一个基,而 是非基变量。,（2）设B是A的一个m阶子矩阵，则B是线性规划问题的基阵，当且仅当B是可逆阵,（3）基的个数Cnm,注：（1）基不一定唯一,4、基解,现令所有的非基变量都等于0，即,设 是线性规划问题LP的一基阵，,表示基变量向量，,表示非基变量向量

3、。,则约束方程(1.2)可化为：,它是一个m个变量m个方程组成的线性方程组，B又是可逆阵，从而得出(1.4)的唯一解,得出约束方程(1.2)至少含有n-m个0元的解,称之为相应于基B的一个基本解或基解(a basic solution)。,5、基可行解,设 是对应于基阵B的一个基解，,如果,则称 为一个基本可行解或基可行解.,(a basic feasible solution)；,相应的基B也称为可行基(feasible base)。,在上例1中， 对应于 的基解为 是一个基可行解， 对应于 的基解为 而不是基可行解。,思考题：试列出例1中问题的所有基解、基可行解。,注：给定线性规划问题LP，其基可行 解的数目是有限个，不会超过 。 图1给出了线性规划问题的解的关系。,图1,非可行解,1.设线性规划,取基,分别指出,对应的基变量和非基变量，,是不是可行基,求出基本解，并说明,1若线性规划无最优解则其可行域无界。（ ） 2凡基本解一定是可行解。 （ ）,2判断题（你认为下列命题是否正确， 对正确的打“”；错误的打“”。）,3线性规划的最优解一定是基本最优解。（ ） 4线性规划的最优解是可行解。（ ） 5可行解是基本解。（ ）,3.线性规划可行域的顶点一定是（ ）。 A.基本可行解B.非基本解 C.非可行解D.最优解 4. X是线性规划的基本可行解，则有（ ）。

人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论