单纯形法只能求最大值吗

发布于 2020-08-01 05:52:45 浏览 286 次

前述

详情

问题解析：

【】

1、单纯形法是针对求解线性规划问题的一个算法，这个名称里的'单纯形'是代数拓扑里的一个概念，可以简单将'单纯形'理解为一个凸集，标准的线性规划问题可以表示为:垍 2、 min（or max） f(x)=cx垍 3、 s.t. Ax=b 4、 x>=0,b>=0 5、以上形式称为线性规划标准型，使用单纯型法时，如果约束条件含有不等式时需新增变量（松弛变量、人工变量）转化为标准型，min. f(x)=cx指求函数最小值（也可以是求最大值），x是一个Rn维向量代表有n个变量，线性规划问题主要是面向实际问题，x变量可以代表距离、成本、价格、数量等，线性规划问题中要求x大于等于0，c同样是一个Rn维向量，这样cx实际上就是一个线性函数f(x);s.t.代表subject to代表服从于意思，这里是指变量x需要满足的约束条件，A是一个Rm*n维矩阵，代表有m个等式约束。下面是一个约束是不等式的情形: 6、 min -4x1-x2垍 7、 s.t. -x1+2x2<=4 8、 2x1+3x2<=12 9、 x1-x2<=3垍 10、 x1,x2>=0 11、求解上面这个问题只要初中数学知识即可，具体可以使用代数法或几何的方法轻松得到，考虑到实际问题当中变量x是多维的，约束条件也会比示例多的多，这就需要一个一劳永逸的算法能通过计算机来获得正解，单纯形法就是这样的一个算法。单纯形法最早由 George Dantzig于1947年提出，单纯形法对于求解线性规划问题是具有跨时代意义的，其实不仅仅是针对线性规划，非线性规划问题在求解的过程中也大量依赖单纯形法，垍