单纯形法求最小值最大值区别
发布于 2020-05-28 18:15:13
浏览 289
详情:
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年提出,单纯形法对于求解线性规划问题是具有跨时代意义的,其实不仅仅是针对线性规划,非线性规划问题在求解的过程中也大量依赖单纯形法,垍
上一篇:请问高岭土价格
下一篇:什么是酒曲