单纯形法基本原理(7)

x3

则必有 x4

x 5

15245

0

进而可以解出x1的一个取值范围，即x1 6x1 0， x1 0

246

,5} 4.

246

且x1 5。

让x1从零增加，其能取得的最大值为x1 min{

由x4 24 6x1 0可知，此时，x4已经从24降到了0，达到了非基的取值，变成非基变量。所以出基的变量是x4。从而得到新的可行基{x1,x3,x5}。这种判断出基变量的方法称为最小比值原则法。

x3

x4

对于式子：

x5 x 0 i

15245

6x1 x1i 1, ,5

1541

5x2 1323x2x2

1616x4x4

5x2 2x2 x2

，将可行基{x1,x3,x5}留在左边，非基变

x3

x1

量x2,x4移到右边，并用代入法消元，则上式变为：

x

5

x 0 i

。由此

i 1, ,5

T

得到一个新的基本可行解：X1 (4,0,15,0,1)。此时目标函数值

Z(X1) 2 4 8 Z(X0) 0.从目标函数值明显看出，X1比X0明显地得到了改善。代

入目标函数得：Z 8

13

x2

13

x4。

这一过程可以用增广矩阵的行初等变换表示，并在增广矩阵末尾行增加一行，称为检验行或者目标函数行，其系数即为对应未知数的系数，常数列对应的数值即为目标函数值。即 0 6

为A

1 2

5211

1000

0100

0010

15 24

，其中(2,1,0,0,0,0)这一行为检验行，是目标函数Z的系5 0

数，行末的0为Z的取值。这个矩阵也称为单纯形矩阵或单纯形数表。

对单纯形矩阵进行行变换可以实现进基和出基两个过程，如上文所述，进基过程依据最大系数原则，出基过程依据最小比值原则。从开始至结束，每一步都需要运用这两个原则，并最终找到Z的最大值。结束的标志即为检验行全部系数没有正数。

[3]

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新教学研究单纯形法基本原理(7)全文阅读和word下载服务。