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