第一章线性规划及单纯形法 .pdfVIP

第一章线性规划及单纯形法

6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsa

replotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb

检验数?jx1x2x

3x4x53500081010012020103634001x3x4x5

000035000令非基变量x1=0，x2=0，找到一个初始基可行解：

x1=0，x2=0，x3=8，

x4=12，x5=36，σj＞0，此解不是最优（因为

z=3x1+5x2+0x3+0x4+0x5)

即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比

值CBXBb检验数?jx1

x2x3x4x53500081010012020103634001x3x

4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出

基变量检验数?j81010060101/2012300-21x3x2x5050

-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x5350008

1010012020103634001x3x4x5000035000-

12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即

得基可行解X1=(0,6,8,0,1

2)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行

解Cj比值CBXBb检验数?

jx1x2x3x4x53500081010060101/2012300-2

1x3x2x5050-30300-5/208-4检验数?j40012/3-1/36

0101/204100-2/31/3x3x2x1053-42000-1/2-1令x

4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0

最优解:X=(4,6,4,0,0

)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问

题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基

，建立初始单纯形表。③计算各非基变量xj的检验数?j=Cj-CBPj′，

若所有?j≤0，则问题已得到最优解，停止计算，否则转入

下步。④在大于0的检验数中，若某个?k所对应的系数列向量

Pk′≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据

max

{?j｜?j＞0}=?k原则，确定xk为换入变量(进基变量)，再按?规则

计算：?=min{bi′/aik′|aik′＞0}=bl

′/alk′确定xBl为换出变量。建立新的单纯形表，此时基变量中xk

取代了xBl的位置。⑥以aik′为主元素进行迭代，把xk

所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素

为0，转第③步。单纯形法的进一步讨论一、大M法二、两阶

段法--人工变量法人工变量法问题：线性规划问题化为标准形时，

若约束条件的系数矩阵中不存在单位矩阵，如何构造初始

可行基？约束条件中加入人工变量设线性规划问题的标准型为：

加入人工变量,构造初始可行基.系数矩阵为单

位矩阵，可构成初始可行基。约束条件已改变，目标函数如何调

整？“惩罚”人工变量！（1）大

M法（2）两阶段法一、大M法人工变量在目标函数中的系数为-

M,其中，M为任意大的正数。目标函数中添加

“罚因子”-M（M是任意大的正数）为人工变量系数，只要人工

变量0，则目标函数不可能实现最优。例:求解线性规划问题

一、大M法一、大M法解:加入松弛变量和剩余变量进行标准化,

加入人工变量构造初始可行基.求解结

果出现检验数均非正时：若基变量中含非零的人工变量，则无可

行解；否则，有最优解。一、大M法用单纯

形法求解（见下页）。1-21-412-201

3-6MM-13M-13-1-1x1x2x30

x41