第7讲最优化问题.pdf

最优化问题——梯度下降法1、⽆约束最优化问题求解此问题的⽅法⽅法分为两⼤类：最优条件法和迭代法。

2、最优条件法我们常常就是通过这个必要条件去求取可能的极⼩值点，再验证这些点是否真的是极⼩值点。

当上式⽅程可以求解的时候，⽆约束最优化问题基本就解决了。

实际中，这个⽅程往往难以求解。

这就引出了第⼆⼤类⽅法：迭代法。

最优条件法：最⼩⼆乘估计3、迭代法（1）梯度下降法（gradient descent），⼜称最速下降法（steepest descent）梯度下降法是求解⽆约束最优化问题的⼀种最常⽤的⽅法。

梯度下降法是迭代算法，每⼀步需要求解⽬标函数的梯度向量。

必备条件：函数f(x)必须可微，也就是说函数f(x)的梯度必须存在优点：实现简单缺点：最速下降法是⼀阶收敛的，往往需要多次迭代才能接近问题最优解。

算法A.1（梯度下降法）输⼊：⽬标函数f(x)，梯度函数g(x)=▽f(x)，计算精度ε；输出：f(x)的极⼩点x*总结：选取适当的初值x(0),不断迭代，更新x的值，进⾏⽬标函数的极⼩化，直到收敛。

由于负梯度⽅向是使函数值下降最快的⽅向，在迭代的每⼀步，以负梯度⽅向更新x的值，从⽽达到减少函数值的⽬的。

λk叫步长或者学习率；梯度⽅向g k=g(x(k)）是x=x(k)时⽬标函数f(x)的⼀阶微分值。

学习率/步长λ的确定：当f(x)的形式确定，我们可以通过求解这个⼀元⽅程来获得迭代步长λ。

当此⽅程形式复杂，解析解不存在，我们就需要使⽤“⼀维搜索”来求解λ了。

⼀维搜索是⼀些数值⽅法，有0.618法、Fibonacci法、抛物线法等等，这⾥不详细解释了。

在实际使⽤中，为了简便，也可以使⽤⼀个预定义的常数⽽不⽤⼀维搜索来确定步长λ。

这时步长的选择往往根据经验或者通过试算来确定。

步长过⼩则收敛慢，步长过⼤可能震荡⽽不收敛。

如下图：当⽬标函数是凸函数时，梯度下降法的解是全局最优解。

但是，⼀般情况下，往往不是凸函数，所以其解不保证是全局最优解。

最优化问题最优化问题(一)例1：一只平底锅上只能剪两只饼。

用它剪1只饼需要2分钟（正面、反面各1分钟）。

问剪3只饼需要几分钟？怎样剪？例2：6个人各拿一只水桶到水龙头接水。

水龙头注满6个人的水桶所需时间分别是5分钟、4分钟、3分钟、10分钟、7分钟、6分钟。

现在只有这一个水龙头可用，问怎样安排这6个人的打水次序，可使他们总的等候最短？这个最短时间是多少？例3：小红放学回家，想让爸爸、妈妈下班后就能吃上晚饭。

她准备做大米饭和炒鸡蛋。

小红家有两个炉灶。

估计一下，洗锅要用1分钟，淘米要用5分钟，做大米饭要用30分钟，打蛋要用1分钟，洗炒勺要用1分钟，烧油要1分钟，炒鸡蛋要3分钟。

你认为最合理的安排要几分钟能做好饭菜？例4：在公路上，每隔100千米有一个仓库，共有5个仓库。

1号仓库里有10吨货物，2号仓库里有20吨货物，5号仓库里有40吨货物，其余两个仓库都是空的。

现在想把所有的货物集中存放在一个仓库里，若每吨货物运输一千米要0.5元运输费，那么至少要花费多少元运费才行？例5：沿铁路有5个工厂，A，B，C，D，E（如图），各厂每天都有10吨货物要外运。

现在想建一座车站，使这5个工厂的货物运到车站的行程总和越小越好。

车站应建在何处？如果在E的右侧增加一个工厂，车站建在何处总行程最小呢？例6：在公路干线的附近，有5个工厂A，B，C，D，E（如图），各厂每天都有10吨货物要存库。

现在想在公路干线上建一座库房，使这5个工厂的货物运到库房的行程总和越小越好，库房应建在何处？例7：工地上有手推车20辆,其中10辆从A1到B1运垃圾,要60车次运完。

另外10辆从A2到B2运砖头，要40车次运完。

工地上的可行道路及路程如图（单位：米）所示。

有人说上面的安排不合理，因为跑空车的路程还可以更少些。

那么，怎样安排才算合理呢？【练习题】1、有7个满杯水、7个半杯水和7个空杯。

不许倒水，你能把这些东西平均分给3个人，使得每人有7只杯子和3杯半水吗？2、有8个人在交通事故中受伤，救援人员1人可以救护2人，而1辆救护车只可以坐4个人。

（六年级）备课教员：×××第七讲最优化问题一、教学目标： 1. 通过简单事例，初步体会统筹思想在实际问题中的应用。

2. 在各种方案中寻求一个最合理，最省事，最节约的方案。

二、教学重点： 1. 通过观察分析、合作探究让学生感受用不同的方法，进行有条理安排的数学统筹方式。

三、教学难点： 1. 让学生经历探索统筹策略的过程，建立统筹思想。

四、教学准备：PPT、8根火柴棒或8枚棋子五、教学过程：第一课时（50分钟）一、导入（5分)师：同学们，你们都是6年级的学生了，平时是不是会帮助爸爸妈妈做家务呢？生：……师：今天，米德和卡尔也要帮助阿博士做事情。

我们来看看他们要做些什么呢？（出示PPT)（与学生初步探讨简单的时间最优化问题）师：这就是我们生活中最常遇见的最优化问题，在解决该类型生活问题我们需要观察分析，有时候还需要通过列举法，一一比较，找出最优化方法。

这节课我们就来学习下吧。

【板书课题：最优化问题】二、探索发现授课（40分）（一）例题1：（13分）把78拆成2个质数之和，它们最大的积是多少？师：同学们，还记得什么是质数吗？最小的质数是？最小的合数是？（简单复习质数、合数等数的概念）生：……师：把78拆成2个质数之和有几种拆法呢，同学们动手试试。

（巡视学生的列举情况，培养学生的细心习惯及观察学生的性格特点）生：……师：我们可以从小到大，一一列举。

（5，73）、（7，71）、（11，67）、（17，61）、（19，59）、（31，47）、（37，41）。

师：同学们，自己看看有没有遗漏的呢？生：……师：同学们，把这些组合都乘积都算出来看看，有什么发现吗？（让学生通过自身实践努力，发现数学规律）生：……师：不错，两个数的和一定，两个数的差越小，它们的积越大。

板书：78=37+4137×41=1517答：它们最大的积是1517。

练习1：（6分）把152拆成2个质数之和，它们最大的积是多少？分析：通过列举法，找出最接近的两个质数组合，它们最大的积就算出来了。

第7讲数学好玩一.设计秋游方案最优化问题：最优化概念反映了人类实践活动中十分普遍的现象，即要在尽可能节省人力、物力和时间前提下，争取获得在可能范围内的最佳效果，因此，最优化问题成为现代数学的一个重要课题，涉及统筹、线性规划一排序不等式等内容．下面我们就最优化问题做出汇总分析．最优化问题不仅具有趣味性，而且由于解题方法灵活，技巧性强，因此对于开拓解题思路，增强数学能力很有益处．但解决这类问题需要的基础知识相当广泛，很难做到一一列举．二.图形中的规律事物的间隔排列规律三.尝试与猜测鸡兔同笼：方法：假设法，方程法，抬腿法，列表法公式1：（兔的脚数×总只数-总脚数）÷（兔的脚数-鸡的脚数）=鸡的只数；总只数-鸡的只数=兔的只数公式2：（总脚数-鸡的脚数×总只数）÷（兔的脚数-鸡的脚数）=兔的只数；总只数-兔的只数=鸡的只数公式3：总脚数÷2-总头数=兔的只数；总只数-兔的只数=鸡的只数公式4：鸡的只数=（4×鸡兔总只数-鸡兔总脚数）÷2；兔的只数=鸡兔总只数-鸡的只数公式5：兔总只数=（鸡兔总脚数-2×鸡兔总只数）÷2；鸡的只数=鸡兔总只数-兔总只数公式6：（头数x4-实际脚数）÷2=鸡公式7：4×+2（总数-x）=总脚数（x=兔，总数-x=鸡数，用于方程）公式8：鸡的只数：兔的只数=兔的脚数-（总脚数÷总只数）：（总脚数÷总只数）-鸡的脚数．题型一：简单规划问题【典例1】（永州模拟）小芳去文具市场买钢笔，每支钢笔零售价为5元，但市场规定，5支或5支以上可以批发，批发价为每支4元．小芳要买3支钢笔，可以怎样买了（请写出你的购买方案和理由）【典例2】（长沙模拟）公园里有红、橙、黄、蓝、紫五种颜色的鲜花．用其中三种颜色的鲜花组成一个大花丛，另两种颜色的鲜花组成一个小花丛．上述各色花的栽种面积依次相当于大花丛面积的12、13、14、15和16．请问：小花丛是由哪两种颜色的鲜花组成的？简述理由．题型二：事物的间隔排列规律【典例1】（长沙）如图所示，按三个图的顺序，第四个图应该是ABCD 的（ ）A ．B ．C ．D ．4．（济南期末）找规律。