购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.2 单纯形法

从上一节中我们看到,若线性规划有最优解,必在可行域的某个顶点达到。最可能想到的是把所有顶点都找出来,然后逐个比较,求出最优解,这种方法事实上是行不通的,因为顶点的个数非常多。例如, m =20, n =40,顶点的个数有 个,要计算这么多顶点对象的目标函数值,显然是不可能的。

换一种思考方法,从某一个基本可行解出发,每次总是寻找比上一个更好的基本可行解,如果不比上一个好就不去计算,这样做就可以大大减少计算量。其基本想法是判别当前解是否最优,提出问题的标准,从可行域中某个基可行解(一个顶点)开始,转换到另一个基可行解(顶点),并且使目标函数逐步增大,最后就得到了最优解。美国数学家丹捷格提出的单纯形方法解决了此问题,单纯形方法到目前为止是求解线性规划的最普遍、最有效的方法。

2.2.1 初始基可行解的确定

为了确定初始基可行解,要首先找出初始可行基,其方法如下:

若线性规划问题:

从A中确定一个初始可行基,使得: ,构造初始可行基有两种方式。若约束条件是“≤”型的不等式,在每个约束条件的左端加上一个松弛变量。经整理,重新对x i 及a ij 进行编号,可得到下列方程组:

显然可以得到一个单位矩阵:

B 作为可行基,将每个等式移项:

x m +1 x m +2 =…= x n =0,由上式可得到一个初始基可行解:

对所有约束条件是“≥”形式的不等式及等式约束情况,化为标准型后若不存在单位矩阵式,就采用人造基方法。即对“≥”型不等式约束减去一个非负剩余变量,再加上一个非负人工变量;对于等式约束再加上一个非负的人工变量,总能得到一个单位矩阵。

2.2.2 最优解的检验和解的判别

由两个变量的线性规划图解方法,我们得到启示,线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况,为此需要建立对解的判别准则。根据上文得到的基解计算公式可归纳如下:

将上式代入目标函数式,整理后得到:

令:

于是:

再令 σ j c j z j j m +1,…, n

则:

(1)最优解判别定理:若 X (0) =( b b ,…, b ,0,…,0) T 为对应于基 B 的一个基可行解,且对于一切 j m +1,…, n σ j ≤0,则 X (0) 为最优解,称 σ j 为检验数。

(2)无穷多最优解判别定理:若 X (0) =( b b ,…, b ,0,…,0) T 为一基可行解,对于一切 j m +1,…, n ,有 σ j ≤0,又存在某个非基变量的检验数 σ m+k =0,则线性规划问题可能有无穷多最优解。

(3)无界解判别定理:若 X (0) =( b b ,…, b ,0,…,0) T 为一基可行解,有一个 σ m+k >0,并且对 k =1,2,…, m ,有 a m k ≤0,那么该线性规划问题具有无界解(或称为无穷解或无有限最优解)。

2.2.3 基变换

若初始基可行解 X (0) 不是最优解及不能判断无界时,需要找一个新的基可行解。具体做法是从原可行解基中换出一个列向量(当然要保持线性独立),从原非可行基中换入一个列向量,得到一个新的可行基,称为基变换。为了换基,先要确定换入变量,再确定换出变量,让它们相应的系数列向量进行交换,得到一个新的基可行解。

1.换入变量的确定

当某些 σ j >0时, x j 增加则目标函数值还可以增大,这时要将某个非基变量 x j 换入到基变量中去(称为换入变量)。若有两个以上的 σ j ,那么选 σ j >0中大的那个,即:max( σ j >0)= σ k ,则对应的 x k 为换入变量。但也可以任选或按最小足码选。

2.换出变量的确定

在确定 x k 为换入变量后,由于其他的非基变量仍然为非基变量,即 x j =0( j =1,2,… n j k ),则约束方程组有:

由于所有的 x j ≥0,所以若令:

x k 的增加不能超过 θ ,此方程相应的变量 x l 即为换出变量。这时的 θ 值是按最小比值来确定的,称为最小比值原则;与此相应的 a lk 称为主元素。

2.2.4 单纯形表

首先介绍一下单纯形表,为了计算上的方便和规格化,对单纯形法计算设计了一种专门表格,称为单纯形表(见表2.3)。

表2.3

在单纯形表的第2~3列列出某个基可行解中的基变量及它们的取值,接下来列出问题中的所有变量。在基变量下面各列数字分别是对应的基向量数字。表中变量 x 1 x 2 ,…, x m 下面各列组成的单位矩阵就是初始基可行解对应的基。

其中:每个基变量 x j 下面的数字,是该变量在约束方程的系数向量 P j 表达为基向量线性组合时的系数。

c j 为表最上端的一行数,是各变量的目标函数中的系数值;

C B 为表中最左端一列数,是与各基变量对应的目标函数中的系数值;

b 列中填入约束方程右端的常数。

检验数 σ j c j z j j m +1,…, n )称为变量 x j 的检验数,将 x j 下面的这列数字 P j C B 这列数中同行的数字分别相乘,再用 x j 上端 c j 值减去上述乘积之和,即:

θ i 列的数字是在确定换入变量后,按 θ 规则计算后填入;其中, x j 为换入变量)。

2.2.5 单纯形法的计算步骤

根据以上讨论,将求解线性规划问题的单纯形法的计算步骤归纳如下:

第一步,求出线性规划的初始基可行解,列出初始单纯形表。

第二步,进行最优性检验。各非基变量检验数为 σ j c j z j j m +1,…, n ),如果 σ j ≤0,则表中的基可行解是问题的最优解,计算到此结束,否则进入下一步。

第三步,在 σ j >0, j m +1,…, n 中,若有某个 σ k 对应 x k 的系数列向量 P k ≤0,则此问题无界,停止计算;否则,转入下一步。

第四步,从一个基可行解换到另一个目标函数值更大的基可行解,列出新的单纯形表。

(1)确定换入变量。有 σ j >0,对应的变量 x j 就可作为换入变量,当有两个以上检验数大于零,一般取最大的 σ k ,即 σ k =max{ σ j σ j >0},取 x k 作为换入变量。

(2)确定换出变量。根据最小 θ 规则,对 p k 列由公式计算得: ,确定是 X 1 换出变量。

(3)元素 a lk 决定了从一个基本可行解到另一个可行解的转移去向,取名为主元素。以 a lk 为主元素进行旋转变换,得到新的单纯形表,转到步骤二。

下面,我们用例2.1说明单纯形表进行迭代运算:

(1)根据问题的标准型,取松弛变量 x 3 x 4 x 5 为基变量,对应得单位矩阵的基,得到初始基可行解 X (0) =(0,0,6,8,18) T ,得到初始单纯形表,如表2.4所示。

表2.4

其中,非基变量的检验数:

(2)由检验数 σ 1 σ 2 大于零, P 1 P 2 有正分量,转入下一步。

(3)max( σ 1 σ 2 )=max(4,3)=4,对应 x 1 为进入变量。

θ =min{ b i a i 1 a i 1 >0}=min{6/1,-,18/2}=6

它对应的基变量 x 3 是换出基变量, x 3 所对应的行与 x 1 所对应的列包括检验数变为(1,0,0,0) T ,在 X B 列将 x 3 换成 x 1 得到新单纯形表(见表2.5)。

表2.5

此时,新基变量 X B =( x 1 x 4 x 5 T ,对应于基可行解 X (1) =(6,0,0,0,8) T ,相应的目标值 z =24。检验表2.5中的检验数行得知 x 2 的检验数为3>0,说明 x 2 应为换入基变量,计算 θ 值:

所以对应的 x 5 为换出基变量,基变量 x 5 的行与进入基变量 x 2 的列交叉处元素3为主元素,再对主元素进行旋转变换,使 x 2 列变为单位向量(0,0,1,0) T ,得到表2.6。

表2.6

此时,基变量为 X B =( x 1 x 4 x 2 T ,对应的基可行解为 X (3) =(6,2,0,4,0) T ,对应目标函数值 z =30。由于所有检验数均小于或等于0,所以此解是最优解,对应基为最优基。 Cq7r0tdOE2M/3klT1LNdxEMDlMwkOf6/zC/gCGAlKDTa+qofGbXhxaMo5B562T5d

点击中间区域
呼出菜单
上一章
目录
下一章
×