单纯形法课程论文

最优化方法课程论文 题目：单纯形法的发展及其应用 系别：理学院 专业：信息与计算科学 姓名： 班级：信息 101 班 单纯形法的发展及其应用 一 单纯形法简介： 单纯形法，求解线性规划问题的通用方法。单纯形是美国数学 家 G.B.丹齐克于 1947 年首先提出来的。它的理论根据是：线性规 划问题的可行域是 n 维向量空间 Rn 中的多面 凸集，其最优值如果 存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可 行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行 鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进 的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因 基本可行解的个数有限，故经有限次转换必能得出问题的最优解。 如果问题无最优解也可用此法判别。 二 单纯形法在线性规划中的应用 1.单纯形法解线性规划问题 在生产管理和经济活动中，经常遇到这些问题，如生产计划问 题，即如何合理利用有限的人、财、物等资源，以便得到最好的经 济效果；材料利用问题，即如何下料使用材最少；配料问题，即在 原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何 用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方 案，使总运费最小；投资问题，即从投资项目中选取方案，使投资 回报最大等等。对于这些问题，都能建立相应的线性规划模型。事 实上，线性规划就是利用数学为工具，来研究在一定条件下，如何 实现目标最优化。单纯形法是求解线性规划问题的通用方法。 (1)单纯形法解线性规划问题的理论根据是： 线性规划问题的可行域是 n 维向量空间 Rn 中的多面凸集，其 最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解 称为基本可行解。 (2)单纯形法的基本思想是： 先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不 是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不 是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限 次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 (3)单纯形法的一般解题步骤可归纳如下： 把线性规划问题的约束方程组表达成典范型方程组，找出基本 可行解作为初始基本可行解。若基本可行解不存在，即约束条件 有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作 为起点，根据最优性条件和可行性条件，引入非基变量取代某一基 变量，找出目标函数值更优的另一基本可行解。按步骤 3 进行迭 代,直到对应检验数满足最优性条件（这时目标函数值不能再改善） ， 即得到问题的最优解。若迭代过程中发现问题的目标函数值无界， 则终止迭代。 (4)概述 根据单纯形法的原理，在线性规划问题中，决策变量（控制变 量）x1，x2，x n 的值称为一个解,满足所有的约束条件的解称为 可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。 这样，一个最优解能在整个由约束条件所确定的可行区域内使目标 函数达到最大值（或最小值）。求解线性规划问题的目的就是要找 出最优解。 最优解可能出现下列情况之一：存在着一个最优解；存在 着无穷多个最优解；不存在最优解，这只在两种情况下发生，即 没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负 的方向无限增大）。 单纯形法的一般解题步骤可归纳如下：把线性规划问题的约 束方程组表达成典范型方程组，找出基本可行解作为初始基本可行 解。若基本可行解不存在，即约束条件有矛盾，则问题无解。 若基本可行解存在，从初始基本可行解作为起点，根据最优性条件 和可行性条件，引入非基变量取代某一基变量，找出目标函数值更 优的另一基本可行解。按步骤 3 进行迭代 ,直到对应检验数满足最 优性条件（这时目标函数值不能再改善），即得到问题的最优解。 若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束 条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件 在计算机上求解，对于具有 106 个决策变量和 104 个约束条件的 线性规划问题已能在计算机上解得。 2.线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式 所谓标准形式是指下列形式： njjxcz1ma),2(01njxmibtsjnji 当实际模型非标准形式时，可以通过以下变换化为标准形式： 当目标函数为 时，可令 Z=-Z，而将其写成为njjxcz1injjxcz1mi 求得最终解时，再求逆变换 Z=-Z即可。 当 st中存在 形式的约束条件时，iniii bxaxa21 可引进变量 0)(121n niiiixxxb 便写原条件成为01 12n iniiixbxaa 其中的 xn+1称为松驰变量，其作用是化不等式约束为等式约束。 同理，若该约束不是用“”号连接，而是用“”连接，则 可引进松驰变量 0)(121n iniiixbxaxa 使原条件写成011n iniixbxa 3.单纯形法迭代原理 （1） 确定初始可行解 当线性规划问题的所有约束条件均为号时，松弛变量 对应的系数矩阵即为单位矩阵，以松弛变量为基变量可 确定基可行解。 对约束条件含号或=号时，可构造人工基，人为产生 一个 mm 单位矩阵用大 M 法或两阶段法获得初始基可 行解。 （2） 最优性检验与解的判别（目标函数极大型） 当所有变量对应的检验数均非正时，现有的基可行解即 为最优解。若存在某个非基变量的检验数为零时，线性 规划问题有无穷多最优解；当所有非基变量的检验数均 严格小于零时，线性规划问题具有唯一最优解。 若存在某个非基变量的检验数大于零，而该非基变量对 应的系数均非正，则该线性规划问题具有无界解（无最 优解） 。 当存在某些非基变量的检验数大于零，需要找一个新的 基可行解，基要进行基变换。 4.确定初始可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初始的 可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨 论方便，不妨假设在标准型线性规划中，系数矩阵中前 m 个系数 列向量恰好构成一个可行基，即=（） ，其中 =（1，2，m）为基变量 x1，x2，xm 的系数列向量构成 的可行基，=(m+1，Pm+2， Pn)为非基变量 xm+1，xm+2， xn 的系数列向量构成的矩阵。 所以约束方程 就可以表示为AX=bBNNXA=()+=b 用可行基的逆阵-1 左乘等式两端，再通过移项可推得：-1BNX=b 若令所有非基变量 ，则基变量NX=0-1BX=b 由此可得初始的基本可行解 1 5.最优性检验 假如已求得一个基本可行解 ，将这一基本可行解代入 1BbX=0 目标函数，可求得相应的目标函数值 1-1BNBbZC()=C0 其中 分别表示基变量和非基变量B12mN+1m2nC=(c,), C=(c,c) 所对应的价值系数子向量。 要判定 是否已经达到最大值，只需将 代-1BZb -1BNX=b 入目标函数，使目标函数用非基变量表示，即： BN-1BNX=C()+(b)+CXm+12-1-1BNBm+,1,nxb() 其中 称为非基变量N 的检验向量，-1NB+1n=C(,) 它的各个分量称为检验数。若 N 的每一个检验数均小于等于 0， 即 N0，那么现在的基本可行解就是最优解。 6.解的判别 定理 1：最优解判别定理 对于线性规划问题 ，若某个基本nmaxZ=CX,DR/A=b,X0 可行解所对应的检验向量 ，则这个基本可行解就是-1NB0 最优解。 定理 2：无穷多最优解判别定理 若 是一个基本可行解，所对应的检验向量 1BbX=0 ，其中存在一个检验数 m+k=0，则线性规划问题-1NBC 有无穷多最优解。 定理 3：无最优解判别定理 若 是一个基本可行解，有一个检验数 ，但是 1BbX=0 m+k0 ，则该线性规划问题无最优解。-1m+kP 7.基本可行解的改进 如果现行的基本可行解不是最优解，即在检验向量 中存在正的检验数，则需在原基本可行解的基础上-1NB=C 寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是： （1）先从检验数为正的非基变量中确定一个换入变量，使它从 非基变量变成基变量（将它的值从零增至正值） 。 （2）再从原来的基变量中确定一个换出变量，使它从基变量变 成非基变量（将它的值从正值减至零） 。 由此可得一个新的基本可行解，由 可知，这样的变换一定能使目标函数值 m+12-1Bm+,1,nxZCb() 有所增加。 8.换入变量的确定-最大增加原则 把基检验数大于 0 的非基变量定为入基变量。若有两个以上的 j0，则选其中的 j 最大者的非基变量为入基变量。 从最优解判别定理知道，当某个 j0 时，非基变量 xj变为基 变量不取零值可以使目标函数值增大，故我们要选基检验数大于 0 的非基变量换到基变量中去（称之为入基变量） 。若有两个以上的 j0，则为了使目标函数增加得更大些，一般选其中的 j最大者 的非基变量为入基变量。 9.换出变量的确定-最小比值原则 把已确定的入基变量在各约束方程中的正的系数除以其所在约 束方程中的常数项的值，把其中最小比值所在的约束方程中的原基 变量确定为出基变量。 即若 lkikik ababx0|mn 则应令 xl 出基。其中 bi 是目前解的基变量取值，aik 是进基 变量 xk 所在列的各个系数分量，要求仅对正分量做比， （这由前述 作法可知，若 aik0，则对应的 xi 不会因 xk 的增加减值而成为出 基变量） 。 10.两阶段法 用大 M 法求解含人工变量的 LP 时，用手工计算不会碰到麻烦， 但用电子计算机求解时，对 M 就只能在计算机内输入一个机器最大 字长的数字，这就可能造成一种计算上的误差，为克服这个困难， 对添加人工变量后的 LP 分两个阶段来计算，称为两阶段法。 第一阶段：不考虑原问题是否存在基可行解，给原 LP 加入人工 变量，并构造仅含人工变量的目标函数 Minw,然后用单纯形法求解， 若得 w=0，说明原 LP 存在基可行解，可进行第二阶段计算，否则， 停止计算。 第二阶段：将第一阶段计算得到的最终单纯形表除去人工变量， 将目标函数行的系数换成原 LP 的目标函数，作为第二阶段计算的初 始表。然后按照前面的方法进行计算。 11.大 M 法 大 M 法首先将线性规划问题化为标准型。如果约束方程组中包 含有一个单位矩阵 I，那么已经得到了一个初始可行基。否则在约 束方程组的左边加上若干个非负的人工变量，使人工变量对应的系 数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位 矩阵为初始基，即可求得一个初始的基本可行解。 为了求得原问题的初始基本可行解，必须尽快通过迭代过程把 人工变量从基变量中替换出来成为非基变量。为此可以在目标函数 中赋予人工变量一个绝对值很大的负系数-。这样只要基变量中还 存在人工变量，目标函数就不可能实现极大化。 以后的计算与单纯形表解法相同，只需认定是一个很大的正 数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明 原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问 题的初始基本可行解。 三 结论 单纯形法的创建标志着线性规划的诞生。单纯形法的创建统一 了以往运输问题和营养问题等的算法，同时推进线性规划理论的发 展。反过来，理论的发展也刺激算法的更新。线性规划在这样理论 与算法相互促进和相互作用中发展。单纯形法有效地提升了数学