资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 线性规划,Linear Programming,1,第一章 线性规划Linear Programming1,主要内容,第一节 线性规划及其数学模型,第二节 图解法,第三节 线性规划的单纯形法,第四节 单纯形法的计算公式,第五节 线性规划在道路交通方面的应用,2,主要内容第一节 线性规划及其数学模型2,第一节 线性规划及其数学模型,1.1.1,线性规划,线性规划,（,Linear Programming, LP,）是在一组约束条件（既定要求）下寻找一个目标函数（衡量指标）的极值。,1.1.2,数学模型,线性规划的数学模型由决策变量、目标函数与约束条件三个要素构成，其特征是：,（,1,）解决问题的目标函数是多个决策变量的线性函数，求最大值或最小值；,（,2,）解决问题的约束条件是一组多个决策变量的线性不等式或等式。,3,第一节 线性规划及其数学模型1.1.1线性规划3,线性规划是研究线性约束条件下线性目标函数的极大值或极小值问题的数学理论和方法；线性规划的数学模型由决策变量、目标函数与约束条件三个要素构成。则线性规划数学模型的一般表达式可写成为：,为了书写方便，上式也可写成：,4,线性规划是研究线性约束条件下线性目标函数的极大值或极小值问题,【例,1.1,】,靠近某河流有两个化工厂（见图,1-1,），流经第一个化工厂的河流流量为,400,万立方米,/,天，在两个工厂之间有一条流量为,200,万立方米,/,天的支流。第一化工厂每天排放含有浓的工业污水,2.5,万立方米，第二化工厂每天排放这种工业污水,1.6,万立方米。已知从第一化工厂排出的工业污水流到第二化工厂以前有,25%,可自然净化。根据环保要求，河流中工业污水的含量应不大于,0.2%,。因此，这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是,1000,元,/,万立方米，第二化工厂处理工业污水的成本是,800,元,/,万立方米。问在满足环保要求的条件下，每厂各应处理多少工业污水，使得这两个工厂总的处理工业污水费用最小。,工厂,2,工厂,1,200,万立方米,/,天,400,万立方米,/,天,5,【例1.1】靠近某河流有两个化工厂（见图1-1），流经第一个,解,设，分别为第一个和第二个化工厂每天应处理工业污水的量。,根据河流中工业污水的含量应不大于,0.2%,的要求，可建立以下不等式：,由于每个工厂每天处理的工业污水量不会大于每天的排放量，故有：,经整理，得到下列线性规划模型：,6,解 设，分别为第一个和第二个化工厂每天应处理工业污水的量。,第二节,图解法,图解法是直接在平面直角坐标系中作图来解线性规划问题的一种方法，只适合于求解两个变量的线性规划问题。,图解法的步骤：,（,1,）可行域的确定。,（,2,）绘制目标函数等值线。,（,3,）求最优解。,7,第二节 图解法图解法是直接在平面直角坐标系中作图来解线性规,【例,1.2,】,用图解法求解下列线性规划问题：,10,20,10,20,0,(1:1),8,【例1.2】用图解法求解下列线性规划问题：102010200,【例,1.3,】,将例,1.2,的目标函数改为， 约束条件不变，则表示目标函数中以参数,z,的这组平行直线与约束条件,的边界线平行。平行移动目标函数直线与可行域相较于线段,AB,，则线段,AB,上任意点都是最优解，如图所示，即最优解不惟一，有无穷多个，称为多重解。最优解的通解可表示为。,0,10,20,10,20,A,B,(2:1),9,【例1.3】将例1.2的目标函数改为，,【例,1.4,】,将例,1.2,的约束条件改为，,目标函数不变，则可行域如图所示，,A,点是最小值点，要达到最大值，目标函数值可在可行域中沿梯度方向继续平移直到无穷远， ， 及,Z,都趋于无穷大（无上界），这种情形称为无界解，也即为无最优解。,10,20,10,20,0,(1:1),A,10,【例1.4】将例1.2的约束条件改为，102010200(1,【例,1.5,】,在例,1.2,的数学模型中增加一个约束条件， 则该问题的可行域为空集，如图所示，即无可行解，因此该问题也就不存在最优解。,10,20,10,20,0,30,30,11,【例1.5】在例1.2的数学模型中增加一个约束条件，,通过以上例题分析，可将图解法得出线性规划问题解的几种情况归纳为如下,12,通过以上例题分析，可将图解法得出线性规划问题解的几种情况归纳,第三节,线性规划的单纯形法,1.3.1,线性规划问题的标准型为：,（,1,）目标函数求最大值（也可以求最小值）；,（,2,）约束条件均为等式方程；,（,3,）变量为非负；,（,4,）常数都大于或等于零。,数学模型可表示为：,13,第三节 线性规划的单纯形法1.3.1线性规划问题的标准型为,14,14,15,15,16,16,1.3.2,线性规划的有关概念,已知线性规划的标准型为：,（,1,）,基,式中,A,是阶矩阵，,mn,且,r(A)=m,，显然,A,中至少有一个子矩阵,B,，使得,r(B)=m,。,B,是矩阵中,m,阶非奇异子矩阵，则称,B,是线性规划的一个,基,（或,基矩阵,）。,【,例,】已知线性规划,求所有基矩阵,17,1.3.2 线性规划的有关概念已知线性规划的标准型为：17,（,2,）基向量、非基向量、基变量、非基变量,当确定某一子矩阵为基矩阵时，则基矩阵对应的列向量称为,基向量,，其余列向量称为,非基向量,，基向量对应的变量称为,基变量,，非基向量对应的变量称为,非基变量,。,（,3,）,基本解,对某一确定基，令非基变量等于零，利用约束条件解出基变量，则这组解称为基的基本解。例,1.9,中对于而言，是其基本解。,（,4,）,可行解,满足约束条件的解称为可行解。,（,5,）,最优解,满足目标函数的可行解称为最优解，即使得目标函数达到极值的可行解就是最优解。,（,6,）,基本可行解,满足非负条件的基本解称为基本可行解（也称基可行解）。,（,7,）,基本最优解,最优解是基本解称为基本最优解。,（,8,）,可行基与最优基,基可行解对应的基称为可行基，基本最优解对应的基称为最优基。最优基也是可行基。,18,（2）基向量、非基向量、基变量、非基变量 当确定某一子矩阵,基本解、可行解、最优解、基本可行解、基本最优解的关系如图所示。箭尾的解一定是箭头的解，否则不一定成立。,基本最优解,基本可行解,最优解,可行解,基本解,19,基本解、可行解、最优解、基本可行解、基本最优解的关系如图所示,1.3.3,线性规划的几何意义,在第二节介绍图解法时，已直观地看到可行域和最优解的几何意义，在此从理论上进一步讨论。,（,1,）,凸集,设,K,是,n,维空间的一个点集，对任意两点 ，当 时，则称为凸集。,从直观上讲，凸集没有凹入部分，其内部没有空洞。实心圆、实心球体、实心立方体等都是凸集，圆环不是凸集。如图,1-6,所示，（,a,）是凸集，（,b,）不是凸集。任何两个凸集的交集是凸集，如图,1-6,（,c,）。,a,c,b,20,1.3.3 线性规划的几何意义 在第二节介绍图解法,21,21,（,4,）,几个定理,【定理,1.1,】 若线性规划可行解非空，则是凸集。,【定理,1.2,】 若线性规划的可行解集合的点是极点的充要条件为是基本可行解。,【定理,1.3,】 若线性规划有最优解，则最优解一定可以在可行解集合的某个极点上得到。,定理,1.1,描述了可行解集的几何特征。,定理,1.2,描述了可行解集的极点与基本可行解的对应关系。极点是基本可行解，基本可行解在极点上，但它们并非一一对应，可能有两个或几个基本可行解对应于同一个极点（退化基本可行解）。,定理,1.3,描述了最优解在可行解集中的位置。若最优解惟一，则最优解只能在某一极点上达到；若有多重最优解，则最优解是在某些极点上的凸组合。因此最优解是可行解集的极点或界点，不可能是可行解集的内点。,由定理,1.2,和定理,1.3,可知，线性规划的最优解是在有限个基本可行解中求得的，这样我们可以找到一种解题方法：先求出可行域的所有顶点，然后计算这些顶点的目标函数值，取最大的最为最优值，其相应的顶点坐标就是最优解。但当、较大时，这种方法是不可行的。,综上所述，若线性规划的可行解集非空且有界，则一定有最优解；若可行解集无界，则线性规划可能有最优解，也可能没有最优解。若线性规划具有无界解，则可行域一定无界。,22,（4）几个定理22,1.3.4,普通单纯形法,单纯形计算方法是一种逐步逼近最优解的迭代方法。其思路是从线性方程组中找出一个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形，逐步迭代直到目标函数实现最大值或最小值为止。,普通单纯形法是最基本最简单的一种方法，它假定标准型系数矩阵中可以观察得到一个可行基（通常是一个单位矩阵或个线性无关的单位向量组成的矩阵），可以通过解线性方程组求得基本可行解，进一步迭代直到求得最优解。,23,1.3.4 普通单纯形法单纯形计算方法是一种逐步逼近最优解,【,例,1.8,】,用单纯形法求下列线性规划的最优解：,24,【例1.8】用单纯形法求下列线性规划的最优解：24,25,25,1.3.5,大,M,和两阶段单纯形法,大,M,单纯形法的基本思想是：约束条件加入人工变量后，,求极大值时，将目标函数变为,求极小值时，将目标函数变为,26,1.3.5 大M和两阶段单纯形法大M单纯形法的基本思想是：,【,例,1.13,】求解线性规划,解,将数学模型化为标准形式,由于该标准型中系数矩阵没有,阶单位矩阵，因此需要在第二个方程中加入人工变量,，目标函数中加上,，得到,27,【例1.13】求解线性规划解 将数学模型化为标准形式由于该,因此该问题的最优解,，最优,。由于最优解中含有人工变量,，说明这个解是伪最优解，是不可行的，也即原问题无可行解,28,因此该问题的最优解，最优。由于最优解中含有人工变量，说明这个,两阶段单纯形法与大,M,单纯形法的目的类似，将人工变量从基变量中换出，以求得原问题的初始基本可行解。将问题分为以下两个阶段：,第一阶段：给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数并实现其最小化，即 。,第二阶段：将第一阶段计算得到的最终表除去人工变量，并且将目标函数行的系数换为原问题的目标函数系数，作为第二阶段计算的初始表。,当第一阶段的最优解 时，说明找到了原问题的一组基本可行解；反之当 时，说明还有不为零的人工变量是基变量，则原问题无可行解。,29,两阶段单纯形法与大M单纯形法的目的类似，将人工变量从基变量中,【,例,】用两阶段单纯形法求解线性规划。,解,标准型为,30,【例】用两阶段单纯形法求解线性规划。 解 标准型为30,在第二、三约束中分别加入人工变量 ， 后，构造第一阶段问题,用单纯形法求解，得到第一阶段问题的计算表,1-9,。,(,下页,),31,在第二、三约束中分别加入人工变量 ， 后，构造第,32,32,在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检验数，必须换成原问题的检验数，可用公式计算。此外，即使第一阶段最优值，也只能说明原问题有可行解，第二阶段问题不一定有最优解，即原问题可能有无界解。,大,M,单纯形法和两阶段单纯形法每一步迭代的方法类似，最后结果相同。,33,在第二阶段计算时，初始表中的检验数不能引用第一阶段最优表的检,1.3.6,退化与循环,单纯形法计算中用最小比值规则确定出基变量时，有时存在两个或两个以上相同的最小比值，使得基本可行解中存在基变量等于零，称为退化基本可行解。这时将该等于零的基变量换出，迭代后目标函数值不变。,34,1.3.6 退化与循环单纯形法计算中用最小比值规则确定出基变,【,例,1.16,】求解线性规划,解,用大,M,单纯形法，加入人工变量,，,得到数学模型,用单纯形法求解见表,1-12,（下页）,35,【例1.16】求解线性规划解 用大M单纯形法，加入人工变量,36,36,由表,1-12,（,3,）和（,5,）得到退化基本最优解 最优值 。,观察该表可知，表,1-12,（,2,）中的最小比值相同，导致出现退化。若选择表,1-12,（,2,）中的 出基，则可直接得到表,1-12,（,5,）。虽然表,1-12,（,3,）和（,5,）的最优解从数值上看相同，但它们是两个不同的基本可行解，对应于同一个极点。,有人构造了一个特例，当出现退化解时，进行多次迭代后又回到初始表，继续迭代出现了无穷的循环，即永远得不到最优解。单纯形法迭代对于大多数退化解是有效的，实际中几乎不会出现循环现象，如有相同的比值，则任意选择出基变量，不必考虑出现循环的结果。,37,由表1-12（3）和（5）得到退化基本最优解,1.4,单纯形法的计算公式,设线性规划,将上述常用公式总结如下：,38,1.4 单纯形法的计算公式设线性规划将上述常用公式总结如下,39,39,1.5,线性规划在道路交通方面的应用,【,例,1.18,】,最小费用集合料问题,某筑路工地需,10000m3,混合集料作为道路基层，拟从附近两个弃土堆取料，从弃土堆,A,取料的装载运输费为,1.0,元,/ m3,，从弃土堆,B,取料的装载运输费为,1.4,元,/ m3,。问如何取料才使总的费用最少。已知弃土堆,A,的材料成分为：砂含量,30%,，砾石含量,70%,；弃土堆,B,的材料成分为：砂含量,60%,，砾石含量,30%,，粘土含量,10%,。混合集料的成分要求为：砂含量,50%,，砾石含量,60%,，粘土含量,80%,。,【,例,1.19,】,截料优化问题,某桥梁工地要制作,100,套钢桁架，因构造要求，需将角钢截成,3,种不同规格的短料：,2.9m,、,2.1m,、,1.5m,。已知每根原料长,7.4m,，试问怎样截料才能使用料最少。,40,1.5 线性规划在道路交通方面的应用【例1.18】最小费,【,例,1.21,】,多阶段投资问题,某客运公司在今后五年内考虑将,10,万元资金给下列项目投资，已知，,项目,A,：从第一年到第四年每年年初需要投资，并于次年末回收本利,115%.,项目,B,：第三年初需要投资，到第五年末能回收本利,125%,，但规定最大投资额不超过,4,万元。,项目,C,：第二年初需要投资，到第五年末能回收本利,140%,，但规定最大投资额不超过,3,万元。,项目,D,：四年内每年初可购买公债，于当年末归还，并加利息,6%,。,试问应如何投资能使第五年末拥有的资金的本利总额为最大,41,【例1.21】多阶段投资问题 某客运公司在今后五年内考虑将1,
展开阅读全文