运筹1.5线性及单纯形法

1、1第一章 线性规划及单纯形法Linear Programming第五节 单纯形法计算步骤一、单纯形表二、单纯形法基本步骤三、单纯形法举例 为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。一、单纯形表1 00 a1,m+1 a1n0 10 a2,m+1 a2n0 01 am,m+1 amnA=一、单纯形表 cj c1 c2 cm cm+1 cm+k cnCB XB b x1 x2 xm xm+1 xm+k xn c1 x1 b1 1 0 0 a1,m+1 a1,m+k a1n c2 x2 b2 0 1 0 a2,m+1 a2,m+k a2n cr

2、 xr br 0 0 0 ar,m+1 ar,m+k arn cm xm bm 0 0 1 am,m+1 am,m+k ann j 0 0 0 m+1 m+k n 一、单纯形表第五节 单纯形法计算步骤一、单纯形表二、单纯形法基本步骤三、单纯形法举例单纯形法解题思路（复习） 根据问题的标准型，从可行域中某个基可行解（顶点）开始，判断其是否为最优解，如为否，则转换到相邻的基可行解（顶点），并使目标函数值不断增大，一直找到最优解为止。二、单纯形法基本步骤(1) 确定初始基（P1,P2, ,Pm）和初始基可行解，列出初始单纯形表； cj c1 c2 cm cm+1 cm+k cnCB XB b x1

3、x2 xm xm+1 xm+k xn c1 x1 b1 1 0 0 a1,m+1 a1,m+k a1n c2 x2 b2 0 1 0 a2,m+1 a2,m+k a2n cr xr br 0 0 0 ar,m+1 ar,m+k arn cm xm bm 0 0 1 am,m+1 am,m+k ann j 0 0 0 m+1 m+k n 二、单纯形法基本步骤 最优性检验： 计算各非基变量xj的检验数， a. 所有检验数j 0, 若是，停止迭代，得到最优解，否则转(3) ； b. 若存在k 0，且对应的Pk 0，停止 迭代，问题为无界解，否则转(3)； = min ai,k 0 =biai, kb

4、lalk定xl为换出变量，alk为主元。由最小比值原则：二、单纯形法基本步骤(3) 基可行解的转换a. 确定换入变量（最大增加原则）b. 确定换出变量（最小比值原则）xl为换入变量转(2)。 a1k 0 a2k 0alk 1amk 0初等行变换Pk =(4)以alk为主元，换基迭代（高斯消去）。(用换入变量xk替代基变量中的换出变量xl，得到一个新的基（P1, , Pl-1, Pk, Pl+1, ,Pm），对应这个基可以找出一个新的基可行解)二、单纯形法基本步骤第l个分量 主元决定了从一个基可行解到相邻基可行解的转移去向新的基仍应是单位矩阵，即Pk应变换成单位向量，为此利用初等行变换生成新的单

5、纯形表。（1）将主元所在l行数字除以主元alk，即有二、单纯形法基本步骤（2）将刚计算得到的第l行数字乘上（- aik ）加到第i行数字上，即有（3）新单纯形表中检验数的求法：二、单纯形法基本步骤第五节 单纯形法计算步骤一、单纯形表二、单纯形法基本步骤三、单纯形法举例第五节 单纯形法计算步骤一、单纯形表二、单纯形法基本步骤三、单纯形法举例 5x2 156x1+2x224 x1+x2 5 x1 , x2 0 例1. max z=2x1 +x2 三、单纯形法举例标准化 max z=2x1 +x2 +0 x3 +0 x4 +0 x5 5x2+x3 = 156x1+2x2 +x4 =24 x1+x2

6、+x5=5 x1 , ,x5 0 三、单纯形法举例(1) 求初始基可行解， 列出初始单纯形表。三、单纯形法举例cj21000CBXBbx1x2x3x4x50 x315051000 x424620100 x5511001cj-zj21000三、单纯形法举例(2) 最优性检验 检验数大于零，因此初始基可行解不是最优解 a. 因1 2，确定x1为换入变量b.= min ai1 0 =biai14x4因此确定x4为换出变量c. 确定6为主元三、单纯形法举例cj21000CBXBbx1x2x3x4x50 x315051000 x4246201040 x55110015cj-zj21000 三、单纯形法举

7、例(3) 用换入变量替换换出变量 新的基 新的基可行解 新的单纯形表 三、单纯形法举例cj21000CBXBbx1x2x3x4x50 x315051002x1412/601/600 x5104/60-1/61cj-zj01/30-1/30三、单纯形法举例cj21000CBXBbx1x2x3x4x50 x3150510032x1412/601/60120 x5104/60-1/613/2cj-zj01/30-1/30 三、单纯形法举例cj21000CBXBbx1x2x3x4x50 x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-

8、1/4-1/2三、单纯形法举例所有检验数j 0，得到最优解；基可行解X=(7/2, 3/2, 15/2, 0, 0)T是最优解,代入目标函数得最优值z=17/2。三、单纯形法举例练习一标准化三、单纯形法举例三、单纯形法举例CBXBb23000 x1x2x3x4x50 x381210040 x41640010_0 x512040013Z=023000三、单纯形法举例CBXBb23000 x1x2x3x4x50 x30 x40 x5 3 0 1 0 0 1/4 16 4 0 0 1 0 2 1 0 1 0 -1/224-2000-3/4Z=9x23三、单纯形法举例CBXBb23000 x1x2x3

9、x4x50 x3 0 x43x2 2 1 0 1 0 -1/2 8 0 0 -4 1 2 3 0 1 0 0 1/4412 - 00-201/4Z=132x1三、单纯形法举例CBXBb23000 x1x2x3x4x52x10 x43x2 4 1 0 0 1/4 0 4 0 0 -2 1/2 1 2 0 1 1/2 -1/8 0Z=1400-1.5-1/80 x5三、单纯形法举例 max z=50 x1 +100 x2 x1 +x2 300 2x1 +x2 400 x2 250 x1 ， x2 0 x1 +x2 + x3 =300 2x1 +x2 + x4 =400 x2 + x5 =250 xj 0,j=1, ，5练习二三、单纯形法举例CBXBb50100000 x1x2x3x4x50 x3300111003000 x4400210104000 x525001001250Z=050100000三、单纯形法举例CBXBb50100000 x1x2x3x4x50 x3501010-