下载文档原格式
单纯形法（Simplex Method）是线性规划问题的一种求解方法。
下面我将以一个简单的线性规划问题为例，详细解释如何使用单纯形法求解。
例题：假设我们有一个简单的线性规划问题，目标是最小化目标函数 z = 3x + 2y，约束条件是 x + y <= 10, x >= 0, y >= 0。
首先，我们需要构建问题的数学模型。
数学模型可以表示为以下形式：z = 3x + 2yx + y <= 10x >= 0y >= 0然后，我们可以将这个线性规划问题表示为一个单纯形表。
单纯形表的形式如下：| c | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ||---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---||x | y | z | u | v | w | x1 | x2 | x3 | ... | xn | s.x | s.y | s.z | c.val | b.x | b.y | b.z | dual.val | dual.x1 | dual.x2 | ... | dual.xn ||在这个表中，c 是目标函数的系数，b 是约束条件的系数，s 是松弛变量的系数，dual 是对偶问题的系数，c.val 是当前解的目标函数值，b.x, b.y, b.z 是约束条件的边界值，s.x, s.y, s.z 是松弛变量的值。
现在，我们可以将例题中的数据填入单纯形表：c = [3, 2, 1]b = [1, 0, -10]s = [1, 1, 0]dual = []然后，我们可以开始迭代求解。
在每一次迭代中，我们首先找到进入变量和离开变量，然后更新单纯形表中的数据。
P79，用单纯形法的表格形式求解第二章例1 1：
在上表中有一个m*m 的单位矩阵，对应的基变量为s 1,s 2,s 3；
●
在s 1,s 2,s 3右边的C B 列中填入这些基变量的目标函数中相应的系数。
●
2：
← 在z j 行中填入第j 列与c B 列中对应的元素相乘相加所得的值，如z 2=0*1+0*1+0*1=0，所在z i 行中的第2位数填入0；
← 在 j j j z c -=σ 行中填入c j -z j 所得的值，如 050c 111-=-=z σ，01002-=σ，003-=σ，004-=σ，005-=σ
← z 表示把初始基本可行解代入目标函数求得的目标函数值，即b 列*c B 列；
3：
4.
5.
6.
初始基本可行解为s1=300,s2=400,s3=250,x1=0,x2=0;
←由于250/1最小，因此确定s3为出基变量；
σ>2σ，因此确定x2为←由于1
入基变量。
出基变量所在行，入基变量所在列的交汇处为主元，这里是a32=1，在表中画圈以示区别.
7：
●第一次迭代，其变量为x2,s1,s2,通过矩阵行的初等变换，求出一个新的基本可行解。
●具体的做法：用行的初等变换使得x2的系数向量p2变换成单位向量，
由于主元在p2的第3 分量上，所以这个单位向量是()T
e1，
=，也就是主元
0，
3
素变成1。
在上表中第3个基变量s3已被x2代替，故基变量列中的第3个基变量应变为x2。
由于第0次迭代表中的主元a32已经为1，因此第3行不变。
为了使第1行的a12为0，只需把第3行*(-1)加到第1行即可。
同样可以求得第2行。
8：
求得第1次迭代的基本可行解为
s 1=50,s 2=150,x 2=250,x 1=0,s 3=0, z=25000.
● 从上表可以看出，第一次迭的501=σ>0 ，因此不是最优解。
设x 1为入基变量，从此值可知b 1/a 11=50为最小正数，因此，s 1为出基变量，a 11为主元，继续迭代如下表所示。
●。
