文档介绍:会计学
1
最优化方法(fāngfǎ)线性规划单纯形法
第一页,共77页。
线性规划:目标(mùbiāo)函数是线性的,约束条件是
线性等式或不等式
线性规划(xiàn xìnɡ ɡuī huá)
第1页/共77页
第二页,共77页。
线性规划(xiàn xìnɡ ɡuī huá)的历史
渊源要追溯到Euler、Liebnitz、Lagrange等
George Dantzig, Von Neumann(Princeton)和Leonid Kantorovich在1940’s创建了线性规划
1947年, George Dantzig发明了单纯形法
1979年,L. Khachain找到了求解线性规划的一种有效方法(第一个多项式时间算法-椭球内点法)
1984年,Narendra Karmarkan发现了另一种求解线性规划的有效方法,已证明是单纯形法的强有力的竞争者(投影内点法)
现在(xiànzài)求解大规模、退化问题最有效的是原-对偶内点法
第2页/共77页
第三页,共77页。
第3页/共77页
第四页,共77页。
第4页/共77页
第五页,共77页。
第5页/共77页
第六页,共77页。
◎ 问题:确定食品数量,满足(mǎnzú)营养需求,花费最小?
◎ 变量(biànliàng):
n种食品,m种营养成份; -第 j 种食品的单价
-每单位第 j 种食品所含第 i 种营养的数量
-食用第 j 种食品的数量
-为了健康,每天必须食用第i 种营养的数量
◎ 模型(móxíng):
例1. 食谱问题
第6页/共77页
第七页,共77页。
例2. 运输(yùnshū)问题
产销平衡/不平衡的运输(yùnshū)问题
第7页/共77页
第八页,共77页。
例3. 其它(qítā)应用
数据包络分析(data envelope analysis, DEA)
网络(wǎngluò)流问题(Network flow)
博弈论(game theory)等
第8页/共77页
第九页,共77页。
线性规划(xiàn xìnɡ ɡuī huá)的一般形式
第9页/共77页
第十页,共77页。