运筹学讲义第一章.doc

第一章 线性规划的单纯形法1.1 线性规划的基本概念1. 问题的提出产品设备128台时原料A4016kg原料B0412kg利润2元/件3元/件建立数学模型：设,分别是生产，的件数，则有：这里称为决策变量。目标函数与约束条件关于决策变量是线性的称为线性规划。线性规划的一般形式：2. 线性规划的标准形特点：目标函数求极大；等式约束；变量非负。令则线性规划标准形的矩阵表达式为：约定：如何化标准形：（I） 目标函数实现极大化，即，令，则；（II）约束条件为不等式约束条件为“” 不等式，则在约束条件的左端加上一个非负的松弛变量；约束条件为“” 不等式，则在约束条件的左端减去一个非负的松弛变量。（III）若存在无约束的变量，可令，其中例1 将线性规划化为标准形。3. 基本概念（I）可行域，可行解，最优解对线性规划的标准形称为线性规划的可行域。任意为线性规划的可行解，若存在，使，有 则称为线性规划的最优解，为最优值。（II）基，基向量，基变量，非基变量，基本解，退化的基本解令。因秩，故中存在个线性无关的列，不妨设的前个列线性无关，则称为线性规划的一个基，而称为线性规划的基向量，对应的变量称为基变量，对应的变量成为非基变量。若令，令，则等价于。故有。由此，得到的一个解。这里非零分量的数目不大于，称为线性规划的基本解，若中至少有一个为零，则称为线性规划的退化的基本解。（III）基可行解，可行基，最优基可行解若一个基本解又是可行解，则称为线性规划的基可行解，其对应的基称为可行基。设是线性规划的一个基可行解，若对任意可行解，都有则称是线性规划的一个最优基可行解。（IV）凸集与凸线性组合设，若有则称为凸集。设,则称是的凸线性组合。设是凸集，若不能表示为中不同两点的凸线性组合，则称是凸集。1.2 线性规划的基本定理定理1. 线性规划的可行域是凸集。定理2. 设是线性规划的可行解，则是基可行解的充要条件是的正分量所对应的系数列向量线性无关。证明： 必要性由基可行解的定义可知。 充分性若向量线性无关，则有。当时，它恰好构成线性规划的一个基，从而为相应的基可行解；当时，则一定可以从其余的列向量中取定个与构成其最大线性无关组，其对应的解恰为，且是基可行解。定理3. 线性规划的基可行解对应于可行域的顶点。 证明：必要性。设是基可行解，要证明是可行域的顶点。若不是可行域的顶点，则必存在可行域中不同的两点与及，使 因是基可行解，不妨设的前个分量是正，而其余的为零，这里，因此有 且，由，与，必可推出于是有 上面两式相减，有 而，因此有线性相关，这与线性无关矛盾。充分性。设是可行域的顶点，要证明是基可行解。因是可行域的顶点，不妨设，而0，。若不是基可行解，则由定理1知：线性相关。因此存在不全为0的数，使：而因此有 因，取充分小，必可使。令故有。这与是可行域的顶点矛盾。 证毕。定理4. 若线性规划有可行解，则必有基可行解。证明：证明是构造性的。设是可行解，不妨设的前个分量大于零，而其余的为零，于是有：若线性无关，则是基可行解。若线性相关，则存在不全为零的使不妨设中至少有一个为正。而是可行解，于是有。因此有令于是是可行解，且中至多只有个分量不为0，这里。必要时重复这一过程，最后得到的可行解其正分量所对应的中的列线性无关。证毕。定理5. 若线性规划有最优解，则必有最优基可行解。证明：设为最优解，在定理4证明的基础上补证目标函数值不变即可。即证或由故对充分小，必有，从而可知是可行解。而为最优解，故必有从而有。 证毕。结论：线性规划的可行域是凸集（有界或无界），它们有有限个顶点。线性规划的每个基可行解对应于可行域的一个顶点。若线性规划有最优解，必在可行域的某个顶点达到最优解。1.3 线性规划的图解法（变量2个）例1 有唯一解。例2有无穷多个解，其解为线段上所有点。例3可行域无界，没有最优解。例4无可行解。在时无解。注：出现例3和例4说明线性规划的数学模型有错误，前者缺乏必要的约束条，后者有矛盾的约束条件。1.4 单纯形法基本思路：根据线性规划的标准形，从线性规划的某个基可行解（或可行域的某个顶点）开始，按照一定的规则，转换到线性规划的另一个基可行解（或可行域的另一个顶点），最终使目标函数达到最大值。1 初始基可行解（可行域顶点）的确定若中存在单位阵构成的基，不妨设，而，则的解等价于 于是存在基可行解。2 单纯形表将约束条件中基变量用非基变量表示，即有代入目标函数，则有这里单纯形表100010001000这里是基变量，具体的每个分量写在第1列，是基变量的值，具体的每个分量的值写在第2列。,下面的行是约束条件的系数矩阵的行。最后一行是检验数行，其中基变量,的检验数是0，非基变量的检验数是。3 解的判别定理定理1. 设是线性规划的基可行解，那么（I）若，则是线性规划的最优解；（II）若存在，使，且，则线性规划无最优解；（III）若存在，使，且存在，使，则线性规划需进行迭代运算；（IV）若，且存在，使，则线性规划有无穷多个最优解。证明：（I）因为在此单纯形表中，目标函数： 若，则由于，必有。时，。故是最优解。(II)令，,则。且 ,当时，故该问题的目标函数无上界。（IV）只需将非基变量换入到基变量中（其它基变量不变），找出一个新的基可行解，故目标函数中对应基可行解的目标函数的值仍为，故也是最优解。因此，连线上所有点都是最优解。4 迭代规则 若初始基可行解不是最优解或不能判别其无解时，需要找一个新的基可行解。为此要确定换入变量，再确定换出变量，这样就得到一个新的基可行解。一个非基变量换入成为基变量。一个基变量换出成为非基变量。（I）换入变量的确定若，则非基变量成为基变量.（II）换出变量的确定 则基变量成为非基变量。（III）迭代后的单纯形表 将单纯形表中第1列中的（换出变量）换成（换入变量），然后利用行初等变换将中的第个分量变成1，而其余的分量变为0。具体方法是：将单纯形表中的第行除以，然后用乘以第行后+第行，这样就可得到新的单纯形表。（IV）迭代的合理性已知线性无关，下面要证明线性无关，且。证明： 因为 ，这里。故对，有 即 取 故 若线性相关，则 而 故 即 而 ，故有线性相关，矛盾。5 单纯形法计算步骤 （I）建立初始单纯形表（假设中存在单位阵）； （II）若，则已得到最优解，停止。否则转入下一步； （III）若在中，存在，而，则无最优解，停止。否则转入下一步； （IV）由，确定为换入变量，按规则 可确定为换出变量； （V）以为主元进行迭代 即将 迭代成， 并将单纯形表列中的换成，得到新的单纯形表； 重复（）（）。例1 应用单纯形法求解线性规划b41000400-212010-14000例 2.1.5 线性规划的大M法与两阶段法1 问题的提出若约束条件的系数矩阵中存在单位阵构成的基，则容易得到初始基可行解，否则难确定初始基可行解，因此需要引入人工变量。例如在的两边加入人工变量若经基的变换，基变量中不再含有非零的人工变量，这表示原问题有可行解。若经基的变换，在单纯形表中一直存在非零的人工变量，这表示原问题无可行解。2 大法在一个线性规划问题中加入人工变量后，要求人工变量对目标函数的取值不受影响，为此设人工变量在目标函数中的系数为，这样在求时，必须把人工变量换成非基变量或等于0的基变量。例1. 设有线性规划试用大法求解。解：引入人工变量，有： 将目标函数中的基变量用非基变量来代替，有 于是列出单纯形表： b111-211003-4120-1101-2000014M3-6M-1+M-1+3M0-M00b103-2010-11000-11-21-20100011+M1-1+M00-M01-3Mb12001-22-510100-11-21-201000121000-11-M-1-Mb410010100-11-29001-2000故最优解为 。3 两阶段法用计算机求解含人工变量的线性规划时，若，则造成溢出，故介绍两阶段法。第一阶段： 若，则原问题无可行解； 若，则原问题存在可行解。 第二阶段： 将第一阶段的最终单纯形表除去人工变量，将目标函数行的系数换成原问题的目标函数的系数，并且注意基变量要用非基变量来表示，用此作为第二阶段计算的初始单纯形表。例2. 设有线性规划 试用二阶段法求解。 解：第一阶段b111-211003-4120-1101-200001-46-1-30100b103-2010-11000-11-21-2010001-10-100103b123001-22-510100-11-21-201000100000011第二阶段：b12001-210100-11-2010021000-1b410010100-19001-2000故最优解： 。1.6 单纯形法的评述1 非退化的情况单纯形法换入变量：当检验数有两个以上为正时，就取其中最大者，由此确定换入变量；若同时有多个最大的检验数，则取其中最小的下标为主元的列。换出变量：当按最小比值确定主元的行号时，若同时有多个等值的最小比，则选取其中最小的下标为主元的行号，由此确定换出的变量。定理1.在非退化的情况下，应用单纯形法经过有限次迭代，必可得到最优解或断定原问题无解。2 退化的情况单纯形计算中用规则确定换出变量时，有时存在两个以上相同的最小值，这样在下一次迭代中就有一个或几个基变量等于0，这就出现退化解。这时换出变量，迭代后目标函数不变，这时不同基表示为同一个顶点。例1. 通过6次迭代还原（1955，Beale）。3 避免循环Bland规则（I）由，确定为换出变量；（II）按规则（同单纯形法一致）。定理2.按Bland规则迭代一定可以避免循环。4 单纯形法是非多项式算法设输入数据的规模是（通常与变量及约束数有关），设在最坏情况下运算次数是，这样的称为算法的计算复杂性。多项式算法：是的一个多项式或以多项式为上界；指数算法：是的一个指数式或以指数式为上界。例如：，100万次/秒的一台计算机需0.2秒； 但，100万次/秒的10亿台计算机需100万年。例：1972，Klee and Minty可行域有个顶点，迭代次，指数算法。特别的，n=31982年，Borg