第二章习题12、对于下面的线性规划问题，以()632,,A A A B =为基写出相对应的典式。

⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++-=++-=++-+-61,0108341242723..2min 63215214321321 j x x x x x x x x x x x x t s x x x j 解：由题可以知：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=100834010042001213A []000121-=TC取一个基()654A A AB =，即：⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡-=183004021B 且⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡---=834042213N[]012-=T B C []001=TN C在matlab 中可以计算得到：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--=-14740812104101B []T b B b 39531-==-1-=b C T B ⎥⎦⎤⎢⎣⎡-=--8321451T N T B C N B C 由()N TN T B T B x C N B C b C Z --=-1可得典式的目标函数：5418321451x x x Z +---=由b Nx B x N B =+-1可得：⎪⎪⎪⎩⎪⎪⎪⎨⎧-=+---=+++=++-3947422558121453412165415431521x x x x x x x x x x x 由此与题中线性规划问题相对应的典式为：⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥-=+---=+++=++-+---=6,,1,039474225581214534121..8321451min 65415431521541 j x x x x x x x x x x x x t s x x x Z j14、用单纯形法求解线面的线性规划问题，并在平面上画出迭代点走过的路线。

⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥≤≤+≤+≤+--=0,10443186052..2min 21221212121x x x x x x x x x t s x x z 解：由题先将题中线性规划问题化为标准形：⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥=+=++=++=++--=6,,1,010*********..2min 6252142132121 j x x x x x x x x x x x x t s x x z j 由此可写出A ，即为：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=100010010*********000152A则可以得出()6543A A A AB =是一个单位矩阵，且()010441860＞Tb =，所以基B 是可行基，6543,,,x x x x 为基变量，21,x x 为非基变量。

基B 对应的基本可行解为：()Tx 1044186000=，其目标函数值00=z 。

方程组b Ax =已是典式，得到一张单纯形表如下：1x 2x 3x 4x5x6xRHS2 1 0 0 0 0 0 3x 2 5 1 0 0 0 60 4x 1 1 0 1 0 0 18 5x 3* 1 0 0 1 0 44 6x 0 1 00 0 1 10由题可知，()21A A N =，[][]120000--==T N TB c c 检验数可由TN T B k c N B c -=-1ζ可得：21=ζ不是负数，则当前解不是最优解，1A 列中有三个元素大于零，取：344344,118,260min ,,min 313212111=⎭⎬⎫⎩⎨⎧=⎭⎬⎫⎩⎨⎧a b a b a b 故转轴元为31a ，1x 为进基变量，5x 为出基变量。

目前的新基为()6143ˆA A A A B =,进行旋转变换后得下表：1x 2x3x 4x 5x 6xRHS0 310 0 32-0 388-3x 0 3131 0 32-0 392 4x 0*320 1 31-0 310 5x 1 31 0 0 310 3446x 01 00 110它对应的基本可行解为:Tx ⎪⎭⎫⎝⎛=1003103920344,其目标函数值为3880-=z 。

但312=ζ为正数，仍不是最优解，此时以22a 为转轴元，2x 为进基变量，4x 为出基变量，进行旋转变化得下表：1x2x3x4x5x6xRHS0 0 0 21-21-0 6181-3x 00 1 213-23- 0 61194x 0 1 0 23 23-0 25 5x 1 0 0 21- 21 0 683 6x 023-211215它对应的基本可行解为：Tx ⎪⎭⎫ ⎝⎛-=21500611925683，目标函数值为61810-=z ，此时检验数向量ζ为负数，故为最优解。

16、用单纯形法求解下列线性规划问题：（1）、⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤-+≤+-≤+++--=3,2,1,020102603..2min 321321321321j x x x x x x x x x x t s x x x z j解：由题先将题中线性规划问题化为标准形：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+-+=++-=++++--=6,5,4,3,2,1,020102603..2min 632153214321321j x x x x x x x x x x x x x t s x x x z j由此可以得到矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--=100111010211001113A则可以得出()654A A AB =是一个单位矩阵，且()0201060＞Tb =，所以基B 是可行基，654,,x x x 为基变量，321,,x x x 为非基变量。

基B 对应的基本可行解为：()Tx 20106000=，其目标函数值00=z 。

由此写出最初的单纯性表：1x 2x 3x4x5x6xRHS2 1 -1 0 0 0 0 4x 3 1 1 1 0 0 60 5x 1* -1 2 0 1 0 10 6x 1 1 1 0 0 1 20由题可知，()321A A A N =，[][]112000--==T N TB c c 检验数可由TN T B k c N B c -=-1ζ可得：21=ζ不是负数，则当前解不是最优解，1A 列中有三个元素大于零，取：10120,110,360min ,,min 313212111=⎭⎬⎫⎩⎨⎧=⎭⎬⎫⎩⎨⎧a b a b a b故转轴元为21a ，1x 为进基变量，5x 为出基变量。

进行旋转变换后得下表：1x 2x 3x4x5x6xRHS0 3 -5 0 -2 0 -20 4x 0 4 -5 1 -3 0 30 1x 1 -1 2 0 1 0 10 6x 0 2* -30 -1 1 10它对应的基本可行解为:()Tx 101030=,其目标函数值为200-=z 。

但32=ζ为正数，仍不是最优解，此时以32a 为转轴元，2x 为进基变量，6x 为出基变量，进行旋转变化得下表：1x 2x 3x 4x5x 6x RHS0 021-21-23--354x 0 0 1 1 -1 -2 10 1x 1 0 210 115 2x 0123- 021-215它对应的基本可行解为：()Tx 0515=，目标函数值为350-=z ，此时检验数向量ζ为负数，故为最优解。

（3）、⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥=++=+-=-+=++-++-=7,,1,06010263..min 7636143265365321 j x x x x x x x x x x x x t s x x x x x z j解：由此可以得到矩阵⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡--=1100100010000100012100110300A则可以得出()7521A A A AB =是一个单位矩阵，且()060106＞Tb =，所以基B 是可行基，7521,,,x x x x 为基变量，643,,x x x 为非基变量。

基B 对应的基本可行解为：()Tx 60600100=，其目标函数值00=z 。

由此写出最初的单纯形表：1x2x 3x 4x5x6x7xRHS-1 1 -1 0 -1 1 0 0 1x 0 0 3 0 1 1 0 6 2x 0 1 2 -1 0 0 0 10 5x -1 0 0 0 0 1 0 0 7x 0 0 10 0 1 1 6由题可知，()643A A A N =，[][]1010111-=-=T N TB c c 检验数可由TN T B k c N B c -=-1ζ可得：14=ζ不是负数，则当前解不是最优解，故2x 为进基变量，5x 为出基变量。

进行旋转变换后得下表：1x 2x 3x4x5x6xRHS0 3 -5 0 -2 0 -20 4x 0 4 -5 1 -3 0 30 1x 1 -1 2 0 1 0 10 6x 0 2*-30 -1 1 10它对应的基本可行解为:()Tx 101030=,其目标函数值为200-=z 。

但32=ζ为正数，仍不是最优解，此时以32a 为转轴元，2x 为进基变量，6x 为出基变量，进行旋转变化得下表：1x 2x 3x4x5x6xRHS0 0 21-0 21-23--35 4x 0 0 1 1 -1 -2 10 1x 1 0 210 115 2x 0123- 021-215它对应的基本可行解为：()Tx 0515=，目标函数值为350-=z ，此时检验数向量ζ为负数，故为最优解。

18、写出下面线性规划的对偶规划⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥+≥+≥+≥++为自变量212121212121,4282334525..1010min x x x x x x x x x x t s x x解：由题可得()T c 1010=，()Tb 4235=，⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=28314125A ， 有定义可得原问题的线性规划问题的对偶规划为：()⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎪⎪⎭⎫⎝⎛101023428115..4235max 43214321w w w w t s w w w w 按分量形式写出的对偶规划为：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+++=++++++4,3,2,1,010********..4235max 432143214321j w w w w w w w w w t s w w w w j20、把线性规划问题：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+≤++0,,32152..min 321322131x x x x x x x t s x x 记为P ， （1） 用单纯形算法解P ；（2） 写出P 的对偶D ；（3） 写出P 的互补松紧条件，并利用他们解对偶D 。

解：（1）、由题将P 化为标准形式为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+=+++0,,,32152..min 43213242131x x x x x x x x x t s x x 由此可写出A ，即为：⎪⎪⎪⎭⎫⎝⎛=012101021A 则可以得出()31A A B =是一个单位矩阵，且()035＞Tb =，所以基B 是可行基，31,x x 为基变量，42,x x 为非基变量。