1最优化方法教案(线性规划).doc

最优化方法一、引言最优化理论与方法是一门应用性很强的年轻学科。它研究某些数学上定义的问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。 虽然最优化可以追朔到十分古老的极值问题，然而，他成为一门独立的学科诗在上世纪40年代末，是在1947年Dantzing提出求解一般线性规划问题的单纯型法之后。现在，解线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、整数规划等各种最优化问题的理论的研究发展迅速，新方法不断出现，实际应用日益广泛。在电子计算机的推动下，最优化理论与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成为一门十分活跃的学科。 现在大多数有代表性的最优化算法已有可以方便使用的软件包，如lindolingo优化软件包。但有效利用这些成果是以有待解决的问题已被模型化成最优化问题的形式为前提的。要做到这点，要有深刻的洞察力和综合能力，这需要掌握最优化算法的结构和特点，并与专业知识的结合和兼蓄。 最优化有着丰富的内容和方法，本课我们主要介绍线性规和非线性规划的主要方法与理论他们是最优化理论的重要分支，也是最基本的部分。第一部分：线性规划第一章：单纯型法第一节问题的引出: 例1：某制造公司需要生产n种产品，生产这n种产品需要m种不同的原材料，第i（i=1,2,.m.。）种原材料的拥有量为bi。实际情况很复杂，我们将其简化或理想化，只关注某个时间点的特定情况，第i种原材料在某时间点的市场价格为i，生产单位数量的第j种产品需消耗第i种原材料aij个单位。第j种产品在同一时间点上的市场价格为j。 考虑问题一：如何安排1，2，.n种产品的生产，从而使收益最大设第j种的产量为单位，第j种产品的收益与市场销售价有关，也与生产第j种产品所消耗的原材料费用有关，因此第j种单位产品的纯收入为，全部纯收入，此时。而我们不可能超出原材料的拥有量生产产品。生产n种产品时，所消耗的第i（i=1,2,.m.。）种原材料的总量为综上所述，我们为达到收益最大，就建立了这样的数学规划问题：这是一个资源配制问题（资源分配问题），也是一个线性规划问题。从另一种角度考虑上述问题：假若由于某种原因，该制造单位打算放弃这些生产项目，而另一家企业希望收购这些资源。那么如何确定这m种原材料的转让价格，同时照顾到买卖双方的利益使买卖有可能成交？设这m种原材料的单位定价为1m。 全部损失机会成本为，定价要不低于市场获利,即 。令是当前市场价格的提升价格，全部机会损失值变为从卖方角度看，希望以尽可能低的价格收购这些资源，即总费用最小，于是得到这两个角度考虑问题得到了两个线性规划问题（LP问题）前例问题中，有些变量决定了问题的最优值，称为决策变量，LP问题中总是要求极大化或极小化由决策变量构成的线性函数，此函数称为目标函数。第二节：线性规划问题的标准型（）A线性规划问题的标准型LP的标准型是指如下形式的优化问题例如（1）（2）都很容易化成标准型先看（1），引入变量，使，则有此时称为松弛变量。对（2）增加变量使，此时称为剩余变量。由此看任一个LP问题都可以化为标准型（3）。前面对不等式约束化成了等式约束再看决策变量： 一组取定的决策变量的值称为一个解。在（3）中，记称为可行域。称为（3）的一个可行解。若存在使 ，都有，则称是（3）的最优解。当时，问题（3）无可行解，称（3）是不可行的。如 。另一种极端的情形是称为无界的情况，即对任意大的目标值都有解。如 ，解, 可以任意大。B线性规划问题的图解法 当时的线性规划问题可以用图解法求其最优解。例2：求解下列LP问题例3： 试用图解法分析问题的最优解随，取值的不同的变化情况。 C线性规划的图表法（单纯形图表法）例4： 解：引入松弛变量将原问题化为标准形观察到一个可行解，此时显然不是最小值。当是的系数，当改变时，也改变。当变大，而不动时，也改变。必须得保证 ，而又希望尽可能大。 当时，改进最大，且可以看出是否需继续改进。做恒等变形。这样得到改进解，此时 将的位置互换，并将目标函数中的变量用替换。从目标函数看，此时前的系数。当由时，目标函数能进一步得到改善。当时，第1和3个约束的数量发生改变，为保证各决策变量的非负性，需满足，得，即，最大能由，此时。得到改善解。在（5）式中将变为单位变量，且目标函数行视为同样地位化简。得到再看如何改善f，由目标行看到前的系数均为正，而的取值已达到下界，所以f已不能再获得改善，即达到最优。其最优解是，所求原问题的最优解为，最优解。总结： 这时若有一初始可行解，选目标行系数0。若（当有多个时，选最大的）以改善目标函数值。为保证可行性，需要满足，由此解出的取值，。再将替换r行单位量的位置。（即变换成单位量，做转换）目标行也跟着做同样的变化。这里有几个概念：基变量：约束中处于单位量的位置的变量，个数与约束的个数相同。非基变量：除了基变量以外的决策变量。：称为进基变量。r行的单位量离基：称为离基变量。替换的由一个表格dictionary转变成另一个表格dictionary称为主元消去法。判别行：目标函数所在的行。判别数：判别行中决策变量前的系数。基本可行解：非基变量取值为0的可行解称为基本可行解。转换步骤：先确定进基变量，再确定离基变量。进基变量的选择准则：改善目标函数值，在dictionary中，判别数0者。离基变量的选择准则：保证可行性。例5：求解LP ， 解：（1）引入松弛变量，化为标准型，写出dictionary。写成字典式表格形式（2）开始迭代第一次迭代：（i）先找进基变量目标行中的判别数0者，只有的系数。是进基变量。（ii）再选离基变量即离基。以=4为主元，消去约束和目标行中的，得到第二次迭代：（i）先找进基变量 （ii）确定离基变量 （iii）以为主元，做主元消去法，得到第三次迭代：（i）选找进基变量，判别行中决策变量的系数（判别数）均0。目标函数不能再改进。已求得最优解与最优值。所以例6： 用图表法求解LP问题解：引入松弛变量化为标准形写出表格形式b11-2100102-140108-1-40014f-12-10000进基变量：判别行：离基变量： b00108001101-2002f00300-1-4进基变量： 离基变量： b