1、01 算法分析1.1单纯形算法1.1.1单纯形法的基本思路利用求线性规划问题基本可行解（极点）的方法求解较大规模的问题是不可行的。有选择地取基本可行解，即从可行域的一个极点出发，沿着可行域的边界移动到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。在线性规划的可行域中先找出一个可行解，检验它是否为最优解，如果是最优解，计算停止；如果不是最优解，那么可以判断线性规划无有限最优解，或者根据一定步骤得出使目标函数值接近最优值的另一个基本可行解。由于基本可行解的个数有限，所以总可以通过有限次迭代，得到线性规划的最优基本可行解或判定线性规划无有限最优解。1.1.2单纯形法的基本步骤描述第 1
2、 步：求初始基可行解，列出初始单纯形表。对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约束方程的系数矩阵中包含一个单位矩阵 ，以此作为基求出问题的一个初始基12,mP可行解。为检验一个基可行解是否最优，需要将其目标函数值与相邻基可行解的目标函数值进行比较。为了书写规范和便于计算，对单纯形法的计算设计了一种专门表格，称为单纯形表(见表 1-1)。迭代计算中每找出一个新的基可行解时，就重画一张单纯形表。含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表。第 2 步：最优性检验。1表 1-1 单纯形表cj c1 cm cj cnCB 基 b x1 xm xj xn
3、c1c2cmx1x2xmb1b2bm100001a1ja2jamja1na2namncj-zj 0 0 1mjijc 1mnic如表中所有检验数 cj-zj0，且基变量中不含有人工变量时，表中的基可行解即为最优解，计算结束。当表中存在 cj-zj 0 时，如有 Pj0，则问题为无界解，计算结束；否则转下一步。第 3 步：从一个基可行解转换到相邻的目标函数值更大的基可行解，列出新的单纯形表。1.确定换入基的变量。只要有检验数 j0，对应的变量 xj 就可作为进基的变量，当有一个以上检验数大于零时，一般从中找出最大一个 k，其对应的变量 xk 作为进基变量。2.确定出基的变量。 确定 xr是出基变
4、量,a rk 为主元。min|0irkkba3.用进基变量 xk 替换出基变量 xr，得到一个新的基 。11,rkrmPP 对应这个基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表(表1-2)。(1) 把第 r 行乘以 之后的结果填入新表的第 r 行；对于 行，把第 r 行rka1 ri乘以 之后与原表中第 i 行；在 列中的 r 行位置填入 ，其余行不变；在rkiaBxkx2列中用 代替 r 行原来的值，其余的行与原表中相同。Bck(2) 然后用 的价值系数 减去 列的各元素与 列各对应元素的乘积，把计jxjcBjx算结果填入 列的最后一行，得到检验数 ，计算并填入 的值（以零减
5、去j jZ列各元素与 b 列各元素的乘积） 1。Bc第 4 步：重复上述过程，就可以得到最优解或判断出无有限最优解。表 1-2 初始单纯形表cj c1 cr cm cj ck CB 基 b x1 xr xm xj xk c1ckcmx1xkxmrka rkb mrka1001krarkmrka0011rjjkabrjka rjmjk010cj- zj 0 krcz 0 rjjkaczz 0 1.1.3单纯形算法求解线性规划的范例在实践中，根据实际问题的要求，常常可以建立线性规划问题的数学模型。下面这个范例，就是一个用单纯形算法求解的线性规划的范例。美佳公司计划制造甲,乙两种家电产品。但因财力、
6、物力等原因，资源有限，已知制造一个家电产品分别占用的设备 A，B 的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件的获利情况，如表 1-3 所示。问该公司应制造两种家电各多少件，使获取的利润为最大。30,5242615Max5432131xxs.txZ表 1-3 产品有关数据表项目 甲 乙 每天可用能力设备 A（h ） 0 5 15设备 B(h) 6 2 24调试工序(h) 1 1 5利润（元） 2 1解：根据题意构 建下列线性规划模型：目标函数 约束条件用单纯形 法求解线性规划问题，标准化后得：取初始基本可行解 （单位矩阵）Ipxxx 54354321 ,2,1,0。初始化
7、单纯形表并计算的过程如表 1-4 所示。在最优单纯形表中，非基变量 的检验数均为负数，于是得到最优解54,，最优目标值 元（表中-17/2 为-Z 的值） 。Tx0,2153,7* 218*Z为了能够更清晰地看清单纯形算法的解题思路以及单纯形算法表格计算过程中表格内各量的关系，把例中的 3 次迭代计算过程重述如下：0,5246Max11xs.tZ4第一次迭代：取初始可行基 ，那么 为基变量， 为非基变量。将基变543,p543,x21,x量和目标函数用非基变量表示：第二次迭代：当前的可行基 ，那么 为基变量， 为非基变量。将基变531,p531,x42,x量和目标函数用非基变量表示：4253
8、42161438xxxZ第三次迭代：当前的可行基 ，那么 为基变量， 为非基变量。将基变321,p321,x54,x量和目标函数用非基变量表示：543254121537xxxxZ在目标函数 中，非基变量 的检验数不是正数，于是得到54217Z4,21542316xxxZ5最优解 ,最优目标值 。Tx0215,37* 218*Z表 1-4 单纯形表表格计算过程2 1 0 0 0cB xB bX1 X2 X3 X4 X50 X3 15 0 5 1 0 0 -0 X4 24 6 2 0 1 0 40 X5 5 1 1 0 0 1 5-Z 0 2 1 0 0 00 X3 15 0 5 1 0 0 32
9、 X1 4 1 2/6 0 1/6 0 37/30 X5 1 0 4/6 0 -1/6 1 4/3-Z -8 0 1/3 0 -1/3 00 X3 15/2 0 0 1 5/4 -15/2 -2 X1 7/2 1 0 0 1/4 -1/2 -1 X2 3/2 0 1 0 -1/4 3/2 4/3-Z -17/2 0 0 0 -1/4 -1/2在最优单纯形表中，非基变量 的检验数均为负数，于是得到最优解54,x6，最优目标值 元（表中-17/2 为-Z 的值） 。Tx0,2153,7* 218*Z1.2大 M单纯形算法1.2.1大 M单纯形算法的基本思想一般线性规划问题的系数矩阵中不含单位矩阵，
10、这时没有明显的基本可行解，常常采用引入非负人工变量的方法来求得初始基本可行解，一般采用大 M 单纯形算法。大 M 法也称为惩罚法，主要做法是取 M0 为一个任意大的正数，在原问题的目标函数中加入-M 乘以每一个人工变量。首先根据不等式符号添加正的或负的松弛变量，查找加入的松弛变量是否构成单位矩阵，构成单位矩阵则计算方法和单纯形算法一样；若是尚未构成单位矩阵，则添加的人工变量与松弛变量构成一个单位矩阵后进行计算。松弛变量在目标函数中的系数为 0，而人工变量的系数则为-M，此处 -M 是强加于人工变量的一种惩罚，其目的是为了强制人工变量由变量转换为非基变量，使之恢复原问题或者说与原问题等价。M 在
11、计算时，可看作一个任意大的正数，非严格的说法，仅为便于在检验数含 M 时判断值的正负，但 M 并不是无穷大，理论上可以证明，M 只要取到某个数值以上就可以。1.2.2大 M单纯计算法的基本步骤描述1.添加松弛变量，看松弛变量的系数是否构成单位矩阵，若尚未构成单位矩阵则加入人工变量，迫使人工变量的系数和松弛变量的系数构成单位矩阵。这也是添加人工变量的目的。2.加入松弛变量和人工变量后就完成了标准化线性规划模型。3.计算标准化后的线性规划模型的方法是应用单纯形算法，所以大 M 单纯形算法的迭代计算方法和单纯形算法的计算方法相同。4.大 M 单纯形算法中含有人工变量系数“-M” ，加入人工变量的目的
12、是构成单7位矩阵，应用单纯形算法迭代计算，但是不能改变原问题，因此让每个人工变量乘以“-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 期
