Question

单纯形法

Answer 1

作为一名数学系的学生，都没有写过关于数学的总结，正上运筹课，学到单纯形法，所以就把他的求解过程写一下。

我们都知道，一个线性规划问题，求解的办法有很多种，我们应用类似枚举法可以求解基本可行解的个数≤Cm,n个时的题目，但是如果可行解个数增大，我们就面临必须快速解决下面三个问题：

解决方法：

  1.表格第一行，分别为目标函数变量的所有系数

  2.表格第二行，left部分，有三项Cb,Xb,b 。right部分，是所有变量（包括基本变量，剩余变量，松弛变量，人工变量）。

3.表格最后一行，为目标函数-Z。Z的计算：变量的目标函数系数－Cb*约束函数变量的系数，然后求和。

4.中间几行，right部分分别为各约束函数的系数。left部分的Xb的确定，是根据right部分的出现单位矩阵的系数开始记录其变量。Cb是Xb的目标函数中的系数。b为当所有变量（除Xb 变量）为0，算出的结果。

人工变量： 要使我们的目标函数实现最大化，所以人工变量必须从基变量中迅速换出去，否则目标函数不能实现最大化。

求解有两种方法：最小化求解和最大化求解

它们有一定的区别，上述方法用于最大化求解。

最小化问题求解： 进基选择判别数为负最小的那一个，在所有判别数大于等于0时达到最优解

最大化问题求解： 进基变量选取判别数为正的最大的那一个数，在所有判别数小于等于0达到最优解

共同点：离基变量均取比值最小的