线性规划模型的应用与灵敏度分析

中国石油大学胜利学院本科毕业设计(论文）

图2-1.单纯行法的基本思路

用单纯行法讨论例1的求解 解：已知例1的标准型为

max Z ?2x2?3x3?0x4?0x5??x1?2x2?8 ??4x1?x4?16?4x 2?x5?12??xj?0,j?1,2,?,5约束条件（2-2）的系数矩阵

显然，x3，x4，x5的系数列向量

? p?1???0??0?3??0?，p???1??，p??4?5??0? ?0????0????1??是线性独立的，因而这些向量构成一个基

?100? B??p??3,p4,p5???010?? ?001??

8

（2-1） （2-2）（2-3） (2-4)

中国石油大学胜利学院本科毕业设计(论文）

对应于B的基变量为x3,x4,x5，从约束条件（2-2）中可以看到

x3?8-x1-2x2 x4?16-4x1 （2-5）

x5?12-4x2当令非基变量x1?x2?0,这时得到一个基本可行解X（0）

（0） x??0,0,8,16,12? （2-6）

r将式(2-3)代入目标函数(2-1)得到

z?0?2x1?3x2?0 （2-7）

这个基本可行解表示：工厂没有安排生产ⅠⅡ产品；资源都没有被利用，所以工厂的利润Z=0。

分析目标函数的表达式(2-7)可以看到：非基变量x1,x2的系数都是正数，因此将非基变量变为基变量，目标函数的值就可能增大，从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加，所以只要在目标函数(2-7)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与某个基变量进行对换，一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中区，同时还有确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。

现分析式(2-5)，当将x2定为换入变量后，必须从x3,x4,x5中换出一个，并保证其余的都是非负，即x3,x4,x5。 当x1=0，由式(2-5)得到

?x3?8-2x2?0? ?x4?16?0 （2-8）

?x?12-4x?02?5可以看出，只有选择

?3 （2-9） x2?min（8/2-12/4）时，才能使式(2-8)成立。

以上数学模型说明了每生产一件产品Ⅱ，需要用掉的各种资源数为(2,0,4)。这些资源中的薄弱环节确定了产品Ⅱ的产量。原材料B的数量决定产品Ⅱ的产量只能是x2=12/4=3件。

9

中国石油大学胜利学院本科毕业设计(论文）

为了求得以x3，x4，x2为基变量的一个基本可行解和进一步分析问题，需将方程(2-5)中x2的位置对换。得到

x3?2x2?8-x1 x4?16-4x1 （2-10）

4x2?12-x5

用高斯消去法求解，得到以非基变量表示的基变量

x3?2-x1?0.5x5 x4?16-4x1

（2-11）

x2?3-0.255x

代入目标函数得到

Z?9?2x1-0.75x5 (2-12)

令非基变量x1?x5?0,得到Z?9,并得另一个基本可行解X(0)?(0,3,2,16,0)T。

从目标函数的表达式(2-12)中可以看到，非基变量x1的系数是正的，说明目标函数的值还可以增大，还不是最优解。于是用上述方法，确定换入、换出变量，继续迭代，再得到另外一个基本可行解X(2)?(2,3,0,8,0)T。

再经过一次迭代，得到一个基本可行解X(3)?(4,2,0,0,4)T。而这时得到的目标函数的表达式是

Z?14-1.5x3-0.125x4 （2-13）

再分析目标函数(2-13),可知所有非基变量x3,x4,的系数都是负数，这说明若要用剩余资源x3,x4,就必须支付附加费用。所以当x3?x4?0时，即不再利用这些资源时，目标函数达到最大值，那么X(3)是最优解。这说明当产品Ⅰ生产4件，产品Ⅱ生产2件，工厂才能得到最大利润。

通过上例，可以了解利用单纯形法求解线性规划问题的思路。

10

中国石油大学胜利学院本科毕业设计(论文）

2.2单纯形法的求解步骤

线性规划问题的求解有以下几个步骤：

(1)确定初始基本可行解。为了确定初始基本可行解，首先要找出初始可行解。 设一线性规划问题为

?cxjj?1nj?n??pjxj?b ?j?1 （2-14）

?x?0，j?1,2，...，n?j可分为两种情况讨论。

①若Pj(j?1,2,???,n)中存在一个单位基，则将其作为初始可行基

10?001?0 B? （2-15） （p1，p2，..，.pm）??00?1②若Pj(j?1,2,???,n)中不存在一个单位基，则人为地构造一个单位初始基。

(2)检验最优解。得到初始基本可行解后，要检验该解是否为最优解。如果是最优解，则停止运算；否则转入（3）基变换。下面给出最优性判别定理。一般情况下，经过迭代后可以得到以非基变量表示基变量的表达式

xj?bi-?，m） （2-16） ?ax （i?1,2，ijjnj?m?1

将式(2-11)代入式(2-10)的目标函数，整理后得

maxZ??cibi??(cj??ciaij)xj （2-17）

i?1i?1i?1mnn令

?，n） Z0??cibi,Zj??ciaji （j?m?1， （2-18）

i?1i?1nm于是

max z ?z0??(cj?zj)xj （2-19）

j?m?1n 11