第二章习题
12、对于下面的线性规划问题，以B??A2,A3,A6?为基写出相对应的典式。
?minx1?2x2?x3??s.t.3x1?x2?2x3?x4?7???2x1?4x2?x5?12 ??4x?3x?8x?x?101236??xj?0,j?1?6?解：由题可以知：
?3?12100?? TA???240010??C??1?21000?
???438001??取一个基B??A4A5??120??3?12?A6?，即：B??400?且N???240?
???????381????438??TTCB???210? CN??100?
在matlab中可以计算得到：
1??00??4?1?1T?1B??0? b?B?1b??35?39?
8?2?7??4?1???4???5TT?1TCBb??1 CBBN?CN???4TT?1T由Z?CBb?CBBN?CNxN可得典式的目标函数：
123??? 8???513Z??1?x1?x4?x5
428由xB?B?1NxN?b可得：
1?1?x?x?x5?3?2124?11?5x?x?x?x5?5 ?13428?47?25?x?4x?x5?x6??394?214?由此与题中线性规划问题相对应的典式为：
513?minZ??1?x?x?x514?428??s.t.?11?x1?x2?x5?3??24? 511?x1?x3?x4?x5?5?428?257??x1?4x4?x5?x6??3924??xj?0,j?1,?,6?
14、用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。
?min?s.t.?????????z??2x1?x22x1?5x2?60x1?x2?183x1?x2?44 x2?10x1,x2?0?minz??2x1?x2?s.t.2x?5x?x?60123??x1?x2?x4?18? ?3x?x?x?44125??x2?x6?10?xj?0,j?1,?,6??解：由题先将题中线性规划问题化为标准形：
?2?1由此可写出A，即为：A???3??051111000010000100?0?? 0??1?则可以得出B??A3A4A5A6?是一个单位矩阵，且b??60184410?＞0，
T所以基B是可行基，x3,x4,x5,x6为基变量，x1,x2为非基变量。基B对应的基本可
T行解为：x??0060184410?，其目标函数值z0?0。方程组Ax?b已是
典式，得到一张单纯形表如下：
x x x
2 1 0 x 2 5 1 x 1 1 0 x 3* 1 0 x0 1 0
123x4
x5
x6
RHS
34560 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 60 18 44 10 由题可知，N??A1TA2?，cB??0000?cT?1? N???2T?1T检验数可由?k?cBBN?cN可得：?1?2不是负数，则当前解不是最优解，A1列
中有三个元素大于零，取：
?bbb??601844?44 min?1,2,3??min?,,???213?3?a11a21a31?故转轴元为a31，x1为进基变量，x5为出基变量。
???A目前的新基为B3
x3x1A4x2A1
A6?,进行旋转变换后得下表：
x x x x
3456RHS0 0 0 13 0 1 0 0 0 0 0 1 0 0 ?2323 0 0 0 0 1 ? 88313323??923103443 x41?313 1 x 0 x5613 1 0 10
9210?44?它对应的基本可行解为:x??0010?,其目标函数值为
33?3?z0??881。但?2?为正数，仍不是最优解，此时以a22为转轴元，x2为进基变33T量，x4为出基变量，进行旋转变化得下表：
3x1
x2
x3
x4
12x5
12x6
RHS0 0 0 1 0 0 0 1 0 0 0 ? ?0 0 0 0 1 ? 1816x 0 13?232 3?23?21212119652 x4 0 1 0 x51?2?32 836152x6
11915??835它对应的基本可行解为：x???00?，目标函数值为
62??62z0??181，此时检验数向量?为负数，故为最优解。 6T
16、用单纯形法求解下列线性规划问题：
?min??s.t.??（1）、????z??2x1?x2?x33x1?x2?x3?60x1?x2?2x3?10x1?x2?x3?20xj?0,j?1,2,3
解：由题先将题中线性规划问题化为标准形：
?min??s.t.??????
z??2x1?x2?x33x1?x2?x3?x4x1?x2?2x3x1?x2?x3?x5?60?10?x6?20
xj?0,j?1,2,3,4,5,6?311100?? 1?12010由此可以得到矩阵A??????11?1001??
则可以得出B??A4A5且b??601020?＞0，所以基BA6?是一个单位矩阵，
T是可行基，x4,x5,x6为基变量，x1,x2,x3为非基变量。基B对应的基本可行解为：
Tx??00061020?，其目标函数值z0?0。
由此写出最初的单纯性表：
x x
2 1 x 3 1 x 1* -1 x 1 1
124x3
x4
x5
x6
RHS
56-1 1 2 1 0 1 0 0 0 0 1 0 0 0 0 1 0 60 10 20 由题可知，N??A1A2TA3?，cB??000?cT?11? N???2T?1T检验数可由?k?cBBN?cN可得：?1?2不是负数，则当前解不是最优解，A1列
中有三个元素大于零，取：
?bbb??601020?min?1,2,3??min?,,??10
?311??a11a21a31?故转轴元为a21，x1为进基变量，x5为出基变量。 进行旋转变换后得下表：
x x
0 3 x 0 4 x 1 -1 x 0 2*
1241x3
x4
x5
x6
RHS
6-5 -5 2 -3 T0 1 0 0 -2 -3 1 -1 0 0 0 1 -20 30 10 10 它对应的基本可行解为:x??301010?,其目标函数值为z0??20。但?2?3为正数，仍不是最优解，此时以a32为转轴元，x2为进基变量，x6为出基变量，进行旋转变化得下表：
x x
12x3 x4
x5 x6 RHS
0 0 1?20 1?23?2-35