最优化方法线性规划单纯形法.ppt

文档介绍：最优化方法线性规划单纯形法线性规划:目标函数是线性的,约束条件是线性等式或不等式线性规划线性规划的历史渊源要追溯到Euler、Liebnitz、eDantzig,VonNeumann(Princeton)和LeonidKantorovich在1940’s创建了线性规划1947年,eDantzig发明了单纯形法1979年,(第一个多项式时间算法-椭球内点法)1984年,NarendraKarmarkan发现了另一种求解线性规划的有效方法,已证明是单纯形法的强有力的竞争者(投影内点法)现在求解大规模、退化问题最有效的是原-对偶内点法◎问题:确定食品数量,满足营养需求,花费最小?◎变量:n种食品,m种营养成份; -第j种食品的单价-每单位第j种食品所含第i种营养的数量-食用第j种食品的数量-为了健康,每天必须食用第i种营养的数量◎模型:(dataenvelopeanalysis,DEA)workflow)博弈论(gametheory)等线性规划的一般形式