第一章 线性规划与单纯形法(4)

第五节 单纯形法原理

单纯形法求解线性规划问题的思路是：先求一个初始的基本可行解并判断它是否最优，若不是最优，再换一个基本可行解并判断，直到得出最优解或无最优解。这是一种逐步逼近最优解的迭代方法。

一、用消元法解线性规划问题

考虑某工厂用三种有限量的资源生产两种产品的最优生产计划问题，其线性规划模型如例1.8所示。

例1.8 求解下列线性规划问题

maxz?2x1?5x2?x1?4?x?3 ?2s.t.??x1?2x2?8??x1?0,x2?0解：分别在3个约束方程中引入松弛变量x3,x4,x5，则可将上述线性规划问题转化为标准型：

maxz?2x1?5x2?x1?x2?s..t??x1?2x2??x1,x2,x3,第一步：求初始基可行解 系数矩阵

?x3?x4?x50?4?3 ?8x4,x5??10100???A??01010???p1?12001???显然R(A)?3，其中可令

p2p3p4p5?

?100???B??010???p3?001???基变量表示基变量的形式

p4p5?

为基矩阵，列向量p3,p4,p5对应的决策变量x3,x4,x5为基变量，将方程组改写为用非

?x3?4?x1??x4?3?x2 ?x?8?x?2x12?5(1.1)

令非基变量x1?0,x2?0，得初始基可行解

- 20 -

X(0)?(0,0,4,3,8)T

此时，目标函数z?2x1?5x2?0。

该初始基可行解表示工厂没有安排生产，所有资源都没有被利用，所以利润为0。 第二步：判优

工厂没有生产，利润为0，显然不是最优解。将式(1.1)代入目标函数中可得

z?2x1?5x2

(1.2)

在式(1.2)中，只有非基变量x1,x2，且其系数都是正数，故若非基变量变为基变量，取值从等于0变为大于0，则目标函数值就会增大。即若生产产品，工厂利润会增加。故初始基可行解X(0)不是最优解。

由此可见：目标函数中非基变量的系数可以用来检验线性规划是否已得到最优解。 第三步：换基

换基的目的是寻找更好的基可行解。由第二步的分析中可知，当非基变量x1,x2增加时，目标函数值会增加。

首先选择一个非基变量变换为基变量，称为入基变量。从实际出发，优先考虑安排单位利润大的产品生产。从目标函数表达式(1.2)可知，非基变量x2的系数大于x1的系数，所以确定x2为入基变量。

其次，根据R(A)?3可知，必须选择一个基变量转换为非基变量，称为出基变量。从目标函数最大化的角度出发，我们希望x2取值变得尽可能大。但受资源有限量的约束，入基变量x2的值不可能无限增大，需保证其余变量的非负性，即下列不等式成立。

?x3?4?x1?0??x4?3?x2?0 ?x?8?x?2x?012?5(1.3)

其中x1仍为非基变量，取值为0。代入式(1.3)解得

3?x???21 ?8?x?2??2(1.4)

故x2的最大可能取值为

x2?min{3/1,8/2}?3

由式(1.3)知，当x2?3时，变量x4?0，故确定x4为出基变量。

第四步：求新的基可行解

新的基变量为x2,x3,x5，非基变量为x1,x4。将约束方程改写为用非基变量表示基变量的形式为

?x3?4?x1??x2?3?x4 ?x?2x?8?x21?5

利用消元法得

- 21 -

?x3?4?x1??x2?3?x4 ?x?2?x?2x14?5p2p5?

(1.5)

?100???这里，新的基矩阵是B??010???p3?021???

令非基变量x1?0,x4?0，得新的基可行解

X(1)?(0,3,4,0,2)T

新的目标函数值为z?2x1?5x2?15。

(1)(0)显然，基可行解X优于初始基可行解X

第五步：判优（实际上是转回第二步） 将式(1.5)代入目标函数表达式中可得

z?2x1?5x4?15

(1)(1.6)

不是最优解。

在目标函数式(1.6)中，非基变量x1系数为正数。所以，如果将x1由非基变量变为基变量，其取值从等于0变为大于0，则目标函数的值就会增大。故基本可行解X第六步：换基

为寻找更优的基可行解，下面首先要换基。由第五步的分析，显然取x1为入基变量。类似第三步确定入基变量x1的值，需满足如下不等式组

?x3?4?x1?0??x2?3?x4?0 ?x?2?x?2x?014?5(1.7)

当另一个非基变量x4仍然为0时，可得到入基变量的值为

x1?min{4/1,2/1}?2

此时，x5?0，故取x5为出基变量。

第七步：求新的基可行解

新的基变量为x2,x3,x1，非基变量为x5,x4。将约束方程改写为用非基变量表示基变量的形式，并用消元法化为

?x3?2?x5?2x4??x2?3?x4 ?x?2?x?2x54?1(1.8)

令非基变量x5?0,x4?0，得新的基可行解

X(2)?(2,3,2,0,0)T

新的目标函数值为z?2x1?5x2?19。

第八步：判优

将式(1.8)代入目标函数式可得

- 22 -

z?19?x4?2x5

(1.9)

从目标函数式(1.9)可知，非基变量x5,x4的系数都为负数，当非基变量从0变为大于0的数时，目标函数值会减小，故此时得到的基本可行解X(2)即是最优解。

该基本最优解说明工厂的最优生产计划为，产品1生产2个单位，产品2生产3个单位，获得最大利润19，其中资源1剩余2个单位，其他两种资源没有剩余。 二、单纯形法的一般原理

设线性规划标准型为

maxz?CX?AX?b s..t??X?0其中A是m?n阶矩阵，且r(A)?m，X?(x1,x2,?,xn)T,C?(c1,c2,?,cn)，

b?(b1,b2,?,bn)T，X?0即xi?0(i?1,2,?,n)。

不妨设A?(P1,P2,?,Pn)中前m个列向量线性无关，构成一个基B?(P1,P2,?,Pm)。记后n?m个列向量构成矩阵N?(Pm?1,Pm?2,?,Pn)，则A?(B,N。记基变量)XB?(x1,x2,?,xm)T，非基变量XN?(xm?1,xm?2,?,xn)T。则约束方程AX?b可写成

?1?XB?(B,N)???b，即BXB?NXN?b

X?N??1因为r(B)?m，故B存在，方程两边同时左乘B得

XB?B?1NXN?B?1b，

XB?B?1b?B?1NXN (1.10)

令非基变量XN?0，故XB?B?1b，则得到基本解

?1?B?1b?X???

?0?(1.11)

若有Bb?0，则解(1.11)为一个基本可行解。此时基B为可行基。

类似地，记CB?(c1,c2,?,cm)，CN?(cm?1,cm?2,?,cn)，C?(CB,CN)。则目标函数z?CX可以写成

?X?z?(CB,CN)?B??CBXB?CNXN

?XN? z?CB(B?1b?B?1NXN)?CNXN

代入式(1.10)，消去目标函数中的基变量得

z?CBB?1b?(CN?CBB?1N)XN (1.12)

令XN?0，得基到本解(1.11)所对应的目标函数值z?CBB?1b。CN?CBB?1N是非基变量XN的系数向量，记为?N?CN?CBB?1N。由例1.8的求解过程可知，若目标函数中非基变量的系数都非正（即?N?0），则目标函数达到最大值，对应的基本可行解为最优解。故称?N为非基变量XN的检验数。其中某一个非基变量xi的检验数

?1?i?Ci?CBB,P(?im?1?,,。 n)i- 23 -

在实际计算中，B?1的计算是比较复杂的。为了简化计算，可取单位阵E为初始基。在

这种情况下，目标函数值简化为

z?CBb

xi的检验数简化为

?i?ci?CBPi (1.13)

定理1.4 最优解判别定理

对于基B，若满足Bb?0，且非基变量检验数?N?0，则对应于基B的基本解(1.11)就是线性规划问题的最优解，基B称为最优基。

若某一基本可行解经过最优检验表明不是最优解，则需要设法求得另一个更好的基本可行解，这一过程称为换基迭代。换基迭代的主要步骤如下：

（1） 确定入基变量 （2） 确定出基变量

（3） 通过消元法求得另一个更好的基本可行解。

前面例子中已说明了这种消元法的基本思路，下面用单纯形表进一步说明。

三、单纯形法表及单纯形法 1、单纯形表

将单纯形法一般原理中的所需数据和结果放在一张表中，其矩阵形式如表1.3所示，采用表格的形式进行计算，这种表格称为单纯形表。

表1.3 ?1cj? CB CN XB XN CB XB b B N ?j 0 CN?CBB?1N 在单纯形表中可以进行解的最优检验，当某一基本可行解不是最优解时，可求得另一个更好的基本可行解，直到求得最优解为止。单纯形表的一般形式见表1.4。

表1.4

cj? CBc1c2?cmc1c2?cmcm?1cm?2?cm xm?1xm?2?xm XBx1x2?xmb x11b10b2 ??0bmx2?xm01?0????0a1,m?1a1,m?20a2,m?1a2,m?2???1an,m?1an,m?2?a1n?a2n ???ann?j 00?0?m?1?m?2??n - 24 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第一章 线性规划与单纯形法(4)在线全文阅读。