运筹学一般单纯形法课件

第三章单纯形法

单纯形法的一般解法大M法和两阶段法

修正单纯形法单纯形法的数学原理单纯形法适用于任何线性规划问题的求解。第一节单纯形法的一般解法

例：步骤1引入松弛变量等，将问题化成标准形式；步骤2具体写出各系数矩阵Ａ，B，Ｐj和Ｃ;特别注意：A矩阵中有否完全单位向量组。步骤3形成初始表如下，表中基变量为Ａ矩阵中完全单位向量组对应的变量。

段cj

→

Cθi

注↓

基bp1p2…pn1基变量对应的cj

基变量例段cj→θi

注↓基bP1P2P3P41cj-zj→

例段cj→031000θi

注↓基bP1P2P3P410x32434100x415-1501cj-zj→

步骤4.1计算检验数Ｃｊ－Ｚｊ：其中Ｚｊ等于Ｐｊ中各分量与相应的左边各Ｃｊ的乘积之和，Ｃｊ－Ｚｊ等于Ｐｊ上面对应的Ｃｊ减去Ｚｊ；段cj→031000θi

注↓基bP1P2P3P410x32434100x415-1501cj-zj→

段cj→031000θi

注↓基bP1P2P3P410x32434100x415-1501cj-zj→31000

步骤4.2：判断（１）若所有检验数均≤０时，即得到最优解和最优值；（２）若检验数存在正值，继续下一步。

本例中：c1-z1>0，c2-z2>0段Cj→031000θi

注↓基bP1P2P3P410x32434100x415-1501cj-zj→31000

步骤5：换基迭代5.1决定主元素5.2换基迭代5.3计算新元素5.1决定主元素：当表中出现正检验数时，找出其中绝对值最大的一个所在的列作为主元列，记为Pj*，然后用主元列中各正分量去除b列中相应的分量，得到θ

i，接着取θ

i中最小的分量所在的行为主元行，记为Pi*；主元行与主元列相交处的元素即主元素，记为Pi*j*；找到主元素后，打上一个圈以示区别。段Cj→031000θi注↓基bP1P2P3P410x32434100x415-1501Cj-Zj→31000

例：段Cj→031000θi注↓基bP1P2P3P410x324341060x415-1(5)013Cj-Zj→31000

主元列主元行主元素5.2：换基

把主元行对应的变量（出基变量/调出变量）从基底调出，用主元列对应的变量（入基变量/调入变量）代替之，进入下一段。例中：x4调出，x2调入。段Cj→031000θi注↓基bP1P2P3P410x324341060x415-1(5)013Cj-Zj→31000

换基后段Cj→031000θi

注↓基bP1P2P3P410x324341060x415-1(5)013Cj-Zj→31000

20x310x2Cj-Zj→

5.3：计算新元素

5.3.1原主元行上元素的计算：将原主元行上的元素，分别除以主元素，使主元素为“1”。即：段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x310x2Cj-Zj→

例：段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x310x23-1/5101/5Cj-Zj→

5.3计算新元素5.3.2原非主元行上元素的计算：先将原主元行上的新元素乘以某一数A后，分别加上原非主元行上的元素，使原主元列上各元素除了原主元素为“1”外，其余均为0。段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x3010x23-1/5101/5Cj-Zj→

则：A=-4段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x31219/501-4/510x23-1/5101/5Cj-Zj→

步骤6：回到第4步

步骤4：计算检验数、判断检验数计算检验数Ｃｊ-Ｚｊ：（１）若所有检验数均≤０时，即得到最优解和最优值；（２）若检验数存在正值，继续下一步。计算检验数，判断检验数段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x31219/501-4/510x23-1/5101/5Cj-Zj→

计算检验数，判断检验数段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x312(19/5)01-4/510x23-1/5101/5Cj-Zj→500-2

换基迭代，计算新元素（原主元行）段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→500-2

33x1

10x2Cj-Zj→

换基迭代，计算新元素（原主元行）段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→500-2

33x160/19105/19-4/19

10x20Cj-Zj→

计算新元素（原非主元行）段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x312(19/5)01-4/560/19调出10x23-1/5101/5-Cj-Zj→500-2

33x160/19105/19-4/19

10x269/19011/193/19Cj-Zj→

计算检验数，判断检验数段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000

20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→500-2

33x160/19105/19-4/19

10x269/19011/193/19Cj-Zj→00-25/19-18/19

结论所有检验数均为非正，得最优解、最优值。最优解即基变量对应的ｂ列数值，不在基变量范围的其他变量数值为０；最优值检验数对应的ｂ列数值的相反数。段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→031000

20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→-30500-2

33x160/19105/19-4/19

10x269/19011/195/19Cj-Zj→-870/1900-25/19-18/19

例2标准化：引入松弛变量x3,x4,x5写出各系数矩阵Ａ，B和Ｃ;解题过程初始表段Cj→034000Qi注↓基bP1P2P3P4P510x36121000x412320100x5201001Cj-Zj→

段Cj→034000Qi注↓基bP1P2P3P4P510x3612100

0x41232010

0x5201001Cj-Zj→034000

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x300x404x2201001

Cj-Zj→

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x321010-20x483001-24x2201001Cj-Zj→

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x321010-20x483001-24x2201001

Cj-Zj→-83000-4

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x32（1）010-22→0x483001-28/34x2201001-

Cj-Zj→-83000-4

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x32（1）010-22→0x483001-28/34x2201001

Cj-Zj→-83000-4

33x121010-2

0x404x20Cj-Zj→段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x32（1）010-22→0x483001-28/34x2201001

Cj-Zj→-83000-4

33x121010-2

0x4200-3144x2201001Cj-Zj→

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x32（1）010-22→0x483001-28/34x2201001

Cj-Zj→-83000-4

33x121010-2

0x4200-3144x2201001Cj-Zj→-1400-302

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x32（1）010-22→0x483001-28/34x2201001

Cj-Zj→-83000-4

33x121010-2

0x4200-31（4）1/2→4x22010012

Cj-Zj→-1400-302

段Cj→034000Qi注↓基bP1P2P3P4P510x36121003

0x412320106

0x520（1）0012→Cj-Zj→034000

20x32（1）010-22→0x483001-28/34x2201001

Cj-Zj→-83000-4

33x121010-2

0x4200-31（4）1/2→4x22010012

Cj-Zj→-1400-302

43x10

0x51/200-3/41/414x20Cj-Zj→

段Cj→034000Qi注↓基bP1P2P3P4P510x36121