maxz?2x1?3x2?8?x1?2x2?x3?4x?x4?16?1 ?4x2?x5?12??xj?0,j?1,...,5?xB x1 x5 x2 例 2.
b 4 4 2 -14 x1 1 0 0 0 x2 0 0 1 0 x3 0 -2 1 23? 2x4 1 41 21? 81? 8x5 0 1 0 0 maxz?2x1?5x2?4?x1?2x2?12? ??3x1?2x2?18?xj?0,j?1,2?§1.5 线性规划的大M法与两阶段法
1． 问题的提出
若约束条件的系数矩阵A中存在单位阵构成的基，则容易得到初始基可行解，否则难确定初始基可行解，因此需要引入人工变量。例如在Ax?b的两边加入人工变量xn?1,xn?2,...,xn?m
?a11x1?a12x2?...?a1nxn?xn?1?b1??xn?2?b2?a21x1?a22x2?...?a2nxn? ...??ax?ax?...?ax?xn?m?bmmnn?m11m22??xj?0,j?1,2,...,m?n若经基的变换，基变量中不再含有非零的人工变量，这表示原问题有可行解。
14
若经基的变换，在单纯形表中一直存在非零的人工变量，这表示原问题无可行解。 2． 大M法
在一个线性规划问题中加入人工变量后，要求人工变量对目标函数的取值不受影响，为此设人工变量在目标函数中的系数为?M(M?0)，这样在求maxz时，必须把人工变量换成非基变量或等于0的基变量。 例1. 设有线性规划
maxz?3x1?x2?x3?11?x1?2x2?x3?x4??4x?x?2x?x5?3 ?123??x3?1??2x1?xj?0,j?1,...,5?试用大M法求解。
解：引入人工变量x6,x7，有：
maxz?3x1?x2?x3?Mx6?Mx7?11?x1?2x2?x3?x4??4x?x?2x?x5?x6?3 ?123??x3?x7?1??2x1?xj?0,j?1,...,7? 将目标函数中的基变量x6,x7用非基变量x1,x2,x3,x5来代替，有
maxz??4M?(3?6M)x1?(?1?M)x2?(?1?3M)x3?Mx5
于是列出单纯形表： xB x4 x6 x7
b 11 3 1 4M x1 1 -4 -2 3-6M x2 -2 1 0 -1+M x3 1 2 x4 1 0 0 0 x5 ０ -1 0 -M x6 0 1 0 0 x7 0 0 1 0 1 -1+3M 15
xB x4 x6 x3 b 10 1 1 1+M x1 3 0 -2 1 x2 -2 x3 0 0 1 0 x4 1 0 0 0 x5 ０ -1 0 -M x6 0 1 0 0 x7 -1 -2 1 1-3M 1 0 -1+M xB x4 x2 x3 b 12 1 1 2 x1 x2 0 1 0 0 x3 0 0 1 0 x4 1 0 0 0 x5 -2 -1 0 -1 x6 2 1 0 1-M x7 -5 -2 1 -1-M 3 0 -2 1 xB x1 x2 x3 b 4 1 9 -2 **x1 1 0 0 0 *x2 0 1 0 0 **x3 0 0 1 0 **x4 1 3x5 ?2 3x6 2 3x7 5? 30 2 31? 3-1 ?4 31? 31 4 31?M 3-2 ?7 32-M 3故最优解为x1?4,x2?1,x3?9,x4?x5?x6?x7?0. z*?2。
3． 两阶段法
用计算机求解含人工变量的线性规划时，若M?0，则造成溢出，故介绍两阶段法。
第一阶段：
16
n?mminw?j?n?1?xj?a11x1?a12x2?...?a1nxn?xn?1?b1??xn?2?b2?a21x1?a22x2?...?a2nxn ?...??ax?ax?...?ax?xn?m?bmmnn?m11m22??xj?0,j?1,...,n?m 若w?0，则原问题无可行解；
若w?0，则原问题存在可行解。 第二阶段：
将第一阶段的最终单纯形表除去人工变量，将目标函数行的系数换成原问题的目标函数的系数，并且注意基变量要用非基变量来表示，用此作为第二阶段计算的初始单纯形表。 例2. 设有线性规划
maxz?3x1?x2?x3?11?x1?2x2?x3?x4??4x?x?2x?x5?3 ?123??x3?1??2x1?xj?0,j?1,...,5? 试用二阶段法求解。 解：第一阶段
minw?x6?x7?11?x1?2x2?x3?x4??4x?x?2x?x5?x6?3 ?123??x3?x7?1??2x1?xj?0,j?1,...,7?xB x4 x6 x7 b 11 3 1 -4 x1 1 -4 -2 6 x2 -2 1 0 -1 x3 1 2 x4 1 0 0 0 x5 ０ -1 0 1 x6 0 1 0 0 x7 0 0 1 0 1 -3 17
xB x4 x6 x3 b 10 1 1 -1 x1 3 0 -2 0 x2 -2 x3 0 0 1 0 x4 1 0 0 0 x5 ０ -1 0 1 x6 0 1 0 0 x7 -1 -2 1 3 1 0 -1 xB x4 x2 x3 b 12 1 1 0 x1 3 0 -2 0 x2 0 1 0 0 x3 0 0 1 0 x4 1 0 0 0 x5 -2 -1 0 0 x6 2 1 0 1 x7 -5 -2 1 1 第二阶段： xB x4 x2 x3
b 12 1 1 2 x1 x2 0 1 0 0 x3 0 0 1 0 x4 1 0 0 0 x5 -2 -1 0 -1 3 0 -2 1 18