习题一1.1利用图解法求下列线性规划问题： （1）21x x z max +=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 5x 2x 2x x 3.t .s 212121 解：根据条件，可行域为下面图形中的阴影部分，，有图形可知，原问题在A 点取得最优值，最优值z=5（2）21x 6x z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+-≤+0x ,x 7x x 1x x 2.t .s 212121 解：图中阴影部分表示可行域，由图可知原问题在点A 处取得最优值，最优值z=-6.（3）21x 2x 3z max +=⎪⎪⎩⎪⎪⎨⎧≥-≥-≤+-0x ,x 4x 2x 1x x .t .s 212121 解：如图所示，可行域为图中阴影部分，易得原线性规划问题为无界解。

（4）21x 5x 2z min -=⎪⎪⎩⎪⎪⎨⎧≥≤+≥+0x ,x 2x x 6x 2x .t .s 212121 解：由图可知该线性规划可行域为空，则原问题无可行解。

1.2 对下列线性规划问题，找出所有的基解，基可行解，并求出最优解和最优值。

（1）4321x 6x 3x 2x 5z min -+-=⎪⎪⎩⎪⎪⎨⎧≥=+++=+++0x ,x ,x ,x 3x 2x x x 27x 4x 3x 2x .t .s 432143214321 解：易知1x 的系数列向量⎪⎪⎭⎫ ⎝⎛=21p 1，2x 的系数列向量⎪⎪⎭⎫ ⎝⎛=12p 2，3x 的系数列向量⎪⎪⎭⎫⎝⎛=13p 3，4x 的系数列向量⎪⎪⎭⎫⎝⎛=24p 4。

①因为21p ,p 线性无关，故有⎪⎩⎪⎨⎧--=+--=+43214321x 2x 3x x 2x 4x 37x 2x ，令非基变量为0x x 43==，得⎪⎪⎩⎪⎪⎨⎧=-=311x 31x 21，所以得到一个基解)0,0,311,31(x )1(-=是非基可行解； ②因为31p ,p 线性无关，可得基解)0,511,0,52(x)2(=，543z 2=；③因为41p ,p 线性无关，可得基解611,0,0,31(x )3(-=，是非基可行解；④因为32p ,p 线性无关，可得基解)0,1,2,0(x )4(=，1z 4-=；⑤因为42p ,p 线性相关，42x ,x 不能构成基变量； ⑥因为43p ,p 线性无关，可得基解)1,1,0,0(x )6(=，3z 6-=；所以)6()4()2(x ,x ,x是原问题的基可行解，)6(x 是最优解，最优值是3z -=。

（2）54321x x x 2x x z max -+-+=⎪⎪⎩⎪⎪⎨⎧=≥=++-=+++5,4,3,2,1i ,0x 4x x 2x 1x x x x .t .s i 5214321 解：易知1x 的系数列向量⎪⎪⎭⎫ ⎝⎛-=11p 1，2x 的系数列向量⎪⎪⎭⎫⎝⎛=21p 2，3x 的系数列向量⎪⎪⎭⎫ ⎝⎛=01p 3，4x 的系数列向量⎪⎪⎭⎫ ⎝⎛=01p 4，5x 的系数列向量⎪⎪⎭⎫⎝⎛=10p 5。

①因为21p ,p 线性无关，故有⎪⎩⎪⎨⎧-=+---=+5214321x 4x 2x x x 1x x ，令非基变量为0x x x 543===，得⎪⎪⎩⎪⎪⎨⎧=-=35x 32x 21，所以得到一个基解)0,0,0,35,32(x )1(-=，是非基可行解； ②因为31p ,p 线性无关，可得基解)0,0,5,0,4(x)2(-=，是非基可行解； ③因为41p ,p 线性无关，可得基解)0,5,0,0,4(x )3(-=，是非基可行解； ④因为51p ,p 线性无关，可得基解)5,0,0,0,1(x )4(=，4z 4-=；⑤因为32p ,p 线性相关，得基解)0,0.1,2,0(x)5(-=，是非基可行解；⑥因为42p ,p 线性无关，可得基解)0,1,0,2,0(x )6(-=，是非基可行解； ⑦因为52p ,p 线性无关，可得基解)2,0,0,1,0(x)7(=，1z 7-=；⑧因为43p ,p 线性相关，43x ,x 不能构成基变量； ⑨因为53p ,p 线性无关，可得基解)4,0,1,0,0(x)9(=，6z 9-=； ⑩因为54p ,p 线性无关，可得基解)4,1,0,0,0(x )10(=，3z 10-=；所以原线性规划的基可行解是)10()9()7()4(x ,x ,x ,x，最优解是)7(x ，最优值是1z -=。

1.3 用单纯形法求解下列线性规划问题； （1）21x 3x 2z max +=⎪⎪⎩⎪⎪⎨⎧≥≥+≤+0x ,x 2x x 5x 3x .t .s 212121 解：引入松弛变量3x ，剩余变量4x 和人工变量5x ，把原问题化为规范式521Mx x 3x 2z max -+=⎪⎪⎩⎪⎪⎨⎧=≥=+-+=++5...2,1i ,0x 2x x x x 5x x 3x .t .s i 5421321，其中M 无限大， 构造初始单纯形表并计算如下：1x 2x 3x 4x 5x2+M 3+M 0 -M 03x 1 3 1 0 0 5 5x1 1 0 -1 1 2以2x 作为换入基，3x 作为换成基，计算得以1x 为换入基，5x 作为换出基有以4x 换入，2x 换出有1x 2x 3x 4x 5x-3 -2 0 M 3---104x 0 2 1 1 -1 3 1x1 3 1 0 0 5根据单纯形表可知，原问题的最优解为)3,0,0,5(x *=，最优值为10z *= （2）321x 2x x z max -+=⎪⎪⎩⎪⎪⎨⎧≥≥+-≤-+0x ,x ,x 7x x 4x 5x x x 3.t .s 321321321 解：引入松弛变量4x ，剩余变量5x 和人工 变量6x ，把原问题规范化为6321Mx x 2x x z max --+= ⎪⎪⎩⎪⎪⎨⎧=≥=+-+-=+-+6...2,1i ,0x 7x x x x 4x 5x x x x 3.t .s i 6532143211x 2x 3x 4x 5x 6x1+M 1-4M -2+M 0 -M 04x3 1 -1 1 0 0 56x1 -4 1 0 -1 1 7以1x 作为换入基，4x 作为换出基有1x 2x 3x 4x 5x 6x以3x 为换入变量，6x 为换出变量，得 所以原问题最优解为)4,0,3(x *=，最优值为5z *-=。

（3）321x x 3x 2z min ++=⎪⎪⎩⎪⎪⎨⎧≥≥+≥++0x ,x ,x 6x 2x 38x 2x 4x .t .s 32121321 解：引入剩余变量4x ,5x 和人工变量6x ,7x ,利用两阶段法得到辅助线性规划76x x w max --=321'x x 3x 2z max ---=⎪⎪⎩⎪⎪⎨⎧=≥=+-+=+-++7...2,1i ,0x 6x x x 2x 38x x x 2x 4x .t .s i 752164321 构造初始单纯形表，并计算1x 2x 3x 4x 5x 6x 7x'z-2 -3 -1 0 0 0 0w 4 6 2 -1 -1 0 0 6x 1 42 -1 0 1 0 87x3 2 0 0 -1 0 1 6以2x 为换入变量，6x 为换出变量，得以1x 为换入变量，7x 为换出变量，得从单纯行表中可知，原问题有无限多个最优解，其中一个为)0,8.1,8.0(x *=，最优值为7z *=。

（4）321x 12x 15x 10z max ++=⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≥++≤++-≤++3,2,1j ,0x 5x x x 215x 15x 6x 59x x 3x 5.t .s j 321321321 解：引入松弛变量5,4x x ，剩余变量,6x ，人工变量7x ，将原问题化为规范式7321Mx x 12x 15x 10z max -++= ⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=+-++=+++-=+++7,...,2,1j ,0x 5x x x x x 215x x 15x 6x 59x x x 3x 5.t .s j 7632153214321 构造初始单纯形表并计算得以1x 为换入变量，4x 为换出变量，得以1x 为换入变量，4x 为换出变量1x 2x 3x 4x 5x 6x 7xz10+2M 15+M 12+M 0 0 -M 0 4x5 3 1 1 0 0 0 95x -5 6 15 0 1 0 0 157x2 1 1 0 0 -1 1 51x 2x 3x 4x 5x 6x 7x进一步计算知道，0x 7≠，所以原问题没有可行解。

1.4 设目标函数极大化的线性规划问题的单纯形表如下，表中无人工变量，当待定常数21121c ,c ,b ,a ,a 为何值时，表中的解：（1）为唯一最优解，（2）为多重解，（3）有无界解，（4）为退化解。

解：①当0c ,c ,0b 211<≥，为唯一最优解；②当0c ,0c 0c ,0c ,0b 21211=≤≤=≥或，为多重解； ③当0c ,0c ,0a ,0b 2121>≤≤≥，具有无界解； ④0c ,0a 0c ,0b 2211>>>=或，为退化的可行解。

1.5 某商店要制定某种商品第二季度的计划，已知该商店仓库容纳此种商品的容量不超过600件，3月底已存货200件，以后每月初进货一次。

假定各月份此种商品买进售出的单价如下，问各月进货、售货各多少件才能使利润最大？假设进货时受到仓库容量的限制，售货1x 2x3x4x 5x 6x1c 0 2c -9 0 00z2x1a12a-1 0 0 75x -1 0 -5 0 1 0 3 6x4 0 -2 1 0 11b时受到进货量的限制，不考虑货物存放在仓库的耗损与保管费用。

月份 买进单价/(元/件) 售出单价/(元/件)4 17 185 16.5 186 1719解：设i x 表示每个月进货量，i y 表示相应月份售货量，其中3,2,1i =，则有数学模型： 321321x 17x 5.16x 17y 19y 18y 18z max ---++=⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧=≥≤+-+-+-≤+-+-≤+--≤+-+--≤+--≤3,2,1i ,0y ,x 200y x y x y x 200y x y x 200y x 200600x y x y x 200600x y x 200600x .t .s i i 332211221111322112111 经计算，当600y ,600x ,600y ,500x ,600y ,400x 332211======时，即四月份进货400件，售货600件，五月份进货500件，售货600件，六月份进货600件售货 600件时，最大利润为6100元。