1 算法分析
1.1单纯形算法
1.1.1单纯形法的基本思路
利用求线性规划问题基本可行解（极点）的方法求解较大规模的问题是不可行的。
有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。
在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。
由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。
1.1.2单纯形法的基本步骤描述
第1步：求初始基可行解，列出初始单纯形表。
对非标准型的线性规划问题首先要化成标准形式。
由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵()12,,,m P P P ，
以此作为基求出问题的一个初始基可行解。
为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。
为了书写规和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表(见表1-1)。
迭代计算中每找出一个新的基可行解时，就重画一单纯形表。
含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。
第2步：最优性检验。
表1-1单纯形表
如表中所有检验数c j -z j ≦0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。
当表中存在c j -z j >0时，如有P j ≦0，则问题为无界解，计算结束；否则转下一步。
第3步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。
1.确定换入基的变量。
只要有检验数δj >0，对应的变量x j 就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个δk ，其对应的变量x k 作为进基变量。
2.确定出基的变量。
min |0i r ik
ik
rk
b b a a a θ⎧⎫⎪=>=⎨⎬⎪⎭⎩确定x r 是出基变量,a rk 为主元。
3.用进基变量x k 替换出基变量x r ，得到一个新的基()111,
,,,,
,r k r m P P P P P -+。
对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表(表1-2)。
(1) 把第r 行乘以rk
a 1
之后的结果填入新表的第r 行；对于r i ≠行，把第r 行乘以⎪⎭
⎫ ⎝
⎛-rk ik
a a 之后与原表中第
i 行；在B x 列中的r 行位置填入k x ，其余行不变；在B
c
列中用k c 代替r 行原来的值，其余的行与原表中相同。
(2) 然后用j x 的价值系数j c 减去B c 列的各元素与j x 列各对应元素的乘积，把计算结果填入j x 列的最后一行，得到检验数j δ，计算并填入Z '-的值（以零减去B c 列各元素与b 列各元素的乘积）[1]。
第4步：重复上述过程，就可以得到最优解或判断出无有限最优解。
表1-2初始单纯形表
1.1.3单纯形算法求解线性规划的例
在实践中，根据实际问题的要求，常常可以建立线性规划问题的数学模型。
下面这个例，就是一个用单纯形算法求解的线性规划的例。
美佳公司计划制造甲,乙两种家电产品。
但因财力、物力等原因，资源有限，已知制造一个家电产品分别占用的设备A ，B 的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表1-3所示。
问该公司应制造两种家电各多少件，使获取的利润为最大。
,,,,5
24261552Max 5432152
14
213
22
1≥=++=++=++=x x x x x x x x x x x x x s.t
x x Z 表1-3 产品有关数据表
解：根据题意构建下列线性规划模型：
目标函数 约束条件
用单纯形法求解线性规划问题，标准化后得：
取初始基本可行解()I p p p x x x x x ======54354321,,,5,24,15,0（单位矩阵）。
初始化单纯形表并计算的过程如表1-4所示。
在最优单纯形表中，非基变量54,x x 的检验数均为负数，于是得到最优解
T
x ⎪
⎭⎫ ⎝⎛=0,0,215,23,27*
，最优目标值
218*=Z 元（表中-17/2为-Z 的值）。
为了能够更清晰地看清单纯形算法的解题思路以及单纯形算法表格计算过程中表格各量的关系，把例中的3次迭代计算过程重述如下：
第一次迭代：
取初始可行基()543,,p p p ，那么543,,x x x 为基变量，21,x x 为非基变量。
将基变量
,524261552Max
21212122
1>≤+≤+≤+=x x x x x x x s.t.
x x Z
和目标函数用非基变量表示：
第二次迭代：
当前的可行基()531,,p p p ，那么531,,x x x 为基变量，42,x x 为非基变量。
将基变量和目标函数用非基变量表示：
4252
3421426
16415156
162431
318x x x x x x x x x x Z +-
=-=--=-+= 第三次迭代：
当前的可行基()321,,p p p ，那么321,,x x x 为基变量，54,x x 为非基变量。
将基变量和目标函数用非基变量表示：
5
4
35
4
25
4
154215452
1523
4123
2
1412
72141217x x x x x x x x x x x Z +-=
-+=
+-=
-
-
=
在目标函数542
1
41217x x Z --=
中，非基变量54,x x 的检验数不是正数，于是得到最
优解T
x ⎪
⎭⎫
⎝⎛=0,0,215,23,27*,最优目标值
218*=Z 。
2
152142
32
152********x x x x x x x x x
x Z --=--=-=+=
表1-4 单纯形表表格计算过程
在最优单纯形表中，非基变量
5
4,x x 的检验数均为负数，于是得到最优解
T
x ⎪⎭⎫
⎝⎛=0,0,215,23,27*
，最优目标值218
*=Z 元（表中-17/2为-Z 的值）。
1.2大M 单纯形算法
1.2.1大M单纯形算法的基本思想
一般线性规划问题的系数矩阵中不含单位矩阵，这时没有明显的基本可行解，常常采用引入非负人工变量的方法来求得初始基本可行解，一般采用大M单纯形算法。
大M法也称为惩罚法，主要做法是取M>0为一个任意大的正数，在原问题的目标函数中加入-M乘以每一个人工变量。
首先根据不等式符号添加正的或负的松弛变量，查找加入的松弛变量是否构成单位矩阵，构成单位矩阵则计算方法和单纯形算法一样；若是尚未构成单位矩阵，则添加的人工变量与松弛变量构成一个单位矩阵后进行计算。
松弛变量在目标函数中的系数为0，而人工变量的系数则为-M，此处-M 是强加于人工变量的一种惩罚，其目的是为了强制人工变量由变量转换为非基变量，使之恢复原问题或者说与原问题等价。
M在计算时，可看作一个任意大的正数，非严格的说法，仅为便于在检验数含M时判断值的正负，但M并不是无穷大，理论上可以证明，M只要取到某个数值以上就可以。
1.2.2大M单纯计算法的基本步骤描述
1.添加松弛变量，看松弛变量的系数是否构成单位矩阵，若尚未构成单位矩阵则加入人工变量，迫使人工变量的系数和松弛变量的系数构成单位矩阵。
这也是添加人工变量的目的。
2.加入松弛变量和人工变量后就完成了标准化线性规划模型。
3.计算标准化后的线性规划模型的方法是应用单纯形算法，所以大M单纯形算法的迭代计算方法和单纯形算法的计算方法相同。
4.大M单纯形算法中含有人工变量系数“-M”，加入人工变量的目的是构成单位矩阵，应用单纯形算法迭代计算，但是不能改变原问题，因此让每个人工变量乘以“-M”，就能够保证标准化后的线性规划模型与原问题等价。
5.“-M”作为字符不能参与计算，然而M作为一个任意大的正数，一般在教学中所要解决的线性规划模型规模并不太大，因此取值M=10000参与计算。
计算过程中的所有“M”都有10000代替。
参考文献
[1] 吴祈宗.运筹学（第2版）[M].机械工业
[2] 胡运权.运筹学教程（第二版）.清华大学
[3] 胡运权.运筹学导论（第8版）.清华大学
[4] 单东林，晓菲，然.锋利的Jquery.人民邮电
[5] 大藤幹，半场方人.HTML&CSS&JavaScript语法辞典.中国青年
[6] 石磊.关于运筹学课程教学改革的几点思考.教育学院学报，2010年2期
[7] 唐开元，王华.浅析运筹学与计算机技术的结合.才智，2009年06期。