交通运筹学教学课件作者张文会第1章节线性规划课件

《交通运筹学教学课件作者张文会第1章节线性规划课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划LinearProgramming1主要内容第一节线性规划及其数学模型第二节图解法第三节线性规划的单纯形法第四节单纯形法的计算公式第五节线性规划在道路交通方面的应用2第一节线性规划及其数学模型1.1.1线性规划线性规划（LinearProgramming,LP）是在一组约束条件（既定要求）下寻找一个目标函数（衡量指标）的极值。1.1.2数学模型线性规划的数学模型由决策变量、目标函数与约束条件三个要素构成，其特征是：（1）解决问题的目标函数是多个决策变量的线性函数，求最大值或最小值；（2）解决问题的约束条件是一组多个决策变量的线性不等式或等式。3线性规划是研究线性约束条件下

2、线性目标函数的极大值或极小值问题的数学理论和方法；线性规划的数学模型由决策变量、目标函数与约束条件三个要素构成。则线性规划数学模型的一般表达式可写成为：为了书写方便，上式也可写成：4【例1.1】靠近某河流有两个化工厂（见图1-1），流经第一个化工厂的河流流量为400万立方米/天，在两个工厂之间有一条流量为200万立方米/天的支流。第一化工厂每天排放含有浓的工业污水2.5万立方米，第二化工厂每天排放这种工业污水1.6万立方米。已知从第一化工厂排出的工业污水流到第二化工厂以前有25%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此，这两个工厂都需各自处理一部分工业污水。

3、第一化工厂处理工业污水的成本是1000元/万立方米，第二化工厂处理工业污水的成本是800元/万立方米。问在满足环保要求的条件下，每厂各应处理多少工业污水，使得这两个工厂总的处理工业污水费用最小。工厂2工厂1200万立方米/天400万立方米/天5解设，分别为第一个和第二个化工厂每天应处理工业污水的量。根据河流中工业污水的含量应不大于0.2%的要求，可建立以下不等式：由于每个工厂每天处理的工业污水量不会大于每天的排放量，故有：经整理，得到下列线性规划模型：6第二节图解法图解法是直接在平面直角坐标系中作图来解线性规划问题的一种方法，只适合于求解两个变量的线性规划问题。图解法的步骤：（1）可行

4、域的确定。（2）绘制目标函数等值线。（3）求最优解。7【例1.2】用图解法求解下列线性规划问题：102010200(1:1)8【例1.3】将例1.2的目标函数改为，约束条件不变，则表示目标函数中以参数z的这组平行直线与约束条件的边界线平行。平行移动目标函数直线与可行域相较于线段AB，则线段AB上任意点都是最优解，如图所示，即最优解不惟一，有无穷多个，称为多重解。最优解的通解可表示为。010201020AB(2:1)9【例1.4】将例1.2的约束条件改为，目标函数不变，则可行域如图所示，A点是最小值点，要达到最大值，目标函数值可在可行域中沿梯度方向继续平移直到无穷远，，及Z都趋于无穷大（

5、无上界），这种情形称为无界解，也即为无最优解。102010200(1:1)A10【例1.5】在例1.2的数学模型中增加一个约束条件，则该问题的可行域为空集，如图所示，即无可行解，因此该问题也就不存在最优解。102010200303011通过以上例题分析，可将图解法得出线性规划问题解的几种情况归纳为如下12第三节线性规划的单纯形法1.3.1线性规划问题的标准型为：（1）目标函数求最大值（也可以求最小值）；（2）约束条件均为等式方程；（3）变量为非负；（4）常数都大于或等于零。数学模型可表示为：131415161.3.2线性规划的有关概念已知线性规划的标准型为：（1）基式中A是阶矩阵，m<

6、n,且r(A)=m，显然A中至少有一个子矩阵B，使得r(B)=m。B是矩阵中m阶非奇异子矩阵，则称B是线性规划的一个基（或基矩阵）。【例】已知线性规划求所有基矩阵17（2）基向量、非基向量、基变量、非基变量当确定某一子矩阵为基矩阵时，则基矩阵对应的列向量称为基向量，其余列向量称为非基向量，基向量对应的变量称为基变量，非基向量对应的变量称为非基变量。（3）基本解对某一确定基，令非基变量等于零，利用约束条件解出基变量，则这组解称为基的基本解。例1.9中对于而言，是其基本解。（4）可行解满足约束条件的解称为可行解。（5）最优解满足目标函数的可行解称为最优解，即使得目标函数达到极值的可行解就是

7、最优解。（6）基本可行解满足非负条件的基本解称为基本可行解（也称基可行解）。（7）基本最优解最优解是基本解称为基本最优解。（8）可行基与最优基基可行解对应的基称为可行基，基本最优解对应的基称为最优基。最优基也是可行基。18基本解、可行解、最优解、基本可行解、基本最优解的关系如图所示。箭尾的解一定是箭头的解，否则不一定成立。基本最优解基本可行解最优解可行解基本解191.3.3线性规划的几何意义在第二节介绍图解法时，已直观地看到可行域和最优解的几何