运筹学：C4单纯形计算步骤

1、上节内容回顾一线性规划与单纯形法单纯形法找出一个初始可行解找出一个初始可行解是否最优是否最优转移到另一个目标函数转移到另一个目标函数（找更大的基本可行解（找更大的基本可行解）最优解最优解是是否否循循环环直到找出为止，核心是：变量迭代直到找出为止，核心是：变量迭代结束结束单纯形法步骤：问题1问题2问题31.3.2初始基可行解的确定u问题1：找初始顶点？u问题2：判断最优？u问题3：转换到另一顶点？11 max (1-20) (1-21() 01,21),njjjnjjjjZc xP xbxjn，u 找初始顶点分三种情况来进行：123(1,2, )()1 0 0,0 1 00 0 1jPPjBP

2、Pn从中若能直接观察到，由此得到初始基可行解。1.3.2初始基可行解的确定 (1,2,;1,2, )jijxa im jn对所有约束条件是“ ”形式的不等式，在每个约束条件的左端加一个松（2）弛变量。重新对 及进行编号，得11,111122,1122,11 mmnnmmnnmm mmmnnmxaxa xbxaxa xbxaxaxb（1-23）转化为第一种情况。得到其初始基可行解。T12( ,0,0)mXb bb1.3.2初始基可行解的确定对等式约束加上一个非负的人工变量；对不等式约束减去一个非负的剩余变量（变为等式约束），再加上一个非负的人工变量。 (3) 对所有约束条件是“ ”形式的不等式及

3、等式约束情况，若不存在单位矩阵时，采用人造基方法:详细情况第五节讨论。1.3.3最优性检验与解的判别u问题1：找初始顶点？u问题2：判断最优？u问题3：转换到另一顶点？对于这四种情况都要根据相应准则判断出来。LPLP解的情况解的情况唯唯 一一 解解无无 穷穷 解解无无 界界 解解无可行解无可行解有最优解有最优解无最优解无最优解1.3.3最优性检验与解的判别将(1-24)代入(1-20),目标函数变成1 (1,2,) (1-24)niiijjj mxba xim111() (1-25)mnmiijiijjij mizcbcc a x经过迭代后，(1-23)式变成11001 1, mjjiijim

4、njiij miizcbjcc amnz zx令，则， (1-27)=1.3.3最优性检验与解的判别1mjjiijicc a为判断解情况的依据！称之为检验数。(0)(0)T12( ,0,0)10,mjXb bbBjmnX若为对应于基 的一个基可行解，且对于一切 ，(1)最优解判别定理，则为有最优解。(0)T1200,( ,0,0)1,mjm kXb bbjmn若为一个基可行解，对(2)无穷多最优解判别定理，又存在某个非基变量于一切的检验数则有无穷多 ，有最优解。(0,)T120,1,2,0( ,0,0)mm ki m kimbaXbb若为一个基可行(3)无界解判别定理有一个且对于，有，那么无解

5、，有界解。1.3.45基变换（迭代、旋转运算）u问题1：找初始顶点？u问题2：判断最优？u问题3：转换到另一顶点？11,111,1122,112,22,11, mmkknnmmkknnll mml kklnnlxaxa xa xbxaxaxa xbxaxa xa xb考虑如下形式的方程组,11, mm mmm kkmnnmxaxaxaxb（1-33）1.3.45基变换（迭代、旋转运算）(0)0max(0),jjkkjXx（1）若基可行解不是最优解，确定换入变量 由最优解判别定理则：。存在设则对应的 为换入变量。111,222,= kkkkklll kkmmm kkxxba xxbaxxba x

6、xbax确定换（2）确定 为换入变量后，在(1-33)中令其它非基变出量为零,得变量,=min(), kiii kkilii kl klxxba xbbaax考虑到变量的非负性要求，即在在由零开始增大时，应始终保持非负。第一个达到零的变量即为换出变量。若则 为换出变量。1.3.45基变换（迭代、旋转运算）1,11,112,12,22,1,1, 1 1 1 1 mknmknl ml klnnlm mm kaaabaaabaaa x baa对增广矩阵 mnmab（1-34）进行初等行变换，得到新的增广矩阵，继而得到新的基可行解，最后得到新的目标函数及检验数。以上过程反复进行。本节内容摘要一一线性规

7、划与单纯形法线性规划与单纯形法1.单纯形法的计算步骤单纯形法的计算步骤单纯形表单纯形表计算步骤计算步骤2.单纯形法的进一步讨论单纯形法的进一步讨论人工变量法人工变量法jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001Z0 04.1 单纯形表，其中ijijjacc 1 mn min(0)ikjkjbaa1miiicb4.1 单纯形表例例1 1 试列出下面LP的初始单纯型表0,124 16 482. .32 max21212121xxxxxxtsxxz12345123142512345max 230002 84 16

8、. . 4 12,0zxxxxxxxxxxstxxx x x x x jc0 0 0 3 2BcBXb000543xxx1216854321 xxxxxi3 4Z03 24.1 单纯形表，其中ijijjacc 0 0 0min(0)ikjkjbaa1 2 1 0 04 0 0 1 00 4 0 0 1 12345123142512345max 230002 84 16. . 4 12,0zxxxxxxxxxxstxxx x x x x4.2 标准LP的单纯形计算步骤1.找初始基础可行基找初始基础可行基 对于对于(max, )，松弛变量对应的列构成一个单位阵，松弛变量对应的列构成一个单位阵2.检

9、验当前基可行解是否为最优解检验当前基可行解是否为最优解 若所有非基变量检验数都若所有非基变量检验数都 0，则为最优解，否则转下一步；，则为最优解，否则转下一步；3.确定改善方向确定改善方向 从正的检验数中找最大，选中者称为入基变量，所在列称为主列从正的检验数中找最大，选中者称为入基变量，所在列称为主列4 确定出基变量确定出基变量 最小比例原则；所在行称为主行最小比例原则；所在行称为主行5.迭代过程迭代过程 主行与主行与主列主列相交的元素称为主元，迭代以主元为中心进行初等行相交的元素称为主元，迭代以主元为中心进行初等行变换，将主元变为变换，将主元变为1，主列主列上其它元素变为上其它元素变为0。6

10、. 此时，得到一个新的单纯形表，重复此时，得到一个新的单纯形表，重复25。4.2 标准LP的单纯形计算步骤例2 请用单纯型表求解下LP0,124 16 482. .32 max21212121xxxxxxtsxxz12345123142512345max 230002 84 16. . 4 12,0zxxxxxxxxxxstxxx x x x x-4i-42124-3/40002-91/400103301004160-1/20101203x4x2xjjcz1/40-200-131/400103321-40080-1/20101221x4x2xjjcz3000320100401200100416

11、0001218000032jc BCBXb1x2x3x4x5xjjcz3x4x5x0-1/8-3/200-140-1/81/2102311/2-2004001/400142jjcz1x2x5x练习：利用单纯形法求解 0,24261553221212121 xxxxxxxxMaxZ 0,24 2615 532432142132121 xxxxxxxxxxxxMaxZ 0 0 -1/12 -7/24-33/4-Z x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cji15/43/4011/4-1/810 -1/125/24本节内容摘要一一线性规划与单纯形法线性规划与单纯形法1.单纯形

12、法的计算步骤单纯形法的计算步骤单纯形表单纯形表计算步骤计算步骤2.单纯形法的进一步讨论单纯形法的进一步讨论人工变量法人工变量法退化退化单纯形法小结单纯形法小结人工变量法人工变量法当约束条件为当约束条件为“ ”或或“”型，引入剩余变量或人工变量型，引入剩余变量或人工变量0,46 2.32132121xxxxxxxxts0,4 6 2.65432153216421xxxxxxxxxxxxxxts1241235123452 6. . 4,0 xxxstxxxxx x x x x人工变量法人工变量法一一 由于所添加的剩余变量的系数为由于所添加的剩余变量的系数为 1，不能构成，不能构成初始初始可行可行基

13、变量，为此引入一个人为的变量基变量，为此引入一个人为的变量（注意，此时约束条件已为（注意，此时约束条件已为“=”型），型），以便取以便取得初始基变量，故称为人工变量；得初始基变量，故称为人工变量；二二 由于人工变量加在等式约束中，故如果原问题由于人工变量加在等式约束中，故如果原问题有解的话，人工变量必须为零才能保证原等式有解的话，人工变量必须为零才能保证原等式约束成立。也就是说，人工变量在原问题的解约束成立。也就是说，人工变量在原问题的解中是不能存在的，应尽快被迭代出去。中是不能存在的，应尽快被迭代出去。三三 大大M法法 与与 两阶段法两阶段法 两种方法都是逼迫人工变量为零。两种方法都是逼迫人

14、工变量为零。 例例1 大大M法的求解过程法的求解过程0,4 6 2. .)007810max(max0,46 2. .7810min6543215321642165432132132121321xxxxxxxxxxxxxxtsMxxxxxxzxxxxxxxxtsxxxz例例1 单纯型表迭代过程单纯型表迭代过程10 x1 3 1 1/2 0 1/2 0 1/2 6 7 x3 1 0 (1/2) 1 1/2 1 1/2 (2) II cjzj 0 1/2 0 3/2 7 M+3/2 10 x1 2 1 0 1 1 1 1 8 x2 2 0 1 2 1 2 1 III 最优解 cjzj 0 0 1

15、2 6 M+2 答：最优解为 x1=2, x2=2, x3=0, OBJ=36 大大M M法的一些说明法的一些说明一一 大大M M法实质上与原单纯型法一样，法实质上与原单纯型法一样，M M可看成一个很可看成一个很大的常数；大的常数；二二 人工变量被迭代出去后就不会再成为基变量；人工变量被迭代出去后就不会再成为基变量；三三 当检验数都满足最优条件，但基变量中仍有人工当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解；变量，说明原线性规划问题无可行解；四四 大大M M法手算很不方便，但是计算机中常用大法手算很不方便，但是计算机中常用大M M法用法用计算机处理数据时，只能用很

16、大的数代替计算机处理数据时，只能用很大的数代替M,M,可能可能造成计算机上的错误，故多采用两阶段法。二阶造成计算机上的错误，故多采用两阶段法。二阶段法手算可能容易。段法手算可能容易。两阶段法两阶段法第二阶段：以第一阶段得到的基础可行解为初始解，采用原单纯型表求解。第一阶段：不考虑原问题是否存在基可行解；给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数和约束, 实现最小化。 然后用单纯形求解，若目标值为0，说明原问题存在基可行解，转第二阶段；否则原问题无可行解，停止。 两阶段法两阶段法 为了简化计算，在第一阶段重新定义价值系数如下：不是人工变量时当为人工变量时当时目标函数为不是人工变量时当为人工变量时当时目标函数为jjjjjjjjxcxcxcxc01max01min用二阶段法求解用二阶段法求解例例1 1的第一阶段的第一阶段 x1 x2 x3 x4 x5 x6 序号 CB XB b 0 0 0 0 0 1 bi/aij* 1 x6 6 (2) 1 0 1 0 1 (3) 0 x3 4 1 1 1 0 1 0 4 I cjzj 2 1 0 1 0 0 0 x1 3 1 1/2 0 1/2 0 1/