发布时间 : 星期一 文章线性规划模型的应用与灵敏度分析更新完毕开始阅读
中国石油大学胜利学院本科毕业设计(论文）
图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