??minz?x1-x2?2x3??s..t2x1?x2?0x3??2??minz?x1-x2?2x4?2x5?-xs..2x1?x2?0x4?0x5?1 ?2x?t??22?-3，?-x ?x?0?2x?0x?0x?-31,x2?1245??x??x1,x2,x4,x5?03自由
??minz?x1-x2?2x4?2x5?0x6??s..t2x1?x2?0x4?0x5?0x6??2??x2x?x 1 ?2?0x4?0x56?-3??x1,x2,x4,x5,x6?0?A???2-1000??-1200-1??x??x?x1??1??x2???1?4?c???x2?
5???2??x6????0??
§2 图解法
例1 用图解法解线性规划
??maxz??x1?x2??s..t2x1?x2??2?x1 ?2x2?2 ??x1 ? x2?5??x1,x2?0 7
x2 (0,5) 2x1-x2=-2 -x1+x2=0 x1-2x2=2 (0,2) (-1,0) (2,0) (0,-1) (5,0) x1
x1+x2=5
z在(1,4)点达到最大值3。
例2 用图解法解线性规划
?min?t?s..??
x2 z?x1?5x2x1?2x2?8 x1? x2?4(0,4) x1-x2=4 x1-5x2=0 (4,0) (8,0) x1 x1+2x2=8 (0,-4) 8
例3 用图解法解线性规划
?min?s..?t????z??2x1?x2x1?x2?1
x1? 3x2??3x1,x2?0无最优解
关于可行域D与最优解的讨论：D＝?，无解、不可行；D≠?，无界；D≠?，有最优解。
§3 单纯形法解LP问题
1．单纯形方法
考虑标准形式的LP问题
?min?t?s..??z?cTxAx?b x?0
设r(A)=m，A的前m列为线性无关。(注意各向量、矩阵的维数)
将A分为左右两块，左边m列为可逆方阵B，右边记为N。(左面m列是不是一定可逆？)
对应将价值向量c和决策向量x的前m行与后n-m行分开，
9
?c?TA?[B,N]，c??B?,cT?[cB,cTN]，
?cN??x?Tx??B?,xT?[xB,xTN]
x?N??xB?Ax?b?[B,N]???b?BxB?NxN?b
?xN? xB?B?1b?B?1NxN
?xB?Tz?cx?[c,c]???cBxB?cTNxNx?N?TTBTNT?cB(B?1b?B?1NxN)?cTNxN，
T?1T?1?cBBb?(cBBN?cTN)xN?xB?T?1T?1?cBBb?[0,0,?,0,cBBN?cT]N??x?N?T?1令?T?[0,0,?,0,cBBN?cTN]，则
T?1z?cBBb??Tx，
且
10
T?1TT?1?T?[cBBB?cB,cBBN?cTN]T?1T?1T?[cBBB,cBBN]?[cB,cTN]。
?cBTB?1[B,N]?cT?cBTB?1A?cT
原LP问题变形为
?min?t?s..??T?1z?cBBb??TxxB?B?1b?B?1NxN x?0若取xN?0，则xB?B?1b,得一个满足等式约束的解
?B?1b?x???，
0??T?1其对应的指标值为 z?cTx?cBBb。
B称为基，
B的列称为基向量，
?B?1b?x???称为基本解，
0???B?1b?x????0时称为基本可行解，此时B称为可行基
?0?B?1b?0时称x为非退化的基本可行解。
下面假设我们要讨论的LP问题对所有的可行基B，都有B?1b?0。
11