单纯形法

来自计算思维百科
跳转至: 导航搜索
单纯形法1.png

有时候我们需要想办法让一个函数达到最大或最大,单纯形法是用来解决这种线性规划问题的有效方法。

基本概念

单纯形是美国数学家G.B.丹齐克于1947年首先提出来的,从此单纯形法成为线性规划的经典算法。许多问题都可以按照线性规划的实例来建模。

利用单纯形法解决线性规划,涉及到线性规划的标准形式,松弛变量、分离变量和输入变量等名词。以下列线性规划问题为例来解释单纯形法中的各个名词含义。

标准形式:

  • 必须是最大化问题
  • 所有约束必须用线性方程组表示
  • 所有变量必须非负

应用范围

在实际生活中,线性规划无处不在。各类工程实践的规划,城市建设规划,成本控制等个方面都需要用到线性规划,而单纯形法作为其经典解法也被广泛用于各类规划问题中。

使用方法及步骤

  1. 初始化:将给定的线性规划问题表示成标准形式,建立初始表格,表格的最右列都为非负,剩下的m列确定了基本可行解的基本变量,行用基本变量标识。
  2. 最右测试:如果目标行(即用来放解的行)所有数为非负,就停止;表格代表一个最优解,其基本变量在最右列,剩下的非基本变量都为0
  3. 确定输入变量:从目标行中选一个最能影响结果的变量(绝对值最大的负单元格),即为输入变量,这个变量所在列即为主元列。
  4. 确定分离变量:除目标行外,用最右列除以各行得到的输入变量对应的最小的值,这个值确定分离变量,也就是要变成非基本变量的变量,该变量所在行即为主元行。
  5. 建立下一个表格 :将主元行中所有数除以主元得到新主元,包括主元行在内的每一行,利用主元将主元列变为0;将主元行前标识用主元列变量代替,回到第一步。

应用案例

应用1-线性规划问题

案例:某商场为庆祝节日推出了一个节日套餐。其中礼包共有两种类型,礼包一里面包含有1张购物券,1份礼品,价值为3百元;礼包二包含1张购物券,3份礼品,价值为5百元;现要求节日套餐必须包含两种礼包,且须满足购物券不多于4张,礼品不多于6份,问应如何组合礼包套餐,可使得套餐的价值最少?

解决步骤:

这是一个关于两个变量的线性规划问题,

根据题意可以将此抽象成下面的问题:

                             x+y≤4

                      x+3y≤6

                      x≥0, y≥0

求3x+5y的最大值或最小值。

 

在上述线性规划问题中,我们可以引入两个变量u,v来将不等式化为方程组形式即:

                     x+y+u=4

                     X+3y+v=6

                     X,y,u,v≥0

上述形式即为标准形式,且u,v即称作松弛变量,就是用来控制x,y的范围的。

1.初始化建表

单纯形法2.png

2.很显然,目标行中都为负,算法没有结束。

3.在目标行中,y对应的绝对值最大,即为输入变量,主元列即为y所在列

4.在y对应列的各行中,u对应行:4/1=4,v对应行:6/3=2,可以得到v对应行的约束条件更大,所以选择v为分离变量,且v所在行即为主元所在行。新主元变量为y。

5.取v=0,使得y的系数为1,即改行除以y,替换v为y,并替换对应行的系数;再利用新主元去更新u行的系数;再按同样方法做下一次迭代。

单纯形法3.png

直到行对应的变量为x,y,最后一列对应的即为解。

可以体现的计算思维

从上面的分析中容易看出利用单纯形法解决线性规划的过程中,不断生成一系列使问题的目标值不断改进的可行解,是一个不断优化的过程,直到不能在优化了,就得到最终解。体现了计算思维中的规划思想。