浙大城院数学建模ppt课件.ppt

《浙大城院数学建模ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章、优化模型§5.1线性规划模型§5.2运输问题§5.3库存问题§5.4最佳捕鱼方案§5.5森林救火费用最小问题8/26/20211MCM§5.5森林救火费用最小问题§5.6光学中的折射原理§5.7身体结构得优化8/26/20212MCM经济管理和科学研究等领域中经常会遇到的问题类型之一。在很多情况下，我们会凭经验解决面临的优化问题，这样做看似有效，风险也较小，但决策时常常会融入太多决策者的主观臆断，因而无法保证结果的最优性。那么，是否一定要做大量的试验来探索最优方案呢？前言：最优化方法是数学学

2、科中的一个应用性很强的分支，它包含的内容十分广泛，有数学规划（如线性规划、非线性规划、二次规划、目标规划、多目标规划等）、库存论、排队论、博弈论、组合优化（离散优化）、随机规划等等。8/26/20213MCM§5.1线性规划模型线性规划（LinearProgramming,简记LP）是数学规划的一个重要组成部分。自从1947年G·B·Dantzig提出求解线性规划的单纯形法以来，线性规划在理论上日趋成熟，在应用上日趋广泛，已成为现代管理中经常采用的基本方法之一。8/26/20214MCM某厂生产甲、

3、乙两种产品，每单位产品销售后的利润分别为4千元与3千元。生产甲产品需用A、B两种机器加工，每单位产品的加工时间分别为2小时和1小时；生产乙产品需用A、B、C三种机器加工，每单位产品的加工时间为每台机器各一小时。若每天可用于加工这两种产品的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应当生产甲、乙两种产品各多少，才能使总利润最大？例5.1（线性规划的实例）8/26/20215MCM例5.1的数学模型设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1、x2应满足：(5.1)4x

4、1+3x2表示生产x1单位甲产品和x2单位乙产品的总利润，被称为问题的目标函数。中的几个不等式是问题的约束条件，记为S.t。由于式中的目标函数与约束条件均为线性函数，故被称为线性规划问题。8/26/20216MCM线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件可以是不等式也可以是等式，变量可以有非负要求也可以没有（称没有非负约束的变量为自由变量）。为了避免这种由于形式多样性而带来的不便，规定线性规划的标准形式为线性规划的标准形式(5.2)8/26/20217MCM或更简洁地，利用矩阵与

5、向量记为(5.3)其中C和x为n维列向量，b为m维列向量，b≥0，A为m×n矩阵，m

6、1x1+…+ainxn－yi=bi，且yi≥0。（3）若xi为自变量，则可令，其中、≥08/26/20219MCM例如，例5.1并非标准形式，其标准形式为(5.4)8/26/202110MCM为了了解线性规划问题的特征并导出求解它的算法，我们先应用图解法来求解例5.1。满足线性规划所有约束条件的点被称为问题的可行点（或可行解），所有可行点构成的集合被称为问题的可行域，记为R。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们就得到了一族平行直线（见图5-1）。线

7、性规划的图解法8/26/202111MCM图5-1（注：）对于例5.1，等位线越趋于右上方，其上的点具有越大的目标函数值。不难看出，例5.1的最优解为x*=(2,6)T，最优目标值z*=26。8/26/202112MCM（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R的“顶点”，（注：我们称这种“顶点”为极点）。从上面的图解过程可以看出并不难证明以下断言：（1）可行域R可能会出现多种情况。R可能是空集也可能是非空集合，当R非空时必定是若干个半平面的交集（除非遇到空间维数的退化）

8、。R既可能是有界区域，也可能是无界区域。（2）在R非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其目标函数值无界）。8/26/202113MCM上述论断可以推广到一般的线性规划问题，区别只在于空间的维数。在一般的n维空间中，满足某一线性等式aix=bi的点集被称为一个超平面，而满足某一线性不等式aix≤bi（或aix≥bi）的点集被称为一个半空间（其中ai为一n维行向量，bi为一实数）。若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，