最优化方法(ii) - 浙江大学.pdf

最优化方法(II) 张宏鑫 2010-06-17 浙江大学计算机学院 内容  线性规划  非线性优化  主要参考书：  线性规划，张建中，许绍吉，科学出版社  最优化理论与方法，袁亚湘，孙文瑜，科学出版社 一、线性规划  在人们的生产实践中，经常会遇到如何利用现有资源 来安排生产，以取得最大经济效益的问题。 $利益驱动$ 运筹学 数学规划 线性规划(Linear Programming，LP)  1947年G. B. Dantzig 求解线性规划的单纯形方法  现有的计算机能处理成千上万个约束条件和决策变量的线性 规划问题之后，线性规划的适用领域更为广泛了。 问题定义 (linear programming, LP)  某计算机公司提供大型计算机系统，有A, B, C三个技术团队  高端系统  每套售后的利润400万元  需用A 、B两个技术团队协作实施  A 团队2个月，B团队1个月；  中端系统  每套售后的利润300万元  需用A, B, C三个技术团队协作实施  每个团队各需1个月  2009年度，A 队可工作10个月，B队8个月、C队7个月  问：怎样的销售策略能使总利润最大？ 问题定义 (linear programming, LP)  设可销售x 个高端系统，x 个中端系统 1 2  目标函数 max z 4x 3x 1 2 2x x 10  1 2  x x 8 1 2  约束条件  x 7 2  x , x 0 附加条件：x 和x 是整数 1 2 1 2 问题定义 (linear programming, LP)  在一组线性的等式或不等式约束下，求一个线 性函数的最小值或最大值。  形式化的定义： min c x +…+ c x 1 1 n n s. t. a x +…+ a x ≤b 11 1 1n n 1 … a x +…+ a x ≤b m 1 1 mn n m x ,…, x ≥ 0