《matlab4线性规划》PPT课件

《《matlab4线性规划》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章线性规划引言什么是线性规划如果最优化问题三要素中的目标函数和约束条件都是线性的，则该最优化问题称为线性规划问题线性规划的应用和发展线性规划（LinearProgramming，简写成LP）是最优化理论和方法中的重要领域之一。其理论上的完整性、方法上的有效性以及应用上的广泛性，较其他分支都成熟的多，同时很多实际问题都可以转化为线性规划来解决线性规划的要点就是在满足线性约束条件的前提下，使预定的线性目标函数达到最优。现在线性规划已不仅仅是一种数学方法，在理论上，它启发了诸如对偶、凸性等最优化理论的核心概

2、念，在实际中更是大量被运用于经济学和管理学领域，成为科学决策的一个有效手段乔治·丹齐格（G.B.Dantzig）被认为是线性规划之父。自从1947年他提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在应用上也日益深入，成为科学与工程领域广泛应用的数学模型。特别是在计算机能处理海量约束条件和设计变量的线性规划问题之后，线性规划就更加受到青睐线性规划的典型实例运输问题设有两个建材厂C1和C2，每年沙石的产量分别为35万吨和55万吨，这些沙石需要供应到W1、W2和W3三个建筑工地，每个建筑工地对沙石

3、的需求量分别为26万吨、38万吨和26万吨，各建材厂到建筑工地之间的运费（万元/万吨）如表所示，问题是应当怎么调运才能使得总运费最少？运费工地建材厂W1W2W3C110129C281113线性规划的典型实例运输问题问题分析假设xij代表建材厂Ci运往建筑工地Wj的数量（万吨），则各建材厂和工地之间的运量可以用下表来表示目标函数即为总运费建材厂C1、C2的输出量应分别为建材厂C1、C2的产量各工地的沙石需求量应当为从各建材厂接收到沙石的总量运输量xij为一非负值分配量工地（万吨）建材厂W1W2W3输出总量C

4、1x11x12x1335C2x21x22x2355接收总量26382690线性规划的典型实例运输问题数学模型线性规划问题的特征均可以用一组设计变量来表示一种实施方案每个问题都有一定的约束条件，这些条件可以用一组线性等式或者线性不等式表达在上述前提下，一般都有一个目标函数，该函数用于衡量方案的优劣，可以表达为设计变量的一个线性函数，我们的目的一般为使得目标函数达到最大值或者最小值线性规划问题的标准型线性规划问题的一般标准型根据线性规划的定义，线性规划问题即求取设计变量x=[x1,x2,…xn]T的值，在线性

5、约束条件下使得线性目标函数达到最大，线性规划问题的一般标准型为：其中，ci、aij、bi为给定的常数线性规划问题的标准型的特点目标函数为设计变量的线性函数，且需要极大化；约束条件为设计变量的一组线性等式，也称为约束方程组；设计变量x1,x2,…xn都有非负限制。线性规划问题的标准型线性规划问题的矩阵标准型利用向量或矩阵符号，线性规划问题的标准型还可以用矩阵形式表达：其中为n维行向量为m×n维矩阵为m维列向量为n维列向量是指其各分量线性规划问题的标准型不同类型的非标准型化为标准型的方法问题为极小化目标函数设

6、原有线性规划问题为极小化目标函数则可设将极小化目标函数问题转化为极大化目标函数问题约束条件为不等式如果原有线性规划问题的约束条件为不等式，则可增加一个或减去一个非负变量，使约束条件变为等式，增加或减去的这个非负变量称为松弛变量。例如，假如约束为则可以在不等式的左边增加一个非负变量xn+1，使不等式变为等式如果约束为则可在不等式的左边减去一个非负变量xn+1，使不等式变为等式模型中的某些变量没有非负限制若对某个变量xj并无限制，取值可正可负，这时可设两个非负变量和，令注意到，因为对原设计变量进行了代换，还需

7、要将代换式代入目标函数和其他约束条件做相应的代换，这样就可以满足线性规划标准型对变量非负的要求线性规划问题的标准型例子将线性规划模型标准化将目标函数两边乘上-1转化为求极大值原问题的约束条件中的前两个条件均为不等式，在第一个不等式的左边加上一个松弛变量x4，在第二个不等式的左边减去一个松弛变量x5，将两者转化为等式约束原问题对设计变量x3没有非负限制，故在此引入非负变量和，令经过上述步骤整理后的标准型为线性规划问题中解的概念概述为了帮助分析线性规划求解过程，先介绍线性规划解的概念。仍然考虑式(4-2)中的

8、线性规划的矩阵标准型：求解上述线性规划问题实际上就是要求出向量x=[x1,x2,…xn]T使其满足Ax=b和x≥0，且目标函数f达到最大值，这个向量称为线性规划问题的解。当求解Ax=b时，假设独立方程的个数为m个，设计变量的维数为n，根据线性代数的知识，如果m=n，则方程有唯一解，无优化的自由度；如果m>n，方程个数大于未知数的个数，则有些约束可能不能被满足，上述两类问题不在我们探讨的范围之列，也就是我们仅讨论m