线性规划的基本定理_第1页
线性规划的基本定理_第2页
线性规划的基本定理_第3页
线性规划的基本定理_第4页
线性规划的基本定理_第5页
已阅读5页,还剩27页未读 继续免费阅读

下载本文档

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

文档简介

3.线性规划的基本定理1标准形式及图解法1.1标准形式矩阵表示3.线性规划的基本性质其中A是mn矩阵,c是n维行向量,b是m维列向量。评注:为计算需要,一般假设b0.否则,可在方程两端乘以(-1)即可化为非负。3.线性规划的基本性质任意非标准形式均可划为标准形式,如引入松弛变量xn+1,

xn+2,…xn+m.则有3.线性规划的基本性质若某变量xj无非负限制,则引入xj

=

xj

'

-

xj

'',

xj

',

xj

''0若有上下界限制,比如xj

lj,令xj

'=xj

-lj,,

有xj

'

03.线性规划的基本性质1.2.图解法当自变量个数少于3时,我们可以用较简便的方法求解。3.线性规划的基本性质Min3x+2.5ys.t.2x+4y403x+2y

50

x,y

0.例如,考虑食谱问题3.线性规划的基本性质30104020501020304050yx03x+2.5y2x+4y403x+2y50(15,2.5)可行区域的极点:(0,25)(15,2.5)最优解(20,0)2基本性质2.1线性规划的可行域3.线性规划的基本性质定理

3.1

线性规划的可行域是凸集.

2.2最优极点观察上例,最优解在极点(15,2.5)达到,我们现在来证明这一事实:线性规划若存在最优解,则最优解一定可在某极点上达到.考察线性规划的标准形式(3.2)3.线性规划的基本性质根据表示定理,任意可行点x可表示为把x的表达式代入(3.2),得等价的线性规划:3.线性规划的基本性质于是,问题简化成3.线性规划的基本性质在(3.6)中令3.线性规划的基本性质显然,当时目标函数取极小值.3.线性规划的基本性质(p)x因此极点是问题(3.2)的最优解.即(3.5)和(3.8)是(3.4)的最优解,此时2,若(3.2)存在有限最优解,则目标数的最优值可在某极点达到.3.线性规划的基本性质定理3.2设线性规划(3.2)的可行域非空,则1,(3.2)存在最优解的充要条件是所有(j)cd非负,其中是可行域的极方向d(j)3最优基本可行解3.线性规划的基本性质前面讨论知道们最优解可在极点达到,而极点是一几何概念,下面从代数的角度来考虑。不失一般性,设rank(A)=m,A=[B,N],B是m阶可逆的.3.线性规划的基本性质于是,Ax=b可写为于是特别的令Nx=0,则称为方程组Ax=b的一个基本解.3.线性规划的基本性质定义3.1B称为基矩阵,的各分量称为基变量.xB基变量的全体称为一组基.的各分量称为基变量.xN为约束条件Ax=b,x0的一个基本可行解.B称为可行基矩阵3.线性规划的基本性质称为一组可行基.Bb>0,称基本可行解是非退化的,若-1若Bb0,-1且至少有一个分量为0,称基本可行解是退化的.3.线性规划的基本性质3.线性规划的基本性质3.线性规划的基本性质容易知道,基矩阵的个数是有限的,因此基本解从而基本可行解的个数也是有限的,不超过3.线性规划的基本性质定理3.3令K={x|Ax=b,x0},A是m×n矩阵,r(A)=m则K的极点集与Ax=b,x0的基本可行解集合等价.3.线性规划的基本性质证明:(提纲)1)设x是K的极点,则x是Ax=b,x0的基本可行解.2)设x是Ax=b,x0的基本可行解,则x是K的极点.3.线性规划的基本性质1),先证极点x的正分量所对应的A的列线性无关.3.线性规划的基本性质3.线性规划的基本性质3.线性规划的基本性质2)设x是Ax=b,x0的基本可行解,记即3.线性规划的基本性质总结,线性规划存在最优解,目标函数的最优值一定能在某极点上达到.可行域K={x|Ax=b,x0}的极点就是其基本可行解.

从而,求线性规划的最优解,只需要求出最优基本可行解即可.3.线性规划的基本性质3.4基本可行解的存在问题3.线性规划的基本性质定

温馨提示

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

评论

0/150

提交评论